MSet15.cs

Hashing Set Class

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
[DebuggerDisplay("Count = {" + nameof(Count) + "}")]
[Serializable]
public class MSet15<T>
{
    private  int[]                _hashBuckets;
    internal IEqualityComparer<T> Comparer;
    internal int                  Position;
    internal Slot[]               Slots;
    public   bool                 SlowGrowth;
    public MSet15() : this(31, EqualityComparer<T>.Default)
    {
    }
    public MSet15(int size) : this(size, EqualityComparer<T>.Default)
    {
    }
    public MSet15(IEqualityComparer<T> comparer) : this(31, 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;
        Position     = -1;
    }
    public MSet15(IEnumerable<T> collection, IEqualityComparer<T> comparer)
    {
        if (comparer == null)
            comparer = EqualityComparer<T>.Default;
        var enumerable = collection as T[] ?? collection.ToArray();
        var size       = enumerable.Length;
        Comparer     = comparer;
        _hashBuckets = new int[size];
        Slots        = new Slot[size];
        Count        = 0;
        Position     = -1;
        foreach (var i in enumerable)
            Add(i);
    }
    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;
        Position              = Count;
        ++Count;
        return false;
    }

    public void AddRange(IEnumerable<T> collection)
    {
        foreach (var i in collection)
            Add(i);
    }
    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;
    }
    public bool Contains(T item)
    {
        return FindEntry(item, Comparer.GetHashCode(item) & int.MaxValue) != -1;
    }
    public T[] ToArray()
    {
        var newArray = new T[Count];
        using (var en = GetEnumerator())
        {
            var ptr = 0;
            while (en.MoveNext())
            {
                var value = en.Current;
                if (value == null)
                    break;
                newArray[ptr++] = value;
            }
            return newArray;
        }
    }
    private void Resize()
    {
        var newSize        = !SlowGrowth ? _hashBuckets.Length + _hashBuckets.Length / 4 * 3 : _hashBuckets.Length + 1;
        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;
    }
    public 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);
    }
    internal struct Slot
    {
        public int HashCode;
        public int Next;
        public T   Value;
    }
}

AcDictionary.cs

