8 Deque * create_size(int size) {
9 Deque * q = (Deque *) calloc(1, sizeof(Deque));
10 Array * a = (Array *) calloc(1, sizeof(Array)+2*sizeof(atomic_int));
11 atomic_store_explicit(&q->array, a, wildcard(1));
12 atomic_store_explicit(&q->top, 0, wildcard(2));
13 atomic_store_explicit(&q->bottom, 0, wildcard(3));
14 atomic_store_explicit(&a->size, size, wildcard(4));
19 Deque * q = (Deque *) calloc(1, sizeof(Deque));
20 Array * a = (Array *) calloc(1, sizeof(Array)+2*sizeof(atomic_int));
21 atomic_store_explicit(&q->array, a, wildcard(1));
22 atomic_store_explicit(&q->top, 0, wildcard(2));
23 atomic_store_explicit(&q->bottom, 0, wildcard(3));
24 atomic_store_explicit(&a->size, 2, wildcard(4));
29 size_t b = atomic_load_explicit(&q->bottom, wildcard(5)) - 1;
30 Array *a = (Array *) atomic_load_explicit(&q->array, wildcard(6));
31 atomic_store_explicit(&q->bottom, b, wildcard(7));
32 atomic_thread_fence(wildcard(8)); // seq_cst
33 size_t t = atomic_load_explicit(&q->top, wildcard(9));
36 /* Non-empty queue. */
37 x = atomic_load_explicit(&a->buffer[b %
38 atomic_load_explicit(&a->size,wildcard(10))], wildcard(11));
40 /* Single last element in queue. */
41 if (!atomic_compare_exchange_strong_explicit(&q->top, &t, t + 1,
42 wildcard(12), wildcard(13))) // 12 -> seq_cst
45 atomic_store_explicit(&q->bottom, b + 1, wildcard(14));
47 } else { /* Empty queue. */
49 atomic_store_explicit(&q->bottom, b + 1, wildcard(15));
54 void resize(Deque *q) {
55 Array *a = (Array *) atomic_load_explicit(&q->array, wildcard(16));
56 size_t size=atomic_load_explicit(&a->size, wildcard(17));
57 size_t new_size=size << 1;
58 Array *new_a = (Array *) calloc(1, new_size * sizeof(atomic_int) + sizeof(Array));
59 size_t top=atomic_load_explicit(&q->top, wildcard(18));
60 size_t bottom=atomic_load_explicit(&q->bottom, wildcard(19));
61 atomic_store_explicit(&new_a->size, new_size, wildcard(20));
63 for(i=top; i < bottom; i++) {
64 atomic_store_explicit(&new_a->buffer[i % new_size],
65 atomic_load_explicit(&a->buffer[i % size], wildcard(21)), wildcard(22));
67 atomic_store_explicit(&q->array, new_a, wildcard(23)); // release
71 void push(Deque *q, int x) {
72 size_t b = atomic_load_explicit(&q->bottom, wildcard(24));
73 size_t t = atomic_load_explicit(&q->top, wildcard(25)); // acquire
74 Array *a = (Array *) atomic_load_explicit(&q->array, wildcard(26));
75 if (b - t > atomic_load_explicit(&a->size, wildcard(27)) - 1) /* Full queue. */ {
77 //Bug in paper...should have next line...
78 a = (Array *) atomic_load_explicit(&q->array, wildcard(28));
80 atomic_store_explicit(&a->buffer[b % atomic_load_explicit(&a->size,
81 wildcard(29))], x, wildcard(30));
82 atomic_thread_fence(wildcard(31)); // release
83 //atomic_thread_fence(release); // release
84 atomic_store_explicit(&q->bottom, b + 1, wildcard(32));
88 size_t t = atomic_load_explicit(&q->top, wildcard(33)); // acquire
89 atomic_thread_fence(wildcard(34)); // seq_cst
90 size_t b = atomic_load_explicit(&q->bottom, wildcard(35)); // acquire
93 /* Non-empty queue. */
95 Array *a = (Array *) atomic_load_explicit(&q->array, wildcard(36));
96 x = atomic_load_explicit(&a->buffer[t % atomic_load_explicit(&a->size,
97 wildcard(37))], wildcard(38));
99 if (!atomic_compare_exchange_strong_explicit(&q->top, &t, t + 1,
100 wildcard(39), wildcard(40)))