Big Hash Set based on BigArray.cs
Uses two arrays, for a single array use BigHashsetSa.cs
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Runtime.Serialization;
using System.Threading;
[Serializable]
[DebuggerDisplay("Count = {Count}")]
[Obsolete]
public class BigHashSet<T> : MonitorActionFunc, IEnumerable<T>, ISerializable, IDeserializationCallback
{
private readonly SerializationInfo sInfo;
public volatile Table _table = new Table();
public BigHashSet() : this(BigArray<T>.Granularity, new BigComparer<T>())
{
}
public BigHashSet(long size) : this(size, new BigComparer<T>())
{
}
public BigHashSet(IBigEqualityComparer<T> comparer) : this(BigArray<T>.Granularity, comparer)
{
}
public BigHashSet(long size, IBigEqualityComparer<T> comparer)
{
Lock(this, () =>
{
if (size < BigArray<T>.Granularity)
size = BigArray<T>.Granularity;
if (comparer == null)
comparer = new DynComparer64<T>();
_table.Comparer = comparer;
_table.HashBuckets = new BigArray<long>(size);
_table.Slots = new BigArray<Slot>(size);
_table._count = 0;
_table.Position = -1;
_table.HashBuckets.OverrideAutoConcurrency = true;
_table.Slots.OverrideAutoConcurrency = true;
});
}
public BigHashSet(IEnumerable<T> collection)
{
Lock(this, () =>
{
var size = BigArray<T>.Granularity;
_table.Comparer = new DynComparer64<T>();
_table.HashBuckets = new BigArray<long>(size);
_table.Slots = new BigArray<Slot>(size);
_table._count = 0;
_table.Position = -1;
_table.HashBuckets.OverrideAutoConcurrency = true;
_table.Slots.OverrideAutoConcurrency = true;
foreach (var item in collection)
Insert(item, true);
});
}
public BigHashSet(IEnumerable<T> collection, IBigEqualityComparer<T> comparer)
{
Lock(this, () =>
{
if (comparer == null)
comparer = new DynComparer64<T>();
var size = BigArray<T>.Granularity;
_table.Comparer = comparer;
_table.Comparer = new DynComparer64<T>();
_table.HashBuckets = new BigArray<long>(size);
_table.Slots = new BigArray<Slot>(size);
_table._count = 0;
_table.Position = -1;
_table.HashBuckets.OverrideAutoConcurrency = true;
_table.Slots.OverrideAutoConcurrency = true;
foreach (var item in collection)
Insert(item, true);
});
}
protected BigHashSet(SerializationInfo info, StreamingContext context)
{
sInfo = info;
}
public long Count
{
get
{
return Lock(this, () =>
{
return _table._count;
});
}
private set
{
Lock(this, () =>
{
_table._count = value;
});
}
}
public T this[T item]
{
get
{
return Lock(this, () =>
{
var pos = FindEntry(item);
if (pos == -1)
throw new Exception($"Getter: Index out of bounds {pos} must be contained within set.");
return _table.Slots[pos]._value;
});
}
set => Insert(item, true);
}
public T this[long index]
{
get
{
return Lock(this, () =>
{
if (index > _table._count || _table._count == 0)
SpinWait.SpinUntil(() => index < _table._count && _table._count > 0, 100);
if (index > _table._count)
throw new Exception($"Getter: Index out of bounds {index} must be less than {_table._count}");
return _table.Slots[index]._value;
});
}
}
public void OnDeserialization(object sender)
{
Lock(this, () =>
{
if (sInfo == null)
return;
var size = sInfo.GetInt64("Capacity");
if (size != 0)
{
Clear();
_table.HashBuckets = new BigArray<long>(size);
_table.Slots = new BigArray<Slot>(size);
_table.Comparer = (IBigEqualityComparer<T>) sInfo.GetValue("Comparer", typeof(IBigEqualityComparer<T>));
_table._count = sInfo.GetInt64("Count");
_table.Position = -1;
var array = (Slot[][]) sInfo.GetValue("Elements", typeof(Slot[][]));
if (array == null)
throw new SerializationException("Missing Elements.");
var buckets = (long[][]) sInfo.GetValue("Buckets", typeof(long[][]));
if (buckets == null)
throw new SerializationException("Missing Buckets.");
_table.Slots.FromArray(array);
_table.HashBuckets.FromArray(buckets);
}
});
}
IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
return GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
public void GetObjectData(SerializationInfo info, StreamingContext context)
{
Lock(this, () =>
{
info.AddValue("Comparer", _table.Comparer, typeof(IBigEqualityComparer<T>));
info.AddValue("Capacity", _table.HashBuckets.Length);
info.AddValue("Count", _table._count);
var array = _table.Slots.ToArray();
info.AddValue("Elements", array, typeof(BigArray<Slot>));
var buck = _table.HashBuckets.ToArray();
info.AddValue("Buckets", buck, typeof(BigArray<long>));
});
}
public void Clear()
{
Lock(this, () =>
{
var size = BigArray<T>.Granularity;
_table.HashBuckets = new BigArray<long>(size);
_table.Slots = new BigArray<Slot>(size);
_table._count = 0;
_table.Position = -1;
});
}
public bool Add(T item)
{
return Insert(item, true);
}
public void AddRange(IEnumerable<T> collection)
{
Lock(this, () =>
{
foreach (var item in collection)
Insert(item, true);
});
}
public bool Contains(T item)
{
return Insert(item, false);
}
private long InternalGetHashCode(T item)
{
if (item == null)
return 0;
return _table.Comparer.GetHashCode(item) & long.MaxValue;
}
internal bool Insert(T item, bool add)
{
return Lock(this, () =>
{
var hashCode = InternalGetHashCode(item);
if (FindEntry(item, hashCode) != -1)
return true;
_table.Position = -1;
if (add)
{
if (_table._count >= _table.Slots.Length)
{
var newSize = _table.HashBuckets.Length << 1;
var newHashBuckets = new BigArray<long>(newSize);
var newSlots = new BigArray<Slot>(newSize);
for (var i = 0L; i < _table._count; i++)
{
var pos = _table.Slots[i]._hashCode % newSize;
newSlots[i] = new Slot(_table.Slots[i]._hashCode, newHashBuckets[pos] - 1, _table.Slots[i]._value);
newHashBuckets[pos] = i + 1;
}
_table.HashBuckets = newHashBuckets;
_table.Slots = newSlots;
}
var hashPos = hashCode % _table.HashBuckets.Length;
var news = new Slot(hashCode, _table.HashBuckets[hashPos] - 1, item);
_table.Slots[_table._count] = news;
_table.HashBuckets[hashPos] = _table._count + 1;
_table.Position = _table._count;
_table._count++;
}
return false;
});
}
private long FindEntry(T item, long hashCode)
{
return Lock(this, () =>
{
for (var position = _table.HashBuckets[hashCode % _table.HashBuckets.Length] - 1; position >= 0; position = _table.Slots[position]._next)
if (_table.Slots[position]._hashCode == hashCode && Equals(_table.Slots[position]._value, item))
{
_table.Position = position;
return _table.Position;
}
return -1;
});
}
public T[] ToArray()
{
return Lock(this, () =>
{
var array = new T[Count];
for (var i = 0L; i < Count; i++)
if (_table.Slots[i]._hashCode >= 0)
array[i] = _table.Slots[i]._value;
return array;
});
}
public long FindEntry(T item)
{
return FindEntry(item, InternalGetHashCode(item));
}
public bool Remove(T item)
{
return Lock(this, () =>
{
var hashCode = _table.Comparer.GetHashCode(item) & long.MaxValue;
for (var position = _table.HashBuckets[hashCode % _table.HashBuckets.Length] - 1; position >= 0; position = _table.Slots[position]._next)
if (_table.Slots[position]._hashCode == hashCode && Equals(_table.Slots[position]._value, item))
{
var hashPos = hashCode % _table.HashBuckets.Length;
var news = new Slot(0, -1, default);
_table.Slots[position] = news;
_table.HashBuckets[hashPos] = -1;
return true;
}
return false;
});
}
public IEnumerator<T> GetEnumerator()
{
return Lock(this, () =>
{
return GetEnum();
});
}
public IEnumerator<T> GetEnum()
{
for (var i = 0; i < Count; i++)
if (_table.Slots[i]._hashCode >= 0)
yield return _table.Slots[i]._value;
}
public class Table
{
public long _count;
internal IBigEqualityComparer<T> Comparer;
internal volatile BigArray<long> HashBuckets;
public long Position;
internal volatile BigArray<Slot> Slots;
}
[Serializable]
internal struct Slot
{
public readonly long _hashCode;
public readonly long _next;
public readonly T _value;
public Slot(long hashcode, long next, T value)
{
_hashCode = hashcode;
_next = next;
_value = value;
}
}
}