Grammar Composition System

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

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

#pragma warning disable 0420

public partial class LockFreeDictionary<K, V> : IDictionary<K, V>
	where K : IEquatable<K>
	where V : IEquatable<V>
{
	public partial class Config
	{
		/// <summary>
		/// Lock-free LIFO stack
		/// </summary>
		public partial struct Freelist
		{
			public Freelist(Config cfg)
			{
				this.cfg = cfg;
				this.m_head = unchecked((UInt32)FreeListTerminator);
			}

			internal const Int32 FreeListTerminator = unchecked((Int32)0xFFFFFFFE);
			const Int64 SequenceMask = unchecked((Int64)0xFFFFFFFF00000000);
			const Int64 SequenceIncrement = 0x0000000100000000;

			readonly Config cfg;
			Int64 m_head;

			/// <summary>
			/// Add an item to the free list
			/// </summary>
			public void AddIndexToFreeList(int gx_add)
			{
				Int64 new_head, head = AtomicRead64(ref m_head);
				while (true)
				{
					cfg.SetEntryNext(gx_add, (Int32)head);

					new_head = ((head + SequenceIncrement) & SequenceMask) | (UInt32)gx_add;

					if ((new_head = Interlocked.CompareExchange(ref m_head, new_head, head)) == head)
						return;

					head = new_head;
				}
			}

			/// <summary>
			/// Pick the first item from the free list.
			/// </summary>
			/// <returns><value>true</value> if an free slot is returned in <paramref name="gx_out"/>, 
			/// <value>false</value> otherwise.</returns>
			public bool TryGetFreeIndex(out int gx_out)
			{
				Int64 new_head, head = AtomicRead64(ref m_head);
				while (true)
				{
					int gx_next;
					while (true)
					{
						gx_out = (Int32)head;
						gx_next = cfg.GetEntryNext(gx_out);

						Int64 same_head = AtomicRead64(ref m_head);
						if (head == same_head)
							break;
						head = same_head;
					}

					if (gx_out == FreeListTerminator)
					{
						gx_out = -1;
						return false;
					}

					new_head = ((head + SequenceIncrement) & SequenceMask) | (UInt32)gx_next;

					if ((new_head = Interlocked.CompareExchange(ref m_head, new_head, head)) == head)
						return true;

					head = new_head;
				}
			}
		};
	};
};