Tag: Dictionary

CcDictionary.cs

Concurrent Dictionary Class without Blocking

Updated: July-27,2021

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading;
[DebuggerDisplay("Count = {" + nameof(Count) + "}")]
public class CcDictionary<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>
{
    private readonly int                     _size;
    private volatile int[]                   _activeThreads;
    private          DicA<TKey, TValue>[]    _array;
    private volatile int                     _bP;
    internal         IEqualityComparer<TKey> _comparer;
    public volatile  int                     NumberOfActiveThreads;
    public CcDictionary() : this(1024, null)
    {
    }
    public CcDictionary(int size) : this(size, null)
    {
    }
    public CcDictionary(int size, IEqualityComparer<TKey> comparer)
    {
        ThreadPool.GetMaxThreads(out var nW, out var nI);
        _array                = new DicA<TKey, TValue>[nW];
        _size                 = size;
        NumberOfActiveThreads = 0;
        _bP                   = 0;
        _activeThreads        = new int[Environment.ProcessorCount];
        _activeThreads.Fill(-1);
        if (comparer == null)
            _comparer = EqualityComparer<TKey>.Default;
        else
            _comparer = comparer;
    }
    public CcDictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection, int concurrencyLevel = 0)
    {
        ThreadPool.GetMaxThreads(out var nW, out var nI);
        _array = new DicA<TKey, TValue>[nW];
        var col = collection.ToList();
        _size                 = col.Count;
        NumberOfActiveThreads = 0;
        _bP                   = 0;
        _activeThreads        = new int[Environment.ProcessorCount];
        _activeThreads.Fill(-1);
        _comparer = EqualityComparer<TKey>.Default;
        var ccl = Environment.ProcessorCount;
        if (concurrencyLevel != 0)
            ccl = concurrencyLevel;
        col.AsParallel().WithDegreeOfParallelism(ccl).ForAll(i =>
        {
            Add(i.Key, i.Value);
        });
    }
    public int Count
    {
        get
        {
            var totalCount = 0;
            for (var i = 0; i < _activeThreads.Length; ++i)
                if (_activeThreads[i] != -1)
                    if (_array[_activeThreads[i]] != null)
                        totalCount += _array[_activeThreads[i]].Count;
            return totalCount;
        }
    }
    public TValue this[TKey key]
    {
        get
        {
           ProcessThread();
            var rv = FindKey(key);
            return rv.idx != -1 ? _array[rv.trd][key] : default;
        }
        set => Add(key, value, true);
    }
    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        return GetEnum();
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnum();
    }
    public bool TryGetValue(TKey key, out TValue value)
    {
        var (idx, trd) = FindKey(key);
        if (idx == -1)
        {
            value = default;
            return false;
        }
        value = _array[trd][key];
        return true;
    }
    public void Clear()
    {
        ThreadPool.GetMaxThreads(out var nW, out var nI);
        _array                = new DicA<TKey, TValue>[nW];
        NumberOfActiveThreads = 0;
        _bP                   = 0;
        _activeThreads        = new int[Environment.ProcessorCount];
        _activeThreads.Fill(-1);
    }
    public void AddRange(IEnumerable<KeyValuePair<TKey, TValue>> collection, int concurrencyLevel = 0)
    {
        var ccl = Environment.ProcessorCount;
        if (concurrencyLevel != 0)
            ccl = concurrencyLevel;
        collection.AsParallel().WithDegreeOfParallelism(ccl).ForAll(i =>
        {
            Add(i.Key, i.Value);
        });
    }
    public void Add(TKey key, TValue value, bool updateValue = false)
    {
        var id  = ProcessThread();
        var idx = FindKey(key);
        if (idx.idx == -1)
            _array[id].Add(key, value);
        else if (updateValue)
            _array[idx.trd].Values[idx.idx] = value;
    }
    private int ProcessThread()
    {
        var id = Thread.CurrentThread.ManagedThreadId;
        if (_array[id] == null)
        {
            _array[id] = new DicA<TKey, TValue>(_size, _comparer);
            Interlocked.Increment(ref NumberOfActiveThreads);
            if (_bP >= _activeThreads.Length)
            {
                var nAtA = new int[_activeThreads.Length << 1];
                nAtA.Fill(-1);
                for (var i = 0; i < _activeThreads.Length; ++i)
                    if (_activeThreads[i] != -1)
                        nAtA[i] = _activeThreads[i];
                _activeThreads = nAtA;
            }
            _activeThreads[_bP] = id;
            Interlocked.Increment(ref _bP);
        }
        return id;
    }
    public bool TryAdd(TKey key, TValue value)
    {
        Add(key, value);
        return true;
    }
    public bool ContainsKey(TKey key)
    {
        for (var i = 0; i < _activeThreads.Length; ++i)
            if (_activeThreads[i] != -1)
                if (_array[_activeThreads[i]] != null)
                    if (_array[_activeThreads[i]].ContainsKey(key))
                        return true;
        return false;
    }
    public bool ContainsValue(TValue value)
    {
        var eComparer = EqualityComparer<TValue>.Default;
        for (var i = 0; i < _activeThreads.Length; ++i)
            if (_activeThreads[i] != -1)
                if (_array[_activeThreads[i]] != null)
                    for (var j = 0; j < _array[_activeThreads[i]].Count; ++j)
                        if (eComparer.Equals(_array[_activeThreads[i]].Values[j], value))
                            return true;
        return false;
    }
    public (int idx, int trd) FindKey(TKey key)
    {
        for (var i = 0; i < _activeThreads.Length; ++i)
            if (_activeThreads[i] != -1)
                if (_array[_activeThreads[i]] != null)
                {
                    var idx = _array[_activeThreads[i]].FindKeyIndex(key);
                    if (idx != -1)
                        return (idx, _activeThreads[i]);
                }
        return (-1, -1);
    }
    public bool Remove(TKey key)
    {
        var (idx, trd) = FindKey(key);
        if (idx == -1)
            return false;
        _array[_activeThreads[trd]].Remove(key);
        return true;
    }
    private IEnumerator<KeyValuePair<TKey, TValue>> GetEnum()
    {
        foreach (var i in ToArray())
            yield return new KeyValuePair<TKey, TValue>(i.Key, i.Value);
    }
    public KeyValuePair<TKey, TValue>[] ToArray()
    {
        var totalCount = 0;
        for (var i = 0; i < _activeThreads.Length; ++i)
            if (_activeThreads[i] != -1)
                if (_array[_activeThreads[i]] != null)
                    totalCount += _array[_activeThreads[i]].Count;
        var ta  = new KeyValuePair<TKey, TValue>[totalCount];
        var ptr = 0;
        for (var i = 0; i < _activeThreads.Length; ++i)
            if (_activeThreads[i] != -1)
                if (_array[_activeThreads[i]] != null)
                    foreach (var v in _array[_activeThreads[i]])
                        ta[ptr++] = new KeyValuePair<TKey, TValue>(v.Key, v.Value);
        return ta;
    }
    public class DicA<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>
    {
        public MSet15<TKey> Keys;
        public int          Resizes;
        public TValue[]     Values;
        public DicA() : this(101, EqualityComparer<TKey>.Default)
        {
        }
        public DicA(int size) : this(size, EqualityComparer<TKey>.Default)
        {
        }
        public DicA(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 DicA(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 IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            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]);
        }
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
        public bool Add(TKey key, TValue value)
        {
            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;
                    Resizes++;
                }
                Values[Keys.Position] = value;
                return false;
            }
            Values[Keys.Position] = value;
            return true;
        }
        public void Remove(TKey key)
        {
            var pos = Keys.FindEntry(key);
            if (pos != -1)
            {
                Values[pos] = default;
                Keys.Remove(key);
            }
        }
        public bool ContainsKey(TKey key)
        {
            return Keys.FindEntry(key) != -1;
        }
        public int FindKeyIndex(TKey key)
        {
            return Keys.FindEntry(key);
        }
    }
}

