OLD | NEW |
1 #ifndef SkTHash_DEFINED | 1 #ifndef SkTHash_DEFINED |
2 #define SkTHash_DEFINED | 2 #define SkTHash_DEFINED |
3 | 3 |
4 #include "SkTypes.h" | 4 #include "SkTypes.h" |
5 #include "SkTemplates.h" | 5 #include "SkTemplates.h" |
6 | 6 |
7 // Before trying to use SkTHashTable, look below to see if SkTHashMap or SkTHash
Set works for you. | 7 // Before trying to use SkTHashTable, look below to see if SkTHashMap or SkTHash
Set works for you. |
8 // They're easier to use, usually perform the same, and have fewer sharp edges. | 8 // They're easier to use, usually perform the same, and have fewer sharp edges. |
9 | 9 |
10 // T and K are treated as ordinary copyable C++ types. | 10 // T and K are treated as ordinary copyable C++ types. |
11 // Traits must have: | 11 // Traits must have: |
12 // - static K GetKey(T) | 12 // - static K GetKey(T) |
13 // - static uint32_t Hash(K) | 13 // - static uint32_t Hash(K) |
14 // If the key is large and stored inside T, you may want to make K a const&. | 14 // If the key is large and stored inside T, you may want to make K a const&. |
15 // Similarly, if T is large you might want it to be a pointer. | 15 // Similarly, if T is large you might want it to be a pointer. |
16 template <typename T, typename K, typename Traits = T> | 16 template <typename T, typename K, typename Traits = T> |
17 class SkTHashTable : SkNoncopyable { | 17 class SkTHashTable : SkNoncopyable { |
18 public: | 18 public: |
19 SkTHashTable() : fCount(0), fCapacity(0) {} | 19 SkTHashTable() : fCount(0), fCapacity(0) {} |
20 | 20 |
| 21 // Clear the table. |
| 22 void reset() { |
| 23 this->~SkTHashTable(); |
| 24 SkNEW_PLACEMENT(this, SkTHashTable); |
| 25 } |
| 26 |
21 // How many entries are in the table? | 27 // How many entries are in the table? |
22 int count() const { return fCount; } | 28 int count() const { return fCount; } |
23 | 29 |
24 // !!!!!!!!!!!!!!!!! CAUTION !!!!!!!!!!!!!
!!!! | 30 // !!!!!!!!!!!!!!!!! CAUTION !!!!!!!!!!!!!
!!!! |
25 // set(), find() and foreach() all allow mutable access to table entries. | 31 // set(), find() and foreach() all allow mutable access to table entries. |
26 // If you change an entry so that it no longer has the same key, all hell | 32 // If you change an entry so that it no longer has the same key, all hell |
27 // will break loose. Do not do that! | 33 // will break loose. Do not do that! |
28 // | 34 // |
29 // Please prefer to use SkTHashMap or SkTHashSet, which do not have this dan
ger. | 35 // Please prefer to use SkTHashMap or SkTHashSet, which do not have this dan
ger. |
30 | 36 |
(...skipping 106 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
137 SkAutoTArray<Slot> fSlots; | 143 SkAutoTArray<Slot> fSlots; |
138 }; | 144 }; |
139 | 145 |
140 // Maps K->V. A more user-friendly wrapper around SkTHashTable, suitable for mo
st use cases. | 146 // Maps K->V. A more user-friendly wrapper around SkTHashTable, suitable for mo
st use cases. |
141 // K and V are treated as ordinary copyable C++ types, with no assumed relations
hip between the two. | 147 // K and V are treated as ordinary copyable C++ types, with no assumed relations
hip between the two. |
142 template <typename K, typename V, uint32_t(*HashK)(const K&)> | 148 template <typename K, typename V, uint32_t(*HashK)(const K&)> |
143 class SkTHashMap : SkNoncopyable { | 149 class SkTHashMap : SkNoncopyable { |
144 public: | 150 public: |
145 SkTHashMap() {} | 151 SkTHashMap() {} |
146 | 152 |
| 153 // Clear the map. |
| 154 void reset() { fTable.reset(); } |
| 155 |
147 // How many key/value pairs are in the table? | 156 // How many key/value pairs are in the table? |
148 int count() const { return fTable.count(); } | 157 int count() const { return fTable.count(); } |
149 | 158 |
150 // N.B. The pointers returned by set() and find() are valid only until the n
ext call to set(). | 159 // N.B. The pointers returned by set() and find() are valid only until the n
ext call to set(). |
151 | 160 |
152 // Set key to val in the table, replacing any previous value with the same k
ey. | 161 // Set key to val in the table, replacing any previous value with the same k
ey. |
153 // We copy both key and val, and return a pointer to the value copy now in t
he table. | 162 // We copy both key and val, and return a pointer to the value copy now in t
he table. |
154 V* set(const K& key, const V& val) { | 163 V* set(const K& key, const V& val) { |
155 Pair in = { key, val }; | 164 Pair in = { key, val }; |
156 Pair* out = fTable.set(in); | 165 Pair* out = fTable.set(in); |
(...skipping 23 matching lines...) Expand all Loading... |
180 | 189 |
181 SkTHashTable<Pair, K> fTable; | 190 SkTHashTable<Pair, K> fTable; |
182 }; | 191 }; |
183 | 192 |
184 // A set of T. T is treated as an ordiary copyable C++ type. | 193 // A set of T. T is treated as an ordiary copyable C++ type. |
185 template <typename T, uint32_t(*HashT)(const T&)> | 194 template <typename T, uint32_t(*HashT)(const T&)> |
186 class SkTHashSet : SkNoncopyable { | 195 class SkTHashSet : SkNoncopyable { |
187 public: | 196 public: |
188 SkTHashSet() {} | 197 SkTHashSet() {} |
189 | 198 |
| 199 // Clear the set. |
| 200 void reset() { fTable.reset(); } |
| 201 |
190 // How many items are in the set? | 202 // How many items are in the set? |
191 int count() const { return fTable.count(); } | 203 int count() const { return fTable.count(); } |
192 | 204 |
193 // Copy an item into the set. | 205 // Copy an item into the set. |
194 void add(const T& item) { fTable.set(item); } | 206 void add(const T& item) { fTable.set(item); } |
195 | 207 |
196 // Is this item in the set? | 208 // Is this item in the set? |
197 bool contains(const T& item) const { return SkToBool(fTable.find(item)); } | 209 bool contains(const T& item) const { return SkToBool(fTable.find(item)); } |
198 | 210 |
199 private: | 211 private: |
200 struct Traits { | 212 struct Traits { |
201 static const T& GetKey(const T& item) { return item; } | 213 static const T& GetKey(const T& item) { return item; } |
202 static uint32_t Hash(const T& item) { return HashT(item); } | 214 static uint32_t Hash(const T& item) { return HashT(item); } |
203 }; | 215 }; |
204 SkTHashTable<T, T, Traits> fTable; | 216 SkTHashTable<T, T, Traits> fTable; |
205 }; | 217 }; |
206 | 218 |
207 #endif//SkTHash_DEFINED | 219 #endif//SkTHash_DEFINED |
OLD | NEW |