1 /* ldap_queue.h -- queue macros */
3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
5 * Copyright 2001-2017 The OpenLDAP Foundation.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted only as authorized by the OpenLDAP
12 * A copy of this license is available in file LICENSE in the
13 * top-level directory of the distribution or, alternatively, at
14 * <http://www.OpenLDAP.org/license.html>.
16 /* Copyright (c) 1991, 1993
17 * The Regents of the University of California. All rights reserved.
19 * Redistribution and use in source and binary forms, with or without
20 * modification, are permitted provided that the following conditions
22 * 1. Redistributions of source code must retain the above copyright
23 * notice, this list of conditions and the following disclaimer.
24 * 2. Redistributions in binary form must reproduce the above copyright
25 * notice, this list of conditions and the following disclaimer in the
26 * documentation and/or other materials provided with the distribution.
27 * 3. All advertising materials mentioning features or use of this software
28 * must display the following acknowledgement:
29 * This product includes software developed by the University of
30 * California, Berkeley and its contributors.
31 * 4. Neither the name of the University nor the names of its contributors
32 * may be used to endorse or promote products derived from this software
33 * without specific prior written permission.
35 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
36 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
37 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
38 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
39 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
40 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
41 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
42 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
43 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
44 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
47 * @(#)queue.h 8.5 (Berkeley) 8/20/94
48 * $FreeBSD: src/sys/sys/queue.h,v 1.32.2.5 2001/09/30 21:12:54 luigi Exp $
50 * See also: ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change
53 * This work is derived from FreeBSD queue.h work. Adapted for use in
54 * OpenLDAP Software by Kurt D. Zeilenga.
57 #ifndef _LDAP_QUEUE_H_
58 #define _LDAP_QUEUE_H_
61 * This file defines five types of data structures: singly-linked lists,
62 * singly-linked tail queues, lists, tail queues, and circular queues.
64 * A singly-linked list is headed by a single forward pointer. The elements
65 * are singly linked for minimum space and pointer manipulation overhead at
66 * the expense of O(n) removal for arbitrary elements. New elements can be
67 * added to the list after an existing element or at the head of the list.
68 * Elements being removed from the head of the list should use the explicit
69 * macro for this purpose for optimum efficiency. A singly-linked list may
70 * only be traversed in the forward direction. Singly-linked lists are ideal
71 * for applications with large datasets and few or no removals or for
72 * implementing a LIFO queue.
74 * A singly-linked tail queue is headed by a pair of pointers, one to the
75 * head of the list and the other to the tail of the list. The elements are
76 * singly linked for minimum space and pointer manipulation overhead at the
77 * expense of O(n) removal for arbitrary elements. New elements can be added
78 * to the list after an existing element, at the head of the list, or at the
79 * end of the list. Elements being removed from the head of the tail queue
80 * should use the explicit macro for this purpose for optimum efficiency.
81 * A singly-linked tail queue may only be traversed in the forward direction.
82 * Singly-linked tail queues are ideal for applications with large datasets
83 * and few or no removals or for implementing a FIFO queue.
85 * A list is headed by a single forward pointer (or an array of forward
86 * pointers for a hash table header). The elements are doubly linked
87 * so that an arbitrary element can be removed without a need to
88 * traverse the list. New elements can be added to the list before
89 * or after an existing element or at the head of the list. A list
90 * may only be traversed in the forward direction.
92 * A tail queue is headed by a pair of pointers, one to the head of the
93 * list and the other to the tail of the list. The elements are doubly
94 * linked so that an arbitrary element can be removed without a need to
95 * traverse the list. New elements can be added to the list before or
96 * after an existing element, at the head of the list, or at the end of
97 * the list. A tail queue may be traversed in either direction.
99 * A circle queue is headed by a pair of pointers, one to the head of the
100 * list and the other to the tail of the list. The elements are doubly
101 * linked so that an arbitrary element can be removed without a need to
102 * traverse the list. New elements can be added to the list before or after
103 * an existing element, at the head of the list, or at the end of the list.
104 * A circle queue may be traversed in either direction, but has a more
105 * complex end of list detection.
107 * For details on the use of these macros, see the queue(3) manual page.
108 * All macros are prefixed with LDAP_.
110 * SLIST_ LIST_ STAILQ_ TAILQ_ CIRCLEQ_
114 * _ENTRY_INIT + + + + +
121 * _FOREACH_REVERSE - - - + +
122 * _INSERT_HEAD + + + + +
123 * _INSERT_BEFORE - + - + +
124 * _INSERT_AFTER + + + + +
125 * _INSERT_TAIL - - + + +
126 * _REMOVE_HEAD + - + - -
132 * Singly-linked List definitions.
134 #define LDAP_SLIST_HEAD(name, type) \
136 struct type *slh_first; /* first element */ \
139 #define LDAP_SLIST_HEAD_INITIALIZER(head) \
142 #define LDAP_SLIST_ENTRY(type) \
144 struct type *sle_next; /* next element */ \
147 #define LDAP_SLIST_ENTRY_INITIALIZER(entry) \
151 * Singly-linked List functions.
153 #define LDAP_SLIST_EMPTY(head) ((head)->slh_first == NULL)
155 #define LDAP_SLIST_FIRST(head) ((head)->slh_first)
157 #define LDAP_SLIST_FOREACH(var, head, field) \
158 for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
160 #define LDAP_SLIST_INIT(head) { \
161 (head)->slh_first = NULL; \
164 #define LDAP_SLIST_ENTRY_INIT(var, field) { \
165 (var)->field.sle_next = NULL; \
168 #define LDAP_SLIST_INSERT_AFTER(slistelm, elm, field) do { \
169 (elm)->field.sle_next = (slistelm)->field.sle_next; \
170 (slistelm)->field.sle_next = (elm); \
173 #define LDAP_SLIST_INSERT_HEAD(head, elm, field) do { \
174 (elm)->field.sle_next = (head)->slh_first; \
175 (head)->slh_first = (elm); \
178 #define LDAP_SLIST_NEXT(elm, field) ((elm)->field.sle_next)
180 #define LDAP_SLIST_REMOVE_HEAD(head, field) do { \
181 (head)->slh_first = (head)->slh_first->field.sle_next; \
184 #define LDAP_SLIST_REMOVE(head, elm, type, field) do { \
185 if ((head)->slh_first == (elm)) { \
186 LDAP_SLIST_REMOVE_HEAD((head), field); \
189 struct type *curelm = (head)->slh_first; \
190 while( curelm->field.sle_next != (elm) ) \
191 curelm = curelm->field.sle_next; \
192 curelm->field.sle_next = \
193 curelm->field.sle_next->field.sle_next; \
198 * Singly-linked Tail queue definitions.
200 #define LDAP_STAILQ_HEAD(name, type) \
202 struct type *stqh_first;/* first element */ \
203 struct type **stqh_last;/* addr of last next element */ \
206 #define LDAP_STAILQ_HEAD_INITIALIZER(head) \
207 { NULL, &(head).stqh_first }
209 #define LDAP_STAILQ_ENTRY(type) \
211 struct type *stqe_next; /* next element */ \
214 #define LDAP_STAILQ_ENTRY_INITIALIZER(entry) \
218 * Singly-linked Tail queue functions.
220 #define LDAP_STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
222 #define LDAP_STAILQ_INIT(head) do { \
223 (head)->stqh_first = NULL; \
224 (head)->stqh_last = &(head)->stqh_first; \
227 #define LDAP_STAILQ_ENTRY_INIT(var, field) { \
228 (var)->field.stqe_next = NULL; \
231 #define LDAP_STAILQ_FIRST(head) ((head)->stqh_first)
233 #define LDAP_STAILQ_LAST(head, type, field) \
234 (LDAP_STAILQ_EMPTY(head) ? \
237 ((char *)((head)->stqh_last) - offsetof(struct type, field))))
239 #define LDAP_STAILQ_FOREACH(var, head, field) \
240 for((var) = (head)->stqh_first; (var); (var) = (var)->field.stqe_next)
242 #define LDAP_STAILQ_INSERT_HEAD(head, elm, field) do { \
243 if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \
244 (head)->stqh_last = &(elm)->field.stqe_next; \
245 (head)->stqh_first = (elm); \
248 #define LDAP_STAILQ_INSERT_TAIL(head, elm, field) do { \
249 (elm)->field.stqe_next = NULL; \
250 *(head)->stqh_last = (elm); \
251 (head)->stqh_last = &(elm)->field.stqe_next; \
254 #define LDAP_STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \
255 if (((elm)->field.stqe_next = (tqelm)->field.stqe_next) == NULL)\
256 (head)->stqh_last = &(elm)->field.stqe_next; \
257 (tqelm)->field.stqe_next = (elm); \
260 #define LDAP_STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
262 #define LDAP_STAILQ_REMOVE_HEAD(head, field) do { \
263 if (((head)->stqh_first = \
264 (head)->stqh_first->field.stqe_next) == NULL) \
265 (head)->stqh_last = &(head)->stqh_first; \
268 #define LDAP_STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \
269 if (((head)->stqh_first = (elm)->field.stqe_next) == NULL) \
270 (head)->stqh_last = &(head)->stqh_first; \
273 #define LDAP_STAILQ_REMOVE(head, elm, type, field) do { \
274 if ((head)->stqh_first == (elm)) { \
275 LDAP_STAILQ_REMOVE_HEAD(head, field); \
278 struct type *curelm = (head)->stqh_first; \
279 while( curelm->field.stqe_next != (elm) ) \
280 curelm = curelm->field.stqe_next; \
281 if((curelm->field.stqe_next = \
282 curelm->field.stqe_next->field.stqe_next) == NULL) \
283 (head)->stqh_last = &(curelm)->field.stqe_next; \
290 #define LDAP_LIST_HEAD(name, type) \
292 struct type *lh_first; /* first element */ \
295 #define LDAP_LIST_HEAD_INITIALIZER(head) \
298 #define LDAP_LIST_ENTRY(type) \
300 struct type *le_next; /* next element */ \
301 struct type **le_prev; /* address of previous next element */ \
304 #define LDAP_LIST_ENTRY_INITIALIZER(entry) \
311 #define LDAP_LIST_EMPTY(head) ((head)->lh_first == NULL)
313 #define LDAP_LIST_FIRST(head) ((head)->lh_first)
315 #define LDAP_LIST_FOREACH(var, head, field) \
316 for((var) = (head)->lh_first; (var); (var) = (var)->field.le_next)
318 #define LDAP_LIST_INIT(head) do { \
319 (head)->lh_first = NULL; \
322 #define LDAP_LIST_ENTRY_INIT(var, field) do { \
323 (var)->field.le_next = NULL; \
324 (var)->field.le_prev = NULL; \
327 #define LDAP_LIST_INSERT_AFTER(listelm, elm, field) do { \
328 if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
329 (listelm)->field.le_next->field.le_prev = \
330 &(elm)->field.le_next; \
331 (listelm)->field.le_next = (elm); \
332 (elm)->field.le_prev = &(listelm)->field.le_next; \
335 #define LDAP_LIST_INSERT_BEFORE(listelm, elm, field) do { \
336 (elm)->field.le_prev = (listelm)->field.le_prev; \
337 (elm)->field.le_next = (listelm); \
338 *(listelm)->field.le_prev = (elm); \
339 (listelm)->field.le_prev = &(elm)->field.le_next; \
342 #define LDAP_LIST_INSERT_HEAD(head, elm, field) do { \
343 if (((elm)->field.le_next = (head)->lh_first) != NULL) \
344 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
345 (head)->lh_first = (elm); \
346 (elm)->field.le_prev = &(head)->lh_first; \
349 #define LDAP_LIST_NEXT(elm, field) ((elm)->field.le_next)
351 #define LDAP_LIST_REMOVE(elm, field) do { \
352 if ((elm)->field.le_next != NULL) \
353 (elm)->field.le_next->field.le_prev = \
354 (elm)->field.le_prev; \
355 *(elm)->field.le_prev = (elm)->field.le_next; \
359 * Tail queue definitions.
361 #define LDAP_TAILQ_HEAD(name, type) \
363 struct type *tqh_first; /* first element */ \
364 struct type **tqh_last; /* addr of last next element */ \
367 #define LDAP_TAILQ_HEAD_INITIALIZER(head) \
368 { NULL, &(head).tqh_first }
370 #define LDAP_TAILQ_ENTRY(type) \
372 struct type *tqe_next; /* next element */ \
373 struct type **tqe_prev; /* address of previous next element */ \
376 #define LDAP_TAILQ_ENTRY_INITIALIZER(entry) \
380 * Tail queue functions.
382 #define LDAP_TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
384 #define LDAP_TAILQ_FOREACH(var, head, field) \
385 for (var = LDAP_TAILQ_FIRST(head); var; var = LDAP_TAILQ_NEXT(var, field))
387 #define LDAP_TAILQ_FOREACH_REVERSE(var, head, headname, field) \
388 for ((var) = LDAP_TAILQ_LAST((head), headname); \
390 (var) = LDAP_TAILQ_PREV((var), headname, field))
392 #define LDAP_TAILQ_FIRST(head) ((head)->tqh_first)
394 #define LDAP_TAILQ_LAST(head, headname) \
395 (*(((struct headname *)((head)->tqh_last))->tqh_last))
397 #define LDAP_TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
399 #define LDAP_TAILQ_PREV(elm, headname, field) \
400 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
402 #define LDAP_TAILQ_INIT(head) do { \
403 (head)->tqh_first = NULL; \
404 (head)->tqh_last = &(head)->tqh_first; \
407 #define LDAP_TAILQ_ENTRY_INIT(var, field) do { \
408 (var)->field.tqe_next = NULL; \
409 (var)->field.tqe_prev = NULL; \
412 #define LDAP_TAILQ_INSERT_HEAD(head, elm, field) do { \
413 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
414 (head)->tqh_first->field.tqe_prev = \
415 &(elm)->field.tqe_next; \
417 (head)->tqh_last = &(elm)->field.tqe_next; \
418 (head)->tqh_first = (elm); \
419 (elm)->field.tqe_prev = &(head)->tqh_first; \
422 #define LDAP_TAILQ_INSERT_TAIL(head, elm, field) do { \
423 (elm)->field.tqe_next = NULL; \
424 (elm)->field.tqe_prev = (head)->tqh_last; \
425 *(head)->tqh_last = (elm); \
426 (head)->tqh_last = &(elm)->field.tqe_next; \
429 #define LDAP_TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
430 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
431 (elm)->field.tqe_next->field.tqe_prev = \
432 &(elm)->field.tqe_next; \
434 (head)->tqh_last = &(elm)->field.tqe_next; \
435 (listelm)->field.tqe_next = (elm); \
436 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
439 #define LDAP_TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
440 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
441 (elm)->field.tqe_next = (listelm); \
442 *(listelm)->field.tqe_prev = (elm); \
443 (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
446 #define LDAP_TAILQ_REMOVE(head, elm, field) do { \
447 if (((elm)->field.tqe_next) != NULL) \
448 (elm)->field.tqe_next->field.tqe_prev = \
449 (elm)->field.tqe_prev; \
451 (head)->tqh_last = (elm)->field.tqe_prev; \
452 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
456 * Circular queue definitions.
458 #define LDAP_CIRCLEQ_HEAD(name, type) \
460 struct type *cqh_first; /* first element */ \
461 struct type *cqh_last; /* last element */ \
464 #define LDAP_CIRCLEQ_ENTRY(type) \
466 struct type *cqe_next; /* next element */ \
467 struct type *cqe_prev; /* previous element */ \
471 * Circular queue functions.
473 #define LDAP_CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))
475 #define LDAP_CIRCLEQ_FIRST(head) ((head)->cqh_first)
477 #define LDAP_CIRCLEQ_FOREACH(var, head, field) \
478 for((var) = (head)->cqh_first; \
479 (var) != (void *)(head); \
480 (var) = (var)->field.cqe_next)
482 #define LDAP_CIRCLEQ_FOREACH_REVERSE(var, head, field) \
483 for((var) = (head)->cqh_last; \
484 (var) != (void *)(head); \
485 (var) = (var)->field.cqe_prev)
487 #define LDAP_CIRCLEQ_INIT(head) do { \
488 (head)->cqh_first = (void *)(head); \
489 (head)->cqh_last = (void *)(head); \
492 #define LDAP_CIRCLEQ_ENTRY_INIT(var, field) do { \
493 (var)->field.cqe_next = NULL; \
494 (var)->field.cqe_prev = NULL; \
497 #define LDAP_CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
498 (elm)->field.cqe_next = (listelm)->field.cqe_next; \
499 (elm)->field.cqe_prev = (listelm); \
500 if ((listelm)->field.cqe_next == (void *)(head)) \
501 (head)->cqh_last = (elm); \
503 (listelm)->field.cqe_next->field.cqe_prev = (elm); \
504 (listelm)->field.cqe_next = (elm); \
507 #define LDAP_CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
508 (elm)->field.cqe_next = (listelm); \
509 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
510 if ((listelm)->field.cqe_prev == (void *)(head)) \
511 (head)->cqh_first = (elm); \
513 (listelm)->field.cqe_prev->field.cqe_next = (elm); \
514 (listelm)->field.cqe_prev = (elm); \
517 #define LDAP_CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
518 (elm)->field.cqe_next = (head)->cqh_first; \
519 (elm)->field.cqe_prev = (void *)(head); \
520 if ((head)->cqh_last == (void *)(head)) \
521 (head)->cqh_last = (elm); \
523 (head)->cqh_first->field.cqe_prev = (elm); \
524 (head)->cqh_first = (elm); \
527 #define LDAP_CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
528 (elm)->field.cqe_next = (void *)(head); \
529 (elm)->field.cqe_prev = (head)->cqh_last; \
530 if ((head)->cqh_first == (void *)(head)) \
531 (head)->cqh_first = (elm); \
533 (head)->cqh_last->field.cqe_next = (elm); \
534 (head)->cqh_last = (elm); \
537 #define LDAP_CIRCLEQ_LAST(head) ((head)->cqh_last)
539 #define LDAP_CIRCLEQ_NEXT(elm,field) ((elm)->field.cqe_next)
541 #define LDAP_CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev)
543 #define LDAP_CIRCLEQ_REMOVE(head, elm, field) do { \
544 if ((elm)->field.cqe_next == (void *)(head)) \
545 (head)->cqh_last = (elm)->field.cqe_prev; \
547 (elm)->field.cqe_next->field.cqe_prev = \
548 (elm)->field.cqe_prev; \
549 if ((elm)->field.cqe_prev == (void *)(head)) \
550 (head)->cqh_first = (elm)->field.cqe_next; \
552 (elm)->field.cqe_prev->field.cqe_next = \
553 (elm)->field.cqe_next; \
556 #endif /* !_LDAP_QUEUE_H_ */