2 .\" The Regents of the University of California. All rights reserved.
3 .\" and Copyright (c) 2020 by Alejandro Colomar <colomar.6.4.3@gmail.com>
5 .\" SPDX-License-Identifier: BSD-3-Clause
8 .TH CIRCLEQ 3 2021-03-22 "Linux man-pages (unreleased)" "Linux Programmer's Manual"
14 CIRCLEQ_FOREACH_REVERSE,
16 CIRCLEQ_HEAD_INITIALIZER,
19 CIRCLEQ_INSERT_BEFORE,
28 \- implementation of a doubly linked circular queue
31 .RI ( libc ", " \-lc )
34 .B #include <sys/queue.h>
36 .B CIRCLEQ_ENTRY(TYPE);
38 .B CIRCLEQ_HEAD(HEADNAME, TYPE);
39 .BI "CIRCLEQ_HEAD CIRCLEQ_HEAD_INITIALIZER(CIRCLEQ_HEAD " head );
40 .BI "void CIRCLEQ_INIT(CIRCLEQ_HEAD *" head );
42 .BI "int CIRCLEQ_EMPTY(CIRCLEQ_HEAD *" head );
44 .BI "void CIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *" head ,
45 .BI " struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
46 .BI "void CIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *" head ,
47 .BI " struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
48 .BI "void CIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *" head ", struct TYPE *" listelm ,
49 .BI " struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
50 .BI "void CIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *" head ", struct TYPE *" listelm ,
51 .BI " struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
53 .BI "struct TYPE *CIRCLEQ_FIRST(CIRCLEQ_HEAD *" head );
54 .BI "struct TYPE *CIRCLEQ_LAST(CIRCLEQ_HEAD *" head );
55 .BI "struct TYPE *CIRCLEQ_PREV(struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
56 .BI "struct TYPE *CIRCLEQ_NEXT(struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
57 .BI "struct TYPE *CIRCLEQ_LOOP_PREV(CIRCLEQ_HEAD *" head ,
58 .BI " struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
59 .BI "struct TYPE *CIRCLEQ_LOOP_NEXT(CIRCLEQ_HEAD *" head ,
60 .BI " struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
62 .BI "CIRCLEQ_FOREACH(struct TYPE *" var ", CIRCLEQ_HEAD *" head ,
63 .BI " CIRCLEQ_ENTRY " NAME );
64 .BI "CIRCLEQ_FOREACH_REVERSE(struct TYPE *" var ", CIRCLEQ_HEAD *" head ,
65 .BI " CIRCLEQ_ENTRY " NAME );
67 .BI "void CIRCLEQ_REMOVE(CIRCLEQ_HEAD *" head ", struct TYPE *" elm ,
68 .BI " CIRCLEQ_ENTRY " NAME );
71 These macros define and operate on doubly linked circular queues.
73 In the macro definitions,
75 is the name of a user-defined structure,
76 that must contain a field of type
82 is the name of a user-defined structure
83 that must be declared using the macro
86 A circular queue is headed by a structure defined by the
89 This structure contains a pair of pointers,
90 one to the first element in the queue
91 and the other to the last element in the queue.
92 The elements are doubly linked
93 so that an arbitrary element can be removed without traversing the queue.
94 New elements can be added to the queue
95 after an existing element,
96 before an existing element,
97 at the head of the queue,
98 or at the end of the queue.
101 structure is declared as follows:
105 CIRCLEQ_HEAD(HEADNAME, TYPE) head;
111 is the structure to be defined, and
113 is the type of the elements to be linked into the queue.
114 A pointer to the head of the queue can later be declared as:
118 struct HEADNAME *headp;
126 are user selectable.)
129 declares a structure that connects the elements in the queue.
131 .BR CIRCLEQ_HEAD_INITIALIZER ()
132 evaluates to an initializer for the queue
136 initializes the queue referenced by
140 evaluates to true if there are no items on the queue.
142 .BR CIRCLEQ_INSERT_HEAD ()
143 inserts the new element
145 at the head of the queue.
147 .BR CIRCLEQ_INSERT_TAIL ()
148 inserts the new element
150 at the end of the queue.
152 .BR CIRCLEQ_INSERT_BEFORE ()
153 inserts the new element
158 .BR CIRCLEQ_INSERT_AFTER ()
159 inserts the new element
165 returns the first item on the queue.
168 returns the last item on the queue.
171 returns the previous item on the queue, or
173 if this item is the first one.
176 returns the next item on the queue, or
178 if this item is the last one.
180 .BR CIRCLEQ_LOOP_PREV ()
181 returns the previous item on the queue.
184 is the first element on the queue, the last element is returned.
186 .BR CIRCLEQ_LOOP_NEXT ()
187 returns the next item on the queue.
190 is the last element on the queue, the first element is returned.
192 .BR CIRCLEQ_FOREACH ()
193 traverses the queue referenced by
195 in the forward direction, assigning each element in turn to
200 if the loop completes normally, or if there were no elements.
202 .BR CIRCLEQ_FOREACH_REVERSE ()
203 traverses the queue referenced by
205 in the reverse direction,
206 assigning each element in turn to
209 .BR CIRCLEQ_REMOVE ()
215 returns nonzero if the queue is empty,
216 and zero if the queue contains at least one entry.
218 .BR CIRCLEQ_FIRST (),
220 .BR CIRCLEQ_LOOP_PREV (),
222 .BR CIRCLEQ_LOOP_NEXT ()
223 return a pointer to the first, last, previous, or next
225 structure, respectively.
231 .BR CIRCLEQ_LOOP_* ()
233 except that if the argument is the first or last element, respectively,
237 .BR CIRCLEQ_HEAD_INITIALIZER ()
238 returns an initializer that can be assigned to the queue
241 Not in POSIX.1, POSIX.1-2001, or POSIX.1-2008.
243 (CIRCLEQ macros first appeared in 4.4BSD).
245 .BR CIRCLEQ_FOREACH ()
247 .BR CIRCLEQ_FOREACH_REVERSE ()
250 to be removed or freed within the loop,
251 as it would interfere with the traversal.
252 .BR CIRCLEQ_FOREACH_SAFE ()
254 .BR CIRCLEQ_FOREACH_REVERSE_SAFE (),
255 which are present on the BSDs but are not present in glibc,
256 fix this limitation by allowing
258 to safely be removed from the list and freed from within the loop
259 without interfering with the traversal.
265 #include <sys/queue.h>
269 CIRCLEQ_ENTRY(entry) entries; /* Queue */
272 CIRCLEQ_HEAD(circlehead, entry);
277 struct entry *n1, *n2, *n3, *np;
278 struct circlehead head; /* Queue head */
281 CIRCLEQ_INIT(&head); /* Initialize the queue */
283 n1 = malloc(sizeof(struct entry)); /* Insert at the head */
284 CIRCLEQ_INSERT_HEAD(&head, n1, entries);
286 n1 = malloc(sizeof(struct entry)); /* Insert at the tail */
287 CIRCLEQ_INSERT_TAIL(&head, n1, entries);
289 n2 = malloc(sizeof(struct entry)); /* Insert after */
290 CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
292 n3 = malloc(sizeof(struct entry)); /* Insert before */
293 CIRCLEQ_INSERT_BEFORE(&head, n2, n3, entries);
295 CIRCLEQ_REMOVE(&head, n2, entries); /* Deletion */
297 /* Forward traversal */
299 CIRCLEQ_FOREACH(np, &head, entries)
301 /* Reverse traversal */
302 CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
303 printf("%i\en", np\->data);
305 n1 = CIRCLEQ_FIRST(&head);
306 while (n1 != (void *)&head) {
307 n2 = CIRCLEQ_NEXT(n1, entries);