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;
        }
    }
}

DynArrayStruct32.cs

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

Dynamic Concurrent Generic Array Structure 32 Bit

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading;
using Microsoft.VisualBasic.Devices;
[DebuggerDisplay("Count = {Count}")]
[Serializable]
public struct DynArrayStruct32<T> : IEnumerable<T>
{
    public const     int               ShiftCount  = 20;
    public const     int               Granularity = 1 << ShiftCount;
    private volatile Table             _table;
    public volatile  T[][]             Arrays;
    public volatile  int               MaximumNumberOfArrays;
    private volatile MonitorActionFunc maf;
    public DynArrayStruct32(long size)
    {
        if (size < Granularity)
            size = Granularity;
        try
        {
            maf                         = new MonitorActionFunc();
            _table                      = new Table();
            MaximumNumberOfArrays       = (int) (new ComputerInfo().AvailablePhysicalMemory / Granularity);
            _table.NumberOfActiveArrays = (int) ((size + (Granularity - 1))                 / Granularity);
            var val = (long) _table.NumberOfActiveArrays                                    * Granularity;
            _table.Length = Interlocked.Read(ref val);
            Arrays        = new T[MaximumNumberOfArrays][];
            for (var i = 0; i < _table.NumberOfActiveArrays; ++i)
                Arrays[i] = new T[Granularity];
        }
        catch (Exception ex)
        {
            throw new Exception($"'Initialize:DynArray' Exception: {ex.Message}");
        }
    }
    public DynArrayStruct32(IEnumerable<T> collection)
    {
        try
        {
            maf                   = new MonitorActionFunc();
            _table                = new Table();
            MaximumNumberOfArrays = (int) (new ComputerInfo().AvailablePhysicalMemory / Granularity);
            var size = Granularity;
            _table.NumberOfActiveArrays = (size + (Granularity - 1)) / Granularity;
            var val = (long) _table.NumberOfActiveArrays * Granularity;
            _table.Length = Interlocked.Read(ref val);
            Arrays        = new T[MaximumNumberOfArrays][];
            for (var i = 0; i < _table.NumberOfActiveArrays; ++i)
                Arrays[i] = new T[Granularity];
        }
        catch (Exception ex)
        {
            throw new Exception($"'Initialize:DynArray' Exception: {ex.Message}");
        }
        foreach (var item in collection)
            Add(item);
    }
    public long Count
    {
        get
        {
            var tmpThis = this;
            return tmpThis.maf.Lock(tmpThis, () =>
            {
                return tmpThis._table.Count;
            });
        }
    }
    public long Length
    {
        get
        {
            var tmpThis = this;
            return tmpThis.maf.Lock(tmpThis, () =>
            {
                return tmpThis._table.Length;
            });
        }
    }
    public T this[long index]
    {
        get
        {
            var tmpThis = this;
            return tmpThis.maf.Lock(tmpThis, () =>
            {
                if (index >= tmpThis._table.Length)
                    throw new Exception($"Getter: Index out of bounds, Index: '{index}' must be less than the Length: '{tmpThis.Length}'.");
                return tmpThis.Arrays[index >> ShiftCount][index & (Granularity - 1)];
            });
        }
        set
        {
            var tmpThis = this;
            tmpThis.maf.Lock(tmpThis, () =>
            {
                if (index + 1 > tmpThis._table.Length)
                    tmpThis.EnsureSize();
                tmpThis.Arrays[index >> ShiftCount][index & (Granularity - 1)] = value;
                tmpThis._table.Count++;
            });
        }
    }
    IEnumerator<T> IEnumerable<T>.GetEnumerator()
    {
        return new Enumerator(this);
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return new Enumerator(this);
    }
    public void Add(T Item)
    {
        var tmpThis = this;
        tmpThis.maf.Lock(tmpThis, () =>
        {
            if (tmpThis._table.Count + 1 > tmpThis._table.Length)
                tmpThis.EnsureSize();
            tmpThis.Arrays[tmpThis._table.Count >> ShiftCount][tmpThis._table.Count & (Granularity - 1)] = Item;
            tmpThis._table.Count++;
        });
    }
    public void AddRange(IEnumerable<T> collection)
    {
        var tmpThis = this;
        tmpThis.maf.Lock(tmpThis, () =>
        {
            foreach (var item in collection)
                tmpThis.Add(item);
        });
    }
    public Enumerator GetEnumerator()
    {
        return new Enumerator(this);
    }
    private void EnsureSize()
    {
        try
        {
            _table.NumberOfActiveArrays++;
            if (_table.NumberOfActiveArrays >= MaximumNumberOfArrays)
                throw new Exception($"Number of active arrays {_table.NumberOfActiveArrays} cannot meet or exceed the maximum number of arrays {MaximumNumberOfArrays} allowed.");
            var val = (long) _table.NumberOfActiveArrays * Granularity;
            _table.Length                           = Interlocked.Read(ref val);
            Arrays[_table.NumberOfActiveArrays - 1] = new T[Granularity];
        }
        catch (Exception ex)
        {
            throw new Exception($"'EnsureSize:DynArray' Exception: {ex.Message}");
        }
    }
    public void Clear()
    {
        var tmpThis = this;
        tmpThis.maf.Lock(tmpThis, () =>
        {
            for (var a = 0L; a < tmpThis._table.NumberOfActiveArrays; a++)
                Array.Clear(tmpThis.Arrays[a], 0, Granularity);
            tmpThis._table.Count = 0;
        });
    }
    public long IndexOf(T item)
    {
        var tmpThis = this;
        return tmpThis.maf.Lock(tmpThis, () =>
        {
            var i = 0L;
            for (; i < tmpThis._table.NumberOfActiveArrays; i++)
            {
                var pos = Array.IndexOf(tmpThis.Arrays[i], item, 0);
                if (pos != -1)
                    return i * Granularity + pos;
            }
            return -1;
        });
    }
    public DynArrayStruct32<T> Copy(int newsize)
    {
        var tmpThis = this;
        return tmpThis.maf.Lock(tmpThis, () =>
        {
            var temp = new DynArrayStruct32<T>(newsize);
            for (var a = 0L; a < tmpThis._table.NumberOfActiveArrays; a++)
                Array.Copy(tmpThis.Arrays[a], temp.Arrays[a], Granularity);
            return temp;
        });
    }
    public DynArrayStruct32<T> CopyOrInsert(T item, int newsize)
    {
        var tmpThis = this;
        return tmpThis.maf.Lock(tmpThis, () =>
        {
            if (newsize > tmpThis._table.Length)
            {
                var temp = new DynArrayStruct32<T>(newsize);
                for (var a = 0L; a < tmpThis._table.NumberOfActiveArrays; a++)
                    Array.Copy(tmpThis.Arrays[a], temp.Arrays[a], Granularity);
                temp._table.Count = tmpThis.Count;
                temp.Add(item);
                return temp;
            }
            tmpThis.Add(item);
            return tmpThis;
        });
    }
    public void FromArray(T[][] array)
    {
        var tmpThis = this;
        tmpThis.maf.Lock(tmpThis, () =>
        {
            tmpThis._table.NumberOfActiveArrays = array.GetUpperBound(0) + 1;
            var val = (long) tmpThis._table.NumberOfActiveArrays * Granularity;
            tmpThis._table.Length = Interlocked.Read(ref val);
            tmpThis.Arrays        = new T[tmpThis._table.NumberOfActiveArrays][];
            for (var i = 0; i < tmpThis._table.NumberOfActiveArrays; ++i)
                tmpThis.Arrays[i] = new T[Granularity];
            for (var a = 0L; a < tmpThis._table.NumberOfActiveArrays; a++)
                Array.Copy(array[a], tmpThis.Arrays[a], Granularity);
        });
    }
    public T[][] ToArray()
    {
        var tmpThis = this;
        return tmpThis.maf.Lock(tmpThis, () =>
        {
            var ta = new T[tmpThis._table.NumberOfActiveArrays][];
            for (var i = 0; i < tmpThis._table.NumberOfActiveArrays; ++i)
                ta[i] = new T[Granularity];
            for (var a = 0L; a < tmpThis._table.NumberOfActiveArrays; a++)
                Array.Copy(tmpThis.Arrays[a], ta[a], Granularity);
            return ta;
        });
    }
    public T[] ToArray32()
    {
        var tmpThis = this;
        return tmpThis.maf.Lock(tmpThis, () =>
        {
            if (tmpThis.Count >= uint.MaxValue)
                throw new Exception("Too many elements to cast to a 32Bit array.");
            var array = new T[tmpThis.Count];
            var cnt   = 0l;
            for (var a = 0L; a < tmpThis._table.NumberOfActiveArrays && cnt < uint.MaxValue; a++, cnt += Granularity)
                Array.Copy(tmpThis.Arrays[a], 0, array, a * Granularity, Granularity);
            return array;
        });
    }
    public (int l, int r) BoundsFromIndex(int index)
    {
        var l = index >> ShiftCount;
        var r = index & (Granularity - 1);
        return (r, r);
    }
    public int IndexFromBounds(int l, int r)
    {
        return l * Granularity + r;
    }
    private class Table
    {
        public          long Count;
        public          long Length;
        public volatile int  NumberOfActiveArrays;
    }
    [Serializable]
    public class Enumerator : IEnumerator<T>
    {
        private readonly DynArrayStruct32<T> _array;
        private volatile eTable              _eTable = new eTable();
        internal Enumerator(DynArrayStruct32<T> array)
        {
            _array         = array;
            _eTable._index = 0;
            Current        = default;
        }
        public T Current
        {
            get;
            private set;
        }
        object IEnumerator.Current
        {
            get
            {
                return _array.maf.Lock(this, () =>
                {
                    if (_eTable._index == _array._table.Count + 1)
                        throw new Exception($"Enumerator out of range: {_eTable._index}");
                    return Current;
                });
            }
        }
        public void Dispose()
        {
        }
        public bool MoveNext()
        {
            return _array.maf.Lock(this, () =>
            {
                for (; _eTable._index < _array._table.Count; ++_eTable._index)
                    if (_eTable._index < _array._table.Count || _eTable._index == 0)
                    {
                        Current = _array[_eTable._index];
                        ++_eTable._index;
                        return true;
                    }
                _eTable._index = _array._table.Count + 1;
                Current        = default;
                return false;
            });
        }
        void IEnumerator.Reset()
        {
            _eTable._index = 0;
            Current        = default;
        }
        private class eTable
        {
            public long _index;
        }
    }
}

