10 atomic_size_t top, bottom;
11 atomic_uintptr_t array; /* Atomic(Array *) */
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);
22 /* Non-empty queue. */
23 x = atomic_load_explicit(&a->buffer[b % a->size], memory_order_relaxed);
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))
29 atomic_store_explicit(&q->bottom, b + 1, memory_order_relaxed);
31 } else { /* Empty queue. */
33 atomic_store_explicit(&q->bottom, b + 1, memory_order_relaxed);
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. */
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);
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);
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))