| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright 2013 Google Inc. | 2 * Copyright 2013 Google Inc. |
| 3 * | 3 * |
| 4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
| 5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
| 6 */ | 6 */ |
| 7 | 7 |
| 8 #ifndef SkTDynamicHash_DEFINED | 8 #ifndef SkTDynamicHash_DEFINED |
| 9 #define SkTDynamicHash_DEFINED | 9 #define SkTDynamicHash_DEFINED |
| 10 | 10 |
| 11 #include "SkMath.h" | 11 #include "SkMath.h" |
| 12 #include "SkTemplates.h" | 12 #include "SkTemplates.h" |
| 13 #include "SkTypes.h" | 13 #include "SkTypes.h" |
| 14 | 14 |
| 15 // Traits requires: | 15 // Traits requires: |
| 16 // static const Key& GetKey(const T&) { ... } | 16 // static const Key& GetKey(const T&) { ... } |
| 17 // static uint32_t Hash(const Key&) { ... } | 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. | 18 // We'll look on T for these by default, or you can pass a custom Traits type. |
| 19 template <typename T, | 19 template <typename T, |
| 20 typename Key, | 20 typename Key, |
| 21 typename Traits = T, | 21 typename Traits = T, |
| 22 int kGrowPercent = 75> // Larger -> more memory efficient, but slower
. | 22 int kGrowPercent = 75> // Larger -> more memory efficient, but slower
. |
| 23 class SkTDynamicHash { | 23 class SkTDynamicHash { |
| 24 public: | 24 public: |
| 25 SkTDynamicHash() : fCount(0), fDeleted(0), fCapacity(0), fArray(NULL) { | 25 SkTDynamicHash() : fCount(0), fDeleted(0), fCapacity(0), fArray(nullptr) { |
| 26 SkASSERT(this->validate()); | 26 SkASSERT(this->validate()); |
| 27 } | 27 } |
| 28 | 28 |
| 29 ~SkTDynamicHash() { | 29 ~SkTDynamicHash() { |
| 30 sk_free(fArray); | 30 sk_free(fArray); |
| 31 } | 31 } |
| 32 | 32 |
| 33 class Iter { | 33 class Iter { |
| 34 public: | 34 public: |
| 35 explicit Iter(SkTDynamicHash* hash) : fHash(hash), fCurrentIndex(-1) { | 35 explicit Iter(SkTDynamicHash* hash) : fHash(hash), fCurrentIndex(-1) { |
| (...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 79 | 79 |
| 80 private: | 80 private: |
| 81 const T* current() const { return fHash->fArray[fCurrentIndex]; } | 81 const T* current() const { return fHash->fArray[fCurrentIndex]; } |
| 82 | 82 |
| 83 const SkTDynamicHash* fHash; | 83 const SkTDynamicHash* fHash; |
| 84 int fCurrentIndex; | 84 int fCurrentIndex; |
| 85 }; | 85 }; |
| 86 | 86 |
| 87 int count() const { return fCount; } | 87 int count() const { return fCount; } |
| 88 | 88 |
| 89 // Return the entry with this key if we have it, otherwise NULL. | 89 // Return the entry with this key if we have it, otherwise nullptr. |
| 90 T* find(const Key& key) const { | 90 T* find(const Key& key) const { |
| 91 int index = this->firstIndex(key); | 91 int index = this->firstIndex(key); |
| 92 for (int round = 0; round < fCapacity; round++) { | 92 for (int round = 0; round < fCapacity; round++) { |
| 93 SkASSERT(index >= 0 && index < fCapacity); | 93 SkASSERT(index >= 0 && index < fCapacity); |
| 94 T* candidate = fArray[index]; | 94 T* candidate = fArray[index]; |
| 95 if (Empty() == candidate) { | 95 if (Empty() == candidate) { |
| 96 return NULL; | 96 return nullptr; |
| 97 } | 97 } |
| 98 if (Deleted() != candidate && GetKey(*candidate) == key) { | 98 if (Deleted() != candidate && GetKey(*candidate) == key) { |
| 99 return candidate; | 99 return candidate; |
| 100 } | 100 } |
| 101 index = this->nextIndex(index, round); | 101 index = this->nextIndex(index, round); |
| 102 } | 102 } |
| 103 SkASSERT(fCapacity == 0); | 103 SkASSERT(fCapacity == 0); |
| 104 return NULL; | 104 return nullptr; |
| 105 } | 105 } |
| 106 | 106 |
| 107 // Add an entry with this key. We require that no entry with newEntry's key
is already present. | 107 // Add an entry with this key. We require that no entry with newEntry's key
is already present. |
| 108 void add(T* newEntry) { | 108 void add(T* newEntry) { |
| 109 SkASSERT(NULL == this->find(GetKey(*newEntry))); | 109 SkASSERT(nullptr == this->find(GetKey(*newEntry))); |
| 110 this->maybeGrow(); | 110 this->maybeGrow(); |
| 111 this->innerAdd(newEntry); | 111 this->innerAdd(newEntry); |
| 112 SkASSERT(this->validate()); | 112 SkASSERT(this->validate()); |
| 113 } | 113 } |
| 114 | 114 |
| 115 // Remove the entry with this key. We require that an entry with this key i
s present. | 115 // Remove the entry with this key. We require that an entry with this key i
s present. |
| 116 void remove(const Key& key) { | 116 void remove(const Key& key) { |
| 117 SkASSERT(this->find(key)); | 117 SkASSERT(this->find(key)); |
| 118 this->innerRemove(key); | 118 this->innerRemove(key); |
| 119 SkASSERT(this->validate()); | 119 SkASSERT(this->validate()); |
| 120 } | 120 } |
| 121 | 121 |
| 122 void rewind() { | 122 void rewind() { |
| 123 if (fArray) { | 123 if (fArray) { |
| 124 sk_bzero(fArray, sizeof(T*)* fCapacity); | 124 sk_bzero(fArray, sizeof(T*)* fCapacity); |
| 125 } | 125 } |
| 126 fCount = 0; | 126 fCount = 0; |
| 127 fDeleted = 0; | 127 fDeleted = 0; |
| 128 } | 128 } |
| 129 | 129 |
| 130 void reset() { | 130 void reset() { |
| 131 fCount = 0; | 131 fCount = 0; |
| 132 fDeleted = 0; | 132 fDeleted = 0; |
| 133 fCapacity = 0; | 133 fCapacity = 0; |
| 134 sk_free(fArray); | 134 sk_free(fArray); |
| 135 fArray = NULL; | 135 fArray = nullptr; |
| 136 } | 136 } |
| 137 | 137 |
| 138 protected: | 138 protected: |
| 139 // These methods are used by tests only. | 139 // These methods are used by tests only. |
| 140 | 140 |
| 141 int capacity() const { return fCapacity; } | 141 int capacity() const { return fCapacity; } |
| 142 | 142 |
| 143 // How many collisions do we go through before finding where this entry shou
ld be inserted? | 143 // How many collisions do we go through before finding where this entry shou
ld be inserted? |
| 144 int countCollisions(const Key& key) const { | 144 int countCollisions(const Key& key) const { |
| 145 int index = this->firstIndex(key); | 145 int index = this->firstIndex(key); |
| 146 for (int round = 0; round < fCapacity; round++) { | 146 for (int round = 0; round < fCapacity; round++) { |
| 147 SkASSERT(index >= 0 && index < fCapacity); | 147 SkASSERT(index >= 0 && index < fCapacity); |
| 148 const T* candidate = fArray[index]; | 148 const T* candidate = fArray[index]; |
| 149 if (Empty() == candidate || Deleted() == candidate || GetKey(*candid
ate) == key) { | 149 if (Empty() == candidate || Deleted() == candidate || GetKey(*candid
ate) == key) { |
| 150 return round; | 150 return round; |
| 151 } | 151 } |
| 152 index = this->nextIndex(index, round); | 152 index = this->nextIndex(index, round); |
| 153 } | 153 } |
| 154 SkASSERT(fCapacity == 0); | 154 SkASSERT(fCapacity == 0); |
| 155 return 0; | 155 return 0; |
| 156 } | 156 } |
| 157 | 157 |
| 158 private: | 158 private: |
| 159 // We have two special values to indicate an empty or deleted entry. | 159 // We have two special values to indicate an empty or deleted entry. |
| 160 static T* Empty() { return reinterpret_cast<T*>(0); } // i.e. NULL | 160 static T* Empty() { return reinterpret_cast<T*>(0); } // i.e. nullptr |
| 161 static T* Deleted() { return reinterpret_cast<T*>(1); } // Also an invalid
pointer. | 161 static T* Deleted() { return reinterpret_cast<T*>(1); } // Also an invalid
pointer. |
| 162 | 162 |
| 163 bool validate() const { | 163 bool validate() const { |
| 164 #define SKTDYNAMICHASH_CHECK(x) SkASSERT(x); if (!(x)) return false | 164 #define SKTDYNAMICHASH_CHECK(x) SkASSERT(x); if (!(x)) return false |
| 165 static const int kLarge = 50; // Arbitrary, tweak to suit your patience
. | 165 static const int kLarge = 50; // Arbitrary, tweak to suit your patience
. |
| 166 | 166 |
| 167 // O(1) checks, always done. | 167 // O(1) checks, always done. |
| 168 // Is capacity sane? | 168 // Is capacity sane? |
| 169 SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity)); | 169 SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity)); |
| 170 | 170 |
| (...skipping 109 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 280 static const Key& GetKey(const T& t) { return Traits::GetKey(t); } | 280 static const Key& GetKey(const T& t) { return Traits::GetKey(t); } |
| 281 static uint32_t Hash(const Key& key) { return Traits::Hash(key); } | 281 static uint32_t Hash(const Key& key) { return Traits::Hash(key); } |
| 282 | 282 |
| 283 int fCount; // Number of non Empty(), non Deleted() entries in fArray. | 283 int fCount; // Number of non Empty(), non Deleted() entries in fArray. |
| 284 int fDeleted; // Number of Deleted() entries in fArray. | 284 int fDeleted; // Number of Deleted() entries in fArray. |
| 285 int fCapacity; // Number of entries in fArray. Always a power of 2. | 285 int fCapacity; // Number of entries in fArray. Always a power of 2. |
| 286 T** fArray; | 286 T** fArray; |
| 287 }; | 287 }; |
| 288 | 288 |
| 289 #endif | 289 #endif |
| OLD | NEW |