source: trunk/CrypPlugins/WorkspaceManager/View/VisualComponents/CryptoLineView/PowerCollections/Hash.cs @ 1927

Last change on this file since 1927 was 1927, checked in by matkovic, 11 years ago

-added PowerCollection library
-added QuadTree
-improved path finding performance

File size: 29.8 KB
Line 
1//******************************
2// Written by Peter Golde
3// Copyright (c) 2004-2007, Wintellect
4//
5// Use and restribution of this code is subject to the license agreement
6// contained in the file "License.txt" accompanying this file.
7//******************************
8
9using System;
10using System.Diagnostics;
11using System.Collections.Generic;
12using System.Runtime.Serialization;
13
14
15namespace Wintellect.PowerCollections
16{
17    /// <summary>
18    /// The base implementation for various collections classes that use hash tables
19    /// as part of their implementation. This class should not (and can not) be
20    /// used directly by end users; it's only for internal use by the collections package. The Hash
21    /// does not handle duplicate values.
22    /// </summary>
23    /// <remarks>
24    /// The Hash manages items of type T, and uses a IComparer&lt;ItemTYpe&gt; that
25    /// hashes compares items to hash items into the table. 
26    ///</remarks>
27    [Serializable]
28    internal class Hash<T> : IEnumerable<T>, ISerializable, IDeserializationCallback
29    {
30        // NOTE: If you add new member variables, you very well may need to change the serialization
31        // code to serialize that member.
32        private IEqualityComparer<T> equalityComparer;                  // interface for comparing elements
33
34        private int count;                                              // The count of elements in the table.
35        private int usedSlots;                          // Includes real elements and deleted elements with the collision bit on. Used to determine
36                                                        // when we need to resize.
37        private int totalSlots;               // Size of the table. Always a power of two.
38        private float loadFactor;          // maximal load factor for the table.
39        private int thresholdGrow;      // floor(totalSlots * loadFactor);
40        private int thresholdShrink;     // thresholdGrow / 3.
41        private int hashMask;              // Mask to convert hash values to the size of the table.
42        private int secondaryShift;       // Shift to get the secondary skip value.
43
44        private Slot[] table;                 // The hash table.
45
46        private int changeStamp;        // An integer that is changed every time the table structurally changes.
47                                                        // Used so that enumerations throw an exception if the tree is changed
48                                                        // during enumeration.
49
50        private const int MINSIZE = 16;       // minimum number of slots.
51
52        private SerializationInfo serializationInfo;       // Info used during deserialization.
53
54        /// <summary>
55        /// The structure that has each slot in the hash table. Each slot has three parts:
56        /// 1. The collision bit. Indicates whether some item visited this slot but had to
57        /// keep looking because the slot was full.
58        /// 2. 31-bit full hash value of the item. If zero, the slot is empty.
59        /// 3. The item itself.
60        /// </summary>
61        struct Slot
62        {
63            private uint hash_collision;   // Lower 31 bits: the hash value. Top bit: the collision bit.
64            public T item;        // The item.
65
66            /// <summary>
67            /// The full hash value associated with the value in this slot, or zero
68            /// if the slot is empty.
69            /// </summary>
70            public int HashValue
71            {
72                get {
73                    return (int) (hash_collision & 0x7FFFFFFF);
74                }
75                set {
76                    Debug.Assert((value & 0x80000000) == 0);  // make sure sign bit isn't set.
77                    hash_collision = (uint)value | (hash_collision & 0x80000000);
78                }
79            }
80
81            /// <summary>
82            /// Is this slot empty?
83            /// </summary>
84            public bool Empty {
85                get {
86                    return HashValue == 0;
87                }
88            }
89
90            /// <summary>
91            /// Clear this slot, leaving the collision bit alone.
92            /// </summary>
93            public void Clear() {
94                HashValue = 0;
95                item = default(T);        // Done to avoid keeping things alive that shouldn't be.
96            }
97
98            /// <summary>
99            /// The "Collision" bit indicates that some value hit this slot and
100            /// collided, so had to try another slot.
101            /// </summary>
102            public bool Collision
103            {
104                get
105                {
106                    return (hash_collision & 0x80000000) != 0;
107                }
108                set
109                {
110                    if (value)
111                        hash_collision |= 0x80000000;
112                    else
113                        hash_collision &= 0x7FFFFFFF;
114                }
115            }
116        }
117
118        /// <summary>
119        /// Constructor. Create a new hash table.
120        /// </summary>
121        /// <param name="equalityComparer">The comparer to use to compare items. </param>
122        public Hash(IEqualityComparer<T> equalityComparer)
123        {
124            this.equalityComparer = equalityComparer;
125            this.loadFactor = 0.70F;           // default load factor.
126        }
127
128        /// <summary>
129        /// Gets the current enumeration stamp. Call CheckEnumerationStamp later
130        /// with this value to throw an exception if the hash table is changed.
131        /// </summary>
132        /// <returns>The current enumeration stamp.</returns>
133        internal int GetEnumerationStamp()
134        {
135            return changeStamp;
136        }
137
138        /// <summary>
139        /// Must be called whenever there is a structural change in the tree. Causes
140        /// changeStamp to be changed, which causes any in-progress enumerations
141        /// to throw exceptions.
142        /// </summary>
143        internal void StopEnumerations()
144        {
145            ++changeStamp;
146        }
147
148        /// <summary>
149        /// Checks the given stamp against the current change stamp. If different, the
150        /// collection has changed during enumeration and an InvalidOperationException
151        /// must be thrown
152        /// </summary>
153        /// <param name="startStamp">changeStamp at the start of the enumeration.</param>
154        internal void CheckEnumerationStamp(int startStamp)
155        {
156            if (startStamp != changeStamp) {
157                throw new InvalidOperationException(Strings.ChangeDuringEnumeration);
158            }
159        }
160
161        /// <summary>
162        /// Gets the full hash code for an item.
163        /// </summary>
164        /// <param name="item">Item to get hash code for.</param>
165        /// <returns>The full hash code. It is never zero.</returns>
166        private int GetFullHash(T item) 
167        {
168            uint hash;
169
170            hash = (uint)Util.GetHashCode(item, equalityComparer);
171
172            // The .NET framework tends to produce pretty bad hash codes.
173            // Scramble them up to be much more random!
174            hash += ~(hash << 15);
175            hash ^=  (hash >> 10);
176            hash +=  (hash << 3);
177            hash ^=  (hash >> 6);
178            hash += ~(hash << 11);
179            hash ^=  (hash >> 16); 
180            hash &= 0x7FFFFFFF;
181            if (hash == 0)
182                hash = 0x7FFFFFFF;     // Make sure it isn't zero.
183            return (int)hash;
184        }
185
186        /// <summary>
187        /// Get the initial bucket number and skip amount from the full hash value.
188        /// </summary>
189        /// <param name="hash">The full hash value.</param>
190        /// <param name="initialBucket">Returns the initial bucket. Always in the range 0..(totalSlots - 1).</param>
191        /// <param name="skip">Returns the skip values. Always odd in the range 0..(totalSlots - 1).</param>
192        private void GetHashValuesFromFullHash(int hash, out int initialBucket, out int skip)
193        {
194            initialBucket = hash & hashMask;
195
196            // The skip value must be relatively prime to the table size. Since the table size is a
197            // power of two, any odd number is relatively prime, so oring in 1 will do it.
198            skip = ((hash >> secondaryShift) & hashMask) | 1;
199        }
200
201        /// <summary>
202        /// Gets the full hash value, initial bucket number, and skip amount for an item.
203        /// </summary>
204        /// <param name="item">Item to get hash value of.</param>
205        /// <param name="initialBucket">Returns the initial bucket. Always in the range 0..(totalSlots - 1).</param>
206        /// <param name="skip">Returns the skip values. Always odd in the range 0..(totalSlots - 1).</param>
207        /// <returns>The full hash value. This is never zero.</returns>
208        private int GetHashValues(T item, out int initialBucket, out int skip)
209        {
210            int hash = GetFullHash(item);
211            GetHashValuesFromFullHash(hash, out initialBucket, out skip);
212            return hash;
213        }
214
215
216        /// <summary>
217        /// Make sure there are enough slots in the hash table that <paramref name="additionalItems"/>
218        /// items can be inserted into the table.
219        /// </summary>
220        /// <param name="additionalItems">Number of additional items we are inserting.</param>
221        private void EnsureEnoughSlots(int additionalItems)
222        {
223            StopEnumerations();
224
225            if (usedSlots + additionalItems > thresholdGrow) {
226                // We need to expand the table. Figure out to what size.
227                int newSize;
228               
229                newSize = Math.Max(totalSlots, MINSIZE);
230                while ((int)(newSize * loadFactor) < usedSlots + additionalItems) {
231                    newSize *= 2;
232                    if (newSize <= 0) {
233                        // Must have overflowed the size of an int. Hard to believe we didn't run out of memory first.
234                        throw new InvalidOperationException(Strings.CollectionTooLarge);
235                    }
236                }
237
238                ResizeTable(newSize);
239            }
240        }
241
242        /// <summary>
243        /// Check if the number of items in the table is small enough that
244        /// we should shrink the table again.
245        /// </summary>
246        private void ShrinkIfNeeded()
247        {
248            if (count < thresholdShrink) {
249                int newSize;
250
251                if (count > 0) {
252                    newSize = MINSIZE;
253                    while ((int)(newSize * loadFactor) < count)
254                        newSize *= 2;
255                }
256                else {
257                    // We've removed all the elements. Shrink to zero.
258                    newSize = 0;
259                }
260
261                ResizeTable(newSize);
262            }
263        }
264
265        /// <summary>
266        /// Given the size of a hash table, compute the "secondary shift" value -- the shift
267        /// that is used to determine the skip amount for collision resolution.
268        /// </summary>
269        /// <param name="newSize">The new size of the table.</param>
270        /// <returns>The secondary skip amount.</returns>
271        private static int GetSecondaryShift(int newSize)
272        {
273            int x = newSize - 2;      // x is of the form 0000111110 -- a single string of 1's followed by a single zero.
274            int secondaryShift = 0;
275
276            // Keep shifting x until it is the set of bits we want to extract: it be the highest bits possible,
277            // but can't overflow into the sign bit.
278            while ((x & 0x40000000) == 0) {
279                x <<= 1;
280                ++secondaryShift;
281            }
282
283            return secondaryShift;
284        }
285
286        /// <summary>
287        /// Resize the hash table to the given new size, moving all items into the
288        /// new hash table.
289        /// </summary>
290        /// <param name="newSize">The new size of the hash table. Must be a power
291        /// of two.</param>
292        private void ResizeTable(int newSize)
293        {
294            Slot[] oldTable = table;        // Move all the items from this table to the new table.
295
296            Debug.Assert((newSize & (newSize - 1)) == 0);            // Check newSize is a power of two.
297            totalSlots = newSize;
298            thresholdGrow = (int)(totalSlots * loadFactor);
299            thresholdShrink = thresholdGrow / 3;
300            if (thresholdShrink <= MINSIZE)
301                thresholdShrink = 1;
302            hashMask = newSize - 1;
303            secondaryShift = GetSecondaryShift(newSize);
304            if (totalSlots > 0)
305                table = new Slot[totalSlots];
306            else
307                table = null;
308
309            if (oldTable != null && table != null) {
310                foreach (Slot oldSlot in oldTable) {
311                    int hash, bucket, skip;
312
313                    hash = oldSlot.HashValue;
314                    GetHashValuesFromFullHash(hash, out bucket, out skip);
315
316                    // Find an empty bucket.
317                    while (! table[bucket].Empty) {
318                        // The slot is used, but isn't our item. Set the collision bit and keep looking.
319                        table[bucket].Collision = true;
320                        bucket = (bucket + skip) & hashMask;
321                    }
322
323                    // We found an empty bucket.
324                    table[bucket].HashValue = hash;
325                    table[bucket].item = oldSlot.item;
326                }
327            }
328
329            usedSlots = count;      // no deleted elements have the collision bit on now.
330        }
331
332        /// <summary>
333        /// Get the number of items in the hash table.
334        /// </summary>
335        /// <value>The number of items stored in the hash table.</value>
336        public int ElementCount
337        {
338            get
339            {
340                return count;
341            }
342        }
343
344        /// <summary>
345        /// Get the number of slots in the hash table. Exposed internally
346        /// for testing purposes.
347        /// </summary>
348        /// <value>The number of slots in the hash table.</value>
349        internal int SlotCount
350        {
351            get
352            {
353                return totalSlots;
354            }
355        }
356
357        /// <summary>
358        /// Get or change the load factor. Changing the load factor may cause
359        /// the size of the table to grow or shrink accordingly.
360        /// </summary>
361        /// <value></value>
362        public float LoadFactor
363        {
364            get
365            {
366                return loadFactor;
367            }
368            set
369            {
370                // Don't allow hopelessly inefficient load factors.
371                if (value < 0.25 || value > 0.95)
372                    throw new ArgumentOutOfRangeException("value", value, Strings.InvalidLoadFactor);
373
374                StopEnumerations();
375
376                bool maybeExpand = value < loadFactor;    // May need to expand or shrink the table -- which?
377
378                // Update loadFactor and thresholds.
379                loadFactor = value;
380                thresholdGrow = (int)(totalSlots * loadFactor);
381                thresholdShrink = thresholdGrow / 3;
382                if (thresholdShrink <= MINSIZE)
383                    thresholdShrink = 1;
384
385                // Possibly expand or shrink the table.
386                if (maybeExpand)
387                    EnsureEnoughSlots(0);
388                else
389                    ShrinkIfNeeded();
390            }
391        }
392
393        /// <summary>
394        /// Insert a new item into the hash table. If a duplicate item exists, can replace or
395        /// do nothing.
396        /// </summary>
397        /// <param name="item">The item to insert.</param>
398        /// <param name="replaceOnDuplicate">If true, duplicate items are replaced. If false, nothing
399        /// is done if a duplicate already exists.</param>
400        /// <param name="previous">If a duplicate was found, returns it (whether replaced or not).</param>
401        /// <returns>True if no duplicate existed, false if a duplicate was found.</returns>
402        public bool Insert(T item, bool replaceOnDuplicate, out T previous)
403        {
404            int hash, bucket, skip;
405            int emptyBucket = -1;                      // If >= 0, an empty bucket we can use for a true insert
406            bool duplicateMightExist = true;      // If true, still the possibility that a duplicate exists.
407
408            EnsureEnoughSlots(1);            // Ensure enough room to insert. Also stops enumerations.
409
410            hash = GetHashValues(item, out bucket, out skip);
411
412            for (;;) {
413                if (table[bucket].Empty) {
414                    // Record the location of the first empty bucket seen. This is where the item will
415                    // go if no duplicate exists.
416                    if (emptyBucket == -1)
417                        emptyBucket = bucket; 
418                 
419                    if (!duplicateMightExist ||  !table[bucket].Collision) {
420                        // There can't be a duplicate further on, because a bucket with the collision bit
421                        // clear was found (here or earlier). We have the place to insert.
422                        break;
423                    }
424                }
425                else if (table[bucket].HashValue == hash && equalityComparer.Equals(table[bucket].item, item)) {
426                    // We found a duplicate item. Replace it if requested to.
427                    previous = table[bucket].item;
428                    if (replaceOnDuplicate) 
429                        table[bucket].item = item;
430                    return false;
431                }
432                else {
433                    // The slot is used, but isn't our item.
434                    if (!table[bucket].Collision) {
435                        // Since the collision bit is off, we can't have a duplicate.
436                        if (emptyBucket >= 0) {
437                            // We already have an empty bucket to use.
438                            break;
439                        }
440                        else {
441                            // Keep searching for an empty bucket to place the item.
442                            table[bucket].Collision = true;
443                            duplicateMightExist = false;
444                        }
445                    }
446                }
447
448                bucket = (bucket + skip) & hashMask;
449            }
450
451            // We found an empty bucket. Insert the new item.
452            table[emptyBucket].HashValue = hash;
453            table[emptyBucket].item = item;
454
455            ++count;
456            if (!table[emptyBucket].Collision)
457                ++usedSlots;
458            previous = default(T);
459            return true;
460        }
461
462        /// <summary>
463        /// Deletes an item from the hash table.
464        /// </summary>
465        /// <param name="item">Item to search for and delete.</param>
466        /// <param name="itemDeleted">If true returned, the actual item stored in the hash table (must be
467        /// equal to <paramref name="item"/>, but may not be identical.</param>
468        /// <returns>True if item was found and deleted, false if item wasn't found.</returns>
469        public bool Delete(T item, out T itemDeleted)
470        {
471            int hash, bucket, skip;
472
473            StopEnumerations();
474
475            if (count == 0) {
476                itemDeleted = default(T);
477                return false;
478            }
479
480            hash = GetHashValues(item, out bucket, out skip);
481
482            for (; ; ) {
483                if (table[bucket].HashValue == hash && equalityComparer.Equals(table[bucket].item, item)) {
484                    // Found the item. Remove it.
485                    itemDeleted = table[bucket].item;
486                    table[bucket].Clear();
487                    --count;
488                    if (!table[bucket].Collision)
489                        --usedSlots;
490                    ShrinkIfNeeded();
491                    return true;
492                }
493                else if (!table[bucket].Collision) {
494                    // No collision bit, so we can stop searching. No such element.
495                    itemDeleted = default(T);
496                    return false;
497                }
498
499                bucket = (bucket + skip) & hashMask;
500            }
501        }
502
503        /// <summary>
504        /// Find an item in the hash table. If found, optionally replace it with the
505        /// finding item.
506        /// </summary>
507        /// <param name="find">Item to find.</param>
508        /// <param name="replace">If true, replaces the equal item in the hash table
509        /// with <paramref name="item"/>.</param>
510        /// <param name="item">Returns the equal item found in the table, if true was returned.</param>
511        /// <returns>True if the item was found, false otherwise.</returns>
512        public bool Find(T find, bool replace, out T item)
513        {
514            int hash, bucket, skip;
515
516            if (count == 0) {
517                item = default(T);
518                return false;
519            }
520
521            hash = GetHashValues(find, out bucket, out skip);
522
523            for (; ; ) {
524                if (table[bucket].HashValue == hash && equalityComparer.Equals(table[bucket].item, find)) {
525                    // Found the item. 
526                    item = table[bucket].item;
527                    if (replace)
528                        table[bucket].item = find;
529                    return true;
530                }
531                else if (!table[bucket].Collision) {
532                    // No collision bit, so we can stop searching. No such element.
533                    item = default(T);
534                    return false;
535                }
536
537                bucket = (bucket + skip) & hashMask;
538            }
539        }
540
541        /// <summary>
542        /// Enumerate all of the items in the hash table. The items
543        /// are enumerated in a haphazard, unpredictable order.
544        /// </summary>
545        /// <returns>An IEnumerator&lt;T&gt; that enumerates the items
546        /// in the hash table.</returns>
547        public IEnumerator<T> GetEnumerator()
548        {
549            if (count > 0) {
550                int startStamp = changeStamp;
551
552                foreach (Slot slot in table) {
553                    if (!slot.Empty) {
554                        yield return slot.item;
555                        CheckEnumerationStamp(startStamp);
556                    }
557                }
558            }
559        }
560
561        /// <summary>
562        /// Enumerate all of the items in the hash table. The items
563        /// are enumerated in a haphazard, unpredictable order.
564        /// </summary>
565        /// <returns>An IEnumerator that enumerates the items
566        /// in the hash table.</returns>
567        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
568        {
569            return GetEnumerator();
570        }
571
572        /// <summary>
573        /// Creates a clone of this hash table.
574        /// </summary>
575        /// <param name="cloneItem">If non-null, this function is applied to each item when cloning. It must be the
576        /// case that this function does not modify the hash code or equality function.</param>
577        /// <returns>A shallow clone that contains the same items.</returns>
578        public Hash<T> Clone(Converter<T,T> cloneItem)
579        {
580            Hash<T> clone = new Hash<T>(equalityComparer);
581            clone.count = this.count;
582            clone.usedSlots = this.usedSlots;
583            clone.totalSlots = this.totalSlots;
584            clone.loadFactor = this.loadFactor;
585            clone.thresholdGrow = this.thresholdGrow;
586            clone.thresholdShrink = this.thresholdShrink;
587            clone.hashMask = this.hashMask;
588            clone.secondaryShift = this.secondaryShift;
589            if (table != null) {
590                clone.table = (Slot[])table.Clone();
591
592                if (cloneItem != null) {
593                    for (int i = 0; i < table.Length; ++i) {
594                        if (!table[i].Empty)
595                            table[i].item = cloneItem(table[i].item);
596                    }
597                }
598            }
599
600            return clone;
601        }
602
603        #region Serialization
604
605        /// <summary>
606        /// Serialize the hash table. Called from the serialization infrastructure.
607        /// </summary>
608        void ISerializable.GetObjectData(SerializationInfo info, StreamingContext context)
609        {
610            if (info == null)
611                throw new ArgumentNullException("info");
612
613            info.AddValue("equalityComparer", equalityComparer, typeof(IEqualityComparer<T>));
614            info.AddValue("loadFactor", loadFactor, typeof(float));
615            T[] items = new T[count];
616            int i = 0;
617            foreach (Slot slot in table)
618                if (! slot.Empty)
619                    items[i++] = slot.item;
620            info.AddValue("items", items, typeof(T[]));
621        }
622
623        /// <summary>
624        /// Called on deserialization. We cannot deserialize now, because hash codes
625        /// might not be correct now. We do real deserialization in the OnDeserialization call.
626        /// </summary>
627        protected Hash(SerializationInfo serInfo, StreamingContext context)
628        {
629            // Save away the serialization info for use later. We can't be sure of hash codes
630            // being stable until the entire object graph is deserialized, so we wait until then
631            // to deserialize.
632            serializationInfo = serInfo;
633        }
634
635        /// <summary>
636        /// Deserialize the hash table. Called from the serialization infrastructure when
637        /// the object graph has finished deserializing.
638        /// </summary>
639        void IDeserializationCallback.OnDeserialization(object sender)
640        {
641            if (serializationInfo == null)
642                return;
643
644            loadFactor = serializationInfo.GetSingle("loadFactor");
645            equalityComparer = (IEqualityComparer<T>) serializationInfo.GetValue("equalityComparer", typeof(IEqualityComparer<T>));
646
647            T[] items = (T[])serializationInfo.GetValue("items", typeof(T[]));
648            T dummy;
649
650            EnsureEnoughSlots(items.Length);
651            foreach (T item in items)
652                Insert(item, true, out dummy);
653
654            serializationInfo = null;
655        }
656
657        #endregion Serialization
658
659#if DEBUG
660        /// <summary>
661        /// Print out basic stats about the hash table.
662        /// </summary>
663        internal void PrintStats()
664        {
665            Console.WriteLine("count={0}  usedSlots={1}  totalSlots={2}", count, usedSlots, totalSlots);
666            Console.WriteLine("loadFactor={0}  thresholdGrow={1}  thresholdShrink={2}", loadFactor, thresholdGrow, thresholdShrink);
667            Console.WriteLine("hashMask={0:X}  secondaryShift={1}", hashMask, secondaryShift);
668            Console.WriteLine();
669        }
670
671        /// <summary>
672        /// Print out the state of the hash table and each of the slots. Each slot looks like:
673        ///     Slot    4: C 4513e41e hello
674        /// where the "C" indicates the collision bit is on
675        /// the next hex number is the hash value
676        /// followed by ToString() on the item.
677        /// </summary>
678        internal void Print()
679        {
680            PrintStats();
681            for (int i = 0; i < totalSlots; ++i) 
682                Console.WriteLine("Slot {0,4:X}: {1} {2,8:X} {3}", i, table[i].Collision ? "C" : " ", 
683                    table[i].HashValue, table[i].Empty ? "<empty>" : table[i].item.ToString());
684            Console.WriteLine();
685        }
686
687        /// <summary>
688        /// Check that everything appears to be OK in the hash table.
689        /// </summary>
690        internal void Validate()
691        {
692            Debug.Assert(count <= usedSlots);
693            Debug.Assert(count <= totalSlots);
694            Debug.Assert(usedSlots <= totalSlots);
695            Debug.Assert(usedSlots <= thresholdGrow);
696            Debug.Assert((int)(totalSlots * loadFactor) == thresholdGrow);
697            if (thresholdShrink > 1)
698                Debug.Assert(thresholdGrow / 3 == thresholdShrink);
699            else
700                Debug.Assert(thresholdGrow / 3 <= MINSIZE);
701            if (totalSlots > 0) {
702                Debug.Assert((totalSlots & (totalSlots - 1)) == 0);  // totalSlots is a power of two.
703                Debug.Assert(totalSlots - 1 == hashMask);
704                Debug.Assert(GetSecondaryShift(totalSlots) == secondaryShift);
705                Debug.Assert(totalSlots == table.Length);
706            }
707
708            // Traverse the table. Make sure that count and usedSlots are right, and that
709            // each slot looks reasonable.
710            int expectedCount = 0, expectedUsed = 0, initialBucket, skip;
711            if (table != null) {
712                for (int i = 0; i < totalSlots; ++i) {
713                    Slot slot = table[i];
714                    if (slot.Empty) {
715                        // Empty slot
716                        if (slot.Collision)
717                            ++expectedUsed;
718                        Debug.Assert(object.Equals(default(T), slot.item));
719                    }
720                    else {
721                        // not empty.
722                        ++expectedCount;
723                        ++expectedUsed;
724                        Debug.Assert(slot.HashValue != 0);
725                        Debug.Assert(GetHashValues(slot.item, out initialBucket, out skip) == slot.HashValue);
726                        if (initialBucket != i)
727                            Debug.Assert(table[initialBucket].Collision);
728                    }
729                }
730            }
731
732            Debug.Assert(expectedCount == count);
733            Debug.Assert(expectedUsed == usedSlots);
734        }
735
736#endif //DEBUG
737
738    }
739} 
Note: See TracBrowser for help on using the repository browser.