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
[DebuggerDisplay("{ToString(),nq}")]
public partial class LockFreeDictionary<K, V> : IDictionary<K, V>
where K : IEquatable<K>
where V : IEquatable<V>
{
/// <summary>
/// Read a 64-bit value (a.) without tearing and (b.) with cache coherence across multiple processors. This requires
/// coordination with the source compiler as well as the runtime JIT compiler.
/// </summary>
static Int64 AtomicRead64(ref Int64 p)
{
/// When running in a 32-bit environment, use the CLR support.
if (IntPtr.Size == 4)
return Interlocked.CompareExchange(ref p, 0, 0);
/// In the 64-bit environment, tearing is not an issue so we only need to request cache coherence. The following
/// is the same as 'return Thread.VolatileRead(ref p)'
Int64 i64 = p;
Thread.MemoryBarrier();
return i64;
}
public
partial class Config
{
// [DebuggerDisplay("{ToString(),nq}")]
public partial
class EntryBlock
{
readonly int i_block;
internal int BlockIndex { get { return i_block; } }
[DebuggerDisplay("{ToString(),nq}")]
public partial struct Entry
{
public override string ToString()
{
if (gx_next == 0 && hash == 0 && Object.Equals(key, default(K)) && Object.Equals(value, default(V)))
return "";
return String.Format(" next: {0:X8} hash: {1:X8} key: {2}"/* value: {4}"*/,
gx_next,
hash,
key/*,
e.value*/);
}
public String BucketCurrent
{
get
{
Config cfg = Config.BucketList.BucketHead._cfg;
if (cfg == null)
return "n/a";
uint c = cfg.m_buckets.BucketCount;
return String.Format("bx for {0} buckets: {1:X8}", c, hash % c);
}
}
public String BucketPrevious
{
get
{
Config cfg = Config.BucketList.BucketHead._cfg;
if (cfg == null)
return "n/a";
Config.BucketListResize bls = cfg.m_buckets as Config.BucketListResize;
if (bls == null)
return "n/a";
uint c = bls._blp.BucketCount;
return String.Format("bx for {0} buckets: {1:X8}", c, hash % c);
}
}
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
[DebuggerDisplay("{ToString(),nq}")]
public partial struct SlotAddr
{
public SlotAddr(EntryBlock eb, int offs)
{
this.eb = eb;
this.offs = offs;
}
readonly int offs;
readonly EntryBlock eb;
public int GlobalIndex { get { return (eb.i_block << eb.cfg.EntriesPerBlockPower) + offs; } }
public bool TryGetEntryNext(out int gx)
{
gx = eb.GetNextHot(offs);
return (uint)gx < (uint)Thread.VolatileRead(ref eb.cfg.m_gx_next);
}
public Entry _entry
{
get
{
Entry e;
eb.GetEntryHot(offs, out e);
return e;
}
}
public override string ToString()
{
return new Config.BucketList.BucketListDebugView.BucketDisplay.SlotAddrDisplay(this).ToString();
}
public EntryBlock _eb { get { return eb; } }
};
public Config _cfg { get { return cfg; } }
public override string ToString()
{
return String.Format("block: {0} length: {1} last=={2}", i_block, rg.Length, next == null);
}
};
// public double DataLoad { get { return (double)dict.Count / m_buckets.BucketCount; } }
// public double TotalLoad { get { return (double)(dict.Count + m_c_free) / m_buckets.BucketCount; } }
internal partial class BucketListResize : BucketList
{
public BucketList _blp { get { return blp; } }
}
public void CheckBuckets()
{
m_buckets.Check();
}
[DebuggerDisplay("{DebugInfo(),nq} ")]
[DebuggerTypeProxy(typeof(LockFreeDictionary<,>.Config.BucketList.BucketListDebugView))]
internal partial class BucketList
{
public class BucketListDebugView
{
BucketList bl;
public BucketListDebugView(LockFreeDictionary<K, V>.Config.BucketList bl)
{
this.bl = bl;
}
[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
public BucketDisplay[] buckets
{
get
{
return bl.rg
.Select((v, i) => new BucketDisplay(bl, i))
//.Where(bd => bd.v != 0)
.ToArray();
}
}
[DebuggerDisplay("{ToString(),nq}")]
// [DebuggerTypeProxy(typeof(LockFreeDictionary<,>.Config.BucketList.BucketListDebugView.BucketDisplay.BucketEntryDebugView))]
public struct BucketDisplay
{
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public BucketList bl;
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public uint bx;
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public UInt64 v;
public BucketDisplay(BucketList bl, int ix)
{
this.bl = bl;
this.bx = (uint)ix;
this.v = bl != null && bl.rg != null && ix < bl.rg.Length ? (UInt64)bl.rg[ix] : 0;
}
public BucketDisplay(LockFreeDictionary<K, V>.Config.BucketList.BucketHead bh)
{
this.bl = bh._bl;
this.bx = bh._bx;
this.v = (UInt64)bh._v;
}
public override string ToString()
{
if (bl == null)
return "(null)";
if (bl.rg == null)
return "(rg null)";
int c = BucketHead.ExtractEntryCount((long)v);
String sc0;
if (c != 0 && ValidCount() != c)
sc0 = "✖";
else if (v == (UInt64)AtomicRead64(ref bl.rg[bx]))
sc0 = "✓";
else
sc0 = "Ⓧ";
String sc3 = c == 0 ? " " : "c: " + c.ToString().PadRight(2);
return String.Format("{0} bx: {1:X8} {2} gx: {3:X8} seq: {4:X8} ({5:X16})",
sc0,
bx,
sc3,
BucketHead.CapturedFirstSlotIndexV((long)v),
BucketHead._seq_no_V((long)v),
v);
}
[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
public SlotAddrDisplay[] entries
{
get
{
return GetEntries().ToArray();
}
}
IEnumerable<SlotAddrDisplay> GetEntries()
{
if (bl == null)
yield break;
int count = BucketHead.ExtractEntryCount((long)v);
int gx = BucketHead.CapturedFirstSlotIndexV((long)v);
for (int i = 0; i < count; i++)
{
yield return new SlotAddrDisplay(bl.cfg, gx);
if ((uint)gx >= (uint)Thread.VolatileRead(ref bl.cfg.m_gx_next))
yield break;
EntryBlock.Entry e;
bl.cfg.GetEntryHot(gx, out e);
if (gx == e.gx_next)
yield break;
gx = e.gx_next;
}
}
int ValidCount()
{
if (bl == null)
return 0;
int count = BucketHead.ExtractEntryCount((long)v);
int actual = 0;
int gx = BucketHead.CapturedFirstSlotIndexV((long)v);
for (int i = 0; i < count; i++)
{
if ((uint)gx >= (uint)Thread.VolatileRead(ref bl.cfg.m_gx_next))
break;
EntryBlock.Entry e;
bl.cfg.GetEntryHot(gx, out e);
if (gx == e.gx_next)
break;
gx = e.gx_next;
actual++;
}
return actual;
}
[DebuggerDisplay("{ToString(),nq}")]
public struct SlotAddrDisplay
{
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
int gx;
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
Config cfg;
public SlotAddrDisplay(Config cfg, int gx)
{
this.gx = gx;
this.cfg = cfg;
}
public SlotAddrDisplay(EntryBlock.SlotAddr sa)
{
this.cfg = null;
this.gx = 0;
if (sa._eb != null)
{
this.cfg = sa._eb._cfg;
this.gx = sa.GlobalIndex;
}
}
public override string ToString()
{
if (gx == Freelist.FreeListTerminator)
return String.Format("Ⓧ {0:X8} Freelist terminator is not a valid global index", gx);
if (gx == -1)
return String.Format("Ⓧ FFFFFFFF is not a valid global index", gx);
if (cfg == null)
return "(no config)";
if ((uint)gx >= (uint)Thread.VolatileRead(ref cfg.m_gx_next))
return String.Format("Ⓧ {0:X8} was never issued as a valid global index", gx);
EntryBlock.Entry e;
cfg.GetEntryHot(gx, out e);
String s = String.Format(" gx: {0:X8} {1}", gx, e.ToString().Trim());
if (gx == e.gx_next)
s = "!loop" + s;
return s;
}
};
};
}
public void Check()
{
for (uint i = 0; i < BucketCount; i++)
{
var bh = new BucketHead(this, i);
int gx = bh.CapturedFirstEntryIndex;
K[] keys = new K[bh.CapturedEntryCount];
for (int j = 0; j < bh.CapturedEntryCount; j++)
{
if ((uint)gx >= (uint)Thread.VolatileRead(ref cfg.m_gx_next))
{
if (Debugger.IsAttached)
Debugger.Break();
throw new Exception("check: global index out of range");
}
EntryBlock.Entry e;
cfg.GetEntryHot(gx,out e);
keys[j] = e.key;
if (gx == e.gx_next)
{
if (Debugger.IsAttached)
Debugger.Break();
throw new Exception("check: loop");
}
gx = e.gx_next;
}
if (keys.Distinct().Count() != keys.Length)
{
if (Debugger.IsAttached)
Debugger.Break();
throw new Exception("check: duplicate key");
}
}
}
internal int EntryCount
{
get
{
int c = 0;
for (int i = 0; i < rg.Length; i++)
c += BucketHead.ExtractEntryCount(AtomicRead64(ref rg[i]));
return c;
}
}
public String DebugInfo()
{
return String.Format("{0} ({1}) buckets: {2} entries: {3}",
this.GetType().Name,
cfg.d.m_config.m_buckets == this ? "current" : "not current",
rg.Length,
this.EntryCount);
}
#if false
public override string ToString()
{
return String.Format("{0} {1} ({2})",
this.GetType().Name,
rg.Length,
_config.dict.m_config.m_buckets == this ? "current" : "not current");
}
#endif
public IEnumerable<EntryBlock.SlotAddr> _Slots()
{
BucketHead._cfg = cfg;
for (uint i = 0; i < rg.Length; i++)
{
if (rg[i] != 0)
{
BucketHead bh = new BucketHead(this, i);
foreach (EntryBlock.SlotAddr sa in bh.Entries)
{
var xyz = sa;
yield return xyz;
}
}
}
}
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public EntryBlock.SlotAddr[] Slots
{
get
{
return _Slots().ToArray();
}
}
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public BucketHead[] _buckets
{
get
{
return rg.Select((v, ix) => new BucketHead(this, (uint)ix)).ToArray();
}
}
public bool ContainsFirstIndex(int gx)
{
for (int i = 0; i < rg.Length; i++)
{
Int64 v = AtomicRead64(ref rg[i]);
if (BucketHead.CapturedFirstSlotIndexV(v) == gx)
return true;
}
return false;
}
[DebuggerDisplay("{ToString(),nq}")]
[DebuggerTypeProxy(typeof(LockFreeDictionary<,>.Config.BucketList.BucketListDebugView.BucketDisplay))]
internal partial struct BucketHead
{
public static Config _cfg;
public BucketList _bl { get { return bl; } }
public uint _bx { get { return bx; } }
public Int64 _v { get { return v; } }
public bool IsInitialized { get { return bl != null; } }
internal static int ExtractEntryCount(Int64 v) { return (int)(v >> 32) & EntriesPerBucketMask; }
public override string ToString()
{
return new BucketList.BucketListDebugView.BucketDisplay(this).ToString();
}
public String LiveStatus
{
get
{
Int64 va = AtomicRead64(ref bl.rg[bx]);
return String.Format("v: {0:X16} cur: {1:X16} {2}", v, va, va == v ? "ok" : "Ⓧ");
}
}
public static String VDisplay(Int64 v)
{
return String.Format("seq: {0:X6} c: {1,-2} gx: {2:X8}", BucketHead._seq_no_V(v), BucketHead.ExtractEntryCount(v), BucketHead.CapturedFirstSlotIndexV(v));
}
public static int CapturedFirstSlotIndexV(Int64 v) { return (int)v; }
public int _seq_no { get { return (int)(v >> 40); } }
public static int _seq_no_V(Int64 v) { return (int)(v >> 40); }
#if false
public override string ToString()
{
if (!IsInitialized)
return "(not initialized)";
if (bx != -1)
{
Int64 newv = bl.rg[bx];
if (v != newv)
{
BucketHead bhnew = new BucketHead(bl, bx);
return String.Format("{7} bx: {0:X8} @{1}({2}) first: {3:X8} ({4:X8}) count: {5} ({6})",
bx,
_seq_no, bhnew._seq_no,
FirstSlotIndex, bhnew.FirstSlotIndex,
_slot_count, bhnew._slot_count,
LiveStatus);
}
}
String chain = "";// String.Join(" ", _cfg.FollowChain(FirstSlotIndex).Take(Math.Min(SlotCount, 10)).Select(sa => "(" + sa.ToString() + ")"));
return String.Format("{5} bx: {0:X8}@ {1} first: {2:X8} count: {3} {4}", bx, _seq_no, FirstSlotIndex, _slot_count, chain, LiveStatus);
}
#endif
// [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public EntryBlock.SlotAddr[] Entries
{
get
{
return _cfg.FollowChain(CapturedFirstEntryIndex).Take(CapturedEntryCount).ToArray();
}
}
};
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// DEBUGGING CODE FOR 'Config' FOLLOWS
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public bool GetExistingSlotAddr(int gx, out EntryBlock.SlotAddr sa)
{
if ((uint)gx >= (uint)Thread.VolatileRead(ref m_gx_next))
{
sa = default(EntryBlock.SlotAddr);
return false;
}
sa = new EntryBlock.SlotAddr(GetBlock(gx >> EntriesPerBlockPower), gx & GlobalIndexMask);
return true;
}
public override string ToString()
{
return String.Format("count: {0} next index: {1}", d.Count, Thread.VolatileRead(ref m_gx_next));
}
public IEnumerable<EntryBlock.SlotAddr> FollowChain(int i)
{
while (true)
{
EntryBlock.SlotAddr sa;
if (!GetExistingSlotAddr(i, out sa))
yield break;
yield return sa;
if (!sa.TryGetEntryNext(out i))
yield break;
}
}
public String Dump()
{
using (StringWriter sw = new StringWriter())
{
sw.WriteLine(new String('%', 114));
sw.WriteLine("count: {0}", d.Count);
sw.WriteLine("=== primary BucketHead entries ({0}) ===", m_buckets.BucketCount);
uint c = m_buckets.BucketCount;
for (uint i = 0; i < c; i++)
{
BucketList.BucketHead bh = new BucketList.BucketHead(m_buckets, i);
if (bh.CapturedEntryCount > 0)
{
//if (i != prev + 1)
//sw.WriteLine("...");
sw.WriteLine("bucket: {0,4} v.{1,-3} : {2,2} entries",
i,
bh._seq_no,
bh.CapturedEntryCount);
foreach (EntryBlock.SlotAddr sa in FollowChain(bh.CapturedFirstEntryIndex).Take(bh.CapturedEntryCount))
{
EntryBlock.Entry ent = sa._entry;
String sk = ent.key == null ? "null" : "\"" + ent.key.ToString() + "\"";
String sv = ent.value == null ? "null" : "\"" + ent.value.ToString() + "\"";
sw.WriteLine(" {0:X8} hash: {1:X8}/{2,-2} k: {3,-43} v: {4,-43} next: {5:X8}",
sa.GlobalIndex,
ent.hash,
ent.hash % c,
sk,
sv,
ent.gx_next);
}
};
}
sw.WriteLine();
for (EntryBlock eb = m_first_block; eb != null; eb = eb.next)
{
sw.WriteLine("=== Entry block #{0} ===", eb.BlockIndex);
for (int i = 0; i < EntriesPerBlock; i++)
{
EntryBlock.Entry ent;
eb.GetEntryHot(i, out ent);
if (ent.hash != 0)
{
String sk = ent.key == null ? "null" : "\"" + ent.key.ToString() + "\"";
String sv = ent.value == null ? "null" : "\"" + ent.value.ToString() + "\"";
int gx_ = (eb.BlockIndex << EntriesPerBlockPower) + i;
sw.WriteLine("{0:X8}: {1:X8} hash: {2:X8} k: {3,-43} v: {4,-43} next: {5:X8} bx1: {6,-3}",
i,
gx_,
ent.hash,
sk,
sv,
ent.gx_next,
ent.hash % m_buckets.BucketCount);
}
}
sw.WriteLine();
}
sw.WriteLine("=== Free list {0} ===");
return sw.ToString();
}
}
//[DebuggerDisplay("{ToString(),nq}")]
public partial struct Freelist
{
public override string ToString()
{
return String.Format("head: {0:X16} count: {2}", m_head, _ied().Count());
}
[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
EntryBlock.SlotAddr[] _debug
{
get { return _ied().ToArray(); }
}
public IEnumerable<EntryBlock.SlotAddr> _ied()
{
EntryBlock.SlotAddr sa;
Int64 cur = m_head;
int gx = (int)cur;
do
{
if (!cfg.GetExistingSlotAddr(gx, out sa))
yield break;
EntryBlock.Entry e = sa._entry;
yield return sa;
if (gx == e.gx_next)
yield break;
gx = e.gx_next;
}
while (gx != FreeListTerminator && gx != -1);
}
};
};
}