Grammar Composition System

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

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

#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>
			/// Atomic (tear-free on x86) and volatile (cached-through on x86 and x64) access to m_head
			/// </summary>
			Int64 Head
			{
				get
				{
					if (IntPtr.Size == 4)
						return Interlocked.CompareExchange(ref m_head, 0, 0);
					Int64 h = m_head;
					Thread.MemoryBarrier();
					return h;
				}
			}

			/// <summary>
			/// Add an item to the free list
			/// </summary>
			public void AddIndexToFreeList(int gx_add)
			{
				Int64 new_head, head = 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 index is returned in <paramref name="gx_out"/>, 
			/// <value>false</value> otherwise.</returns>
			public bool TryGetFreeIndex(out int gx_out)
			{
				Int64 same_head, new_head, head = Head;
				while (true)
				{
					int gx_next;
					while (true)
					{
						gx_out = (Int32)head;
						gx_next = cfg.GetNextHot(gx_out);

						if (head == (same_head = 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;
				}
			}
		};
	};
};