DynHashSet32n.cs

Posted on August 6, 2020Tags , , ,   Leave a comment on DynHashSet32n.cs

Dynamic Concurrent Hash Set 32 Bit

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading;
/// <summary>
///     Modified from ConcurrentDictionary. 20% faster than ConcurrentDictionary
/// </summary>
/// <typeparam name="T"></typeparam>
[DebuggerTypeProxy(typeof(HashSetDebugView<>))]
[DebuggerDisplay("Count = {Count}")]
[Serializable]
public class DynHashSet32n<T> : ConcurrencyCheck, IReadOnlyCollection<T>, ICollection<T>
{
    private readonly IEqualityComparer<T> _comparer;
    private readonly bool                 _growLockArray;
    private          int                  _budget;
    private volatile Tables               _tables;
    private volatile int                  grows;
    public DynHashSet32n() : this(DefaultConcurrencyLevel, 1048576, true, null)
    {
    }
    public DynHashSet32n(int capacity) : this(DefaultConcurrencyLevel, capacity, false, null)
    {
    }
    public DynHashSet32n(int concurrencyLevel, int capacity) : this(concurrencyLevel, capacity, false, null)
    {
    }
    public DynHashSet32n(IEnumerable<T> collection) : this(collection, null)
    {
    }
    public DynHashSet32n(IEqualityComparer<T> comparer) : this(DefaultConcurrencyLevel, 1048576, true, comparer)
    {
    }
    public DynHashSet32n(IEnumerable<T> collection, IEqualityComparer<T> comparer) : this(comparer)
    {
        if (collection == null)
            throw new Exception("Collection is null.");
        InitializeFromCollection(collection);
    }
    public DynHashSet32n(int concurrencyLevel, IEnumerable<T> collection, IEqualityComparer<T> comparer) : this(concurrencyLevel, 1048576, false, comparer)
    {
        if (collection == null)
            throw new Exception("Collection is null.");
        InitializeFromCollection(collection);
    }
    public DynHashSet32n(int concurrencyLevel, int capacity, IEqualityComparer<T> comparer) : this(concurrencyLevel, capacity, false, comparer)
    {
    }
    private DynHashSet32n(int concurrencyLevel, int capacity, bool growLockArray, IEqualityComparer<T> comparer)
    {
        if (concurrencyLevel < 1)
            throw new Exception("Concurrency Level needs to be 1 or higher.");
        if (capacity < 0)
            throw new Exception("Capacity needs to be a positive number");
        if (capacity < concurrencyLevel)
            capacity = concurrencyLevel;
        var locks = new object[concurrencyLevel];
        for (var i = 0; i < locks.Length; i++)
            locks[i] = new object();
        var countPerLock = new int[locks.Length];
        var buckets      = new Node[capacity];
        _tables        = new Tables(buckets, locks, countPerLock);
        _growLockArray = growLockArray;
        _budget        = buckets.Length / locks.Length;
        _comparer      = comparer ?? EqualityComparer<T>.Default;
    }
    private static int DefaultConcurrencyLevel => Environment.ProcessorCount;
    public bool IsEmpty
    {
        get
        {
            var acquiredLocks = 0;
            try
            {
                AcquireAllLocks(ref acquiredLocks);
                if (_tables.CountPerLock.Any(t => t != 0))
                    return false;
            }
            finally
            {
                ReleaseLocks(0, acquiredLocks);
            }
            return true;
        }
    }
    public T this[int index]
    {
        get
        {
            if (index > Count)
                throw new Exception($"Getter: Index out of bounds {index} must be less than {Count}");
            return _tables.Buckets[index].Item;
        }
    }
    public void Clear()
    {
        var locksAcquired = 0;
        try
        {
            AcquireAllLocks(ref locksAcquired);
            var nTables = new Tables(new Node[1048576], _tables.Locks, new int[_tables.CountPerLock.Length]);
            _tables = nTables;
            _budget = Math.Max(1, nTables.Buckets.Length / nTables.Locks.Length);
        }
        finally
        {
            ReleaseLocks(0, locksAcquired);
        }
    }
    public bool Contains(T item)
    {
        if (item == null) return false;
        var hashcode     = _comparer.GetHashCode(item);
        var tables       = _tables;
        var bucketNumber = (hashcode & int.MaxValue) % tables.Buckets.Length;
        var current      = Volatile.Read(ref tables.Buckets[bucketNumber]);
        while (current != null)
        {
            if (hashcode == current.Hashcode && _comparer.Equals(current.Item, item))
                return true;
            current = current.Next;
        }
        return false;
    }
    void ICollection<T>.Add(T item)
    {
        Add(item);
    }
    bool ICollection<T>.IsReadOnly => false;
    void ICollection<T>.CopyTo(T[] array, int arrayIndex)
    {
        if (array == null)
            throw new Exception("The array is null.");
        if (arrayIndex < 0)
            throw new Exception("The array index is out of range.");
        var locksAcquired = 0;
        try
        {
            AcquireAllLocks(ref locksAcquired);
            var count = 0;
            for (var i = 0; i < _tables.Locks.Length && count >= 0; i++)
                count += _tables.CountPerLock[i];
            if (array.Length - count < arrayIndex || count < 0)
                throw new Exception("The index is equal to or greater than the length of the array.");
            CopyTo(array, arrayIndex);
        }
        finally
        {
            ReleaseLocks(0, locksAcquired);
        }
    }
    bool ICollection<T>.Remove(T item)
    {
        return TryRemove(item);
    }
    public int Count
    {
        get
        {
            var count         = 0;
            var acquiredLocks = 0;
            try
            {
                AcquireAllLocks(ref acquiredLocks);
                count += _tables.CountPerLock.Sum();
            }
            finally
            {
                ReleaseLocks(0, acquiredLocks);
            }
            return count;
        }
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
    public IEnumerator<T> GetEnumerator()
    {
        var buckets = _tables.Buckets;
        for (var i = 0; i < buckets.Length; i++)
        {
            var current = Volatile.Read(ref buckets[i]);
            while (current != null)
            {
                yield return current.Item;
                current = current.Next;
            }
        }
    }
    private void InitializeFromCollection(IEnumerable<T> collection)
    {
        foreach (var item in collection)
        {
            if (item == null)
                throw new Exception("Item in collection is null.");
            if (!AddInternal(item, false))
                throw new Exception("Source Contains Duplicates.");
        }
        if (_budget != 0)
            return;
        _budget = _tables.Buckets.Length / _tables.Locks.Length;
    }
    public bool Add(T item)
    {
        return AddInternal(item, true);
    }
    public bool TryRemove(T item)
    {
        var hashcode = _comparer.GetHashCode(item);
        while (true)
        {
            var tables = _tables;
            GetBucketAndlockNumber(hashcode, out var bucketNumber, out var lockNumber, tables.Buckets.Length, tables.Locks.Length);
            if (CheckState())
            {
                lock (tables.Locks[lockNumber])
                {
                    if (tables != _tables)
                        continue;
                    Node previous = null;
                    for (var current = tables.Buckets[bucketNumber]; current != null; current = current.Next)
                    {
                        if (hashcode == current.Hashcode && _comparer.Equals(current.Item, item))
                        {
                            if (previous == null)
                                Volatile.Write(ref tables.Buckets[bucketNumber], current.Next);
                            else
                                previous.Next = current.Next;
                            tables.CountPerLock[lockNumber]--;
                            return true;
                        }
                        previous = current;
                    }
                }
            }
            else
            {
                if (tables != _tables)
                    continue;
                Node previous = null;
                for (var current = tables.Buckets[bucketNumber]; current != null; current = current.Next)
                {
                    if (hashcode == current.Hashcode && _comparer.Equals(current.Item, item))
                    {
                        if (previous == null)
                            Volatile.Write(ref tables.Buckets[bucketNumber], current.Next);
                        else
                            previous.Next = current.Next;
                        tables.CountPerLock[lockNumber]--;
                        return true;
                    }
                    previous = current;
                }
            }
            return false;
        }
    }
    private bool AddInternal(T item, bool acquireLock)
    {
        var hashcode = _comparer.GetHashCode(item);
        while (true)
        {
            var tables = _tables;
            GetBucketAndlockNumber(hashcode, out var bucketNumber, out var lockNumber, tables.Buckets.Length, tables.Locks.Length);
            var resize    = false;
            var lockTaken = false;
            try
            {
                if (acquireLock && CheckState())
                    Monitor.Enter(tables.Locks[lockNumber], ref lockTaken);
                if (tables != _tables)
                    continue;
                for (var node = tables.Buckets[bucketNumber]; node != null; node = node.Next)
                    if (hashcode == node.Hashcode && _comparer.Equals(node.Item, item))
                        return false;
                Volatile.Write(ref tables.Buckets[bucketNumber], new Node(item, hashcode, tables.Buckets[bucketNumber]));
                checked
                {
                    tables.CountPerLock[lockNumber]++;
                }
                if (tables.CountPerLock[lockNumber] > _budget)
                    resize = true;
            }
            finally
            {
                if (lockTaken && CheckState())
                    Monitor.Exit(tables.Locks[lockNumber]);
            }
            if (resize)
                GrowTable(tables);
            return true;
        }
    }
    private static void GetBucketAndlockNumber(int hashcode, out int bucketNumber, out int lockNumber, int bucketCount, int lockCount)
    {
        bucketNumber = (hashcode & int.MaxValue) % bucketCount;
        lockNumber   = bucketNumber              % lockCount;
    }
    private void GrowTable(Tables tables)
    {
        var locksAcquired = 0;
        try
        {
            grows++;
            AcquireLocks(0, 1, ref locksAcquired);
            if (tables != _tables)
                return;
            var approxCount = tables.CountPerLock.Aggregate<int, long>(0, (current, t) => current + t);
            if (approxCount < tables.Buckets.Length / 4)
            {
                _budget = 2 * _budget;
                if (_budget < 0)
                    _budget = int.MaxValue;
                return;
            }
            var nLength      = 0;
            var maxTableSize = false;
            try
            {
                checked
                {
                    nLength = tables.Buckets.Length * 2 + 1;
                    while (nLength % 3 == 0 || nLength % 5 == 0 || nLength % 7 == 0)
                        nLength += 2;
                    if (nLength > int.MaxValue - 0x100000)
                        maxTableSize = true;
                }
            }
            catch (OverflowException)
            {
                maxTableSize = true;
            }
            if (maxTableSize)
            {
                nLength = int.MaxValue - 0x100000;
                _budget = int.MaxValue;
            }
            AcquireLocks(1, tables.Locks.Length, ref locksAcquired);
            var nLocks = tables.Locks;
            if (_growLockArray && tables.Locks.Length < 1024)
            {
                nLocks = new object[tables.Locks.Length * 2];
                Array.Copy(tables.Locks, 0, nLocks, 0, tables.Locks.Length);
                for (var i = tables.Locks.Length; i < nLocks.Length; i++)
                    nLocks[i] = new object();
            }
            var nBuckets      = new Node[nLength];
            var nCountPerLock = new int[nLocks.Length];
            foreach (var t in tables.Buckets)
            {
                var current = t;
                while (current != null)
                {
                    var next = current.Next;
                    GetBucketAndlockNumber(current.Hashcode, out var nbucketNumber, out var newlockNumber, nBuckets.Length, nLocks.Length);
                    nBuckets[nbucketNumber] = new Node(current.Item, current.Hashcode, nBuckets[nbucketNumber]);
                    checked
                    {
                        nCountPerLock[newlockNumber]++;
                    }
                    current = next;
                }
            }
            _budget = Math.Max(1, nBuckets.Length / nLocks.Length);
            _tables = new Tables(nBuckets, nLocks, nCountPerLock);
        }
        finally
        {
            ReleaseLocks(0, locksAcquired);
        }
    }
    private void AcquireAllLocks(ref int locksAcquired)
    {
        if (CheckState())
        {
            AcquireLocks(0, 1,                    ref locksAcquired);
            AcquireLocks(1, _tables.Locks.Length, ref locksAcquired);
        }
    }
    private void AcquireLocks(int fromInclusive, int toExclusive, ref int locksAcquired)
    {
        if (CheckState())
        {
            var locks = _tables.Locks;
            for (var i = fromInclusive; i < toExclusive; i++)
            {
                var lockTaken = false;
                try
                {
                    Monitor.Enter(locks[i], ref lockTaken);
                }
                finally
                {
                    if (lockTaken)
                        locksAcquired++;
                }
            }
        }
    }
    private void ReleaseLocks(int fromInclusive, int toExclusive)
    {
        if (CheckState())
            for (var i = fromInclusive; i < toExclusive; i++)
                Monitor.Exit(_tables.Locks[i]);
    }
    private void CopyTo(T[] array, int index)
    {
        var buckets = _tables.Buckets;
        foreach (var t in buckets)
            for (var current = t; current != null; current = current.Next)
            {
                array[index] = current.Item;
                index++;
            }
    }
    public T[] ToArray()
    {
        var locksAcquired = 0;
        try
        {
            AcquireAllLocks(ref locksAcquired);
            var length = 0;
            var index  = 0;
            while (index < _tables.Locks.Length)
            {
                checked
                {
                    length += _tables.CountPerLock[index];
                }
                checked
                {
                    ++index;
                }
            }
            if (length == 0)
                return Array.Empty<T>();
            var array = new T[length];
            CopyTo(array, 0);
            return array;
        }
        finally
        {
            ReleaseLocks(0, locksAcquired);
        }
    }
    private class Tables
    {
        public readonly Node[]   Buckets;
        public readonly object[] Locks;
        public volatile int[]    CountPerLock;
        public Tables(Node[] buckets, object[] locks, int[] countPerLock)
        {
            Buckets      = buckets;
            Locks        = locks;
            CountPerLock = countPerLock;
        }
    }
    private class Node
    {
        public readonly int  Hashcode;
        public readonly T    Item;
        public volatile Node Next;
        public Node(T item, int hashcode, Node next)
        {
            Item     = item;
            Hashcode = hashcode;
            Next     = next;
        }
    }
}

MSet15.cs

Posted on August 5, 2020Tags ,   Leave a comment on MSet15.cs

Small Hash Set Class (Minimal)

using System;
using System.Collections.Generic;
using System.Diagnostics;
[DebuggerDisplay("Count = {" + nameof(Count) + "}")]
[Serializable]
public class MSet15<T>
{
    private IEqualityComparer<T> _comparer;
    private int[]                _hashBuckets;
    private Slot[]               _slots;
    public MSet15() : this(11, EqualityComparer<T>.Default)
    {
    }
    public MSet15(int size) : this(size, EqualityComparer<T>.Default)
    {
    }
    public MSet15(IEqualityComparer<T> comparer) : this(11, comparer)
    {
    }
    public MSet15(int size, IEqualityComparer<T> comparer)
    {
        if (comparer == null)
            comparer = EqualityComparer<T>.Default;
        _comparer    = comparer;
        _hashBuckets = new int[size];
        _slots       = new Slot[size];
        Count        = 0;
    }
    public int Count
    {
        get;
        private set;
    }
    public IEnumerator<T> GetEnumerator()
    {
        for (var i = 0; i < Count; i++)
            if (_slots[i].HashCode > 0)
                yield return _slots[i].Value;
    }
    public bool Add(T item)
    {
        var hashCode = _comparer.GetHashCode(item) & int.MaxValue;
        if (FindEntry(item, hashCode) != -1)
            return true;
        if (Count >= _slots.Length)
            Resize();
        var hashPos = hashCode % _hashBuckets.Length;
        _slots[Count].Next     = _hashBuckets[hashPos] - 1;
        _slots[Count].Value    = item;
        _slots[Count].HashCode = hashCode;
        _hashBuckets[hashPos]  = Count + 1;
        ++Count;
        return false;
    }
    public bool Contains(T item)
    {
        return FindEntry(item, _comparer.GetHashCode(item) & int.MaxValue) != -1;
    }
    private void Resize()
    {
        var newSize        = _hashBuckets.Length * 2;
        var newSlots       = new Slot[newSize];
        var newHashBuckets = new int[newSize];
        var newCount       = 0;
        var en             = GetEnumerator();
        while (en.MoveNext())
        {
            var item     = en.Current;
            var hashCode = _comparer.GetHashCode(item) & int.MaxValue;
            var hashPos  = hashCode % newHashBuckets.Length;
            newSlots[newCount].Next     = newHashBuckets[hashPos] - 1;
            newSlots[newCount].Value    = item;
            newSlots[newCount].HashCode = hashCode;
            newHashBuckets[hashPos]     = newCount + 1;
            ++newCount;
        }
        _slots       = newSlots;
        _hashBuckets = newHashBuckets;
        Count        = newCount;
    }
    private int FindEntry(T item, int hashCode)
    {
        for (var position = _hashBuckets[hashCode % _hashBuckets.Length] - 1; position >= 0; position = _slots[position].Next)
            if (_slots[position].HashCode == hashCode && _comparer.Equals(_slots[position].Value, item))
                return position;
        return -1;
    }
    public int FindEntry(T item)
    {
        return FindEntry(item, _comparer.GetHashCode(item) & int.MaxValue);
    }
    internal struct Slot
    {
        public int HashCode;
        public int Next;
        public T   Value;
    }
}

TinySet.cs

Posted on July 30, 2020Tags , ,   Leave a comment on TinySet.cs

A Small HashSet Class

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
[DebuggerTypeProxy(typeof(HashSetDebugView<>))]
[DebuggerDisplay("Count = {" + nameof(Count) + "}")]
[Serializable]
public class TinySet<T>
{
    private  int[]                _hashBuckets;
    private  SizeHelper<T>        _newSize = new SizeHelper<T>();
    internal IEqualityComparer<T> Comparer;
    public   int                  Position;
    internal Slot[]               Slots;
    public TinySet() : this(101, EqualityComparer<T>.Default)
    {
    }
    public TinySet(int size) : this(size, EqualityComparer<T>.Default)
    {
    }
    public TinySet(IEqualityComparer<T> comparer) : this(101, comparer)
    {
    }
    public TinySet(int size, IEqualityComparer<T> comparer)
    {
        if (comparer == null)
            comparer = EqualityComparer<T>.Default;
        Comparer     = comparer;
        _hashBuckets = new int[size];
        Slots        = new Slot[size];
        Count        = 0;
        Position     = -1;
    }
    public TinySet(IEnumerable<T> collection, IEqualityComparer<T> comparer)
    {
        if (comparer == null)
            comparer = EqualityComparer<T>.Default;
        Comparer = comparer;
        if (!(collection is ICollection<T> coll))
            return;
        var size = coll.Count;
        _hashBuckets = new int[size];
        Slots        = new Slot[size];
        UnionWith(coll);
    }
    public int Count
    {
        get;
        private set;
    }
    public T[] ToArray()
    {
        var newArray = new T[Count];
        var copied   = 0;
        for (var i = 0; i < Count && copied < Count; i++)
            if (Slots[i].HashCode > 0)
                newArray[copied++] = Slots[i].Value;
        return newArray;
    }
    public void Create(int size, IEqualityComparer<T> comparer)
    {
        if (comparer == null)
            comparer = EqualityComparer<T>.Default;
        Comparer     = comparer;
        _hashBuckets = new int[size];
        Slots        = new Slot[size];
        Count        = 0;
        Position     = -1;
    }
    public void Clear()
    {
        var size = Slots.Length;
        _hashBuckets = new int[size];
        Slots        = new Slot[size];
        Count        = 0;
        Position     = -1;
    }
    public bool Add(T item)
    {
        return Insert(item, true);
    }
    public bool Contains(T item)
    {
        return Insert(item, false);
    }
    internal bool Insert(T item, bool add)
    {
        var hashCode = Comparer.GetHashCode(item) & int.MaxValue;
        if (FindEntry(item, hashCode) != -1)
            return true;
        if (add)
        {
            if (Count >= Slots.Length)
                SetSizeAndOrForceNewHashCodes(_newSize.GetNewSize(_hashBuckets.Length));
            var hashPos = hashCode % _hashBuckets.Length;
            Slots[Count].Next     = _hashBuckets[hashPos] - 1;
            Slots[Count].Value    = item;
            Slots[Count].HashCode = hashCode;
            _hashBuckets[hashPos] = Count + 1;
            Position              = Count;
            ++Count;
        }
        return false;
    }
    public void ForceNewHashCodes()
    {
        SetSizeAndOrForceNewHashCodes();
    }
    private void SetSizeAndOrForceNewHashCodes(int Size = 0)
    {
        if (Count == 0) return;
        var newSize        = Size == 0 ? Count : Size;
        var newSlots       = new Slot[newSize];
        var newHashBuckets = new int[newSize];
        if (Slots != null)
            Array.Copy(Slots, 0, newSlots, 0, Count);
        for (var i = 0; i < newSize; ++i)
            if (newSlots[i].HashCode > 0 && newSlots[i].Value != null)
                newSlots[i].HashCode = Comparer.GetHashCode(newSlots[i].Value) & int.MaxValue;
        for (var i = 0; i < newSize; ++i)
        {
            var pos = newSlots[i].HashCode % newSize;
            newSlots[i].Next    = newHashBuckets[pos] - 1;
            newHashBuckets[pos] = i                   + 1;
        }
        Slots        = newSlots;
        _hashBuckets = newHashBuckets;
    }
    public void TrimExcess()
    {
        var newHashBuckets = new int[Count];
        var newSlots       = new Slot[Count];
        Array.Copy(Slots, newSlots, Count);
        for (var i = 0; i < Count; i++)
        {
            var pos = newSlots[i].HashCode % Count;
            newSlots[i].Next    = newHashBuckets[pos] - 1;
            newHashBuckets[pos] = i                   + 1;
        }
        _hashBuckets = newHashBuckets;
        Slots        = newSlots;
    }
    public bool Remove(T item)
    {
        if (Count != 0)
        {
            var hashCode = Comparer.GetHashCode(item) & int.MaxValue;
            var iPos     = hashCode % _hashBuckets.Length;
            var tPos     = -1;
            for (var sPos = _hashBuckets[iPos] - 1; sPos >= 0; sPos = Slots[sPos].Next)
            {
                if (Slots[sPos].HashCode == hashCode && Comparer.Equals(Slots[sPos].Value, item))
                {
                    if (tPos < 0)
                        _hashBuckets[iPos] = Slots[sPos].Next + 1;
                    else
                        Slots[tPos].Next = Slots[sPos].Next;
                    Slots[sPos].HashCode = -1;
                    Slots[sPos].Value    = default;
                    Slots[sPos].Next     = 0;
                    --Count;
                    return true;
                }
                tPos = sPos;
            }
        }
        return false;
    }
    private int FindEntry(T item, int hashCode)
    {
        for (var position = _hashBuckets[hashCode % _hashBuckets.Length] - 1; position >= 0; position = Slots[position].Next)
            if (Slots[position].HashCode == hashCode && Comparer.Equals(Slots[position].Value, item))
            {
                Position = position;
                return position;
            }
        return -1;
    }
    public int FindEntry(T item)
    {
        return FindEntry(item, Comparer.GetHashCode(item) & int.MaxValue);
    }
    public void ExceptWith(IEnumerable<T> other)
    {
        if (other == null)
            throw new Exception("The other set must not be null.");
        if (Count == 0)
            return;
        if (Equals(other, this))
            Clear();
        else
            foreach (var obj in other)
                Remove(obj);
    }
    public void UnionWith(IEnumerable<T> other)
    {
        if (other == null)
            throw new Exception("The other set must not be null.");
        foreach (var obj in other)
            Add(obj);
    }
    public bool Overlaps(IEnumerable<T> other)
    {
        if (other == null)
            throw new Exception("The other set must not be null.");
        return Count != 0 && other.Any(Contains);
    }
    public bool ContainsAllElements(IEnumerable<T> other)
    {
        return other.All(Contains);
    }
    public int RemoveWhere(Predicate<T> pred)
    {
        if (pred == null)
            throw new Exception("The Predicate cannot be null.");
        var matches = 0;
        for (var i = 0; i < Count; ++i)
            if (Slots[i].HashCode >= 0)
            {
                var obj = Slots[i].Value;
                if (pred(obj) && Remove(obj))
                    ++matches;
            }
        return matches;
    }
    internal struct Slot
    {
        public int HashCode;
        public int Next;
        public T   Value;
    }
}