Grammar Composition System

/src/branch/20101223-mtid-affinity-experiment/lockfreedictionary.cs

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&lt;T&gt;"/> 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;

		/// scale each EntryBlock to keep out of the large object heap
		int v = 85000 / Config.Entry.StructureSize;
		int r = 1;
		while ((v >>= 1) > 0)
			r++;
		m_entries_per_block_power = Math.Max(r - 1, 8);

		m_config = new Config(this, m_entries_per_block_power);
	}

	[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,

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

	const int DefaultCapacity = 35;

	/// <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>

	int c_processors;

	public Options m_options =
		//Options.DebugOutput|
		Options.None;

	public
		/*volatile*/ Config m_config;

	int m_entries_per_block_power;

	internal struct KeyInfo
	{
		internal int gx_found;
		internal int i_found;
		internal int gx_last;
		internal bool Found { get { return gx_found != -1; } }
	};

	uint _check_key(ref K key, out int mtid)
	{
		if (Config.Entry.f_key_null_check && key == null)
			throw new ArgumentNullException("key");

		mtid = -1;
		m_config.CheckAssist(ref mtid);

		/// hash zero indicates a freelist entry so ensure that it's not used
		uint h = (uint)key.GetHashCode();
		return h == 0 ? 1 : h;
	}

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	// atomic transactions
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	/// <param name="key"></param>
	/// <param name="in_value"></param>
	/// <returns></returns>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public V GetOrAdd(K key, V in_value)
	{
		int mtid;
		uint h = _check_key(ref key, out mtid);

		while (true)
		{
			Config.BucketList.BucketHead bh;
			bool f;
			V out_value;
			if (m_config.m_buckets.GetBucketHead(ref mtid, h, out bh) && bh.TryGetValueForKey(key, out f, out out_value))
			{
				/// get
				if (f)
				{
					if (mtid != -1) m_config.free_lists[mtid] = m_config.free_lists_x[mtid];
					return out_value;
				}

				/// add
				if (bh.TryInsertFirstItem(ref mtid, h, ref key, ref in_value))
				{
					bh.Config.IncrementCountAndCheck(ref mtid);
					if (mtid != -1) m_config.free_lists[mtid] = m_config.free_lists_x[mtid];
					return in_value;
				}
			}
		}
	}

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	/// <param name="key"></param>
	/// <param name="value"></param>
	/// <returns></returns>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public bool TryAdd(K key, V value)
	{
		int mtid;
		uint h = _check_key(ref key, out mtid);

		while (true)
		{
			Config.BucketList.BucketHead bh;
			if (!m_config.m_buckets.GetBucketHead(ref mtid, h, out bh))
				continue;

			bool f;
			if (!bh.TryContainsKey(key, out f))
				continue;

			if (f)
			{
				if (mtid != -1) m_config.free_lists[mtid] = m_config.free_lists_x[mtid];
				return false;
			}

			if (bh.TryInsertFirstItem(ref mtid, h, ref key, ref value))
			{
				bh.Config.IncrementCountAndCheck(ref mtid);
				if (mtid != -1) m_config.free_lists[mtid] = m_config.free_lists_x[mtid];
				return true;
			}
		}
	}

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	/// <param name="key"></param>
	/// <param name="value"></param>
	/// <returns></returns>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public bool TryGetValue(K key, out V value)
	{
		int mtid;
		uint h = _check_key(ref key, out mtid);

		Config.BucketList.BucketHead bh;
		bool f_found;
		while (!m_config.m_buckets.GetBucketHead(ref mtid, h, out bh) || !bh.TryGetValueForKey(key, out f_found, out value))
			;
		if (mtid != -1) m_config.free_lists[mtid] = m_config.free_lists_x[mtid];
		return f_found;
	}

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	/// <param name="key"></param>
	/// <param name="val"></param>
	/// <returns></returns>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public bool TryRemove(K key, out V val)
	{
		int mtid;
		uint h = _check_key(ref key, out mtid);

		while (true)
		{
			Config.BucketList.BucketHead bh;
			if (!m_config.m_buckets.GetBucketHead(ref mtid, h, out bh))
				continue;

			int c = bh.CapturedEntryCount;
			if (c == 0)
				break;

			KeyInfo ki;
			if (!bh.TryFindKeyInfo(h, key, out ki, out val))
				continue;

			if (!ki.Found)
				break;

			TryResult tr = TryResult.Impossible;
			if (c == 1)
			{
				/// remove the only one
				ki.gx_last = -1;
				/// continues below...
			}
			else if (ki.i_found == 0 || (tr = Config.BucketList.BucketHead.IfDirectRotateToFront(ref bh, ki.gx_last, ki.gx_found)) != TryResult.Impossible)
			{
				if (tr == TryResult.Expired)
					continue;

				/// remove the first one
				int offs;
				ki.gx_last = bh.Config.GetBlock(ki.gx_found, out offs)[offs].gx_next;
				/// TryUpdate incorporates data dependence on gx, no need for acquire fence
				/// continues below...
			}
			else if (ki.i_found == c - 1 || Config.BucketList.BucketHead.TryRotateToEnd(ref mtid, ref bh, ki.gx_last, ki.i_found))
			{
				/// remove the last one by decrementing the count
				ki.gx_last = bh.CapturedFirstEntryIndex;
				/// continues below...
			}
			else
				continue;

			/// ...final update
			if (bh.TryUpdateHead(ki.gx_last, c - 1))
			{
				bh.Config.ReleaseIndex(ref mtid, ki.gx_found);
				Interlocked.Decrement(ref bh.Config.m_count);
				if (mtid != -1) m_config.free_lists[mtid] = m_config.free_lists_x[mtid];
				return true;
			}
		}
		/// nothing to remove
		if (mtid != -1) m_config.free_lists[mtid] = m_config.free_lists_x[mtid];
		val = default(V);
		return false;
	}

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	/// <param name="key"></param>
	/// <param name="in_value"></param>
	/// <param name="cmp_value"></param>
	/// <returns></returns>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public bool TryUpdate(K key, V in_value, V cmp_value)
	{
		int mtid;
		uint h = _check_key(ref key, out mtid);

		while (true)
		{
			Config.BucketList.BucketHead bh;
			if (!m_config.m_buckets.GetBucketHead(ref mtid, h, out bh))
				continue;

			int c = bh.CapturedEntryCount;
			if (c == 0)
			{
				if (mtid != -1) m_config.free_lists[mtid] = m_config.free_lists_x[mtid];
				return false;
			}

			V cur_val;
			KeyInfo ki;
			if (!bh.TryFindKeyInfo(h, key, out ki, out cur_val))
				continue;

			if (!ki.Found)
			{
				if (mtid != -1) m_config.free_lists[mtid] = m_config.free_lists_x[mtid];
				return false;
			}

			if (!Config.Entry.CompareValues(cur_val, cmp_value))
			{
				if (mtid != -1) m_config.free_lists[mtid] = m_config.free_lists_x[mtid];
				return false;
			}

			Config cfg = bh.Config;
			if ((cfg.d.m_options & Options.CheckForVacuousValueUpdates) > 0 && Config.Entry.CompareValues(in_value, cur_val))
			{
				if (mtid != -1) m_config.free_lists[mtid] = m_config.free_lists_x[mtid];
				return true;
			}

			TryResult tr = TryResult.Impossible;
			int gx_next;
			if (c == 1)
			{
				gx_next = -1;
				/// continues below...
			}
			else if (ki.i_found == 0 || (tr = Config.BucketList.BucketHead.IfDirectRotateToFront(ref bh, ki.gx_last, ki.gx_found)) != TryResult.Impossible)
			{
				if (tr == TryResult.Expired)
					continue;

				int offs;
				gx_next = cfg.GetBlock(bh.CapturedFirstEntryIndex, out offs)[offs].gx_next;
				/// no acquire fence required on this read: e_update is not shared until the CompareExchange full fence
				/// in TryReplaceFirstOrShift
				/// continues below...
			}
			else if (ki.i_found == c - 1 || Config.BucketList.BucketHead.TryRotateToEnd(ref mtid, ref bh, ki.gx_last, ki.i_found))
			{
				gx_next = bh.CapturedFirstEntryIndex;
				/// continues below...
			}
			else
				continue;

			/// ...try e_update
			if (bh.TryReplaceFirstOrShift(ref mtid, h, gx_next, ref key, ref in_value))
			{
				cfg.ReleaseIndex(ref mtid, ki.gx_found);
				if (mtid != -1) m_config.free_lists[mtid] = m_config.free_lists_x[mtid];
				return true;
			}
		}
	}

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	/// <param name="key"></param>
	/// <param name="add_val_func"></param>
	/// <param name="update_val_func"></param>
	/// <returns></returns>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public V AddOrUpdate(K key, Func<K, V> add_val_func, Func<K, V, V> update_val_func)
	{
		if (key == null) 
			throw new ArgumentNullException("key");
		if (add_val_func == null)
			throw new ArgumentNullException("add_val_func");
		if (update_val_func == null)
			throw new ArgumentNullException("update_val_func");

		while (true)
		{
			V old_val;
			if (TryGetValue(key, out old_val))
			{
				V new_val = update_val_func(key, old_val);
				if (TryUpdate(key, new_val, old_val))
					return new_val;
			}
			else
			{
				V new_val = add_val_func(key);
				if (TryAdd(key, new_val))
					return new_val;
			}
		}
	}


	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	// 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 (!TryAdd(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 TryRemove(key, out _dont_need);
	}

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	/// <param name="key"></param>
	/// <returns></returns>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public V this[K key]
	{
		get
		{
			int mtid;
			uint h = _check_key(ref key, out mtid);

			Config.BucketList.BucketHead bh;
			V v;
			while (!m_config.m_buckets.GetBucketHead(ref mtid, h, out bh) || !bh.TryFindKeyThrow(key, out v))
				;
			if (mtid != -1) m_config.free_lists[mtid] = m_config.free_lists_x[mtid];
			return v;
		}
		set
		{
			int mtid;
			uint h = _check_key(ref key, out mtid);

			while (true)
			{
				Config.BucketList.BucketHead bh;
				if (!m_config.m_buckets.GetBucketHead(ref mtid, h, out bh))
					continue;

				int c = bh.CapturedEntryCount;
				if (c == 0)
					goto add_item;

				V cur_val;
				KeyInfo ki;
				if (!bh.TryFindKeyInfo(h, key, out ki, out cur_val))
					continue;

				if (!ki.Found)
					goto add_item;

				Config cfg = bh.Config;
				if ((cfg.d.m_options & Options.CheckForVacuousValueUpdates) > 0 && Config.Entry.CompareValues(cur_val, value))
				{
					if (mtid != -1) m_config.free_lists[mtid] = m_config.free_lists_x[mtid];
					return;
				}

				TryResult tr = TryResult.Impossible;
				int gx_next;
				if (c == 1)
				{
					gx_next = -1;
					/// continues below...
				}
				else if (ki.i_found == 0 || (tr = Config.BucketList.BucketHead.IfDirectRotateToFront(ref bh, ki.gx_last, ki.gx_found)) != TryResult.Impossible)
				{
					if (tr == TryResult.Expired)
						continue;

					/// This will be a replace-first operation on the bucket
					int offs;
					gx_next = cfg.GetBlock(bh.CapturedFirstEntryIndex, out offs)[offs].gx_next;
					/// no acquire fence required on this read: whatever value is read into e_update.gx_next is not published until 
					/// after the full fence in TryReplaceFirstOrShift->TryUpdate->CompareExchange, and its correctness depends only
					/// upon the success of the CMPEXCHG
					/// continues below...
				}
				else if (ki.i_found == c - 1 || Config.BucketList.BucketHead.TryRotateToEnd(ref mtid, ref bh, ki.gx_last, ki.i_found))
				{
					/// This will be a shift operation on the bucket
					gx_next = bh.CapturedFirstEntryIndex;
					/// continues below...
				}
				else
					continue;

				/// ...replace first or shift. In either case, the count remains the same.
				if (bh.TryReplaceFirstOrShift(ref mtid, h, gx_next, ref key, ref value))
				{
					cfg.ReleaseIndex(ref mtid, ki.gx_found);
					if (mtid != -1) m_config.free_lists[mtid] = m_config.free_lists_x[mtid];
					return;
				}
				continue;

			add_item:
				/// try to add the item
				if (bh.TryInsertFirstItem(ref mtid, h, ref key, ref value))
				{
					bh.Config.IncrementCountAndCheck(ref mtid);
					if (mtid != -1) m_config.free_lists[mtid] = m_config.free_lists_x[mtid];
					return;
				}
			}
		}
	}

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <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)
	{
		int mtid;
		uint h = _check_key(ref key, out mtid);

		Config.BucketList.BucketHead bh;
		bool f;
		while (!m_config.m_buckets.GetBucketHead(ref mtid, h, out bh) || !bh.TryContainsKey(key, out f))
			;
		if (mtid != -1) m_config.free_lists[mtid] = m_config.free_lists_x[mtid];
		return f;
	}

	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();
			if (mtid != -1) m_config.free_lists[mtid] = m_config.free_lists_x[mtid];
			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)
	{
		if (!TryAdd(item.Key, 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)
	{
		V _dont_need;
		return TryRemove(item.Key, 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, m_entries_per_block_power);
	}

	/// <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)
	{
		int mtid;
		K k = item.Key;
		uint h = _check_key(ref k, out mtid);

		Config.BucketList.BucketHead bh;
		bool f_found;
		V v;
		while (!m_config.m_buckets.GetBucketHead(ref mtid, h, out bh) || !bh.TryGetValueForKey(item.Key, out f_found, out v))
			;
		if (mtid != -1) m_config.free_lists[mtid] = m_config.free_lists_x[mtid];
		return f_found && Config.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();
	}
};