code.kerkeslager.com Git - fur/blob - c/queue.c

   1 /*
   2 This is an adaptation of Michael and Scott's lock-free queue.
   3
   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
   6 */
   7 #ifndef QUEUE_C
   8 #define QUEUE_C
   9
  10 #include<stdbool.h>
  11 #include<stdint.h>
  12 #include<stdlib.h>
  13 #include"queue.h">
  14
  15 struct QueueNodeTaggedPointer;
  16 struct QueueNode;
  17
  18 typedef struct QueueNodeTaggedPointer QueueNodeTaggedPointer;
  19 typedef struct QueueNode QueueNode;
  20
  21 struct QueueNodeTaggedPointer {
  22   QueueNode* ptr;
  23   uint64_t count;
  24 };
  25
  26 QueueNodeTaggedPointer QueueNodeTaggedPointer_create(QueueNode* ptr, uint64_t count) {
  27   QueueNodeTaggedPointer result = { ptr, count };
  28   return result;
  29 }
  30
  31 struct QueueNode {
  32   void* value;
  33   volatile QueueNodeTaggedPointer next;
  34 };
  35
  36 volatile struct Queue {
  37   QueueNodeTaggedPointer nose;
  38   QueueNodeTaggedPointer tail;
  39 };
  40
  41 Queue* Queue_construct() {
  42   QueueNode* dummy = malloc(sizeof(QueueNode));
  43   dummy->next = NULL;
  44
  45   Queue* result = malloc(sizeof(Queue));
  46   result->nose.ptr = dummy;
  47   result->tail.ptr = dummy;
  48   return result;
  49 }
  50
  51 void Queue_enqueue(Queue* self, void* value) {
  52   QueueNode* node = malloc(sizeof(QueueNode));
  53   node->value = value;
  54   node->next.ptr = NULL;
  55
  56   while(true) {
  57     QueueNodeTaggedPointer tail = self->tail;
  58     QueueNodeTaggedPointer next = tail.ptr->next;
  59
  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));
  64           return;
  65         }
  66         else {
  67           __sync_bool_compare_and_swap(&(self->tail), tail, QueueNodeTaggedPointer_create(next.ptr, tail.count + 1));
  68         }
  69       }
  70     }
  71   }
  72 }
  73
  74 void* Queue_dequeue(Queue* self, void* defaultValue) {
  75   while(true) {
  76     QueueNodeTaggedPointer nose = self->nose;
  77     QueueNodeTaggedPointer tail = self->tail;
  78     QueueNodeTaggedPointer head = nose.ptr->next;
  79
  80     if(nose == self->nose) {
  81       if(nose.ptr == tail.ptr) {
  82         if(head.ptr == NULL) {
  83           return defaultValue;
  84         }
  85         else {
  86           __sync_bool_compare_and_swap(&(self->tail), tail, QueueNodeTaggedPointer_create(head.ptr, tail.count + 1));
  87         }
  88       }
  89       else {
  90         void* result = head.ptr->value;
  91         if(__sync_bool_compare_and_swap(&(self->nose), nose, QueueNodeTaggedPointer_create(head.ptr, nose.count + 1))) {
  92           free(nose.ptr);
  93           return result;
  94         }
  95       }
  96     }
  97   }
  98 }
  99
 100 #endif