Created
August 4, 2024 17:31
-
-
Save sakno/afbf26ec05143575190f69a8f30fb9b4 to your computer and use it in GitHub Desktop.
Lock-free queue in C#
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 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