|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Diagnostics.Contracts;
using System.Runtime.Serialization;
using System.Security;
using Microsoft.Build.Internal;
using Microsoft.Build.Shared;
/*
==================================================================================================================
This is the standard Hashset with the following changes:
* class renamed
* require T implements IKeyed, and accept IKeyed directly where necessary
* all constructors require a comparer -- an IEqualityComparer<IKeyed> -- to avoid mistakes
* change Contains to give you back the found entry, rather than a boolean
* change Add so that it always adds, even if there's an entry already present with the same name.
We want "replacement" semantics, like a dictionary keyed on name.
* constructor that allows the collection to be read-only
* implement IDictionary<string, T>
* some convenience methods taking 'string' as overloads of methods taking IKeyed
==================================================================================================================
*/
#nullable disable
// The BuildXL package causes an indirect dependency on the RuntimeContracts package, which adds an analyzer which forbids the use of System.Diagnostics.Contract.
// So effectively if your dependencies use RuntimeContracts, it attempts to force itself on your as well.
// See: https://github.com/SergeyTeplyakov/RuntimeContracts/issues/12
#pragma warning disable RA001 // Do not use System.Diagnostics.Contract class.
namespace Microsoft.Build.Collections
{
/// <summary>
/// Implementation notes:
/// This uses an array-based implementation similar to <see cref="Dictionary{TKey, TValue}" />, using a buckets array
/// to map hash values to the Slots array. Items in the Slots array that hash to the same value
/// are chained together through the "next" indices.
///
/// The capacity is always prime; so during resizing, the capacity is chosen as the next prime
/// greater than double the last capacity.
///
/// The underlying data structures are lazily initialized. Because of the observation that,
/// in practice, hashtables tend to contain only a few elements, the initial capacity is
/// set very small (3 elements) unless the ctor with a collection is used.
///
/// The +/- 1 modifications in methods that add, check for containment, etc allow us to
/// distinguish a hash code of 0 from an uninitialized bucket. This saves us from having to
/// reset each bucket to -1 when resizing. See Contains, for example.
///
/// Set methods such as UnionWith, IntersectWith, ExceptWith, and SymmetricExceptWith modify
/// this set.
///
/// Some operations can perform faster if we can assume "other" contains unique elements
/// according to this equality comparer. The only times this is efficient to check is if
/// other is a hashset. Note that checking that it's a hashset alone doesn't suffice; we
/// also have to check that the hashset is using the same equality comparer. If other
/// has a different equality comparer, it will have unique elements according to its own
/// equality comparer, but not necessarily according to ours. Therefore, to go these
/// optimized routes we check that other is a hashset using the same equality comparer.
///
/// A HashSet with no elements has the properties of the empty set. (See IsSubset, etc. for
/// special empty set checks.)
///
/// A couple of methods have a special case if other is this (e.g. SymmetricExceptWith).
/// If we didn't have these checks, we could be iterating over the set and modifying at
/// the same time.
/// </summary>
/// <typeparam name="T"></typeparam>
[DebuggerTypeProxy(typeof(Microsoft.Build.Collections.HashSetDebugView<>))]
[DebuggerDisplay("Count = {Count}")]
[SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix", Justification = "By design")]
[Serializable()]
#if FEATURE_SECURITY_PERMISSIONS
[System.Security.Permissions.HostProtection(MayLeakOnAbort = true)]
#endif
internal class RetrievableEntryHashSet<T> : IRetrievableEntryHashSet<T>
where T : class, IKeyed
{
// store lower 31 bits of hash code
private const int Lower31BitMask = 0x7FFFFFFF;
// when constructing a hashset from an existing collection, it may contain duplicates,
// so this is used as the max acceptable excess ratio of capacity to count. Note that
// this is only used on the ctor and not to automatically shrink if the hashset has, e.g,
// a lot of adds followed by removes. Users must explicitly shrink by calling TrimExcess.
// This is set to 3 because capacity is acceptable as 2x rounded up to nearest prime.
private const int ShrinkThreshold = 3;
// constants for serialization
private const String CapacityName = "Capacity";
private const String ElementsName = "Elements";
private const String ComparerName = "Comparer";
private const String VersionName = "Version";
private int[] _buckets;
private Slot[] _slots;
private int _count;
private int _lastIndex;
private int _freeList;
private IEqualityComparer<string> _comparer;
private IConstrainedEqualityComparer<string> _constrainedComparer;
private int _version;
private bool _readOnly;
// temporary variable needed during deserialization
private SerializationInfo _siInfo;
#region Constructors
public RetrievableEntryHashSet(IEqualityComparer<string> comparer)
{
if (comparer == null)
{
ErrorUtilities.ThrowInternalError("use explicit comparer");
}
_comparer = comparer;
_constrainedComparer = comparer as IConstrainedEqualityComparer<string>;
_lastIndex = 0;
_count = 0;
_freeList = -1;
_version = 0;
}
public RetrievableEntryHashSet(IEnumerable<T> collection, IEqualityComparer<string> comparer, bool readOnly = false)
: this(collection, comparer)
{
_readOnly = true; // Set after possible initialization from another collection
}
public RetrievableEntryHashSet(IEnumerable<KeyValuePair<string, T>> collection, IEqualityComparer<string> comparer, bool readOnly = false)
: this(collection.Values(), comparer, readOnly)
{
_readOnly = true; // Set after possible initialization from another collection
}
/// <summary>
/// Implementation Notes:
/// Since resizes are relatively expensive (require rehashing), this attempts to minimize
/// the need to resize by setting the initial capacity based on size of collection.
/// </summary>
public RetrievableEntryHashSet(int suggestedCapacity, IEqualityComparer<string> comparer)
: this(comparer)
{
Initialize(suggestedCapacity);
}
/// <summary>
/// Implementation Notes:
/// Since resizes are relatively expensive (require rehashing), this attempts to minimize
/// the need to resize by setting the initial capacity based on size of collection.
/// </summary>
public RetrievableEntryHashSet(IEnumerable<T> collection, IEqualityComparer<string> comparer)
: this(comparer)
{
if (collection == null)
{
throw new ArgumentNullException(nameof(collection));
}
Contract.EndContractBlock();
// to avoid excess resizes, first set size based on collection's count. Collection
// may contain duplicates, so call TrimExcess if resulting hashset is larger than
// threshold
int suggestedCapacity = 0;
ICollection<T> coll = collection as ICollection<T>;
if (coll != null)
{
suggestedCapacity = coll.Count;
}
Initialize(suggestedCapacity);
this.UnionWith(collection);
if ((_count == 0 && _slots.Length > HashHelpers.GetMinPrime()) ||
(_count > 0 && _slots.Length / _count > ShrinkThreshold))
{
TrimExcess();
}
}
protected RetrievableEntryHashSet(SerializationInfo info, StreamingContext context)
{
// We can't do anything with the keys and values until the entire graph has been
// deserialized and we have a reasonable estimate that GetHashCode is not going to
// fail. For the time being, we'll just cache this. The graph is not valid until
// OnDeserialization has been called.
_siInfo = info;
}
#endregion
// Convenience to minimise change to callers used to dictionaries
public ICollection<string> Keys
{
get
{
var keys = new string[_count];
int i = 0;
foreach (var item in this)
{
keys[i] = item.Key;
i++;
}
return keys;
}
}
// Convenience to minimise change to callers used to dictionaries
public ICollection<T> Values
{
get { return this; }
}
#region ICollection<T> methods
// Convenience to minimise change to callers used to dictionaries
internal T this[string name]
{
get
{
return Get(name);
}
set
{
Debug.Assert(String.Equals(name, value.Key, StringComparison.Ordinal));
Add(value);
}
}
/// <summary>
/// Add item to this hashset. This is the explicit implementation of the <see cref="ICollection{T}" />
/// interface. The other Add method returns bool indicating whether item was added.
/// </summary>
/// <param name="item">item to add</param>
void ICollection<T>.Add(T item)
{
AddEvenIfPresent(item);
}
/// <summary>
/// Remove all items from this set. This clears the elements but not the underlying
/// buckets and slots array. Follow this call by TrimExcess to release these.
/// </summary>
public void Clear()
{
if (_readOnly)
{
ErrorUtilities.ThrowInvalidOperation("OM_NotSupportedReadOnlyCollection");
}
if (_lastIndex > 0)
{
Debug.Assert(_buckets != null, "m_buckets was null but m_lastIndex > 0");
// clear the elements so that the gc can reclaim the references.
// clear only up to m_lastIndex for m_slots
Array.Clear(_slots, 0, _lastIndex);
Array.Clear(_buckets, 0, _buckets.Length);
_lastIndex = 0;
_count = 0;
_freeList = -1;
}
_version++;
}
// Convenience
internal bool Contains(string key)
{
return Get(key) != null;
}
bool ICollection<KeyValuePair<string, T>>.Contains(KeyValuePair<string, T> entry)
{
Debug.Assert(String.Equals(entry.Key, entry.Value.Key, StringComparison.Ordinal));
return Get(entry.Value.Key) != null;
}
public bool ContainsKey(string key)
{
return Get(key) != null;
}
T IDictionary<string, T>.this[string name]
{
get { return Get(name); }
set { Add(value); }
}
/// <summary>
/// Checks if this hashset contains the item
/// </summary>
/// <param name="item">item to check for containment</param>
/// <returns>true if item contained; false if not</returns>
public bool Contains(T item)
{
return Get(item.Key) != null;
}
// Convenience to minimise change to callers used to dictionaries
public bool TryGetValue(string key, out T item)
{
item = Get(key);
return item != null;
}
/// <summary>
/// Gets the item if any with the given name
/// </summary>
/// <param name="key">key to check for containment</param>
/// <returns>The item, if it was found. Otherwise, default(T).</returns>
public T Get(string key)
{
return GetCore(key, 0, key?.Length ?? 0);
}
/// <summary>
/// Gets the item if any with the given name
/// </summary>
/// <param name="key">key to check for containment</param>
/// <param name="index">The position of the substring within <paramref name="key"/>.</param>
/// <param name="length">The maximum number of characters in the <paramref name="key"/> to lookup.</param>
/// <returns>true if item contained; false if not</returns>
public T Get(string key, int index, int length)
{
if (length < 0)
{
throw new ArgumentOutOfRangeException(nameof(length));
}
if (index < 0 || index > (key == null ? 0 : key.Length) - length)
{
throw new ArgumentOutOfRangeException(nameof(index));
}
if (_constrainedComparer == null)
{
throw new InvalidOperationException("Cannot do a constrained lookup on this collection.");
}
return GetCore(key, index, length);
}
/// <summary>
/// Gets the item if any with the given name
/// </summary>
/// <param name="item">item to check for containment</param>
/// <param name="index">The position of the substring within <paramref name="item"/>.</param>
/// <param name="length">The maximum number of characters in the <paramref name="item"/> to lookup.</param>
/// <returns>true if item contained; false if not</returns>
private T GetCore(string item, int index, int length)
{
if (_buckets != null)
{
int hashCode = InternalGetHashCode(item, index, length);
// see note at "HashSet" level describing why "- 1" appears in for loop
for (int i = _buckets[hashCode % _buckets.Length] - 1; i >= 0; i = _slots[i].next)
{
if (_slots[i].hashCode == hashCode && _constrainedComparer != null ? _constrainedComparer.Equals(_slots[i].value.Key, item, index, length) : _comparer.Equals(_slots[i].value.Key, item))
{
return _slots[i].value;
}
}
}
// either m_buckets is null or wasn't found
return default(T);
}
/// <summary>
/// Copy items in this hashset to array, starting at arrayIndex
/// </summary>
/// <param name="array">array to add items to</param>
/// <param name="arrayIndex">index to start at</param>
public void CopyTo(T[] array, int arrayIndex)
{
CopyTo(array, arrayIndex, _count);
}
/// <summary>
/// Remove entry that compares equal to T
/// </summary>
public bool Remove(T item)
{
return Remove(item.Key);
}
bool ICollection<KeyValuePair<string, T>>.Remove(KeyValuePair<string, T> entry)
{
Debug.Assert(String.Equals(entry.Key, entry.Value.Key, StringComparison.Ordinal));
return Remove(entry.Value);
}
/// <summary>
/// Remove item from this hashset
/// </summary>
/// <param name="item">item to remove</param>
/// <returns>true if removed; false if not (i.e. if the item wasn't in the HashSet)</returns>
public bool Remove(string item)
{
if (_readOnly)
{
ErrorUtilities.ThrowInvalidOperation("OM_NotSupportedReadOnlyCollection");
}
if (_buckets != null)
{
int hashCode = InternalGetHashCode(item);
int bucket = hashCode % _buckets.Length;
int last = -1;
for (int i = _buckets[bucket] - 1; i >= 0; last = i, i = _slots[i].next)
{
if (_slots[i].hashCode == hashCode && _comparer.Equals(_slots[i].value.Key, item))
{
if (last < 0)
{
// first iteration; update buckets
_buckets[bucket] = _slots[i].next + 1;
}
else
{
// subsequent iterations; update 'next' pointers
_slots[last].next = _slots[i].next;
}
_slots[i].hashCode = -1;
_slots[i].value = default(T);
_slots[i].next = _freeList;
_count--;
_version++;
if (_count == 0)
{
_lastIndex = 0;
_freeList = -1;
}
else
{
_freeList = i;
}
return true;
}
}
}
// either m_buckets is null or wasn't found
return false;
}
/// <summary>
/// Number of elements in this hashset
/// </summary>
public int Count
{
get { return _count; }
}
/// <summary>
/// Whether this is readonly
/// </summary>
public bool IsReadOnly
{
get { return _readOnly; }
}
/// <summary>
/// Permanently prevent changes to the set.
/// </summary>
internal void MakeReadOnly()
{
_readOnly = true;
}
#endregion
#region IEnumerable methods
public Enumerator GetEnumerator()
{
return new Enumerator(this);
}
IEnumerator<KeyValuePair<string, T>> IEnumerable<KeyValuePair<string, T>>.GetEnumerator()
{
foreach (var entry in this)
{
yield return new KeyValuePair<string, T>(entry.Key, entry);
}
}
IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
return new Enumerator(this);
}
IEnumerator IEnumerable.GetEnumerator()
{
return new Enumerator(this);
}
#endregion
#region ISerializable methods
// [SecurityPermissionAttribute(SecurityAction.LinkDemand, Flags = SecurityPermissionFlag.SerializationFormatter)]
[SecurityCritical]
public virtual void GetObjectData(SerializationInfo info, StreamingContext context)
{
if (info == null)
{
throw new ArgumentNullException(nameof(info));
}
// need to serialize version to avoid problems with serializing while enumerating
info.AddValue(VersionName, _version);
info.AddValue(ComparerName, _comparer, typeof(IEqualityComparer<string>));
info.AddValue(CapacityName, _buckets == null ? 0 : _buckets.Length);
if (_buckets != null)
{
T[] array = new T[_count];
CopyTo(array);
info.AddValue(ElementsName, array, typeof(T[]));
}
}
#endregion
#region IDeserializationCallback methods
public virtual void OnDeserialization(Object sender)
{
if (_siInfo == null)
{
// It might be necessary to call OnDeserialization from a container if the
// container object also implements OnDeserialization. However, remoting will
// call OnDeserialization again. We can return immediately if this function is
// called twice. Note we set m_siInfo to null at the end of this method.
return;
}
int capacity = _siInfo.GetInt32(CapacityName);
_comparer = (IEqualityComparer<string>)_siInfo.GetValue(ComparerName, typeof(IEqualityComparer<string>));
_constrainedComparer = _comparer as IConstrainedEqualityComparer<string>;
_freeList = -1;
if (capacity != 0)
{
_buckets = new int[capacity];
_slots = new Slot[capacity];
T[] array = (T[])_siInfo.GetValue(ElementsName, typeof(T[]));
if (array == null)
{
throw new SerializationException();
}
// there are no resizes here because we already set capacity above
for (int i = 0; i < array.Length; i++)
{
AddEvenIfPresent(array[i]);
}
}
else
{
_buckets = null;
}
_version = _siInfo.GetInt32(VersionName);
_siInfo = null;
}
#endregion
#region HashSet methods
/// <summary>
/// Add item to this HashSet.
/// *** MSBUILD NOTE: Always added - overwrite semantics
/// </summary>
public void Add(T item)
{
AddEvenIfPresent(item);
}
void IDictionary<string, T>.Add(string key, T item)
{
if (key != item.Key)
{
throw new InvalidOperationException();
}
AddEvenIfPresent(item);
}
void ICollection<KeyValuePair<string, T>>.Add(KeyValuePair<string, T> entry)
{
Debug.Assert(String.Equals(entry.Key, entry.Value.Key, StringComparison.Ordinal));
AddEvenIfPresent(entry.Value);
}
/// <summary>
/// Take the union of this HashSet with other. Modifies this set.
///
/// Implementation note: GetSuggestedCapacity (to increase capacity in advance avoiding
/// multiple resizes ended up not being useful in practice; quickly gets to the
/// point where it's a wasteful check.
/// </summary>
/// <param name="other">enumerable with items to add</param>
public void UnionWith(IEnumerable<T> other)
{
if (other == null)
{
throw new ArgumentNullException(nameof(other));
}
Contract.EndContractBlock();
foreach (T item in other)
{
AddEvenIfPresent(item);
}
}
// Copy all elements into array starting at zero based index specified
[SuppressMessage("Microsoft.Usage", "CA2208:InstantiateArgumentExceptionsCorrectly", Justification = "Decently informative for an exception that will probably never actually see the light of day")]
void ICollection<KeyValuePair<string, T>>.CopyTo(KeyValuePair<string, T>[] array, int index)
{
if (index < 0 || Count > array.Length - index)
{
throw new ArgumentException("index");
}
int i = index;
foreach (var entry in this)
{
array[i] = new KeyValuePair<string, T>(entry.Key, entry);
i++;
}
}
public void CopyTo(T[] array) { CopyTo(array, 0, _count); }
[SuppressMessage("Microsoft.Usage", "CA2208:InstantiateArgumentExceptionsCorrectly", Justification = "Decently informative for an exception that will probably never actually see the light of day")]
public void CopyTo(T[] array, int arrayIndex, int count)
{
if (array == null)
{
throw new ArgumentNullException(nameof(array));
}
Contract.EndContractBlock();
// check array index valid index into array
if (arrayIndex < 0)
{
throw new ArgumentOutOfRangeException(nameof(arrayIndex));
}
// also throw if count less than 0
if (count < 0)
{
throw new ArgumentOutOfRangeException(nameof(count));
}
// will array, starting at arrayIndex, be able to hold elements? Note: not
// checking arrayIndex >= array.Length (consistency with list of allowing
// count of 0; subsequent check takes care of the rest)
if (arrayIndex > array.Length || count > array.Length - arrayIndex)
{
throw new ArgumentException("arrayIndex");
}
int numCopied = 0;
for (int i = 0; i < _lastIndex && numCopied < count; i++)
{
if (_slots[i].hashCode >= 0)
{
array[arrayIndex + numCopied] = _slots[i].value;
numCopied++;
}
}
}
/// <summary>
/// Sets the capacity of this list to the size of the list (rounded up to nearest prime),
/// unless count is 0, in which case we release references.
///
/// This method can be used to minimize a list's memory overhead once it is known that no
/// new elements will be added to the list. To completely clear a list and release all
/// memory referenced by the list, execute the following statements:
///
/// list.Clear();
/// list.TrimExcess();
/// </summary>
public void TrimExcess()
{
Debug.Assert(_count >= 0, "m_count is negative");
if (_count == 0)
{
// if count is zero, clear references
_buckets = null;
_slots = null;
_version++;
}
else
{
Debug.Assert(_buckets != null, "m_buckets was null but m_count > 0");
// similar to IncreaseCapacity but moves down elements in case add/remove/etc
// caused fragmentation
int newSize = HashHelpers.GetPrime(_count);
Slot[] newSlots = new Slot[newSize];
int[] newBuckets = new int[newSize];
// move down slots and rehash at the same time. newIndex keeps track of current
// position in newSlots array
int newIndex = 0;
for (int i = 0; i < _lastIndex; i++)
{
if (_slots[i].hashCode >= 0)
{
newSlots[newIndex] = _slots[i];
// rehash
int bucket = newSlots[newIndex].hashCode % newSize;
newSlots[newIndex].next = newBuckets[bucket] - 1;
newBuckets[bucket] = newIndex + 1;
newIndex++;
}
}
Debug.Assert(newSlots.Length <= _slots.Length, "capacity increased after TrimExcess");
_lastIndex = newIndex;
_slots = newSlots;
_buckets = newBuckets;
_freeList = -1;
}
}
#endregion
#region Helper methods
/// <summary>
/// Initializes buckets and slots arrays. Uses suggested capacity by finding next prime
/// greater than or equal to capacity.
/// </summary>
/// <param name="capacity"></param>
private void Initialize(int capacity)
{
Debug.Assert(_buckets == null, "Initialize was called but m_buckets was non-null");
int size = HashHelpers.GetPrime(capacity);
_buckets = new int[size];
_slots = new Slot[size];
}
/// <summary>
/// Expand to new capacity. New capacity is next prime greater than or equal to suggested
/// size. This is called when the underlying array is filled. This performs no
/// defragmentation, allowing faster execution; note that this is reasonable since
/// AddEvenIfPresent attempts to insert new elements in re-opened spots.
/// </summary>
private void IncreaseCapacity()
{
Debug.Assert(_buckets != null, "IncreaseCapacity called on a set with no elements");
int newSize = HashHelpers.ExpandPrime(_count);
if (newSize <= _count)
{
throw new ArgumentException("newSize");
}
// Able to increase capacity; copy elements to larger array and rehash
Slot[] newSlots = new Slot[newSize];
if (_slots != null)
{
Array.Copy(_slots, 0, newSlots, 0, _lastIndex);
}
int[] newBuckets = new int[newSize];
for (int i = 0; i < _lastIndex; i++)
{
int bucket = newSlots[i].hashCode % newSize;
newSlots[i].next = newBuckets[bucket] - 1;
newBuckets[bucket] = i + 1;
}
_slots = newSlots;
_buckets = newBuckets;
}
/// <summary>
/// Adds value to HashSet if not contained already
/// Returns true if added and false if already present
/// ** MSBUILD: Modified so that it DOES add even if present. It will return false in that case, though.**
/// </summary>
/// <param name="value">value to find</param>
/// <returns></returns>
private bool AddEvenIfPresent(T value)
{
if (_readOnly)
{
ErrorUtilities.ThrowInvalidOperation("OM_NotSupportedReadOnlyCollection");
}
if (_buckets == null)
{
Initialize(0);
}
string key = value.Key;
int hashCode = InternalGetHashCode(key);
int bucket = hashCode % _buckets.Length;
for (int i = _buckets[hashCode % _buckets.Length] - 1; i >= 0; i = _slots[i].next)
{
if (_slots[i].hashCode == hashCode && _comparer.Equals(_slots[i].value.Key, key))
{
// NOTE: this must add EVEN IF it is already present,
// as it may be a different object with the same name,
// and we want "last wins" semantics
_slots[i].value = value;
return false;
}
}
int index;
if (_freeList >= 0)
{
index = _freeList;
_freeList = _slots[index].next;
}
else
{
if (_lastIndex == _slots.Length)
{
IncreaseCapacity();
// this will change during resize
bucket = hashCode % _buckets.Length;
}
index = _lastIndex;
_lastIndex++;
}
_slots[index].hashCode = hashCode;
_slots[index].value = value;
_slots[index].next = _buckets[bucket] - 1;
_buckets[bucket] = index + 1;
_count++;
_version++;
return true;
}
/// <summary>
/// Equality comparer against another of this type.
/// Compares entries by reference - not merely by using the comparer on the key
/// </summary>
internal bool EntriesAreReferenceEquals(RetrievableEntryHashSet<T> other)
{
if (Object.ReferenceEquals(this, other))
{
return true;
}
if (this.Count != other.Count)
{
return false;
}
T ours;
foreach (T element in other)
{
if (!TryGetValue(element.Key, out ours) || !Object.ReferenceEquals(element, ours))
{
return false;
}
}
return true;
}
/// <summary>
/// Copies this to an array. Used for DebugView
/// </summary>
/// <returns></returns>
internal T[] ToArray()
{
T[] newArray = new T[Count];
CopyTo(newArray);
return newArray;
}
private int InternalGetHashCode(string item, int index, int length)
{
// No need to check for null 'item' as we own all comparers
if (_constrainedComparer != null)
{
return _constrainedComparer.GetHashCode(item, index, length) & Lower31BitMask;
}
return InternalGetHashCode(item);
}
/// <summary>
/// Workaround Comparers that throw ArgumentNullException for GetHashCode(null).
/// </summary>
/// <param name="item"></param>
/// <returns>hash code</returns>
private int InternalGetHashCode(string item)
{
if (item == null)
{
return 0;
}
return _comparer.GetHashCode(item) & Lower31BitMask;
}
#endregion
// used for set checking operations (using enumerables) that rely on counting
internal struct ElementCount
{
internal int uniqueCount;
internal int unfoundCount;
}
internal struct Slot
{
internal int hashCode; // Lower 31 bits of hash code, -1 if unused
internal T value;
internal int next; // Index of next entry, -1 if last
}
#if !SILVERLIGHT
[Serializable()]
#if FEATURE_SECURITY_PERMISSIONS
[System.Security.Permissions.HostProtection(MayLeakOnAbort = true)]
#endif
#endif
public struct Enumerator : IEnumerator<T>, System.Collections.IEnumerator
{
private RetrievableEntryHashSet<T> _set;
private int _index;
private int _version;
private T _current;
internal Enumerator(RetrievableEntryHashSet<T> set)
{
_set = set;
_index = 0;
_version = set._version;
_current = default(T);
}
public void Dispose()
{
}
public bool MoveNext()
{
if (_version != _set._version)
{
throw new InvalidOperationException();
}
while (_index < _set._lastIndex)
{
if (_set._slots[_index].hashCode >= 0)
{
_current = _set._slots[_index].value;
_index++;
return true;
}
_index++;
}
_index = _set._lastIndex + 1;
_current = default(T);
return false;
}
public T Current
{
get
{
return _current;
}
}
Object System.Collections.IEnumerator.Current
{
get
{
if (_index == 0 || _index == _set._lastIndex + 1)
{
throw new InvalidOperationException();
}
return Current;
}
}
void System.Collections.IEnumerator.Reset()
{
if (_version != _set._version)
{
throw new InvalidOperationException();
}
_index = 0;
_current = default(T);
}
}
}
}
|