Support Dictionary for Hash Mapping

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
[DebuggerDisplay("Count = {Count}")]
[Serializable]
public class AcDictionary<TKey, TValue> : MonitorActionFuncWrapper, IEnumerable<KeyValuePair<TKey, TValue>>
{
    public MSet15<TKey> _keys;
    public TValue[]     _values;
    public AcDictionary() : this(101, EqualityComparer<TKey>.Default)
    {
    }
    public AcDictionary(int size) : this(size, EqualityComparer<TKey>.Default)
    {
    }
    public AcDictionary(int size, IEqualityComparer<TKey> comparer)
    {
        if (comparer == null)
            comparer = EqualityComparer<TKey>.Default;
        _keys          = new MSet15<TKey>(size);
        _values        = new TValue[size];
        _keys.Comparer = comparer;
    }
    public AcDictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection, IEqualityComparer<TKey> comparer = null)
    {
        if (comparer == null)
            comparer = EqualityComparer<TKey>.Default;
        _keys.Comparer = comparer;
        foreach (var kp in collection)
            Add(kp.Key, kp.Value);
    }
    public int Count => _keys.Count;
    public TValue this[TKey key]
    {
        get
        {
            var pos = _keys.FindEntry(key);
            return pos == -1 ? default : _values[pos];
        }
        set => Add(key, value);
    }
    public TValue[]                     Values        => _values;
    public KeyValuePair<TKey, TValue>[] KeyValuePairs => ToArray();
    public TKey[]                       Keys          => _keys.ToArray();
    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        return Lock(this, () =>
        {
            return GetEnum();
        });
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return Lock(this, () =>
        {
            return GetEnum();
        });
    }
    private IEnumerator<KeyValuePair<TKey, TValue>> GetEnum()
    {
        for (var i = 0; i < Count; i++)
            if (_keys.Slots[i].HashCode > 0)
                yield return new KeyValuePair<TKey, TValue>(_keys.Slots[i].Value, _values[i]);
    }
    public bool Add(TKey key, TValue value)
    {
        return Lock(this, () =>
        {
            if (!_keys.Add(key))
            {
                if (Values.Length != _keys.Slots.Length)
                {
                    var nValues = new TValue[_keys.Slots.Length];
                    Array.Copy(_values, nValues, _values.Length);
                    _values = nValues;
                }
                Values[_keys.Position] = value;
                return false;
            }
            Values[_keys.Position] = value;
            return true;
        });
    }
    public void Remove(TKey key)
    {
        Lock(this, () =>
        {
            var pos = _keys.FindEntry(key);
            if (pos != -1)
            {
                Values[pos] = default;
                _keys.Remove(key);
            }
        });
    }
    public bool ContainsKey(TKey key)
    {
        return Lock(this, () =>
        {
            return _keys.FindEntry(key) != -1;
        });
    }
    public bool ContainsValue(TValue value)
    {
        return Lock(this, () =>
        {
            var vab = value.GetBytes();
            foreach (var v in _values)
            {
                if (v == null)
                    continue;
                var vab1 = v.GetBytes();
                if (vab.Compare(vab1))
                    return true;
            }
            return false;
        });
    }
    public int FindKeyIndex(TKey key)
    {
        return Lock(this, () =>
        {
            return _keys.FindEntry(key);
        });
    }
    public KeyValuePair<TKey, TValue>[] ToArray()
    {
        return Lock(this, () =>
        {
            var array = new KeyValuePair<TKey, TValue>[Count];
            var idx   = 0;
            foreach (var k in _keys)
                if (_keys.FindEntry(k) != -1)
                {
                    var v = _values[_keys.Position];
                    array[idx] = new KeyValuePair<TKey, TValue>(k, v);
                    idx++;
                }
            return array;
        });
    }
    public void Clear()
    {
        Lock(this, () =>
        {
            _keys   = new MSet15<TKey>(_keys.Slots.Length);
            _values = new TValue[_keys.Slots.Length];
        });
    }
}
[SecuritySafeCritical]
    public static unsafe bool Compare(this byte[] a1, byte[] a2)
    {
        if (a1 == null && a2 == null)
            return true;
        if (a1 == null || a2 == null || a1.Length != a2.Length)
            return false;
        fixed (byte* p1 = a1, p2 = a2)
        {
            var   Len = a1.Length;
            byte* x1  = p1, x2 = p2;
            while (Len > 7)
            {
                if (*(long*) x2 != *(long*) x1)
                    return false;
                x1  += 8;
                x2  += 8;
                Len -= 8;
            }
            switch (Len % 8)
            {
                case 0:
                    break;
                case 7:
                    if (*(int*) x2 != *(int*) x1)
                        return false;
                    x1 += 4;
                    x2 += 4;
                    if (*(short*) x2 != *(short*) x1)
                        return false;
                    x1 += 2;
                    x2 += 2;
                    if (*x2 != *x1)
                        return false;
                    break;
                case 6:
                    if (*(int*) x2 != *(int*) x1)
                        return false;
                    x1 += 4;
                    x2 += 4;
                    if (*(short*) x2 != *(short*) x1)
                        return false;
                    break;
                case 5:
                    if (*(int*) x2 != *(int*) x1)
                        return false;
                    x1 += 4;
                    x2 += 4;
                    if (*x2 != *x1)
                        return false;
                    break;
                case 4:
                    if (*(int*) x2 != *(int*) x1)
                        return false;
                    break;
                case 3:
                    if (*(short*) x2 != *(short*) x1)
                        return false;
                    x1 += 2;
                    x2 += 2;
                    if (*x2 != *x1)
                        return false;
                    break;
                case 2:
                    if (*(short*) x2 != *(short*) x1)
                        return false;
                    break;
                case 1:
                    if (*x2 != *x1)
                        return false;
                    break;
            }
            return true;
        }
    }

BigArray.cs

Big Array Class Arrays Over 2GB Limit

