using System;
using System.Text;
using System.IO;
using System.Diagnostics;
using System.Collections.Generic;
using System.Threading;
using System.Threading.Tasks;
using System.Linq;
#pragma warning disable 0420
public partial class LockFreeDictionary<K, V> : IDictionary<K, V>
where K : IEquatable<K>
where V : IEquatable<V>
{
static Int64 AtomicRead64(ref Int64 p)
{
if (IntPtr.Size == 4)
return Interlocked.CompareExchange(ref p, 0, 0);
/// The following is the same as 'return Thread.VolatileRead(ref p)'
Int64 i64 = p;
Thread.MemoryBarrier();
return i64;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public partial class Config
{
const int DefaultCapacity = 35;
internal int EntriesPerBlockPower;
internal int EntriesPerBlock;
internal int GlobalIndexMask;
public Config(LockFreeDictionary<K, V> dict)
{
this.dict = dict;
if (dict.m_options.HasFlag(Options.AttemptScaleToLargeObjectHeap))
{
/// attempt to place each EntryBlock in the large object heap
int v = 85000 / EntryBlock.Entry.StructureSize;
int r = 1;
while ((v >>= 1) > 0)
r++;
EntriesPerBlockPower = r;
}
else
EntriesPerBlockPower = 10;
EntriesPerBlock = 1 << EntriesPerBlockPower;
GlobalIndexMask = EntriesPerBlock - 1;
m_first_block = new EntryBlock(this, 0);
free_lists = new Freelist[FreeListCount];
for (int i = 0; i < FreeListCount; i++)
free_lists[i] = new Freelist(this);
m_buckets = new BucketListPrimary(this, DefaultCapacity);
}
internal LockFreeDictionary<K, V> dict;
/// each EntryBlock stores a fixed number of entries
readonly EntryBlock m_first_block;
/// entries have a global index across all EntryBlocks
public volatile int m_gx_next;
/// the number of entries in the dictionary is explicitly maintained
public int m_count = 0;
/// number of free lists determined by 2^P
const int FreeListCountPower = 1;//0;
const int FreeListCount = (1 << FreeListCountPower);
const int FreeListCountMask = FreeListCount - 1;
/// a small number of free lists
Freelist[] free_lists;
/// free list choosing index. don't care about atomicity
volatile int i_free_list = 0;
/// a pair of bucket arrays that can be atomically swapped
volatile internal BucketList m_buckets;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
internal bool IsCurrent { get { return this == dict.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;
}
/// <summary>
/// Get the block for the specified index. Allocates a new block, if necessary
/// </summary>
public EntryBlock GetBlock(int i_block)
{
EntryBlock eb = m_first_block;
for (int i = 0; i < i_block; i++)
{
if (eb.next == null)
Interlocked.CompareExchange(ref eb.next, new EntryBlock(this, i_block), null);
eb = eb.next; /// C# volatile
}
return eb;
}
EntryBlock.Entry _default_alloc_entry = new EntryBlock.Entry(-1, 0, default(K), default(V));
EntryBlock.Entry _default_freelist_entry = new EntryBlock.Entry(0, 0, default(K), default(V));
/// <summary>
/// Get an unused slot, either from one of the freelists, or by allocating a new slot
/// </summary>
internal int GetUnusedIndex()
{
int gx;
if (free_lists[++i_free_list & FreeListCountMask].TryGetFreeIndex(out gx))
{
#if DEBUG
Interlocked.Decrement(ref m_c_free);
#endif
}
else
gx = Interlocked.Increment(ref m_gx_next) - 1;
#if DEBUG
StoreEntry(gx, ref _default_alloc_entry);
#endif
return gx;
}
internal void ReleaseIndex(int gx)
{
#if DEBUG
StoreEntry(gx, ref _default_freelist_entry);
#endif
free_lists[++i_free_list & FreeListCountMask].AddIndexToFreeList(gx);
#if DEBUG
Interlocked.Increment(ref m_c_free);
#endif
}
/// <summary>
/// Release the entries on a (privately-held) chain of entries to the free list. The chain is privately held if:
/// - it has never been published in a BucketHead -or-
/// - disconnection from its BucketHead has been successfully transacted
/// </summary>
internal void ReleaseChain(int gx, int count)
{
Debug.Assert(count > 0);
int i = 0;
while (++i < count)
{
int gx_next = GetEntryNext(gx);
ReleaseIndex(gx);
gx = gx_next;
}
ReleaseIndex(gx);
}
/// <summary>
/// Copy a chain of entries.
/// </summary>
/// <returns>
/// <value>true</value> if the chain was copied, <value>false</value> if the chain was not copied because
/// the bucket head became invalid. In this case, the caller can try again if desired.
/// </returns>
internal bool CopyChain(BucketList.BucketHead bh, int count, out int gx_head, out int gx_tail)
{
Debug.Assert(count > 0);
int gx_prev = gx_head = gx_tail = default(int);
int gx = bh.CapturedFirstSlotIndex;
int j = 0;
while (true)
{
EntryBlock.Entry e_src;
GetEntryLoose(gx, out e_src);
if (bh.IsExpired)
{
if (j > 0)
ReleaseChain(gx_head, j);
return false;
}
gx_tail = GetUnusedIndex();
StoreEntryLoose(gx_tail, ref e_src);
if (j == 0)
gx_head = gx_tail;
else
SetEntryNext(gx_prev, gx_tail);
if (++j == count)
return true;
gx = e_src.gx_next;
gx_prev = gx_tail;
}
}
public void GetEntryLoose(int gx, out EntryBlock.Entry e)
{
GetBlock(gx >> EntriesPerBlockPower).GetEntryLoose(gx & GlobalIndexMask, out e);
}
public void StoreEntryLoose(int gx, ref EntryBlock.Entry e)
{
GetBlock(gx >> EntriesPerBlockPower).StoreEntryLoose(gx & GlobalIndexMask, ref e);
}
public void SetEntryNext(int gx, int gx_next)
{
GetBlock(gx >> EntriesPerBlockPower).SetEntryNext(gx & GlobalIndexMask, gx_next);
}
public int GetEntryNext(int gx)
{
return GetBlock(gx >> EntriesPerBlockPower).GetEntryNext(gx & GlobalIndexMask);
}
public uint GetHashAndNext(int gx, out int gx_next)
{
return GetBlock(gx >> EntriesPerBlockPower).GetHashAndNext(gx & GlobalIndexMask, out gx_next);
}
public void GetKeyReadback(int gx, out K key)
{
GetBlock(gx >> EntriesPerBlockPower).GetKeyReadback(gx & GlobalIndexMask, out key);
}
public void SetEntryValueLoose(int gx, ref V v)
{
GetBlock(gx >> EntriesPerBlockPower).SetEntryValueLoose(gx & GlobalIndexMask, ref v);
}
public void SetEntryValueReadback(int gx, ref V v)
{
GetBlock(gx >> EntriesPerBlockPower).SetEntryValueReadback(gx & GlobalIndexMask, ref v);
}
};
};