Add solution to first project euler problem in elixir
[sandbox] / vm / mpsc_queue.c
1 #ifndef MPSC_QUEUE
2 #define MPSC_QUEUE
3
4 #include <stdbool.h>
5 #include <stdlib.h>
6
7 struct MPSCQueue;
8 typedef struct MPSCQueue MPSCQueue;
9 struct MPSCQueueNode;
10 typedef struct MPSCQueueNode MPSCQueueNode;
11
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*));
16
17 struct MPSCQueue
18 {
19   // This implements a multiple-producer, single-consumer lockless concurrent
20   // queue.
21   //
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:
25   //
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
31   //    store an item.
32   //
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.
36   MPSCQueueNode* head;
37   MPSCQueueNode* tail;
38 };
39
40 struct MPSCQueueNode
41 {
42   // This implements a singly-linked list.
43   void* item;
44   MPSCQueueNode* next;
45 };
46
47 void initializeMPSCQueue(MPSCQueue* queue)
48 {
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
51   // used.
52   MPSCQueueNode* dummyNode = malloc(sizeof(MPSCQueueNode));
53   dummyNode->next = NULL;
54   queue->head = dummyNode;
55   queue->tail = dummyNode;
56 }
57
58 bool isEmpty(MPSCQueue* queue)
59 {
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
62   // `tail`.
63   return queue->head == queue->tail;
64 }
65
66 void enqueue(MPSCQueue* queue, void* item)
67 {
68   // Create the node that will be the new tail.
69   MPSCQueueNode* node = malloc(sizeof(MPSCQueueNode));
70   node->item = item;
71   node->next = NULL;
72
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));
79
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.
84   //
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.
88   MPSCQueueNode* tail;
89   while((tail = queue->tail)->next != NULL)
90   {
91     __sync_val_compare_and_swap(&(queue->tail), tail, tail->next);
92   }
93 }
94
95 void* dequeue(MPSCQueue* queue)
96 {
97   if(isEmpty(queue))
98   {
99     return NULL; // TODO Provide ability to return a defined default.
100   }
101
102   MPSCQueueNode* oldHead = queue->head;
103   queue->head = oldHead->next;
104   free(oldHead);
105
106   return queue->head->item;
107 }
108
109 void destructMPSCQueue(MPSCQueue* queue, void (*itemFreer)(void*))
110 {
111   MPSCQueueNode* current = queue->head;
112
113   while(current != NULL)
114   {
115     itemFreer(current->item);
116     MPSCQueueNode* temp = current->next;
117     free(current);
118     current = temp;
119   }
120 }
121
122 #endif