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 | |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 11 | #include "SkMath.h" |
commit-bot@chromium.org | 5b8bde5 | 2014-01-16 18:16:37 +0000 | [diff] [blame] | 12 | #include "SkTemplates.h" |
| 13 | #include "SkTypes.h" |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 14 | |
commit-bot@chromium.org | 55bd940 | 2014-04-02 19:17:00 +0000 | [diff] [blame] | 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. |
reed@google.com | b14ecda | 2013-07-31 18:02:55 +0000 | [diff] [blame] | 19 | template <typename T, |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 20 | typename Key, |
commit-bot@chromium.org | 55bd940 | 2014-04-02 19:17:00 +0000 | [diff] [blame] | 21 | typename Traits = T, |
commit-bot@chromium.org | 7a4b9fa | 2014-01-13 18:28:14 +0000 | [diff] [blame] | 22 | int kGrowPercent = 75> // Larger -> more memory efficient, but slower. |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 23 | class SkTDynamicHash { |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 24 | public: |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 25 | SkTDynamicHash() : fCount(0), fDeleted(0), fCapacity(0), fArray(nullptr) { |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 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 | 1f6cf69 | 2014-03-05 01:00:50 +0000 | [diff] [blame] | 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 | |
robertphillips | 3d533ac | 2014-07-20 09:40:00 -0700 | [diff] [blame] | 60 | class ConstIter { |
| 61 | public: |
| 62 | explicit ConstIter(const SkTDynamicHash* hash) : fHash(hash), fCurrentIndex(-1) { |
| 63 | SkASSERT(hash); |
| 64 | ++(*this); |
| 65 | } |
| 66 | bool done() const { |
| 67 | SkASSERT(fCurrentIndex <= fHash->fCapacity); |
| 68 | return fCurrentIndex == fHash->fCapacity; |
| 69 | } |
| 70 | const T& operator*() const { |
| 71 | SkASSERT(!this->done()); |
| 72 | return *this->current(); |
| 73 | } |
| 74 | void operator++() { |
| 75 | do { |
| 76 | fCurrentIndex++; |
| 77 | } while (!this->done() && (this->current() == Empty() || this->current() == Deleted())); |
| 78 | } |
| 79 | |
| 80 | private: |
| 81 | const T* current() const { return fHash->fArray[fCurrentIndex]; } |
| 82 | |
| 83 | const SkTDynamicHash* fHash; |
| 84 | int fCurrentIndex; |
| 85 | }; |
| 86 | |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 87 | int count() const { return fCount; } |
skia.committer@gmail.com | 956b310 | 2013-07-26 07:00:58 +0000 | [diff] [blame] | 88 | |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 89 | // Return the entry with this key if we have it, otherwise nullptr. |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 90 | T* find(const Key& key) const { |
| 91 | int index = this->firstIndex(key); |
| 92 | for (int round = 0; round < fCapacity; round++) { |
mtklein | 2e09d18 | 2014-07-09 09:20:54 -0700 | [diff] [blame] | 93 | SkASSERT(index >= 0 && index < fCapacity); |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 94 | T* candidate = fArray[index]; |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 95 | if (Empty() == candidate) { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 96 | return nullptr; |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 97 | } |
commit-bot@chromium.org | 158f646 | 2014-04-02 17:03:09 +0000 | [diff] [blame] | 98 | if (Deleted() != candidate && GetKey(*candidate) == key) { |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 99 | return candidate; |
| 100 | } |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 101 | index = this->nextIndex(index, round); |
| 102 | } |
commit-bot@chromium.org | 7a4b9fa | 2014-01-13 18:28:14 +0000 | [diff] [blame] | 103 | SkASSERT(fCapacity == 0); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 104 | return nullptr; |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 105 | } |
skia.committer@gmail.com | 956b310 | 2013-07-26 07:00:58 +0000 | [diff] [blame] | 106 | |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 107 | // 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] | 108 | void add(T* newEntry) { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 109 | SkASSERT(nullptr == this->find(GetKey(*newEntry))); |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 110 | this->maybeGrow(); |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 111 | this->innerAdd(newEntry); |
| 112 | SkASSERT(this->validate()); |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 113 | } |
skia.committer@gmail.com | 956b310 | 2013-07-26 07:00:58 +0000 | [diff] [blame] | 114 | |
robertphillips | 3d533ac | 2014-07-20 09:40:00 -0700 | [diff] [blame] | 115 | // Remove the entry with this key. We require that an entry with this key is present. |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 116 | void remove(const Key& key) { |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 117 | SkASSERT(this->find(key)); |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 118 | this->innerRemove(key); |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 119 | SkASSERT(this->validate()); |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 120 | } |
skia.committer@gmail.com | 956b310 | 2013-07-26 07:00:58 +0000 | [diff] [blame] | 121 | |
robertphillips | 3d533ac | 2014-07-20 09:40:00 -0700 | [diff] [blame] | 122 | void rewind() { |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 123 | if (fArray) { |
robertphillips | 3d533ac | 2014-07-20 09:40:00 -0700 | [diff] [blame] | 124 | sk_bzero(fArray, sizeof(T*)* fCapacity); |
| 125 | } |
| 126 | fCount = 0; |
| 127 | fDeleted = 0; |
| 128 | } |
| 129 | |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 130 | void reset() { |
| 131 | fCount = 0; |
| 132 | fDeleted = 0; |
| 133 | fCapacity = 0; |
| 134 | sk_free(fArray); |
| 135 | fArray = nullptr; |
robertphillips | 3d533ac | 2014-07-20 09:40:00 -0700 | [diff] [blame] | 136 | } |
| 137 | |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 138 | protected: |
| 139 | // These methods are used by tests only. |
| 140 | |
| 141 | int capacity() const { return fCapacity; } |
| 142 | |
| 143 | // How many collisions do we go through before finding where this entry should be inserted? |
| 144 | int countCollisions(const Key& key) const { |
| 145 | int index = this->firstIndex(key); |
| 146 | for (int round = 0; round < fCapacity; round++) { |
mtklein | 2e09d18 | 2014-07-09 09:20:54 -0700 | [diff] [blame] | 147 | SkASSERT(index >= 0 && index < fCapacity); |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 148 | const T* candidate = fArray[index]; |
commit-bot@chromium.org | 158f646 | 2014-04-02 17:03:09 +0000 | [diff] [blame] | 149 | if (Empty() == candidate || Deleted() == candidate || GetKey(*candidate) == key) { |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 150 | return round; |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 151 | } |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 152 | index = this->nextIndex(index, round); |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 153 | } |
commit-bot@chromium.org | 7a4b9fa | 2014-01-13 18:28:14 +0000 | [diff] [blame] | 154 | SkASSERT(fCapacity == 0); |
| 155 | return 0; |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 156 | } |
skia.committer@gmail.com | 956b310 | 2013-07-26 07:00:58 +0000 | [diff] [blame] | 157 | |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 158 | private: |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 159 | // We have two special values to indicate an empty or deleted entry. |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 160 | static T* Empty() { return reinterpret_cast<T*>(0); } // i.e. nullptr |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 161 | 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] | 162 | |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 163 | bool validate() const { |
dongseong.hwang | 00ed9a9 | 2015-04-28 12:26:52 -0700 | [diff] [blame] | 164 | #define SKTDYNAMICHASH_CHECK(x) SkASSERT(x); if (!(x)) return false |
commit-bot@chromium.org | cd0bf0a | 2014-01-17 17:55:14 +0000 | [diff] [blame] | 165 | static const int kLarge = 50; // Arbitrary, tweak to suit your patience. |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 166 | |
commit-bot@chromium.org | cd0bf0a | 2014-01-17 17:55:14 +0000 | [diff] [blame] | 167 | // O(1) checks, always done. |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 168 | // Is capacity sane? |
mtklein@google.com | ba0ca99 | 2013-08-20 17:03:02 +0000 | [diff] [blame] | 169 | SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity)); |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 170 | |
commit-bot@chromium.org | cd0bf0a | 2014-01-17 17:55:14 +0000 | [diff] [blame] | 171 | // O(N) checks, skipped when very large. |
| 172 | if (fCount < kLarge * kLarge) { |
| 173 | // Are fCount and fDeleted correct, and are all elements findable? |
| 174 | int count = 0, deleted = 0; |
| 175 | for (int i = 0; i < fCapacity; i++) { |
| 176 | if (Deleted() == fArray[i]) { |
| 177 | deleted++; |
| 178 | } else if (Empty() != fArray[i]) { |
| 179 | count++; |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 180 | SKTDYNAMICHASH_CHECK(this->find(GetKey(*fArray[i]))); |
commit-bot@chromium.org | cd0bf0a | 2014-01-17 17:55:14 +0000 | [diff] [blame] | 181 | } |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 182 | } |
commit-bot@chromium.org | cd0bf0a | 2014-01-17 17:55:14 +0000 | [diff] [blame] | 183 | SKTDYNAMICHASH_CHECK(count == fCount); |
| 184 | SKTDYNAMICHASH_CHECK(deleted == fDeleted); |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 185 | } |
| 186 | |
commit-bot@chromium.org | cd0bf0a | 2014-01-17 17:55:14 +0000 | [diff] [blame] | 187 | // O(N^2) checks, skipped when large. |
| 188 | if (fCount < kLarge) { |
| 189 | // Are all entries unique? |
| 190 | for (int i = 0; i < fCapacity; i++) { |
| 191 | if (Empty() == fArray[i] || Deleted() == fArray[i]) { |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 192 | continue; |
| 193 | } |
commit-bot@chromium.org | cd0bf0a | 2014-01-17 17:55:14 +0000 | [diff] [blame] | 194 | for (int j = i+1; j < fCapacity; j++) { |
| 195 | if (Empty() == fArray[j] || Deleted() == fArray[j]) { |
| 196 | continue; |
| 197 | } |
| 198 | SKTDYNAMICHASH_CHECK(fArray[i] != fArray[j]); |
commit-bot@chromium.org | 158f646 | 2014-04-02 17:03:09 +0000 | [diff] [blame] | 199 | SKTDYNAMICHASH_CHECK(!(GetKey(*fArray[i]) == GetKey(*fArray[j]))); |
commit-bot@chromium.org | cd0bf0a | 2014-01-17 17:55:14 +0000 | [diff] [blame] | 200 | } |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 201 | } |
| 202 | } |
mtklein@google.com | ba0ca99 | 2013-08-20 17:03:02 +0000 | [diff] [blame] | 203 | #undef SKTDYNAMICHASH_CHECK |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 204 | return true; |
| 205 | } |
| 206 | |
| 207 | void innerAdd(T* newEntry) { |
| 208 | const Key& key = GetKey(*newEntry); |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 209 | int index = this->firstIndex(key); |
| 210 | for (int round = 0; round < fCapacity; round++) { |
mtklein | 2e09d18 | 2014-07-09 09:20:54 -0700 | [diff] [blame] | 211 | SkASSERT(index >= 0 && index < fCapacity); |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 212 | const T* candidate = fArray[index]; |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 213 | if (Empty() == candidate || Deleted() == candidate) { |
| 214 | if (Deleted() == candidate) { |
| 215 | fDeleted--; |
| 216 | } |
| 217 | fCount++; |
| 218 | fArray[index] = newEntry; |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 219 | return; |
reed@google.com | b8d17fe | 2013-07-25 17:42:24 +0000 | [diff] [blame] | 220 | } |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 221 | index = this->nextIndex(index, round); |
| 222 | } |
commit-bot@chromium.org | 7a4b9fa | 2014-01-13 18:28:14 +0000 | [diff] [blame] | 223 | SkASSERT(fCapacity == 0); |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 224 | } |
| 225 | |
| 226 | void innerRemove(const Key& key) { |
| 227 | const int firstIndex = this->firstIndex(key); |
| 228 | int index = firstIndex; |
| 229 | for (int round = 0; round < fCapacity; round++) { |
mtklein | 2e09d18 | 2014-07-09 09:20:54 -0700 | [diff] [blame] | 230 | SkASSERT(index >= 0 && index < fCapacity); |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 231 | const T* candidate = fArray[index]; |
commit-bot@chromium.org | 158f646 | 2014-04-02 17:03:09 +0000 | [diff] [blame] | 232 | if (Deleted() != candidate && GetKey(*candidate) == key) { |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 233 | fDeleted++; |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 234 | fCount--; |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 235 | fArray[index] = Deleted(); |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 236 | return; |
| 237 | } |
| 238 | index = this->nextIndex(index, round); |
reed@google.com | b8d17fe | 2013-07-25 17:42:24 +0000 | [diff] [blame] | 239 | } |
commit-bot@chromium.org | 7a4b9fa | 2014-01-13 18:28:14 +0000 | [diff] [blame] | 240 | SkASSERT(fCapacity == 0); |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 241 | } |
| 242 | |
| 243 | void maybeGrow() { |
commit-bot@chromium.org | 7a4b9fa | 2014-01-13 18:28:14 +0000 | [diff] [blame] | 244 | if (100 * (fCount + fDeleted + 1) > fCapacity * kGrowPercent) { |
| 245 | this->resize(fCapacity > 0 ? fCapacity * 2 : 4); |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 246 | } |
| 247 | } |
| 248 | |
| 249 | void resize(int newCapacity) { |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 250 | SkDEBUGCODE(int oldCount = fCount;) |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 251 | int oldCapacity = fCapacity; |
commit-bot@chromium.org | 7a4b9fa | 2014-01-13 18:28:14 +0000 | [diff] [blame] | 252 | SkAutoTMalloc<T*> oldArray(fArray); |
skia.committer@gmail.com | 956b310 | 2013-07-26 07:00:58 +0000 | [diff] [blame] | 253 | |
commit-bot@chromium.org | 7a4b9fa | 2014-01-13 18:28:14 +0000 | [diff] [blame] | 254 | fCount = fDeleted = 0; |
| 255 | fCapacity = newCapacity; |
| 256 | fArray = (T**)sk_calloc_throw(sizeof(T*) * fCapacity); |
skia.committer@gmail.com | 956b310 | 2013-07-26 07:00:58 +0000 | [diff] [blame] | 257 | |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 258 | for (int i = 0; i < oldCapacity; i++) { |
| 259 | T* entry = oldArray[i]; |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 260 | if (Empty() != entry && Deleted() != entry) { |
commit-bot@chromium.org | 7a4b9fa | 2014-01-13 18:28:14 +0000 | [diff] [blame] | 261 | this->innerAdd(entry); |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 262 | } |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 263 | } |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 264 | SkASSERT(oldCount == fCount); |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 265 | } |
skia.committer@gmail.com | 956b310 | 2013-07-26 07:00:58 +0000 | [diff] [blame] | 266 | |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 267 | // fCapacity is always a power of 2, so this masks the correct low bits to index into our hash. |
| 268 | uint32_t hashMask() const { return fCapacity - 1; } |
| 269 | |
| 270 | int firstIndex(const Key& key) const { |
| 271 | return Hash(key) & this->hashMask(); |
| 272 | } |
| 273 | |
| 274 | // Given index at round N, what is the index to check at N+1? round should start at 0. |
| 275 | int nextIndex(int index, int round) const { |
| 276 | // This will search a power-of-two array fully without repeating an index. |
| 277 | return (index + round + 1) & this->hashMask(); |
| 278 | } |
| 279 | |
commit-bot@chromium.org | 55bd940 | 2014-04-02 19:17:00 +0000 | [diff] [blame] | 280 | static const Key& GetKey(const T& t) { return Traits::GetKey(t); } |
| 281 | static uint32_t Hash(const Key& key) { return Traits::Hash(key); } |
| 282 | |
mtklein@google.com | c9ab2b7 | 2013-08-12 14:51:25 +0000 | [diff] [blame] | 283 | int fCount; // Number of non Empty(), non Deleted() entries in fArray. |
| 284 | int fDeleted; // Number of Deleted() entries in fArray. |
commit-bot@chromium.org | f916f9e | 2013-08-05 22:31:20 +0000 | [diff] [blame] | 285 | int fCapacity; // Number of entries in fArray. Always a power of 2. |
| 286 | T** fArray; |
reed@google.com | 5d1e558 | 2013-07-25 14:36:15 +0000 | [diff] [blame] | 287 | }; |
| 288 | |
| 289 | #endif |