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