benchmark/chase-lev-deque-bugfix/deque.h

   1 #ifndef DEQUE_H
   2 #define DEQUE_H
   3
   4 #include <spec_lib.h>
   5 #include <stdlib.h>
   6 #include <cdsannotate.h>
   7 #include <specannotation.h>
   8 #include <model_memory.h>
   9 #include "common.h"
  10
  11 typedef struct {
  12         atomic_size_t size;
  13         atomic_int buffer[];
  14 } Array;
  15
  16 typedef struct {
  17         atomic_size_t top, bottom;
  18         atomic_uintptr_t array; /* Atomic(Array *) */
  19 } Deque;
  20
  21 #define EMPTY 0xffffffff
  22 #define ABORT 0xfffffffe
  23
  24 /**
  25     @Begin
  26     @Options:
  27         LANG = C;
  28     @Global_define:
  29         @DeclareStruct:
  30         typedef struct tag_elem {
  31             call_id_t id;
  32             int data;
  33         } tag_elem_t;
  34
  35         @DeclareVar:
  36         spec_list *__deque;
  37         id_tag_t *tag;
  38         @InitVar:
  39             __deque= new_spec_list();
  40             tag = new_id_tag(); // Beginning of available id
  41         @DefineFunc:
  42             tag_elem_t* new_tag_elem(call_id_t id, int data) {
  43                 tag_elem_t *e = (tag_elem_t*) CMODEL_MALLOC(sizeof(tag_elem_t));
  44                 e->id = id;
  45                 e->data = data;
  46                 return e;
  47             }
  48         @DefineFunc:
  49             call_id_t get_id(void *wrapper) {
  50                 return ((tag_elem_t*) wrapper)->id;
  51             }
  52         @DefineFunc:
  53             int get_data(void *wrapper) {
  54                 return ((tag_elem_t*) wrapper)->data;
  55             }
  56     @Happens_before:
  57         Push -> Steal
  58                 Push -> Take
  59     @End
  60 */
  61
  62
  63 Deque * create();
  64 void resize(Deque *q);
  65
  66 /**
  67     @Begin
  68     @Interface: Take
  69     @Commit_point_set: Take_Point1 | Take_Point2 | Take_Point3
  70     @ID: __RET__ == EMPTY ? DEFAULT_CALL_ID : get_id(back(__deque))
  71     @Action:
  72         int _Old_Val = EMPTY;
  73                 if (size(__deque) > 0) {
  74                         _Old_Val = get_data(back(__deque));
  75                 pop_back(__deque);
  76                 }
  77     @Post_check:
  78         _Old_Val == __RET__
  79     @End
  80 */
  81 int take(Deque *q);
  82
  83 /**
  84     @Begin
  85     @Interface: Push
  86     @Commit_point_set: Push_Point
  87     @ID: get_and_inc(tag);
  88     @Action:
  89         tag_elem_t *elem = new_tag_elem(__ID__, x);
  90         push_back(__deque, elem);
  91     @End
  92 */
  93 void push(Deque *q, int x);
  94
  95 /**
  96     @Begin
  97     @Interface: Steal
  98     @Commit_point_set: Steal_Point1 | Steal_Point2
  99     @ID: (__RET__ == EMPTY || __RET__ == ABORT) ? DEFAULT_CALL_ID : get_id(front(__deque))
 100     @Action:
 101         int _Old_Val = EMPTY;
 102                 if (size(__deque) > 0) {
 103                         _Old_Val = get_data(front(__deque));
 104                 pop_front(__deque);
 105                 }
 106     @Post_check:
 107         _Old_Val == __RET__
 108     @End
 109 */
 110 int steal(Deque *q);
 111
 112 #endif