2 * collectd - src/utils_deq.h
3 * Copyright(c) 2017 Red Hat Inc.
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:
12 * The above copyright notice and this permission notice shall be included in
13 * all copies or substantial portions of the Software.
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.
24 * Andy Smith <ansmith@redhat.com>
34 #define CT_ASSERT(exp) \
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))
41 #define ZERO(p) memset(p, 0, sizeof(*p))
43 #define DEQ_DECLARE(i, d) \
51 #define DEQ_LINKS_N(n, t) \
54 #define DEQ_LINKS(t) DEQ_LINKS_N(, t)
65 #define DEQ_IS_EMPTY(d) ((d).head == 0)
66 #define DEQ_ITEM_INIT_N(n, i) \
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) \
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
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)
94 #define DEQ_INSERT_HEAD_N(n, d, i) \
96 CT_ASSERT((i)->next##n == 0); \
97 CT_ASSERT((i)->prev##n == 0); \
99 (i)->next##n = (d).head; \
100 (d).head->prev##n = i; \
104 CT_ASSERT((d).size == 0); \
110 #define DEQ_INSERT_HEAD(d, i) DEQ_INSERT_HEAD_N(, d, i)
112 #define DEQ_INSERT_TAIL_N(n, d, i) \
114 CT_ASSERT((i)->next##n == 0); \
115 CT_ASSERT((i)->prev##n == 0); \
117 (i)->prev##n = (d).tail; \
118 (d).tail->next##n = i; \
122 CT_ASSERT((d).size == 0); \
128 #define DEQ_INSERT_TAIL(d, i) DEQ_INSERT_TAIL_N(, d, i)
130 #define DEQ_REMOVE_HEAD_N(n, d) \
132 CT_ASSERT((d).head); \
134 (d).scratch = (d).head; \
135 (d).head = (d).head->next##n; \
136 if ((d).head == 0) { \
138 CT_ASSERT((d).size == 1); \
140 (d).head->prev##n = 0; \
142 (d).scratch->next##n = 0; \
143 (d).scratch->prev##n = 0; \
146 #define DEQ_REMOVE_HEAD(d) DEQ_REMOVE_HEAD_N(, d)
148 #define DEQ_REMOVE_TAIL_N(n, d) \
150 CT_ASSERT((d).tail); \
152 (d).scratch = (d).tail; \
153 (d).tail = (d).tail->prev##n; \
154 if ((d).tail == 0) { \
156 CT_ASSERT((d).size == 1); \
158 (d).tail->next##n = 0; \
160 (d).scratch->next##n = 0; \
161 (d).scratch->prev##n = 0; \
164 #define DEQ_REMOVE_TAIL(d) DEQ_REMOVE_TAIL_N(, d)
166 #define DEQ_INSERT_AFTER_N(n, d, i, a) \
168 CT_ASSERT((i)->next##n == 0); \
169 CT_ASSERT((i)->prev##n == 0); \
172 (a)->next##n->prev##n = (i); \
175 (i)->next##n = (a)->next##n; \
176 (i)->prev##n = (a); \
177 (a)->next##n = (i); \
180 #define DEQ_INSERT_AFTER(d, i, a) DEQ_INSERT_AFTER_N(, d, i, a)
182 #define DEQ_REMOVE_N(n, d, i) \
185 (i)->next##n->prev##n = (i)->prev##n; \
187 (d).tail = (i)->prev##n; \
189 (i)->prev##n->next##n = (i)->next##n; \
191 (d).head = (i)->next##n; \
192 CT_ASSERT((d).size > 0); \
196 CT_ASSERT((d).size || (!(d).head && !(d).tail)); \
198 #define DEQ_REMOVE(d, i) DEQ_REMOVE_N(, d, i)
200 #define DEQ_APPEND_N(n, 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; \
212 #define DEQ_APPEND(d1, d2) DEQ_APPEND_N(, d1, d2)