2 This is an adaptation of Michael and Scott's lock-free queue.
4 Whitepaper containing pseudocode can be found here:
5 https://www.liblfds.org/downloads/white%20papers/[Queue]%20-%20[Michael,%20Scott]%20-%20Simple,%20Fast,%20and%20Practical%20Non-Blocking%20and%20Blocking%20Concurrent%20Queue%20Algorithms.pdf
15 struct QueueNodeTaggedPointer;
18 typedef struct QueueNodeTaggedPointer QueueNodeTaggedPointer;
19 typedef struct QueueNode QueueNode;
21 struct QueueNodeTaggedPointer {
26 QueueNodeTaggedPointer QueueNodeTaggedPointer_create(QueueNode* ptr, uint64_t count) {
27 QueueNodeTaggedPointer result = { ptr, count };
33 volatile QueueNodeTaggedPointer next;
36 volatile struct Queue {
37 QueueNodeTaggedPointer nose;
38 QueueNodeTaggedPointer tail;
41 Queue* Queue_construct() {
42 QueueNode* dummy = malloc(sizeof(QueueNode));
45 Queue* result = malloc(sizeof(Queue));
46 result->nose.ptr = dummy;
47 result->tail.ptr = dummy;
51 void Queue_enqueue(Queue* self, void* value) {
52 QueueNode* node = malloc(sizeof(QueueNode));
54 node->next.ptr = NULL;
57 QueueNodeTaggedPointer tail = self->tail;
58 QueueNodeTaggedPointer next = tail.ptr->next;
60 if(tail == self->tail) {
61 if(next.ptr == NULL) {
62 if(__sync_bool_compare_and_swap(&(tail.ptr->next), next, QueueNodeTaggedPointer_create(node, next.count + 1))) {
63 __sync_bool_compare_and_swap(&(self->tail), tail, QueueNodeTaggedPointer_create(node, tail.count + 1));
67 __sync_bool_compare_and_swap(&(self->tail), tail, QueueNodeTaggedPointer_create(next.ptr, tail.count + 1));
74 void* Queue_dequeue(Queue* self, void* defaultValue) {
76 QueueNodeTaggedPointer nose = self->nose;
77 QueueNodeTaggedPointer tail = self->tail;
78 QueueNodeTaggedPointer head = nose.ptr->next;
80 if(nose == self->nose) {
81 if(nose.ptr == tail.ptr) {
82 if(head.ptr == NULL) {
86 __sync_bool_compare_and_swap(&(self->tail), tail, QueueNodeTaggedPointer_create(head.ptr, tail.count + 1));
90 void* result = head.ptr->value;
91 if(__sync_bool_compare_and_swap(&(self->nose), nose, QueueNodeTaggedPointer_create(head.ptr, nose.count + 1))) {