A Classic Geek: 2012

I like Mono, I'm OK with NHibernate, but recently I ran into a problem as I posted on StackOverflow. It seems Mono still hasn't gotten some kinks worked out of the HashSet<T> class, and this was a problem for me.

The error I was getting was a nice YSOD:

Server Error in '/' Application

Object reference not set to an instance of an object

Description: HTTP 500. Error processing request.

Stack Trace:

System.NullReferenceException: Object reference not set to an instance of an object
at FluentNHibernate.Visitors.DefaultMappingModelVisitor.Visit (FluentNHibernate.MappingModel.ColumnMapping columnMapping) [0x00000] in <filename unknown>:0
at FluentNHibernate.MappingModel.KeyMapping.AcceptVisitor (IMappingModelVisitor visitor) [0x00000] in <filename unknown>:0
at FluentNHibernate.Visitors.DefaultMappingModelVisitor.Visit (FluentNHibernate.MappingModel.KeyMapping keyMapping) [0x00000] in <filename unknown>:0
at FluentNHibernate.MappingModel.ClassBased.SubclassMapping.AcceptVisitor (IMappingModelVisitor visitor) [0x00000] in <filename unknown>:0
at FluentNHibernate.Visitors.DefaultMappingModelVisitor.Visit (FluentNHibernate.MappingModel.ClassBased.SubclassMapping subclassMapping) [0x00000] in <filename unknown>:0
at FluentNHibernate.MappingModel.ClassBased.ClassMappingBase.AcceptVisitor (IMappingModelVisitor visitor) [0x00000] in <filename unknown>:0
at FluentNHibernate.MappingModel.ClassBased.ClassMapping.AcceptVisitor (IMappingModelVisitor visitor) [0x00000] in <filename unknown>:0
at FluentNHibernate.Visitors.DefaultMappingModelVisitor.Visit (FluentNHibernate.MappingModel.ClassBased.ClassMapping classMapping) [0x00000] in <filename unknown>:0
at FluentNHibernate.MappingModel.HibernateMapping.AcceptVisitor (IMappingModelVisitor visitor) [0x00000] in <filename unknown>:0
at FluentNHibernate.Visitors.DefaultMappingModelVisitor.<Visit>b__0 (FluentNHibernate.MappingModel.HibernateMapping x) [0x00000] in <filename unknown>:0
at FluentNHibernate.Utils.CollectionExtensions.Each[HibernateMapping] (IEnumerable`1 enumerable, System.Action`1 each) [0x00000] in <filename unknown>:0
at FluentNHibernate.Visitors.DefaultMappingModelVisitor.Visit (IEnumerable`1 mappings) [0x00000] in <filename unknown>:0
at FluentNHibernate.PersistenceModel.ApplyVisitors (IEnumerable`1 mappings) [0x00000] in <filename unknown>:0
at FluentNHibernate.PersistenceModel.BuildMappings () [0x00000] in <filename unknown>:0
at FluentNHibernate.PersistenceModel.EnsureMappingsBuilt () [0x00000] in <filename unknown>:0
at FluentNHibernate.PersistenceModel.Configure (NHibernate.Cfg.Configuration cfg) [0x00000] in <filename unknown>:0
at FluentNHibernate.Cfg.MappingConfiguration.Apply (NHibernate.Cfg.Configuration cfg) [0x00000] in <filename unknown>:0
at FluentNHibernate.Cfg.FluentConfiguration.BuildConfiguration () [0x00000] in <filename unknown>:0
Version information: Mono Runtime Version: 2.10.8.1 (Debian 2.10.8.1-1ubuntu2.2); ASP.NET Version: 4.0.30319.1

After hours of research (and essentially branching FluentNHibernate) I was able to fix this error. This occurs because there is a bug in Mono that does not implement the `HashSet<T>` properly. When FluentNHibernate uses the improperly implemented class, the hashset returns a null instead of a value. (As per this)

What I ended up doing (and yes, this is a kludge) is I implemented a `HashTable<T>` class using (I assume reflected) .NET 4.0 source code of the `HashSet<T>` and replaced the implementations of the `HashSet<T>` with this new class. I downloaded the source of FluentNHibernate from here and added a folder called Sub, then put the following classes into the folder:

using System.Diagnostics;

using System.Diagnostics.CodeAnalysis;

using System.Runtime.Serialization;

using System.Security.Permissions;

using Iesi.Collections.Generic;

namespace System.Collections.Generic

