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 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
43 index = this->nextIndex(index, round); | 43 index = this->nextIndex(index, round); |
44 } | 44 } |
45 SkASSERT(fCapacity == 0); | 45 SkASSERT(fCapacity == 0); |
46 return NULL; | 46 return NULL; |
47 } | 47 } |
48 | 48 |
49 // Add an entry with this key. We require that no entry with newEntry's key
is already present. | 49 // Add an entry with this key. We require that no entry with newEntry's key
is already present. |
50 void add(T* newEntry) { | 50 void add(T* newEntry) { |
51 SkASSERT(NULL == this->find(GetKey(*newEntry))); | 51 SkASSERT(NULL == this->find(GetKey(*newEntry))); |
52 this->maybeGrow(); | 52 this->maybeGrow(); |
53 SkASSERT(this->validate()); | |
54 this->innerAdd(newEntry); | 53 this->innerAdd(newEntry); |
55 SkASSERT(this->validate()); | 54 SkASSERT(this->validate()); |
56 } | 55 } |
57 | 56 |
58 // Remove the entry with this key. We reqire that an entry with this key is
present. | 57 // Remove the entry with this key. We reqire that an entry with this key is
present. |
59 void remove(const Key& key) { | 58 void remove(const Key& key) { |
60 SkASSERT(NULL != this->find(key)); | 59 SkASSERT(NULL != this->find(key)); |
61 this->innerRemove(key); | 60 this->innerRemove(key); |
62 SkASSERT(this->validate()); | 61 SkASSERT(this->validate()); |
63 } | 62 } |
(...skipping 17 matching lines...) Expand all Loading... |
81 return 0; | 80 return 0; |
82 } | 81 } |
83 | 82 |
84 private: | 83 private: |
85 // We have two special values to indicate an empty or deleted entry. | 84 // We have two special values to indicate an empty or deleted entry. |
86 static T* Empty() { return reinterpret_cast<T*>(0); } // i.e. NULL | 85 static T* Empty() { return reinterpret_cast<T*>(0); } // i.e. NULL |
87 static T* Deleted() { return reinterpret_cast<T*>(1); } // Also an invalid
pointer. | 86 static T* Deleted() { return reinterpret_cast<T*>(1); } // Also an invalid
pointer. |
88 | 87 |
89 bool validate() const { | 88 bool validate() const { |
90 #define SKTDYNAMICHASH_CHECK(x) SkASSERT((x)); if (!(x)) return false | 89 #define SKTDYNAMICHASH_CHECK(x) SkASSERT((x)); if (!(x)) return false |
| 90 static const int kLarge = 50; // Arbitrary, tweak to suit your patience
. |
91 | 91 |
| 92 // O(1) checks, always done. |
92 // Is capacity sane? | 93 // Is capacity sane? |
93 SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity)); | 94 SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity)); |
94 | 95 |
95 // Is fCount correct? | 96 // O(N) checks, skipped when very large. |
96 int count = 0; | 97 if (fCount < kLarge * kLarge) { |
97 for (int i = 0; i < fCapacity; i++) { | 98 // Are fCount and fDeleted correct, and are all elements findable? |
98 if (Empty() != fArray[i] && Deleted() != fArray[i]) { | 99 int count = 0, deleted = 0; |
99 count++; | 100 for (int i = 0; i < fCapacity; i++) { |
| 101 if (Deleted() == fArray[i]) { |
| 102 deleted++; |
| 103 } else if (Empty() != fArray[i]) { |
| 104 count++; |
| 105 SKTDYNAMICHASH_CHECK(NULL != this->find(GetKey(*fArray[i])))
; |
| 106 } |
100 } | 107 } |
101 } | 108 SKTDYNAMICHASH_CHECK(count == fCount); |
102 SKTDYNAMICHASH_CHECK(count == fCount); | 109 SKTDYNAMICHASH_CHECK(deleted == fDeleted); |
103 | |
104 // Is fDeleted correct? | |
105 int deleted = 0; | |
106 for (int i = 0; i < fCapacity; i++) { | |
107 if (Deleted() == fArray[i]) { | |
108 deleted++; | |
109 } | |
110 } | |
111 SKTDYNAMICHASH_CHECK(deleted == fDeleted); | |
112 | |
113 // Are all entries findable? | |
114 for (int i = 0; i < fCapacity; i++) { | |
115 if (Empty() == fArray[i] || Deleted() == fArray[i]) { | |
116 continue; | |
117 } | |
118 SKTDYNAMICHASH_CHECK(NULL != this->find(GetKey(*fArray[i]))); | |
119 } | 110 } |
120 | 111 |
121 // Are all entries unique? | 112 // O(N^2) checks, skipped when large. |
122 for (int i = 0; i < fCapacity; i++) { | 113 if (fCount < kLarge) { |
123 if (Empty() == fArray[i] || Deleted() == fArray[i]) { | 114 // Are all entries unique? |
124 continue; | 115 for (int i = 0; i < fCapacity; i++) { |
125 } | 116 if (Empty() == fArray[i] || Deleted() == fArray[i]) { |
126 for (int j = i+1; j < fCapacity; j++) { | |
127 if (Empty() == fArray[j] || Deleted() == fArray[j]) { | |
128 continue; | 117 continue; |
129 } | 118 } |
130 SKTDYNAMICHASH_CHECK(fArray[i] != fArray[j]); | 119 for (int j = i+1; j < fCapacity; j++) { |
131 SKTDYNAMICHASH_CHECK(!Equal(*fArray[i], GetKey(*fArray[j]))); | 120 if (Empty() == fArray[j] || Deleted() == fArray[j]) { |
132 SKTDYNAMICHASH_CHECK(!Equal(*fArray[j], GetKey(*fArray[i]))); | 121 continue; |
| 122 } |
| 123 SKTDYNAMICHASH_CHECK(fArray[i] != fArray[j]); |
| 124 SKTDYNAMICHASH_CHECK(!Equal(*fArray[i], GetKey(*fArray[j])))
; |
| 125 SKTDYNAMICHASH_CHECK(!Equal(*fArray[j], GetKey(*fArray[i])))
; |
| 126 } |
133 } | 127 } |
134 } | 128 } |
135 #undef SKTDYNAMICHASH_CHECK | 129 #undef SKTDYNAMICHASH_CHECK |
136 return true; | 130 return true; |
137 } | 131 } |
138 | 132 |
139 void innerAdd(T* newEntry) { | 133 void innerAdd(T* newEntry) { |
140 const Key& key = GetKey(*newEntry); | 134 const Key& key = GetKey(*newEntry); |
141 int index = this->firstIndex(key); | 135 int index = this->firstIndex(key); |
142 for (int round = 0; round < fCapacity; round++) { | 136 for (int round = 0; round < fCapacity; round++) { |
(...skipping 64 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
207 return (index + round + 1) & this->hashMask(); | 201 return (index + round + 1) & this->hashMask(); |
208 } | 202 } |
209 | 203 |
210 int fCount; // Number of non Empty(), non Deleted() entries in fArray. | 204 int fCount; // Number of non Empty(), non Deleted() entries in fArray. |
211 int fDeleted; // Number of Deleted() entries in fArray. | 205 int fDeleted; // Number of Deleted() entries in fArray. |
212 int fCapacity; // Number of entries in fArray. Always a power of 2. | 206 int fCapacity; // Number of entries in fArray. Always a power of 2. |
213 T** fArray; | 207 T** fArray; |
214 }; | 208 }; |
215 | 209 |
216 #endif | 210 #endif |
OLD | NEW |