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