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