{

/// <summary>

/// Implementation notes:

/// This uses an array-based implementation similar to Dictionary<T>, 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 HashTable. Note that checking that it's a HashTable alone doesn't suffice; we

/// also have to check that the HashTable 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 HashTable using the same equality comparer.

///

/// A HashTable 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.

/// </t></summary>

/// <typeparam name="T"></typeparam>

[Serializable()]

// [DebuggerTypeProxy(typeof(System.Collections.Generic.HashTableDebugView<>))]

[DebuggerDisplay("Count = {Count}")]

[System.Security.Permissions.HostProtection(MayLeakOnAbort = true)]

[SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix", Justification = "By design")]

public class HashTable<T> : ICollection<T>, ISerializable, IDeserializationCallback

{

// store lower 31 bits of hash code

private const int Lower31BitMask = 0x7FFFFFFF;

// factor used to increase HashTable capacity

private const int GrowthFactor = 2;

// cutoff point, above which we won't do stackallocs. This corresponds to 100 integers.

private const int StackAllocThreshold = 100;

// when constructing a HashTable 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 HashTable 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[] m_buckets;

private Slot[] m_slots;

private int m_count;

private int m_lastIndex;

private int m_freeList;

private IEqualityComparer<T> m_comparer;

private int m_version;

// temporary variable needed during deserialization

private SerializationInfo m_siInfo;

#region Constructors

public HashTable()

: this(EqualityComparer<T>.Default) { }

public HashTable(IEqualityComparer<T> comparer)

{

if (comparer == null)

{

comparer = EqualityComparer<T>.Default;

}

this.m_comparer = comparer;

m_lastIndex = 0;

m_count = 0;

m_freeList = -1;

m_version = 0;

}

public HashTable(IEnumerable<T> collection)

: this(collection, EqualityComparer<T>.Default) { }

/// <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>

/// <param name="collection">

/// <param name="comparer">

public HashTable(IEnumerable<T> collection, IEqualityComparer<T> comparer)

: this(comparer)

{

if (collection == null)

{

throw new ArgumentNullException("collection");

}

// to avoid excess resizes, first set size based on collection's count. Collection

// may contain duplicates, so call TrimExcess if resulting HashTable 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 ((m_count == 0 && m_slots.Length > HashHelpers.GetMinPrime()) ||

(m_count > 0 && m_slots.Length / m_count > ShrinkThreshold))

{

TrimExcess();

}

protected HashTable(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.

m_siInfo = info;

}

#endregion

#region ICollection<T> methods

/// <summary>

/// Add item to this HashTable. This is the explicit implementation of the ICollection<T>

/// interface. The other Add method returns bool indicating whether item was added.

/// </t></summary>

/// <param name="item">item to add

void ICollection<T>.Add(T item)

{

AddIfNotPresent(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 (m_lastIndex > 0)

{

Debug.Assert(m_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(m_slots, 0, m_lastIndex);

Array.Clear(m_buckets, 0, m_buckets.Length);

m_lastIndex = 0;

m_count = 0;

m_freeList = -1;

}

m_version++;

}

/// <summary>

/// Checks if this HashTable contains the item

/// </summary>

/// <param name="item">item to check for containment

/// <returns>true if item contained; false if not</returns>

public bool Contains(T item)

{

if (m_buckets != null)

{

int hashCode = InternalGetHashCode(item);

// see note at "HashTable" level describing why "- 1" appears in for loop

for (int i = m_buckets[hashCode % m_buckets.Length] - 1; i >= 0; i = m_slots[i].next)

{

if (m_slots[i].hashCode == hashCode && m_comparer.Equals(m_slots[i].value, item))

{

return true;

}

// either m_buckets is null or wasn't found

return false;

}

/// <summary>

/// Copy items in this HashTable to array, starting at arrayIndex

/// </summary>

/// <param name="array">array to add items to

/// <param name="arrayIndex">index to start at

public void CopyTo(T[] array, int arrayIndex)

{

CopyTo(array, arrayIndex, m_count);

}

/// <summary>

/// Remove item from this HashTable

/// </summary>

/// <param name="item">item to remove

/// <returns>true if removed; false if not (i.e. if the item wasn't in the HashTable)</returns>

public bool Remove(T item)

{

if (m_buckets != null)

{

int hashCode = InternalGetHashCode(item);

int bucket = hashCode % m_buckets.Length;

int last = -1;

for (int i = m_buckets[bucket] - 1; i >= 0; last = i, i = m_slots[i].next)

{

if (m_slots[i].hashCode == hashCode && m_comparer.Equals(m_slots[i].value, item))

{

if (last < 0)

{

// first iteration; update buckets

m_buckets[bucket] = m_slots[i].next + 1;

}

else

{

// subsequent iterations; update 'next' pointers

m_slots[last].next = m_slots[i].next;

}

m_slots[i].hashCode = -1;

m_slots[i].value = default(T);

m_slots[i].next = m_freeList;

m_count--;

m_version++;

if (m_count == 0)

{

m_lastIndex = 0;

m_freeList = -1;

}

else

{

m_freeList = i;

}

return true;

}

// either m_buckets is null or wasn't found

return false;

}

/// <summary>

/// Number of elements in this HashTable

/// </summary>

public int Count

{

get { return m_count; }

}

/// <summary>

/// Whether this is readonly

/// </summary>

bool ICollection<T>.IsReadOnly

{

get { return false; }

}

#endregion

#region IEnumerable methods

public Enumerator GetEnumerator()

{

return new Enumerator(this);

}

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)]

public virtual void GetObjectData(SerializationInfo info, StreamingContext context)

{

if (info == null)

{

throw new ArgumentNullException("info");

}

// need to serialize version to avoid problems with serializing while enumerating

info.AddValue(VersionName, m_version);

info.AddValue(ComparerName, m_comparer, typeof(IEqualityComparer<T>));

info.AddValue(CapacityName, m_buckets == null ? 0 : m_buckets.Length);

if (m_buckets != null)

{

T[] array = new T[m_count];

CopyTo(array);

info.AddValue(ElementsName, array, typeof(T[]));

}

#endregion

#region IDeserializationCallback methods

public virtual void OnDeserialization(Object sender)

{

if (m_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 = m_siInfo.GetInt32(CapacityName);

m_comparer = (IEqualityComparer<T>)m_siInfo.GetValue(ComparerName, typeof(IEqualityComparer<T>));

m_freeList = -1;

if (capacity != 0)

{

m_buckets = new int[capacity];

m_slots = new Slot[capacity];

T[] array = (T[])m_siInfo.GetValue(ElementsName, typeof(T[]));

if (array == null)

{

throw new SerializationException(SR.GetString(SR.Serialization_MissingKeys));

}

// there are no resizes here because we already set capacity above

for (int i = 0; i < array.Length; i++)

{

AddIfNotPresent(array[i]);

}

else

{

m_buckets = null;

}

m_version = m_siInfo.GetInt32(VersionName);

m_siInfo = null;

}

#endregion

#region HashTable methods

/// <summary>

/// Add item to this HashTable. Returns bool indicating whether item was added (won't be

/// added if already present)

/// </summary>

/// <param name="item">

/// <returns>true if added, false if already present</returns>

public bool Add(T item)

{

return AddIfNotPresent(item);

}

/// <summary>

/// Take the union of this HashTable 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

public void UnionWith(IEnumerable<T> other)

{

if (other == null)

{

throw new ArgumentNullException("other");

}

foreach (T item in other)

{

AddIfNotPresent(item);

}

/// <summary>

/// Takes the intersection of this set with other. Modifies this set.

///

/// Implementation Notes:

/// We get better perf if other is a HashTable using same equality comparer, because we

/// get constant contains check in other. Resulting cost is O(n1) to iterate over this.

///

/// If we can't go above route, iterate over the other and mark intersection by checking

/// contains in this. Then loop over and delete any unmarked elements. Total cost is n2+n1.

///

/// Attempts to return early based on counts alone, using the property that the

/// intersection of anything with the empty set is the empty set.

/// </summary>

/// <param name="other">enumerable with items to add

// <securitykernel critical="True" ring="1">

// <referencescritical name="Method: IntersectWithEnumerable(IEnumerable`1<T>):Void" ring="1">

// </referencescritical></securitykernel>

[System.Security.SecurityCritical]

public void IntersectWith(IEnumerable<T> other)

{

if (other == null)

{

throw new ArgumentNullException("other");

}

// intersection of anything with empty set is empty set, so return if count is 0

if (m_count == 0)

{

return;

}

// if other is empty, intersection is empty set; remove all elements and we're done

// can only figure this out if implements ICollection<T>. (IEnumerable<T> has no count)

ICollection<T> otherAsCollection = other as ICollection<T>;

if (otherAsCollection != null)

{

if (otherAsCollection.Count == 0)

{

Clear();

return;

}

HashTable<T> otherAsSet = other as HashTable<T>;

// faster if other is a HashTable using same equality comparer; so check

// that other is a HashTable using the same equality comparer.

if (otherAsSet != null && AreEqualityComparersEqual(this, otherAsSet))

{

IntersectWithHashTableWithSameEC(otherAsSet);

return;

}

IntersectWithEnumerable(other);

}

/// <summary>

/// Remove items in other from this set. Modifies this set.

/// </summary>

/// <param name="other">enumerable with items to remove

public void ExceptWith(IEnumerable<T> other)

{

if (other == null)

{

throw new ArgumentNullException("other");

}

// this is already the enpty set; return

if (m_count == 0)

{

return;

}

// special case if other is this; a set minus itself is the empty set

if (other == this)

{

Clear();

return;

}

// remove every element in other from this

foreach (T element in other)

{

Remove(element);

}

/// <summary>

/// Takes symmetric difference (XOR) with other and this set. Modifies this set.

/// </summary>

/// <param name="other">enumerable with items to XOR

// <securitykernel critical="True" ring="1">

// <referencescritical name="Method: SymmetricExceptWithEnumerable(IEnumerable`1<T>):Void" ring="1">

// </referencescritical></securitykernel>

[System.Security.SecurityCritical]

public void SymmetricExceptWith(IEnumerable<T> other)

{

if (other == null)

{

throw new ArgumentNullException("other");

}

// if set is empty, then symmetric difference is other

if (m_count == 0)

{

UnionWith(other);

return;

}

// special case this; the symmetric difference of a set with itself is the empty set

if (other == this)

{

Clear();

return;

}

HashTable<T> otherAsSet = other as HashTable<T>;

// If other is a HashTable, it has unique elements according to its equality comparer,

// but if they're using different equality comparers, then assumption of uniqueness

// will fail. So first check if other is a HashTable using the same equality comparer;

// symmetric except is a lot faster and avoids bit array allocations if we can assume

// uniqueness

if (otherAsSet != null && AreEqualityComparersEqual(this, otherAsSet))

{

SymmetricExceptWithUniqueHashTable(otherAsSet);

}

else

{

SymmetricExceptWithEnumerable(other);

}

/// <summary>

/// Checks if this is a subset of other.

///

/// Implementation Notes:

/// The following properties are used up-front to avoid element-wise checks:

/// 1. If this is the empty set, then it's a subset of anything, including the empty set

/// 2. If other has unique elements according to this equality comparer, and this has more

/// elements than other, then it can't be a subset.

///

/// Furthermore, if other is a HashTable using the same equality comparer, we can use a

/// faster element-wise check.

/// </summary>

/// <param name="other">

/// <returns>true if this is a subset of other; false if not</returns>

// <securitykernel critical="True" ring="1">

// <referencescritical name="Method: CheckUniqueAndUnfoundElements(IEnumerable`1<T>, Boolean):ElementCount" ring="1">

// </referencescritical></securitykernel>

[System.Security.SecurityCritical]

public bool IsSubsetOf(IEnumerable<T> other)

{

if (other == null)

{

throw new ArgumentNullException("other");

}

// The empty set is a subset of any set

if (m_count == 0)

{

return true;

}

HashTable<T> otherAsSet = other as HashTable<T>;

// faster if other has unique elements according to this equality comparer; so check

// that other is a HashTable using the same equality comparer.

if (otherAsSet != null && AreEqualityComparersEqual(this, otherAsSet))

{

// if this has more elements then it can't be a subset

if (m_count > otherAsSet.Count)

{

return false;

}

// already checked that we're using same equality comparer. simply check that

// each element in this is contained in other.

return IsSubsetOfHashTableWithSameEC(otherAsSet);

}

else

{

ElementCount result = CheckUniqueAndUnfoundElements(other, false);

return (result.uniqueCount == m_count && result.unfoundCount >= 0);

}

/// <summary>

/// Checks if this is a proper subset of other (i.e. strictly contained in)

///

/// Implementation Notes:

/// The following properties are used up-front to avoid element-wise checks:

/// 1. If this is the empty set, then it's a proper subset of a set that contains at least

/// one element, but it's not a proper subset of the empty set.

/// 2. If other has unique elements according to this equality comparer, and this has >=

/// the number of elements in other, then this can't be a proper subset.

///

/// Furthermore, if other is a HashTable using the same equality comparer, we can use a

/// faster element-wise check.

/// </summary>

/// <param name="other">

/// <returns>true if this is a proper subset of other; false if not</returns>

// <securitykernel critical="True" ring="1">

// <referencescritical name="Method: CheckUniqueAndUnfoundElements(IEnumerable`1<T>, Boolean):ElementCount" ring="1">

// </referencescritical></securitykernel>

[System.Security.SecurityCritical]

public bool IsProperSubsetOf(IEnumerable<T> other)

{

if (other == null)

{

throw new ArgumentNullException("other");

}

ICollection<T> otherAsCollection = other as ICollection<T>;

if (otherAsCollection != null)

{

// the empty set is a proper subset of anything but the empty set

if (m_count == 0)

{

return otherAsCollection.Count > 0;

}

HashTable<T> otherAsSet = other as HashTable<T>;

// faster if other is a HashTable (and we're using same equality comparer)

if (otherAsSet != null && AreEqualityComparersEqual(this, otherAsSet))

{

if (m_count >= otherAsSet.Count)

{

return false;

}

// this has strictly less than number of items in other, so the following

// check suffices for proper subset.

return IsSubsetOfHashTableWithSameEC(otherAsSet);

}

ElementCount result = CheckUniqueAndUnfoundElements(other, false);

return (result.uniqueCount == m_count && result.unfoundCount > 0);

}

/// <summary>

/// Checks if this is a superset of other

///

/// Implementation Notes:

/// The following properties are used up-front to avoid element-wise checks:

/// 1. If other has no elements (it's the empty set), then this is a superset, even if this

/// is also the empty set.

/// 2. If other has unique elements according to this equality comparer, and this has less

/// than the number of elements in other, then this can't be a superset

///

/// </summary>

/// <param name="other">

/// <returns>true if this is a superset of other; false if not</returns>

public bool IsSupersetOf(IEnumerable<T> other)

{

if (other == null)

{

throw new ArgumentNullException("other");

}

// try to fall out early based on counts

ICollection<T> otherAsCollection = other as ICollection<T>;

if (otherAsCollection != null)

{

// if other is the empty set then this is a superset

if (otherAsCollection.Count == 0)

{

return true;

}

HashTable<T> otherAsSet = other as HashTable<T>;

// try to compare based on counts alone if other is a HashTable with

// same equality comparer

if (otherAsSet != null && AreEqualityComparersEqual(this, otherAsSet))

{

if (otherAsSet.Count > m_count)

{

return false;

}

return ContainsAllElements(other);

}

/// <summary>

/// Checks if this is a proper superset of other (i.e. other strictly contained in this)

///

/// Implementation Notes:

/// This is slightly more complicated than above because we have to keep track if there

/// was at least one element not contained in other.

///

/// The following properties are used up-front to avoid element-wise checks:

/// 1. If this is the empty set, then it can't be a proper superset of any set, even if

/// other is the empty set.

/// 2. If other is an empty set and this contains at least 1 element, then this is a proper

/// superset.

/// 3. If other has unique elements according to this equality comparer, and other's count

/// is greater than or equal to this count, then this can't be a proper superset

///

/// Furthermore, if other has unique elements according to this equality comparer, we can

/// use a faster element-wise check.

/// </summary>

/// <param name="other">

/// <returns>true if this is a proper superset of other; false if not</returns>

// <securitykernel critical="True" ring="1">

// <referencescritical name="Method: CheckUniqueAndUnfoundElements(IEnumerable`1<T>, Boolean):ElementCount" ring="1">

// </referencescritical></securitykernel>

[System.Security.SecurityCritical]

public bool IsProperSupersetOf(IEnumerable<T> other)

{

if (other == null)

{

throw new ArgumentNullException("other");

}

// the empty set isn't a proper superset of any set.

if (m_count == 0)

{

return false;

}

ICollection<T> otherAsCollection = other as ICollection<T>;

if (otherAsCollection != null)

{

// if other is the empty set then this is a superset

if (otherAsCollection.Count == 0)

{

// note that this has at least one element, based on above check

return true;

}

HashTable<T> otherAsSet = other as HashTable<T>;

// faster if other is a HashTable with the same equality comparer

if (otherAsSet != null && AreEqualityComparersEqual(this, otherAsSet))

{

if (otherAsSet.Count >= m_count)

{

return false;

}

// now perform element check

return ContainsAllElements(otherAsSet);

}

// couldn't fall out in the above cases; do it the long way

ElementCount result = CheckUniqueAndUnfoundElements(other, true);

return (result.uniqueCount < m_count && result.unfoundCount == 0);

}

/// <summary>

/// Checks if this set overlaps other (i.e. they share at least one item)

/// </summary>

/// <param name="other">

/// <returns>true if these have at least one common element; false if disjoint</returns>

public bool Overlaps(IEnumerable<T> other)

{

if (other == null)

{

throw new ArgumentNullException("other");

}

if (m_count == 0)

{

return false;

}

foreach (T element in other)

{

if (Contains(element))

{

return true;

}

return false;

}

/// <summary>

/// Checks if this and other contain the same elements. This is set equality:

/// duplicates and order are ignored

/// </summary>

/// <param name="other">

/// <returns></returns>

// <securitykernel critical="True" ring="1">

// <referencescritical name="Method: CheckUniqueAndUnfoundElements(IEnumerable`1<T>, Boolean):ElementCount" ring="1">

// </referencescritical></securitykernel>

[System.Security.SecurityCritical]

public bool SetEquals(IEnumerable<T> other)

{

if (other == null)

{

throw new ArgumentNullException("other");

}

HashTable<T> otherAsSet = other as HashTable<T>;

// faster if other is a HashTable and we're using same equality comparer

if (otherAsSet != null && AreEqualityComparersEqual(this, otherAsSet))

{

// attempt to return early: since both contain unique elements, if they have

// different counts, then they can't be equal

if (m_count != otherAsSet.Count)

{

return false;

}

// already confirmed that the sets have the same number of distinct elements, so if

// one is a superset of the other then they must be equal

return ContainsAllElements(otherAsSet);

}

else

{

ICollection<T> otherAsCollection = other as ICollection<T>;

if (otherAsCollection != null)

{

// if this count is 0 but other contains at least one element, they can't be equal

if (m_count == 0 && otherAsCollection.Count > 0)

{

return false;

}

ElementCount result = CheckUniqueAndUnfoundElements(other, true);

return (result.uniqueCount == m_count && result.unfoundCount == 0);

}

public void CopyTo(T[] array) { CopyTo(array, 0, m_count); }

public void CopyTo(T[] array, int arrayIndex, int count)

{

if (array == null)

{

throw new ArgumentNullException("array");

}

// check array index valid index into array

if (arrayIndex < 0)

{

throw new ArgumentOutOfRangeException("arrayIndex", SR.GetString(SR.ArgumentOutOfRange_NeedNonNegNum));

}

// also throw if count less than 0

if (count < 0)

{

throw new ArgumentOutOfRangeException("count", SR.GetString(SR.ArgumentOutOfRange_NeedNonNegNum));

}

// 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(SR.GetString(SR.Arg_ArrayPlusOffTooSmall));

}

int numCopied = 0;

for (int i = 0; i < m_lastIndex && numCopied < count; i++)

{

if (m_slots[i].hashCode >= 0)

{

array[arrayIndex + numCopied] = m_slots[i].value;

numCopied++;

}

/// <summary>

/// Remove elements that match specified predicate. Returns the number of elements removed

/// </summary>

/// <param name="match">

/// <returns></returns>

public int RemoveWhere(Predicate<T> match)

{

if (match == null)

{

throw new ArgumentNullException("match");

}

int numRemoved = 0;

for (int i = 0; i < m_lastIndex; i++)

{

if (m_slots[i].hashCode >= 0)

{

// cache value in case delegate removes it

T value = m_slots[i].value;

if (match(value))

{

// check again that remove actually removed it

if (Remove(value))

{

numRemoved++;

}

return numRemoved;

}

/// <summary>

/// Gets the IEqualityComparer that is used to determine equality of keys for

/// the HashTable.

/// </summary>

public IEqualityComparer<T> Comparer

{

get

{

return m_comparer;

}

/// <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(m_count >= 0, "m_count is negative");

if (m_count == 0)

{

// if count is zero, clear references

m_buckets = null;

m_slots = null;

m_version++;

}

else

{

Debug.Assert(m_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(m_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 < m_lastIndex; i++)

{

if (m_slots[i].hashCode >= 0)

{

newSlots[newIndex] = m_slots[i];

// rehash

int bucket = newSlots[newIndex].hashCode % newSize;

newSlots[newIndex].next = newBuckets[bucket] - 1;

newBuckets[bucket] = newIndex + 1;

newIndex++;

}

Debug.Assert(newSlots.Length <= m_slots.Length, "capacity increased after TrimExcess");

m_lastIndex = newIndex;

m_slots = newSlots;

m_buckets = newBuckets;

m_freeList = -1;

}

/// <summary>

/// Used for deep equality of HashTable testing

/// </summary>

/// <returns></returns>

public static IEqualityComparer<HashTable<T>> CreateSetComparer()

{

return new HashTableEqualityComparer<T>();

}

#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">

private void Initialize(int capacity)

{

Debug.Assert(m_buckets == null, "Initialize was called but m_buckets was non-null");

int size = HashHelpers.GetPrime(capacity);

m_buckets = new int[size];

m_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

/// AddIfNotPresent attempts to insert new elements in re-opened spots.

/// </summary>

/// <param name="sizeSuggestion">

private void IncreaseCapacity()

{

Debug.Assert(m_buckets != null, "IncreaseCapacity called on a set with no elements");

// Handle overflow conditions. Try to expand capacity by GrowthFactor. If that causes

// overflow, use size suggestion of m_count and see if HashHelpers returns a value

// greater than that. If not, capacity can't be increased so throw capacity overflow

// exception.

int sizeSuggestion = unchecked(m_count * GrowthFactor);

if (sizeSuggestion < 0)

{

sizeSuggestion = m_count;

}

int newSize = HashHelpers.GetPrime(sizeSuggestion);

if (newSize <= m_count)

{

throw new ArgumentException(SR.GetString(SR.Arg_HSCapacityOverflow));

}

// Able to increase capacity; copy elements to larger array and rehash

Slot[] newSlots = new Slot[newSize];

if (m_slots != null)

{

Array.Copy(m_slots, 0, newSlots, 0, m_lastIndex);

}

int[] newBuckets = new int[newSize];

for (int i = 0; i < m_lastIndex; i++)

{

int bucket = newSlots[i].hashCode % newSize;

newSlots[i].next = newBuckets[bucket] - 1;

newBuckets[bucket] = i + 1;

}

m_slots = newSlots;

m_buckets = newBuckets;

}

/// <summary>

/// Adds value to HashTable if not contained already

/// Returns true if added and false if already present

/// </summary>

/// <param name="value">value to find

/// <returns></returns>

private bool AddIfNotPresent(T value)

{

if (m_buckets == null)

{

Initialize(0);

}

int hashCode = InternalGetHashCode(value);

int bucket = hashCode % m_buckets.Length;

for (int i = m_buckets[hashCode % m_buckets.Length] - 1; i >= 0; i = m_slots[i].next)

{

if (m_slots[i].hashCode == hashCode && m_comparer.Equals(m_slots[i].value, value))

{

return false;

}

int index;

if (m_freeList >= 0)

{

index = m_freeList;

m_freeList = m_slots[index].next;

}

else

{

if (m_lastIndex == m_slots.Length)

{

IncreaseCapacity();

// this will change during resize

bucket = hashCode % m_buckets.Length;

}

index = m_lastIndex;

m_lastIndex++;

}

m_slots[index].hashCode = hashCode;

m_slots[index].value = value;

m_slots[index].next = m_buckets[bucket] - 1;

m_buckets[bucket] = index + 1;

m_count++;

m_version++;

return true;

}

/// <summary>

/// Checks if this contains of other's elements. Iterates over other's elements and

/// returns false as soon as it finds an element in other that's not in this.

/// Used by SupersetOf, ProperSupersetOf, and SetEquals.

/// </summary>

/// <param name="other">

/// <returns></returns>

private bool ContainsAllElements(IEnumerable<T> other)

{

foreach (T element in other)

{

if (!Contains(element))

{

return false;

}

return true;

}

/// <summary>

/// Implementation Notes:

/// If other is a HashTable and is using same equality comparer, then checking subset is

/// faster. Simply check that each element in this is in other.

///

/// Note: if other doesn't use same equality comparer, then Contains check is invalid,

/// which is why callers must take are of this.

///

/// If callers are concerned about whether this is a proper subset, they take care of that.

///

/// </summary>

/// <param name="other">

/// <returns></returns>

private bool IsSubsetOfHashTableWithSameEC(HashTable<T> other)

{

foreach (T item in this)

{

if (!other.Contains(item))

{

return false;

}

return true;

}

/// <summary>

/// If other is a HashTable that uses same equality comparer, intersect is much faster

/// because we can use other's Contains

/// </summary>

/// <param name="other">

private void IntersectWithHashTableWithSameEC(HashTable<T> other)

{

for (int i = 0; i < m_lastIndex; i++)

{

if (m_slots[i].hashCode >= 0)

{

T item = m_slots[i].value;

if (!other.Contains(item))

{

Remove(item);

}

/// <summary>

/// Iterate over other. If contained in this, mark an element in bit array corresponding to

/// its position in m_slots. If anything is unmarked (in bit array), remove it.

///

/// This attempts to allocate on the stack, if below StackAllocThreshold.

/// </summary>

/// <param name="other">

// <securitykernel critical="True" ring="0">

// <usesunsafecode name="Local bitArrayPtr of type: Int32*">

// <referencescritical name="Method: BitHelper..ctor(System.Int32*,System.Int32)" ring="1">

// <referencescritical name="Method: BitHelper.MarkBit(System.Int32):System.Void" ring="1">

// <referencescritical name="Method: BitHelper.IsMarked(System.Int32):System.Boolean" ring="1">

// </referencescritical></referencescritical></referencescritical></usesunsafecode></securitykernel>

[System.Security.SecurityCritical]

private unsafe void IntersectWithEnumerable(IEnumerable<T> other)

{

Debug.Assert(m_buckets != null, "m_buckets shouldn't be null; callers should check first");

// keep track of current last index; don't want to move past the end of our bit array

// (could happen if another thread is modifying the collection)

int originalLastIndex = m_lastIndex;

int intArrayLength = BitHelper.ToIntArrayLength(originalLastIndex);

BitHelper bitHelper;

if (intArrayLength <= StackAllocThreshold)

{

int* bitArrayPtr = stackalloc int[intArrayLength];

bitHelper = new BitHelper(bitArrayPtr, intArrayLength);

}

else

{

int[] bitArray = new int[intArrayLength];

bitHelper = new BitHelper(bitArray, intArrayLength);

}

// mark if contains: find index of in slots array and mark corresponding element in bit array

foreach (T item in other)

{

int index = InternalIndexOf(item);

if (index >= 0)

{

bitHelper.MarkBit(index);

}

// if anything unmarked, remove it. Perf can be optimized here if BitHelper had a

// FindFirstUnmarked method.

for (int i = 0; i < originalLastIndex; i++)

{

if (m_slots[i].hashCode >= 0 && !bitHelper.IsMarked(i))

{

Remove(m_slots[i].value);

}

/// <summary>

/// Used internally by set operations which have to rely on bit array marking. This is like

/// Contains but returns index in slots array.

/// </summary>

/// <param name="item">

/// <returns></returns>

private int InternalIndexOf(T item)

{

Debug.Assert(m_buckets != null, "m_buckets was null; callers should check first");

int hashCode = InternalGetHashCode(item);

for (int i = m_buckets[hashCode % m_buckets.Length] - 1; i >= 0; i = m_slots[i].next)

{

if ((m_slots[i].hashCode) == hashCode && m_comparer.Equals(m_slots[i].value, item))

{

return i;

}

// wasn't found

return -1;

}

/// <summary>

/// if other is a set, we can assume it doesn't have duplicate elements, so use this

/// technique: if can't remove, then it wasn't present in this set, so add.

///

/// As with other methods, callers take care of ensuring that other is a HashTable using the

/// same equality comparer.

/// </summary>

/// <param name="other">

private void SymmetricExceptWithUniqueHashTable(HashTable<T> other)

{

foreach (T item in other)

{

if (!Remove(item))

{

AddIfNotPresent(item);

}

/// <summary>

/// Implementation notes:

///

/// Used for symmetric except when other isn't a HashTable. This is more tedious because

/// other may contain duplicates. HashTable technique could fail in these situations:

/// 1. Other has a duplicate that's not in this: HashTable technique would add then

/// remove it.

/// 2. Other has a duplicate that's in this: HashTable technique would remove then add it

/// back.

/// In general, its presence would be toggled each time it appears in other.

///

/// This technique uses bit marking to indicate whether to add/remove the item. If already

/// present in collection, it will get marked for deletion. If added from other, it will

/// get marked as something not to remove.

///

/// </summary>

/// <param name="other">

// <securitykernel critical="True" ring="0">

// <usesunsafecode name="Local itemsToRemovePtr of type: Int32*">

// <usesunsafecode name="Local itemsAddedFromOtherPtr of type: Int32*">

// <referencescritical name="Method: BitHelper..ctor(System.Int32*,System.Int32)" ring="1">

// <referencescritical name="Method: BitHelper.MarkBit(System.Int32):System.Void" ring="1">

// <referencescritical name="Method: BitHelper.IsMarked(System.Int32):System.Boolean" ring="1">

// </referencescritical></referencescritical></referencescritical></usesunsafecode></usesunsafecode></securitykernel>

[System.Security.SecurityCritical]

private unsafe void SymmetricExceptWithEnumerable(IEnumerable<T> other)

{

int originalLastIndex = m_lastIndex;

int intArrayLength = BitHelper.ToIntArrayLength(originalLastIndex);

BitHelper itemsToRemove;

BitHelper itemsAddedFromOther;

if (intArrayLength <= StackAllocThreshold / 2)

{

int* itemsToRemovePtr = stackalloc int[intArrayLength];

itemsToRemove = new BitHelper(itemsToRemovePtr, intArrayLength);

int* itemsAddedFromOtherPtr = stackalloc int[intArrayLength];

itemsAddedFromOther = new BitHelper(itemsAddedFromOtherPtr, intArrayLength);

}

else

{

int[] itemsToRemoveArray = new int[intArrayLength];

itemsToRemove = new BitHelper(itemsToRemoveArray, intArrayLength);

int[] itemsAddedFromOtherArray = new int[intArrayLength];

itemsAddedFromOther = new BitHelper(itemsAddedFromOtherArray, intArrayLength);

}

foreach (T item in other)

{

int location = 0;

bool added = AddOrGetLocation(item, out location);

if (added)

{

// wasn't already present in collection; flag it as something not to remove

// *NOTE* if location is out of range, we should ignore. BitHelper will

// detect that it's out of bounds and not try to mark it. But it's

// expected that location could be out of bounds because adding the item

// will increase m_lastIndex as soon as all the free spots are filled.

itemsAddedFromOther.MarkBit(location);

}

else

{

// already there...if not added from other, mark for remove.

// *NOTE* Even though BitHelper will check that location is in range, we want

// to check here. There's no point in checking items beyond originalLastIndex

// because they could not have been in the original collection

if (location < originalLastIndex && !itemsAddedFromOther.IsMarked(location))

{

itemsToRemove.MarkBit(location);

}

// if anything marked, remove it

for (int i = 0; i < originalLastIndex; i++)

{

if (itemsToRemove.IsMarked(i))

{

Remove(m_slots[i].value);

}

/// <summary>

/// Add if not already in HashTable. Returns an out param indicating index where added. This

/// is used by SymmetricExcept because it needs to know the following things:

/// - whether the item was already present in the collection or added from other

/// - where it's located (if already present, it will get marked for removal, otherwise

/// marked for keeping)

/// </summary>

/// <param name="value">

/// <param name="location">

/// <returns></returns>

private bool AddOrGetLocation(T value, out int location)

{

Debug.Assert(m_buckets != null, "m_buckets is null, callers should have checked");

int hashCode = InternalGetHashCode(value);

int bucket = hashCode % m_buckets.Length;

for (int i = m_buckets[hashCode % m_buckets.Length] - 1; i >= 0; i = m_slots[i].next)

{

if (m_slots[i].hashCode == hashCode && m_comparer.Equals(m_slots[i].value, value))

{

location = i;

return false; //already present

}

int index;

if (m_freeList >= 0)

{

index = m_freeList;

m_freeList = m_slots[index].next;

}

else

{

if (m_lastIndex == m_slots.Length)

{

IncreaseCapacity();

// this will change during resize

bucket = hashCode % m_buckets.Length;

}

index = m_lastIndex;

m_lastIndex++;

}

m_slots[index].hashCode = hashCode;

m_slots[index].value = value;

m_slots[index].next = m_buckets[bucket] - 1;

m_buckets[bucket] = index + 1;

m_count++;

m_version++;

location = index;

return true;

}

/// <summary>

/// Determines counts that can be used to determine equality, subset, and superset. This

/// is only used when other is an IEnumerable and not a HashTable. If other is a HashTable

/// these properties can be checked faster without use of marking because we can assume

/// other has no duplicates.

///

/// The following count checks are performed by callers:

/// 1. Equals: checks if unfoundCount = 0 and uniqueFoundCount = m_count; i.e. everything

/// in other is in this and everything in this is in other

/// 2. Subset: checks if unfoundCount >= 0 and uniqueFoundCount = m_count; i.e. other may

/// have elements not in this and everything in this is in other

/// 3. Proper subset: checks if unfoundCount > 0 and uniqueFoundCount = m_count; i.e

/// other must have at least one element not in this and everything in this is in other

/// 4. Proper superset: checks if unfound count = 0 and uniqueFoundCount strictly less

/// than m_count; i.e. everything in other was in this and this had at least one element

/// not contained in other.

///

/// An earlier implementation used delegates to perform these checks rather than returning

/// an ElementCount struct; however this was changed due to the perf overhead of delegates.

/// </summary>

/// <param name="other">

/// <param name="returnIfUnfound">Allows us to finish faster for equals and proper superset

/// because unfoundCount must be 0.

/// <returns></returns>

// <securitykernel critical="True" ring="0">

// <usesunsafecode name="Local bitArrayPtr of type: Int32*">

// <referencescritical name="Method: BitHelper..ctor(System.Int32*,System.Int32)" ring="1">

// <referencescritical name="Method: BitHelper.IsMarked(System.Int32):System.Boolean" ring="1">

// <referencescritical name="Method: BitHelper.MarkBit(System.Int32):System.Void" ring="1">

// </referencescritical></referencescritical></referencescritical></usesunsafecode></securitykernel>

[System.Security.SecurityCritical]

private unsafe ElementCount CheckUniqueAndUnfoundElements(IEnumerable<T> other, bool returnIfUnfound)

{

ElementCount result;

// need special case in case this has no elements.

if (m_count == 0)

{

int numElementsInOther = 0;

foreach (T item in other)

{

numElementsInOther++;

// break right away, all we want to know is whether other has 0 or 1 elements

break;

}

result.uniqueCount = 0;

result.unfoundCount = numElementsInOther;

return result;

}

Debug.Assert((m_buckets != null) && (m_count > 0), "m_buckets was null but count greater than 0");

int originalLastIndex = m_lastIndex;

int intArrayLength = BitHelper.ToIntArrayLength(originalLastIndex);

BitHelper bitHelper;

if (intArrayLength <= StackAllocThreshold)

{

int* bitArrayPtr = stackalloc int[intArrayLength];

bitHelper = new BitHelper(bitArrayPtr, intArrayLength);

}

else

{

int[] bitArray = new int[intArrayLength];

bitHelper = new BitHelper(bitArray, intArrayLength);

}

// count of items in other not found in this

int unfoundCount = 0;

// count of unique items in other found in this

int uniqueFoundCount = 0;

foreach (T item in other)

{

int index = InternalIndexOf(item);

if (index >= 0)

{

if (!bitHelper.IsMarked(index))

{

// item hasn't been seen yet

bitHelper.MarkBit(index);

uniqueFoundCount++;

}

else

{

unfoundCount++;

if (returnIfUnfound)

{

break;

}

result.uniqueCount = uniqueFoundCount;

result.unfoundCount = unfoundCount;

return result;

}

/// <summary>

/// Copies this to an array. Used for DebugView

/// </summary>

/// <returns></returns>

internal T[] ToArray()

{

T[] newArray = new T[Count];

CopyTo(newArray);

return newArray;

}

/// <summary>

/// Internal method used for HashTableEqualityComparer. Compares set1 and set2 according

/// to specified comparer.

///

/// Because items are hashed according to a specific equality comparer, we have to resort

/// to n^2 search if they're using different equality comparers.

/// </summary>

/// <param name="set1">

/// <param name="set2">

/// <param name="comparer">

/// <returns></returns>

internal static bool HashTableEquals(HashTable<T> set1, HashTable<T> set2, IEqualityComparer<T> comparer)

{

// handle null cases first

if (set1 == null)

{

return (set2 == null);

}

else if (set2 == null)

{

// set1 != null

return false;

}

// all comparers are the same; this is faster

if (AreEqualityComparersEqual(set1, set2))

{

if (set1.Count != set2.Count)

{

return false;

}

// suffices to check subset

foreach (T item in set2)

{

if (!set1.Contains(item))

{

return false;

}

return true;

}

else

{ // n^2 search because items are hashed according to their respective ECs

foreach (T set2Item in set2)

{

bool found = false;

foreach (T set1Item in set1)

{

if (comparer.Equals(set2Item, set1Item))

{

found = true;

break;

}

if (!found)

{

return false;

}

return true;

}

/// <summary>

/// Checks if equality comparers are equal. This is used for algorithms that can

/// speed up if it knows the other item has unique elements. I.e. if they're using

/// different equality comparers, then uniqueness assumption between sets break.

/// </summary>

/// <param name="set1">

/// <param name="set2">

/// <returns></returns>

private static bool AreEqualityComparersEqual(HashTable<T> set1, HashTable<T> set2)

{

return set1.Comparer.Equals(set2.Comparer);

}

/// <summary>

/// Workaround Comparers that throw ArgumentNullException for GetHashCode(null).

/// </summary>

/// <param name="item">

/// <returns>hash code</returns>

private int InternalGetHashCode(T item)

{

if (item == null)

{

return 0;

}

return m_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

}

[Serializable()]

[System.Security.Permissions.HostProtection(MayLeakOnAbort = true)]

public struct Enumerator : IEnumerator<T>, System.Collections.IEnumerator

{

private HashTable<T> set;

private int index;

private int version;

private T current;

internal Enumerator(HashTable<T> set)

{

this.set = set;

index = 0;

version = set.m_version;

current = default(T);

}

public void Dispose()

{

}

public bool MoveNext()

{

if (version != set.m_version)

{

throw new InvalidOperationException(SR.GetString(SR.InvalidOperation_EnumFailedVersion));

}

while (index < set.m_lastIndex)

{

if (set.m_slots[index].hashCode >= 0)

{

current = set.m_slots[index].value;

index++;

return true;

}

index++;

}

index = set.m_lastIndex + 1;

current = default(T);

return false;

}

public T Current

{

get

{

return current;

}

Object System.Collections.IEnumerator.Current

{

get

{

if (index == 0 || index == set.m_lastIndex + 1)

{

throw new InvalidOperationException(SR.GetString(SR.InvalidOperation_EnumOpCantHappen));

}

return Current;

}

void System.Collections.IEnumerator.Reset()

{

if (version != set.m_version)

{

throw new InvalidOperationException(SR.GetString(SR.InvalidOperation_EnumFailedVersion));

}

index = 0;

current = default(T);

}

using System.Diagnostics;

using System.Runtime.ConstrainedExecution;

namespace System.Collections.Generic

{

/// <summary>

/// Duplicated because internal to mscorlib

/// </summary>

internal static class HashHelpers

{

// Table of prime numbers to use as hash table sizes.

// The entry used for capacity is the smallest prime number in this array

// that is larger than twice the previous capacity.

internal static readonly int[] primes = {

3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,

1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,

17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,

187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,

1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369};

[ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]

internal static bool IsPrime(int candidate)

{

if ((candidate & 1) != 0)

{

int limit = (int)Math.Sqrt(candidate);

for (int divisor = 3; divisor <= limit; divisor += 2)

{

if ((candidate % divisor) == 0)

{

return false;

}

return true;

}

return (candidate == 2);

}

[ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]

internal static int GetPrime(int min)

{

Debug.Assert(min >= 0, "min less than zero; handle overflow checking before calling HashHelpers");

for (int i = 0; i < primes.Length; i++)

{

int prime = primes[i];

if (prime >= min)

{

return prime;

}

// Outside of our predefined table. Compute the hard way.

for (int i = (min | 1); i < Int32.MaxValue; i += 2)

{

if (IsPrime(i))

{

return i;

}

return min;

}

internal static int GetMinPrime()

{

return primes[0];

}

using System.Diagnostics;

namespace System.Collections.Generic {

/// <summary>

/// Debug view for HashTable

/// </summary>

/// <typeparam name="T"></typeparam>

internal class HashTableDebugView<T> {

private HashTable<T> Set;

public HashTableDebugView(HashTable<T> theSet) {

if (theSet == null) {

throw new ArgumentNullException("theSet");

}

this.Set = theSet;

}

[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]

public T[] Items {

get {

return Set.ToArray();

}

using System;

using System.Collections;

using System.Collections.Generic;

namespace System.Collections.Generic

{

/// <summary>

/// Equality comparer for HashTables of HashTables

/// </summary>

/// <typeparam name="T"></typeparam>

[Serializable()]

internal class HashTableEqualityComparer<T> : IEqualityComparer<HashTable<T>>

{

private IEqualityComparer<T> m_comparer;

public HashTableEqualityComparer()

{

m_comparer = EqualityComparer<T>.Default;

}

public HashTableEqualityComparer(IEqualityComparer<T> comparer)

{

if (comparer == null)

{

m_comparer = EqualityComparer<T>.Default;

}

else

{

m_comparer = comparer;

}

// using m_comparer to keep equals properties in tact; don't want to choose one of the comparers

public bool Equals(HashTable<T> x, HashTable<T> y)

{

return HashTable<T>.HashTableEquals(x, y, m_comparer);

}

public int GetHashCode(HashTable<T> obj)

{

int hashCode = 0;

if (obj != null)

{

foreach (T t in obj)

{

hashCode = hashCode ^ (m_comparer.GetHashCode(t) & 0x7FFFFFFF);

}

} // else returns hashcode of 0 for null HashTables

return hashCode;

}

// Equals method for the comparer itself.

public override bool Equals(Object obj)

{

HashTableEqualityComparer<T> comparer = obj as HashTableEqualityComparer<T>;

if (comparer == null)

{

return false;

}

return (this.m_comparer == comparer.m_comparer);

}

public override int GetHashCode()

{

return m_comparer.GetHashCode();

}

namespace System.Collections.Generic

{

public class SR

{

public static string ArgumentOutOfRange_NeedNonNegNum { get { return "ArgumentOutOfRange_NeedNonNegNum"; } }

public static string Arg_ArrayPlusOffTooSmall { get { return "Arg_ArrayPlusOffTooSmall"; } }

public static string Serialization_MissingKeys { get { return "Serialization_MissingKeys"; } }

public static string Arg_HSCapacityOverflow { get { return "Arg_HSCapacityOverflow"; } }

public static string InvalidOperation_EnumFailedVersion { get { return "InvalidOperation_EnumFailedVersion"; } }

public static string InvalidOperation_EnumOpCantHappen { get { return "InvalidOperation_EnumOpCantHappen"; } }

public static string GetString(object p)

{

return p.ToString();

}

using System;

using System.Collections;

using System.Text;

namespace System.Collections.Generic

{

/// <summary>

/// ABOUT:

/// Helps with operations that rely on bit marking to indicate whether an item in the

/// collection should be added, removed, visited already, etc.

///

/// BitHelper doesn't allocate the array; you must pass in an array or ints allocated on the

/// stack or heap. ToIntArrayLength() tells you the int array size you must allocate.

///

/// USAGE:

/// Suppose you need to represent a bit array of length (i.e. logical bit array length)

/// BIT_ARRAY_LENGTH. Then this is the suggested way to instantiate BitHelper:

/// ****************************************************************************

/// int intArrayLength = BitHelper.ToIntArrayLength(BIT_ARRAY_LENGTH);

/// BitHelper bitHelper;

/// if (intArrayLength less than stack alloc threshold)

/// int* m_arrayPtr = stackalloc int[intArrayLength];

/// bitHelper = new BitHelper(m_arrayPtr, intArrayLength);

/// else

/// int[] m_arrayPtr = new int[intArrayLength];

/// bitHelper = new BitHelper(m_arrayPtr, intArrayLength);

/// ***************************************************************************

///

/// IMPORTANT:

/// The second ctor args, length, should be specified as the length of the int array, not

/// the logical bit array. Because length is used for bounds checking into the int array,

/// it's especially important to get this correct for the stackalloc version. See the code

/// samples above; this is the value gotten from ToIntArrayLength().

///

/// The length ctor argument is the only exception; for other methods -- MarkBit and

/// IsMarked -- pass in values as indices into the logical bit array, and it will be mapped

/// to the position within the array of ints.

///

///</summary>

unsafe internal class BitHelper

{ // should not be serialized

private const byte MarkedBitFlag = 1;

private const byte IntSize = 32;

// m_length of underlying int array (not logical bit array)

private int m_length;

// ptr to stack alloc'd array of ints

private int* m_arrayPtr;

// array of ints

private int[] m_array;

// whether to operate on stack alloc'd or heap alloc'd array

private bool useStackAlloc;

/// <summary>

/// Instantiates a BitHelper with a heap alloc'd array of ints

/// </summary>

/// <param name="bitArray">int array to hold bits

/// <param name="length">length of int array

// <securitykernel critical="True" ring="0">

// <usesunsafecode name="Field: m_arrayPtr">

// <usesunsafecode name="Parameter bitArrayPtr of type: Int32*">

// </usesunsafecode></usesunsafecode></securitykernel>

[System.Security.SecurityCritical]

internal BitHelper(int* bitArrayPtr, int length)

{

this.m_arrayPtr = bitArrayPtr;

this.m_length = length;

useStackAlloc = true;

}

/// <summary>

/// Instantiates a BitHelper with a heap alloc'd array of ints

/// </summary>

/// <param name="bitArray">int array to hold bits

/// <param name="length">length of int array

internal BitHelper(int[] bitArray, int length)

{

this.m_array = bitArray;

this.m_length = length;

}

/// <summary>

/// Mark bit at specified position

/// </summary>

/// <param name="bitPosition">

// <securitykernel critical="True" ring="0">

// <usesunsafecode name="Field: m_arrayPtr">

// </usesunsafecode></securitykernel>

[System.Security.SecurityCritical]

internal unsafe void MarkBit(int bitPosition)

{

if (useStackAlloc)

{

int bitArrayIndex = bitPosition / IntSize;

if (bitArrayIndex < m_length && bitArrayIndex >= 0)

{

m_arrayPtr[bitArrayIndex] |= (MarkedBitFlag << (bitPosition % IntSize));

}

else

{

int bitArrayIndex = bitPosition / IntSize;

if (bitArrayIndex < m_length && bitArrayIndex >= 0)

{

m_array[bitArrayIndex] |= (MarkedBitFlag << (bitPosition % IntSize));

}

/// <summary>

/// Is bit at specified position marked?

/// </summary>

/// <param name="bitPosition">

/// <returns></returns>

// <securitykernel critical="True" ring="0">

// <usesunsafecode name="Field: m_arrayPtr">

// </usesunsafecode></securitykernel>

[System.Security.SecurityCritical]

internal unsafe bool IsMarked(int bitPosition)

{

if (useStackAlloc)

{

int bitArrayIndex = bitPosition / IntSize;

if (bitArrayIndex < m_length && bitArrayIndex >= 0)

{

return ((m_arrayPtr[bitArrayIndex] & (MarkedBitFlag << (bitPosition % IntSize))) != 0);

}

return false;

}

else

{

int bitArrayIndex = bitPosition / IntSize;

if (bitArrayIndex < m_length && bitArrayIndex >= 0)

{

return ((m_array[bitArrayIndex] & (MarkedBitFlag << (bitPosition % IntSize))) != 0);

}

return false;

}

/// <summary>

/// How many ints must be allocated to represent n bits. Returns (n+31)/32, but

/// avoids overflow

/// </summary>

/// <param name="n">

/// <returns></returns>

internal static int ToIntArrayLength(int n)

{

return n > 0 ? ((n - 1) / IntSize + 1) : 0;

}

I then renamed all the `HashSet` classes in FluentNHibernate to `HashTable`. Most unit tests passed at this point, with the lion's share failing due to SQLite which I hadn't bothered to install.

Compiled (had to compile as "unsafe" due to the `BitHelper` class) and replaced the FluentNHibernate.dll in my bin directory. Voila! it worked.

A Classic Geek

Saturday, December 8, 2012

Setting up a static IP in Ubuntu 12.04+

Monday, October 8, 2012

Mono and FluentNHibernate