ConcurrencyCheck.cs

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

Check and Store Concurrency Usage

using System;
using System.Diagnostics;
using System.Threading;
public class ConcurrencyCheck
{
    public volatile ConcurrencyInfo concurrencyInfo = new ConcurrencyInfo();
    private         int             ProcessorCount => Environment.ProcessorCount;
    public bool OverrideAutoConcurrency
    {
        get;
        set;
    }
    public bool QuickCheck
    {
        get;
        set;
    } = false;
    public bool UsingConcurrency
    {
        get;
        private set;
    }
    public bool CheckState()
    {
        if (OverrideAutoConcurrency)
            return false;
        if (QuickCheck && concurrencyInfo.Calls > ProcessorCount && concurrencyInfo.LockState == 0)
            return false;
        if (concurrencyInfo.StatusThreadId != Thread.CurrentThread.ManagedThreadId)
        {
            concurrencyInfo.StatusThreadId = Thread.CurrentThread.ManagedThreadId;
            concurrencyInfo.Add(concurrencyInfo.StatusThreadId);
        }
        if (concurrencyInfo.LockState == 1)
            return true;
        if (concurrencyInfo.BeginningThreadId == 0 && concurrencyInfo.LockState == 0 && Thread.CurrentThread.ManagedThreadId != 0)
            concurrencyInfo.BeginningThreadId = Thread.CurrentThread.ManagedThreadId;
        if (concurrencyInfo.LockState == 0)
            if (concurrencyInfo.BeginningThreadId != Thread.CurrentThread.ManagedThreadId)
            {
                concurrencyInfo.LockState = 1;
                UsingConcurrency          = true;
                return true;
            }
        concurrencyInfo.Calls++;
        return false;
    }
    [DebuggerDisplay("UniqueThreadIds = {ActiveThreads}")]
    public class ConcurrencyInfo
    {
        public volatile int     ActiveThreads=1;
        public volatile int     BeginningThreadId;
        public volatile int     Calls;
        public volatile ulong[] ContextSwitches = new ulong[32768];
        public volatile int     LockState;
        public volatile int     StatusThreadId;
        public volatile int[]   UniqueThreadIds = new int[32768];
        public void Add(int value)
        {
            if (UniqueThreadIds[value] != value)
            {
                UniqueThreadIds[value] = value;
                ActiveThreads++;
                return;
            }
            ContextSwitches[value]++;
        }
    }
}

