ms-queue: remove more externs and unintended shared data
[model-checker-benchmarks.git] / 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 }