emulator/opengl: Remove android::KeyedVector usage.

Replace it with a custom emugl::IdToObjectMap template
class that owns the objects, simplifying the code.

Change-Id: Id18319e8080211acebed814bc0d702fbaab3b245

6 files changed, 636 insertions, 146 deletions

diff --git a/emulator/opengl/shared/OpenglCodecCommon/GLSharedGroup.cpp b/emulator/opengl/shared/OpenglCodecCommon/GLSharedGroup.cpp
index a03f8c9..f317259 100644
--- a/emulator/opengl/shared/OpenglCodecCommon/GLSharedGroup.cpp
+++ b/emulator/opengl/shared/OpenglCodecCommon/GLSharedGroup.cpp
@@ -16,23 +16,20 @@
 
 #include "GLSharedGroup.h"
 
-/**** KeyedVector utilities ****/
-
-template <typename T>
-static void clearObjectMap(android::DefaultKeyedVector<GLuint, T>& v) {
-    for (size_t i = 0; i < v.size(); i++)
-        delete v.valueAt(i);
-    v.clear();
-}
-
 /**** BufferData ****/
 
 BufferData::BufferData() : m_size(0) {};
+
 BufferData::BufferData(GLsizeiptr size, void * data) : m_size(size)
 {
-    void * buffer = NULL;
-    if (size>0) buffer = m_fixedBuffer.alloc(size);
-    if (data) memcpy(buffer, data, size);
+    void* buffer = NULL;
+
+    if (size > 0) {
+        buffer = m_fixedBuffer.alloc(size);
+        if (data) {
+            memcpy(buffer, data, size);
+        }
+    }
 }
 
 /**** ProgramData ****/
@@ -223,49 +220,32 @@ bool ProgramData::detachShader(GLuint shader)
 /***** GLSharedGroup ****/
 
 GLSharedGroup::GLSharedGroup() :
-    m_buffers(android::DefaultKeyedVector<GLuint, BufferData*>(NULL)),
-    m_programs(android::DefaultKeyedVector<GLuint, ProgramData*>(NULL)),
-    m_shaders(android::DefaultKeyedVector<GLuint, ShaderData*>(NULL))
-{
-}
+    m_buffers(), m_programs(), m_shaders() {}
 
