src/utils_deq.h

   1 #ifndef utils_deq_h
   2 #define utils_deq_h 1
   3
   4 #include <stdlib.h>
   5 #include <assert.h>
   6 #include <memory.h>
   7
   8 #define CT_ASSERT(exp) { assert(exp); }
   9
  10 #define NEW(t)             (t*)  malloc(sizeof(t))
  11 #define NEW_ARRAY(t,n)     (t*)  malloc(sizeof(t)*(n))
  12 #define NEW_PTR_ARRAY(t,n) (t**) malloc(sizeof(t*)*(n))
  13
  14 //
  15 // If available, use aligned_alloc for cache-line-aligned allocations.  Otherwise
  16 // fall back to plain malloc.
  17 //
  18 #define NEW_CACHE_ALIGNED(t,p) \
  19 do { \
  20     if (posix_memalign((void*) &(p), 64, (sizeof(t) + (sizeof(t) % 64 ? 64 - (sizeof(t) % 64) : 0))) != 0) (p) = 0; \
  21 } while (0)
  22
  23 #define ALLOC_CACHE_ALIGNED(s,p) \
  24 do { \
  25     if (posix_memalign((void*) &(p), 64, (s + (s % 64 ? 64 - (s % 64) : 0))) != 0) (p) = 0; \
  26 } while (0)
  27
  28 #define ZERO(p) memset(p, 0, sizeof(*p))
  29
  30 #define DEQ_DECLARE(i,d) typedef struct { \
  31     i      *head;       \
  32     i      *tail;       \
  33     i      *scratch;    \
  34     size_t  size;       \
  35     } d
  36
  37 #define DEQ_LINKS_N(n,t) t *prev##n; t *next##n
  38 #define DEQ_LINKS(t) DEQ_LINKS_N(,t)
  39 #define DEQ_EMPTY {0,0,0,0}
  40
  41 #define DEQ_INIT(d) do { (d).head = 0; (d).tail = 0; (d).scratch = 0; (d).size = 0; } while (0)
  42 #define DEQ_IS_EMPTY(d) ((d).head == 0)
  43 #define DEQ_ITEM_INIT_N(n,i) do { (i)->next##n = 0; (i)->prev##n = 0; } while(0)
  44 #define DEQ_ITEM_INIT(i) DEQ_ITEM_INIT_N(,i)
  45 #define DEQ_HEAD(d) ((d).head)
  46 #define DEQ_TAIL(d) ((d).tail)
  47 #define DEQ_SIZE(d) ((d).size)
  48 #define DEQ_NEXT_N(n,i) (i)->next##n
  49 #define DEQ_NEXT(i) DEQ_NEXT_N(,i)
  50 #define DEQ_PREV_N(n,i) (i)->prev##n
  51 #define DEQ_PREV(i) DEQ_PREV_N(,i)
  52 #define DEQ_MOVE(d1,d2) do {d2 = d1; DEQ_INIT(d1);} while (0)
  53 /**
  54  *@pre ptr points to first element of deq
  55  *@post ptr points to first element of deq that passes test, or 0. Test should involve ptr.
  56  */
  57 #define DEQ_FIND_N(n,ptr,test) while((ptr) && !(test)) ptr = DEQ_NEXT_N(n,ptr);
  58 #define DEQ_FIND(ptr,test) DEQ_FIND_N(,ptr,test)
  59
  60 #define DEQ_INSERT_HEAD_N(n,d,i)  \
  61 do {                              \
  62     CT_ASSERT((i)->next##n == 0); \
  63     CT_ASSERT((i)->prev##n == 0); \
  64     if ((d).head) {               \
  65         (i)->next##n = (d).head;  \
  66         (d).head->prev##n = i;    \
  67     } else {                      \
  68         (d).tail = i;             \
  69         (i)->next##n = 0;         \
  70         CT_ASSERT((d).size == 0); \
  71     }                             \
  72     (i)->prev##n = 0;             \
  73     (d).head = i;                 \
  74     (d).size++;                   \
  75 } while (0)
  76 #define DEQ_INSERT_HEAD(d,i) DEQ_INSERT_HEAD_N(,d,i)
  77
  78 #define DEQ_INSERT_TAIL_N(n,d,i)  \
  79 do {                              \
  80     CT_ASSERT((i)->next##n == 0); \
  81     CT_ASSERT((i)->prev##n == 0); \
  82     if ((d).tail) {               \
  83         (i)->prev##n = (d).tail;  \
  84         (d).tail->next##n = i;    \
  85     } else {                      \
  86         (d).head = i;             \
  87         (i)->prev##n = 0;         \
  88         CT_ASSERT((d).size == 0); \
  89     }                             \
  90     (i)->next##n = 0;             \
  91     (d).tail = i;                 \
  92     (d).size++;                   \
  93 } while (0)
  94 #define DEQ_INSERT_TAIL(d,i) DEQ_INSERT_TAIL_N(,d,i)
  95
  96 #define DEQ_REMOVE_HEAD_N(n,d)    \
  97 do {                              \
  98     CT_ASSERT((d).head);          \
  99     if ((d).head) {               \
 100         (d).scratch = (d).head;   \
 101         (d).head = (d).head->next##n;  \
 102         if ((d).head == 0) {      \
 103             (d).tail = 0;         \
 104             CT_ASSERT((d).size == 1); \
 105         } else                     \
 106             (d).head->prev##n = 0; \
 107         (d).size--;                \
 108         (d).scratch->next##n = 0;  \
 109         (d).scratch->prev##n = 0;  \
 110     }                              \
 111 } while (0)
 112 #define DEQ_REMOVE_HEAD(d)  DEQ_REMOVE_HEAD_N(,d)
 113
 114 #define DEQ_REMOVE_TAIL_N(n,d)  \
 115 do {                            \
 116     CT_ASSERT((d).tail);        \
 117     if ((d).tail) {             \
 118         (d).scratch = (d).tail; \
 119         (d).tail = (d).tail->prev##n;  \
 120         if ((d).tail == 0) {    \
 121             (d).head = 0;       \
 122             CT_ASSERT((d).size == 1); \
 123         } else                  \
 124             (d).tail->next##n = 0; \
 125         (d).size--;             \
 126         (d).scratch->next##n = 0;  \
 127         (d).scratch->prev##n = 0;  \
 128     }                           \
 129 } while (0)
 130 #define DEQ_REMOVE_TAIL(d) DEQ_REMOVE_TAIL_N(,d)
 131
 132 #define DEQ_INSERT_AFTER_N(n,d,i,a) \
 133 do {                                \
 134     CT_ASSERT((i)->next##n == 0);   \
 135     CT_ASSERT((i)->prev##n == 0);   \
 136     CT_ASSERT(a);                   \
 137     if ((a)->next##n)               \
 138         (a)->next##n->prev##n = (i);  \
 139     else                            \
 140         (d).tail = (i);             \
 141     (i)->next##n = (a)->next##n;    \
 142     (i)->prev##n = (a);             \
 143     (a)->next##n = (i);             \
 144     (d).size++;                     \
 145 } while (0)
 146 #define DEQ_INSERT_AFTER(d,i,a) DEQ_INSERT_AFTER_N(,d,i,a)
 147
 148 #define DEQ_REMOVE_N(n,d,i)                    \
 149 do {                                           \
 150     if ((i)->next##n)                          \
 151         (i)->next##n->prev##n = (i)->prev##n;  \
 152     else                                       \
 153         (d).tail = (i)->prev##n;               \
 154     if ((i)->prev##n)                          \
 155         (i)->prev##n->next##n = (i)->next##n;  \
 156     else                                       \
 157         (d).head = (i)->next##n;               \
 158     CT_ASSERT((d).size > 0);                   \
 159     (d).size--;                                \
 160     (i)->next##n = 0;                          \
 161     (i)->prev##n = 0;                          \
 162     CT_ASSERT((d).size || (!(d).head && !(d).tail)); \
 163 } while (0)
 164 #define DEQ_REMOVE(d,i) DEQ_REMOVE_N(,d,i)
 165
 166 #define DEQ_APPEND_N(n,d1,d2)           \
 167 do {                                    \
 168     if (!(d1).head)                     \
 169         (d1) = (d2);                    \
 170     else if ((d2).head) {               \
 171         (d1).tail->next##n = (d2).head; \
 172         (d2).head->prev##n = (d1).tail; \
 173         (d1).tail = (d2).tail;          \
 174         (d1).size += (d2).size;         \
 175     }                                   \
 176     DEQ_INIT(d2);                       \
 177 } while (0)
 178 #define DEQ_APPEND(d1,d2) DEQ_APPEND_N(,d1,d2)
 179
 180 #endif