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 215