-GLSharedGroup::~GLSharedGroup()
-{
-    m_buffers.clear();
-    m_programs.clear();
-    clearObjectMap(m_buffers);
-    clearObjectMap(m_programs);
-    clearObjectMap(m_shaders);
-}
+GLSharedGroup::~GLSharedGroup() {}
 
 BufferData * GLSharedGroup::getBufferData(GLuint bufferId)
 {
     emugl::Mutex::AutoLock _lock(m_lock);
-    return m_buffers.valueFor(bufferId);
+    return m_buffers.get(bufferId);
 }
 
 void GLSharedGroup::addBufferData(GLuint bufferId, GLsizeiptr size, void * data)
 {
     emugl::Mutex::AutoLock _lock(m_lock);
-    m_buffers.add(bufferId, new BufferData(size, data));
+    m_buffers.set(bufferId, new BufferData(size, data));
 }
 
 void GLSharedGroup::updateBufferData(GLuint bufferId, GLsizeiptr size, void * data)
 {
     emugl::Mutex::AutoLock _lock(m_lock);
-    ssize_t idx = m_buffers.indexOfKey(bufferId);
-    if (idx >= 0) {
-        delete m_buffers.valueAt(idx);
-        m_buffers.editValueAt(idx) = new BufferData(size, data);
-    } else {
-        m_buffers.add(bufferId, new BufferData(size, data));
-    }
+    m_buffers.set(bufferId, new BufferData(size, data));
 }
 
 GLenum GLSharedGroup::subUpdateBufferData(GLuint bufferId, GLintptr offset, GLsizeiptr size, void * data)
 {
     emugl::Mutex::AutoLock _lock(m_lock);
-    BufferData * buf = m_buffers.valueFor(bufferId);
+    BufferData * buf = m_buffers.get(bufferId);
     if ((!buf) || (buf->m_size < offset+size) || (offset < 0) || (size<0)) return GL_INVALID_VALUE;
 
     //it's safe to update now
@@ -276,32 +256,20 @@ GLenum GLSharedGroup::subUpdateBufferData(GLuint bufferId, GLintptr offset, GLsi
 void GLSharedGroup::deleteBufferData(GLuint bufferId)
 {
     emugl::Mutex::AutoLock _lock(m_lock);
-    ssize_t idx = m_buffers.indexOfKey(bufferId);
-    if (idx >= 0) {
-        delete m_buffers.valueAt(idx);
-        m_buffers.removeItemsAt(idx);
-    }
+    ssize_t idx = m_buffers.remove(bufferId);
 }
 
 void GLSharedGroup::addProgramData(GLuint program)
 {
     emugl::Mutex::AutoLock _lock(m_lock);
-    ProgramData *pData = m_programs.valueFor(program);
-    if (pData)
-    {
-        m_programs.removeItem(program);
-        delete pData;
-    }
-
-    m_programs.add(program,new ProgramData());
+    m_programs.set(program, new ProgramData());
 }
 
 void GLSharedGroup::initProgramData(GLuint program, GLuint numIndexes)
 {
     emugl::Mutex::AutoLock _lock(m_lock);
-    ProgramData *pData = m_programs.valueFor(program);
-    if (pData)
-    {
+    ProgramData *pData = m_programs.get(program);
+    if (pData) {
         pData->initProgramData(numIndexes);
     }
 }
@@ -309,136 +277,133 @@ void GLSharedGroup::initProgramData(GLuint program, GLuint numIndexes)
 bool GLSharedGroup::isProgramInitialized(GLuint program)
 {
     emugl::Mutex::AutoLock _lock(m_lock);
-    ProgramData* pData = m_programs.valueFor(program);
-    if (pData)
-    {
-        return pData->isInitialized();
-    }
-    return false;
+    ProgramData* pData = m_programs.get(program);
+    return pData && pData->isInitialized();
 }
 
 void GLSharedGroup::deleteProgramData(GLuint program)
 {
     emugl::Mutex::AutoLock _lock(m_lock);
-    ProgramData *pData = m_programs.valueFor(program);
-    if (pData)
-        delete pData;
-    m_programs.removeItem(program);
+    m_programs.remove(program);
 }
 
 void GLSharedGroup::attachShader(GLuint program, GLuint shader)
 {
     emugl::Mutex::AutoLock _lock(m_lock);
-    ProgramData* programData = m_programs.valueFor(program);
-    ssize_t idx = m_shaders.indexOfKey(shader);
-    if (programData && idx >= 0) {
-        if (programData->attachShader(shader)) {
-            refShaderDataLocked(idx);
-        }
+    ProgramData* programData = m_programs.get(program);
+    if (programData && programData->attachShader(shader)) {
+        refShaderDataLocked(shader);
     }
 }
 
 void GLSharedGroup::detachShader(GLuint program, GLuint shader)
 {
     emugl::Mutex::AutoLock _lock(m_lock);
-    ProgramData* programData = m_programs.valueFor(program);
-    ssize_t idx = m_shaders.indexOfKey(shader);
-    if (programData && idx >= 0) {
-        if (programData->detachShader(shader)) {
-            unrefShaderDataLocked(idx);
-        }
+    ProgramData* programData = m_programs.get(program);
+    if (programData && programData->detachShader(shader)) {
+        unrefShaderDataLocked(shader);
     }
 }
 
-void GLSharedGroup::setProgramIndexInfo(GLuint program, GLuint index, GLint base, GLint size, GLenum type, const char* name)
+void GLSharedGroup::setProgramIndexInfo(GLuint program,
+                                        GLuint index,
+                                        GLint base,
+                                        GLint size,
+                                        GLenum type,
+                                        const char* name)
 {
     emugl::Mutex::AutoLock _lock(m_lock);
-    ProgramData* pData = m_programs.valueFor(program);
-    if (pData)
-    {
-        pData->setIndexInfo(index,base,size,type);
-
-        if (type == GL_SAMPLER_2D) {
-            size_t n = pData->getNumShaders();
-            for (size_t i = 0; i < n; i++) {
-                GLuint shaderId = pData->getShader(i);
-                ShaderData* shader = m_shaders.valueFor(shaderId);
-                if (!shader) continue;
-                ShaderData::StringList::iterator nameIter = shader->samplerExternalNames.begin();
-                ShaderData::StringList::iterator nameEnd  = shader->samplerExternalNames.end();
-                while (nameIter != nameEnd) {
-                    if (*nameIter == name) {
-                        pData->setIndexFlags(index, ProgramData::INDEX_FLAG_SAMPLER_EXTERNAL);
-                        break;
-                    }
-                    ++nameIter;
+    ProgramData* pData = m_programs.get(program);
+    if (!pData) {
+        return;
+    }
+    pData->setIndexInfo(index,base,size,type);
+
+    if (type == GL_SAMPLER_2D) {
+        size_t n = pData->getNumShaders();
+        for (size_t i = 0; i < n; i++) {
+            GLuint shaderId = pData->getShader(i);
+            ShaderData* shader = m_shaders.get(shaderId);
+            if (!shader) continue;
+            ShaderData::StringList::iterator nameIter =
+                    shader->samplerExternalNames.begin();
+            ShaderData::StringList::iterator nameEnd  =
+                    shader->samplerExternalNames.end();
+            while (nameIter != nameEnd) {
+                if (*nameIter == name) {
+                    pData->setIndexFlags(
+                            index,
+                            ProgramData::INDEX_FLAG_SAMPLER_EXTERNAL);
+                    break;
                 }
+                ++nameIter;
             }
         }
     }
 }
 
+
 GLenum GLSharedGroup::getProgramUniformType(GLuint program, GLint location)
 {
     emugl::Mutex::AutoLock _lock(m_lock);
-    ProgramData* pData = m_programs.valueFor(program);
-    GLenum type=0;
-    if (pData)
-    {
-        type = pData->getTypeForLocation(location);
-    }
-    return type;
+    ProgramData* pData = m_programs.get(program);
+    return pData ? pData->getTypeForLocation(location) : 0;
 }
 
 bool  GLSharedGroup::isProgram(GLuint program)
 {
     emugl::Mutex::AutoLock _lock(m_lock);
-    ProgramData* pData = m_programs.valueFor(program);
-    return (pData!=NULL);
+    ProgramData* pData = m_programs.get(program);
+    return (pData != NULL);
 }
 
 void GLSharedGroup::setupLocationShiftWAR(GLuint program)
 {
     emugl::Mutex::AutoLock _lock(m_lock);
-    ProgramData* pData = m_programs.valueFor(program);
+    ProgramData* pData = m_programs.get(program);
     if (pData) pData->setupLocationShiftWAR();
 }
 
-GLint GLSharedGroup::locationWARHostToApp(GLuint program, GLint hostLoc, GLint arrIndex)
+GLint GLSharedGroup::locationWARHostToApp(GLuint program,
+                                          GLint hostLoc,
+                                          GLint arrIndex)
 {
     emugl::Mutex::AutoLock _lock(m_lock);
-    ProgramData* pData = m_programs.valueFor(program);
-    if (pData) return pData->locationWARHostToApp(hostLoc, arrIndex);
-    else return hostLoc;
+    ProgramData* pData = m_programs.get(program);
+    return pData ? pData->locationWARHostToApp(hostLoc, arrIndex) : hostLoc;
 }
 
 GLint GLSharedGroup::locationWARAppToHost(GLuint program, GLint appLoc)
 {
     emugl::Mutex::AutoLock _lock(m_lock);
-    ProgramData* pData = m_programs.valueFor(program);
-    if (pData) return pData->locationWARAppToHost(appLoc);
-    else return appLoc;
+    ProgramData* pData = m_programs.get(program);
+    return pData ? pData->locationWARAppToHost(appLoc) : appLoc;
 }
 
 bool GLSharedGroup::needUniformLocationWAR(GLuint program)
 {
     emugl::Mutex::AutoLock _lock(m_lock);
-    ProgramData* pData = m_programs.valueFor(program);
-    if (pData) return pData->needUniformLocationWAR();
-    return false;
+    ProgramData* pData = m_programs.get(program);
+    return pData ? pData->needUniformLocationWAR() : false;
 }
 
-GLint GLSharedGroup::getNextSamplerUniform(GLuint program, GLint index, GLint* val, GLenum* target) const
+GLint GLSharedGroup::getNextSamplerUniform(GLuint program,
+                                           GLint index,
+                                           GLint* val,
+                                           GLenum* target) const
 {
     emugl::Mutex::AutoLock _lock(m_lock);
-    ProgramData* pData = m_programs.valueFor(program);
+    ProgramData* pData = m_programs.get(program);
     return pData ? pData->getNextSamplerUniform(index, val, target) : -1;
 }
 
-bool GLSharedGroup::setSamplerUniform(GLuint program, GLint appLoc, GLint val, GLenum* target)
+bool GLSharedGroup::setSamplerUniform(GLuint program,
+                                      GLint appLoc,
+                                      GLint val,
+                                      GLenum* target)
 {
     emugl::Mutex::AutoLock _lock(m_lock);
-    ProgramData* pData = m_programs.valueFor(program);
+    ProgramData* pData = m_programs.get(program);
     return pData ? pData->setSamplerUniform(appLoc, val, target) : false;
 }
 
@@ -446,44 +411,39 @@ bool GLSharedGroup::addShaderData(GLuint shader)
 {
     emugl::Mutex::AutoLock _lock(m_lock);
     ShaderData* data = new ShaderData;
-    if (data) {
-        if (m_shaders.add(shader, data) < 0) {
-            delete data;
-            data = NULL;
-        }
-        data->refcount = 1;
-    }
-    return data != NULL;
+    data->refcount = 1;
+    m_shaders.set(shader, data);
+    return true;
 }
 
 ShaderData* GLSharedGroup::getShaderData(GLuint shader)
 {
     emugl::Mutex::AutoLock _lock(m_lock);
-    return m_shaders.valueFor(shader);
+    ShaderData* data = m_shaders.get(shader);
+    if (data) {
+        data->refcount++;
+    }
+    return data;
 }
 
 void GLSharedGroup::unrefShaderData(GLuint shader)
 {
     emugl::Mutex::AutoLock _lock(m_lock);
-    ssize_t idx = m_shaders.indexOfKey(shader);
-    if (idx >= 0) {
-        unrefShaderDataLocked(idx);
-    }
+    unrefShaderDataLocked(shader);
 }
 
-void GLSharedGroup::refShaderDataLocked(ssize_t shaderIdx)
+void GLSharedGroup::refShaderDataLocked(GLuint shader)
 {
-    assert(shaderIdx >= 0 && shaderIdx <= m_shaders.size());
-    ShaderData* data = m_shaders.valueAt(shaderIdx);
-    data->refcount++;
+    ShaderData* data = m_shaders.get(shader);
+    if (data) {
+        data->refcount++;
+    }
 }
 
-void GLSharedGroup::unrefShaderDataLocked(ssize_t shaderIdx)
+void GLSharedGroup::unrefShaderDataLocked(GLuint shader)
 {
-    assert(shaderIdx >= 0 && shaderIdx <= m_shaders.size());
-    ShaderData* data = m_shaders.valueAt(shaderIdx);
-    if (--data->refcount == 0) {
-        delete data;
-        m_shaders.removeItemsAt(shaderIdx);
+    ShaderData* data = m_shaders.get(shader);
+    if (data && --data->refcount == 0) {
+        m_shaders.remove(shader);
     }
 }
diff --git a/emulator/opengl/shared/OpenglCodecCommon/GLSharedGroup.h b/emulator/opengl/shared/OpenglCodecCommon/GLSharedGroup.h
index 713e17e..0daa3a8 100644
--- a/emulator/opengl/shared/OpenglCodecCommon/GLSharedGroup.h
+++ b/emulator/opengl/shared/OpenglCodecCommon/GLSharedGroup.h
@@ -16,6 +16,7 @@
 #ifndef _GL_SHARED_GROUP_H_
 #define _GL_SHARED_GROUP_H_
 
+#include "emugl/common/id_to_object_map.h"
 #include "emugl/common/mutex.h"
 #include "emugl/common/pod_vector.h"
 #include "emugl/common/smart_ptr.h"
@@ -34,7 +35,6 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include "ErrorLog.h"
-#include <utils/KeyedVector.h>
 #include <utils/List.h>
 #include <utils/String8.h>
 #include "FixedBuffer.h"
@@ -101,13 +101,13 @@ struct ShaderData {
 
 class GLSharedGroup {
 private:
-    android::DefaultKeyedVector<GLuint, BufferData*> m_buffers;
-    android::DefaultKeyedVector<GLuint, ProgramData*> m_programs;
-    android::DefaultKeyedVector<GLuint, ShaderData*> m_shaders;
+    emugl::IdToObjectMap<BufferData> m_buffers;
+    emugl::IdToObjectMap<ProgramData> m_programs;
+    emugl::IdToObjectMap<ShaderData> m_shaders;
     mutable emugl::Mutex m_lock;
 
-    void refShaderDataLocked(ssize_t shaderIdx);
-    void unrefShaderDataLocked(ssize_t shaderIdx);
+    void refShaderDataLocked(GLuint shader);
+    void unrefShaderDataLocked(GLuint shader);
 
 public:
     GLSharedGroup();
diff --git a/emulator/opengl/shared/emugl/common/Android.mk b/emulator/opengl/shared/emugl/common/Android.mk
index 5f8fecb..ff98dd0 100644
--- a/emulator/opengl/shared/emugl/common/Android.mk
+++ b/emulator/opengl/shared/emugl/common/Android.mk
@@ -6,6 +6,7 @@ LOCAL_PATH := $(call my-dir)
 ### emugl_common host library ###########################################
 
 commonSources := \
+        id_to_object_map.cpp \
         lazy_instance.cpp \
         pod_vector.cpp \
         smart_ptr.cpp \
@@ -27,6 +28,7 @@ $(call emugl-end-module)
 ### emugl_common_unittests ##############################################
 
 host_commonSources := \
+    id_to_object_map_unittest.cpp \
     lazy_instance_unittest.cpp \
     pod_vector_unittest.cpp \
     mutex_unittest.cpp \
diff --git a/emulator/opengl/shared/emugl/common/id_to_object_map.cpp b/emulator/opengl/shared/emugl/common/id_to_object_map.cpp
new file mode 100644
index 0000000..597c9eb
--- /dev/null
+++ b/emulator/opengl/shared/emugl/common/id_to_object_map.cpp
@@ -0,0 +1,236 @@
+// 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/id_to_object_map.h"
+
+#include <stdlib.h>
+
+namespace emugl {
+
+namespace {
+
+typedef IdToObjectMapBase::KeyType KeyType;
+
+enum {
+    kMinShift = 3,
+    kMaxShift = 31,
+    kMinCapacity = (1 << kMinShift),
+    kLoadScale = 1024,
+    kMinLoad = kLoadScale/4,    // 25% minimum load.
+    kMaxLoad = kLoadScale*3/4,  // 75% maximum load.
+
+    kInvalidKey = IdToObjectMapBase::kMaxId + 1U,
+    kTombstone = IdToObjectMapBase::kMaxId + 2U,
+};
+
+// Return a number that indicates if the current |capacity| is appropriate
+// to hold |size| items in our map.
+// -1 -> the capacity is too small and needs to be increased.
+//  0 -> the capacity is ok.
+// +1 -> the capacity is too large and needs to be decreased.
+int capacityCompare(size_t shift, size_t size) {
+    size_t capacity = 1U << shift;
+    // Essentially, one can rewrite:
+    //   load < minLoad
+    // as:
+    //   size / capacity < minLoad
+    //   capacity * minLoad > size
+    if (capacity * kMinLoad  > size * kLoadScale)
+        return +1;
+
+    // Similarly, one can rewrite:
+    //   load > maxLoad
+    // as:
+    //   size / capacity > maxLoad
+    //   capacity * maxLoad < size
+    if (capacity * kMaxLoad < size * kLoadScale)
+        return -1;
+
+    return 0;
+}
+
+size_t probeKeys(const KeyType* keys, size_t shift, KeyType key) {
+    static const int kPrimes[] = {
+    1,          /* For 1 << 0 */
+    2,
+    3,
+    7,
+    13,
+    31,
+    61,
+    127,
+    251,
+    509,
+    1021,
+    2039,
+    4093,
+    8191,
+    16381,
+    32749,
+    65521,      /* For 1 << 16 */
+    131071,
+    262139,
+    524287,
+    1048573,
+    2097143,
+    4194301,
+    8388593,
+    16777213,
+    33554393,
+    67108859,
+    134217689,
+    268435399,
+    536870909,
+    1073741789,
+    2147483647  /* For 1 << 31 */
+    };
+
+    size_t slot = key % kPrimes[shift];
+    size_t step = 0;
+    for (;;) {
+        KeyType k = keys[slot];
+        if (k == kInvalidKey || k == kTombstone || k == key)
+            return slot;
+
+        step += 1;
+        slot = (slot + step) & (1U << shift);
+    }
+}
+
+}  // namespace
+
+IdToObjectMapBase::IdToObjectMapBase() :
+        mCount(0), mShift(kMinShift) {
+    size_t capacity = 1U << mShift;
+    mKeys = static_cast<KeyType*>(::calloc(sizeof(mKeys[0]), capacity));
+    mValues = static_cast<void**>(::calloc(sizeof(mValues[0]), capacity));
+    for (size_t n = 0; n < capacity; ++n) {
+        mKeys[n] = kInvalidKey;
+    }
+}
+
+IdToObjectMapBase::~IdToObjectMapBase() {
+    mShift = 0;
+    mCount = 0;
+    ::free(mKeys);
+    ::free(mValues);
+}
+
+bool IdToObjectMapBase::contains(KeyType key) const {
+    size_t slot = probeKeys(mKeys, mShift, key);
+    switch (mKeys[slot]) {
+        case kInvalidKey:
+        case kTombstone:
+            return false;
+        default:
+            ;
+    }
+    return true;
+}
+
+bool IdToObjectMapBase::find(KeyType key, void** value) const {
+    size_t slot = probeKeys(mKeys, mShift, key);
+    if (!isValidKey(mKeys[slot])) {
+        *value = NULL;
+        return false;
+    }
+    *value = mValues[slot];
+    return true;
+}
+
+void* IdToObjectMapBase::set(KeyType key, void* value) {
+    if (!value)
+        return remove(key);
+
+    size_t slot = probeKeys(mKeys, mShift, key);
+    void* result;
+    if (isValidKey(mKeys[slot])) {
+        result = mValues[slot];
+        mValues[slot] = value;
+    } else {
+        mKeys[slot] = key;
+        mValues[slot] = value;
+        result = NULL;
+        mCount++;
+        resize(mCount);
+    }
+    return result;
+}
+
+void* IdToObjectMapBase::remove(KeyType key) {
+    size_t slot = probeKeys(mKeys, mShift, key);
+    if (!isValidKey(mKeys[slot]))
+        return NULL;
+
+    void* result = mValues[slot];
+    mValues[slot] = NULL;
+    mKeys[slot] = kTombstone;
+    mCount--;
+    return result;
+}
+
+void IdToObjectMapBase::resize(size_t newSize) {
+    int ret = capacityCompare(mShift, newSize);
+    if (!ret)
+        return;
+
+    size_t oldCapacity = 1U << mShift;
+    size_t newShift = mShift;
+
+    if (ret < 0) {
+        // Capacity is too small and must be increased.
+        do {
+            if (newShift == kMaxShift)
+                break;
+            ++newShift;
+        } while (capacityCompare(newShift, newSize) < 0);
+    } else {
+        // Capacity is too large and must be decreased.
+        do {
+            if (newShift == kMinShift)
+                break;
+            newShift--;
+        } while (capacityCompare(newShift, newSize) > 0);
+    }
+    if (newShift == mShift)
+        return;
+
+    // Allocate new arrays.
+    size_t newCapacity = 1U << newShift;
+    KeyType* newKeys = static_cast<KeyType*>(
+            ::calloc(sizeof(newKeys[0]), newCapacity));
+    void** newValues = static_cast<void**>(
+            ::calloc(sizeof(newValues[0]), newCapacity));
+    for (size_t n = 0; n < newCapacity; ++n)
+        newKeys[n] = kInvalidKey;
+
+    // Copy old entries into new arrays.
+    for (size_t n = 0; n < oldCapacity; ++n) {
+        KeyType key = mKeys[n];
+        if (isValidKey(key)) {
+            size_t newSlot = probeKeys(newKeys, newShift, key);
+            newKeys[newSlot] = key;
+            newValues[newSlot] = mValues[n];
+        }
+    }
+
+    // Swap arrays, and get rid of old ones.
+    ::free(mKeys);
+    ::free(mValues);
+    mKeys = newKeys;
+    mValues = newValues;
+    mShift = newShift;
+}
+
+}  // namespace emugl
diff --git a/emulator/opengl/shared/emugl/common/id_to_object_map.h b/emulator/opengl/shared/emugl/common/id_to_object_map.h
new file mode 100644
index 0000000..e3d0a81
--- /dev/null
+++ b/emulator/opengl/shared/emugl/common/id_to_object_map.h
@@ -0,0 +1,176 @@
+// 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_ID_TO_OBJECT_MAP_H
+#define EMUGL_COMMON_ID_TO_OBJECT_MAP_H
+
+#include <stddef.h>
+
+namespace emugl {
+
+// Base implementation class for IdToObjectMap template.
+// Used to reduce template-instanciated code generation.
+class IdToObjectMapBase {
+public:
+    // The type of keys in this map.
+    typedef unsigned KeyType;
+
+    // Values higher than kMaxId cannot be used as map keys.
+    enum {
+        kMaxId = 0xfffffffdU,
+    };
+
+    static inline bool isValidKey(KeyType key) {
+        return key <= kMaxId;
+    }
+
+protected:
+    IdToObjectMapBase();
+
+    ~IdToObjectMapBase();
+
+    void clear();
+
+    // Return size
+    inline size_t size() const { return mCount; }
+
+    inline size_t capacity() const { return 1U << mShift; }
+
+    // Return true iff the map contains a given key.
+    bool contains(KeyType key) const;
+
+    // Find a value associated with a given |key| in the map.
+    // On success, return true and sets |*value| to the value/pointer,
+    // which is _still_ owned by the map.
+    // On failure, return false and sets |*value| to NULL.
+    bool find(KeyType key, void** value) const;
+
+    // Associate a value with a given |key| in the map.
+    // Return the old value for the key, if any. Caller is responsible
+    // for freeing it.
+    void* set(KeyType key, void* value);
+
+    // Remove the value associated with a given |key|.
+    // Return the old value, if any. Caller is responsible for
+    // freeing it.
+    void* remove(KeyType key);
+
+    size_t mCount;
+    size_t mShift;
+    KeyType* mKeys;
+    void** mValues;
+
+private:
+    // Resize the map if needed to ensure it can hold at least |newSize|
+    // entries.
+    void resize(size_t newSize);
+};
+
+// A templated data container that acts as a dictionary mapping unsigned
+// integer keys to heap-allocated objects of type T. The dictionary
+// owns the objects associated with its keys, and automatically destroys
+// them when it is destroyed, or during replacement or removal.
+template <class T>
+class IdToObjectMap : public IdToObjectMapBase {
+public:
+    // Initialize an empty instance.
+    IdToObjectMap() : IdToObjectMapBase() {}
+
+    // Destroy this instance.
+    ~IdToObjectMap() {
+        clear();
+    }
+
+    // Return the number of items in this map.
+    inline size_t size() const { return IdToObjectMapBase::size(); }
+
+    // Return true iff the map is empty.
+    inline bool empty() const { return !IdToObjectMapBase::size(); }
+
+    // Remove all items from the map.
+    void clear();
+
+    // Returns true iff the dictionary contains a value for |key|.
+    inline bool contains(KeyType key) const {
+        return IdToObjectMapBase::contains(key);
+    }
+
+    // Find the value corresponding to |key| in this map.
+    // On success, return true, and sets |*value| to point to the
+    // value (still owned by the instance). On failure, return false.
+    inline bool find(KeyType key, T** value) const {
+        return IdToObjectMapBase::find(key, reinterpret_cast<void**>(value));
+    }
+
+    // Return the value associated with a given |key|, or NULL if it is
+    // not in the map. Result is still owned by the map.
+    inline T* get(KeyType key) const {
+        T* result = NULL;
+        this->find(key, &result);
+        return result;
+    }
+
+    // Associate |value| with a given |key|. Returns true if a previous
+    // value was replaced, and false if this is the first time a value
+    // was associated with the given key. IMPORTANT: This transfers
+    // ownership of |value| to the map instance. In case of replacement,
+    // the old value is automatically destroyed. Using NULL as the value
+    // is equivalent to calling remove().
+    bool set(KeyType key, T* value);
+
+    // Remove any value associated with |key|.
+    // Return true iff a value was associated with the key and destroyed
+    // by this function, false if there was no value associated with the
+    // key (or if it was NULL).
+    bool remove(KeyType key);
+};
+
+template <class T>
+void IdToObjectMap<T>::clear() {
+    size_t n = capacity();
+    while (n > 0) {
+        --n;
+        if (!isValidKey(mKeys[n]))
+            continue;
+
+        delete static_cast<T*>(mValues[n]);
+        mValues[n] = NULL;
+        mKeys[n] = kMaxId + 1U;
+    }
+    mCount = 0;
+}
+
+template <class T>
+bool IdToObjectMap<T>::set(KeyType key, T* value) {
+    T* oldValue = static_cast<T*>(IdToObjectMapBase::set(key, value));
+    if (!oldValue) {
+        return false;
+    }
+    delete oldValue;
+    return true;
+}
+
+template <class T>
+bool IdToObjectMap<T>::remove(KeyType key) {
+    T* oldValue = static_cast<T*>(IdToObjectMapBase::remove(key));
+    if (!oldValue)
+        return false;
+    delete oldValue;
+    return true;
+}
+
+}  // namespace emugl
+
+
+#endif  // EMUGL_COMMON_ID_TO_OBJECT_MAP_H
diff --git a/emulator/opengl/shared/emugl/common/id_to_object_map_unittest.cpp b/emulator/opengl/shared/emugl/common/id_to_object_map_unittest.cpp
new file mode 100644
index 0000000..50740be
--- /dev/null
+++ b/emulator/opengl/shared/emugl/common/id_to_object_map_unittest.cpp
@@ -0,0 +1,116 @@
+// 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/id_to_object_map.h"
+
+#include <gtest/gtest.h>
+
+namespace emugl {
+
+namespace {
+
+typedef IdToObjectMapBase::KeyType KeyType;
+
+class Foo {
+public:
+    Foo() : mVal(0) {}
+    Foo(int val) : mVal(val) {}
+    ~Foo() {}
+    int val() const { return mVal; }
+    void setVal(int val) { mVal = val; }
+private:
+    int mVal;
+};
+
+}  // namespace
+
+TEST(IdToObjectMap, Empty) {
+    IdToObjectMap<Foo> map;
+    EXPECT_TRUE(map.empty());
+    EXPECT_EQ(0U, map.size());
+}
+
+TEST(IdToObjectMap, SetIntegerRange) {
+    IdToObjectMap<Foo> map;
+    KeyType kMax = 10000;
+
+    // Add all items in the map.
+    for (KeyType n = 0; n < kMax; ++n) {
+        EXPECT_FALSE(map.set(n, new Foo(n))) << "For key " << n;
+    }
+
+    // Check final size.
+    EXPECT_EQ(static_cast<size_t>(kMax), map.size());
+
+    // Find all items in the map.
+    for (KeyType n = 0; n < kMax; ++n) {
+        EXPECT_TRUE(map.contains(n)) << "For key " << n;
+        Foo* foo = NULL;
+        EXPECT_TRUE(map.find(n, &foo)) << "For key " << n;
+        if (foo) {
+            EXPECT_EQ(static_cast<int>(n), foo->val()) << "For key " << n;
+        }
+    }
+}
+
+TEST(IdToObjectMap, RemoveAll) {
+    IdToObjectMap<Foo> map;
+    KeyType kMax = 10000;
+
+    // Add all items in the map.
+    for (KeyType n = 0; n < kMax; ++n) {
+        EXPECT_FALSE(map.set(n, new Foo(n))) << "For key " << n;
+    }
+
+    EXPECT_EQ(static_cast<size_t>(kMax), map.size());
+
+    for (KeyType n = 0; n < kMax; ++n) {
+        EXPECT_TRUE(map.remove(n)) << "For key " << n;
+    }
+    EXPECT_EQ(0U, map.size());
+}
+
+TEST(IdToObjectMap, RemoveOdd) {
+    IdToObjectMap<Foo> map;
+    KeyType kMax = 10000;
+
+    // Add all items in the map.
+    for (KeyType n = 0; n < kMax; ++n) {
+        EXPECT_FALSE(map.set(n, new Foo(n))) << "For key " << n;
+    }
+
+    EXPECT_EQ(static_cast<size_t>(kMax), map.size());
+
+    for (KeyType n = 0; n < kMax; ++n) {
+        if (n & 1) {
+            EXPECT_TRUE(map.remove(n)) << "For key " << n;
+        }
+    }
+    EXPECT_EQ(static_cast<size_t>(kMax / 2), map.size());
+
+    for (KeyType n = 0; n < kMax; ++n) {
+        if (n & 1) {
+            EXPECT_FALSE(map.contains(n)) << "For key " << n;
+        } else {
+            EXPECT_TRUE(map.contains(n)) << "For key " << n;
+            Foo* foo = NULL;
+            EXPECT_TRUE(map.find(n, &foo)) << "For key " << n;
+            if (foo) {
+                EXPECT_EQ(static_cast<int>(n), foo->val());
+            }
+        }
+    }
+}
+
+}  // namespace emugl