src/utils_deq.h

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