Grammar Composition System

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

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


public partial class LockFreeDictionary<K, V> : IDictionary<K, V>
	where K : IEquatable<K>
	where V : IEquatable<V>
{
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <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(K key, V value)
	{
		uint h = _check_key(key);

		Config.BucketList.BucketHead bh;
		EntryBlock.Entry e_new = new EntryBlock.Entry(0, h, key, value);
		while (true)
		{
			if (m_config.m_buckets.GetBucketHead(h, out bh))
			{
				bool f_contains;
				if (bh.TryChainContainsKey(h, key, out f_contains))
				{
					if (f_contains)
						return false;

					if (bh.TryInsertFirstItem(ref e_new))
						break;
				}
			}
		}

		Config cfg_used = bh.Config;
		int c = Interlocked.Increment(ref cfg_used.m_count);
		if (c > cfg_used.m_buckets.BucketCount || bh.CapturedSlotCount > Config.BucketList.BucketHead.SlotsThreshold)
		{
			Config.BucketListPrimary blp = cfg_used.m_buckets as Config.BucketListPrimary;
			if (blp != null)
				blp.InitiateBucketResize();
		}
		return true;
	}

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	bool _try_get_remove_update(Op op, K key, ref V in_value, out V out_value)
	{
		uint h = _check_key(key);

	sync_restart:
		Config.BucketList.BucketHead bh;
		if (!m_config.m_buckets.GetBucketHead(h, out bh))
			goto sync_restart;

		Config cfg = bh.Config;
		int c = bh.CapturedSlotCount;
		int gx = bh.CapturedFirstSlotIndex;

		for (int i = 0; i < c; i++)
		{
			EntryBlock.Entry e;
			cfg.GetEntryLoose(gx, out e);
			if (bh.IsExpired)
				goto sync_restart;

			if (e.hash == h && e.key.Equals(key))
			{
				if (op == Op.Update)
				{
					if ((cfg.dict.m_options & Options.CheckForVacuousValueUpdates) == 0 || !e.value.Equals(in_value))
						cfg.SetEntryValueReadback(gx, ref in_value);
					out_value = in_value;
				}
				else
				{
					/// retrieve the value for the caller
					out_value = e.value;
					if (op == Op.Remove)
					{
						/// easy way #1: removing the first one: change the header link and the decrement the count
						if (i == 0)
						{
							if (!bh.TryUpdate(e.gx_next, c - 1))
								goto sync_restart;

							cfg.ReleaseIndex(gx);
						}
						else if (i == c - 1)
						{
							/// easy way #2: removing the last one: just decrement the count
							if (!bh.TryUpdate(bh.CapturedFirstSlotIndex, c - 1))
								goto sync_restart;

							cfg.ReleaseIndex(gx);
						}
						else
						{
							/// hard way: copy nodes from 0..i-1
							int gx_head, gx_tail;
							if (!cfg.CopyChain(bh, i, out gx_head, out gx_tail))
								goto sync_restart;

							cfg.SetEntryNext(gx_tail, e.gx_next);

							if (!bh.TryUpdate(gx_head, c - 1))
							{
								cfg.ReleaseChain(gx_head, i);
								goto sync_restart;
							}

							/// success: release the old chain up to and including the entry being removed. The
							/// new chain is re-using the rest
							cfg.ReleaseChain(bh.CapturedFirstSlotIndex, i + 1);
						}
						Interlocked.Decrement(ref cfg.m_count);
					}
				}
				return true;
			}

			gx = e.gx_next;
		}

		out_value = default(V);
		return false;
	}

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	bool _try_update_atomic(K key, ref V in_value, ref V cmp_value)
	{
		uint h = _check_key(key);

	sync_restart:
		Config cfg = m_config.dict.m_config;
		Config.BucketList.BucketHead bh;
		if (!cfg.m_buckets.GetBucketHead(h, out bh))
			goto sync_restart;

		int c = bh.CapturedSlotCount;
		int gx = bh.CapturedFirstSlotIndex;

		for (int i = 0; i < c; i++)
		{
			EntryBlock.Entry e;
			cfg.GetEntryLoose(gx, out e);
			if (bh.IsExpired)
				goto sync_restart;

			if (e.hash == h && e.key.Equals(key))
			{
				/// value types cannot use compareexchange of course

				if (i == 0)
				{
					/// we make no ordering guarantees so it's ok to exit
					if (!e.value.Equals(cmp_value))
						return false;
					if ((cfg.dict.m_options & Options.CheckForVacuousValueUpdates) > 0 && cmp_value.Equals(in_value))
						return true;

					/// replace first one: easy case
					//			e.value = in_value;
					//		EntryBlock.SlotAddr sa_new = cfg.GetUnusedSlot();
					//	sa_new.StoreEntry(ref e);
					//if (!bh.TryUpdate())
					//goto sync_restart;

					//cfg.ReleaseSlot(sa);
				}
				else
				{
					/// for all others, build new chain
				}

				return true;
			}

			gx = e.gx_next;
		}
		return false;
	}


	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	uint _check_key(K key)
	{
		if (f_null_check && key == null)
			throw new ArgumentNullException("key");

		return (uint)key.GetHashCode();
	}
};