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                         //model_print("init_list\n");
  41             tag = new_id_tag(); // Beginning of available id
  42                 //@Cleanup:
  43                         //if (__deque) {
  44                                 //free_spec_list(__deque);
  45                                 //model_print("free_list\n");
  46                         //}
  47                         //if (tag)
  48                                 //free_id_tag(tag);
  49         @DefineFunc:
  50             tag_elem_t* new_tag_elem(call_id_t id, int data) {
  51                 tag_elem_t *e = (tag_elem_t*) CMODEL_MALLOC(sizeof(tag_elem_t));
  52                 e->id = id;
  53                 e->data = data;
  54                 return e;
  55             }
  56         @DefineFunc:
  57             call_id_t get_id(void *wrapper) {
  58                                 //tag_elem_t *res = (tag_elem_t*) wrapper;
  59                                 return res == NULL ? 0 : ((tag_elem_t*) wrapper)->id;
  60                                 //if (res == NULL) {
  61                                         //model_print("wrong id here\n");
  62                                         //return 0;
  63                                 //}
  64                 //return res->id;
  65             }
  66         @DefineFunc:
  67             int get_data(void *wrapper) {
  68                                 //tag_elem_t *res = (tag_elem_t*) wrapper;
  69                 //return res->data;
  70                                 return ((tag_elem_t*) wrapper)->data;
  71             }
  72     @Happens_before:
  73         Push -> Steal
  74                 Push -> Take
  75     @End
  76 */
  77
  78
  79 Deque * create();
  80 void resize(Deque *q);
  81
  82 /**
  83     @Begin
  84     @Interface: Take
  85     //@Commit_point_set: Take_Read_Bottom | Take_CAS_Top | Take_Additional_Point
  86     @Commit_point_set: Take_Read_Bottom | Take_Additional_Point
  87     @ID: __RET__ == EMPTY ? DEFAULT_CALL_ID : get_id(back(__deque))
  88     @Action:
  89         int _Old_Val = EMPTY;
  90                 if (__RET__ != EMPTY && size(__deque) > 0) {
  91                         _Old_Val = get_data(back(__deque));
  92                 pop_back(__deque);
  93                 }
  94     @Post_check: _Old_Val == __RET__
  95     @End
  96 */
  97 int take(Deque *q);
  98
  99 /**
 100     @Begin
 101     @Interface: Push
 102     @Commit_point_set: Push_Update_Bottom
 103     @ID: get_and_inc(tag);
 104     @Action: push_back(__deque, new_tag_elem(__ID__, x));
 105     @End
 106 */
 107 void push(Deque *q, int x);
 108
 109 /**
 110     @Begin
 111     @Interface: Steal
 112     //@Commit_point_set: Steal_Read_Bottom | Steal_CAS_Top | Steal_Additional_Point
 113     @Commit_point_set: Steal_Read_Bottom | Steal_Additional_Point
 114     @ID: (__RET__ == EMPTY || __RET__ == ABORT) ? DEFAULT_CALL_ID : get_id(front(__deque))
 115     @Action:
 116         int _Old_Val = EMPTY;
 117                 if (__RET__ != EMPTY && __RET__ != ABORT && size(__deque) > 0) {
 118                         _Old_Val = get_data(front(__deque));
 119                         pop_front(__deque);
 120                 }
 121     @Post_check:
 122         _Old_Val == __RET__ || __RET__ == EMPTY || __RET__ == ABORT
 123     @End
 124 */
 125 int steal(Deque *q);
 126
 127 #endif