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