chase-lev-deque/deque.c

   1 #include <stdatomic.h>
   2 #include <inttypes.h>
   3 #include "deque.h"
   4 #include <stdlib.h>
   5 #include <stdio.h>
   6
   7 Deque * create() {
   8         Deque * q = (Deque *) calloc(1, sizeof(Deque));
   9         Array * a = (Array *) calloc(1, sizeof(Array)+2*sizeof(atomic_int));
  10         atomic_store_explicit(&q->array, a, memory_order_relaxed);
  11         atomic_store_explicit(&q->top, 0, memory_order_relaxed);
  12         atomic_store_explicit(&q->bottom, 0, memory_order_relaxed);
  13         atomic_store_explicit(&a->size, 2, memory_order_relaxed);
  14         return q;
  15 }
  16
  17 int take(Deque *q) {
  18         size_t b = atomic_load_explicit(&q->bottom, memory_order_relaxed) - 1;
  19         Array *a = (Array *) atomic_load_explicit(&q->array, memory_order_relaxed);
  20         atomic_store_explicit(&q->bottom, b, memory_order_relaxed);
  21         atomic_thread_fence(memory_order_seq_cst);
  22         size_t t = atomic_load_explicit(&q->top, memory_order_relaxed);
  23         int x;
  24         if (t <= b) {
  25                 /* Non-empty queue. */
  26                 x = atomic_load_explicit(&a->buffer[b % atomic_load_explicit(&a->size,memory_order_relaxed)], memory_order_relaxed);
  27                 if (t == b) {
  28                         /* Single last element in queue. */
  29                         if (!atomic_compare_exchange_strong_explicit(&q->top, &t, t + 1, memory_order_seq_cst, memory_order_relaxed))
  30                                 /* Failed race. */
  31                                 x = EMPTY;
  32                         atomic_store_explicit(&q->bottom, b + 1, memory_order_relaxed);
  33                 }
  34         } else { /* Empty queue. */
  35                 x = EMPTY;
  36                 atomic_store_explicit(&q->bottom, b + 1, memory_order_relaxed);
  37         }
  38         return x;
  39 }
  40
  41 void resize(Deque *q) {
  42         Array *a = (Array *) atomic_load_explicit(&q->array, memory_order_relaxed);
  43         size_t size=atomic_load_explicit(&a->size, memory_order_relaxed);
  44         size_t new_size=size << 1;
  45         Array *new_a = (Array *) calloc(1, new_size * sizeof(atomic_int) + sizeof(Array));
  46         size_t top=atomic_load_explicit(&q->top, memory_order_relaxed);
  47         size_t bottom=atomic_load_explicit(&q->bottom, memory_order_relaxed);
  48         atomic_store_explicit(&new_a->size, new_size, memory_order_relaxed);
  49         size_t i;
  50         for(i=top; i < bottom; i++) {
  51                 atomic_store_explicit(&new_a->buffer[i % new_size], atomic_load_explicit(&a->buffer[i % size], memory_order_relaxed), memory_order_relaxed);
  52         }
  53         atomic_store_explicit(&q->array, new_a, memory_order_relaxed);
  54         printf("resize\n");
  55 }
  56
  57 void push(Deque *q, int x) {
  58         size_t b = atomic_load_explicit(&q->bottom, memory_order_relaxed);
  59         size_t t = atomic_load_explicit(&q->top, memory_order_acquire);
  60         Array *a = (Array *) atomic_load_explicit(&q->array, memory_order_relaxed);
  61         if (b - t > atomic_load_explicit(&a->size, memory_order_relaxed) - 1) /* Full queue. */ {
  62                 resize(q);
  63                 //Bug in paper...should have next line...
  64                 a = (Array *) atomic_load_explicit(&q->array, memory_order_relaxed);
  65         }
  66         atomic_store_explicit(&a->buffer[b % atomic_load_explicit(&a->size, memory_order_relaxed)], x, memory_order_relaxed);
  67         atomic_thread_fence(memory_order_release);
  68         atomic_store_explicit(&q->bottom, b + 1, memory_order_relaxed);
  69 }
  70
  71 int steal(Deque *q) {
  72         size_t t = atomic_load_explicit(&q->top, memory_order_acquire);
  73         atomic_thread_fence(memory_order_seq_cst);
  74         size_t b = atomic_load_explicit(&q->bottom, memory_order_acquire);
  75         int x = EMPTY;
  76         if (t < b) {
  77                 /* Non-empty queue. */
  78                 Array *a = (Array *) atomic_load_explicit(&q->array, memory_order_relaxed);
  79                 x = atomic_load_explicit(&a->buffer[t % atomic_load_explicit(&a->size, memory_order_relaxed)], memory_order_relaxed);
  80                 if (!atomic_compare_exchange_strong_explicit(&q->top, &t, t + 1, memory_order_seq_cst, memory_order_relaxed))
  81                         /* Failed race. */
  82                         return ABORT;
  83         }
  84         return x;
  85 }