Skip to content

Instantly share code, notes, and snippets.

@sakno
Created August 4, 2024 17:31
Show Gist options
  • Save sakno/afbf26ec05143575190f69a8f30fb9b4 to your computer and use it in GitHub Desktop.
Save sakno/afbf26ec05143575190f69a8f30fb9b4 to your computer and use it in GitHub Desktop.
Lock-free queue in C#
public class LockFreeQueue<T>
{
private Node? head, tail;
private void EnqueueWithContention(Node currentTail, Node newNode)
{
var tmp = currentTail;
do
{
currentTail = tmp;
tmp = Interlocked.CompareExchange(ref currentTail.Next, newNode, null);
} while (tmp is not null);
// attempt to install a new tail. Do not retry if failed, competing thread installed more recent version of it
Interlocked.CompareExchange(ref tail, newNode, currentTail);
}
public void Enqueue(T item)
{
var newNode = new Node(item);
if (Interlocked.CompareExchange(ref tail, newNode, null) is { } currentTail)
{
EnqueueWithContention(currentTail, newNode);
}
else
{
head = newNode;
}
}
public bool TryDequeue([MaybeNullWhen(false)] out T result)
{
if (Volatile.Read(in head) is { } currentHead)
return TryDequeueWithContention(currentHead, out result);
result = default;
return false;
}
private bool TryDequeueWithContention(Node currentHead, [MaybeNullWhen(false)] out T value)
{
for (Node? newHead, tmp; !currentHead.TryRead(out value); currentHead = ReferenceEquals(tmp, currentHead) ? newHead : tmp)
{
newHead = currentHead.Next;
if (newHead is null)
{
value = default;
return false;
}
tmp = Interlocked.CompareExchange(ref head, newHead, currentHead);
Debug.Assert(tmp is not null);
}
return true;
}
private sealed class Node(T value)
{
internal Node? Next;
private volatile uint visited;
internal bool TryRead([MaybeNullWhen(false)] out T result)
{
if (Interlocked.Exchange(ref visited, 1U) is 0U)
{
result = value;
if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
{
value = default!;
}
return true;
}
result = default;
return false;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment