#define newthing
using System;
using System.Text;
using System.IO;
using System.Diagnostics;
using System.Collections.Generic;
using System.Threading;
using System.Threading.Tasks;
using System.Runtime.InteropServices;
using System.Linq;
#pragma warning disable 0420, 0414
public partial class LockFreeDictionary<K, V> : IDictionary<K, V>
where K : IEquatable<K>
where V : IEquatable<V>
{
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
[StructLayout(LayoutKind.Auto, Pack = 64)]
public partial class Config
{
int EntriesPerBlockPower;
int EntriesPerBlock;
int GlobalIndexMask;
int ResizeTrigger;
public Config(LockFreeDictionary<K, V> dict, int entries_per_block_power)
{
this.d = dict;
EntriesPerBlockPower = entries_per_block_power;
EntriesPerBlock = 1 << EntriesPerBlockPower;
GlobalIndexMask = EntriesPerBlock - 1;
ResizeTrigger = GlobalIndexMask & unchecked((int)0xFFFFFFF0);
entry_blocks = new Entry[0x10][];
entry_blocks[0] = new Entry[EntriesPerBlock];
#if newthing
free_lists = new Freelist[800];
free_lists_x = new Freelist[800];
for (int i = 0; i < free_lists.Length; i+=100)
{
free_lists_x[i] = free_lists[i] = new Freelist(this);
}
#else
free_lists = new Freelist[BucketList.HashFriendly((uint)dict.c_processors * 2)];
for (int i = 0; i < free_lists.Length; i++)
free_lists[i] = new Freelist(this);
#endif
m_buckets = new BucketListPrimary(this, DefaultCapacity);
}
internal LockFreeDictionary<K, V> d;
/// each EntryBlock stores a fixed number of entries
Entry[][] entry_blocks;
/// entries have a global index across all EntryBlocks
int m_gx_next;
/// a pair of bucket arrays that can be atomically swapped
internal volatile BucketList m_buckets;
/// the number of entries in the dictionary is maintained with interlocked operations
internal int m_count = 0;
/// a small number of free lists
internal Freelist[] free_lists;
internal Freelist[] free_lists_x;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
internal bool IsCurrent { get { return this == d.m_config; } }
internal BucketList ChangeBuckets(BucketList bl_old, BucketList bl_new)
{
BucketList bl_cur = Interlocked.CompareExchange(ref m_buckets, bl_new, bl_old);
return bl_cur == bl_old ? bl_new : bl_cur;
}
internal void CheckAssist(ref int mtid)
{
Config.BucketListResize blr = m_buckets as Config.BucketListResize;
if (blr != null)
blr._check_assist(ref mtid);
}
internal void RequestBucketResize(ref int mtid)
{
Config.BucketListPrimary blp = m_buckets as Config.BucketListPrimary;
if (blp != null)
blp.InitiateBucketResize(ref mtid);
}
internal void IncrementCountAndCheck(ref int mtid)
{
int c = Interlocked.Increment(ref m_count);
if (c > m_buckets.BucketCount)
RequestBucketResize(ref mtid);
}
internal IEnumerator<KeyValuePair<K, V>> EnumerateKeyValuePairs()
{
int mtid = -1;
for (int offs, i = 0; i < m_gx_next; i++)
{
Entry e = GetBlock(i, out offs)[offs]; /// todo: this is subject to torn reads
Thread.MemoryBarrier();
if (e.hash != Freelist.FreelistHash)
{
bool f;
BucketList.BucketHead bh;
do
m_buckets.GetBucketHead(ref mtid, e.hash, out bh); /// ignore config change
while (!bh.TryContainsKey(e.key, out f));
if (f)
yield return new KeyValuePair<K, V>(e.key, e.value);
}
}
}
#if newthing
int[] fl_affinity = new int[256];
Freelist GetFreelist(ref int mtid)
{
if (mtid != -1)
return free_lists_x[mtid];
int mid = (Thread.CurrentThread.ManagedThreadId & 0xFF) * 8;
int ix = fl_affinity[mid];
Freelist fl_use;
while ((fl_use = free_lists[ix]) == null || Interlocked.CompareExchange(ref free_lists[ix], null, fl_use) != fl_use)
{
if ((ix += 100) == free_lists.Length)
ix = 0;
}
mtid = fl_affinity[mid] = ix;
return fl_use;
}
#endif
/// <summary>
/// Get an unused entry index, either from one of the freelists, or by allocating a new one
/// </summary>
internal int GetUnusedIndex(ref int mtid)
{
Freelist fl_use;
#if newthing
fl_use = GetFreelist(ref mtid);
#else
if (mtid == -1)
mtid = Thread.CurrentThread.ManagedThreadId % free_lists.Length;
fl_use = free_lists[mtid];
#endif
int gx;
if (!fl_use.TryGetFreeIndex(out gx))
{
if ((uint)m_gx_next >= 0xFFFFFFF0)
throw new OverflowException("The dictionary already contains the amximum number of elements.");
gx = Interlocked.Increment(ref m_gx_next) - 1;
}
return gx;
}
/// <summary>
/// Add an entry index to one of the the freelists
/// </summary>
internal void ReleaseIndex(ref int mtid, int gx)
{
Freelist fl_use;
#if newthing
fl_use = GetFreelist(ref mtid);
#else
if (mtid == -1)
mtid = Thread.CurrentThread.ManagedThreadId % free_lists.Length;
fl_use = free_lists[mtid];
#endif
fl_use.AddIndexToFreeList(gx);
}
internal Entry[] GetBlock(int gx, out int offs)
{
int i_block = (gx >> EntriesPerBlockPower);
offs = gx & GlobalIndexMask;
Entry[] eb = entry_blocks[i_block];
if (eb == null)
{
Entry[][] rgeb_loc = entry_blocks;
Thread.MemoryBarrier();
if (i_block == rgeb_loc.Length - 1)
{
Entry[][] rgeb_new = new Entry[rgeb_loc.Length + 0x10][];
rgeb_loc.CopyTo(rgeb_new, 0);
var t1 = Interlocked.CompareExchange(ref entry_blocks, rgeb_new, rgeb_loc);
rgeb_loc = (t1 == rgeb_loc) ? rgeb_new : t1;
}
eb = rgeb_loc[i_block];
if (eb == null)
{
Entry[] eb_new = new Entry[EntriesPerBlock];
eb = Interlocked.CompareExchange(ref entry_blocks[i_block], eb_new, null) ?? eb_new;
}
}
#if false
else if (offs >= ResizeTrigger)
{
int mtid = Thread.CurrentThread.ManagedThreadId % free_lists.Length;
}
#endif
return eb;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public partial struct Entry
{
/// to merit 'beforefieldinit' semantics, we cannot have a static constructor and must do this all inline
static Type t_key = typeof(K);
static Type t_value = typeof(V);
static internal bool f_value_type_key = t_key.IsValueType;
static internal bool f_value_type_value = t_value.IsValueType;
static internal bool f_key_null_check = !f_value_type_key || Nullable.GetUnderlyingType(t_key) != null;
static internal int StructureSize { get { return cb_ent; } }
static int cb_ent = sizeof(int) + sizeof(uint) +
(f_value_type_key ? Marshal.SizeOf(default(K)) : IntPtr.Size) +
(f_value_type_value ? Marshal.SizeOf(default(V)) : IntPtr.Size);
internal int gx_next;
internal uint hash;
internal K key;
internal V value;
static internal bool CompareValues(V v1, V v2)
{
return (!f_value_type_value && v1 == null) ? v2 == null : v1.Equals(v2);
}
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// Lock-free LIFO stack
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public partial class Freelist
{
public Freelist(Config cfg)
{
this.cfg = cfg;
this.m_head = unchecked((UInt32)FreeListTerminator);
this.p2 = new FalseSharingPadding();
}
internal const Int32 FreelistHash = 0;
internal const Int32 FreeListTerminator = unchecked((Int32)0xFFFFFFFE);
const Int64 SequenceMask = unchecked((Int64)0xFFFFFFFF00000000);
const Int64 SequenceIncrement = 0x0000000100000000;
Config cfg;
FalseSharingPadding p2;
Int64 m_head;
/// <summary>
/// Add an item to the free list
/// </summary>
public void AddIndexToFreeList(int gx_add)
{
Int64 new_head, head = Interlocked.CompareExchange(ref m_head, 0, 0);
int offs;
Entry[] rg = cfg.GetBlock(gx_add, out offs);
rg[offs] = default(Entry); // permit GC release of reference types, set Entry.FreelistHash
while (true)
{
rg[offs].gx_next = (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 = Interlocked.CompareExchange(ref m_head, 0, 0);
while (true)
{
int offs, gx_next;
while (true)
{
gx_out = (Int32)head;
if (gx_out == FreeListTerminator)
{
gx_out = -1;
return false;
}
gx_next = cfg.GetBlock(gx_out, out offs)[offs].gx_next;
/// acquire frence: read of gx_next must occur prior to the read of m_head in this.Head.
Thread.MemoryBarrier();
if (head == (same_head = Interlocked.CompareExchange(ref m_head, 0, 0)))
break;
head = same_head;
}
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;
}
}
};
};
};
[StructLayout(LayoutKind.Explicit, Size = 2000)]
internal struct FalseSharingPadding { }