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