ObjectDictionary.cs

Object Dictionary Single Associative Array, Searchable Keys and Values 

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
[DebuggerDisplay("Count = {Count}")]
[Serializable]
public class ObjectDictionary : MonitorActionFuncWrapper, IEnumerable<KeyValuePair<object, object>>
{
    public ObjectBase _keys;
    public ObjectBase _values;
    public ObjectDictionary() : this(101)
    {
    }
    public ObjectDictionary(int size)
    {
        _keys   = new ObjectBase(size);
        _values = new ObjectBase(size);
    }
    public ObjectDictionary(IEnumerable<KeyValuePair<object, object>> collection)
    {
        foreach (var kp in collection)
            Add(kp.Key, kp.Value);
    }
    public int Count => _keys.Count;
    public object this[object key]
    {
        get
        {
            var pos = _keys.GetObjectIndex(key, false);
            return pos.idx == -1 ? default : _values[pos.idx];
        }
        set => Add(key, value);
    }
    public object[]                       Values        => _values.ToArray();
    public KeyValuePair<object, object>[] KeyValuePairs => ToArray();
    public object[]                       Keys          => _keys.ToArray();
    public IEnumerator<KeyValuePair<object, object>> GetEnumerator()
    {
        return Lock(this, () =>
        {
            return GetEnum();
        });
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return Lock(this, () =>
        {
            return GetEnum();
        });
    }
    private IEnumerator<KeyValuePair<object, object>> GetEnum()
    {
        for (var i = 0; i < Count; i++)
            yield return new KeyValuePair<object, object>(_keys[i], _values[i]);
    }
    public bool Add(object key, object value)
    {
        return Lock(this, () =>
        {
            if (_keys.Contains(key) || _values.Contains(value))
                return false;
            
            var ka = _keys.Add(key);
            var va = _values.Add(value);

            if (ka || va)
            {
                int a = 1;
            }

            return ka && va;
        });
    }
    public void RemoveKey(object key)
    {
        var kidx = _keys.GetObjectIndex(key, false).idx;
        if (kidx != -1)
        {
            var keys   = _keys;
            var values = _values;
            Clear();
            for (var i = 0; i < keys.Count; ++i)
                if (i != kidx)
                    Add(keys[i], values[i]);
        }
    }
    public void RemoveValue(object value)
    {
        var vidx = _values.GetObjectIndex(value, false).idx;
        if (vidx != -1)
        {
            var keys   = _keys;
            var values = _values;
            Clear();
            for (var i = 0; i < keys.Count; ++i)
                if (i != vidx)
                    Add(keys[i], values[i]);
        }
    }
    public void RebuildLists()
    {
        var keys   = _keys;
        var values = _values;
        Clear();
        for (var i = 0; i < keys.Count; ++i)
            Add(keys[i], values[i]);
    }
    public bool ContainsKey(object key)
    {
        return Lock(this, () =>
        {
            return _keys.Contains(key);
        });
    }
    public bool ContainsValue(object value)
    {
        return Lock(this, () =>
        {
            return _values.Contains(value);
        });
    }
    public int FindKeyIndex(object key)
    {
        return Lock(this, () =>
        {
            return _keys.GetObjectIndex(key, false).idx;
        });
    }
    public int FindValueIndex(object value)
    {
        return Lock(this, () =>
        {
            return _values.GetObjectIndex(value, false).idx;
        });
    }
    public KeyValuePair<object, object>[] ToArray()
    {
        return Lock(this, () =>
        {
            var array = new KeyValuePair<object, object>[Count];
            for (var i = 0; i < Count; i++)
                array[i] = new KeyValuePair<object, object>(_keys[i], _values[i]);
            return array;
        });
    }
    public void Clear()
    {
        Lock(this, () =>
        {
            _keys   = new ObjectBase(_keys.Count);
            _values = new ObjectBase(_values.Count);
        });
    }
}

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

TinyDictionary.cs

A Small Dictionary Class

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
[DebuggerDisplay("Count = {Count}")]
[Serializable]
public class TinyDictionary<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>
{
    public MSet15<TKey> Keys;
    public int          Resizes;
    public TValue[]     Values;
    public TinyDictionary() : this(101, EqualityComparer<TKey>.Default)
    {
    }
    public TinyDictionary(int size) : this(size, EqualityComparer<TKey>.Default)
    {
    }
    public TinyDictionary(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 TinyDictionary(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 IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        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]);
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
    public bool Add(TKey key, TValue value)
    {
        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;
                Resizes++;
            }
            Values[Keys.Position] = value;
            return false;
        }
        Values[Keys.Position] = value;
        return true;
    }
    public void Remove(TKey key)
    {
        var pos = Keys.FindEntry(key);
        if (pos != -1)
        {
            Values[pos] = default;
            Keys.Remove(key);
        }
    }
    public bool ContainsKey(TKey key)
    {
        return Keys.FindEntry(key) != -1;
    }
    public int FindKeyIndex(TKey key)
    {
        return Keys.FindEntry(key);
    }
}