mcs-queue/my_queue.c

   1 #include "main.h"
   2
   3 extern unsigned pid;
   4 extern unsigned iterations;
   5 extern unsigned initial_nodes;
   6 extern unsigned backoff;
   7 extern unsigned backoff_base;
   8 extern private_t private;
   9 extern shared_mem_t* smp;
  10
  11 void init_private()
  12 {
  13         private.node = 2 + initial_nodes + pid;
  14         private.value = 1 + initial_nodes + (pid * iterations);
  15
  16 }
  17
  18 void init_memory()
  19 {
  20 }
  21
  22 unsigned new_node()
  23 {
  24         return private.node;
  25 }
  26
  27 void reclaim(unsigned node)
  28 {
  29         private.node = node;
  30 }
  31
  32 void init_queue()
  33 {
  34         unsigned i;
  35
  36         /* initialize queue */
  37         smp->head.sep.ptr = 1;
  38         smp->head.sep.count = 0;
  39         smp->tail.sep.ptr = 1;
  40         smp->tail.sep.count = 0;
  41         smp->nodes[1].next.sep.ptr = NULL;
  42         smp->nodes[1].next.sep.count = 0;
  43
  44         /* initialize avail list */
  45         for (i=2; i<MAX_NODES; i++) {
  46                 smp->nodes[i].next.sep.ptr = i+1;
  47                 smp->nodes[i].next.sep.count = 0;
  48         }
  49         smp->nodes[MAX_NODES].next.sep.ptr = NULL;
  50         smp->nodes[MAX_NODES].next.sep.count = 0;
  51
  52         /* initialize queue contents */
  53         if (initial_nodes > 0) {
  54                 for (i=2; i<initial_nodes+2; i++) {
  55                         smp->nodes[i].value = i;
  56                         smp->nodes[i-1].next.sep.ptr = i;
  57                         smp->nodes[i].next.sep.ptr = NULL;
  58                 }
  59                 smp->head.sep.ptr = 1;
  60                 smp->tail.sep.ptr = 1 + initial_nodes;
  61         }
  62 }
  63
  64 void enqueue(unsigned val)
  65 {
  66         unsigned success;
  67         unsigned node;
  68         pointer_t tail;
  69         pointer_t next;
  70
  71         node = new_node();
  72         smp->nodes[node].value = val;
  73         smp->nodes[node].next.sep.ptr = NULL;
  74
  75         backoff = backoff_base;
  76         for (success = FALSE; success == FALSE; ) {
  77                 tail.con = smp->tail.con;
  78                 next.con = smp->nodes[tail.sep.ptr].next.con;
  79                 if (tail.con == smp->tail.con) {
  80                         if (next.sep.ptr == NULL) {
  81                                 backoff = backoff_base;
  82                                 success = cas(&smp->nodes[tail.sep.ptr].next,
  83                                                 next.con,
  84                                                 MAKE_LONG(node, next.sep.count+1));
  85                         }
  86                         if (success == FALSE) {
  87                                 cas(&smp->tail,
  88                                                 tail.con,
  89                                                 MAKE_LONG(smp->nodes[tail.sep.ptr].next.sep.ptr,
  90                                                         tail.sep.count+1));
  91                                 backoff_delay();
  92                         }
  93                 }
  94         }
  95         cas(&smp->tail,
  96                         tail.con,
  97                         MAKE_LONG(node, tail.sep.count+1));
  98 }
  99
 100 unsigned dequeue()
 101 {
 102         unsigned value;
 103         unsigned success;
 104         pointer_t head;
 105         pointer_t tail;
 106         pointer_t next;
 107
 108         backoff = backoff_base;
 109         for (success = FALSE; success == FALSE; ) {
 110                 head.con = smp->head.con;
 111                 tail.con = smp->tail.con;
 112                 next.con = smp->nodes[head.sep.ptr].next.con;
 113                 if (smp->head.con == head.con) {
 114                         if (head.sep.ptr == tail.sep.ptr) {
 115                                 if (next.sep.ptr == NULL) {
 116                                         return NULL;
 117                                 }
 118                                 cas(&smp->tail,
 119                                                 tail.con,
 120                                                 MAKE_LONG(next.sep.ptr, tail.sep.count+1));
 121                                 backoff_delay();
 122                         } else {
 123                                 value = smp->nodes[next.sep.ptr].value;
 124                                 success = cas(&smp->head,
 125                                                 head.con,
 126                                                 MAKE_LONG(next.sep.ptr, head.sep.count+1));
 127                                 if (success == FALSE) {
 128                                         backoff_delay();
 129                                 }
 130                         }
 131                 }
 132         }
 133         reclaim(head.sep.ptr);
 134         return value;
 135 }