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* elem) 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 private: 64 enum { 65 kHashCount = 1 << kHashBits, 66 kHashMask = kHashCount - 1 67 }; 68 static unsigned hash2Index(uint32_t hash) { 69 hash ^= hash >> 16; 70 if (kHashBits <= 8) { 71 hash ^= hash >> 8; 72 } 73 return hash & kHashMask; 74 } 75 76 mutable T* fHash[kHashCount]; 77 SkTDArray<T*> fSorted; 78 79 // search fSorted, and return the found index, or ~index of where it 80 // should be inserted 81 int searchArray(const Key&) const; 82 }; 83 84 /////////////////////////////////////////////////////////////////////////////// 85 86 template <typename T, typename Key, size_t kHashBits> 87 int GrTHashTable<T, Key, kHashBits>::searchArray(const Key& key) const { 88 int count = fSorted.count(); 89 if (0 == count) { 90 // we should insert it at 0 91 return ~0; 92 } 93 94 const T* const* array = fSorted.begin(); 95 int high = count - 1; 96 int low = 0; 97 while (high > low) { 98 int index = (low + high) >> 1; 99 if (Key::LT(*array[index], key)) { 100 low = index + 1; 101 } else { 102 high = index; 103 } 104 } 105 106 // check if we found it 107 if (Key::EQ(*array[high], key)) { 108 // above search should have found the first occurrence if there 109 // are multiple. 110 GrAssert(0 == high || Key::LT(*array[high - 1], key)); 111 return high; 112 } 113 114 // now return the ~ of where we should insert it 115 if (Key::LT(*array[high], key)) { 116 high += 1; 117 } 118 return ~high; 119 } 120 121 template <typename T, typename Key, size_t kHashBits> 122 T* GrTHashTable<T, Key, kHashBits>::find(const Key& key) const { 123 GrTDefaultFindFunctor<T> find; 124 125 return this->find(key, find); 126 } 127 128 template <typename T, typename Key, size_t kHashBits> 129 template <typename FindFuncType> 130 T* GrTHashTable<T, Key, kHashBits>::find(const Key& key, const FindFuncType& findFunc) const { 131 132 int hashIndex = hash2Index(key.getHash()); 133 T* elem = fHash[hashIndex]; 134 135 if (NULL != elem && Key::EQ(*elem, key) && findFunc(elem)) { 136 return elem; 137 } 138 139 // bsearch for the key in our sorted array 140 int index = this->searchArray(key); 141 if (index < 0) { 142 return NULL; 143 } 144 145 const T* const* array = fSorted.begin(); 146 147 // above search should have found the first occurrence if there 148 // are multiple. 149 GrAssert(0 == index || Key::LT(*array[index - 1], key)); 150 151 for ( ; index < count() && Key::EQ(*array[index], key); ++index) { 152 if (findFunc(fSorted[index])) { 153 // update the hash 154 fHash[hashIndex] = fSorted[index]; 155 return fSorted[index]; 156 } 157 } 158 159 return NULL; 160 } 161 162 template <typename T, typename Key, size_t kHashBits> 163 bool GrTHashTable<T, Key, kHashBits>::insert(const Key& key, T* elem) { 164 int index = this->searchArray(key); 165 bool first = index < 0; 166 if (first) { 167 // turn it into the actual index 168 index = ~index; 169 } 170 // add it to our array 171 *fSorted.insert(index) = elem; 172 // update our hash table (overwrites any dupe's position in the hash) 173 fHash[hash2Index(key.getHash())] = elem; 174 return first; 175 } 176 177 template <typename T, typename Key, size_t kHashBits> 178 void GrTHashTable<T, Key, kHashBits>::remove(const Key& key, const T* elem) { 179 int index = hash2Index(key.getHash()); 180 if (fHash[index] == elem) { 181 fHash[index] = NULL; 182 } 183 184 // remove from our sorted array 185 index = this->searchArray(key); 186 GrAssert(index >= 0); 187 // if there are multiple matches searchArray will give us the first match 188 // march forward until we find elem. 189 while (elem != fSorted[index]) { 190 ++index; 191 GrAssert(index < fSorted.count()); 192 } 193 GrAssert(elem == fSorted[index]); 194 fSorted.remove(index); 195 } 196 197 template <typename T, typename Key, size_t kHashBits> 198 T* GrTHashTable<T, Key, kHashBits>::removeAt(int elemIndex, uint32_t hash) { 199 int hashIndex = hash2Index(hash); 200 if (fHash[hashIndex] == fSorted[elemIndex]) { 201 fHash[hashIndex] = NULL; 202 } 203 // remove from our sorted array 204 T* elem = fSorted[elemIndex]; 205 fSorted.remove(elemIndex); 206 return elem; 207 } 208 209 template <typename T, typename Key, size_t kHashBits> 210 void GrTHashTable<T, Key, kHashBits>::removeAll() { 211 fSorted.reset(); 212 Gr_bzero(fHash, sizeof(fHash)); 213 } 214 215 template <typename T, typename Key, size_t kHashBits> 216 void GrTHashTable<T, Key, kHashBits>::deleteAll() { 217 fSorted.deleteAll(); 218 Gr_bzero(fHash, sizeof(fHash)); 219 } 220 221 template <typename T, typename Key, size_t kHashBits> 222 void GrTHashTable<T, Key, kHashBits>::unrefAll() { 223 fSorted.unrefAll(); 224 Gr_bzero(fHash, sizeof(fHash)); 225 } 226 227 #if GR_DEBUG 228 template <typename T, typename Key, size_t kHashBits> 229 void GrTHashTable<T, Key, kHashBits>::validate() const { 230 int count = fSorted.count(); 231 for (int i = 1; i < count; i++) { 232 GrAssert(Key::LT(*fSorted[i - 1], *fSorted[i]) || 233 Key::EQ(*fSorted[i - 1], *fSorted[i])); 234 } 235 } 236 237 template <typename T, typename Key, size_t kHashBits> 238 bool GrTHashTable<T, Key, kHashBits>::contains(T* elem) const { 239 int index = fSorted.find(elem); 240 return index >= 0; 241 } 242 243 #endif 244 245 #endif 246