Debian Codegraph @

src/utils/deq/deq.h

raw
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 <[email protected]>
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