5 typedef struct Queue Queue;
7 typedef struct QueueNode QueueNode;
9 void initializeQueue(Queue* queue);
10 void enqueue(Queue* queue, void* item);
11 void* dequeue(Queue* queue);
12 void freeQueue(Queue* queue, void (*itemFreer)(void*));
16 // This implements a multiple-producer, single-consumer lockless concurrent
19 // After initialization, `head` and `tail` always points to a valid memory
20 // location--they are never `NULL`. To achieve this we initialize `head` and
21 // `tail` with a dummy node. This has two negative implications:
23 // 1. Unintuitively, `head->item` actually represents the item most recently
24 // dequeued. In fact, `head->item` may have been freed after it was
25 // dequeued, so we should never dereference it.
26 // 2. At initialization, no item has been dequeued yet, so we must allocate
27 // an extra `QueueNode` at initialization which will never be used to
30 // However, this extra memory allocation at initialization means that we
31 // never have to check whether `head` or `tail` are `NULL`, or initialize
32 // these variables concurrently, which are expensive operations.
39 // This implements a singly-linked list.
44 void initializeQueue(Queue* queue)
46 // Initialize the queue with a node that fakes the previously dequeued item.
47 // We don't have to initialize `dummyNode->item` because it will never be
49 QueueNode* dummyNode = malloc(sizeof(QueueNode));
50 dummyNode->next = NULL;
51 queue->head = dummyNode;
52 queue->tail = dummyNode;
55 bool isEmpty(Queue* queue)
57 // In a normal singly-linked list, the list is empty when the `head` is
58 // `NULL`, but here the queue is empty when the `head` is the same as the
60 return queue->head == queue->tail;
63 void enqueue(Queue* queue, void* item)
65 // Create the node that will be the new tail.
66 QueueNode* node = malloc(sizeof(QueueNode));
70 // Append the node to the list. Note that this is blocked as long as
71 // `queue->tail` is not actually pointing to the last node in the list
72 // because then `queue->tail->next` will not be `NULL`. This situation
73 // occurs when another thread has called `enqueue` and appended a node to
74 // the list, but hasn't yet updated `queue->tail`.
75 while(!__sync_bool_compare_and_swap(&(queue->tail->next), NULL, node));
77 // Move `queue->tail` forward until it points to the end of the list.
78 // Other threads attempting to eqneue will be unable to do so until this
79 // is complete. Additionally, other threads attempting to dequeue will be
80 // blocked until `queue->tail` has advanced by at least one node.
82 // We don't have to worry that another thread might have appended more
83 // nodes; advancing `queue->tail` to the end of the linked list is always
84 // the correct thing to do.
86 while((tail = queue->tail)->next != NULL)
88 __sync_val_compare_and_swap(&(queue->tail), tail, tail->next);
92 void* dequeue(Queue* queue)
96 return NULL; // TODO Provide ability to return a defined default.
99 QueueNode* oldHead = queue->head;
100 queue->head = oldHead->next;
103 return queue->head->item;
106 void freeQueue(Queue* queue, void (*itemFreer)(void*))
108 QueueNode* current = queue->head;
110 while(current != NULL)
112 itemFreer(current->item);
113 QueueNode* temp = current->next;