mcs/class/System.Core/ReferenceSources/Set.cs

   1 // Extracted from ../../../external/referencesource/System.Core/System/Linq/Enumerable.cs
   2
   3 using System;
   4 using System.Collections;
   5 using System.Collections.Generic;
   6 using System.Threading;
   7
   8 namespace System.Linq
   9 {
  10     internal class Set<TElement>
  11     {
  12         int[] buckets;
  13         Slot[] slots;
  14         int count;
  15         int freeList;
  16         IEqualityComparer<TElement> comparer;
  17
  18         public Set() : this(null) { }
  19
  20         public Set(IEqualityComparer<TElement> comparer) {
  21             if (comparer == null) comparer = EqualityComparer<TElement>.Default;
  22             this.comparer = comparer;
  23             buckets = new int[7];
  24             slots = new Slot[7];
  25             freeList = -1;
  26         }
  27
  28         // If value is not in set, add it and return true; otherwise return false
  29         public bool Add(TElement value) {
  30             return !Find(value, true);
  31         }
  32
  33         // Check whether value is in set
  34         public bool Contains(TElement value) {
  35             return Find(value, false);
  36         }
  37
  38         // If value is in set, remove it and return true; otherwise return false
  39         public bool Remove(TElement value) {
  40             int hashCode = InternalGetHashCode(value);
  41             int bucket = hashCode % buckets.Length;
  42             int last = -1;
  43             for (int i = buckets[bucket] - 1; i >= 0; last = i, i = slots[i].next) {
  44                 if (slots[i].hashCode == hashCode && comparer.Equals(slots[i].value, value)) {
  45                     if (last < 0) {
  46                         buckets[bucket] = slots[i].next + 1;
  47                     }
  48                     else {
  49                         slots[last].next = slots[i].next;
  50                     }
  51                     slots[i].hashCode = -1;
  52                     slots[i].value = default(TElement);
  53                     slots[i].next = freeList;
  54                     freeList = i;
  55                     return true;
  56                 }
  57             }
  58             return false;
  59         }
  60
  61         bool Find(TElement value, bool add) {
  62             int hashCode = InternalGetHashCode(value);
  63             for (int i = buckets[hashCode % buckets.Length] - 1; i >= 0; i = slots[i].next) {
  64                 if (slots[i].hashCode == hashCode && comparer.Equals(slots[i].value, value)) return true;
  65             }
  66             if (add) {
  67                 int index;
  68                 if (freeList >= 0) {
  69                     index = freeList;
  70                     freeList = slots[index].next;
  71                 }
  72                 else {
  73                     if (count == slots.Length) Resize();
  74                     index = count;
  75                     count++;
  76                 }
  77                 int bucket = hashCode % buckets.Length;
  78                 slots[index].hashCode = hashCode;
  79                 slots[index].value = value;
  80                 slots[index].next = buckets[bucket] - 1;
  81                 buckets[bucket] = index + 1;
  82             }
  83             return false;
  84         }
  85
  86         void Resize() {
  87             int newSize = checked(count * 2 + 1);
  88             int[] newBuckets = new int[newSize];
  89             Slot[] newSlots = new Slot[newSize];
  90             Array.Copy(slots, 0, newSlots, 0, count);
  91             for (int i = 0; i < count; i++) {
  92                 int bucket = newSlots[i].hashCode % newSize;
  93                 newSlots[i].next = newBuckets[bucket] - 1;
  94                 newBuckets[bucket] = i + 1;
  95             }
  96             buckets = newBuckets;
  97             slots = newSlots;
  98         }
  99
 100         internal int InternalGetHashCode(TElement value)
 101         {
 102             //[....] DevDivBugs 171937. work around comparer implementations that throw when passed null
 103             return (value == null) ? 0 : comparer.GetHashCode(value) & 0x7FFFFFFF;
 104         }
 105
 106         internal struct Slot
 107         {
 108             internal int hashCode;
 109             internal TElement value;
 110             internal int next;
 111         }
 112     }
 113 }