Skip to content

Instantly share code, notes, and snippets.

@ionuttamas
Last active October 11, 2015 09:55
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ionuttamas/c8c2333e36e7570ae1aa to your computer and use it in GitHub Desktop.
Save ionuttamas/c8c2333e36e7570ae1aa to your computer and use it in GitHub Desktop.
Lock-free list implementation
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();
}
}
public class Node<T>
{
public NodeReference<T> Reference;
public Node()
{
Reference = new NodeReference<T>();
}
public Node(T item)
{
Reference = new NodeReference<T>(item);
}
}
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