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 |
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
50 } while (!this->done() && (this->current() == Empty() || this->curre
nt() == Deleted())); | 50 } while (!this->done() && (this->current() == Empty() || this->curre
nt() == Deleted())); |
51 } | 51 } |
52 | 52 |
53 private: | 53 private: |
54 T* current() const { return fHash->fArray[fCurrentIndex]; } | 54 T* current() const { return fHash->fArray[fCurrentIndex]; } |
55 | 55 |
56 SkTDynamicHash* fHash; | 56 SkTDynamicHash* fHash; |
57 int fCurrentIndex; | 57 int fCurrentIndex; |
58 }; | 58 }; |
59 | 59 |
| 60 class ConstIter { |
| 61 public: |
| 62 explicit ConstIter(const SkTDynamicHash* hash) : fHash(hash), fCurrentIn
dex(-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->curre
nt() == Deleted())); |
| 78 } |
| 79 |
| 80 private: |
| 81 const T* current() const { return fHash->fArray[fCurrentIndex]; } |
| 82 |
| 83 const SkTDynamicHash* fHash; |
| 84 int fCurrentIndex; |
| 85 }; |
| 86 |
60 int count() const { return fCount; } | 87 int count() const { return fCount; } |
61 | 88 |
62 // Return the entry with this key if we have it, otherwise NULL. | 89 // Return the entry with this key if we have it, otherwise NULL. |
63 T* find(const Key& key) const { | 90 T* find(const Key& key) const { |
64 int index = this->firstIndex(key); | 91 int index = this->firstIndex(key); |
65 for (int round = 0; round < fCapacity; round++) { | 92 for (int round = 0; round < fCapacity; round++) { |
66 SkASSERT(index >= 0 && index < fCapacity); | 93 SkASSERT(index >= 0 && index < fCapacity); |
67 T* candidate = fArray[index]; | 94 T* candidate = fArray[index]; |
68 if (Empty() == candidate) { | 95 if (Empty() == candidate) { |
69 return NULL; | 96 return NULL; |
70 } | 97 } |
71 if (Deleted() != candidate && GetKey(*candidate) == key) { | 98 if (Deleted() != candidate && GetKey(*candidate) == key) { |
72 return candidate; | 99 return candidate; |
73 } | 100 } |
74 index = this->nextIndex(index, round); | 101 index = this->nextIndex(index, round); |
75 } | 102 } |
76 SkASSERT(fCapacity == 0); | 103 SkASSERT(fCapacity == 0); |
77 return NULL; | 104 return NULL; |
78 } | 105 } |
79 | 106 |
80 // 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. |
81 void add(T* newEntry) { | 108 void add(T* newEntry) { |
82 SkASSERT(NULL == this->find(GetKey(*newEntry))); | 109 SkASSERT(NULL == this->find(GetKey(*newEntry))); |
83 this->maybeGrow(); | 110 this->maybeGrow(); |
84 this->innerAdd(newEntry); | 111 this->innerAdd(newEntry); |
85 SkASSERT(this->validate()); | 112 SkASSERT(this->validate()); |
86 } | 113 } |
87 | 114 |
88 // Remove the entry with this key. We reqire that an entry with this key is
present. | 115 // Remove the entry with this key. We require that an entry with this key i
s present. |
89 void remove(const Key& key) { | 116 void remove(const Key& key) { |
90 SkASSERT(NULL != this->find(key)); | 117 SkASSERT(NULL != this->find(key)); |
91 this->innerRemove(key); | 118 this->innerRemove(key); |
92 SkASSERT(this->validate()); | 119 SkASSERT(this->validate()); |
93 } | 120 } |
94 | 121 |
| 122 void rewind() { |
| 123 if (NULL != fArray) { |
| 124 sk_bzero(fArray, sizeof(T*)* fCapacity); |
| 125 } |
| 126 fCount = 0; |
| 127 fDeleted = 0; |
| 128 } |
| 129 |
| 130 void reset() { |
| 131 fCount = 0; |
| 132 fDeleted = 0; |
| 133 fCapacity = 0; |
| 134 sk_free(fArray); |
| 135 fArray = NULL; |
| 136 } |
| 137 |
95 protected: | 138 protected: |
96 // These methods are used by tests only. | 139 // These methods are used by tests only. |
97 | 140 |
98 int capacity() const { return fCapacity; } | 141 int capacity() const { return fCapacity; } |
99 | 142 |
100 // 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? |
101 int countCollisions(const Key& key) const { | 144 int countCollisions(const Key& key) const { |
102 int index = this->firstIndex(key); | 145 int index = this->firstIndex(key); |
103 for (int round = 0; round < fCapacity; round++) { | 146 for (int round = 0; round < fCapacity; round++) { |
104 SkASSERT(index >= 0 && index < fCapacity); | 147 SkASSERT(index >= 0 && index < fCapacity); |
(...skipping 132 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
237 static const Key& GetKey(const T& t) { return Traits::GetKey(t); } | 280 static const Key& GetKey(const T& t) { return Traits::GetKey(t); } |
238 static uint32_t Hash(const Key& key) { return Traits::Hash(key); } | 281 static uint32_t Hash(const Key& key) { return Traits::Hash(key); } |
239 | 282 |
240 int fCount; // Number of non Empty(), non Deleted() entries in fArray. | 283 int fCount; // Number of non Empty(), non Deleted() entries in fArray. |
241 int fDeleted; // Number of Deleted() entries in fArray. | 284 int fDeleted; // Number of Deleted() entries in fArray. |
242 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. |
243 T** fArray; | 286 T** fArray; |
244 }; | 287 }; |
245 | 288 |
246 #endif | 289 #endif |
OLD | NEW |