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