using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using glue;
using glue.Debugging;
using glue.Collections.XSpinLock;
#pragma warning disable 0649
namespace agree
{
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public class HybridSpinLockTray : HybridTray
{
public HybridSpinLockTray(int tix, TypeMgr tm, int last_mark, int next_id)
: base(tix, tm, last_mark, next_id)
{
for (int i = 0; i < Pools.Length; i++)
Pools[i] = new Pool(this, i);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
sealed class Pool : ConstraintPool
{
public Pool(Tray tr, int i_feat)
: base(tr, i_feat)
{
Nop.X(fsp1, fsp2);
singl = new Dictionary<Int32, Edge>();
var o = new FalseSharing.Padding2048();
multi = new Dictionary<Int32, Edge>();
Nop.X(o);
}
FalseSharing.Padding60 fsp1;
SpinLock m_lock = new SpinLock(false); // do not make this 'readonly'
FalseSharing.Padding60 fsp2;
Dictionary<Int32, Edge> singl;
Dictionary<Int32, Edge> multi;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public override Edge GetEdge(Int32 m)
{
Debug.Assert(m != 0);
Edge c;
if (m <= ((HybridTray)tr).last_frozen_mark)
singl.TryGetValue(m, out c);
else
{
bool entered = false;
try
{
m_lock.Enter(ref entered);
multi.TryGetValue(m, out c);
}
finally
{
if (entered)
m_lock.Exit(false);
}
}
return c;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public override bool TryGetEdge(int m, out Edge e)
{
Debug.Assert(m != 0);
if (m <= ((HybridTray)tr).last_frozen_mark)
return singl.TryGetValue(m, out e);
bool entered = false;
try
{
m_lock.Enter(ref entered);
return multi.TryGetValue(m, out e);
}
finally
{
if (entered)
m_lock.Exit(false);
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// Store the constraint for the specified mark. Handle Edge value semantics properly.
/// Allows detached mark to be set for bare or atomic types
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public override void SetEdge(Int32 m, Edge c)
{
Debug.Assert(m != 0 && m >= tr._protect_mark);
if (m <= ((HybridTray)tr).last_frozen_mark)
singl[m] = c;
else
{
bool entered = false;
try
{
m_lock.Enter(ref entered);
multi[m] = c;
}
finally
{
if (entered)
m_lock.Exit(false);
}
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public override void RemoveEdge(Int32 m)
{
Debug.Assert(m != 0 && m >= tr._protect_mark);
if (m <= ((HybridTray)tr).last_frozen_mark)
singl.Remove(m);
else
{
bool entered = false;
try
{
m_lock.Enter(ref entered);
multi.Remove(m);
}
finally
{
if (entered)
m_lock.Exit(false);
}
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public override bool TryRemoveEdge(Int32 m, out Edge e)
{
Debug.Assert(m != 0 && m >= tr._protect_mark);
if (m <= ((HybridTray)tr).last_frozen_mark)
return singl.TryGetValue(m, out e) ? singl.Remove(m) : false;
bool entered = false;
try
{
m_lock.Enter(ref entered);
return multi.TryGetValue(m, out e) ? multi.Remove(m) : false;
}
finally
{
if (entered)
m_lock.Exit(false);
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public override bool ContainsInMark(Int32 m)
{
Debug.Assert(m != 0);
if (m <= ((HybridTray)tr).last_frozen_mark)
return singl.ContainsKey(m);
bool entered = false;
try
{
m_lock.Enter(ref entered);
return multi.ContainsKey(m);
}
finally
{
if (entered)
m_lock.Exit(false);
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public override int Count
{
get { return singl.Count + multi.Count; }
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public override IEnumerable<int> Marks
{
get
{
tr.mre_truncate_ok.WaitOne();
return singl.Keys.Concat(multi.Keys);
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public override IEnumerable<Edge> Edges
{
get
{
tr.mre_truncate_ok.WaitOne();
return singl.Values.Concat(multi.Values);
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public override IEnumerable<KeyValuePair<int, Edge>> PoolEdges
{
get
{
tr.mre_truncate_ok.WaitOne();
return singl.Concat(multi);
}
}
};
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public class HybridSpinLockRwTray : HybridTray
{
public HybridSpinLockRwTray(int tix, TypeMgr tm, int last_mark, int next_id)
: base(tix, tm, last_mark, next_id)
{
for (int i = 0; i < Pools.Length; i++)
Pools[i] = new Pool(this, i);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
sealed class Pool : ConstraintPool
{
public Pool(Tray tr, int i_feat)
: base(tr, i_feat)
{
Nop.X(fsp1, fsp2, fsp3, fsp4);
singl = new Dictionary<Int32, Edge>(100000);
var o = new FalseSharing.Padding2048();
multi = new Dictionary<Int32, Edge>(100000);
Nop.X(o);
}
private const int MAXIMUM_WAITERS = 0x7ffffffe;
private const int SPINNING_FACTOR = 100;
private const int SLEEP_ONE_FREQUENCY = 40;
private const int SLEEP_ZERO_FREQUENCY = 10;
private const int LOCK_ANONYMOUS_OWNED = 1;
private const int WAITERS_MASK = 0x7ffffffe;
private const int LOCK_UNOWNED = 0;
FalseSharing.Padding128 fsp1;
private volatile int m_lock;
FalseSharing.Padding128 fsp2;
int c_readers = 0;
FalseSharing.Padding128 fsp3;
Dictionary<Int32, Edge> singl;
Dictionary<Int32, Edge> multi;
FalseSharing.Padding128 fsp4;
readonly int processorCount = Environment.ProcessorCount;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public override Edge GetEdge(Int32 m)
{
Debug.Assert(m != 0);
Edge c;
if (m <= ((HybridTray)tr).last_frozen_mark)
singl.TryGetValue(m, out c);
else
{
AddReader();
multi.TryGetValue(m, out c);
Interlocked.Decrement(ref c_readers);
}
return c;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public override bool TryGetEdge(int m, out Edge e)
{
Debug.Assert(m != 0);
if (m <= ((HybridTray)tr).last_frozen_mark)
return singl.TryGetValue(m, out e);
AddReader();
bool b = multi.TryGetValue(m, out e);
Interlocked.Decrement(ref c_readers);
return b;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// Store the constraint for the specified mark. Handle Edge value semantics properly.
/// Allows detached mark to be set for bare or atomic types
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public override void SetEdge(Int32 m, Edge c)
{
Debug.Assert(m != 0 && m >= tr._protect_mark);
if (m <= ((HybridTray)tr).last_frozen_mark)
singl[m] = c;
else
{
EnterWriter();
multi[m] = c;
m_lock--;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public override void RemoveEdge(Int32 m)
{
Debug.Assert(m != 0 && m >= tr._protect_mark);
if (m <= ((HybridTray)tr).last_frozen_mark)
singl.Remove(m);
else
{
EnterWriter();
multi.Remove(m);
m_lock--;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public override bool TryRemoveEdge(Int32 m, out Edge e)
{
Debug.Assert(m != 0 && m >= tr._protect_mark);
if (m <= ((HybridTray)tr).last_frozen_mark)
return singl.TryGetValue(m, out e) ? singl.Remove(m) : false;
EnterWriter();
bool b = multi.TryGetValue(m, out e) ? multi.Remove(m) : false;
m_lock--;
return b;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public override bool ContainsInMark(Int32 m)
{
Debug.Assert(m != 0);
if (m <= ((HybridTray)tr).last_frozen_mark)
return singl.ContainsKey(m);
AddReader();
bool b = multi.ContainsKey(m);
Interlocked.Decrement(ref c_readers);
return b;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public override int Count
{
get { return singl.Count + multi.Count; }
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public override IEnumerable<int> Marks
{
get
{
tr.mre_truncate_ok.WaitOne();
return singl.Keys.Concat(multi.Keys);
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public override IEnumerable<Edge> Edges
{
get
{
tr.mre_truncate_ok.WaitOne();
return singl.Values.Concat(multi.Values);
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public override IEnumerable<KeyValuePair<int, Edge>> PoolEdges
{
get
{
tr.mre_truncate_ok.WaitOne();
return singl.Concat(multi);
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void AddReader()
{
int owner = m_lock;
if ((owner & LOCK_ANONYMOUS_OWNED) == LOCK_UNOWNED)
{
if (Interlocked.CompareExchange(ref m_lock, owner | 1, owner) == owner)
{
Interlocked.Increment(ref c_readers);
m_lock--;
return;
}
}
SpinWait wait = new SpinWait();
while (true)
{
owner = m_lock;
if ((owner & LOCK_ANONYMOUS_OWNED) == LOCK_UNOWNED)
{
if (Interlocked.CompareExchange(ref m_lock, owner | 1, owner) == owner)
{
Interlocked.Increment(ref c_readers);
m_lock--;
return;
}
}
else if ((owner & WAITERS_MASK) == MAXIMUM_WAITERS || Interlocked.CompareExchange(ref m_lock, owner + 2, owner) == owner)
break;
wait.SpinOnce();
}
int c_wait = ((owner + 2) & WAITERS_MASK) / 2;
if (c_wait < processorCount)
{
int j = 1;
for (int i = 1; i <= c_wait * SPINNING_FACTOR; i++)
{
Thread.SpinWait((c_wait + i) * SPINNING_FACTOR * j);
if (j < processorCount)
j++;
owner = m_lock;
if ((owner & LOCK_ANONYMOUS_OWNED) == LOCK_UNOWNED)
{
if (Interlocked.CompareExchange(ref m_lock, ((owner & WAITERS_MASK) == 0 ? 0 : owner - 2) | 1, owner) == owner)
{
Interlocked.Increment(ref c_readers);
m_lock--;
return;
}
}
}
}
for (int iter = 0; ; iter++)
{
owner = m_lock;
if ((owner & LOCK_ANONYMOUS_OWNED) == LOCK_UNOWNED)
{
if (Interlocked.CompareExchange(ref m_lock, ((owner & WAITERS_MASK) == 0 ? 0 : owner - 2) | 1, owner) == owner)
{
Interlocked.Increment(ref c_readers);
m_lock--;
return;
}
}
if ((iter % SLEEP_ONE_FREQUENCY) == 0)
Thread.Sleep(1);
else if ((iter % SLEEP_ZERO_FREQUENCY) == 0)
Thread.Sleep(0);
else
Thread.Yield();
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void EnterWriter()
{
int owner = m_lock;
if ((owner & LOCK_ANONYMOUS_OWNED) == LOCK_UNOWNED)
{
if (Interlocked.CompareExchange(ref m_lock, owner | 1, owner) == owner)
{
while (c_readers > 0)
Thread.SpinWait(0);
return;
}
}
SpinWait wait = new SpinWait();
while (true)
{
owner = m_lock;
if ((owner & LOCK_ANONYMOUS_OWNED) == LOCK_UNOWNED)
{
if (Interlocked.CompareExchange(ref m_lock, owner | 1, owner) == owner)
{
while (c_readers > 0)
Thread.SpinWait(0);
return;
}
}
else if ((owner & WAITERS_MASK) == MAXIMUM_WAITERS || Interlocked.CompareExchange(ref m_lock, owner + 2, owner) == owner)
break;
wait.SpinOnce();
}
int c_wait = ((owner + 2) & WAITERS_MASK) / 2;
if (c_wait < processorCount)
{
int j = 1;
for (int i = 1; i <= c_wait * SPINNING_FACTOR; i++)
{
Thread.SpinWait((c_wait + i) * SPINNING_FACTOR * j);
if (j < processorCount)
j++;
owner = m_lock;
if ((owner & LOCK_ANONYMOUS_OWNED) == LOCK_UNOWNED)
{
if (Interlocked.CompareExchange(ref m_lock, ((owner & WAITERS_MASK) == 0 ? 0 : owner - 2) | 1, owner) == owner)
{
while (c_readers > 0)
Thread.SpinWait(0);
return;
}
}
}
}
for (int iter = 0; ; iter++)
{
owner = m_lock;
if ((owner & LOCK_ANONYMOUS_OWNED) == LOCK_UNOWNED)
{
if (Interlocked.CompareExchange(ref m_lock, ((owner & WAITERS_MASK) == 0 ? 0 : owner - 2) | 1, owner) == owner)
{
while (c_readers > 0)
Thread.SpinWait(0);
return;
}
}
if ((iter % SLEEP_ONE_FREQUENCY) == 0)
Thread.Sleep(1);
else if ((iter % SLEEP_ZERO_FREQUENCY) == 0)
Thread.Sleep(0);
else
Thread.Yield();
}
}
};
};
}