code.kerkeslager.com Git - sandbox/blob - lockless/mpsc_queue.c

   1 #include <assert.h>
   2 #include <stdlib.h>
   3
   4 struct Queue;
   5 typedef struct Queue Queue;
   6
   7 struct QueueNode;
   8 typedef struct QueueNode QueueNode;
   9
  10 struct Queue
  11 {
  12   QueueNode* head;
  13   QueueNode* tail;
  14 };
  15
  16 struct QueueNode
  17 {
  18   void* item;
  19   QueueNode* next;
  20 };
  21
  22 void initQueue(Queue* queue)
  23 {
  24   QueueNode* fake = malloc(sizeof(QueueNode));
  25
  26   fake->next = NULL;
  27
  28   queue->head = fake;
  29   queue->tail = fake;
  30 }
  31
  32 void enqueue(Queue* queue, void* item)
  33 {
  34   // Create the node
  35   QueueNode* node = malloc(sizeof(QueueNode));
  36   node->item = item;
  37   node->next = NULL;
  38
  39   // Append the node
  40   while(!__sync_bool_compare_and_swap(&(queue->tail->next), NULL, node));
  41
  42   // Reuse the node variable to update the tail
  43   while((node = queue->tail)->next != NULL)
  44   {
  45     __sync_bool_compare_and_swap(&(queue->tail), node, node->next);
  46   }
  47 }
  48
  49 void* dequeue(Queue* queue, void* defaultResult)
  50 {
  51   if(queue->head == queue->tail) return defaultResult;
  52
  53   assert(queue->head->next != NULL);
  54
  55   QueueNode* previous = queue->head;
  56   queue->head = previous->next;
  57   free(previous);
  58   return queue->head->item;
  59 }
  60
  61 void freeQueue(Queue* queue)
  62 {
  63   QueueNode* node = queue->head;
  64   free(queue);
  65
  66   while(node != NULL)
  67   {
  68     QueueNode* temp = node;
  69     node = temp->next;
  70     free(temp);
  71   }
  72 }
  73
  74 int main() { }