reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 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" |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 12 | #include "SkMath.h" |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 13 | |
reed@google.com | b14ecda | 2013-07-31 18:02:55 +0000 | [diff] [blame] | 14 | template <typename T, |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 15 | typename Key, |
| 16 | const Key& (GetKey)(const T&), |
| 17 | uint32_t (Hash)(const Key&), |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 18 | bool (Equal)(const T&, const Key&), |
| 19 | int kGrowPercent = 75, // Larger -> more memory efficient, but slower. |
| 20 | int kShrinkPercent = 25> |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 21 | class SkTDynamicHash { |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 22 | static const int kMinCapacity = 4; // Smallest capacity we allow. |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 23 | public: |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 24 | SkTDynamicHash(int initialCapacity=64/sizeof(T*)) { |
| 25 | this->reset(SkNextPow2(initialCapacity > kMinCapacity ? initialCapacity : kMinCapacity)); |
| 26 | SkASSERT(this->validate()); |
| 27 | } |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 28 | |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 29 | ~SkTDynamicHash() { |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 30 | sk_free(fArray); |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 31 | } |
skia.committer@gmail.com | 956b310 | 2013-07-26 07:00:58 +0000 | [diff] [blame] | 32 | |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 33 | int count() const { return fCount; } |
skia.committer@gmail.com | 956b310 | 2013-07-26 07:00:58 +0000 | [diff] [blame] | 34 | |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 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++) { |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 39 | T* candidate = fArray[index]; |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 40 | if (Empty() == candidate) { |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 41 | return NULL; |
| 42 | } |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 43 | if (Deleted() != candidate && Equal(*candidate, key)) { |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 44 | return candidate; |
| 45 | } |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 46 | index = this->nextIndex(index, round); |
| 47 | } |
| 48 | SkASSERT(!"find: should be unreachable"); |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 49 | return NULL; |
| 50 | } |
skia.committer@gmail.com | 956b310 | 2013-07-26 07:00:58 +0000 | [diff] [blame] | 51 | |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 52 | // Add an entry with this key. We require that no entry with newEntry's key is already present. |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 53 | void add(T* newEntry) { |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 54 | SkASSERT(NULL == this->find(GetKey(*newEntry))); |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 55 | this->maybeGrow(); |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 56 | SkASSERT(this->validate()); |
| 57 | this->innerAdd(newEntry); |
| 58 | SkASSERT(this->validate()); |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 59 | } |
skia.committer@gmail.com | 956b310 | 2013-07-26 07:00:58 +0000 | [diff] [blame] | 60 | |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 61 | // Remove the entry with this key. We reqire that an entry with this key is present. |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 62 | void remove(const Key& key) { |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 63 | SkASSERT(NULL != this->find(key)); |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 64 | this->innerRemove(key); |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 65 | SkASSERT(this->validate()); |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 66 | this->maybeShrink(); |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 67 | SkASSERT(this->validate()); |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 68 | } |
skia.committer@gmail.com | 956b310 | 2013-07-26 07:00:58 +0000 | [diff] [blame] | 69 | |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 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++) { |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 79 | const T* candidate = fArray[index]; |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 80 | if (Empty() == candidate || Deleted() == candidate || Equal(*candidate, key)) { |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 81 | return round; |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 82 | } |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 83 | index = this->nextIndex(index, round); |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 84 | } |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 85 | SkASSERT(!"countCollisions: should be unreachable"); |
| 86 | return -1; |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 87 | } |
skia.committer@gmail.com | 956b310 | 2013-07-26 07:00:58 +0000 | [diff] [blame] | 88 | |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 89 | private: |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 90 | // We have two special values to indicate an empty or deleted entry. |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 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. |
reed@google.com | b8d17fe | 2013-07-25 17:42:24 +0000 | [diff] [blame] | 93 | |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 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; |
reed@google.com | b8d17fe | 2013-07-25 17:42:24 +0000 | [diff] [blame] | 98 | } |
| 99 | |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 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); |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 160 | int index = this->firstIndex(key); |
| 161 | for (int round = 0; round < fCapacity; round++) { |
| 162 | const T* candidate = fArray[index]; |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 163 | if (Empty() == candidate || Deleted() == candidate) { |
| 164 | if (Deleted() == candidate) { |
| 165 | fDeleted--; |
| 166 | } |
| 167 | fCount++; |
| 168 | fArray[index] = newEntry; |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 169 | return; |
reed@google.com | b8d17fe | 2013-07-25 17:42:24 +0000 | [diff] [blame] | 170 | } |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 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++; |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 183 | fCount--; |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 184 | fArray[index] = Deleted(); |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 185 | return; |
| 186 | } |
| 187 | index = this->nextIndex(index, round); |
reed@google.com | b8d17fe | 2013-07-25 17:42:24 +0000 | [diff] [blame] | 188 | } |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 189 | SkASSERT(!"innerRemove: should be unreachable"); |
| 190 | } |
| 191 | |
| 192 | void maybeGrow() { |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 193 | if (fCount + fDeleted + 1 > (fCapacity * kGrowPercent) / 100) { |
| 194 | resize(fCapacity * 2); |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 195 | } |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 196 | } |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 197 | |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 198 | void maybeShrink() { |
| 199 | if (fCount < (fCapacity * kShrinkPercent) / 100 && fCapacity / 2 > kMinCapacity) { |
| 200 | resize(fCapacity / 2); |
| 201 | } |
| 202 | } |
| 203 | |
| 204 | void resize(int newCapacity) { |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 205 | SkDEBUGCODE(int oldCount = fCount;) |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 206 | int oldCapacity = fCapacity; |
| 207 | T** oldArray = fArray; |
skia.committer@gmail.com | 956b310 | 2013-07-26 07:00:58 +0000 | [diff] [blame] | 208 | |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 209 | reset(newCapacity); |
skia.committer@gmail.com | 956b310 | 2013-07-26 07:00:58 +0000 | [diff] [blame] | 210 | |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 211 | for (int i = 0; i < oldCapacity; i++) { |
| 212 | T* entry = oldArray[i]; |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 213 | if (Empty() != entry && Deleted() != entry) { |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 214 | this->add(entry); |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 215 | } |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 216 | } |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 217 | SkASSERT(oldCount == fCount); |
reed@google.com | b8d17fe | 2013-07-25 17:42:24 +0000 | [diff] [blame] | 218 | |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 219 | sk_free(oldArray); |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 220 | } |
skia.committer@gmail.com | 956b310 | 2013-07-26 07:00:58 +0000 | [diff] [blame] | 221 | |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 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 | |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame^] | 235 | int fCount; // Number of non Empty(), non Deleted() entries in fArray. |
| 236 | int fDeleted; // Number of Deleted() entries in fArray. |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 237 | int fCapacity; // Number of entries in fArray. Always a power of 2. |
| 238 | T** fArray; |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 239 | }; |
| 240 | |
| 241 | #endif |