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
public partial class LockFreeDictionary<K, V> : IDictionary<K, V>
where K : IEquatable<K>
where V : IEquatable<V>
{
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public partial class Config
{
const int DefaultCapacity = 35;
readonly int EntriesPerBlockPower;
readonly int EntriesPerBlock;
readonly int GlobalIndexMask;
public Config(LockFreeDictionary<K, V> dict)
{
this.d = dict;
if (d.m_options.HasFlag(Options.AttemptScaleToLargeObjectHeap))
{
/// attempt to place each EntryBlock in the large object heap
int v = 85000 / Config.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[dict.c_processors * 2];
for (int i = 0; i < free_lists.Length; i++)
free_lists[i] = new Freelist(this);
m_buckets = new BucketListPrimary(this, DefaultCapacity);
}
internal readonly LockFreeDictionary<K, V> d;
/// each EntryBlock stores a fixed number of entries
readonly EntryBlock m_first_block;
/// 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
readonly Freelist[] free_lists;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
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 i = 0; i < m_gx_next; i++)
{
EntryBlock.Entry e;
GetEntryHot(i, out e);
if (e.hash != EntryBlock.Entry.FreelistHash)
{
int gx;
BucketList.BucketHead bh;
do
m_buckets.GetBucketHead(ref mtid, e.hash, out bh); /// ignore config change
while (!bh.TryFindKey(e.hash, e.key, out gx));
if (gx != -1)
yield return new KeyValuePair<K, V>(e.key, e.value);
}
}
}
/// <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)
{
if (mtid == -1)
mtid = Thread.CurrentThread.ManagedThreadId % free_lists.Length;
int gx;
if (!free_lists[mtid].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;
}
#if DEBUG
StoreEntryHot(gx, ref EntryBlock.Entry.AllocDefault);
#endif
return gx;
}
/// <summary>
/// Add an entry index to one of the the freelists
/// </summary>
internal void ReleaseIndex(ref int mtid, int gx)
{
#if DEBUG
StoreEntryHot(gx, ref EntryBlock.Entry.FreelistDefault);
#endif
if (mtid == -1)
mtid = Thread.CurrentThread.ManagedThreadId % free_lists.Length;
free_lists[mtid].AddIndexToFreeList(gx);
}
/// <summary>
/// Get the block for the specified index. Allocates a new block, if necessary
/// </summary>
EntryBlock GetBlock(int gx)
{
EntryBlock eb = m_first_block;
for (int i = EntriesPerBlock; i <= gx; i += EntriesPerBlock)
{
EntryBlock next = eb.next;
Thread.MemoryBarrier();
if (next == null)
{
next = new EntryBlock(this, i >> EntriesPerBlockPower);
eb = Interlocked.CompareExchange(ref eb.next, next, null) ?? next;
}
else
eb = next;
}
return eb;
}
internal void StoreEntryHot(int gx, ref EntryBlock.Entry e)
{
(gx < EntriesPerBlock ? m_first_block : GetBlock(gx))
.StoreEntryHot(gx & GlobalIndexMask, ref e);
}
internal void SetEntryNext(int gx, int gx_next)
{
(gx < EntriesPerBlock ? m_first_block : GetBlock(gx))
.SetEntryNext(gx & GlobalIndexMask, gx_next);
}
internal void SetFreelistNext(int gx, int gx_next)
{
(gx < EntriesPerBlock ? m_first_block : GetBlock(gx))
.SetFreelistNext(gx & GlobalIndexMask, gx_next);
}
internal void SetEntryHash(int gx, uint h)
{
(gx < EntriesPerBlock ? m_first_block : GetBlock(gx))
.SetEntryHash(gx & GlobalIndexMask, h);
}
internal int TransactEntryNext(int gx, int gx_next, int gx_compare)
{
return (gx < EntriesPerBlock ? m_first_block : GetBlock(gx))
.TransactEntryNext(gx & GlobalIndexMask, gx_next, gx_compare);
}
internal int GetNextHot(int gx)
{
return (gx < EntriesPerBlock ? m_first_block : GetBlock(gx))
.GetNextHot(gx & GlobalIndexMask);
}
internal uint GetHashAndNextHot(int gx, out int gx_next)
{
return (gx < EntriesPerBlock ? m_first_block : GetBlock(gx))
.GetHashAndNextHot(gx & GlobalIndexMask, out gx_next);
}
internal void GetEntryHot(int gx, out EntryBlock.Entry e)
{
(gx < EntriesPerBlock ? m_first_block : GetBlock(gx))
.GetEntryHot(gx & GlobalIndexMask, out e);
}
internal void GetKeyHot(int gx, out K key)
{
(gx < EntriesPerBlock ? m_first_block : GetBlock(gx))
.GetKeyHot(gx & GlobalIndexMask, out key);
}
internal void GetValueHot(int gx, out V v)
{
(gx < EntriesPerBlock ? m_first_block : GetBlock(gx))
.GetValueHot(gx & GlobalIndexMask, out v);
}
};
};