chase-lev-deque/deque.c

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