1 2 /* 3 * Copyright 2010 Google Inc. 4 * 5 * Use of this source code is governed by a BSD-style license that can be 6 * found in the LICENSE file. 7 */ 8 9 10 11 #ifndef GrTHashCache_DEFINED 12 #define GrTHashCache_DEFINED 13 14 #include "GrTypes.h" 15 #include "SkTDArray.h" 16 17 // GrTDefaultFindFunctor implements the default find behavior for 18 // GrTHashTable (i.e., return the first resource that matches the 19 // provided key) 20 template <typename T> class GrTDefaultFindFunctor { 21 public: 22 // always accept the first element examined 23 bool operator()(const T*) const { return true; } 24 }; 25 26 /** 27 * Key needs 28 * static bool EQ(const Entry&, const HashKey&); 29 * static bool LT(const Entry&, const HashKey&); 30 * uint32_t getHash() const; 31 * 32 * Allows duplicate key entries but on find you may get 33 * any of the duplicate entries returned. 34 */ 35 template <typename T, typename Key, size_t kHashBits> class GrTHashTable { 36 public: 37 GrTHashTable() { Gr_bzero(fHash, sizeof(fHash)); } 38 ~GrTHashTable() {} 39 40 int count() const { return fSorted.count(); } 41 T* find(const Key&) const; 42 template <typename FindFuncType> T* find(const Key&, const FindFuncType&) const; 43 // return true if key was unique when inserted. 44 bool insert(const Key&, T*); 45 void remove(const Key&, const T*); 46 T* removeAt(int index, uint32_t hash); 47 void removeAll(); 48 void deleteAll(); 49 void unrefAll(); 50 51 /** 52 * Return the index for the element, using a linear search. 53 */ 54 int slowFindIndex(T* elem) const { return fSorted.find(elem); } 55 56 #if GR_DEBUG 57 void validate() const; 58 bool contains(T*) const; 59 #endif 60 61 // testing 62 const SkTDArray<T*>& getArray() const { return fSorted; } 63 SkTDArray<T*>& getArray() { return fSorted; } 64 private: 65 enum { 66 kHashCount = 1 << kHashBits, 67 kHashMask = kHashCount - 1 68 }; 69 static unsigned hash2Index(uint32_t hash) { 70 hash ^= hash >> 16; 71 if (kHashBits <= 8) { 72 hash ^= hash >> 8; 73 } 74 return hash & kHashMask; 75 } 76 77 mutable T* fHash[kHashCount]; 78 SkTDArray<T*> fSorted; 79 80 // search fSorted, and return the found index, or ~index of where it 81 // should be inserted 82 int searchArray(const Key&) const; 83 }; 84 85 /////////////////////////////////////////////////////////////////////////////// 86 87 template <typename T, typename Key, size_t kHashBits> 88 int GrTHashTable<T, Key, kHashBits>::searchArray(const Key& key) const { 89 int count = fSorted.count(); 90 if (0 == count) { 91 // we should insert it at 0 92 return ~0; 93 } 94 95 const T* const* array = fSorted.begin(); 96 int high = count - 1; 97 int low = 0; 98 while (high > low) { 99 int index = (low + high) >> 1; 100 if (Key::LT(*array[index], key)) { 101 low = index + 1; 102 } else { 103 high = index; 104 } 105 } 106 107 // check if we found it 108 if (Key::EQ(*array[high], key)) { 109 // above search should have found the first occurrence if there 110 // are multiple. 111 GrAssert(0 == high || Key::LT(*array[high - 1], key)); 112 return high; 113 } 114 115 // now return the ~ of where we should insert it 116 if (Key::LT(*array[high], key)) { 117 high += 1; 118 } 119 return ~high; 120 } 121 122 template <typename T, typename Key, size_t kHashBits> 123 T* GrTHashTable<T, Key, kHashBits>::find(const Key& key) const { 124 GrTDefaultFindFunctor<T> find; 125 126 return this->find(key, find); 127 } 128 129 template <typename T, typename Key, size_t kHashBits> 130 template <typename FindFuncType> 131 T* GrTHashTable<T, Key, kHashBits>::find(const Key& key, const FindFuncType& findFunc) const { 132 133 int hashIndex = hash2Index(key.getHash()); 134 T* elem = fHash[hashIndex]; 135 136 if (NULL != elem && Key::EQ(*elem, key) && findFunc(elem)) { 137 return elem; 138 } 139 140 // bsearch for the key in our sorted array 141 int index = this->searchArray(key); 142 if (index < 0) { 143 return NULL; 144 } 145 146 const T* const* array = fSorted.begin(); 147 148 // above search should have found the first occurrence if there 149 // are multiple. 150 GrAssert(0 == index || Key::LT(*array[index - 1], key)); 151 152 for ( ; index < count() && Key::EQ(*array[index], key); ++index) { 153 if (findFunc(fSorted[index])) { 154 // update the hash 155 fHash[hashIndex] = fSorted[index]; 156 return fSorted[index]; 157 } 158 } 159 160 return NULL; 161 } 162 163 template <typename T, typename Key, size_t kHashBits> 164 bool GrTHashTable<T, Key, kHashBits>::insert(const Key& key, T* elem) { 165 int index = this->searchArray(key); 166 bool first = index < 0; 167 if (first) { 168 // turn it into the actual index 169 index = ~index; 170 } 171 // add it to our array 172 *fSorted.insert(index) = elem; 173 // update our hash table (overwrites any dupe's position in the hash) 174 fHash[hash2Index(key.getHash())] = elem; 175 return first; 176 } 177 178 template <typename T, typename Key, size_t kHashBits> 179 void GrTHashTable<T, Key, kHashBits>::remove(const Key& key, const T* elem) { 180 int index = hash2Index(key.getHash()); 181 if (fHash[index] == elem) { 182 fHash[index] = NULL; 183 } 184 185 // remove from our sorted array 186 index = this->searchArray(key); 187 GrAssert(index >= 0); 188 // if there are multiple matches searchArray will give us the first match 189 // march forward until we find elem. 190 while (elem != fSorted[index]) { 191 ++index; 192 GrAssert(index < fSorted.count()); 193 } 194 GrAssert(elem == fSorted[index]); 195 fSorted.remove(index); 196 } 197 198 template <typename T, typename Key, size_t kHashBits> 199 T* GrTHashTable<T, Key, kHashBits>::removeAt(int elemIndex, uint32_t hash) { 200 int hashIndex = hash2Index(hash); 201 if (fHash[hashIndex] == fSorted[elemIndex]) { 202 fHash[hashIndex] = NULL; 203 } 204 // remove from our sorted array 205 T* elem = fSorted[elemIndex]; 206 fSorted.remove(elemIndex); 207 return elem; 208 } 209 210 template <typename T, typename Key, size_t kHashBits> 211 void GrTHashTable<T, Key, kHashBits>::removeAll() { 212 fSorted.reset(); 213 Gr_bzero(fHash, sizeof(fHash)); 214 } 215 216 template <typename T, typename Key, size_t kHashBits> 217 void GrTHashTable<T, Key, kHashBits>::deleteAll() { 218 fSorted.deleteAll(); 219 Gr_bzero(fHash, sizeof(fHash)); 220 } 221 222 template <typename T, typename Key, size_t kHashBits> 223 void GrTHashTable<T, Key, kHashBits>::unrefAll() { 224 fSorted.unrefAll(); 225 Gr_bzero(fHash, sizeof(fHash)); 226 } 227 228 #if GR_DEBUG 229 template <typename T, typename Key, size_t kHashBits> 230 void GrTHashTable<T, Key, kHashBits>::validate() const { 231 int count = fSorted.count(); 232 for (int i = 1; i < count; i++) { 233 GrAssert(Key::LT(*fSorted[i - 1], *fSorted[i]) || 234 Key::EQ(*fSorted[i - 1], *fSorted[i])); 235 } 236 } 237 238 template <typename T, typename Key, size_t kHashBits> 239 bool GrTHashTable<T, Key, kHashBits>::contains(T* elem) const { 240 int index = fSorted.find(elem); 241 return index >= 0; 242 } 243 244 #endif 245 246 #endif 247