emulator/opengl: Add UniqueIntegerMap class.

This helper class will be used by future patches to map arbitraty
opaque 'void*' values (e.g. EGLImage values) to 32-bit unique values
that can be sent through the wire protocol.

Change-Id: I5b17a1f230e5f9f8b905af66ba79b312f3f01e55

3 files changed, 329 insertions, 0 deletions

diff --git a/emulator/opengl/shared/emugl/common/Android.mk b/emulator/opengl/shared/emugl/common/Android.mk
index 6aaa0d9..f481c0c 100644
--- a/emulator/opengl/shared/emugl/common/Android.mk
+++ b/emulator/opengl/shared/emugl/common/Android.mk
@@ -49,6 +49,7 @@ host_commonSources := \
     smart_ptr_unittest.cpp \
     thread_store_unittest.cpp \
     thread_unittest.cpp \
+    unique_integer_map_unittest.cpp \
 
 $(call emugl-begin-host-executable,emugl_common_host_unittests)
 LOCAL_SRC_FILES := $(host_commonSources)
diff --git a/emulator/opengl/shared/emugl/common/unique_integer_map.h b/emulator/opengl/shared/emugl/common/unique_integer_map.h
new file mode 100644
index 0000000..720aceb
--- /dev/null
+++ b/emulator/opengl/shared/emugl/common/unique_integer_map.h
@@ -0,0 +1,225 @@
+// Copyright (C) 2014 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef EMUGL_COMMON_UNIQUE_INTEGER_MAP_H
+#define EMUGL_COMMON_UNIQUE_INTEGER_MAP_H
+
+#include "emugl/common/pod_vector.h"
+
+#include <stdint.h>
+
+namespace emugl {
+
+// Helper template class that implements a bi-directional mapping between
+// two integer types |A| and |B|. More specifically:
+//
+// - The map allocates values of type |B| when a key of type |A| is entered
+//   in the map.
+//
+// - keys and values cannot be 0, which is reserved (i.e. means 'invalid').
+//
+// This is used in EmuGL to map liberal 'void*' values (e.g. EGLimages ones)
+// to unique 32-bit IDs that can be written to / read from the wire protocol.
+template <typename A, typename B>
+class UniqueIntegerMap {
+public:
+    UniqueIntegerMap() : mForwardPairs(), mBackwardPairs() {}
+    ~UniqueIntegerMap() {}
+
+    // Return true iff the map is empty.
+    const bool empty() const { return mForwardPairs.empty(); }
+
+    // Return the number of (key,value) pairs in the map.
+    size_t size() const { return mForwardPairs.size(); }
+
+    // Find the value associated with |key| in the map.
+    // Returns 0 in case of failure, or if |key| is 0.
+    B find(const A key) const;
+
+    // Find the key associated with a given |value| in the map.
+    // Returns 0 if |value| is 0, or in case of failure.
+    A findKeyFor(const B value) const;
+
+    // Add |key| to the map and return an automatically-allocated
+    // unique value for it. Return 0 if |key| is 0.
+    B add(const A key);
+
+    // Delete the entry associated with a given |key|. The
+    // corresponding value may be recycled by future calls to add().
+    void del(const A key);
+
+private:
+    typedef struct {
+        A first;
+        B second;
+    } ForwardPair;
+
+    typedef struct {
+        B first;
+        A second;
+    } BackwardPair;
+
+    size_t findKeyIndexPlusOne(const A key) const;
+    size_t findValueIndexPlusOne(const B value) const;
+
+    B allocValue();
+    void freeValue(B value);
+
+    PodVector<ForwardPair> mForwardPairs;
+    PodVector<BackwardPair> mBackwardPairs;
+
+    B mLastValue;
+    PodVector<B> mFreeValues;
+};
+
+template <typename A, typename B>
+B UniqueIntegerMap<A,B>::find(const A key) const {
+    size_t keyIndex = findKeyIndexPlusOne(key);
+    if (!keyIndex) {
+        return 0;
+    }
+    return mForwardPairs[keyIndex - 1U].second;
+}
+
+template <typename A, typename B>
+A UniqueIntegerMap<A,B>::findKeyFor(const B value) const {
+    size_t valueIndex = findValueIndexPlusOne(value);
+    if (!valueIndex) {
+        return 0;
+    }
+    return mBackwardPairs[valueIndex - 1U].second;
+}
+
+template <typename A, typename B>
+B UniqueIntegerMap<A,B>::add(const A key) {
+    // Binary search to find the proper insertion point for the key.
+    // Also checks that the key isn't already in the set.
+    size_t min = 0;
+    size_t max = mForwardPairs.size();
+    while (min < max) {
+        size_t mid = min + ((max - min) >> 1);
+        A midKey = mForwardPairs[mid].first;
+        if (midKey < key) {
+            min = mid + 1U;
+        } else if (midKey > key) {
+            max = mid;
+        } else {
+            // Already in the set.
+            return 0;
+        }
+    }
+
+    // Generate new unique value
+    B value = allocValue();
+
+    ForwardPair* pair = mForwardPairs.emplace(min);
+    pair->first = key;
+    pair->second = value;
+
+    // Binary search to find proper insertion point for the value.
+    min = 0;
+    max = mBackwardPairs.size();
+    while (min < max) {
+        size_t mid = min + ((max - min) >> 1);
+        B midValue = mBackwardPairs[mid].first;
+        if (midValue < value) {
+            min = mid + 1U;
+        } else {
+            max = mid;
+        }
+    }
+
+    BackwardPair* backPair = mBackwardPairs.emplace(min);
+    backPair->first = value;
+    backPair->second = key;
+
+    return value;
+}
+
+template <typename A, typename B>
+void UniqueIntegerMap<A,B>::del(const A key) {
+    size_t keyIndex = findKeyIndexPlusOne(key);
+    if (!keyIndex) {
+        return;
+    }
+    B value = mForwardPairs[keyIndex - 1U].second;
+    size_t valueIndex = findValueIndexPlusOne(value);
+    mForwardPairs.remove(keyIndex - 1U);
+    mBackwardPairs.remove(valueIndex - 1U);
+    freeValue(value);
+}
+
+template <typename A, typename B>
+size_t UniqueIntegerMap<A,B>::findKeyIndexPlusOne(const A key) const {
+    // Binary search in forward pair array.
+    size_t min = 0;
+    size_t max = mForwardPairs.size();
+    while (min < max) {
+        size_t mid = min + ((max - min) >> 1);
+        A midKey = mForwardPairs[mid].first;
+        if (midKey < key) {
+            min = mid + 1U;
+        } else if (midKey > key) {
+            max = mid;
+        } else {
+            return mid + 1U;
+        }
+    }
+    return 0U;
+}
+
+template <typename A, typename B>
+size_t UniqueIntegerMap<A,B>::findValueIndexPlusOne(const B value) const {
+    // Binary search in revere pair array.
+    size_t min = 0;
+    size_t max = mBackwardPairs.size();
+    while (min < max) {
+        size_t mid = min + ((max - min) >> 1);
+        B midValue = mBackwardPairs[mid].first;
+        if (midValue < value) {
+            min = mid + 1U;
+        } else if (midValue > value) {
+            max = mid;
+        } else {
+            return mid + 1U;
+        }
+    }
+    return 0U;
+}
+
+template <typename A, typename B>
+B UniqueIntegerMap<A,B>::allocValue() {
+    if (!mFreeValues.empty()) {
+        B result = mFreeValues[0];
+        mFreeValues.pop();
+        return result;
+    }
+    return ++mLastValue;
+}
+
+template <typename A, typename B>
+void UniqueIntegerMap<A,B>::freeValue(B value) {
+    if (!value) {
+        return;
+    }
+    if (value == mLastValue) {
+        mLastValue--;
+        return;
+    }
+    mFreeValues.append(value);
+}
+
+}  // namespace emugl
+
+#endif  // EMUGL_COMMON_INTEGER_MAP_H
diff --git a/emulator/opengl/shared/emugl/common/unique_integer_map_unittest.cpp b/emulator/opengl/shared/emugl/common/unique_integer_map_unittest.cpp
new file mode 100644
index 0000000..8aee013
--- /dev/null
+++ b/emulator/opengl/shared/emugl/common/unique_integer_map_unittest.cpp
@@ -0,0 +1,103 @@
+// Copyright (C) 2014 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "emugl/common/unique_integer_map.h"
+
+#include <gtest/gtest.h>
+
+#include <stdio.h>
+
+namespace emugl {
+
+typedef UniqueIntegerMap<uintptr_t,uint32_t> MyMap;
+
+TEST(UniqueIntegerMap, Empty) {
+    MyMap map;
+
+    EXPECT_TRUE(map.empty());
+    EXPECT_EQ(0U, map.size());
+    EXPECT_EQ(0U, map.find(0U));
+    EXPECT_EQ(0U, map.find(1U));
+    EXPECT_EQ(0U, map.find(2U));
+    EXPECT_EQ(0U, map.find(4U));
+}
+
+TEST(UniqueIntegerMap, AddOne) {
+    MyMap map;
+    uintptr_t key1 = 1U;
+    uint32_t val1 = map.add(key1);
+
+    EXPECT_NE(0U, val1);
+    EXPECT_EQ(val1, map.find(key1));
+    EXPECT_EQ(key1, map.findKeyFor(val1));
+
+    EXPECT_FALSE(map.empty());
+    EXPECT_EQ(1U, map.size());
+
+    EXPECT_EQ(0U, map.find(0));
+    EXPECT_EQ(0U, map.findKeyFor(0));
+
+    EXPECT_EQ(0U, map.find(key1 + 1));
+    EXPECT_EQ(0U, map.findKeyFor(val1 + 1));
+}
+
+TEST(UniqueIntegerMap, AddMultiple) {
+    MyMap map;
+    const size_t kCount = 100;
+    const size_t kKeyMultiplier = 3U;  // must be >= 2.
+    uint32_t values[kCount];
+
+    for (size_t n = 0; n < kCount; ++n) {
+        uintptr_t key = 1U + n * kKeyMultiplier;
+        values[n] = map.add(key);
+        EXPECT_NE(0U, values[n]) << "key #" << n;
+    }
+
+    EXPECT_EQ(kCount, map.size());
+
+    for (size_t n = 0; n < kCount; ++n) {
+        uintptr_t key = 1U + n * kKeyMultiplier;
+        EXPECT_EQ(values[n], map.find(key)) << "key #" << n;
+        EXPECT_EQ(0U, map.find(key + 1U)) << "key #" << n;
+    }
+
+    for (size_t n = 0; n < kCount; ++n) {
+        uintptr_t key = 1U + n * kKeyMultiplier;
+        EXPECT_EQ(key, map.findKeyFor(values[n]));
+    }
+}
+
+TEST(UniqueIntegerMap, Del) {
+    MyMap map;
+    const size_t kCount = 100;
+    const size_t kKeyMultiplier = 3U;  // must be >= 2.
+    uint32_t values[kCount];
+
+    for (size_t n = 0; n < kCount; ++n) {
+        uintptr_t key = 1U + n * kKeyMultiplier;
+        values[n] = map.add(key);
+    }
+
+    for (size_t n = 0; n < kCount; ++n) {
+        uintptr_t key = 1U + n * kKeyMultiplier;
+        map.del(key);
+        EXPECT_EQ(kCount - 1U - n, map.size());
+        EXPECT_EQ(0U, map.find(key));
+        EXPECT_EQ(0U, map.findKeyFor(values[n]));
+    }
+
+    EXPECT_TRUE(map.empty());
+}
+
+}  // namespace emugl