benchmarks/checkfence/msqueue/msn.c

   1 #include "lsl_protos.h"
   2
   3 /* ---- data types  ---- */
   4
   5 typedef int value_t;
   6
   7 typedef struct node {
   8   struct node *next;
   9   value_t value;
  10 } node_t;
  11
  12 typedef struct queue {
  13   node_t *head;
  14   node_t *tail;
  15 } queue_t;
  16
  17 /* ---- operations  ---- */
  18
  19 void init_queue(queue_t *queue)
  20 {
  21   node_t *node = lsl_malloc_noreuse(sizeof(node_t));
  22   node->next = 0;
  23   queue->head = queue->tail = node;
  24 }
  25
  26 void enqueue(queue_t *queue, value_t value)
  27 {
  28   node_t *node;
  29   node_t *tail;
  30   node_t *next;
  31
  32   node = lsl_malloc_noreuse(sizeof(node_t));
  33   node->value = value;
  34   node->next = 0;
  35   while (true) {
  36     tail = queue->tail;
  37     next = tail->next;
  38     if (tail == queue->tail)
  39       if (next == 0) {
  40         if (lsl_cas_64(&tail->next, next, node))
  41           break;
  42       } else
  43         lsl_cas_ptr(&queue->tail, tail, next);
  44   }
  45   lsl_cas_ptr(&queue->tail, tail, node);
  46 }
  47
  48 boolean_t dequeue(queue_t *queue, value_t *pvalue)
  49 {
  50   node_t *head;
  51   node_t *tail;
  52   node_t *next;
  53
  54   while (true) {
  55     head = queue->head;
  56     tail = queue->tail;
  57     next = head->next;
  58     if (head == queue->head) {
  59       if (head == tail) {
  60         if (next == 0)
  61           return false;
  62         lsl_cas_ptr(&queue->tail, tail, next);
  63       } else {
  64         *pvalue = next->value;
  65         if (lsl_cas_ptr(&queue->head, head, next))
  66           break;
  67       }
  68     }
  69   }
  70   lsl_free_noreuse(head);
  71   return true;
  72 }