queue.h - dedup - deduplicating backup program
(HTM) git clone git://bitreich.org/dedup/ git://enlrupgkhuxnvlhsf6lc3fziv5h2hhfrinws65d7roiv6bfj7d652fid.onion/dedup/
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) Tags
(DIR) README
(DIR) LICENSE
---
queue.h (18350B)
---
1 /* $OpenBSD: queue.h,v 1.45 2018/07/12 14:22:54 sashan Exp $ */
2 /* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */
3
4 /*
5 * Copyright (c) 1991, 1993
6 * The Regents of the University of California. All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. Neither the name of the University nor the names of its contributors
17 * may be used to endorse or promote products derived from this software
18 * without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 *
32 * @(#)queue.h 8.5 (Berkeley) 8/20/94
33 */
34
35 #ifndef _SYS_QUEUE_H_
36 #define _SYS_QUEUE_H_
37
38 /*
39 * This file defines five types of data structures: singly-linked lists,
40 * lists, simple queues, tail queues and XOR simple queues.
41 *
42 *
43 * A singly-linked list is headed by a single forward pointer. The elements
44 * are singly linked for minimum space and pointer manipulation overhead at
45 * the expense of O(n) removal for arbitrary elements. New elements can be
46 * added to the list after an existing element or at the head of the list.
47 * Elements being removed from the head of the list should use the explicit
48 * macro for this purpose for optimum efficiency. A singly-linked list may
49 * only be traversed in the forward direction. Singly-linked lists are ideal
50 * for applications with large datasets and few or no removals or for
51 * implementing a LIFO queue.
52 *
53 * A list is headed by a single forward pointer (or an array of forward
54 * pointers for a hash table header). The elements are doubly linked
55 * so that an arbitrary element can be removed without a need to
56 * traverse the list. New elements can be added to the list before
57 * or after an existing element or at the head of the list. A list
58 * may only be traversed in the forward direction.
59 *
60 * A simple queue is headed by a pair of pointers, one to the head of the
61 * list and the other to the tail of the list. The elements are singly
62 * linked to save space, so elements can only be removed from the
63 * head of the list. New elements can be added to the list before or after
64 * an existing element, at the head of the list, or at the end of the
65 * list. A simple queue may only be traversed in the forward direction.
66 *
67 * A tail queue is headed by a pair of pointers, one to the head of the
68 * list and the other to the tail of the list. The elements are doubly
69 * linked so that an arbitrary element can be removed without a need to
70 * traverse the list. New elements can be added to the list before or
71 * after an existing element, at the head of the list, or at the end of
72 * the list. A tail queue may be traversed in either direction.
73 *
74 * An XOR simple queue is used in the same way as a regular simple queue.
75 * The difference is that the head structure also includes a "cookie" that
76 * is XOR'd with the queue pointer (first, last or next) to generate the
77 * real pointer value.
78 *
79 * For details on the use of these macros, see the queue(3) manual page.
80 */
81
82 #if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC))
83 #define _Q_INVALID ((void *)-1)
84 #define _Q_INVALIDATE(a) (a) = _Q_INVALID
85 #else
86 #define _Q_INVALIDATE(a)
87 #endif
88
89 /*
90 * Singly-linked List definitions.
91 */
92 #define SLIST_HEAD(name, type) \
93 struct name { \
94 struct type *slh_first; /* first element */ \
95 }
96
97 #define SLIST_HEAD_INITIALIZER(head) \
98 { NULL }
99
100 #define SLIST_ENTRY(type) \
101 struct { \
102 struct type *sle_next; /* next element */ \
103 }
104
105 /*
106 * Singly-linked List access methods.
107 */
108 #define SLIST_FIRST(head) ((head)->slh_first)
109 #define SLIST_END(head) NULL
110 #define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head))
111 #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
112
113 #define SLIST_FOREACH(var, head, field) \
114 for((var) = SLIST_FIRST(head); \
115 (var) != SLIST_END(head); \
116 (var) = SLIST_NEXT(var, field))
117
118 #define SLIST_FOREACH_SAFE(var, head, field, tvar) \
119 for ((var) = SLIST_FIRST(head); \
120 (var) && ((tvar) = SLIST_NEXT(var, field), 1); \
121 (var) = (tvar))
122
123 /*
124 * Singly-linked List functions.
125 */
126 #define SLIST_INIT(head) { \
127 SLIST_FIRST(head) = SLIST_END(head); \
128 }
129
130 #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
131 (elm)->field.sle_next = (slistelm)->field.sle_next; \
132 (slistelm)->field.sle_next = (elm); \
133 } while (0)
134
135 #define SLIST_INSERT_HEAD(head, elm, field) do { \
136 (elm)->field.sle_next = (head)->slh_first; \
137 (head)->slh_first = (elm); \
138 } while (0)
139
140 #define SLIST_REMOVE_AFTER(elm, field) do { \
141 (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \
142 } while (0)
143
144 #define SLIST_REMOVE_HEAD(head, field) do { \
145 (head)->slh_first = (head)->slh_first->field.sle_next; \
146 } while (0)
147
148 #define SLIST_REMOVE(head, elm, type, field) do { \
149 if ((head)->slh_first == (elm)) { \
150 SLIST_REMOVE_HEAD((head), field); \
151 } else { \
152 struct type *curelm = (head)->slh_first; \
153 \
154 while (curelm->field.sle_next != (elm)) \
155 curelm = curelm->field.sle_next; \
156 curelm->field.sle_next = \
157 curelm->field.sle_next->field.sle_next; \
158 } \
159 _Q_INVALIDATE((elm)->field.sle_next); \
160 } while (0)
161
162 /*
163 * List definitions.
164 */
165 #define LIST_HEAD(name, type) \
166 struct name { \
167 struct type *lh_first; /* first element */ \
168 }
169
170 #define LIST_HEAD_INITIALIZER(head) \
171 { NULL }
172
173 #define LIST_ENTRY(type) \
174 struct { \
175 struct type *le_next; /* next element */ \
176 struct type **le_prev; /* address of previous next element */ \
177 }
178
179 /*
180 * List access methods.
181 */
182 #define LIST_FIRST(head) ((head)->lh_first)
183 #define LIST_END(head) NULL
184 #define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head))
185 #define LIST_NEXT(elm, field) ((elm)->field.le_next)
186
187 #define LIST_FOREACH(var, head, field) \
188 for((var) = LIST_FIRST(head); \
189 (var)!= LIST_END(head); \
190 (var) = LIST_NEXT(var, field))
191
192 #define LIST_FOREACH_SAFE(var, head, field, tvar) \
193 for ((var) = LIST_FIRST(head); \
194 (var) && ((tvar) = LIST_NEXT(var, field), 1); \
195 (var) = (tvar))
196
197 /*
198 * List functions.
199 */
200 #define LIST_INIT(head) do { \
201 LIST_FIRST(head) = LIST_END(head); \
202 } while (0)
203
204 #define LIST_INSERT_AFTER(listelm, elm, field) do { \
205 if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
206 (listelm)->field.le_next->field.le_prev = \
207 &(elm)->field.le_next; \
208 (listelm)->field.le_next = (elm); \
209 (elm)->field.le_prev = &(listelm)->field.le_next; \
210 } while (0)
211
212 #define LIST_INSERT_BEFORE(listelm, elm, field) do { \
213 (elm)->field.le_prev = (listelm)->field.le_prev; \
214 (elm)->field.le_next = (listelm); \
215 *(listelm)->field.le_prev = (elm); \
216 (listelm)->field.le_prev = &(elm)->field.le_next; \
217 } while (0)
218
219 #define LIST_INSERT_HEAD(head, elm, field) do { \
220 if (((elm)->field.le_next = (head)->lh_first) != NULL) \
221 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
222 (head)->lh_first = (elm); \
223 (elm)->field.le_prev = &(head)->lh_first; \
224 } while (0)
225
226 #define LIST_REMOVE(elm, field) do { \
227 if ((elm)->field.le_next != NULL) \
228 (elm)->field.le_next->field.le_prev = \
229 (elm)->field.le_prev; \
230 *(elm)->field.le_prev = (elm)->field.le_next; \
231 _Q_INVALIDATE((elm)->field.le_prev); \
232 _Q_INVALIDATE((elm)->field.le_next); \
233 } while (0)
234
235 #define LIST_REPLACE(elm, elm2, field) do { \
236 if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \
237 (elm2)->field.le_next->field.le_prev = \
238 &(elm2)->field.le_next; \
239 (elm2)->field.le_prev = (elm)->field.le_prev; \
240 *(elm2)->field.le_prev = (elm2); \
241 _Q_INVALIDATE((elm)->field.le_prev); \
242 _Q_INVALIDATE((elm)->field.le_next); \
243 } while (0)
244
245 /*
246 * Simple queue definitions.
247 */
248 #define SIMPLEQ_HEAD(name, type) \
249 struct name { \
250 struct type *sqh_first; /* first element */ \
251 struct type **sqh_last; /* addr of last next element */ \
252 }
253
254 #define SIMPLEQ_HEAD_INITIALIZER(head) \
255 { NULL, &(head).sqh_first }
256
257 #define SIMPLEQ_ENTRY(type) \
258 struct { \
259 struct type *sqe_next; /* next element */ \
260 }
261
262 /*
263 * Simple queue access methods.
264 */
265 #define SIMPLEQ_FIRST(head) ((head)->sqh_first)
266 #define SIMPLEQ_END(head) NULL
267 #define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
268 #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
269
270 #define SIMPLEQ_FOREACH(var, head, field) \
271 for((var) = SIMPLEQ_FIRST(head); \
272 (var) != SIMPLEQ_END(head); \
273 (var) = SIMPLEQ_NEXT(var, field))
274
275 #define SIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \
276 for ((var) = SIMPLEQ_FIRST(head); \
277 (var) && ((tvar) = SIMPLEQ_NEXT(var, field), 1); \
278 (var) = (tvar))
279
280 /*
281 * Simple queue functions.
282 */
283 #define SIMPLEQ_INIT(head) do { \
284 (head)->sqh_first = NULL; \
285 (head)->sqh_last = &(head)->sqh_first; \
286 } while (0)
287
288 #define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \
289 if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
290 (head)->sqh_last = &(elm)->field.sqe_next; \
291 (head)->sqh_first = (elm); \
292 } while (0)
293
294 #define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \
295 (elm)->field.sqe_next = NULL; \
296 *(head)->sqh_last = (elm); \
297 (head)->sqh_last = &(elm)->field.sqe_next; \
298 } while (0)
299
300 #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
301 if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
302 (head)->sqh_last = &(elm)->field.sqe_next; \
303 (listelm)->field.sqe_next = (elm); \
304 } while (0)
305
306 #define SIMPLEQ_REMOVE_HEAD(head, field) do { \
307 if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
308 (head)->sqh_last = &(head)->sqh_first; \
309 } while (0)
310
311 #define SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \
312 if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \
313 == NULL) \
314 (head)->sqh_last = &(elm)->field.sqe_next; \
315 } while (0)
316
317 #define SIMPLEQ_CONCAT(head1, head2) do { \
318 if (!SIMPLEQ_EMPTY((head2))) { \
319 *(head1)->sqh_last = (head2)->sqh_first; \
320 (head1)->sqh_last = (head2)->sqh_last; \
321 SIMPLEQ_INIT((head2)); \
322 } \
323 } while (0)
324
325 /*
326 * XOR Simple queue definitions.
327 */
328 #define XSIMPLEQ_HEAD(name, type) \
329 struct name { \
330 struct type *sqx_first; /* first element */ \
331 struct type **sqx_last; /* addr of last next element */ \
332 unsigned long sqx_cookie; \
333 }
334
335 #define XSIMPLEQ_ENTRY(type) \
336 struct { \
337 struct type *sqx_next; /* next element */ \
338 }
339
340 /*
341 * XOR Simple queue access methods.
342 */
343 #define XSIMPLEQ_XOR(head, ptr) ((__typeof(ptr))((head)->sqx_cookie ^ \
344 (unsigned long)(ptr)))
345 #define XSIMPLEQ_FIRST(head) XSIMPLEQ_XOR(head, ((head)->sqx_first))
346 #define XSIMPLEQ_END(head) NULL
347 #define XSIMPLEQ_EMPTY(head) (XSIMPLEQ_FIRST(head) == XSIMPLEQ_END(head))
348 #define XSIMPLEQ_NEXT(head, elm, field) XSIMPLEQ_XOR(head, ((elm)->field.sqx_next))
349
350
351 #define XSIMPLEQ_FOREACH(var, head, field) \
352 for ((var) = XSIMPLEQ_FIRST(head); \
353 (var) != XSIMPLEQ_END(head); \
354 (var) = XSIMPLEQ_NEXT(head, var, field))
355
356 #define XSIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \
357 for ((var) = XSIMPLEQ_FIRST(head); \
358 (var) && ((tvar) = XSIMPLEQ_NEXT(head, var, field), 1); \
359 (var) = (tvar))
360
361 /*
362 * XOR Simple queue functions.
363 */
364 #define XSIMPLEQ_INIT(head) do { \
365 arc4random_buf(&(head)->sqx_cookie, sizeof((head)->sqx_cookie)); \
366 (head)->sqx_first = XSIMPLEQ_XOR(head, NULL); \
367 (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \
368 } while (0)
369
370 #define XSIMPLEQ_INSERT_HEAD(head, elm, field) do { \
371 if (((elm)->field.sqx_next = (head)->sqx_first) == \
372 XSIMPLEQ_XOR(head, NULL)) \
373 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
374 (head)->sqx_first = XSIMPLEQ_XOR(head, (elm)); \
375 } while (0)
376
377 #define XSIMPLEQ_INSERT_TAIL(head, elm, field) do { \
378 (elm)->field.sqx_next = XSIMPLEQ_XOR(head, NULL); \
379 *(XSIMPLEQ_XOR(head, (head)->sqx_last)) = XSIMPLEQ_XOR(head, (elm)); \
380 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
381 } while (0)
382
383 #define XSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
384 if (((elm)->field.sqx_next = (listelm)->field.sqx_next) == \
385 XSIMPLEQ_XOR(head, NULL)) \
386 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
387 (listelm)->field.sqx_next = XSIMPLEQ_XOR(head, (elm)); \
388 } while (0)
389
390 #define XSIMPLEQ_REMOVE_HEAD(head, field) do { \
391 if (((head)->sqx_first = XSIMPLEQ_XOR(head, \
392 (head)->sqx_first)->field.sqx_next) == XSIMPLEQ_XOR(head, NULL)) \
393 (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \
394 } while (0)
395
396 #define XSIMPLEQ_REMOVE_AFTER(head, elm, field) do { \
397 if (((elm)->field.sqx_next = XSIMPLEQ_XOR(head, \
398 (elm)->field.sqx_next)->field.sqx_next) \
399 == XSIMPLEQ_XOR(head, NULL)) \
400 (head)->sqx_last = \
401 XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
402 } while (0)
403
404
405 /*
406 * Tail queue definitions.
407 */
408 #define TAILQ_HEAD(name, type) \
409 struct name { \
410 struct type *tqh_first; /* first element */ \
411 struct type **tqh_last; /* addr of last next element */ \
412 }
413
414 #define TAILQ_HEAD_INITIALIZER(head) \
415 { NULL, &(head).tqh_first }
416
417 #define TAILQ_ENTRY(type) \
418 struct { \
419 struct type *tqe_next; /* next element */ \
420 struct type **tqe_prev; /* address of previous next element */ \
421 }
422
423 /*
424 * Tail queue access methods.
425 */
426 #define TAILQ_FIRST(head) ((head)->tqh_first)
427 #define TAILQ_END(head) NULL
428 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
429 #define TAILQ_LAST(head, headname) \
430 (*(((struct headname *)((head)->tqh_last))->tqh_last))
431 /* XXX */
432 #define TAILQ_PREV(elm, headname, field) \
433 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
434 #define TAILQ_EMPTY(head) \
435 (TAILQ_FIRST(head) == TAILQ_END(head))
436
437 #define TAILQ_FOREACH(var, head, field) \
438 for((var) = TAILQ_FIRST(head); \
439 (var) != TAILQ_END(head); \
440 (var) = TAILQ_NEXT(var, field))
441
442 #define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
443 for ((var) = TAILQ_FIRST(head); \
444 (var) != TAILQ_END(head) && \
445 ((tvar) = TAILQ_NEXT(var, field), 1); \
446 (var) = (tvar))
447
448
449 #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
450 for((var) = TAILQ_LAST(head, headname); \
451 (var) != TAILQ_END(head); \
452 (var) = TAILQ_PREV(var, headname, field))
453
454 #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
455 for ((var) = TAILQ_LAST(head, headname); \
456 (var) != TAILQ_END(head) && \
457 ((tvar) = TAILQ_PREV(var, headname, field), 1); \
458 (var) = (tvar))
459
460 /*
461 * Tail queue functions.
462 */
463 #define TAILQ_INIT(head) do { \
464 (head)->tqh_first = NULL; \
465 (head)->tqh_last = &(head)->tqh_first; \
466 } while (0)
467
468 #define TAILQ_INSERT_HEAD(head, elm, field) do { \
469 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
470 (head)->tqh_first->field.tqe_prev = \
471 &(elm)->field.tqe_next; \
472 else \
473 (head)->tqh_last = &(elm)->field.tqe_next; \
474 (head)->tqh_first = (elm); \
475 (elm)->field.tqe_prev = &(head)->tqh_first; \
476 } while (0)
477
478 #define TAILQ_INSERT_TAIL(head, elm, field) do { \
479 (elm)->field.tqe_next = NULL; \
480 (elm)->field.tqe_prev = (head)->tqh_last; \
481 *(head)->tqh_last = (elm); \
482 (head)->tqh_last = &(elm)->field.tqe_next; \
483 } while (0)
484
485 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
486 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
487 (elm)->field.tqe_next->field.tqe_prev = \
488 &(elm)->field.tqe_next; \
489 else \
490 (head)->tqh_last = &(elm)->field.tqe_next; \
491 (listelm)->field.tqe_next = (elm); \
492 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
493 } while (0)
494
495 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
496 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
497 (elm)->field.tqe_next = (listelm); \
498 *(listelm)->field.tqe_prev = (elm); \
499 (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
500 } while (0)
501
502 #define TAILQ_REMOVE(head, elm, field) do { \
503 if (((elm)->field.tqe_next) != NULL) \
504 (elm)->field.tqe_next->field.tqe_prev = \
505 (elm)->field.tqe_prev; \
506 else \
507 (head)->tqh_last = (elm)->field.tqe_prev; \
508 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
509 _Q_INVALIDATE((elm)->field.tqe_prev); \
510 _Q_INVALIDATE((elm)->field.tqe_next); \
511 } while (0)
512
513 #define TAILQ_REPLACE(head, elm, elm2, field) do { \
514 if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \
515 (elm2)->field.tqe_next->field.tqe_prev = \
516 &(elm2)->field.tqe_next; \
517 else \
518 (head)->tqh_last = &(elm2)->field.tqe_next; \
519 (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \
520 *(elm2)->field.tqe_prev = (elm2); \
521 _Q_INVALIDATE((elm)->field.tqe_prev); \
522 _Q_INVALIDATE((elm)->field.tqe_next); \
523 } while (0)
524
525 #define TAILQ_CONCAT(head1, head2, field) do { \
526 if (!TAILQ_EMPTY(head2)) { \
527 *(head1)->tqh_last = (head2)->tqh_first; \
528 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
529 (head1)->tqh_last = (head2)->tqh_last; \
530 TAILQ_INIT((head2)); \
531 } \
532 } while (0)
533
534 #endif /* !_SYS_QUEUE_H_ */