Updated: Dec-14,2020

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading;
using Microsoft.VisualBasic.Devices;
[DebuggerDisplay("Count = {Count}")]
[Serializable]
public class BigArray<T> : MonitorActionFunc, IEnumerable<T>, IDisposable
{
    public const     int   ShiftCount  = 19;
    public const     int   Granularity = 1 << ShiftCount;
    private          bool  _disposed;
    private volatile T[][] _mdArray;
    private volatile Table _table = new Table();
    private volatile bool  _writing;
    public BigArray() : this(0)
    {
    }
    public BigArray(long size)
    {
        if (size < Granularity)
            size = Granularity;
        var i = 0;
        try
        {
            _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);
            var ms  = new MeasureSize<T>();
            var oas = ms.GetByteSize(Granularity);
            var am  = new ComputerInfo().AvailablePhysicalMemory;
            var rm  = (ulong) (oas * _table.NumberOfActiveArrays * Granularity);
            var maa = am / (ulong) (oas * Granularity);
            if (rm > am || (ulong) _table.NumberOfActiveArrays > maa)
                throw new Exception($"Requested memory {rm} exceeds available memory {am}");
            _mdArray = new T[maa][];
            for (i = 0; i < _table.NumberOfActiveArrays; ++i)
                _mdArray[i] = new T[Granularity];
            _writing = false;
        }
        catch (Exception ex)
        {
            throw new Exception($"Exception: {ex.Message}");
        }
    }
    public long Count
    {
        get
        {
            return Lock(_table.Count, () =>
            {
                return _table.Count;
            });
        }
    }
    public long Length
    {
        get
        {
            return Lock(_table.Length, () =>
            {
                return _table.Length;
            });
        }
    }
    public T this[long index]
    {
        get
        {
            while (_writing)
                new SpinWait().SpinOnce();
            if (index >= _table.Length)
                throw new Exception($"Getter: Index out of bounds, Index: '{index}' must be less than the Length: '{Length}'.");
            return _mdArray[index >> ShiftCount][index & (Granularity - 1)];
        }
        set
        {
            Lock(this, () =>
            {
                if (index + 1 > _table.Length)
                    ResizeArray();
                _writing                                                 = true;
                _mdArray[index >> ShiftCount][index & (Granularity - 1)] = value;
                _table.Count++;
                _writing = false;
            });
        }
    }
    public void Dispose()
    {
        Dispose(true);
    }
    IEnumerator<T> IEnumerable<T>.GetEnumerator()
    {
        return GetEnumerator();
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
    public void Add(T Item)
    {
        Lock(this, () =>
        {
            if (_table.Count + 1 > _table.Length)
                ResizeArray();
            _writing = true;
            var x = _table.Count >> ShiftCount;
            var y = _table.Count & (Granularity - 1);
            _mdArray[x][y] = Item;
            _table.Count++;
            _writing = false;
        });
    }
    private void ResizeArray()
    {
        try
        {
            Interlocked.Increment(ref _table.NumberOfActiveArrays);
            var val = (long) _table.NumberOfActiveArrays * Granularity;
            _table.Length = Interlocked.Read(ref val);
            var ms  = new MeasureSize<T>();
            var oas = ms.GetByteSize(Granularity);
            var am  = new ComputerInfo().AvailablePhysicalMemory;
            var rm  = (ulong) (oas * _table.NumberOfActiveArrays * Granularity);
            var maa = am / (ulong) (oas * Granularity);
            if (rm > am || (ulong) _table.NumberOfActiveArrays > maa)
                throw new Exception($"Requested memory {rm} exceeds available memory {am}");
            _mdArray                                  = new T[maa][];
            _mdArray[_table.NumberOfActiveArrays - 1] = new T[Granularity];
        }
        catch (Exception ex)
        {
            throw new Exception($"Exception: {ex.Message}");
        }
    }
    public void Clear()
    {
        Lock(this, () =>
        {
            _writing = true;
            for (var a = 0L; a < _table.NumberOfActiveArrays; a++)
                Array.Clear(_mdArray[a], 0, Granularity);
            _table.Count = 0;
            _writing     = false;
        });
    }
    public long IndexOf(T item)
    {
        return Lock(this, () =>
        {
            var i = 0L;
            for (; i < _table.NumberOfActiveArrays; i++)
            {
                while (_writing)
                    new SpinWait().SpinOnce();
                var pos = Array.IndexOf(_mdArray[i], item, 0);
                if (pos != -1)
                    return i * Granularity + pos;
            }
            return -1;
        });
    }
    public BigArray<T> Copy(long newsize)
    {
        return Lock(this, () =>
        {
            var temp = new BigArray<T>(newsize);
            for (var a = 0L; a < _table.NumberOfActiveArrays; a++)
            {
                while (_writing)
                    new SpinWait().SpinOnce();
                Array.Copy(_mdArray[a], temp._mdArray[a], Granularity);
            }
            temp._table.Count = Count;
            return temp;
        });
    }
    public void FromArray(T[][] array)
    {
        Lock(this, () =>
        {
            _table.NumberOfActiveArrays = array.GetUpperBound(0) + 1;
            var val = (long) _table.NumberOfActiveArrays * Granularity;
            _table.Length = Interlocked.Read(ref val);
            _mdArray      = new T[_table.NumberOfActiveArrays][];
            for (var i = 0; i < _table.NumberOfActiveArrays; ++i)
                _mdArray[i] = new T[Granularity];
            for (var a = 0L; a < _table.NumberOfActiveArrays; a++)
                Array.Copy(array[a], _mdArray[a], Granularity);
        });
    }
    public T[][] ToArray()
    {
        return Lock(this, () =>
        {
            var ta = new T[_table.NumberOfActiveArrays][];
            for (var i = 0; i < _table.NumberOfActiveArrays; ++i)
                ta[i] = new T[Granularity];
            for (var a = 0L; a < _table.NumberOfActiveArrays; a++)
                Array.Copy(_mdArray[a], ta[a], Granularity);
            return ta;
        });
    }
    private void Dispose(bool disposing)
    {
        if (!_disposed)
            if (disposing)
                _mdArray = null;
        _disposed = true;
    }
    public IEnumerator<T> GetEnumerator()
    {
        return Lock(this, () =>
        {
            return GetEnum();
        });
    }
    public IEnumerator<T> GetEnum()
    {
        for (var i = 0; i < Count; i++)
            yield return this[i];
    }
    private class Table
    {
        public          long Count;
        public          long Length;
        public volatile int  MaximumNumberOfArrays;
        public volatile int  NumberOfActiveArrays;
    }
}