MonitorActionFunc.cs

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

Use to Lock Local Functions with Concurrency

using System;
using System.Threading;
public class MonitorActionFunc : ConcurrencyCheck
{
    public void Lock(object localObject, Action action)
    {
        if (CheckState())
        {
            var lockTaken = false;
            try
            {
                Monitor.Enter(localObject, ref lockTaken);
                action();
            }
            finally
            {
                if (lockTaken)
                    Monitor.Exit(localObject);
            }
        }
        else
        {
            action();
        }
    }
    public TResult Lock<TResult>(object localObject, Func<TResult> func)
    {
        if (CheckState())
        {
            var lockTaken = false;
            try
            {
                Monitor.Enter(localObject, ref lockTaken);
                return func();
            }
            finally
            {
                if (lockTaken)
                    Monitor.Exit(localObject);
            }
        }
        return func();
    }
    public (TResult1, TResult2) Lock<TResult1, TResult2>(object localObject, Func<(TResult1, TResult2)> func)
    {
        if (CheckState())
        {
            var lockTaken = false;
            try
            {
                Monitor.Enter(localObject, ref lockTaken);
                return func();
            }
            finally
            {
                if (lockTaken)
                    Monitor.Exit(localObject);
            }
        }
        return func();
    }
    public (TResult1, TResult2) Lock<TArg, TResult1, TResult2>(object localObject, Func<TArg, (TResult1, TResult2)> func, TArg arg)
    {
        if (CheckState())
        {
            var lockTaken = false;
            try
            {
                Monitor.Enter(localObject, ref lockTaken);
                return func(arg);
            }
            finally
            {
                if (lockTaken)
                    Monitor.Exit(localObject);
            }
        }
        return func(arg);
    }
    public TResult Lock<TArg, TResult>(object localObject, Func<TArg, TResult> func, TArg arg)
    {
        if (CheckState())
        {
            var lockTaken = false;
            try
            {
                Monitor.Enter(localObject, ref lockTaken);
                return func(arg);
            }
            finally
            {
                if (lockTaken)
                    Monitor.Exit(localObject);
            }
        }
        return func(arg);
    }
    public void Lock<TArg>(object localObject, Action<TArg> action, TArg arg)
    {
        if (CheckState())
        {
            var lockTaken = false;
            try
            {
                Monitor.Enter(localObject, ref lockTaken);
                action(arg);
            }
            finally
            {
                if (lockTaken)
                    Monitor.Exit(localObject);
            }
        }
        else
        {
            action(arg);
        }
    }
}

