1 /* 2 * Copyright 2013 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #ifndef SkTDynamicHash_DEFINED 9 #define SkTDynamicHash_DEFINED 10 11 #include "SkTypes.h" 12 #include "SkMath.h" 13 14 template <typename T, 15 typename Key, 16 const Key& (GetKey)(const T&), 17 uint32_t (Hash)(const Key&), 18 bool (Equal)(const T&, const Key&), 19 int kGrowPercent = 75, // Larger -> more memory efficient, but slower. 20 int kShrinkPercent = 25> 21 class SkTDynamicHash { 22 static const int kMinCapacity = 4; // Smallest capacity we allow. 23 public: 24 SkTDynamicHash(int initialCapacity=64/sizeof(T*)) { 25 this->reset(SkNextPow2(initialCapacity > kMinCapacity ? initialCapacity : kMinCapacity)); 26 SkASSERT(this->validate()); 27 } 28 29 ~SkTDynamicHash() { 30 sk_free(fArray); 31 } 32 33 int count() const { return fCount; } 34 35 // Return the entry with this key if we have it, otherwise NULL. 36 T* find(const Key& key) const { 37 int index = this->firstIndex(key); 38 for (int round = 0; round < fCapacity; round++) { 39 T* candidate = fArray[index]; 40 if (Empty() == candidate) { 41 return NULL; 42 } 43 if (Deleted() != candidate && Equal(*candidate, key)) { 44 return candidate; 45 } 46 index = this->nextIndex(index, round); 47 } 48 SkASSERT(!"find: should be unreachable"); 49 return NULL; 50 } 51 52 // Add an entry with this key. We require that no entry with newEntry's key is already present. 53 void add(T* newEntry) { 54 SkASSERT(NULL == this->find(GetKey(*newEntry))); 55 this->maybeGrow(); 56 SkASSERT(this->validate()); 57 this->innerAdd(newEntry); 58 SkASSERT(this->validate()); 59 } 60 61 // Remove the entry with this key. We reqire that an entry with this key is present. 62 void remove(const Key& key) { 63 SkASSERT(NULL != this->find(key)); 64 this->innerRemove(key); 65 SkASSERT(this->validate()); 66 this->maybeShrink(); 67 SkASSERT(this->validate()); 68 } 69 70 protected: 71 // These methods are used by tests only. 72 73 int capacity() const { return fCapacity; } 74 75 // How many collisions do we go through before finding where this entry should be inserted? 76 int countCollisions(const Key& key) const { 77 int index = this->firstIndex(key); 78 for (int round = 0; round < fCapacity; round++) { 79 const T* candidate = fArray[index]; 80 if (Empty() == candidate || Deleted() == candidate || Equal(*candidate, key)) { 81 return round; 82 } 83 index = this->nextIndex(index, round); 84 } 85 SkASSERT(!"countCollisions: should be unreachable"); 86 return -1; 87 } 88 89 private: 90 // We have two special values to indicate an empty or deleted entry. 91 static T* Empty() { return reinterpret_cast<T*>(0); } // i.e. NULL 92 static T* Deleted() { return reinterpret_cast<T*>(1); } // Also an invalid pointer. 93 94 static T** AllocArray(int capacity) { 95 T** array = (T**)sk_malloc_throw(sizeof(T*) * capacity); 96 sk_bzero(array, sizeof(T*) * capacity); // All cells == Empty(). 97 return array; 98 } 99 100 void reset(int capacity) { 101 fCount = 0; 102 fDeleted = 0; 103 fCapacity = capacity; 104 fArray = AllocArray(fCapacity); 105 } 106 107 bool validate() const { 108 #define CHECK(x) SkASSERT((x)); if (!(x)) return false 109 110 // Is capacity sane? 111 CHECK(SkIsPow2(fCapacity)); 112 CHECK(fCapacity >= kMinCapacity); 113 114 // Is fCount correct? 115 int count = 0; 116 for (int i = 0; i < fCapacity; i++) { 117 if (Empty() != fArray[i] && Deleted() != fArray[i]) { 118 count++; 119 } 120 } 121 CHECK(count == fCount); 122 123 // Is fDeleted correct? 124 int deleted = 0; 125 for (int i = 0; i < fCapacity; i++) { 126 if (Deleted() == fArray[i]) { 127 deleted++; 128 } 129 } 130 CHECK(deleted == fDeleted); 131 132 // Are all entries findable? 133 for (int i = 0; i < fCapacity; i++) { 134 if (Empty() == fArray[i] || Deleted() == fArray[i]) { 135 continue; 136 } 137 CHECK(NULL != this->find(GetKey(*fArray[i]))); 138 } 139 140 // Are all entries unique? 141 for (int i = 0; i < fCapacity; i++) { 142 if (Empty() == fArray[i] || Deleted() == fArray[i]) { 143 continue; 144 } 145 for (int j = i+1; j < fCapacity; j++) { 146 if (Empty() == fArray[j] || Deleted() == fArray[j]) { 147 continue; 148 } 149 CHECK(fArray[i] != fArray[j]); 150 CHECK(!Equal(*fArray[i], GetKey(*fArray[j]))); 151 CHECK(!Equal(*fArray[j], GetKey(*fArray[i]))); 152 } 153 } 154 #undef CHECK 155 return true; 156 } 157 158 void innerAdd(T* newEntry) { 159 const Key& key = GetKey(*newEntry); 160 int index = this->firstIndex(key); 161 for (int round = 0; round < fCapacity; round++) { 162 const T* candidate = fArray[index]; 163 if (Empty() == candidate || Deleted() == candidate) { 164 if (Deleted() == candidate) { 165 fDeleted--; 166 } 167 fCount++; 168 fArray[index] = newEntry; 169 return; 170 } 171 index = this->nextIndex(index, round); 172 } 173 SkASSERT(!"add: should be unreachable"); 174 } 175 176 void innerRemove(const Key& key) { 177 const int firstIndex = this->firstIndex(key); 178 int index = firstIndex; 179 for (int round = 0; round < fCapacity; round++) { 180 const T* candidate = fArray[index]; 181 if (Deleted() != candidate && Equal(*candidate, key)) { 182 fDeleted++; 183 fCount--; 184 fArray[index] = Deleted(); 185 return; 186 } 187 index = this->nextIndex(index, round); 188 } 189 SkASSERT(!"innerRemove: should be unreachable"); 190 } 191 192 void maybeGrow() { 193 if (fCount + fDeleted + 1 > (fCapacity * kGrowPercent) / 100) { 194 resize(fCapacity * 2); 195 } 196 } 197 198 void maybeShrink() { 199 if (fCount < (fCapacity * kShrinkPercent) / 100 && fCapacity / 2 > kMinCapacity) { 200 resize(fCapacity / 2); 201 } 202 } 203 204 void resize(int newCapacity) { 205 SkDEBUGCODE(int oldCount = fCount;) 206 int oldCapacity = fCapacity; 207 T** oldArray = fArray; 208 209 reset(newCapacity); 210 211 for (int i = 0; i < oldCapacity; i++) { 212 T* entry = oldArray[i]; 213 if (Empty() != entry && Deleted() != entry) { 214 this->add(entry); 215 } 216 } 217 SkASSERT(oldCount == fCount); 218 219 sk_free(oldArray); 220 } 221 222 // fCapacity is always a power of 2, so this masks the correct low bits to index into our hash. 223 uint32_t hashMask() const { return fCapacity - 1; } 224 225 int firstIndex(const Key& key) const { 226 return Hash(key) & this->hashMask(); 227 } 228 229 // Given index at round N, what is the index to check at N+1? round should start at 0. 230 int nextIndex(int index, int round) const { 231 // This will search a power-of-two array fully without repeating an index. 232 return (index + round + 1) & this->hashMask(); 233 } 234 235 int fCount; // Number of non Empty(), non Deleted() entries in fArray. 236 int fDeleted; // Number of Deleted() entries in fArray. 237 int fCapacity; // Number of entries in fArray. Always a power of 2. 238 T** fArray; 239 }; 240 241 #endif 242