OLD | NEW |
| (Empty) |
1 | |
2 /* | |
3 * Copyright 2010 Google Inc. | |
4 * | |
5 * Use of this source code is governed by a BSD-style license that can be | |
6 * found in the LICENSE file. | |
7 */ | |
8 | |
9 | |
10 | |
11 #ifndef GrTHashTable_DEFINED | |
12 #define GrTHashTable_DEFINED | |
13 | |
14 #include "GrTypes.h" | |
15 #include "SkTDArray.h" | |
16 | |
17 /** | |
18 * Key needs | |
19 * static bool Equals(const Entry&, const Key&); | |
20 * static bool LessThan(const Entry&, const Key&); | |
21 * static bool Equals(const Entry&, const Entry&); for SK_DEBUG if GrTHashT
able::validate() is called | |
22 * static bool LessThan(const Entry&, const Entry&); for SK_DEBUG if GrTHas
hTable::validate() is called | |
23 * uint32_t getHash() const; | |
24 * | |
25 * Allows duplicate key entries but on find you may get | |
26 * any of the duplicate entries returned. | |
27 */ | |
28 template <typename T, typename Key, size_t kHashBits> class GrTHashTable { | |
29 public: | |
30 GrTHashTable() { this->clearHash(); } | |
31 ~GrTHashTable() {} | |
32 | |
33 int count() const { return fSorted.count(); } | |
34 | |
35 struct Any { | |
36 // Return the first resource that matches the key. | |
37 bool operator()(const T*) const { return true; } | |
38 }; | |
39 | |
40 T* find(const Key& key) const { return this->find(key, Any()); } | |
41 template <typename Filter> T* find(const Key&, Filter filter) const; | |
42 | |
43 // return true if key was unique when inserted. | |
44 bool insert(const Key&, T*); | |
45 void remove(const Key&, const T*); | |
46 | |
47 void deleteAll(); | |
48 | |
49 #ifdef SK_DEBUG | |
50 void validate() const; | |
51 bool contains(T*) const; | |
52 #endif | |
53 | |
54 // testing | |
55 const SkTDArray<T*>& getArray() const { return fSorted; } | |
56 SkTDArray<T*>& getArray() { return fSorted; } | |
57 private: | |
58 void clearHash() { sk_bzero(fHash, sizeof(fHash)); } | |
59 | |
60 enum { | |
61 kHashCount = 1 << kHashBits, | |
62 kHashMask = kHashCount - 1 | |
63 }; | |
64 static unsigned hash2Index(intptr_t hash) { | |
65 #if 0 | |
66 if (sizeof(hash) == 8) { | |
67 hash ^= hash >> 32; | |
68 } | |
69 #endif | |
70 hash ^= hash >> 16; | |
71 if (kHashBits <= 8) { | |
72 hash ^= hash >> 8; | |
73 } | |
74 return hash & kHashMask; | |
75 } | |
76 | |
77 mutable T* fHash[kHashCount]; | |
78 SkTDArray<T*> fSorted; | |
79 | |
80 // search fSorted, and return the found index, or ~index of where it | |
81 // should be inserted | |
82 int searchArray(const Key&) const; | |
83 }; | |
84 | |
85 /////////////////////////////////////////////////////////////////////////////// | |
86 | |
87 template <typename T, typename Key, size_t kHashBits> | |
88 int GrTHashTable<T, Key, kHashBits>::searchArray(const Key& key) const { | |
89 int count = fSorted.count(); | |
90 if (0 == count) { | |
91 // we should insert it at 0 | |
92 return ~0; | |
93 } | |
94 | |
95 const T* const* array = fSorted.begin(); | |
96 int high = count - 1; | |
97 int low = 0; | |
98 while (high > low) { | |
99 int index = (low + high) >> 1; | |
100 if (Key::LessThan(*array[index], key)) { | |
101 low = index + 1; | |
102 } else { | |
103 high = index; | |
104 } | |
105 } | |
106 | |
107 // check if we found it | |
108 if (Key::Equals(*array[high], key)) { | |
109 // above search should have found the first occurrence if there | |
110 // are multiple. | |
111 SkASSERT(0 == high || Key::LessThan(*array[high - 1], key)); | |
112 return high; | |
113 } | |
114 | |
115 // now return the ~ of where we should insert it | |
116 if (Key::LessThan(*array[high], key)) { | |
117 high += 1; | |
118 } | |
119 return ~high; | |
120 } | |
121 | |
122 template <typename T, typename Key, size_t kHashBits> | |
123 template <typename Filter> | |
124 T* GrTHashTable<T, Key, kHashBits>::find(const Key& key, Filter filter) const { | |
125 | |
126 int hashIndex = hash2Index(key.getHash()); | |
127 T* elem = fHash[hashIndex]; | |
128 | |
129 if (NULL != elem && Key::Equals(*elem, key) && filter(elem)) { | |
130 return elem; | |
131 } | |
132 | |
133 // bsearch for the key in our sorted array | |
134 int index = this->searchArray(key); | |
135 if (index < 0) { | |
136 return NULL; | |
137 } | |
138 | |
139 const T* const* array = fSorted.begin(); | |
140 | |
141 // above search should have found the first occurrence if there | |
142 // are multiple. | |
143 SkASSERT(0 == index || Key::LessThan(*array[index - 1], key)); | |
144 | |
145 for ( ; index < count() && Key::Equals(*array[index], key); ++index) { | |
146 if (filter(fSorted[index])) { | |
147 // update the hash | |
148 fHash[hashIndex] = fSorted[index]; | |
149 return fSorted[index]; | |
150 } | |
151 } | |
152 | |
153 return NULL; | |
154 } | |
155 | |
156 template <typename T, typename Key, size_t kHashBits> | |
157 bool GrTHashTable<T, Key, kHashBits>::insert(const Key& key, T* elem) { | |
158 int index = this->searchArray(key); | |
159 bool first = index < 0; | |
160 if (first) { | |
161 // turn it into the actual index | |
162 index = ~index; | |
163 } | |
164 // add it to our array | |
165 *fSorted.insert(index) = elem; | |
166 // update our hash table (overwrites any dupe's position in the hash) | |
167 fHash[hash2Index(key.getHash())] = elem; | |
168 return first; | |
169 } | |
170 | |
171 template <typename T, typename Key, size_t kHashBits> | |
172 void GrTHashTable<T, Key, kHashBits>::remove(const Key& key, const T* elem) { | |
173 int index = hash2Index(key.getHash()); | |
174 if (fHash[index] == elem) { | |
175 fHash[index] = NULL; | |
176 } | |
177 | |
178 // remove from our sorted array | |
179 index = this->searchArray(key); | |
180 SkASSERT(index >= 0); | |
181 // if there are multiple matches searchArray will give us the first match | |
182 // march forward until we find elem. | |
183 while (elem != fSorted[index]) { | |
184 ++index; | |
185 SkASSERT(index < fSorted.count()); | |
186 } | |
187 SkASSERT(elem == fSorted[index]); | |
188 fSorted.remove(index); | |
189 } | |
190 | |
191 template <typename T, typename Key, size_t kHashBits> | |
192 void GrTHashTable<T, Key, kHashBits>::deleteAll() { | |
193 fSorted.deleteAll(); | |
194 this->clearHash(); | |
195 } | |
196 | |
197 #ifdef SK_DEBUG | |
198 template <typename T, typename Key, size_t kHashBits> | |
199 void GrTHashTable<T, Key, kHashBits>::validate() const { | |
200 int count = fSorted.count(); | |
201 for (int i = 1; i < count; i++) { | |
202 SkASSERT(Key::LessThan(*fSorted[i - 1], *fSorted[i]) || | |
203 Key::Equals(*fSorted[i - 1], *fSorted[i])); | |
204 } | |
205 } | |
206 | |
207 template <typename T, typename Key, size_t kHashBits> | |
208 bool GrTHashTable<T, Key, kHashBits>::contains(T* elem) const { | |
209 int index = fSorted.find(elem); | |
210 return index >= 0; | |
211 } | |
212 | |
213 #endif | |
214 | |
215 #endif | |
OLD | NEW |