1// Licensed to the .NET Foundation under one or more agreements.
2// The .NET Foundation licenses this file to you under the MIT license.
3// See the LICENSE file in the project root for more information.
4
5
6/*++---------------------------------------------------------------------------------------
7
8Module Name:
9
10 hash.h
11
12Abstract:
13
14 Fast hash table classes,
15--*/
16
17#ifndef _HASH_H_
18#define _HASH_H_
19
20#ifndef ASSERT
21#define ASSERT _ASSERTE
22#endif
23
24
25#include "crst.h"
26
27// #define HASHTABLE_PROFILE
28
29// Track collision chains of up to length X
30const unsigned int HASHTABLE_LOOKUP_PROBES_DATA = 20;
31
32//-------------------------------------------------------
33// enums for special Key values used in hash table
34//
35enum
36{
37 EMPTY = 0,
38 DELETED = 1,
39 INVALIDENTRY = ~0
40};
41
42typedef ULONG_PTR UPTR;
43
44//------------------------------------------------------------------------------
45// classes in use
46//------------------------------------------------------------------------------
47class Bucket;
48class HashMap;
49
50//-------------------------------------------------------
51// class Bucket
52// used by hash table implementation
53//
54typedef DPTR(class Bucket) PTR_Bucket;
55class Bucket
56{
57public:
58 UPTR m_rgKeys[4];
59 UPTR m_rgValues[4];
60
61#define VALUE_MASK (sizeof(LPVOID) == 4 ? 0x7FFFFFFF : I64(0x7FFFFFFFFFFFFFFF))
62
63 void SetValue (UPTR value, UPTR i)
64 {
65 LIMITED_METHOD_CONTRACT;
66
67 ASSERT(value <= VALUE_MASK);
68 m_rgValues[i] = (UPTR) ((m_rgValues[i] & ~VALUE_MASK) | value);
69 }
70
71 UPTR GetValue (UPTR i)
72 {
73 LIMITED_METHOD_DAC_CONTRACT;
74
75 return (UPTR)(m_rgValues[i] & VALUE_MASK);
76 }
77
78 UPTR IsCollision() // useful sentinel for fast fail of lookups
79 {
80 LIMITED_METHOD_CONTRACT;
81
82 return (UPTR) (m_rgValues[0] & ~VALUE_MASK);
83 }
84
85 void SetCollision()
86 {
87 LIMITED_METHOD_CONTRACT;
88
89 m_rgValues[0] |= ~VALUE_MASK; // set collision bit
90 m_rgValues[1] &= VALUE_MASK; // reset has free slots bit
91 }
92
93 BOOL HasFreeSlots()
94 {
95 WRAPPER_NO_CONTRACT;
96
97 // check for free slots available in the bucket
98 // either there is no collision or a free slot has been during
99 // compaction
100 return (!IsCollision() || (m_rgValues[1] & ~VALUE_MASK));
101 }
102
103 void SetFreeSlots()
104 {
105 LIMITED_METHOD_CONTRACT;
106
107 m_rgValues[1] |= ~VALUE_MASK; // set has free slots bit
108 }
109
110 BOOL InsertValue(const UPTR key, const UPTR value);
111};
112
113
114//------------------------------------------------------------------------------
115// bool (*CompareFnPtr)(UPTR,UPTR); pointer to a function that takes 2 UPTRs
116// and returns a boolean, provide a function with this signature to the HashTable
117// to use for comparing Values during lookup
118//------------------------------------------------------------------------------
119typedef BOOL (*CompareFnPtr)(UPTR,UPTR);
120
121class Compare
122{
123protected:
124 Compare()
125 {
126 LIMITED_METHOD_CONTRACT;
127
128 m_ptr = NULL;
129 }
130public:
131 CompareFnPtr m_ptr;
132
133 Compare(CompareFnPtr ptr)
134 {
135 LIMITED_METHOD_CONTRACT;
136
137 _ASSERTE(ptr != NULL);
138 m_ptr = ptr;
139 }
140
141 virtual ~Compare()
142 {
143 LIMITED_METHOD_CONTRACT;
144 }
145
146 virtual UPTR CompareHelper(UPTR val1, UPTR storedval)
147 {
148 WRAPPER_NO_CONTRACT;
149
150#ifndef _DEBUG
151 CONTRACTL
152 {
153 DISABLED(THROWS); // This is not a bug, we cannot decide, since the function ptr called may be either.
154 DISABLED(GC_NOTRIGGER); // This is not a bug, we cannot decide, since the function ptr called may be either.
155 }
156 CONTRACTL_END;
157#endif // !_DEBUG
158
159 return (*m_ptr)(val1,storedval);
160 }
161};
162
163class ComparePtr : public Compare
164{
165public:
166 ComparePtr (CompareFnPtr ptr)
167 {
168 LIMITED_METHOD_CONTRACT;
169
170 _ASSERTE(ptr != NULL);
171 m_ptr = ptr;
172 }
173
174 virtual UPTR CompareHelper(UPTR val1, UPTR storedval)
175 {
176 WRAPPER_NO_CONTRACT;
177
178#ifndef _DEBUG
179 CONTRACTL
180 {
181 DISABLED(THROWS); // This is not a bug, we cannot decide, since the function ptr called may be either.
182 DISABLED(GC_NOTRIGGER); // This is not a bug, we cannot decide, since the function ptr called may be either.
183 }
184 CONTRACTL_END;
185#endif // !_DEBUG
186
187 storedval <<=1;
188 return (*m_ptr)(val1,storedval);
189 }
190};
191
192//------------------------------------------------------------------------------
193// Class HashMap
194// Fast Hash table, for concurrent use,
195// stores a 4 byte Key and a 4 byte Value for each slot.
196// Duplicate keys are allowed, (keys are compared as 4 byte UPTRs)
197// Duplicate values are allowed,(values are compared using comparison fn. provided)
198// but if no comparison function is provided then the values should be unique
199//
200// Lookup's don't require to take locks, unless you specify fAsyncMode.
201// Insert and Delete operations require locks
202// Inserting a duplicate value will assert in DEBUG mode, the PROPER way to perform inserts
203// is to take a lock, do a lookup and if the lookup fails then Insert
204//
205// In async mode, deleted slots are not immediately reclaimed (until a rehash), and
206// accesses to the hash table cause a transition to cooperative GC mode, and reclamation of old
207// hash maps (after a rehash) are deferred until GC time.
208// In sync mode, none of this is necessary; however calls to LookupValue must be synchronized as well.
209//
210// Algorithm:
211// The Hash table is an array of buckets, each bucket can contain 4 key/value pairs
212// Special key values are used to identify EMPTY and DELETED slots
213// Hash function uses the current size of the hash table and a SEED based on the key
214// to choose the bucket, seed starts of being the key and gets refined every time
215// the hash function is re-applied.
216//
217// Inserts choose an empty slot in the current bucket for new entries, if the current bucket
218// is full, then the seed is refined and a new bucket is choosen, if an empty slot is not found
219// after 8 retries, the hash table is expanded, this causes the current array of buckets to
220// be put in a free list and a new array of buckets is allocated and all non-deleted entries
221// from the old hash table are rehashed to the new array
222// The old arrays are reclaimed during Compact phase, which should only be called during GC or
223// any other time it is guaranteed that no Lookups are taking place.
224// Concurrent Insert and Delete operations need to be serialized
225//
226// Delete operations, mark the Key in the slot as DELETED, the value is not removed and inserts
227// don't reuse these slots, they get reclaimed during expansion and compact phases.
228//
229//------------------------------------------------------------------------------
230
231class HashMap
232{
233public:
234
235 //@constructor
236 HashMap() DAC_EMPTY();
237 //destructor
238 ~HashMap() DAC_EMPTY();
239
240 // Init
241 void Init(BOOL fAsyncMode, LockOwner *pLock)
242 {
243 WRAPPER_NO_CONTRACT;
244
245 Init(0, (Compare *)NULL,fAsyncMode, pLock);
246 }
247 // Init
248 void Init(DWORD cbInitialSize, BOOL fAsyncMode, LockOwner *pLock)
249 {
250 WRAPPER_NO_CONTRACT;
251
252 Init(cbInitialSize, (Compare*)NULL, fAsyncMode, pLock);
253 }
254 // Init
255 void Init(CompareFnPtr ptr, BOOL fAsyncMode, LockOwner *pLock)
256 {
257 WRAPPER_NO_CONTRACT;
258
259 Init(0, ptr, fAsyncMode, pLock);
260 }
261
262 // Init method
263 void Init(DWORD cbInitialSize, CompareFnPtr ptr, BOOL fAsyncMode, LockOwner *pLock);
264
265
266 //Init method
267 void Init(DWORD cbInitialSize, Compare* pCompare, BOOL fAsyncMode, LockOwner *pLock);
268
269 // check to see if the value is already in the Hash Table
270 // key should be > DELETED
271 // if provided, uses the comparison function ptr to compare values
272 // returns INVALIDENTRY if not found
273 UPTR LookupValue(UPTR key, UPTR value);
274
275 // Insert if the value is not already present
276 // it is illegal to insert duplicate values in the hash map
277 // do a lookup to verify the value is not already present
278
279 void InsertValue(UPTR key, UPTR value);
280
281 // Replace the value if present
282 // returns the previous value, or INVALIDENTRY if not present
283 // does not insert a new value under any circumstances
284
285 UPTR ReplaceValue(UPTR key, UPTR value);
286
287 // mark the entry as deleted and return the stored value
288 // returns INVALIDENTRY, if not found
289 UPTR DeleteValue (UPTR key, UPTR value);
290
291 // for unique keys, use this function to get the value that is
292 // stored in the hash table, returns INVALIDENTRY if key not found
293 UPTR Gethash(UPTR key);
294
295 // Called only when all threads are frozed, like during GC
296 // for a SINGLE user mode, call compact after every delete
297 // operation on the hash table
298 void Compact();
299
300 // Remove all entries from the hash tablex
301 void Clear();
302
303#ifdef DACCESS_COMPILE
304 void EnumMemoryRegions(CLRDataEnumMemoryFlags flags);
305#endif
306
307 // inline helper, in non HASHTABLE_PROFILE mode becomes a NO-OP
308 void ProfileLookup(UPTR ntry, UPTR retValue);
309 // data members used for profiling
310#ifdef HASHTABLE_PROFILE
311 unsigned m_cbRehash; // number of times rehashed
312 unsigned m_cbRehashSlots; // number of slots that were rehashed
313 unsigned m_cbObsoleteTables;
314 unsigned m_cbTotalBuckets;
315 unsigned m_cbInsertProbesGt8; // inserts that needed more than 8 probes
316 LONG m_rgLookupProbes[HASHTABLE_LOOKUP_PROBES_DATA]; // lookup probes
317 UPTR maxFailureProbe; // cost of failed lookup
318
319 void DumpStatistics();
320#endif // HASHTABLE_PROFILE
321
322#if 0 // Test-only code for debugging this class.
323#ifndef DACCESS_COMPILE
324 static void LookupPerfTest(HashMap * table, const unsigned int MinThreshold);
325 static void HashMapTest();
326#endif // !DACCESS_COMPILE
327#endif // 0 // Test-only code for debugging this class.
328
329protected:
330 // static helper function
331 static UPTR PutEntry (Bucket* rgBuckets, UPTR key, UPTR value);
332private:
333
334 DWORD GetNearestIndex(DWORD cbInitialSize);
335
336#ifdef _DEBUG
337 static void Enter(HashMap *); // check valid to enter
338 static void Leave(HashMap *); // check valid to leave
339
340 typedef Holder<HashMap *, HashMap::Enter, HashMap::Leave> SyncAccessHolder;
341 BOOL m_fInSyncCode; // test for non-synchronus access
342#else // !_DEBUG
343 // in non DEBUG mode use a no-op helper
344 typedef NoOpBaseHolder<HashMap *> SyncAccessHolder;
345#endif // !_DEBUG
346
347 // compute the new size, based on the number of free slots
348 // available, compact or expand
349 UPTR NewSize();
350 // create a new bucket array and rehash the non-deleted entries
351 void Rehash();
352 static DWORD GetSize(PTR_Bucket rgBuckets);
353 static void SetSize(Bucket* rgBuckets, size_t size);
354 PTR_Bucket Buckets();
355 UPTR CompareValues(const UPTR value1, const UPTR value2);
356
357 // For double hashing, compute the second hash function once, then add.
358 // H(key, i) = H1(key) + i * H2(key), where 0 <= i < numBuckets
359 static void HashFunction(const UPTR key, const UINT numBuckets, UINT &seed, UINT &incr);
360
361 Compare* m_pCompare; // compare object to be used in lookup
362 SIZE_T m_iPrimeIndex; // current size (index into prime array)
363 PTR_Bucket m_rgBuckets; // array of buckets
364
365 // track the number of inserts and deletes
366 SIZE_T m_cbPrevSlotsInUse;
367 SIZE_T m_cbInserts;
368 SIZE_T m_cbDeletes;
369 // mode of operation, synchronus or single user
370 bool m_fAsyncMode;
371
372#ifdef _DEBUG
373 LPVOID m_lockData;
374 FnLockOwner m_pfnLockOwner;
375 EEThreadId m_writerThreadId;
376#endif // _DEBUG
377
378#ifdef _DEBUG
379 // A thread must own a lock for a hash if it is a writer.
380 BOOL OwnLock();
381#endif // _DEBUG
382
383public:
384 ///---------Iterator----------------
385
386 // Iterator,
387 class Iterator
388 {
389 PTR_Bucket m_pBucket;
390 PTR_Bucket m_pSentinel;
391 int m_id;
392 BOOL m_fEnd;
393
394 public:
395
396 // Constructor
397 Iterator(Bucket* pBucket) :
398 m_pBucket(dac_cast<PTR_Bucket>(pBucket)),
399 m_id(-1), m_fEnd(false)
400 {
401 SUPPORTS_DAC;
402 WRAPPER_NO_CONTRACT;
403
404 if (!m_pBucket) {
405 m_pSentinel = NULL;
406 m_fEnd = true;
407 return;
408 }
409 size_t cbSize = (PTR_size_t(m_pBucket))[0];
410 m_pBucket++;
411 m_pSentinel = m_pBucket+cbSize;
412 MoveNext(); // start
413 }
414
415 Iterator(const Iterator& iter)
416 {
417 LIMITED_METHOD_CONTRACT;
418
419 m_pBucket = iter.m_pBucket;
420 m_pSentinel = iter.m_pSentinel;
421 m_id = iter.m_id;
422 m_fEnd = iter.m_fEnd;
423
424 }
425
426 //destructor
427 ~Iterator(){ LIMITED_METHOD_DAC_CONTRACT; };
428
429 // friend operator==
430 friend bool operator == (const Iterator& lhs, const Iterator& rhs)
431 {
432 LIMITED_METHOD_CONTRACT;
433
434 return (lhs.m_pBucket == rhs.m_pBucket && lhs.m_id == rhs.m_id);
435 }
436 // operator =
437 inline Iterator& operator= (const Iterator& iter)
438 {
439 LIMITED_METHOD_CONTRACT;
440
441 m_pBucket = iter.m_pBucket;
442 m_pSentinel = iter.m_pSentinel;
443 m_id = iter.m_id;
444 m_fEnd = iter.m_fEnd;
445 return *this;
446 }
447
448 // operator ++
449 inline void operator++ ()
450 {
451 WRAPPER_NO_CONTRACT;
452 SUPPORTS_DAC;
453
454 _ASSERTE(!m_fEnd); // check we are not alredy at end
455 MoveNext();
456 }
457 // operator --
458
459
460
461 //accessors : GetDisc() , returns the discriminator
462 inline UPTR GetKey()
463 {
464 LIMITED_METHOD_CONTRACT;
465
466 _ASSERTE(!m_fEnd); // check we are not alredy at end
467 return m_pBucket->m_rgKeys[m_id];
468 }
469 //accessors : SetDisc() , sets the discriminator
470
471
472 //accessors : GetValue(),
473 // returns the pointer that corresponds to the discriminator
474 inline UPTR GetValue()
475 {
476 WRAPPER_NO_CONTRACT;
477 SUPPORTS_DAC;
478
479 _ASSERTE(!m_fEnd); // check we are not alredy at end
480 return m_pBucket->GetValue(m_id);
481 }
482
483
484 // end(), check if the iterator is at the end of the bucket
485 inline BOOL end() const
486 {
487 LIMITED_METHOD_DAC_CONTRACT;
488
489 return m_fEnd;
490 }
491
492 protected:
493
494 void MoveNext()
495 {
496 LIMITED_METHOD_DAC_CONTRACT;
497
498 for (;m_pBucket < m_pSentinel; m_pBucket++)
499 { //loop thru all buckets
500 for (m_id = m_id+1; m_id < 4; m_id++)
501 { //loop through all slots
502 if (m_pBucket->m_rgKeys[m_id] > DELETED)
503 {
504 return;
505 }
506 }
507 m_id = -1;
508 }
509 m_fEnd = true;
510 }
511
512 };
513
514 inline Bucket* firstBucket()
515 {
516 WRAPPER_NO_CONTRACT;
517 SUPPORTS_DAC;
518
519 return m_rgBuckets;
520 }
521
522 // return an iterator, positioned at the beginning of the bucket
523 inline Iterator begin()
524 {
525 WRAPPER_NO_CONTRACT;
526
527 return Iterator(m_rgBuckets);
528 }
529
530 inline SIZE_T GetCount()
531 {
532 LIMITED_METHOD_CONTRACT;
533
534 return m_cbInserts-m_cbDeletes;
535 }
536};
537
538//---------------------------------------------------------------------------------------
539// class PtrHashMap
540// Wrapper class for using Hash table to store pointer values
541// HashMap class requires that high bit is always reset
542// The allocator used within the runtime, always allocates objects 8 byte aligned
543// so we can shift right one bit, and store the result in the hash table
544class PtrHashMap
545{
546 HashMap m_HashMap;
547
548 // key really acts as a hash code. Sanitize it from special values used by the underlying HashMap.
549 inline static UPTR SanitizeKey(UPTR key)
550 {
551 return (key > DELETED) ? key : (key + 100);
552 }
553
554public:
555#ifndef DACCESS_COMPILE
556 void *operator new(size_t size, LoaderHeap *pHeap);
557 void operator delete(void *p);
558#endif // !DACCESS_COMPILE
559
560 // Init
561 void Init(BOOL fAsyncMode, LockOwner *pLock)
562 {
563 WRAPPER_NO_CONTRACT;
564
565 Init(0,NULL,fAsyncMode,pLock);
566 }
567 // Init
568 void Init(DWORD cbInitialSize, BOOL fAsyncMode, LockOwner *pLock)
569 {
570 WRAPPER_NO_CONTRACT;
571
572 Init(cbInitialSize, NULL, fAsyncMode,pLock);
573 }
574 // Init
575 void Init(CompareFnPtr ptr, BOOL fAsyncMode, LockOwner *pLock)
576 {
577 WRAPPER_NO_CONTRACT;
578
579 Init(0, ptr, fAsyncMode,pLock);
580 }
581
582 // Init method
583 void Init(DWORD cbInitialSize, CompareFnPtr ptr, BOOL fAsyncMode, LockOwner *pLock);
584
585 // check to see if the value is already in the Hash Table
586 LPVOID LookupValue(UPTR key, LPVOID pv)
587 {
588 WRAPPER_NO_CONTRACT;
589
590 key = SanitizeKey(key);
591
592 // gmalloc allocator, always allocates 8 byte aligned
593 // so we can shift out the lowest bit
594 // ptr right shift by 1
595 UPTR value = (UPTR)pv;
596 _ASSERTE((value & 0x1) == 0);
597 value>>=1;
598 UPTR val = m_HashMap.LookupValue (key, value);
599 if (val != (UPTR) INVALIDENTRY)
600 {
601 val<<=1;
602 }
603 return (LPVOID)val;
604 }
605
606 // Insert if the value is not already present
607 // it is illegal to insert duplicate values in the hash map
608 // users should do a lookup to verify the value is not already present
609
610 void InsertValue(UPTR key, LPVOID pv)
611 {
612 WRAPPER_NO_CONTRACT;
613
614 key = SanitizeKey(key);
615
616 // gmalloc allocator, always allocates 8 byte aligned
617 // so we can shift out the lowest bit
618 // ptr right shift by 1
619 UPTR value = (UPTR)pv;
620 _ASSERTE((value & 0x1) == 0);
621 value>>=1;
622 m_HashMap.InsertValue (key, value);
623 }
624
625 // Replace the value if present
626 // returns the previous value, or INVALIDENTRY if not present
627 // does not insert a new value under any circumstances
628
629 LPVOID ReplaceValue(UPTR key, LPVOID pv)
630 {
631 WRAPPER_NO_CONTRACT;
632
633 key = SanitizeKey(key);
634
635 // gmalloc allocator, always allocates 8 byte aligned
636 // so we can shift out the lowest bit
637 // ptr right shift by 1
638 UPTR value = (UPTR)pv;
639 _ASSERTE((value & 0x1) == 0);
640 value>>=1;
641 UPTR val = m_HashMap.ReplaceValue (key, value);
642 if (val != (UPTR) INVALIDENTRY)
643 {
644 val<<=1;
645 }
646 return (LPVOID)val;
647 }
648
649 // mark the entry as deleted and return the stored value
650 // returns INVALIDENTRY if not found
651 LPVOID DeleteValue (UPTR key,LPVOID pv)
652 {
653 WRAPPER_NO_CONTRACT;
654
655 key = SanitizeKey(key);
656
657 UPTR value = (UPTR)pv;
658 _ASSERTE((value & 0x1) == 0);
659 value >>=1 ;
660 UPTR val = m_HashMap.DeleteValue(key, value);
661 if (val != (UPTR) INVALIDENTRY)
662 {
663 val <<= 1;
664 }
665 return (LPVOID)val;
666 }
667
668 // for unique keys, use this function to get the value that is
669 // stored in the hash table, returns INVALIDENTRY if key not found
670 LPVOID Gethash(UPTR key)
671 {
672 WRAPPER_NO_CONTRACT;
673
674 key = SanitizeKey(key);
675
676 UPTR val = m_HashMap.Gethash(key);
677 if (val != (UPTR) INVALIDENTRY)
678 {
679 val <<= 1;
680 }
681 return (LPVOID)val;
682 }
683
684 void Compact()
685 {
686 WRAPPER_NO_CONTRACT;
687
688 m_HashMap.Compact();
689 }
690
691 void Clear()
692 {
693 WRAPPER_NO_CONTRACT;
694
695 m_HashMap.Clear();
696 }
697
698 class PtrIterator
699 {
700 HashMap::Iterator iter;
701
702 public:
703 PtrIterator(HashMap& hashMap) : iter(hashMap.begin())
704 {
705 LIMITED_METHOD_DAC_CONTRACT;
706 }
707 PtrIterator(Bucket* bucket) : iter(bucket)
708 {
709 LIMITED_METHOD_DAC_CONTRACT;
710 }
711
712 ~PtrIterator()
713 {
714 LIMITED_METHOD_DAC_CONTRACT;
715 }
716
717 BOOL end()
718 {
719 WRAPPER_NO_CONTRACT;
720 SUPPORTS_DAC;
721
722 return iter.end();
723 }
724
725 UPTR GetKey()
726 {
727 WRAPPER_NO_CONTRACT;
728 SUPPORTS_DAC;
729
730 return iter.GetKey();
731 }
732
733 PTR_VOID GetValue()
734 {
735 WRAPPER_NO_CONTRACT;
736 SUPPORTS_DAC;
737
738 UPTR val = iter.GetValue();
739 if (val != (UPTR) INVALIDENTRY)
740 {
741 val <<= 1;
742 }
743 return PTR_VOID(val);
744 }
745
746 void operator++()
747 {
748 WRAPPER_NO_CONTRACT;
749 SUPPORTS_DAC;
750
751 iter.operator++();
752 }
753 };
754
755 inline Bucket* firstBucket()
756 {
757 WRAPPER_NO_CONTRACT;
758 SUPPORTS_DAC;
759
760 return m_HashMap.firstBucket();
761 }
762
763 // return an iterator, positioned at the beginning of the bucket
764 inline PtrIterator begin()
765 {
766 WRAPPER_NO_CONTRACT;
767
768 return PtrIterator(m_HashMap);
769 }
770
771 inline SIZE_T GetCount()
772 {
773 LIMITED_METHOD_CONTRACT;
774
775 return m_HashMap.GetCount();
776 }
777
778#ifdef DACCESS_COMPILE
779 void EnumMemoryRegions(CLRDataEnumMemoryFlags flags)
780 {
781 SUPPORTS_DAC;
782 m_HashMap.EnumMemoryRegions(flags);
783 }
784#endif // DACCESS_COMPILE
785};
786
787//---------------------------------------------------------------------
788// inline Bucket*& NextObsolete (Bucket* rgBuckets)
789// get the next obsolete bucket in the chain
790inline
791Bucket*& NextObsolete (Bucket* rgBuckets)
792{
793 LIMITED_METHOD_CONTRACT;
794
795 return *(Bucket**)&((size_t*)rgBuckets)[1];
796}
797
798#endif // !_HASH_H_
799