Grammar Composition System

/src/branch/20101217-lock-free-dictionary/internal.cs

using System;
using System.Diagnostics;
using System.Collections.Generic;
using System.Threading;


public partial class LockFreeDictionary<K, V> : IDictionary<K, V>
	where K : IEquatable<K>
	where V : IEquatable<V>
{
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	uint _check_key(ref K key, out int mtid)
	{
		if (Config.EntryBlock.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;
	}

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// Obtain a chain head that doesn't contain the key and attempt to atomically insert the new Entry into it.
	/// If the atomic operation fails, start over.
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	bool _try_add(ref K key, V value)
	{
		int mtid;
		uint h = _check_key(ref key, out mtid);

		Config.EntryBlock.Entry e_new = new Config.EntryBlock.Entry(h, key, value);
		while (true)
		{
			Config.BucketList.BucketHead bh;
			if (!m_config.m_buckets.GetBucketHead(ref mtid, h, out bh))
				continue;

			int gx;
			if (!bh.TryFindKey(h, key, out gx))
				continue;

			if (gx != -1)
				return false;

			if (bh.TryInsertFirstItem(ref mtid, ref e_new))
			{
				bh.Config.IncrementCountAndCheck(ref mtid);
				return true;
			}
		}
	}

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// Obtain a chain head that doesn't contain the key and attempt to atomically insert the new Entry into it.
	/// If the atomic operation fails, start over.
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	V _transact_get_add(ref K key, V in_value)
	{
		int mtid;
		uint h = _check_key(ref key, out mtid);

		Config.EntryBlock.Entry e_new = new Config.EntryBlock.Entry(h, key, in_value);
		while (true)
		{
			Config.BucketList.BucketHead bh;
			int gx;
			if (m_config.m_buckets.GetBucketHead(ref mtid, h, out bh) && bh.TryFindKey(h, key, out gx))
			{
				/// get
				if (gx != -1)
				{
					V out_value;
					if (bh.TryGetValue(gx, out out_value))
						return out_value;
				}

				/// add
				if (bh.TryInsertFirstItem(ref mtid, ref e_new))
				{
					bh.Config.IncrementCountAndCheck(ref mtid);
					return in_value;
				}
			}
		}
	}


	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	bool _try_get(ref K key, out V out_value)
	{
		int mtid;
		uint h = _check_key(ref key, out mtid);

		while (true)
		{
			Config.BucketList.BucketHead bh;
			int gx;
			if (m_config.m_buckets.GetBucketHead(ref mtid, h, out bh) && bh.TryFindKey(h, key, out gx))
			{
				if (gx == -1)
				{
					out_value = default(V);
					return false;
				}

				if (bh.TryGetValue(gx, out out_value))
					return true;
			}
		}
	}


	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	bool _try_remove(ref K key, out V out_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)
				break;

			int gx_found, i, gx;
			if (!bh.TryFindKey(h, ref key, out gx_found, out i, out gx))
				continue;

			if (gx_found == -1)
				break;

			if (!bh.TryGetValue(gx_found, out out_value))
				continue;

			TryResult tr = TryResult.Impossible;
			if (c == 1)
			{
				/// remove the only one
				gx = -1;
				/// continues below...
			}
			else if (i == 0 || (tr = bh.CanCarouselTo(gx, gx_found, ref bh)) != TryResult.Impossible)
			{
				if (tr == TryResult.Expired)
					continue;

				/// remove the first one
				gx = bh.Config.GetNextHot(gx_found);
				/// continues below...
			}
			else if (i == c - 1 || bh.TryRotateToEnd(ref mtid, gx, i, ref bh))
			{
				/// remove the last one by decrementing the count
				gx = bh.CapturedFirstEntryIndex;
				/// continues below...
			}
			else
				continue;

			/// ...final update
			if (bh.TryUpdate(gx, c - 1))
			{
				bh.Config.ReleaseIndex(ref mtid, gx_found);
				Interlocked.Decrement(ref bh.Config.m_count);
				return true;
			}
		}
		/// nothing to remove
		out_value = default(V);
		return false;
	}

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	bool _try_update(ref K key, ref V value)
	{
		int mtid;
		uint h = _check_key(ref key, out mtid);

		Config.EntryBlock.Entry e_update = new Config.EntryBlock.Entry(h, key, value);
		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)
				return false;

			int gx_found, i, gx_last;
			if (!bh.TryFindKey(h, ref key, out gx_found, out i, out gx_last))
				continue;

			if (gx_found == -1)
				return false;

			Config cfg = bh.Config;
			if ((cfg.d.m_options & Options.CheckForVacuousValueUpdates) > 0)
			{
				V cur_val;
				if (bh.TryGetValue(gx_found, out cur_val) && Config.EntryBlock.Entry.CompareValues(cur_val, value))
					return true;
			}

			TryResult tr = TryResult.Impossible;
			if (c == 1)
			{
				e_update.gx_next = -1;
				/// continues below...
			}
			else if (i == 0 || (tr = bh.CanCarouselTo(gx_last, gx_found, ref bh)) != TryResult.Impossible)
			{
				if (tr == TryResult.Expired)
					continue;

				e_update.gx_next = cfg.GetNextHot(bh.CapturedFirstEntryIndex);
				/// continues below...
			}
			else if (i == c - 1 || bh.TryRotateToEnd(ref mtid, gx_last, i, ref bh))
			{
				e_update.gx_next = bh.CapturedFirstEntryIndex;
				/// continues below...
			}
			else
				continue;

			/// ...try e_update
			if (bh.TryReplaceFirst(ref mtid, ref e_update))
			{
				cfg.ReleaseIndex(ref mtid, gx_found);
				return true;
			}
		}
	}


	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	bool _transact_update(ref K key, ref V in_value, ref V cmp_value)
	{
		int mtid;
		uint h = _check_key(ref key, out mtid);
		Config.EntryBlock.Entry e_update = new Config.EntryBlock.Entry(h, key, in_value);

		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)
				return false;

			int gx_found, i, gx_last;
			if (!bh.TryFindKey(h, ref key, out gx_found, out i, out gx_last))
				continue;

			if (gx_found == -1)
				return false;

			V cur_val;
			if (!bh.TryGetValue(gx_found, out cur_val))
				continue;

			if (!Config.EntryBlock.Entry.CompareValues(cur_val, cmp_value))
				return false;

			Config cfg = bh.Config;
			if ((cfg.d.m_options & Options.CheckForVacuousValueUpdates) > 0 && Config.EntryBlock.Entry.CompareValues(in_value, cur_val))
				return true;

			TryResult tr = TryResult.Impossible;
			if (c == 1)
			{
				e_update.gx_next = -1;
				/// continues below...
			}
			else if (i == 0 || (tr = bh.CanCarouselTo(gx_last, gx_found, ref bh)) != TryResult.Impossible)
			{
				if (tr == TryResult.Expired)
					continue;

				e_update.gx_next = cfg.GetNextHot(bh.CapturedFirstEntryIndex);
				/// continues below...
			}
			else if (i == c - 1 || bh.TryRotateToEnd(ref mtid, gx_last, i, ref bh))
			{
				e_update.gx_next = bh.CapturedFirstEntryIndex;
				/// continues below...
			}
			else
				continue;

			/// ...try e_update
			if (bh.TryReplaceFirst(ref mtid, ref e_update))
			{
				cfg.ReleaseIndex(ref mtid, gx_found);
				return true;
			}
		}
	}
};