ZOB64.cs

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

Example Zobrist Hashing 64-Bit

using System;
using System.Runtime.InteropServices;
using System.Security.Cryptography;
/// <summary>
///     
///     https://en.wikipedia.org/wiki/Zobrist_hashing
///    
/// </summary>
public class ZOB64 : HashAlgorithm
{
    private readonly ulong      starthash = 0x391615744853B307;
    private          ulong[]    _table;
    private          ulong      hash;
    private          uint       hash32;
    private          ZOB32State zhs;
    public ZOB64()
    {
        hash = starthash;
        BuildTable(0x7965CBDDD4A9E7AF);
    }
    public override int HashSize => 64;
    public override void Initialize()
    {
        hash = starthash;
    }
    protected override void HashCore(byte[] bytes, int ibStart, int cbSize)
    {
        Hash64(bytes, ibStart, cbSize);
    }
    private static ulong RotateLeft(ulong value, int count)
    {
        return(value << count) | (value >> (64 - count % 64));
    }
    private unsafe void Hash64(byte[] bytes, int ibStart, int cbSize)
    {
        if(bytes == null)
            return;
        if(ibStart >= bytes.Length || cbSize > bytes.Length)
            return;
        var i = 1;
        fixed(byte* pb = bytes)
        {
            var nb = pb + ibStart;
            while(cbSize >= 1)
            {
                hash   ^= RotateLeft(_table[*nb], i++);
                nb     += 1;
                cbSize -= 1;
            }
        }
    }
    protected override byte[] HashFinal()
    {
        zhs.hash64 = hash;
        hash32     = zhs.hi ^ zhs.lo;
        return hash.GetBytes();
    }
    public void BuildTable(ulong seed)
    {
        var s1   = (int) seed;
        var s2   = (int) (seed >> 32);
        var rnd  = new Random(s1);
        var rnd1 = new Random(s2);
        var tt   = new DynHashSet32<ulong>();
        _table = new ulong[256];
        var u = new ZOB32State();
        for(var i = 0; i < 256; i++)
        {
            ulong v;
            do
            {
                u.hi = (uint) rnd.Next();
                u.lo = (uint) rnd1.Next();
                v    = u.hash64;
            } while(tt.Contains(v));
            tt.Add(v);
            _table[i] = v;
        }
    }
    [StructLayout(LayoutKind.Explicit)]
    public struct ZOB32State
    {
        [FieldOffset(0)] public ulong hash64;
        [FieldOffset(0)] public uint  lo;
        [FieldOffset(4)] public uint  hi;
    }
}

