chase-lev-deque/deque.c

   1 typedef struct {
   2         atomic_size_t size;
   3         atomic_int buffer[];
   4 } Array;
   5
   6 typedef struct {
   7         atomic_size_t top, bottom;
   8         Atomic(Array *) array;
   9 } Deque;
  10
  11 int take(Deque *q) {
  12         size_t b = load_explicit(&q->bottom, relaxed) - 1;
  13         Array *a = load_explicit(&q->array, relaxed);
  14         store_explicit(&q->bottom, b, relaxed);
  15         thread_fence(seq_cst);
  16         size_t t = load_explicit(&q->top, relaxed);
  17         int x;
  18         if (t <= b) {
  19                 /* Non-empty queue. */
  20                 x = load_explicit(&a->buffer[b % a->size], relaxed);
  21                 if (t == b) {
  22                         /* Single last element in queue. */
  23                         if (!compare_exchange_strong_explicit(&q->top, &t, t + 1, seq_cst, relaxed))
  24                                 /* Failed race. */
  25                                 x = EMPTY;
  26                         store_explicit(&q->bottom, b + 1, relaxed);
  27                 }
  28         } else { /* Empty queue. */
  29                 x = EMPTY;
  30                 store_explicit(&q->bottom, b + 1, relaxed);
  31         }
  32         return x;
  33 }
  34
  35 void push(Deque *q, int x) {
  36         size_t b = load_explicit(&q->bottom, relaxed);
  37         size_t t = load_explicit(&q->top, acquire);
  38         Array *a = load_explicit(&q->array, relaxed);
  39         if (b - t > a->size - 1) /* Full queue. */
  40                 resize(q);
  41         store_explicit(&a->buffer[b % a->size], x, relaxed);
  42         thread_fence(release);
  43         store_explicit(&q->bottom, b + 1, relaxed);
  44 }
  45
  46 int steal(Deque *q) {
  47         size_t t = load_explicit(&q->top, acquire);
  48         thread_fence(seq_cst);
  49         size_t b = load_explicit(&q->bottom, acquire);
  50         int x = EMPTY;
  51         if (t < b) {
  52                 /* Non-empty queue. */
  53                 Array *a = load_explicit(&q->array, relaxed);
  54                 x = load_explicit(&a->buffer[t % a->size], relaxed);
  55                 if (!compare_exchange_strong_explicit(&q->top, &t, t + 1, seq_cst, relaxed))
  56                         /* Failed race. */
  57                         return ABORT;
  58         }
  59         return x;
  60 }