|
|
using System;
|
|
|
using System.Threading;
|
|
|
|
|
|
namespace Implab.Parallels {
|
|
|
public class MTLinkedList<TNode> where TNode : MTLinkedListNode<TNode> {
|
|
|
TNode m_first;
|
|
|
TNode m_last;
|
|
|
|
|
|
public void InsertAfter( TNode pos, TNode node) {
|
|
|
Safe.ArgumentNotNull(node, "node");
|
|
|
if (!Attach(node))
|
|
|
throw new InvalidOperationException("The specified node already attached to a list");
|
|
|
|
|
|
TNode next;
|
|
|
|
|
|
while (true) {
|
|
|
// insert first if pos == null
|
|
|
next = pos == null ? m_first : pos.next;
|
|
|
node.prev = pos;
|
|
|
node.next = next;
|
|
|
if (next == m_first) {
|
|
|
if (next != Interlocked.CompareExchange(ref m_first, node, next))
|
|
|
continue;
|
|
|
// race
|
|
|
} else {
|
|
|
if (next != Interlocked.CompareExchange(ref pos.next, node, next))
|
|
|
continue;
|
|
|
// race
|
|
|
}
|
|
|
break;
|
|
|
}
|
|
|
|
|
|
while (true) {
|
|
|
if (next == null) {
|
|
|
if (pos != Interlocked.CompareExchange(ref m_last, node, pos))
|
|
|
continue;
|
|
|
} else {
|
|
|
if (pos != Interlocked.CompareExchange(ref next.prev, node, pos))
|
|
|
continue;
|
|
|
}
|
|
|
break;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
public void InsertBefore( TNode pos, TNode node) {
|
|
|
Safe.ArgumentNotNull(node, "node");
|
|
|
|
|
|
if (!Attach(node))
|
|
|
return;
|
|
|
|
|
|
TNode prev;
|
|
|
|
|
|
while (true) {
|
|
|
// insert first if pos == null
|
|
|
prev = pos == null ? m_last : pos.prev;
|
|
|
node.next = pos;
|
|
|
node.prev = prev;
|
|
|
if (prev == m_last) {
|
|
|
if (prev != Interlocked.CompareExchange(ref m_last, node, prev))
|
|
|
continue;
|
|
|
// race
|
|
|
} else {
|
|
|
if (prev != Interlocked.CompareExchange(ref pos.prev, node, prev))
|
|
|
continue;
|
|
|
// race
|
|
|
}
|
|
|
break;
|
|
|
}
|
|
|
|
|
|
while (true) {
|
|
|
if (prev == null) {
|
|
|
if (pos != Interlocked.CompareExchange(ref m_first, node, pos))
|
|
|
continue;
|
|
|
} else {
|
|
|
if (pos != Interlocked.CompareExchange(ref prev.next, node, pos))
|
|
|
continue;
|
|
|
}
|
|
|
break;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
bool Detach(TNode node) {
|
|
|
MTLinkedList<TNode> parent;
|
|
|
|
|
|
do {
|
|
|
parent = node.parentList;
|
|
|
if (parent == null || parent != this)
|
|
|
return false;
|
|
|
} while(parent != Interlocked.CompareExchange(ref node.parentList, null, parent));
|
|
|
}
|
|
|
|
|
|
bool Attach(TNode node) {
|
|
|
MTLinkedList<TNode> parent;
|
|
|
|
|
|
do {
|
|
|
parent = node.parentList;
|
|
|
if (parent != null)
|
|
|
return false;
|
|
|
} while(parent != Interlocked.CompareExchange(ref node.parentList, this, parent));
|
|
|
}
|
|
|
|
|
|
public void Remove(TNode node) {
|
|
|
Safe.ArgumentNotNull(node, "node");
|
|
|
|
|
|
if (!Detach(node))
|
|
|
return;
|
|
|
|
|
|
TNode prev;
|
|
|
TNode next;
|
|
|
|
|
|
while (true) {
|
|
|
prev = node.prev;
|
|
|
next = node.next;
|
|
|
|
|
|
if (prev == null) {
|
|
|
if (node != Interlocked.CompareExchange(ref m_first, next, node))
|
|
|
continue;
|
|
|
} else {
|
|
|
if (node != Interlocked.CompareExchange(ref prev.next, next, node))
|
|
|
continue;
|
|
|
}
|
|
|
|
|
|
break;
|
|
|
}
|
|
|
|
|
|
while (true) {
|
|
|
if (next == null) {
|
|
|
if (node != Interlocked.CompareExchange(ref m_last, prev, node))
|
|
|
continue;
|
|
|
} else {
|
|
|
if (node != Interlocked.CompareExchange(ref next.prev, prev, node))
|
|
|
continue;
|
|
|
}
|
|
|
break;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
}
|
|
|
}
|
|
|
|
|
|
|