KSM128.cs

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

Re-Work of the Sha3 Keccak Sponge for 128 Bit Hashing

using System;
using System.Runtime.CompilerServices;
public class KSM128 : HashAlgorithmEx
{
    private readonly int _outputLength;
    private readonly int _rateBytes;
    private readonly ulong[] _roundConstants =
    {
        0x0000000000000001,
        0x0000000000008082,
        0x800000000000808A,
        0x8000000080008000,
        0x000000000000808B,
        0x0000000080000001,
        0x8000000080008081,
        0x8000000000008009,
        0x000000000000008A,
        0x0000000000000088,
        0x0000000080008009,
        0x000000008000000A,
        0x000000008000808B,
        0x800000000000008B,
        0x8000000000008089,
        0x8000000000008003,
        0x8000000000008002,
        0x8000000000000080,
        0x000000000000800A,
        0x800000008000000A,
        0x8000000080008081,
        0x8000000000008080,
        0x0000000080000001,
        0x8000000080008008
    };
    private readonly ulong[] _seed;
    private          int     _blockSize;
    private          int     _input;
    private          int     _output;
    private          byte[]  _result;
    private          ulong[] _state;
    public           int     HashLength;
    public           int     Rounds = 24;
    public KSM128(int size, int rounds = 24, ulong[] seed = null)
    {
        if (rounds > 24)
            throw new Exception($"Maximum rounds allowed is {24}");
        var MaxBR     = (64 >> 3) * 5;
        var sizeBytes = size >> 3;
        var rateBytes = MaxBR - (sizeBytes << 1);
        var MaxSize   = ((MaxBR - 8)       >> 1) << 3;
        if (rateBytes < 8)
            throw new Exception($"Maximum size allowed is {MaxSize} Bits with {128} bit Width specified. Specified Size is {size} Bits.");
        var outputLength = size >> 3;
        _rateBytes    = rateBytes;
        _outputLength = outputLength;
        HashLength    = outputLength;
        _seed         = seed;
    }
    public override void Initialize()
    {
        _blockSize = 0;
        _input     = 0;
        _output    = 0;
        _state     = new ulong[5];
        _result    = new byte[_outputLength];
        if (_seed != null && _seed[0] != 0)
        {
            for (var i = 0; i < _seed.Length && i < _state.Length; ++i)
                _state[i] = _seed[i];
            Permute(_state);
        }
    }
    public void Absorb(byte[] array, int start, int size)
    {
        while (size > 0)
        {
            _blockSize = Math.Min(size, _rateBytes);
            for (var index = start; index < _blockSize; ++index)
            {
                var num = Convert.ToByte(Buffer.GetByte(_state, index) ^ array[index + _input]);
                Buffer.SetByte(_state, index, num);
            }
            _input += _blockSize;
            size   -= _blockSize;
            if (_blockSize == _rateBytes)
            {
                Permute(_state);
                _blockSize = 0;
            }
        }
    }
    public byte[] Squeeze()
    {
        Buffer.SetByte(_state, _blockSize,     Convert.ToByte(Buffer.GetByte(_state, _blockSize)     ^ 6));
        Buffer.SetByte(_state, _rateBytes - 1, Convert.ToByte(Buffer.GetByte(_state, _rateBytes - 1) ^ 128));
        Permute(_state);
        var outputLength = _outputLength;
        while (outputLength > 0)
        {
            _blockSize = Math.Min(outputLength, _rateBytes);
            Buffer.BlockCopy(_state, 0, _result, _output, _blockSize);
            _output      += _blockSize;
            outputLength -= _blockSize;
            if (outputLength > 0)
                Permute(_state);
        }
        return _result;
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private void Permute(ulong[] state)
    {
        for (var round = 0; round < Rounds; ++round)
        {
            Theta(out var C0, state, out var C1, out var C2, out var C3, out var C4);
            RhoPi(state);
            Chi(ref C0, state, ref C1, ref C2, ref C3, ref C4);
            Iota(round, state);
        }
    }
    private static void Theta(out ulong C0, ulong[] state, out ulong C1, out ulong C2, out ulong C3, out ulong C4)
    {
        C0 = state[0] ^ state[4];
        C1 = state[1] ^ state[0];
        C2 = state[2] ^ state[1];
        C3 = state[3] ^ state[2];
        C4 = state[4] ^ state[3];
        var D0 = Rol(C1, 1) ^ C4;
        var D1 = Rol(C2, 1) ^ C0;
        var D2 = Rol(C3, 1) ^ C1;
        var D3 = Rol(C4, 1) ^ C2;
        var D4 = Rol(C0, 1) ^ C3;
        state[0] ^= D0;
        state[1] ^= D1;
        state[2] ^= D2;
        state[3] ^= D3;
        state[4] ^= D4;
    }
    private static void RhoPi(ulong[] state)
    {
        var a = Rol(state[1], 1);
        state[1] = Rol(state[4], 44);
        state[4] = Rol(state[3], 43);
        state[3] = Rol(state[2], 14);
        state[4] = Rol(state[1], 21);
        state[2] = a;
    }
    private void Iota(int round, ulong[] state)
    {
        state[0] ^= _roundConstants[round];
    }
    private static void Chi(ref ulong C0, ulong[] state, ref ulong C1, ref ulong C2, ref ulong C3, ref ulong C4)
    {
        C0       = state[0] ^ (~state[1] & state[2]);
        C1       = state[1] ^ (~state[2] & state[3]);
        C2       = state[2] ^ (~state[3] & state[4]);
        C3       = state[3] ^ (~state[4] & state[0]);
        C4       = state[4] ^ (~state[0] & state[1]);
        state[0] = C0;
        state[1] = C1;
        state[2] = C2;
        state[3] = C3;
        state[4] = C4;
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static ulong Rol(ulong x, byte y)
    {
        return (x << y) | (x >> (64 - y));
    }
    protected override void HashCore(byte[] array, int ibStart, int cbSize)
    {
        Initialize();
        Absorb(array, ibStart, cbSize);
    }
    protected override byte[] HashFinal()
    {
        return Squeeze();
    }
}

CRC64cs

Posted on August 6, 2020Tags ,   Leave a comment on CRC64cs

Standard CRC 64

using System;
using System.Globalization;
using System.Security.Cryptography;
using System.Text;
public class CRC64 : HashAlgorithm
{
    /// <summary>
    ///     https://en.wikipedia.org/wiki/Polynomial_representations_of_cyclic_redundancy_checks
    /// </summary>
    public enum PolyType : ulong
    {
        ECMA182 = 0xD800000000000000,
        ISOPoly = 0xC96C5795D7870F42
    }
    private const  ulong   Seed = 0x0;
    private static ulong[] _table;
    private        ulong   _hash;
    public CRC64(PolyType pt = PolyType.ECMA182)
    {
        HashSizeValue = 64;
        InitializeTable((ulong) pt);
        Initialize();
    }
    public override void Initialize()
    {
        _hash = Seed;
    }
    protected override void HashCore(byte[] data, int start, int size)
    {
        State = 1;
        for (var i = start; i < start + size; i++)
            unchecked
            {
                _hash = (_hash >> 8) ^ _table[(data[i] ^ _hash) & 0xff];
            }
    }
    protected override byte[] HashFinal()
    {
        HashValue = UInt64ToBigEndianBytes(_hash);
        State     = 0;
        _hash     = Seed;
        return HashValue;
    }
    private static byte[] UInt64ToBigEndianBytes(ulong value)
    {
        var result = BitConverter.GetBytes(value);
        if (BitConverter.IsLittleEndian)
            Array.Reverse(result);
        return result;
    }
    public static string ToHex(byte[] data)
    {
        var builder = new StringBuilder();
        foreach (var item in data)
            builder.Append(item.ToString("X2", CultureInfo.InvariantCulture));
        return builder.ToString();
    }
    private static void InitializeTable(ulong polynomial)
    {
        _table = new ulong[256];
        for (var i = 0; i < 256; ++i)
        {
            var entry = (ulong) i;
            for (var j = 0; j < 8; ++j)
                if ((entry & 1) == 1)
                    entry = (entry >> 1) ^ polynomial;
                else
                    entry = entry >> 1;
            _table[i] = entry;
        }
    }
}

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;
    }
}

