ms-queue/my_queue.c

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