MTLinkedList.cs
140 lines
| 4.2 KiB
| text/x-csharp
|
CSharpLexer
cin
|
r113 | 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; | ||||
| } | ||||
| } | ||||
| } | ||||
| } | ||||