ComparerEx.cs

Posted on August 4, 2020  Leave a comment on ComparerEx.cs

Custom Comparer using mapped Hashing

using System;
using System.Collections.Generic;

[Serializable]
public class ComparerEx<T> : IEqualityComparer<T>
{
    private static Type _type;
    private static Mapping64BitToHash32Bit Hash;
    public bool Equals(T x, T y)
    {
        if (x == null || y == null)
            return false;
        if (_type == null)
            _type = x.GetType();
        if (_type.IsArray)
        {
            var xb = x.GetBytesObject(_type);
            var yb = y.GetBytesObject(_type);
            return xb.Compare(yb);
        }
        return x.Equals(y);
    }
    public unsafe int GetHashCode(T obj)
    {
        if (_type == null) _type = obj.GetType();
        if (Hash  == null) Hash  = new Mapping64BitToHash32Bit();
        var objB   = obj.GetBytesObject(_type);
        return Hash.ComputeHash(objB).ToInt();
    }
}

SizeHelper.cs

Posted on August 3, 2020  Leave a comment on SizeHelper.cs

Use to Grow an Array in a Generic List

using System;
using System.Collections.Generic;
using Microsoft.VisualBasic.Devices;
public class SizeHelper<T>
{
    private static readonly FixedIntXPrimality bp = new FixedIntXPrimality(64);
    private readonly        int                AllocatedSizeLimit;
    public                  int[]              Curve;
    private                 int                Resizes;
    public SizeHelper()
    {
        var measure   = new MeasureSize<T>();
        var sizeOfOne = measure.GetByteSize();
        var am        = new ComputerInfo().AvailablePhysicalMemory;
        AllocatedSizeLimit = (int) ((long) am / sizeOfOne);
    }
    public int GetNewSize(int currentSize)
    {
        Resizes++;
        var minS = currentSize * 2;
        if (Curve == null)
            BuildCurve(minS);
        foreach (var v in Curve)
            if (v > minS)
                return v;
        var nv = GetNextValue(minS);
        return nv != -1 ? nv : int.MaxValue;
    }
    private int GetNextValue(int currentValue)
    {
        for (var value = currentValue | 1; value < AllocatedSizeLimit; value += 16384 )
        {
            if (value < 0)
                break;
            if (bp.IsPrime(value))
                return value + 1;
        }
        return -1;
    }
    private void BuildCurve(int Size)
    {
        int Sizer(int oldSize)
        {
            try
            {
                oldSize = (int) (uint) oldSize;
                var log     = Math.Log(oldSize);
                var inv     = 1.0 / log * 4;
                var newSize = oldSize   * (1.0 + inv);
                return (int) (uint) newSize;
            }
            catch
            {
                return AllocatedSizeLimit;
            }
        }
        var curlst = new List<int>();
        var value  = Size | 1;
        do
        {
            value = Sizer(value);
            if (value < 0)
                break;
            if (value < AllocatedSizeLimit)
                curlst.Add(value);
        } while (value < AllocatedSizeLimit);
        Curve = curlst.ToArray();
        var dl   = new List<int>();
        var last = 0;
        for (var i = 0; i < Curve.Length; ++i)
        {
            if (i > 0)
                last = Curve[i - 1];
            var v = Curve[i];
            dl.Add(v - last);
        }
        var str = "";
        foreach (var v in dl)
            str += $"{v},";
    }
}