stack.c

   1 #include "stack.h"
   2
   3 Simple_Stack S;
   4 void **location;
   5 int *collision;
   6
   7 void StackOp (ThreadInfo * pInfo) {
   8     if (TryPerformStackOp (p) == FALSE)
   9         LesOP (p);
  10     return;
  11 }
  12
  13 void LesOP (ThreadInfo * p) {
  14     while (1) {
  15         location[mypid] = p;
  16         pos = GetPosition (p);
  17         him = collision[pos];
  18         while (!CAS (&collision[pos], him, mypid))
  19             him = collision[pos];
  20         if (him != EMPTY) {
  21             q = location[him];
  22             if (q != NULL && q->id == him && q->op != p->op) {
  23                 if (CAS (&location[mypid], p, NULL)) {
  24                     if (TryCollision (p, q) == TRUE)
  25                         return;
  26                     else
  27                         goto stack;
  28                 } else {
  29                     FinishCollision (p);
  30                     return;
  31                 }
  32             }
  33             delay (p->spin);
  34             if (!CAS (&location[mypid], p, NULL)) {
  35                 FinishCollision (p);
  36                 return;
  37             }
  38         stack:
  39             if (TryPerformStackOp (p) == TRUE)
  40                 return;
  41         }
  42     }
  43 }
  44
  45 bool TryPerformStackOp (ThreadInfo * p) {
  46     Cell *phead, *pnext;
  47     if (p->op == PUSH) {
  48         phead = S.ptop;
  49         p->cell.pnext = phead;
  50         if (CAS (&S.ptop, phead, &p->cell))
  51             return TRUE;
  52         else
  53             return FALSE;
  54     }
  55     if (p->op == POP) {
  56         phead = S.ptop;
  57         if (phead == NULL) {
  58             p->cell = EMPTY;
  59             return TRUE;
  60         }
  61         pnext = phead->pnext;
  62         if (CAS (&S.ptop, phead, pnext)) {
  63             p->cell = *phead;
  64             return TRUE;
  65         } else {
  66             p->cell = EMPTY;
  67             return FALSE;
  68         }
  69     }
  70 }
  71
  72 void FinishCollision (ProcessInfo * p) {
  73     if (p->op == POP) {
  74         p->pcell = location[mypid]->pcell;
  75         location[mypid] = NULL;
  76     }
  77 }
  78
  79 void TryCollision (ThreadInfo * p, ThreadInfo * q) {
  80     if (p->op == PUSH) {
  81         if (CAS (&location[him], q, p))
  82             return TRUE;
  83         else
  84             return FALSE;
  85     }
  86     if (p->op == POP) {
  87         if (CAS (&location[him], q, NULL)) {
  88             p->cell = q->cell;
  89             location[mypid] = NULL;
  90             return TRUE;
  91         }
  92         else
  93             return FALSE;
  94     }
  95 }