1 // Copyright (C) 2014 The Android Open Source Project 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef EMUGL_COMMON_ID_TO_OBJECT_MAP_H 16 #define EMUGL_COMMON_ID_TO_OBJECT_MAP_H 17 18 #include <stddef.h> 19 20 namespace emugl { 21 22 // Base implementation class for IdToObjectMap template. 23 // Used to reduce template-instanciated code generation. 24 class IdToObjectMapBase { 25 public: 26 // The type of keys in this map. 27 typedef unsigned KeyType; 28 29 // Values higher than kMaxId cannot be used as map keys. 30 enum { 31 kMaxId = 0xfffffffdU, 32 }; 33 34 static inline bool isValidKey(KeyType key) { 35 return key <= kMaxId; 36 } 37 38 protected: 39 IdToObjectMapBase(); 40 41 ~IdToObjectMapBase(); 42 43 void clear(); 44 45 // Return size 46 inline size_t size() const { return mCount; } 47 48 inline size_t capacity() const { return 1U << mShift; } 49 50 // Return true iff the map contains a given key. 51 bool contains(KeyType key) const; 52 53 // Find a value associated with a given |key| in the map. 54 // On success, return true and sets |*value| to the value/pointer, 55 // which is _still_ owned by the map. 56 // On failure, return false and sets |*value| to NULL. 57 bool find(KeyType key, void** value) const; 58 59 // Associate a value with a given |key| in the map. 60 // Return the old value for the key, if any. Caller is responsible 61 // for freeing it. 62 void* set(KeyType key, void* value); 63 64 // Remove the value associated with a given |key|. 65 // Return the old value, if any. Caller is responsible for 66 // freeing it. 67 void* remove(KeyType key); 68 69 size_t mCount; 70 size_t mShift; 71 KeyType* mKeys; 72 void** mValues; 73 74 private: 75 // Resize the map if needed to ensure it can hold at least |newSize| 76 // entries. 77 void resize(size_t newSize); 78 }; 79 80 // A templated data container that acts as a dictionary mapping unsigned 81 // integer keys to heap-allocated objects of type T. The dictionary 82 // owns the objects associated with its keys, and automatically destroys 83 // them when it is destroyed, or during replacement or removal. 84 template <class T> 85 class IdToObjectMap : public IdToObjectMapBase { 86 public: 87 // Initialize an empty instance. 88 IdToObjectMap() : IdToObjectMapBase() {} 89 90 // Destroy this instance. 91 ~IdToObjectMap() { 92 clear(); 93 } 94 95 // Return the number of items in this map. 96 inline size_t size() const { return IdToObjectMapBase::size(); } 97 98 // Return true iff the map is empty. 99 inline bool empty() const { return !IdToObjectMapBase::size(); } 100 101 // Remove all items from the map. 102 void clear(); 103 104 // Returns true iff the dictionary contains a value for |key|. 105 inline bool contains(KeyType key) const { 106 return IdToObjectMapBase::contains(key); 107 } 108 109 // Find the value corresponding to |key| in this map. 110 // On success, return true, and sets |*value| to point to the 111 // value (still owned by the instance). On failure, return false. 112 inline bool find(KeyType key, T** value) const { 113 return IdToObjectMapBase::find(key, reinterpret_cast<void**>(value)); 114 } 115 116 // Return the value associated with a given |key|, or NULL if it is 117 // not in the map. Result is still owned by the map. 118 inline T* get(KeyType key) const { 119 T* result = NULL; 120 this->find(key, &result); 121 return result; 122 } 123 124 // Associate |value| with a given |key|. Returns true if a previous 125 // value was replaced, and false if this is the first time a value 126 // was associated with the given key. IMPORTANT: This transfers 127 // ownership of |value| to the map instance. In case of replacement, 128 // the old value is automatically destroyed. Using NULL as the value 129 // is equivalent to calling remove(). 130 bool set(KeyType key, T* value); 131 132 // Remove any value associated with |key|. 133 // Return true iff a value was associated with the key and destroyed 134 // by this function, false if there was no value associated with the 135 // key (or if it was NULL). 136 bool remove(KeyType key); 137 }; 138 139 template <class T> 140 void IdToObjectMap<T>::clear() { 141 size_t n = capacity(); 142 while (n > 0) { 143 --n; 144 if (!isValidKey(mKeys[n])) 145 continue; 146 147 delete static_cast<T*>(mValues[n]); 148 mValues[n] = NULL; 149 mKeys[n] = kMaxId + 1U; 150 } 151 mCount = 0; 152 } 153 154 template <class T> 155 bool IdToObjectMap<T>::set(KeyType key, T* value) { 156 T* oldValue = static_cast<T*>(IdToObjectMapBase::set(key, value)); 157 if (!oldValue) { 158 return false; 159 } 160 delete oldValue; 161 return true; 162 } 163 164 template <class T> 165 bool IdToObjectMap<T>::remove(KeyType key) { 166 T* oldValue = static_cast<T*>(IdToObjectMapBase::remove(key)); 167 if (!oldValue) 168 return false; 169 delete oldValue; 170 return true; 171 } 172 173 } // namespace emugl 174 175 176 #endif // EMUGL_COMMON_ID_TO_OBJECT_MAP_H 177