8 typedef struct MPSCQueue MPSCQueue;
10 typedef struct MPSCQueueNode MPSCQueueNode;
12 void initializeMPSCQueue(MPSCQueue* queue);
13 void enqueue(MPSCQueue* queue, void* item);
14 void* dequeue(MPSCQueue* queue);
15 void destructMPSCQueue(MPSCQueue* queue, void (*itemFreer)(void*));
19 // This implements a multiple-producer, single-consumer lockless concurrent
22 // After initialization, `head` and `tail` always points to a valid memory
23 // location--they are never `NULL`. To achieve this we initialize `head` and
24 // `tail` with a dummy node. This has two negative implications:
26 // 1. Unintuitively, `head->item` actually represents the item most recently
27 // dequeued. In fact, `head->item` may have been freed after it was
28 // dequeued, so we should never dereference it.
29 // 2. At initialization, no item has been dequeued yet, so we must allocate
30 // an extra `MPSCQueueNode` at initialization which will never be used to
33 // However, this extra memory allocation at initialization means that we
34 // never have to check whether `head` or `tail` are `NULL`, or initialize
35 // these variables concurrently, which are expensive operations.
42 // This implements a singly-linked list.
47 void initializeMPSCQueue(MPSCQueue* queue)
49 // Initialize the queue with a node that fakes the previously dequeued item.
50 // We don't have to initialize `dummyNode->item` because it will never be
52 MPSCQueueNode* dummyNode = malloc(sizeof(MPSCQueueNode));
53 dummyNode->next = NULL;
54 queue->head = dummyNode;
55 queue->tail = dummyNode;
58 bool isEmpty(MPSCQueue* queue)
60 // In a normal singly-linked list, the list is empty when the `head` is
61 // `NULL`, but here the queue is empty when the `head` is the same as the
63 return queue->head == queue->tail;
66 void enqueue(MPSCQueue* queue, void* item)
68 // Create the node that will be the new tail.
69 MPSCQueueNode* node = malloc(sizeof(MPSCQueueNode));
73 // Append the node to the list. Note that this is blocked as long as
74 // `queue->tail` is not actually pointing to the last node in the list
75 // because then `queue->tail->next` will not be `NULL`. This situation
76 // occurs when another thread has called `enqueue` and appended a node to
77 // the list, but hasn't yet updated `queue->tail`.
78 while(!__sync_bool_compare_and_swap(&(queue->tail->next), NULL, node));
80 // Move `queue->tail` forward until it points to the end of the list.
81 // Other threads attempting to eqneue will be unable to do so until this
82 // is complete. Additionally, other threads attempting to dequeue will be
83 // blocked until `queue->tail` has advanced by at least one node.
85 // We don't have to worry that another thread might have appended more
86 // nodes; advancing `queue->tail` to the end of the linked list is always
87 // the correct thing to do.
89 while((tail = queue->tail)->next != NULL)
91 __sync_val_compare_and_swap(&(queue->tail), tail, tail->next);
95 void* dequeue(MPSCQueue* queue)
99 return NULL; // TODO Provide ability to return a defined default.
102 MPSCQueueNode* oldHead = queue->head;
103 queue->head = oldHead->next;
106 return queue->head->item;
109 void destructMPSCQueue(MPSCQueue* queue, void (*itemFreer)(void*))
111 MPSCQueueNode* current = queue->head;
113 while(current != NULL)
115 itemFreer(current->item);
116 MPSCQueueNode* temp = current->next;