src/utils_deq.h

   1 /**
   2  * collectd - src/utils_deq.h
   3  * Copyright(c) 2017 Red Hat Inc.
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a
   6  * copy of this software and associated documentation files (the "Software"),
   7  * to deal in the Software without restriction, including without limitation
   8  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   9  * and/or sell copies of the Software, and to permit persons to whom the
  10  * Software is furnished to do so, subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be included in
  13  * all copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  18  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  21  * DEALINGS IN THE SOFTWARE.
  22  *
  23  * Authors:
  24  *   Andy Smith <ansmith@redhat.com>
  25  */
  26
  27 #ifndef utils_deq_h
  28 #define utils_deq_h 1
  29
  30 #include <assert.h>
  31 #include <memory.h>
  32 #include <stdlib.h>
  33
  34 #define CT_ASSERT(exp)                                                         \
  35   { assert(exp); }
  36
  37 #define NEW(t) (t *)malloc(sizeof(t))
  38 #define NEW_ARRAY(t, n) (t *)malloc(sizeof(t) * (n))
  39 #define NEW_PTR_ARRAY(t, n) (t **)malloc(sizeof(t *) * (n))
  40
  41 #define ZERO(p) memset(p, 0, sizeof(*p))
  42
  43 #define DEQ_DECLARE(i, d)                                                      \
  44   typedef struct {                                                             \
  45     i *head;                                                                   \
  46     i *tail;                                                                   \
  47     i *scratch;                                                                \
  48     size_t size;                                                               \
  49   } d
  50
  51 #define DEQ_LINKS_N(n, t)                                                      \
  52   t *prev##n;                                                                  \
  53   t *next##n
  54 #define DEQ_LINKS(t) DEQ_LINKS_N(, t)
  55 #define DEQ_EMPTY                                                              \
  56   { 0, 0, 0, 0 }
  57
  58 #define DEQ_INIT(d)                                                            \
  59   do {                                                                         \
  60     (d).head = 0;                                                              \
  61     (d).tail = 0;                                                              \
  62     (d).scratch = 0;                                                           \
  63     (d).size = 0;                                                              \
  64   } while (0)
  65 #define DEQ_IS_EMPTY(d) ((d).head == 0)
  66 #define DEQ_ITEM_INIT_N(n, i)                                                  \
  67   do {                                                                         \
  68     (i)->next##n = 0;                                                          \
  69     (i)->prev##n = 0;                                                          \
  70   } while (0)
  71 #define DEQ_ITEM_INIT(i) DEQ_ITEM_INIT_N(, i)
  72 #define DEQ_HEAD(d) ((d).head)
  73 #define DEQ_TAIL(d) ((d).tail)
  74 #define DEQ_SIZE(d) ((d).size)
  75 #define DEQ_NEXT_N(n, i) (i)->next##n
  76 #define DEQ_NEXT(i) DEQ_NEXT_N(, i)
  77 #define DEQ_PREV_N(n, i) (i)->prev##n
  78 #define DEQ_PREV(i) DEQ_PREV_N(, i)
  79 #define DEQ_MOVE(d1, d2)                                                       \
  80   do {                                                                         \
  81     d2 = d1;                                                                   \
  82     DEQ_INIT(d1);                                                              \
  83   } while (0)
  84 /**
  85  *@pre ptr points to first element of deq
  86  *@post ptr points to first element of deq that passes test, or 0. Test should
  87  *involve ptr.
  88  */
  89 #define DEQ_FIND_N(n, ptr, test)                                               \
  90   while ((ptr) && !(test))                                                     \
  91     ptr = DEQ_NEXT_N(n, ptr);
  92 #define DEQ_FIND(ptr, test) DEQ_FIND_N(, ptr, test)
  93
  94 #define DEQ_INSERT_HEAD_N(n, d, i)                                             \
  95   do {                                                                         \
  96     CT_ASSERT((i)->next##n == 0);                                              \
  97     CT_ASSERT((i)->prev##n == 0);                                              \
  98     if ((d).head) {                                                            \
  99       (i)->next##n = (d).head;                                                 \
 100       (d).head->prev##n = i;                                                   \
 101     } else {                                                                   \
 102       (d).tail = i;                                                            \
 103       (i)->next##n = 0;                                                        \
 104       CT_ASSERT((d).size == 0);                                                \
 105     }                                                                          \
 106     (i)->prev##n = 0;                                                          \
 107     (d).head = i;                                                              \
 108     (d).size++;                                                                \
 109   } while (0)
 110 #define DEQ_INSERT_HEAD(d, i) DEQ_INSERT_HEAD_N(, d, i)
 111
 112 #define DEQ_INSERT_TAIL_N(n, d, i)                                             \
 113   do {                                                                         \
 114     CT_ASSERT((i)->next##n == 0);                                              \
 115     CT_ASSERT((i)->prev##n == 0);                                              \
 116     if ((d).tail) {                                                            \
 117       (i)->prev##n = (d).tail;                                                 \
 118       (d).tail->next##n = i;                                                   \
 119     } else {                                                                   \
 120       (d).head = i;                                                            \
 121       (i)->prev##n = 0;                                                        \
 122       CT_ASSERT((d).size == 0);                                                \
 123     }                                                                          \
 124     (i)->next##n = 0;                                                          \
 125     (d).tail = i;                                                              \
 126     (d).size++;                                                                \
 127   } while (0)
 128 #define DEQ_INSERT_TAIL(d, i) DEQ_INSERT_TAIL_N(, d, i)
 129
 130 #define DEQ_REMOVE_HEAD_N(n, d)                                                \
 131   do {                                                                         \
 132     CT_ASSERT((d).head);                                                       \
 133     if ((d).head) {                                                            \
 134       (d).scratch = (d).head;                                                  \
 135       (d).head = (d).head->next##n;                                            \
 136       if ((d).head == 0) {                                                     \
 137         (d).tail = 0;                                                          \
 138         CT_ASSERT((d).size == 1);                                              \
 139       } else                                                                   \
 140         (d).head->prev##n = 0;                                                 \
 141       (d).size--;                                                              \
 142       (d).scratch->next##n = 0;                                                \
 143       (d).scratch->prev##n = 0;                                                \
 144     }                                                                          \
 145   } while (0)
 146 #define DEQ_REMOVE_HEAD(d) DEQ_REMOVE_HEAD_N(, d)
 147
 148 #define DEQ_REMOVE_TAIL_N(n, d)                                                \
 149   do {                                                                         \
 150     CT_ASSERT((d).tail);                                                       \
 151     if ((d).tail) {                                                            \
 152       (d).scratch = (d).tail;                                                  \
 153       (d).tail = (d).tail->prev##n;                                            \
 154       if ((d).tail == 0) {                                                     \
 155         (d).head = 0;                                                          \
 156         CT_ASSERT((d).size == 1);                                              \
 157       } else                                                                   \
 158         (d).tail->next##n = 0;                                                 \
 159       (d).size--;                                                              \
 160       (d).scratch->next##n = 0;                                                \
 161       (d).scratch->prev##n = 0;                                                \
 162     }                                                                          \
 163   } while (0)
 164 #define DEQ_REMOVE_TAIL(d) DEQ_REMOVE_TAIL_N(, d)
 165
 166 #define DEQ_INSERT_AFTER_N(n, d, i, a)                                         \
 167   do {                                                                         \
 168     CT_ASSERT((i)->next##n == 0);                                              \
 169     CT_ASSERT((i)->prev##n == 0);                                              \
 170     CT_ASSERT(a);                                                              \
 171     if ((a)->next##n)                                                          \
 172       (a)->next##n->prev##n = (i);                                             \
 173     else                                                                       \
 174       (d).tail = (i);                                                          \
 175     (i)->next##n = (a)->next##n;                                               \
 176     (i)->prev##n = (a);                                                        \
 177     (a)->next##n = (i);                                                        \
 178     (d).size++;                                                                \
 179   } while (0)
 180 #define DEQ_INSERT_AFTER(d, i, a) DEQ_INSERT_AFTER_N(, d, i, a)
 181
 182 #define DEQ_REMOVE_N(n, d, i)                                                  \
 183   do {                                                                         \
 184     if ((i)->next##n)                                                          \
 185       (i)->next##n->prev##n = (i)->prev##n;                                    \
 186     else                                                                       \
 187       (d).tail = (i)->prev##n;                                                 \
 188     if ((i)->prev##n)                                                          \
 189       (i)->prev##n->next##n = (i)->next##n;                                    \
 190     else                                                                       \
 191       (d).head = (i)->next##n;                                                 \
 192     CT_ASSERT((d).size > 0);                                                   \
 193     (d).size--;                                                                \
 194     (i)->next##n = 0;                                                          \
 195     (i)->prev##n = 0;                                                          \
 196     CT_ASSERT((d).size || (!(d).head && !(d).tail));                           \
 197   } while (0)
 198 #define DEQ_REMOVE(d, i) DEQ_REMOVE_N(, d, i)
 199
 200 #define DEQ_APPEND_N(n, d1, d2)                                                \
 201   do {                                                                         \
 202     if (!(d1).head)                                                            \
 203       (d1) = (d2);                                                             \
 204     else if ((d2).head) {                                                      \
 205       (d1).tail->next##n = (d2).head;                                          \
 206       (d2).head->prev##n = (d1).tail;                                          \
 207       (d1).tail = (d2).tail;                                                   \
 208       (d1).size += (d2).size;                                                  \
 209     }                                                                          \
 210     DEQ_INIT(d2);                                                              \
 211   } while (0)
 212 #define DEQ_APPEND(d1, d2) DEQ_APPEND_N(, d1, d2)
 213
 214 #endif