using System;
using System.Diagnostics;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Linq;
#pragma warning disable 0420
/// <title>Lock-free and wait-free generic concurrent dictionary</title>
/// <author>Glenn Slayden http://www.glennslayden.com</author>
/// <date>December 2010</date>
/// <keywords>lock-free, wait-free, non-blocking, concurrent, associative array, dictionary, hash map, hash table</keywords>
/// <typeparam name="K">Type of the key that is used to retrieve a data item. All key instances must be distinct. For reference
/// type (object) keys and <seealso cref="Nullable<T>"/> keys, key instances may not be null. Value type key types should
/// support a low-collision <seealso cref="GetHashCode"/> implementation.</typeparam>
/// <typeparam name="V">Type of the data item that is associated with a key.</typeparam>
public partial class LockFreeDictionary<K, V> : IDictionary<K, V>
where K : IEquatable<K>
where V : IEquatable<V>
{
public LockFreeDictionary()
{
c_processors = Environment.ProcessorCount;
m_config = new Config(this);
}
[Flags]
public enum Options
{
None = 0,
/// Atomic update of dictionary values can be costly, but for some value types, equality comparisons are also costly.
/// Setting this flag elects that, when updating, value instances should be checked for equality against the existing
/// value for the key (if any) in order to possibly avoid transacting an atomic update.
CheckForVacuousValueUpdates = 0x00000001,
/// Entries are held in blocks, each of which is pre-allocated for a fixed number of entries. This fixed number of entries
/// per block can be calculated based on the number of entries that will cause the block to be allocated in the large object
/// heap. This calculation is approximate since it is based on both: implementation details of the GC, and; the marshaling
/// sizes--calculated when the dictionary is initialized--of the generic type arguments.
AttemptScaleToLargeObjectHeap = 0x00000002,
/// Enable the bucket table to be shrunk when the number of elements in the dictionary falls below half of what it
/// once was. This does not affect the size of the entry tables, which cannot be efficiently shrunk.
ShrinkBucketTable = 0x00000004,
DebugOutput = 0x00000008,
};
/// <summary>
/// updating of value types can have 3 options:
/// - unsafe
/// - non-atomic readback-after-write with full fence (but torn read is still possible, and can match the readback)
/// - atomic
/// </summary>
readonly int c_processors;
public Options m_options = Options.AttemptScaleToLargeObjectHeap;
public
volatile Config m_config;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Atomic operations
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public V GetOrAdd(K key, V value)
{
return _transact_get_add(ref key, value);
}
public bool TryAdd(K key, V value)
{
return _try_add(ref key, value);
}
public bool TryGetValue(K key, out V value)
{
return _try_get(ref key, out value);
}
public bool TryRemove(K key, out V value)
{
return _try_remove(ref key, out value);
}
public bool TryUpdate(K key, V newValue, V comparisonValue)
{
return _transact_update(ref key, ref newValue, ref comparisonValue);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// IDictionary<TKey, TValue>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// Although this member is thread-safe, the value should not be considered added if another thread could have removed
/// it during the time this function is returning.
/// </summary>
/// <param name="key"></param>
/// <param name="value"></param>
/// <exception cref="ArgumentException">An element with the same key already exists.</exception>
/// <exception cref="ArgumentNullException"><paramref name="key"/> cannot be null.</exception>
public void Add(K key, V value)
{
if (!_try_add(ref key, value))
throw new ArgumentException("An item with the same key has already been added.");
}
/// <summary>
/// Although this member is thread-safe, the result should be considered advisory if another thread could have re-inserted
/// an item with the same key by the time the return value is examined.
/// </summary>
public bool Remove(K key)
{
V _dont_need;
return _try_remove(ref key, out _dont_need);
}
public V this[K key]
{
get
{
V v;
if (!_try_get(ref key, out v))
throw new KeyNotFoundException();
return v;
}
set
{
if (!_try_update(ref key, ref value))
throw new KeyNotFoundException();
}
}
/// <summary>
/// Although this member is thread-safe, the result should be considered advisory if another thread could
/// have removed the item by the time the return value is examined.
/// </summary>
public bool ContainsKey(K key)
{
V _dont_need;
return _try_get(ref key, out _dont_need);
}
public ICollection<K> Keys
{
get
{
return new ReadOnlyCollection<K>(null);
}
}
public ICollection<V> Values
{
get
{
return new ReadOnlyCollection<V>(null);
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// ICollection<KeyValuePair<TKey,TValue>> follows
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// Although this property is thread-safe, the result should be considered advisory if another thread could have added or
/// removed items by the time the return value is examined.
/// </summary>
public int Count
{
get
{
int mtid = -1;
m_config.CheckAssist(ref mtid);
int c = m_config.m_count;
Thread.MemoryBarrier();
return c;
}
}
/// <summary>
/// Although this member is thread-safe, the item should not be considered added if another thread could have removed
/// it during the time this function is returning.
/// </summary>
/// <param name="item"></param>
void ICollection<KeyValuePair<K, V>>.Add(KeyValuePair<K, V> item)
{
K k = item.Key;
if (!_try_add(ref k, item.Value))
throw new ArgumentException("An item with the same key has already been added.");
}
/// <summary>
/// Although this member is thread-safe, the result should be considered advisory if another thread could have re-inserted
/// an item with the same key by the time the return value is examined.
/// </summary>
/// <param name="item"></param>
/// <returns></returns>
bool ICollection<KeyValuePair<K, V>>.Remove(KeyValuePair<K, V> item)
{
K k = item.Key;
V _dont_need;
return _try_remove(ref k, out _dont_need);
}
/// <summary>
/// Although this member is thread-safe, the dictionary should not be considered empty if another thread could have
/// added items to the dictionary during the time this function is returning. Changes that were initiated prior to
/// this call but which haven't completed yet may be applied to either before or after the clearing operation.
/// </summary>
public void Clear()
{
/// (no point in calling CheckAssist on the old config)
m_config = new Config(this);
}
/// <summary>
/// Although this member is thread-safe, the result should be considered advisory if another thread could
/// have removed the item by the time the return value is examined.
/// </summary>
/// <param name="item"></param>
/// <returns></returns>
bool ICollection<KeyValuePair<K, V>>.Contains(KeyValuePair<K, V> item)
{
K k = item.Key;
V v;
return _try_get(ref k, out v) && Config.EntryBlock.Entry.CompareValues(v, item.Value); ;
}
/// <summary>
/// Copy a snapshot of the dictionary contents to an array of key-value pairs.
/// </summary>
/// <param name="array"></param>
/// <param name="arrayIndex"></param>
void ICollection<KeyValuePair<K, V>>.CopyTo(KeyValuePair<K, V>[] array, int arrayIndex)
{
this.ToArray().CopyTo(array, arrayIndex);
}
/// <summary>
/// This property has the value 'true'
/// </summary>
bool ICollection<KeyValuePair<K, V>>.IsReadOnly
{
get { return true; }
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// IEnumerable<KeyValuePair<TKey,TValue>> follows
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public IEnumerator<KeyValuePair<K, V>> GetEnumerator()
{
return m_config.EnumerateKeyValuePairs();
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// IEnumerable follows
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
};