rev |
line source |
nuclear@3
|
1 /************************************************************************************
|
nuclear@3
|
2
|
nuclear@3
|
3 PublicHeader: None
|
nuclear@3
|
4 Filename : OVR_Hash.h
|
nuclear@3
|
5 Content : Template hash-table/set implementation
|
nuclear@3
|
6 Created : September 19, 2012
|
nuclear@3
|
7 Notes :
|
nuclear@3
|
8
|
nuclear@3
|
9 Copyright : Copyright 2012 Oculus VR, Inc. All Rights reserved.
|
nuclear@3
|
10
|
nuclear@3
|
11 Use of this software is subject to the terms of the Oculus license
|
nuclear@3
|
12 agreement provided at the time of installation or download, or which
|
nuclear@3
|
13 otherwise accompanies this software in either electronic or hard copy form.
|
nuclear@3
|
14
|
nuclear@3
|
15 ************************************************************************************/
|
nuclear@3
|
16
|
nuclear@3
|
17 #ifndef OVR_Hash_h
|
nuclear@3
|
18 #define OVR_Hash_h
|
nuclear@3
|
19
|
nuclear@3
|
20 #include "OVR_ContainerAllocator.h"
|
nuclear@3
|
21 #include "OVR_Alg.h"
|
nuclear@3
|
22
|
nuclear@3
|
23 // 'new' operator is redefined/used in this file.
|
nuclear@3
|
24 #undef new
|
nuclear@3
|
25
|
nuclear@3
|
26 namespace OVR {
|
nuclear@3
|
27
|
nuclear@3
|
28 //-----------------------------------------------------------------------------------
|
nuclear@3
|
29 // ***** Hash Table Implementation
|
nuclear@3
|
30
|
nuclear@3
|
31 // HastSet and Hash.
|
nuclear@3
|
32 //
|
nuclear@3
|
33 // Hash table, linear probing, internal chaining. One interesting/nice thing
|
nuclear@3
|
34 // about this implementation is that the table itself is a flat chunk of memory
|
nuclear@3
|
35 // containing no pointers, only relative indices. If the key and value types
|
nuclear@3
|
36 // of the Hash contain no pointers, then the Hash can be serialized using raw IO.
|
nuclear@3
|
37 //
|
nuclear@3
|
38 // Never shrinks, unless you explicitly Clear() it. Expands on
|
nuclear@3
|
39 // demand, though. For best results, if you know roughly how big your
|
nuclear@3
|
40 // table will be, default it to that size when you create it.
|
nuclear@3
|
41 //
|
nuclear@3
|
42 // Key usability feature:
|
nuclear@3
|
43 //
|
nuclear@3
|
44 // 1. Allows node hash values to either be cached or not.
|
nuclear@3
|
45 //
|
nuclear@3
|
46 // 2. Allows for alternative keys with methods such as GetAlt(). Handy
|
nuclear@3
|
47 // if you need to search nodes by their components; no need to create
|
nuclear@3
|
48 // temporary nodes.
|
nuclear@3
|
49 //
|
nuclear@3
|
50
|
nuclear@3
|
51
|
nuclear@3
|
52 // *** Hash functors:
|
nuclear@3
|
53 //
|
nuclear@3
|
54 // IdentityHash - use when the key is already a good hash
|
nuclear@3
|
55 // HFixedSizeHash - general hash based on object's in-memory representation.
|
nuclear@3
|
56
|
nuclear@3
|
57
|
nuclear@3
|
58 // Hash is just the input value; can use this for integer-indexed hash tables.
|
nuclear@3
|
59 template<class C>
|
nuclear@3
|
60 class IdentityHash
|
nuclear@3
|
61 {
|
nuclear@3
|
62 public:
|
nuclear@3
|
63 UPInt operator()(const C& data) const
|
nuclear@3
|
64 { return (UPInt) data; }
|
nuclear@3
|
65 };
|
nuclear@3
|
66
|
nuclear@3
|
67 // Computes a hash of an object's representation.
|
nuclear@3
|
68 template<class C>
|
nuclear@3
|
69 class FixedSizeHash
|
nuclear@3
|
70 {
|
nuclear@3
|
71 public:
|
nuclear@3
|
72 // Alternative: "sdbm" hash function, suggested at same web page
|
nuclear@3
|
73 // above, http::/www.cs.yorku.ca/~oz/hash.html
|
nuclear@3
|
74 // This is somewhat slower then Bernstein, but it works way better than the above
|
nuclear@3
|
75 // hash function for hashing large numbers of 32-bit ints.
|
nuclear@3
|
76 static OVR_FORCE_INLINE UPInt SDBM_Hash(const void* data_in, UPInt size, UPInt seed = 5381)
|
nuclear@3
|
77 {
|
nuclear@3
|
78 const UByte* data = (const UByte*) data_in;
|
nuclear@3
|
79 UPInt h = seed;
|
nuclear@3
|
80 while (size > 0)
|
nuclear@3
|
81 {
|
nuclear@3
|
82 size--;
|
nuclear@3
|
83 h = (h << 16) + (h << 6) - h + (UPInt)data[size];
|
nuclear@3
|
84 }
|
nuclear@3
|
85 return h;
|
nuclear@3
|
86 }
|
nuclear@3
|
87
|
nuclear@3
|
88 UPInt operator()(const C& data) const
|
nuclear@3
|
89 {
|
nuclear@3
|
90 unsigned char* p = (unsigned char*) &data;
|
nuclear@3
|
91 int size = sizeof(C);
|
nuclear@3
|
92
|
nuclear@3
|
93 return SDBM_Hash(p, size);
|
nuclear@3
|
94 }
|
nuclear@3
|
95 };
|
nuclear@3
|
96
|
nuclear@3
|
97
|
nuclear@3
|
98
|
nuclear@3
|
99 // *** HashsetEntry Entry types.
|
nuclear@3
|
100
|
nuclear@3
|
101 // Compact hash table Entry type that re-computes hash keys during hash traversal.
|
nuclear@3
|
102 // Good to use if the hash function is cheap or the hash value is already cached in C.
|
nuclear@3
|
103 template<class C, class HashF>
|
nuclear@3
|
104 class HashsetEntry
|
nuclear@3
|
105 {
|
nuclear@3
|
106 public:
|
nuclear@3
|
107 // Internal chaining for collisions.
|
nuclear@3
|
108 SPInt NextInChain;
|
nuclear@3
|
109 C Value;
|
nuclear@3
|
110
|
nuclear@3
|
111 HashsetEntry()
|
nuclear@3
|
112 : NextInChain(-2) { }
|
nuclear@3
|
113 HashsetEntry(const HashsetEntry& e)
|
nuclear@3
|
114 : NextInChain(e.NextInChain), Value(e.Value) { }
|
nuclear@3
|
115 HashsetEntry(const C& key, SPInt next)
|
nuclear@3
|
116 : NextInChain(next), Value(key) { }
|
nuclear@3
|
117
|
nuclear@3
|
118 bool IsEmpty() const { return NextInChain == -2; }
|
nuclear@3
|
119 bool IsEndOfChain() const { return NextInChain == -1; }
|
nuclear@3
|
120
|
nuclear@3
|
121 // Cached hash value access - can be optimized bu storing hash locally.
|
nuclear@3
|
122 // Mask value only needs to be used if SetCachedHash is not implemented.
|
nuclear@3
|
123 UPInt GetCachedHash(UPInt maskValue) const { return HashF()(Value) & maskValue; }
|
nuclear@3
|
124 void SetCachedHash(UPInt) {}
|
nuclear@3
|
125
|
nuclear@3
|
126 void Clear()
|
nuclear@3
|
127 {
|
nuclear@3
|
128 Value.~C(); // placement delete
|
nuclear@3
|
129 NextInChain = -2;
|
nuclear@3
|
130 }
|
nuclear@3
|
131 // Free is only used from dtor of hash; Clear is used during regular operations:
|
nuclear@3
|
132 // assignment, hash reallocations, value reassignments, so on.
|
nuclear@3
|
133 void Free() { Clear(); }
|
nuclear@3
|
134 };
|
nuclear@3
|
135
|
nuclear@3
|
136 // Hash table Entry type that caches the Entry hash value for nodes, so that it
|
nuclear@3
|
137 // does not need to be re-computed during access.
|
nuclear@3
|
138 template<class C, class HashF>
|
nuclear@3
|
139 class HashsetCachedEntry
|
nuclear@3
|
140 {
|
nuclear@3
|
141 public:
|
nuclear@3
|
142 // Internal chaining for collisions.
|
nuclear@3
|
143 SPInt NextInChain;
|
nuclear@3
|
144 UPInt HashValue;
|
nuclear@3
|
145 C Value;
|
nuclear@3
|
146
|
nuclear@3
|
147 HashsetCachedEntry()
|
nuclear@3
|
148 : NextInChain(-2) { }
|
nuclear@3
|
149 HashsetCachedEntry(const HashsetCachedEntry& e)
|
nuclear@3
|
150 : NextInChain(e.NextInChain), HashValue(e.HashValue), Value(e.Value) { }
|
nuclear@3
|
151 HashsetCachedEntry(const C& key, SPInt next)
|
nuclear@3
|
152 : NextInChain(next), Value(key) { }
|
nuclear@3
|
153
|
nuclear@3
|
154 bool IsEmpty() const { return NextInChain == -2; }
|
nuclear@3
|
155 bool IsEndOfChain() const { return NextInChain == -1; }
|
nuclear@3
|
156
|
nuclear@3
|
157 // Cached hash value access - can be optimized bu storing hash locally.
|
nuclear@3
|
158 // Mask value only needs to be used if SetCachedHash is not implemented.
|
nuclear@3
|
159 UPInt GetCachedHash(UPInt maskValue) const { OVR_UNUSED(maskValue); return HashValue; }
|
nuclear@3
|
160 void SetCachedHash(UPInt hashValue) { HashValue = hashValue; }
|
nuclear@3
|
161
|
nuclear@3
|
162 void Clear()
|
nuclear@3
|
163 {
|
nuclear@3
|
164 Value.~C();
|
nuclear@3
|
165 NextInChain = -2;
|
nuclear@3
|
166 }
|
nuclear@3
|
167 // Free is only used from dtor of hash; Clear is used during regular operations:
|
nuclear@3
|
168 // assignment, hash reallocations, value reassignments, so on.
|
nuclear@3
|
169 void Free() { Clear(); }
|
nuclear@3
|
170 };
|
nuclear@3
|
171
|
nuclear@3
|
172
|
nuclear@3
|
173 //-----------------------------------------------------------------------------------
|
nuclear@3
|
174 // *** HashSet implementation - relies on either cached or regular entries.
|
nuclear@3
|
175 //
|
nuclear@3
|
176 // Use: Entry = HashsetCachedEntry<C, HashF> if hashes are expensive to
|
nuclear@3
|
177 // compute and thus need caching in entries.
|
nuclear@3
|
178 // Entry = HashsetEntry<C, HashF> if hashes are already externally cached.
|
nuclear@3
|
179 //
|
nuclear@3
|
180 template<class C, class HashF = FixedSizeHash<C>,
|
nuclear@3
|
181 class AltHashF = HashF,
|
nuclear@3
|
182 class Allocator = ContainerAllocator<C>,
|
nuclear@3
|
183 class Entry = HashsetCachedEntry<C, HashF> >
|
nuclear@3
|
184 class HashSetBase
|
nuclear@3
|
185 {
|
nuclear@3
|
186 enum { HashMinSize = 8 };
|
nuclear@3
|
187
|
nuclear@3
|
188 public:
|
nuclear@3
|
189 OVR_MEMORY_REDEFINE_NEW(HashSetBase)
|
nuclear@3
|
190
|
nuclear@3
|
191 typedef HashSetBase<C, HashF, AltHashF, Allocator, Entry> SelfType;
|
nuclear@3
|
192
|
nuclear@3
|
193 HashSetBase() : pTable(NULL) { }
|
nuclear@3
|
194 HashSetBase(int sizeHint) : pTable(NULL) { SetCapacity(this, sizeHint); }
|
nuclear@3
|
195 HashSetBase(const SelfType& src) : pTable(NULL) { Assign(this, src); }
|
nuclear@3
|
196
|
nuclear@3
|
197 ~HashSetBase()
|
nuclear@3
|
198 {
|
nuclear@3
|
199 if (pTable)
|
nuclear@3
|
200 {
|
nuclear@3
|
201 // Delete the entries.
|
nuclear@3
|
202 for (UPInt i = 0, n = pTable->SizeMask; i <= n; i++)
|
nuclear@3
|
203 {
|
nuclear@3
|
204 Entry* e = &E(i);
|
nuclear@3
|
205 if (!e->IsEmpty())
|
nuclear@3
|
206 e->Free();
|
nuclear@3
|
207 }
|
nuclear@3
|
208
|
nuclear@3
|
209 Allocator::Free(pTable);
|
nuclear@3
|
210 pTable = NULL;
|
nuclear@3
|
211 }
|
nuclear@3
|
212 }
|
nuclear@3
|
213
|
nuclear@3
|
214
|
nuclear@3
|
215 void Assign(const SelfType& src)
|
nuclear@3
|
216 {
|
nuclear@3
|
217 Clear();
|
nuclear@3
|
218 if (src.IsEmpty() == false)
|
nuclear@3
|
219 {
|
nuclear@3
|
220 SetCapacity(src.GetSize());
|
nuclear@3
|
221
|
nuclear@3
|
222 for (ConstIterator it = src.Begin(); it != src.End(); ++it)
|
nuclear@3
|
223 {
|
nuclear@3
|
224 Add(*it);
|
nuclear@3
|
225 }
|
nuclear@3
|
226 }
|
nuclear@3
|
227 }
|
nuclear@3
|
228
|
nuclear@3
|
229
|
nuclear@3
|
230 // Remove all entries from the HashSet table.
|
nuclear@3
|
231 void Clear()
|
nuclear@3
|
232 {
|
nuclear@3
|
233 if (pTable)
|
nuclear@3
|
234 {
|
nuclear@3
|
235 // Delete the entries.
|
nuclear@3
|
236 for (UPInt i = 0, n = pTable->SizeMask; i <= n; i++)
|
nuclear@3
|
237 {
|
nuclear@3
|
238 Entry* e = &E(i);
|
nuclear@3
|
239 if (!e->IsEmpty())
|
nuclear@3
|
240 e->Clear();
|
nuclear@3
|
241 }
|
nuclear@3
|
242
|
nuclear@3
|
243 Allocator::Free(pTable);
|
nuclear@3
|
244 pTable = NULL;
|
nuclear@3
|
245 }
|
nuclear@3
|
246 }
|
nuclear@3
|
247
|
nuclear@3
|
248 // Returns true if the HashSet is empty.
|
nuclear@3
|
249 bool IsEmpty() const
|
nuclear@3
|
250 {
|
nuclear@3
|
251 return pTable == NULL || pTable->EntryCount == 0;
|
nuclear@3
|
252 }
|
nuclear@3
|
253
|
nuclear@3
|
254
|
nuclear@3
|
255 // Set a new or existing value under the key, to the value.
|
nuclear@3
|
256 // Pass a different class of 'key' so that assignment reference object
|
nuclear@3
|
257 // can be passed instead of the actual object.
|
nuclear@3
|
258 template<class CRef>
|
nuclear@3
|
259 void Set(const CRef& key)
|
nuclear@3
|
260 {
|
nuclear@3
|
261 UPInt hashValue = HashF()(key);
|
nuclear@3
|
262 SPInt index = (SPInt)-1;
|
nuclear@3
|
263
|
nuclear@3
|
264 if (pTable != NULL)
|
nuclear@3
|
265 index = findIndexCore(key, hashValue & pTable->SizeMask);
|
nuclear@3
|
266
|
nuclear@3
|
267 if (index >= 0)
|
nuclear@3
|
268 {
|
nuclear@3
|
269 E(index).Value = key;
|
nuclear@3
|
270 }
|
nuclear@3
|
271 else
|
nuclear@3
|
272 {
|
nuclear@3
|
273 // Entry under key doesn't exist.
|
nuclear@3
|
274 add(key, hashValue);
|
nuclear@3
|
275 }
|
nuclear@3
|
276 }
|
nuclear@3
|
277
|
nuclear@3
|
278 template<class CRef>
|
nuclear@3
|
279 inline void Add(const CRef& key)
|
nuclear@3
|
280 {
|
nuclear@3
|
281 UPInt hashValue = HashF()(key);
|
nuclear@3
|
282 add(key, hashValue);
|
nuclear@3
|
283 }
|
nuclear@3
|
284
|
nuclear@3
|
285 // Remove by alternative key.
|
nuclear@3
|
286 template<class K>
|
nuclear@3
|
287 void RemoveAlt(const K& key)
|
nuclear@3
|
288 {
|
nuclear@3
|
289 if (pTable == NULL)
|
nuclear@3
|
290 return;
|
nuclear@3
|
291
|
nuclear@3
|
292 UPInt hashValue = AltHashF()(key);
|
nuclear@3
|
293 SPInt index = hashValue & pTable->SizeMask;
|
nuclear@3
|
294
|
nuclear@3
|
295 Entry* e = &E(index);
|
nuclear@3
|
296
|
nuclear@3
|
297 // If empty node or occupied by collider, we have nothing to remove.
|
nuclear@3
|
298 if (e->IsEmpty() || (e->GetCachedHash(pTable->SizeMask) != (UPInt)index))
|
nuclear@3
|
299 return;
|
nuclear@3
|
300
|
nuclear@3
|
301 // Save index
|
nuclear@3
|
302 SPInt naturalIndex = index;
|
nuclear@3
|
303 SPInt prevIndex = -1;
|
nuclear@3
|
304
|
nuclear@3
|
305 while ((e->GetCachedHash(pTable->SizeMask) != (UPInt)naturalIndex) || !(e->Value == key))
|
nuclear@3
|
306 {
|
nuclear@3
|
307 // Keep looking through the chain.
|
nuclear@3
|
308 prevIndex = index;
|
nuclear@3
|
309 index = e->NextInChain;
|
nuclear@3
|
310 if (index == -1)
|
nuclear@3
|
311 return; // End of chain, item not found
|
nuclear@3
|
312 e = &E(index);
|
nuclear@3
|
313 }
|
nuclear@3
|
314
|
nuclear@3
|
315 // Found it - our item is at index
|
nuclear@3
|
316 if (naturalIndex == index)
|
nuclear@3
|
317 {
|
nuclear@3
|
318 // If we have a follower, move it to us
|
nuclear@3
|
319 if (!e->IsEndOfChain())
|
nuclear@3
|
320 {
|
nuclear@3
|
321 Entry* enext = &E(e->NextInChain);
|
nuclear@3
|
322 e->Clear();
|
nuclear@3
|
323 new (e) Entry(*enext);
|
nuclear@3
|
324 // Point us to the follower's cell that will be cleared
|
nuclear@3
|
325 e = enext;
|
nuclear@3
|
326 }
|
nuclear@3
|
327 }
|
nuclear@3
|
328 else
|
nuclear@3
|
329 {
|
nuclear@3
|
330 // We are not at natural index, so deal with the prev items next index
|
nuclear@3
|
331 E(prevIndex).NextInChain = e->NextInChain;
|
nuclear@3
|
332 }
|
nuclear@3
|
333
|
nuclear@3
|
334 // Clear us, of the follower cell that was moved.
|
nuclear@3
|
335 e->Clear();
|
nuclear@3
|
336 pTable->EntryCount --;
|
nuclear@3
|
337 // Should we check the size to condense hash? ...
|
nuclear@3
|
338 }
|
nuclear@3
|
339
|
nuclear@3
|
340 // Remove by main key.
|
nuclear@3
|
341 template<class CRef>
|
nuclear@3
|
342 void Remove(const CRef& key)
|
nuclear@3
|
343 {
|
nuclear@3
|
344 RemoveAlt(key);
|
nuclear@3
|
345 }
|
nuclear@3
|
346
|
nuclear@3
|
347 // Retrieve the pointer to a value under the given key.
|
nuclear@3
|
348 // - If there's no value under the key, then return NULL.
|
nuclear@3
|
349 // - If there is a value, return the pointer.
|
nuclear@3
|
350 template<class K>
|
nuclear@3
|
351 C* Get(const K& key)
|
nuclear@3
|
352 {
|
nuclear@3
|
353 SPInt index = findIndex(key);
|
nuclear@3
|
354 if (index >= 0)
|
nuclear@3
|
355 return &E(index).Value;
|
nuclear@3
|
356 return 0;
|
nuclear@3
|
357 }
|
nuclear@3
|
358
|
nuclear@3
|
359 template<class K>
|
nuclear@3
|
360 const C* Get(const K& key) const
|
nuclear@3
|
361 {
|
nuclear@3
|
362 SPInt index = findIndex(key);
|
nuclear@3
|
363 if (index >= 0)
|
nuclear@3
|
364 return &E(index).Value;
|
nuclear@3
|
365 return 0;
|
nuclear@3
|
366 }
|
nuclear@3
|
367
|
nuclear@3
|
368 // Alternative key versions of Get. Used by Hash.
|
nuclear@3
|
369 template<class K>
|
nuclear@3
|
370 const C* GetAlt(const K& key) const
|
nuclear@3
|
371 {
|
nuclear@3
|
372 SPInt index = findIndexAlt(key);
|
nuclear@3
|
373 if (index >= 0)
|
nuclear@3
|
374 return &E(index).Value;
|
nuclear@3
|
375 return 0;
|
nuclear@3
|
376 }
|
nuclear@3
|
377
|
nuclear@3
|
378 template<class K>
|
nuclear@3
|
379 C* GetAlt(const K& key)
|
nuclear@3
|
380 {
|
nuclear@3
|
381 SPInt index = findIndexAlt(key);
|
nuclear@3
|
382 if (index >= 0)
|
nuclear@3
|
383 return &E(index).Value;
|
nuclear@3
|
384 return 0;
|
nuclear@3
|
385 }
|
nuclear@3
|
386
|
nuclear@3
|
387 template<class K>
|
nuclear@3
|
388 bool GetAlt(const K& key, C* pval) const
|
nuclear@3
|
389 {
|
nuclear@3
|
390 SPInt index = findIndexAlt(key);
|
nuclear@3
|
391 if (index >= 0)
|
nuclear@3
|
392 {
|
nuclear@3
|
393 if (pval)
|
nuclear@3
|
394 *pval = E(index).Value;
|
nuclear@3
|
395 return true;
|
nuclear@3
|
396 }
|
nuclear@3
|
397 return false;
|
nuclear@3
|
398 }
|
nuclear@3
|
399
|
nuclear@3
|
400
|
nuclear@3
|
401 UPInt GetSize() const
|
nuclear@3
|
402 {
|
nuclear@3
|
403 return pTable == NULL ? 0 : (UPInt)pTable->EntryCount;
|
nuclear@3
|
404 }
|
nuclear@3
|
405
|
nuclear@3
|
406
|
nuclear@3
|
407 // Resize the HashSet table to fit one more Entry. Often this
|
nuclear@3
|
408 // doesn't involve any action.
|
nuclear@3
|
409 void CheckExpand()
|
nuclear@3
|
410 {
|
nuclear@3
|
411 if (pTable == NULL)
|
nuclear@3
|
412 {
|
nuclear@3
|
413 // Initial creation of table. Make a minimum-sized table.
|
nuclear@3
|
414 setRawCapacity(HashMinSize);
|
nuclear@3
|
415 }
|
nuclear@3
|
416 else if (pTable->EntryCount * 5 > (pTable->SizeMask + 1) * 4)
|
nuclear@3
|
417 {
|
nuclear@3
|
418 // pTable is more than 5/4 ths full. Expand.
|
nuclear@3
|
419 setRawCapacity((pTable->SizeMask + 1) * 2);
|
nuclear@3
|
420 }
|
nuclear@3
|
421 }
|
nuclear@3
|
422
|
nuclear@3
|
423 // Hint the bucket count to >= n.
|
nuclear@3
|
424 void Resize(UPInt n)
|
nuclear@3
|
425 {
|
nuclear@3
|
426 // Not really sure what this means in relation to
|
nuclear@3
|
427 // STLport's hash_map... they say they "increase the
|
nuclear@3
|
428 // bucket count to at least n" -- but does that mean
|
nuclear@3
|
429 // their real capacity after Resize(n) is more like
|
nuclear@3
|
430 // n*2 (since they do linked-list chaining within
|
nuclear@3
|
431 // buckets?).
|
nuclear@3
|
432 SetCapacity(n);
|
nuclear@3
|
433 }
|
nuclear@3
|
434
|
nuclear@3
|
435 // Size the HashSet so that it can comfortably contain the given
|
nuclear@3
|
436 // number of elements. If the HashSet already contains more
|
nuclear@3
|
437 // elements than newSize, then this may be a no-op.
|
nuclear@3
|
438 void SetCapacity(UPInt newSize)
|
nuclear@3
|
439 {
|
nuclear@3
|
440 UPInt newRawSize = (newSize * 5) / 4;
|
nuclear@3
|
441 if (newRawSize <= GetSize())
|
nuclear@3
|
442 return;
|
nuclear@3
|
443 setRawCapacity(newRawSize);
|
nuclear@3
|
444 }
|
nuclear@3
|
445
|
nuclear@3
|
446 // Disable inappropriate 'operator ->' warning on MSVC6.
|
nuclear@3
|
447 #ifdef OVR_CC_MSVC
|
nuclear@3
|
448 #if (OVR_CC_MSVC < 1300)
|
nuclear@3
|
449 # pragma warning(disable : 4284)
|
nuclear@3
|
450 #endif
|
nuclear@3
|
451 #endif
|
nuclear@3
|
452
|
nuclear@3
|
453 // Iterator API, like STL.
|
nuclear@3
|
454 struct ConstIterator
|
nuclear@3
|
455 {
|
nuclear@3
|
456 const C& operator * () const
|
nuclear@3
|
457 {
|
nuclear@3
|
458 OVR_ASSERT(Index >= 0 && Index <= (SPInt)pHash->pTable->SizeMask);
|
nuclear@3
|
459 return pHash->E(Index).Value;
|
nuclear@3
|
460 }
|
nuclear@3
|
461
|
nuclear@3
|
462 const C* operator -> () const
|
nuclear@3
|
463 {
|
nuclear@3
|
464 OVR_ASSERT(Index >= 0 && Index <= (SPInt)pHash->pTable->SizeMask);
|
nuclear@3
|
465 return &pHash->E(Index).Value;
|
nuclear@3
|
466 }
|
nuclear@3
|
467
|
nuclear@3
|
468 void operator ++ ()
|
nuclear@3
|
469 {
|
nuclear@3
|
470 // Find next non-empty Entry.
|
nuclear@3
|
471 if (Index <= (SPInt)pHash->pTable->SizeMask)
|
nuclear@3
|
472 {
|
nuclear@3
|
473 Index++;
|
nuclear@3
|
474 while ((UPInt)Index <= pHash->pTable->SizeMask &&
|
nuclear@3
|
475 pHash->E(Index).IsEmpty())
|
nuclear@3
|
476 {
|
nuclear@3
|
477 Index++;
|
nuclear@3
|
478 }
|
nuclear@3
|
479 }
|
nuclear@3
|
480 }
|
nuclear@3
|
481
|
nuclear@3
|
482 bool operator == (const ConstIterator& it) const
|
nuclear@3
|
483 {
|
nuclear@3
|
484 if (IsEnd() && it.IsEnd())
|
nuclear@3
|
485 {
|
nuclear@3
|
486 return true;
|
nuclear@3
|
487 }
|
nuclear@3
|
488 else
|
nuclear@3
|
489 {
|
nuclear@3
|
490 return (pHash == it.pHash) && (Index == it.Index);
|
nuclear@3
|
491 }
|
nuclear@3
|
492 }
|
nuclear@3
|
493
|
nuclear@3
|
494 bool operator != (const ConstIterator& it) const
|
nuclear@3
|
495 {
|
nuclear@3
|
496 return ! (*this == it);
|
nuclear@3
|
497 }
|
nuclear@3
|
498
|
nuclear@3
|
499
|
nuclear@3
|
500 bool IsEnd() const
|
nuclear@3
|
501 {
|
nuclear@3
|
502 return (pHash == NULL) ||
|
nuclear@3
|
503 (pHash->pTable == NULL) ||
|
nuclear@3
|
504 (Index > (SPInt)pHash->pTable->SizeMask);
|
nuclear@3
|
505 }
|
nuclear@3
|
506
|
nuclear@3
|
507 ConstIterator()
|
nuclear@3
|
508 : pHash(NULL), Index(0)
|
nuclear@3
|
509 { }
|
nuclear@3
|
510
|
nuclear@3
|
511 public:
|
nuclear@3
|
512 // Constructor was intentionally made public to allow create
|
nuclear@3
|
513 // iterator with arbitrary index.
|
nuclear@3
|
514 ConstIterator(const SelfType* h, SPInt index)
|
nuclear@3
|
515 : pHash(h), Index(index)
|
nuclear@3
|
516 { }
|
nuclear@3
|
517
|
nuclear@3
|
518 const SelfType* GetContainer() const
|
nuclear@3
|
519 {
|
nuclear@3
|
520 return pHash;
|
nuclear@3
|
521 }
|
nuclear@3
|
522 SPInt GetIndex() const
|
nuclear@3
|
523 {
|
nuclear@3
|
524 return Index;
|
nuclear@3
|
525 }
|
nuclear@3
|
526
|
nuclear@3
|
527 protected:
|
nuclear@3
|
528 friend class HashSetBase<C, HashF, AltHashF, Allocator, Entry>;
|
nuclear@3
|
529
|
nuclear@3
|
530 const SelfType* pHash;
|
nuclear@3
|
531 SPInt Index;
|
nuclear@3
|
532 };
|
nuclear@3
|
533
|
nuclear@3
|
534 friend struct ConstIterator;
|
nuclear@3
|
535
|
nuclear@3
|
536
|
nuclear@3
|
537 // Non-const Iterator; Get most of it from ConstIterator.
|
nuclear@3
|
538 struct Iterator : public ConstIterator
|
nuclear@3
|
539 {
|
nuclear@3
|
540 // Allow non-const access to entries.
|
nuclear@3
|
541 C& operator*() const
|
nuclear@3
|
542 {
|
nuclear@3
|
543 OVR_ASSERT(ConstIterator::Index >= 0 && ConstIterator::Index <= (SPInt)ConstIterator::pHash->pTable->SizeMask);
|
nuclear@3
|
544 return const_cast<SelfType*>(ConstIterator::pHash)->E(ConstIterator::Index).Value;
|
nuclear@3
|
545 }
|
nuclear@3
|
546
|
nuclear@3
|
547 C* operator->() const
|
nuclear@3
|
548 {
|
nuclear@3
|
549 return &(operator*());
|
nuclear@3
|
550 }
|
nuclear@3
|
551
|
nuclear@3
|
552 Iterator()
|
nuclear@3
|
553 : ConstIterator(NULL, 0)
|
nuclear@3
|
554 { }
|
nuclear@3
|
555
|
nuclear@3
|
556 // Removes current element from Hash
|
nuclear@3
|
557 void Remove()
|
nuclear@3
|
558 {
|
nuclear@3
|
559 RemoveAlt(operator*());
|
nuclear@3
|
560 }
|
nuclear@3
|
561
|
nuclear@3
|
562 template <class K>
|
nuclear@3
|
563 void RemoveAlt(const K& key)
|
nuclear@3
|
564 {
|
nuclear@3
|
565 SelfType* phash = const_cast<SelfType*>(ConstIterator::pHash);
|
nuclear@3
|
566 //Entry* ee = &phash->E(ConstIterator::Index);
|
nuclear@3
|
567 //const C& key = ee->Value;
|
nuclear@3
|
568
|
nuclear@3
|
569 UPInt hashValue = AltHashF()(key);
|
nuclear@3
|
570 SPInt index = hashValue & phash->pTable->SizeMask;
|
nuclear@3
|
571
|
nuclear@3
|
572 Entry* e = &phash->E(index);
|
nuclear@3
|
573
|
nuclear@3
|
574 // If empty node or occupied by collider, we have nothing to remove.
|
nuclear@3
|
575 if (e->IsEmpty() || (e->GetCachedHash(phash->pTable->SizeMask) != (UPInt)index))
|
nuclear@3
|
576 return;
|
nuclear@3
|
577
|
nuclear@3
|
578 // Save index
|
nuclear@3
|
579 SPInt naturalIndex = index;
|
nuclear@3
|
580 SPInt prevIndex = -1;
|
nuclear@3
|
581
|
nuclear@3
|
582 while ((e->GetCachedHash(phash->pTable->SizeMask) != (UPInt)naturalIndex) || !(e->Value == key))
|
nuclear@3
|
583 {
|
nuclear@3
|
584 // Keep looking through the chain.
|
nuclear@3
|
585 prevIndex = index;
|
nuclear@3
|
586 index = e->NextInChain;
|
nuclear@3
|
587 if (index == -1)
|
nuclear@3
|
588 return; // End of chain, item not found
|
nuclear@3
|
589 e = &phash->E(index);
|
nuclear@3
|
590 }
|
nuclear@3
|
591
|
nuclear@3
|
592 if (index == (SPInt)ConstIterator::Index)
|
nuclear@3
|
593 {
|
nuclear@3
|
594 // Found it - our item is at index
|
nuclear@3
|
595 if (naturalIndex == index)
|
nuclear@3
|
596 {
|
nuclear@3
|
597 // If we have a follower, move it to us
|
nuclear@3
|
598 if (!e->IsEndOfChain())
|
nuclear@3
|
599 {
|
nuclear@3
|
600 Entry* enext = &phash->E(e->NextInChain);
|
nuclear@3
|
601 e->Clear();
|
nuclear@3
|
602 new (e) Entry(*enext);
|
nuclear@3
|
603 // Point us to the follower's cell that will be cleared
|
nuclear@3
|
604 e = enext;
|
nuclear@3
|
605 --ConstIterator::Index;
|
nuclear@3
|
606 }
|
nuclear@3
|
607 }
|
nuclear@3
|
608 else
|
nuclear@3
|
609 {
|
nuclear@3
|
610 // We are not at natural index, so deal with the prev items next index
|
nuclear@3
|
611 phash->E(prevIndex).NextInChain = e->NextInChain;
|
nuclear@3
|
612 }
|
nuclear@3
|
613
|
nuclear@3
|
614 // Clear us, of the follower cell that was moved.
|
nuclear@3
|
615 e->Clear();
|
nuclear@3
|
616 phash->pTable->EntryCount --;
|
nuclear@3
|
617 }
|
nuclear@3
|
618 else
|
nuclear@3
|
619 OVR_ASSERT(0); //?
|
nuclear@3
|
620 }
|
nuclear@3
|
621
|
nuclear@3
|
622 private:
|
nuclear@3
|
623 friend class HashSetBase<C, HashF, AltHashF, Allocator, Entry>;
|
nuclear@3
|
624
|
nuclear@3
|
625 Iterator(SelfType* h, SPInt i0)
|
nuclear@3
|
626 : ConstIterator(h, i0)
|
nuclear@3
|
627 { }
|
nuclear@3
|
628 };
|
nuclear@3
|
629
|
nuclear@3
|
630 friend struct Iterator;
|
nuclear@3
|
631
|
nuclear@3
|
632 Iterator Begin()
|
nuclear@3
|
633 {
|
nuclear@3
|
634 if (pTable == 0)
|
nuclear@3
|
635 return Iterator(NULL, 0);
|
nuclear@3
|
636
|
nuclear@3
|
637 // Scan till we hit the First valid Entry.
|
nuclear@3
|
638 UPInt i0 = 0;
|
nuclear@3
|
639 while (i0 <= pTable->SizeMask && E(i0).IsEmpty())
|
nuclear@3
|
640 {
|
nuclear@3
|
641 i0++;
|
nuclear@3
|
642 }
|
nuclear@3
|
643 return Iterator(this, i0);
|
nuclear@3
|
644 }
|
nuclear@3
|
645 Iterator End() { return Iterator(NULL, 0); }
|
nuclear@3
|
646
|
nuclear@3
|
647 ConstIterator Begin() const { return const_cast<SelfType*>(this)->Begin(); }
|
nuclear@3
|
648 ConstIterator End() const { return const_cast<SelfType*>(this)->End(); }
|
nuclear@3
|
649
|
nuclear@3
|
650 template<class K>
|
nuclear@3
|
651 Iterator Find(const K& key)
|
nuclear@3
|
652 {
|
nuclear@3
|
653 SPInt index = findIndex(key);
|
nuclear@3
|
654 if (index >= 0)
|
nuclear@3
|
655 return Iterator(this, index);
|
nuclear@3
|
656 return Iterator(NULL, 0);
|
nuclear@3
|
657 }
|
nuclear@3
|
658
|
nuclear@3
|
659 template<class K>
|
nuclear@3
|
660 Iterator FindAlt(const K& key)
|
nuclear@3
|
661 {
|
nuclear@3
|
662 SPInt index = findIndexAlt(key);
|
nuclear@3
|
663 if (index >= 0)
|
nuclear@3
|
664 return Iterator(this, index);
|
nuclear@3
|
665 return Iterator(NULL, 0);
|
nuclear@3
|
666 }
|
nuclear@3
|
667
|
nuclear@3
|
668 template<class K>
|
nuclear@3
|
669 ConstIterator Find(const K& key) const { return const_cast<SelfType*>(this)->Find(key); }
|
nuclear@3
|
670
|
nuclear@3
|
671 template<class K>
|
nuclear@3
|
672 ConstIterator FindAlt(const K& key) const { return const_cast<SelfType*>(this)->FindAlt(key); }
|
nuclear@3
|
673
|
nuclear@3
|
674 private:
|
nuclear@3
|
675 // Find the index of the matching Entry. If no match, then return -1.
|
nuclear@3
|
676 template<class K>
|
nuclear@3
|
677 SPInt findIndex(const K& key) const
|
nuclear@3
|
678 {
|
nuclear@3
|
679 if (pTable == NULL)
|
nuclear@3
|
680 return -1;
|
nuclear@3
|
681 UPInt hashValue = HashF()(key) & pTable->SizeMask;
|
nuclear@3
|
682 return findIndexCore(key, hashValue);
|
nuclear@3
|
683 }
|
nuclear@3
|
684
|
nuclear@3
|
685 template<class K>
|
nuclear@3
|
686 SPInt findIndexAlt(const K& key) const
|
nuclear@3
|
687 {
|
nuclear@3
|
688 if (pTable == NULL)
|
nuclear@3
|
689 return -1;
|
nuclear@3
|
690 UPInt hashValue = AltHashF()(key) & pTable->SizeMask;
|
nuclear@3
|
691 return findIndexCore(key, hashValue);
|
nuclear@3
|
692 }
|
nuclear@3
|
693
|
nuclear@3
|
694 // Find the index of the matching Entry. If no match, then return -1.
|
nuclear@3
|
695 template<class K>
|
nuclear@3
|
696 SPInt findIndexCore(const K& key, UPInt hashValue) const
|
nuclear@3
|
697 {
|
nuclear@3
|
698 // Table must exist.
|
nuclear@3
|
699 OVR_ASSERT(pTable != 0);
|
nuclear@3
|
700 // Hash key must be 'and-ed' by the caller.
|
nuclear@3
|
701 OVR_ASSERT((hashValue & ~pTable->SizeMask) == 0);
|
nuclear@3
|
702
|
nuclear@3
|
703 UPInt index = hashValue;
|
nuclear@3
|
704 const Entry* e = &E(index);
|
nuclear@3
|
705
|
nuclear@3
|
706 // If empty or occupied by a collider, not found.
|
nuclear@3
|
707 if (e->IsEmpty() || (e->GetCachedHash(pTable->SizeMask) != index))
|
nuclear@3
|
708 return -1;
|
nuclear@3
|
709
|
nuclear@3
|
710 while(1)
|
nuclear@3
|
711 {
|
nuclear@3
|
712 OVR_ASSERT(e->GetCachedHash(pTable->SizeMask) == hashValue);
|
nuclear@3
|
713
|
nuclear@3
|
714 if (e->GetCachedHash(pTable->SizeMask) == hashValue && e->Value == key)
|
nuclear@3
|
715 {
|
nuclear@3
|
716 // Found it.
|
nuclear@3
|
717 return index;
|
nuclear@3
|
718 }
|
nuclear@3
|
719 // Values can not be equal at this point.
|
nuclear@3
|
720 // That would mean that the hash key for the same value differs.
|
nuclear@3
|
721 OVR_ASSERT(!(e->Value == key));
|
nuclear@3
|
722
|
nuclear@3
|
723 // Keep looking through the chain.
|
nuclear@3
|
724 index = e->NextInChain;
|
nuclear@3
|
725 if (index == (UPInt)-1)
|
nuclear@3
|
726 break; // end of chain
|
nuclear@3
|
727
|
nuclear@3
|
728 e = &E(index);
|
nuclear@3
|
729 OVR_ASSERT(!e->IsEmpty());
|
nuclear@3
|
730 }
|
nuclear@3
|
731 return -1;
|
nuclear@3
|
732 }
|
nuclear@3
|
733
|
nuclear@3
|
734
|
nuclear@3
|
735 // Add a new value to the HashSet table, under the specified key.
|
nuclear@3
|
736 template<class CRef>
|
nuclear@3
|
737 void add(const CRef& key, UPInt hashValue)
|
nuclear@3
|
738 {
|
nuclear@3
|
739 CheckExpand();
|
nuclear@3
|
740 hashValue &= pTable->SizeMask;
|
nuclear@3
|
741
|
nuclear@3
|
742 pTable->EntryCount++;
|
nuclear@3
|
743
|
nuclear@3
|
744 SPInt index = hashValue;
|
nuclear@3
|
745 Entry* naturalEntry = &(E(index));
|
nuclear@3
|
746
|
nuclear@3
|
747 if (naturalEntry->IsEmpty())
|
nuclear@3
|
748 {
|
nuclear@3
|
749 // Put the new Entry in.
|
nuclear@3
|
750 new (naturalEntry) Entry(key, -1);
|
nuclear@3
|
751 }
|
nuclear@3
|
752 else
|
nuclear@3
|
753 {
|
nuclear@3
|
754 // Find a blank spot.
|
nuclear@3
|
755 SPInt blankIndex = index;
|
nuclear@3
|
756 do {
|
nuclear@3
|
757 blankIndex = (blankIndex + 1) & pTable->SizeMask;
|
nuclear@3
|
758 } while(!E(blankIndex).IsEmpty());
|
nuclear@3
|
759
|
nuclear@3
|
760 Entry* blankEntry = &E(blankIndex);
|
nuclear@3
|
761
|
nuclear@3
|
762 if (naturalEntry->GetCachedHash(pTable->SizeMask) == (UPInt)index)
|
nuclear@3
|
763 {
|
nuclear@3
|
764 // Collision. Link into this chain.
|
nuclear@3
|
765
|
nuclear@3
|
766 // Move existing list head.
|
nuclear@3
|
767 new (blankEntry) Entry(*naturalEntry); // placement new, copy ctor
|
nuclear@3
|
768
|
nuclear@3
|
769 // Put the new info in the natural Entry.
|
nuclear@3
|
770 naturalEntry->Value = key;
|
nuclear@3
|
771 naturalEntry->NextInChain = blankIndex;
|
nuclear@3
|
772 }
|
nuclear@3
|
773 else
|
nuclear@3
|
774 {
|
nuclear@3
|
775 // Existing Entry does not naturally
|
nuclear@3
|
776 // belong in this slot. Existing
|
nuclear@3
|
777 // Entry must be moved.
|
nuclear@3
|
778
|
nuclear@3
|
779 // Find natural location of collided element (i.e. root of chain)
|
nuclear@3
|
780 SPInt collidedIndex = naturalEntry->GetCachedHash(pTable->SizeMask);
|
nuclear@3
|
781 OVR_ASSERT(collidedIndex >= 0 && collidedIndex <= (SPInt)pTable->SizeMask);
|
nuclear@3
|
782 for (;;)
|
nuclear@3
|
783 {
|
nuclear@3
|
784 Entry* e = &E(collidedIndex);
|
nuclear@3
|
785 if (e->NextInChain == index)
|
nuclear@3
|
786 {
|
nuclear@3
|
787 // Here's where we need to splice.
|
nuclear@3
|
788 new (blankEntry) Entry(*naturalEntry);
|
nuclear@3
|
789 e->NextInChain = blankIndex;
|
nuclear@3
|
790 break;
|
nuclear@3
|
791 }
|
nuclear@3
|
792 collidedIndex = e->NextInChain;
|
nuclear@3
|
793 OVR_ASSERT(collidedIndex >= 0 && collidedIndex <= (SPInt)pTable->SizeMask);
|
nuclear@3
|
794 }
|
nuclear@3
|
795
|
nuclear@3
|
796 // Put the new data in the natural Entry.
|
nuclear@3
|
797 naturalEntry->Value = key;
|
nuclear@3
|
798 naturalEntry->NextInChain = -1;
|
nuclear@3
|
799 }
|
nuclear@3
|
800 }
|
nuclear@3
|
801
|
nuclear@3
|
802 // Record hash value: has effect only if cached node is used.
|
nuclear@3
|
803 naturalEntry->SetCachedHash(hashValue);
|
nuclear@3
|
804 }
|
nuclear@3
|
805
|
nuclear@3
|
806 // Index access helpers.
|
nuclear@3
|
807 Entry& E(UPInt index)
|
nuclear@3
|
808 {
|
nuclear@3
|
809 // Must have pTable and access needs to be within bounds.
|
nuclear@3
|
810 OVR_ASSERT(index <= pTable->SizeMask);
|
nuclear@3
|
811 return *(((Entry*) (pTable + 1)) + index);
|
nuclear@3
|
812 }
|
nuclear@3
|
813 const Entry& E(UPInt index) const
|
nuclear@3
|
814 {
|
nuclear@3
|
815 OVR_ASSERT(index <= pTable->SizeMask);
|
nuclear@3
|
816 return *(((Entry*) (pTable + 1)) + index);
|
nuclear@3
|
817 }
|
nuclear@3
|
818
|
nuclear@3
|
819
|
nuclear@3
|
820 // Resize the HashSet table to the given size (Rehash the
|
nuclear@3
|
821 // contents of the current table). The arg is the number of
|
nuclear@3
|
822 // HashSet table entries, not the number of elements we should
|
nuclear@3
|
823 // actually contain (which will be less than this).
|
nuclear@3
|
824 void setRawCapacity(UPInt newSize)
|
nuclear@3
|
825 {
|
nuclear@3
|
826 if (newSize == 0)
|
nuclear@3
|
827 {
|
nuclear@3
|
828 // Special case.
|
nuclear@3
|
829 Clear();
|
nuclear@3
|
830 return;
|
nuclear@3
|
831 }
|
nuclear@3
|
832
|
nuclear@3
|
833 // Minimum size; don't incur rehashing cost when expanding
|
nuclear@3
|
834 // very small tables. Not that we perform this check before
|
nuclear@3
|
835 // 'log2f' call to avoid fp exception with newSize == 1.
|
nuclear@3
|
836 if (newSize < HashMinSize)
|
nuclear@3
|
837 newSize = HashMinSize;
|
nuclear@3
|
838 else
|
nuclear@3
|
839 {
|
nuclear@3
|
840 // Force newSize to be a power of two.
|
nuclear@3
|
841 int bits = Alg::UpperBit(newSize-1) + 1; // Chop( Log2f((float)(newSize-1)) + 1);
|
nuclear@3
|
842 OVR_ASSERT((UPInt(1) << bits) >= newSize);
|
nuclear@3
|
843 newSize = UPInt(1) << bits;
|
nuclear@3
|
844 }
|
nuclear@3
|
845
|
nuclear@3
|
846 SelfType newHash;
|
nuclear@3
|
847 newHash.pTable = (TableType*)
|
nuclear@3
|
848 Allocator::Alloc(
|
nuclear@3
|
849 sizeof(TableType) + sizeof(Entry) * newSize);
|
nuclear@3
|
850 // Need to do something on alloc failure!
|
nuclear@3
|
851 OVR_ASSERT(newHash.pTable);
|
nuclear@3
|
852
|
nuclear@3
|
853 newHash.pTable->EntryCount = 0;
|
nuclear@3
|
854 newHash.pTable->SizeMask = newSize - 1;
|
nuclear@3
|
855 UPInt i, n;
|
nuclear@3
|
856
|
nuclear@3
|
857 // Mark all entries as empty.
|
nuclear@3
|
858 for (i = 0; i < newSize; i++)
|
nuclear@3
|
859 newHash.E(i).NextInChain = -2;
|
nuclear@3
|
860
|
nuclear@3
|
861 // Copy stuff to newHash
|
nuclear@3
|
862 if (pTable)
|
nuclear@3
|
863 {
|
nuclear@3
|
864 for (i = 0, n = pTable->SizeMask; i <= n; i++)
|
nuclear@3
|
865 {
|
nuclear@3
|
866 Entry* e = &E(i);
|
nuclear@3
|
867 if (e->IsEmpty() == false)
|
nuclear@3
|
868 {
|
nuclear@3
|
869 // Insert old Entry into new HashSet.
|
nuclear@3
|
870 newHash.Add(e->Value);
|
nuclear@3
|
871 // placement delete of old element
|
nuclear@3
|
872 e->Clear();
|
nuclear@3
|
873 }
|
nuclear@3
|
874 }
|
nuclear@3
|
875
|
nuclear@3
|
876 // Delete our old data buffer.
|
nuclear@3
|
877 Allocator::Free(pTable);
|
nuclear@3
|
878 }
|
nuclear@3
|
879
|
nuclear@3
|
880 // Steal newHash's data.
|
nuclear@3
|
881 pTable = newHash.pTable;
|
nuclear@3
|
882 newHash.pTable = NULL;
|
nuclear@3
|
883 }
|
nuclear@3
|
884
|
nuclear@3
|
885 struct TableType
|
nuclear@3
|
886 {
|
nuclear@3
|
887 UPInt EntryCount;
|
nuclear@3
|
888 UPInt SizeMask;
|
nuclear@3
|
889 // Entry array follows this structure
|
nuclear@3
|
890 // in memory.
|
nuclear@3
|
891 };
|
nuclear@3
|
892 TableType* pTable;
|
nuclear@3
|
893 };
|
nuclear@3
|
894
|
nuclear@3
|
895
|
nuclear@3
|
896
|
nuclear@3
|
897 //-----------------------------------------------------------------------------------
|
nuclear@3
|
898 template<class C, class HashF = FixedSizeHash<C>,
|
nuclear@3
|
899 class AltHashF = HashF,
|
nuclear@3
|
900 class Allocator = ContainerAllocator<C>,
|
nuclear@3
|
901 class Entry = HashsetCachedEntry<C, HashF> >
|
nuclear@3
|
902 class HashSet : public HashSetBase<C, HashF, AltHashF, Allocator, Entry>
|
nuclear@3
|
903 {
|
nuclear@3
|
904 public:
|
nuclear@3
|
905 typedef HashSetBase<C, HashF, AltHashF, Allocator, Entry> BaseType;
|
nuclear@3
|
906 typedef HashSet<C, HashF, AltHashF, Allocator, Entry> SelfType;
|
nuclear@3
|
907
|
nuclear@3
|
908 HashSet() { }
|
nuclear@3
|
909 HashSet(int sizeHint) : BaseType(sizeHint) { }
|
nuclear@3
|
910 HashSet(const SelfType& src) : BaseType(src) { }
|
nuclear@3
|
911 ~HashSet() { }
|
nuclear@3
|
912
|
nuclear@3
|
913 void operator = (const SelfType& src) { BaseType::Assign(src); }
|
nuclear@3
|
914
|
nuclear@3
|
915 // Set a new or existing value under the key, to the value.
|
nuclear@3
|
916 // Pass a different class of 'key' so that assignment reference object
|
nuclear@3
|
917 // can be passed instead of the actual object.
|
nuclear@3
|
918 template<class CRef>
|
nuclear@3
|
919 void Set(const CRef& key)
|
nuclear@3
|
920 {
|
nuclear@3
|
921 BaseType::Set(key);
|
nuclear@3
|
922 }
|
nuclear@3
|
923
|
nuclear@3
|
924 template<class CRef>
|
nuclear@3
|
925 inline void Add(const CRef& key)
|
nuclear@3
|
926 {
|
nuclear@3
|
927 BaseType::Add(key);
|
nuclear@3
|
928 }
|
nuclear@3
|
929
|
nuclear@3
|
930 // Hint the bucket count to >= n.
|
nuclear@3
|
931 void Resize(UPInt n)
|
nuclear@3
|
932 {
|
nuclear@3
|
933 BaseType::SetCapacity(n);
|
nuclear@3
|
934 }
|
nuclear@3
|
935
|
nuclear@3
|
936 // Size the HashSet so that it can comfortably contain the given
|
nuclear@3
|
937 // number of elements. If the HashSet already contains more
|
nuclear@3
|
938 // elements than newSize, then this may be a no-op.
|
nuclear@3
|
939 void SetCapacity(UPInt newSize)
|
nuclear@3
|
940 {
|
nuclear@3
|
941 BaseType::SetCapacity(newSize);
|
nuclear@3
|
942 }
|
nuclear@3
|
943
|
nuclear@3
|
944 };
|
nuclear@3
|
945
|
nuclear@3
|
946 // HashSet with uncached hash code; declared for convenience.
|
nuclear@3
|
947 template<class C, class HashF = FixedSizeHash<C>,
|
nuclear@3
|
948 class AltHashF = HashF,
|
nuclear@3
|
949 class Allocator = ContainerAllocator<C> >
|
nuclear@3
|
950 class HashSetUncached : public HashSet<C, HashF, AltHashF, Allocator, HashsetEntry<C, HashF> >
|
nuclear@3
|
951 {
|
nuclear@3
|
952 public:
|
nuclear@3
|
953
|
nuclear@3
|
954 typedef HashSetUncached<C, HashF, AltHashF, Allocator> SelfType;
|
nuclear@3
|
955 typedef HashSet<C, HashF, AltHashF, Allocator, HashsetEntry<C, HashF> > BaseType;
|
nuclear@3
|
956
|
nuclear@3
|
957 // Delegated constructors.
|
nuclear@3
|
958 HashSetUncached() { }
|
nuclear@3
|
959 HashSetUncached(int sizeHint) : BaseType(sizeHint) { }
|
nuclear@3
|
960 HashSetUncached(const SelfType& src) : BaseType(src) { }
|
nuclear@3
|
961 ~HashSetUncached() { }
|
nuclear@3
|
962
|
nuclear@3
|
963 void operator = (const SelfType& src)
|
nuclear@3
|
964 {
|
nuclear@3
|
965 BaseType::operator = (src);
|
nuclear@3
|
966 }
|
nuclear@3
|
967 };
|
nuclear@3
|
968
|
nuclear@3
|
969
|
nuclear@3
|
970 //-----------------------------------------------------------------------------------
|
nuclear@3
|
971 // ***** Hash hash table implementation
|
nuclear@3
|
972
|
nuclear@3
|
973 // Node for Hash - necessary so that Hash can delegate its implementation
|
nuclear@3
|
974 // to HashSet.
|
nuclear@3
|
975 template<class C, class U, class HashF>
|
nuclear@3
|
976 struct HashNode
|
nuclear@3
|
977 {
|
nuclear@3
|
978 typedef HashNode<C, U, HashF> SelfType;
|
nuclear@3
|
979 typedef C FirstType;
|
nuclear@3
|
980 typedef U SecondType;
|
nuclear@3
|
981
|
nuclear@3
|
982 C First;
|
nuclear@3
|
983 U Second;
|
nuclear@3
|
984
|
nuclear@3
|
985 // NodeRef is used to allow passing of elements into HashSet
|
nuclear@3
|
986 // without using a temporary object.
|
nuclear@3
|
987 struct NodeRef
|
nuclear@3
|
988 {
|
nuclear@3
|
989 const C* pFirst;
|
nuclear@3
|
990 const U* pSecond;
|
nuclear@3
|
991
|
nuclear@3
|
992 NodeRef(const C& f, const U& s) : pFirst(&f), pSecond(&s) { }
|
nuclear@3
|
993 NodeRef(const NodeRef& src) : pFirst(src.pFirst), pSecond(src.pSecond) { }
|
nuclear@3
|
994
|
nuclear@3
|
995 // Enable computation of ghash_node_hashf.
|
nuclear@3
|
996 inline UPInt GetHash() const { return HashF()(*pFirst); }
|
nuclear@3
|
997 // Necessary conversion to allow HashNode::operator == to work.
|
nuclear@3
|
998 operator const C& () const { return *pFirst; }
|
nuclear@3
|
999 };
|
nuclear@3
|
1000
|
nuclear@3
|
1001 // Note: No default constructor is necessary.
|
nuclear@3
|
1002 HashNode(const HashNode& src) : First(src.First), Second(src.Second) { }
|
nuclear@3
|
1003 HashNode(const NodeRef& src) : First(*src.pFirst), Second(*src.pSecond) { }
|
nuclear@3
|
1004 void operator = (const NodeRef& src) { First = *src.pFirst; Second = *src.pSecond; }
|
nuclear@3
|
1005
|
nuclear@3
|
1006 template<class K>
|
nuclear@3
|
1007 bool operator == (const K& src) const { return (First == src); }
|
nuclear@3
|
1008
|
nuclear@3
|
1009 template<class K>
|
nuclear@3
|
1010 static UPInt CalcHash(const K& data) { return HashF()(data); }
|
nuclear@3
|
1011 inline UPInt GetHash() const { return HashF()(First); }
|
nuclear@3
|
1012
|
nuclear@3
|
1013 // Hash functors used with this node. A separate functor is used for alternative
|
nuclear@3
|
1014 // key lookup so that it does not need to access the '.First' element.
|
nuclear@3
|
1015 struct NodeHashF
|
nuclear@3
|
1016 {
|
nuclear@3
|
1017 template<class K>
|
nuclear@3
|
1018 UPInt operator()(const K& data) const { return data.GetHash(); }
|
nuclear@3
|
1019 };
|
nuclear@3
|
1020 struct NodeAltHashF
|
nuclear@3
|
1021 {
|
nuclear@3
|
1022 template<class K>
|
nuclear@3
|
1023 UPInt operator()(const K& data) const { return HashNode<C,U,HashF>::CalcHash(data); }
|
nuclear@3
|
1024 };
|
nuclear@3
|
1025 };
|
nuclear@3
|
1026
|
nuclear@3
|
1027
|
nuclear@3
|
1028
|
nuclear@3
|
1029 // **** Extra hashset_entry types to allow NodeRef construction.
|
nuclear@3
|
1030
|
nuclear@3
|
1031 // The big difference between the below types and the ones used in hash_set is that
|
nuclear@3
|
1032 // these allow initializing the node with 'typename C::NodeRef& keyRef', which
|
nuclear@3
|
1033 // is critical to avoid temporary node allocation on stack when using placement new.
|
nuclear@3
|
1034
|
nuclear@3
|
1035 // Compact hash table Entry type that re-computes hash keys during hash traversal.
|
nuclear@3
|
1036 // Good to use if the hash function is cheap or the hash value is already cached in C.
|
nuclear@3
|
1037 template<class C, class HashF>
|
nuclear@3
|
1038 class HashsetNodeEntry
|
nuclear@3
|
1039 {
|
nuclear@3
|
1040 public:
|
nuclear@3
|
1041 // Internal chaining for collisions.
|
nuclear@3
|
1042 SPInt NextInChain;
|
nuclear@3
|
1043 C Value;
|
nuclear@3
|
1044
|
nuclear@3
|
1045 HashsetNodeEntry()
|
nuclear@3
|
1046 : NextInChain(-2) { }
|
nuclear@3
|
1047 HashsetNodeEntry(const HashsetNodeEntry& e)
|
nuclear@3
|
1048 : NextInChain(e.NextInChain), Value(e.Value) { }
|
nuclear@3
|
1049 HashsetNodeEntry(const C& key, SPInt next)
|
nuclear@3
|
1050 : NextInChain(next), Value(key) { }
|
nuclear@3
|
1051 HashsetNodeEntry(const typename C::NodeRef& keyRef, SPInt next)
|
nuclear@3
|
1052 : NextInChain(next), Value(keyRef) { }
|
nuclear@3
|
1053
|
nuclear@3
|
1054 bool IsEmpty() const { return NextInChain == -2; }
|
nuclear@3
|
1055 bool IsEndOfChain() const { return NextInChain == -1; }
|
nuclear@3
|
1056 UPInt GetCachedHash(UPInt maskValue) const { return HashF()(Value) & maskValue; }
|
nuclear@3
|
1057 void SetCachedHash(UPInt hashValue) { OVR_UNUSED(hashValue); }
|
nuclear@3
|
1058
|
nuclear@3
|
1059 void Clear()
|
nuclear@3
|
1060 {
|
nuclear@3
|
1061 Value.~C(); // placement delete
|
nuclear@3
|
1062 NextInChain = -2;
|
nuclear@3
|
1063 }
|
nuclear@3
|
1064 // Free is only used from dtor of hash; Clear is used during regular operations:
|
nuclear@3
|
1065 // assignment, hash reallocations, value reassignments, so on.
|
nuclear@3
|
1066 void Free() { Clear(); }
|
nuclear@3
|
1067 };
|
nuclear@3
|
1068
|
nuclear@3
|
1069 // Hash table Entry type that caches the Entry hash value for nodes, so that it
|
nuclear@3
|
1070 // does not need to be re-computed during access.
|
nuclear@3
|
1071 template<class C, class HashF>
|
nuclear@3
|
1072 class HashsetCachedNodeEntry
|
nuclear@3
|
1073 {
|
nuclear@3
|
1074 public:
|
nuclear@3
|
1075 // Internal chaining for collisions.
|
nuclear@3
|
1076 SPInt NextInChain;
|
nuclear@3
|
1077 UPInt HashValue;
|
nuclear@3
|
1078 C Value;
|
nuclear@3
|
1079
|
nuclear@3
|
1080 HashsetCachedNodeEntry()
|
nuclear@3
|
1081 : NextInChain(-2) { }
|
nuclear@3
|
1082 HashsetCachedNodeEntry(const HashsetCachedNodeEntry& e)
|
nuclear@3
|
1083 : NextInChain(e.NextInChain), HashValue(e.HashValue), Value(e.Value) { }
|
nuclear@3
|
1084 HashsetCachedNodeEntry(const C& key, SPInt next)
|
nuclear@3
|
1085 : NextInChain(next), Value(key) { }
|
nuclear@3
|
1086 HashsetCachedNodeEntry(const typename C::NodeRef& keyRef, SPInt next)
|
nuclear@3
|
1087 : NextInChain(next), Value(keyRef) { }
|
nuclear@3
|
1088
|
nuclear@3
|
1089 bool IsEmpty() const { return NextInChain == -2; }
|
nuclear@3
|
1090 bool IsEndOfChain() const { return NextInChain == -1; }
|
nuclear@3
|
1091 UPInt GetCachedHash(UPInt maskValue) const { OVR_UNUSED(maskValue); return HashValue; }
|
nuclear@3
|
1092 void SetCachedHash(UPInt hashValue) { HashValue = hashValue; }
|
nuclear@3
|
1093
|
nuclear@3
|
1094 void Clear()
|
nuclear@3
|
1095 {
|
nuclear@3
|
1096 Value.~C();
|
nuclear@3
|
1097 NextInChain = -2;
|
nuclear@3
|
1098 }
|
nuclear@3
|
1099 // Free is only used from dtor of hash; Clear is used during regular operations:
|
nuclear@3
|
1100 // assignment, hash reallocations, value reassignments, so on.
|
nuclear@3
|
1101 void Free() { Clear(); }
|
nuclear@3
|
1102 };
|
nuclear@3
|
1103
|
nuclear@3
|
1104
|
nuclear@3
|
1105 //-----------------------------------------------------------------------------------
|
nuclear@3
|
1106 template<class C, class U,
|
nuclear@3
|
1107 class HashF = FixedSizeHash<C>,
|
nuclear@3
|
1108 class Allocator = ContainerAllocator<C>,
|
nuclear@3
|
1109 class HashNode = OVR::HashNode<C,U,HashF>,
|
nuclear@3
|
1110 class Entry = HashsetCachedNodeEntry<HashNode, typename HashNode::NodeHashF>,
|
nuclear@3
|
1111 class Container = HashSet<HashNode, typename HashNode::NodeHashF,
|
nuclear@3
|
1112 typename HashNode::NodeAltHashF, Allocator,
|
nuclear@3
|
1113 Entry> >
|
nuclear@3
|
1114 class Hash
|
nuclear@3
|
1115 {
|
nuclear@3
|
1116 public:
|
nuclear@3
|
1117 OVR_MEMORY_REDEFINE_NEW(Hash)
|
nuclear@3
|
1118
|
nuclear@3
|
1119 // Types used for hash_set.
|
nuclear@3
|
1120 typedef U ValueType;
|
nuclear@3
|
1121 typedef Hash<C, U, HashF, Allocator, HashNode, Entry, Container> SelfType;
|
nuclear@3
|
1122
|
nuclear@3
|
1123 // Actual hash table itself, implemented as hash_set.
|
nuclear@3
|
1124 Container mHash;
|
nuclear@3
|
1125
|
nuclear@3
|
1126 public:
|
nuclear@3
|
1127 Hash() { }
|
nuclear@3
|
1128 Hash(int sizeHint) : mHash(sizeHint) { }
|
nuclear@3
|
1129 Hash(const SelfType& src) : mHash(src.mHash) { }
|
nuclear@3
|
1130 ~Hash() { }
|
nuclear@3
|
1131
|
nuclear@3
|
1132 void operator = (const SelfType& src) { mHash = src.mHash; }
|
nuclear@3
|
1133
|
nuclear@3
|
1134 // Remove all entries from the Hash table.
|
nuclear@3
|
1135 inline void Clear() { mHash.Clear(); }
|
nuclear@3
|
1136 // Returns true if the Hash is empty.
|
nuclear@3
|
1137 inline bool IsEmpty() const { return mHash.IsEmpty(); }
|
nuclear@3
|
1138
|
nuclear@3
|
1139 // Access (set).
|
nuclear@3
|
1140 inline void Set(const C& key, const U& value)
|
nuclear@3
|
1141 {
|
nuclear@3
|
1142 typename HashNode::NodeRef e(key, value);
|
nuclear@3
|
1143 mHash.Set(e);
|
nuclear@3
|
1144 }
|
nuclear@3
|
1145 inline void Add(const C& key, const U& value)
|
nuclear@3
|
1146 {
|
nuclear@3
|
1147 typename HashNode::NodeRef e(key, value);
|
nuclear@3
|
1148 mHash.Add(e);
|
nuclear@3
|
1149 }
|
nuclear@3
|
1150
|
nuclear@3
|
1151 // Removes an element by clearing its Entry.
|
nuclear@3
|
1152 inline void Remove(const C& key)
|
nuclear@3
|
1153 {
|
nuclear@3
|
1154 mHash.RemoveAlt(key);
|
nuclear@3
|
1155 }
|
nuclear@3
|
1156 template<class K>
|
nuclear@3
|
1157 inline void RemoveAlt(const K& key)
|
nuclear@3
|
1158 {
|
nuclear@3
|
1159 mHash.RemoveAlt(key);
|
nuclear@3
|
1160 }
|
nuclear@3
|
1161
|
nuclear@3
|
1162 // Retrieve the value under the given key.
|
nuclear@3
|
1163 // - If there's no value under the key, then return false and leave *pvalue alone.
|
nuclear@3
|
1164 // - If there is a value, return true, and Set *Pvalue to the Entry's value.
|
nuclear@3
|
1165 // - If value == NULL, return true or false according to the presence of the key.
|
nuclear@3
|
1166 bool Get(const C& key, U* pvalue) const
|
nuclear@3
|
1167 {
|
nuclear@3
|
1168 const HashNode* p = mHash.GetAlt(key);
|
nuclear@3
|
1169 if (p)
|
nuclear@3
|
1170 {
|
nuclear@3
|
1171 if (pvalue)
|
nuclear@3
|
1172 *pvalue = p->Second;
|
nuclear@3
|
1173 return true;
|
nuclear@3
|
1174 }
|
nuclear@3
|
1175 return false;
|
nuclear@3
|
1176 }
|
nuclear@3
|
1177
|
nuclear@3
|
1178 template<class K>
|
nuclear@3
|
1179 bool GetAlt(const K& key, U* pvalue) const
|
nuclear@3
|
1180 {
|
nuclear@3
|
1181 const HashNode* p = mHash.GetAlt(key);
|
nuclear@3
|
1182 if (p)
|
nuclear@3
|
1183 {
|
nuclear@3
|
1184 if (pvalue)
|
nuclear@3
|
1185 *pvalue = p->Second;
|
nuclear@3
|
1186 return true;
|
nuclear@3
|
1187 }
|
nuclear@3
|
1188 return false;
|
nuclear@3
|
1189 }
|
nuclear@3
|
1190
|
nuclear@3
|
1191 // Retrieve the pointer to a value under the given key.
|
nuclear@3
|
1192 // - If there's no value under the key, then return NULL.
|
nuclear@3
|
1193 // - If there is a value, return the pointer.
|
nuclear@3
|
1194 inline U* Get(const C& key)
|
nuclear@3
|
1195 {
|
nuclear@3
|
1196 HashNode* p = mHash.GetAlt(key);
|
nuclear@3
|
1197 return p ? &p->Second : 0;
|
nuclear@3
|
1198 }
|
nuclear@3
|
1199 inline const U* Get(const C& key) const
|
nuclear@3
|
1200 {
|
nuclear@3
|
1201 const HashNode* p = mHash.GetAlt(key);
|
nuclear@3
|
1202 return p ? &p->Second : 0;
|
nuclear@3
|
1203 }
|
nuclear@3
|
1204
|
nuclear@3
|
1205 template<class K>
|
nuclear@3
|
1206 inline U* GetAlt(const K& key)
|
nuclear@3
|
1207 {
|
nuclear@3
|
1208 HashNode* p = mHash.GetAlt(key);
|
nuclear@3
|
1209 return p ? &p->Second : 0;
|
nuclear@3
|
1210 }
|
nuclear@3
|
1211 template<class K>
|
nuclear@3
|
1212 inline const U* GetAlt(const K& key) const
|
nuclear@3
|
1213 {
|
nuclear@3
|
1214 const HashNode* p = mHash.GetAlt(key);
|
nuclear@3
|
1215 return p ? &p->Second : 0;
|
nuclear@3
|
1216 }
|
nuclear@3
|
1217
|
nuclear@3
|
1218 // Sizing methods - delegate to Hash.
|
nuclear@3
|
1219 inline UPInt GetSize() const { return mHash.GetSize(); }
|
nuclear@3
|
1220 inline void Resize(UPInt n) { mHash.Resize(n); }
|
nuclear@3
|
1221 inline void SetCapacity(UPInt newSize) { mHash.SetCapacity(newSize); }
|
nuclear@3
|
1222
|
nuclear@3
|
1223 // Iterator API, like STL.
|
nuclear@3
|
1224 typedef typename Container::ConstIterator ConstIterator;
|
nuclear@3
|
1225 typedef typename Container::Iterator Iterator;
|
nuclear@3
|
1226
|
nuclear@3
|
1227 inline Iterator Begin() { return mHash.Begin(); }
|
nuclear@3
|
1228 inline Iterator End() { return mHash.End(); }
|
nuclear@3
|
1229 inline ConstIterator Begin() const { return mHash.Begin(); }
|
nuclear@3
|
1230 inline ConstIterator End() const { return mHash.End(); }
|
nuclear@3
|
1231
|
nuclear@3
|
1232 Iterator Find(const C& key) { return mHash.FindAlt(key); }
|
nuclear@3
|
1233 ConstIterator Find(const C& key) const { return mHash.FindAlt(key); }
|
nuclear@3
|
1234
|
nuclear@3
|
1235 template<class K>
|
nuclear@3
|
1236 Iterator FindAlt(const K& key) { return mHash.FindAlt(key); }
|
nuclear@3
|
1237 template<class K>
|
nuclear@3
|
1238 ConstIterator FindAlt(const K& key) const { return mHash.FindAlt(key); }
|
nuclear@3
|
1239 };
|
nuclear@3
|
1240
|
nuclear@3
|
1241
|
nuclear@3
|
1242
|
nuclear@3
|
1243 // Hash with uncached hash code; declared for convenience.
|
nuclear@3
|
1244 template<class C, class U, class HashF = FixedSizeHash<C>, class Allocator = ContainerAllocator<C> >
|
nuclear@3
|
1245 class HashUncached
|
nuclear@3
|
1246 : public Hash<C, U, HashF, Allocator, HashNode<C,U,HashF>,
|
nuclear@3
|
1247 HashsetNodeEntry<HashNode<C,U,HashF>, typename HashNode<C,U,HashF>::NodeHashF> >
|
nuclear@3
|
1248 {
|
nuclear@3
|
1249 public:
|
nuclear@3
|
1250 typedef HashUncached<C, U, HashF, Allocator> SelfType;
|
nuclear@3
|
1251 typedef Hash<C, U, HashF, Allocator, HashNode<C,U,HashF>,
|
nuclear@3
|
1252 HashsetNodeEntry<HashNode<C,U,HashF>,
|
nuclear@3
|
1253 typename HashNode<C,U,HashF>::NodeHashF> > BaseType;
|
nuclear@3
|
1254
|
nuclear@3
|
1255 // Delegated constructors.
|
nuclear@3
|
1256 HashUncached() { }
|
nuclear@3
|
1257 HashUncached(int sizeHint) : BaseType(sizeHint) { }
|
nuclear@3
|
1258 HashUncached(const SelfType& src) : BaseType(src) { }
|
nuclear@3
|
1259 ~HashUncached() { }
|
nuclear@3
|
1260 void operator = (const SelfType& src) { BaseType::operator = (src); }
|
nuclear@3
|
1261 };
|
nuclear@3
|
1262
|
nuclear@3
|
1263
|
nuclear@3
|
1264
|
nuclear@3
|
1265 // And identity hash in which keys serve as hash value. Can be uncached,
|
nuclear@3
|
1266 // since hash computation is assumed cheap.
|
nuclear@3
|
1267 template<class C, class U, class Allocator = ContainerAllocator<C>, class HashF = IdentityHash<C> >
|
nuclear@3
|
1268 class HashIdentity
|
nuclear@3
|
1269 : public HashUncached<C, U, HashF, Allocator>
|
nuclear@3
|
1270 {
|
nuclear@3
|
1271 public:
|
nuclear@3
|
1272 typedef HashIdentity<C, U, Allocator, HashF> SelfType;
|
nuclear@3
|
1273 typedef HashUncached<C, U, HashF, Allocator> BaseType;
|
nuclear@3
|
1274
|
nuclear@3
|
1275 // Delegated constructors.
|
nuclear@3
|
1276 HashIdentity() { }
|
nuclear@3
|
1277 HashIdentity(int sizeHint) : BaseType(sizeHint) { }
|
nuclear@3
|
1278 HashIdentity(const SelfType& src) : BaseType(src) { }
|
nuclear@3
|
1279 ~HashIdentity() { }
|
nuclear@3
|
1280 void operator = (const SelfType& src) { BaseType::operator = (src); }
|
nuclear@3
|
1281 };
|
nuclear@3
|
1282
|
nuclear@3
|
1283
|
nuclear@3
|
1284 } // OVR
|
nuclear@3
|
1285
|
nuclear@3
|
1286
|
nuclear@3
|
1287 #ifdef OVR_DEFINE_NEW
|
nuclear@3
|
1288 #define new OVR_DEFINE_NEW
|
nuclear@3
|
1289 #endif
|
nuclear@3
|
1290
|
nuclear@3
|
1291 #endif
|