Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(197)

Side by Side Diff: src/core/SkTDynamicHash.h

Issue 222343002: SkTDynamicHash: remove need for Equals(const T&, const Key&) param. (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: Created 6 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/core/SkScaledImageCache.cpp ('k') | src/gpu/GrResourceCache.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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 template <typename T, 15 template <typename T,
16 typename Key, 16 typename Key,
17 const Key& (GetKey)(const T&), 17 const Key& (GetKey)(const T&),
18 uint32_t (Hash)(const Key&), 18 uint32_t (Hash)(const Key&),
19 bool (Equal)(const T&, const Key&),
20 int kGrowPercent = 75> // Larger -> more memory efficient, but slower . 19 int kGrowPercent = 75> // Larger -> more memory efficient, but slower .
21 class SkTDynamicHash { 20 class SkTDynamicHash {
22 public: 21 public:
23 SkTDynamicHash() : fCount(0), fDeleted(0), fCapacity(0), fArray(NULL) { 22 SkTDynamicHash() : fCount(0), fDeleted(0), fCapacity(0), fArray(NULL) {
24 SkASSERT(this->validate()); 23 SkASSERT(this->validate());
25 } 24 }
26 25
27 ~SkTDynamicHash() { 26 ~SkTDynamicHash() {
28 sk_free(fArray); 27 sk_free(fArray);
29 } 28 }
(...skipping 28 matching lines...) Expand all
58 int count() const { return fCount; } 57 int count() const { return fCount; }
59 58
60 // Return the entry with this key if we have it, otherwise NULL. 59 // Return the entry with this key if we have it, otherwise NULL.
61 T* find(const Key& key) const { 60 T* find(const Key& key) const {
62 int index = this->firstIndex(key); 61 int index = this->firstIndex(key);
63 for (int round = 0; round < fCapacity; round++) { 62 for (int round = 0; round < fCapacity; round++) {
64 T* candidate = fArray[index]; 63 T* candidate = fArray[index];
65 if (Empty() == candidate) { 64 if (Empty() == candidate) {
66 return NULL; 65 return NULL;
67 } 66 }
68 if (Deleted() != candidate && Equal(*candidate, key)) { 67 if (Deleted() != candidate && GetKey(*candidate) == key) {
69 return candidate; 68 return candidate;
70 } 69 }
71 index = this->nextIndex(index, round); 70 index = this->nextIndex(index, round);
72 } 71 }
73 SkASSERT(fCapacity == 0); 72 SkASSERT(fCapacity == 0);
74 return NULL; 73 return NULL;
75 } 74 }
76 75
77 // Add an entry with this key. We require that no entry with newEntry's key is already present. 76 // Add an entry with this key. We require that no entry with newEntry's key is already present.
78 void add(T* newEntry) { 77 void add(T* newEntry) {
(...skipping 13 matching lines...) Expand all
92 protected: 91 protected:
93 // These methods are used by tests only. 92 // These methods are used by tests only.
94 93
95 int capacity() const { return fCapacity; } 94 int capacity() const { return fCapacity; }
96 95
97 // How many collisions do we go through before finding where this entry shou ld be inserted? 96 // How many collisions do we go through before finding where this entry shou ld be inserted?
98 int countCollisions(const Key& key) const { 97 int countCollisions(const Key& key) const {
99 int index = this->firstIndex(key); 98 int index = this->firstIndex(key);
100 for (int round = 0; round < fCapacity; round++) { 99 for (int round = 0; round < fCapacity; round++) {
101 const T* candidate = fArray[index]; 100 const T* candidate = fArray[index];
102 if (Empty() == candidate || Deleted() == candidate || Equal(*candida te, key)) { 101 if (Empty() == candidate || Deleted() == candidate || GetKey(*candid ate) == key) {
103 return round; 102 return round;
104 } 103 }
105 index = this->nextIndex(index, round); 104 index = this->nextIndex(index, round);
106 } 105 }
107 SkASSERT(fCapacity == 0); 106 SkASSERT(fCapacity == 0);
108 return 0; 107 return 0;
109 } 108 }
110 109
111 private: 110 private:
112 // We have two special values to indicate an empty or deleted entry. 111 // We have two special values to indicate an empty or deleted entry.
(...skipping 29 matching lines...) Expand all
142 // Are all entries unique? 141 // Are all entries unique?
143 for (int i = 0; i < fCapacity; i++) { 142 for (int i = 0; i < fCapacity; i++) {
144 if (Empty() == fArray[i] || Deleted() == fArray[i]) { 143 if (Empty() == fArray[i] || Deleted() == fArray[i]) {
145 continue; 144 continue;
146 } 145 }
147 for (int j = i+1; j < fCapacity; j++) { 146 for (int j = i+1; j < fCapacity; j++) {
148 if (Empty() == fArray[j] || Deleted() == fArray[j]) { 147 if (Empty() == fArray[j] || Deleted() == fArray[j]) {
149 continue; 148 continue;
150 } 149 }
151 SKTDYNAMICHASH_CHECK(fArray[i] != fArray[j]); 150 SKTDYNAMICHASH_CHECK(fArray[i] != fArray[j]);
152 SKTDYNAMICHASH_CHECK(!Equal(*fArray[i], GetKey(*fArray[j]))) ; 151 SKTDYNAMICHASH_CHECK(!(GetKey(*fArray[i]) == GetKey(*fArray[ j])));
153 SKTDYNAMICHASH_CHECK(!Equal(*fArray[j], GetKey(*fArray[i]))) ;
154 } 152 }
155 } 153 }
156 } 154 }
157 #undef SKTDYNAMICHASH_CHECK 155 #undef SKTDYNAMICHASH_CHECK
158 return true; 156 return true;
159 } 157 }
160 158
161 void innerAdd(T* newEntry) { 159 void innerAdd(T* newEntry) {
162 const Key& key = GetKey(*newEntry); 160 const Key& key = GetKey(*newEntry);
163 int index = this->firstIndex(key); 161 int index = this->firstIndex(key);
(...skipping 10 matching lines...) Expand all
174 index = this->nextIndex(index, round); 172 index = this->nextIndex(index, round);
175 } 173 }
176 SkASSERT(fCapacity == 0); 174 SkASSERT(fCapacity == 0);
177 } 175 }
178 176
179 void innerRemove(const Key& key) { 177 void innerRemove(const Key& key) {
180 const int firstIndex = this->firstIndex(key); 178 const int firstIndex = this->firstIndex(key);
181 int index = firstIndex; 179 int index = firstIndex;
182 for (int round = 0; round < fCapacity; round++) { 180 for (int round = 0; round < fCapacity; round++) {
183 const T* candidate = fArray[index]; 181 const T* candidate = fArray[index];
184 if (Deleted() != candidate && Equal(*candidate, key)) { 182 if (Deleted() != candidate && GetKey(*candidate) == key) {
185 fDeleted++; 183 fDeleted++;
186 fCount--; 184 fCount--;
187 fArray[index] = Deleted(); 185 fArray[index] = Deleted();
188 return; 186 return;
189 } 187 }
190 index = this->nextIndex(index, round); 188 index = this->nextIndex(index, round);
191 } 189 }
192 SkASSERT(fCapacity == 0); 190 SkASSERT(fCapacity == 0);
193 } 191 }
194 192
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after
229 return (index + round + 1) & this->hashMask(); 227 return (index + round + 1) & this->hashMask();
230 } 228 }
231 229
232 int fCount; // Number of non Empty(), non Deleted() entries in fArray. 230 int fCount; // Number of non Empty(), non Deleted() entries in fArray.
233 int fDeleted; // Number of Deleted() entries in fArray. 231 int fDeleted; // Number of Deleted() entries in fArray.
234 int fCapacity; // Number of entries in fArray. Always a power of 2. 232 int fCapacity; // Number of entries in fArray. Always a power of 2.
235 T** fArray; 233 T** fArray;
236 }; 234 };
237 235
238 #endif 236 #endif
OLDNEW
« no previous file with comments | « src/core/SkScaledImageCache.cpp ('k') | src/gpu/GrResourceCache.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698