diff options
Diffstat (limited to 'emulator/opengl/shared/emugl')
4 files changed, 530 insertions, 0 deletions
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 |