Last active
October 11, 2015 09:55
-
-
Save ionuttamas/c8c2333e36e7570ae1aa to your computer and use it in GitHub Desktop.
Lock-free list implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class List<T>:IEnumerable<T> | |
{ | |
private readonly T _sentinel; | |
private readonly Node<T> _head; | |
public List() | |
{ | |
_head = new Node<T>(); | |
_sentinel = default(T); | |
} | |
public List(T item) | |
{ | |
_head = new Node<T>(item); | |
_sentinel = item; | |
} | |
public void Add(T item) | |
{ | |
Node<T> node = new Node<T>(item); | |
NodeReference<T> newReference; | |
do | |
{ | |
newReference = new NodeReference<T> | |
{ | |
Next = node | |
}; | |
node.Reference = _head.Reference; | |
node.Reference.Value = item; | |
} | |
while (!Atomic.CAS(ref _head.Reference, node.Reference, newReference)); | |
} | |
public void Remove(T item) | |
{ | |
Node<T> node = _head; | |
while (node != null) | |
{ | |
if (node.Reference == null) | |
return; | |
if (node.Reference.Value.Equals(item)) | |
{ | |
Remove(node); | |
break; | |
} | |
node = node.Reference.Next; | |
} | |
} | |
private void Remove(Node<T> item) | |
{ | |
Node<T> next; | |
NodeReference<T> oldReference; | |
NodeReference<T> newReference; | |
do | |
{ | |
oldReference = item.Reference; | |
next = item.Reference.Next; | |
if (next?.Reference == null) | |
{ | |
newReference = null; | |
} | |
else | |
{ | |
newReference = new NodeReference<T> | |
{ | |
Next = next.Reference.Next, | |
Value = next.Reference.Value | |
}; | |
} | |
} while (!Atomic.CAS(ref item.Reference, oldReference, newReference)); | |
} | |
public IEnumerator<T> GetEnumerator() | |
{ | |
Node<T> node = _head.Reference.Next; | |
while (node != null) | |
{ | |
if (node.Reference == null) | |
yield break; | |
yield return node.Reference.Value; | |
node = node.Reference.Next; | |
} | |
} | |
IEnumerator IEnumerable.GetEnumerator() | |
{ | |
return GetEnumerator(); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Node<T> | |
{ | |
public NodeReference<T> Reference; | |
public Node() | |
{ | |
Reference = new NodeReference<T>(); | |
} | |
public Node(T item) | |
{ | |
Reference = new NodeReference<T>(item); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class NodeReference<T> | |
{ | |
public T Value { get; set; } | |
public Node<T> Next; | |
public NodeReference() | |
{ | |
} | |
public NodeReference(T item) | |
{ | |
Value = item; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment