1CIRCLEQ(3) Linux Programmer's Manual CIRCLEQ(3)
2
6 CIRCLEQ_EMPTY, CIRCLEQ_ENTRY, CIRCLEQ_FIRST, CIRCLEQ_FOREACH, CIR‐
7 CLEQ_FOREACH_REVERSE, CIRCLEQ_HEAD, CIRCLEQ_HEAD_INITIALIZER, CIR‐
8 CLEQ_INIT, CIRCLEQ_INSERT_AFTER, CIRCLEQ_INSERT_BEFORE, CIRCLEQ_IN‐
9 SERT_HEAD, CIRCLEQ_INSERT_TAIL, CIRCLEQ_LAST, CIRCLEQ_LOOP_NEXT, CIR‐
10 CLEQ_LOOP_PREV, CIRCLEQ_NEXT, CIRCLEQ_PREV, CIRCLEQ_REMOVE - implemen‐
11 tation of a doubly linked circular queue
12
14 #include <sys/queue.h>
15 CIRCLEQ_ENTRY(TYPE);
17 CIRCLEQ_HEAD(HEADNAME, TYPE);
19 CIRCLEQ_HEAD CIRCLEQ_HEAD_INITIALIZER(CIRCLEQ_HEAD head);
20 void CIRCLEQ_INIT(CIRCLEQ_HEAD *head);
21 int CIRCLEQ_EMPTY(CIRCLEQ_HEAD *head);
23 void CIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *head,
25 struct TYPE *elm, CIRCLEQ_ENTRY NAME);
26 void CIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *head,
27 struct TYPE *elm, CIRCLEQ_ENTRY NAME);
28 void CIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *head, struct TYPE *listelm,
29 struct TYPE *elm, CIRCLEQ_ENTRY NAME);
30 void CIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *head, struct TYPE *listelm,
31 struct TYPE *elm, CIRCLEQ_ENTRY NAME);
32 struct TYPE *CIRCLEQ_FIRST(CIRCLEQ_HEAD *head);
34 struct TYPE *CIRCLEQ_LAST(CIRCLEQ_HEAD *head);
35 struct TYPE *CIRCLEQ_PREV(struct TYPE *elm, CIRCLEQ_ENTRY NAME);
36 struct TYPE *CIRCLEQ_NEXT(struct TYPE *elm, CIRCLEQ_ENTRY NAME);
37 struct TYPE *CIRCLEQ_LOOP_PREV(CIRCLEQ_HEAD *head,
38 struct TYPE *elm, CIRCLEQ_ENTRY NAME);
39 struct TYPE *CIRCLEQ_LOOP_NEXT(CIRCLEQ_HEAD *head,
40 struct TYPE *elm, CIRCLEQ_ENTRY NAME);
41 CIRCLEQ_FOREACH(struct TYPE *var, CIRCLEQ_HEAD *head,
43 CIRCLEQ_ENTRY NAME);
44 CIRCLEQ_FOREACH_REVERSE(struct TYPE *var, CIRCLEQ_HEAD *head,
45 CIRCLEQ_ENTRY NAME);
46 void CIRCLEQ_REMOVE(CIRCLEQ_HEAD *head, struct TYPE *elm,
48 CIRCLEQ_ENTRY NAME);
49
51 These macros define and operate on doubly linked circular queues.
52 In the macro definitions, TYPE is the name of a user-defined structure,
54 that must contain a field of type CIRCLEQ_ENTRY, named NAME. The argu‐
55 ment HEADNAME is the name of a user-defined structure that must be de‐
56 clared using the macro CIRCLEQ_HEAD().
57 Creation
59 A circular queue is headed by a structure defined by the CIRCLEQ_HEAD()
60 macro. This structure contains a pair of pointers, one to the first
61 element in the queue and the other to the last element in the queue.
62 The elements are doubly linked so that an arbitrary element can be re‐
63 moved without traversing the queue. New elements can be added to the
64 queue after an existing element, before an existing element, at the
65 head of the queue, or at the end of the queue. A CIRCLEQ_HEAD struc‐
66 ture is declared as follows:
67 CIRCLEQ_HEAD(HEADNAME, TYPE) head;
69 where struct HEADNAME is the structure to be defined, and struct TYPE
71 is the type of the elements to be linked into the queue. A pointer to
72 the head of the queue can later be declared as:
73 struct HEADNAME *headp;
75 (The names head and headp are user selectable.)
77 CIRCLEQ_ENTRY() declares a structure that connects the elements in the
79 queue.
80 CIRCLEQ_HEAD_INITIALIZER() evaluates to an initializer for the queue
82 head.
83 CIRCLEQ_INIT() initializes the queue referenced by head.
85 CIRCLEQ_EMPTY() evaluates to true if there are no items on the queue.
87 Insertion
89 CIRCLEQ_INSERT_HEAD() inserts the new element elm at the head of the
90 queue.
91 CIRCLEQ_INSERT_TAIL() inserts the new element elm at the end of the
93 queue.
94 CIRCLEQ_INSERT_BEFORE() inserts the new element elm before the element
96 listelm.
97 CIRCLEQ_INSERT_AFTER() inserts the new element elm after the element
99 listelm.
100 Traversal
102 CIRCLEQ_FIRST() returns the first item on the queue.
103 CIRCLEQ_LAST() returns the last item on the queue.
105 CIRCLEQ_PREV() returns the previous item on the queue, or &head if this
107 item is the first one.
108 CIRCLEQ_NEXT() returns the next item on the queue, or &head if this
110 item is the last one.
111 CIRCLEQ_LOOP_PREV() returns the previous item on the queue. If elm is
113 the first element on the queue, the last element is returned.
114 CIRCLEQ_LOOP_NEXT() returns the next item on the queue. If elm is the
116 last element on the queue, the first element is returned.
117 CIRCLEQ_FOREACH() traverses the queue referenced by head in the forward
119 direction, assigning each element in turn to var. var is set to &head
120 if the loop completes normally, or if there were no elements.
121 CIRCLEQ_FOREACH_REVERSE() traverses the queue referenced by head in the
123 reverse direction, assigning each element in turn to var.
124 Removal
126 CIRCLEQ_REMOVE() removes the element elm from the queue.
127
129 CIRCLEQ_EMPTY() returns nonzero if the queue is empty, and zero if the
130 queue contains at least one entry.
131 CIRCLEQ_FIRST(), CIRCLEQ_LAST(), CIRCLEQ_LOOP_PREV(), and CIR‐
133 CLEQ_LOOP_NEXT() return a pointer to the first, last, previous, or next
134 TYPE structure, respectively.
135 CIRCLEQ_PREV(), and CIRCLEQ_NEXT() are similar to their CIR‐
137 CLEQ_LOOP_*() counterparts, except that if the argument is the first or
138 last element, respectively, they return &head.
139 CIRCLEQ_HEAD_INITIALIZER() returns an initializer that can be assigned
141 to the queue head.
142
144 Not in POSIX.1, POSIX.1-2001, or POSIX.1-2008. Present on the BSDs
145 (CIRCLEQ macros first appeared in 4.4BSD).
146
148 CIRCLEQ_FOREACH() and CIRCLEQ_FOREACH_REVERSE() don't allow var to be
149 removed or freed within the loop, as it would interfere with the tra‐
150 versal. CIRCLEQ_FOREACH_SAFE() and CIRCLEQ_FOREACH_REVERSE_SAFE(),
151 which are present on the BSDs but are not present in glibc, fix this
152 limitation by allowing var to safely be removed from the list and freed
153 from within the loop without interfering with the traversal.
154
156 #include <stddef.h>
157 #include <stdio.h>
158 #include <stdlib.h>
159 #include <sys/queue.h>
160 struct entry {
162 int data;
163 CIRCLEQ_ENTRY(entry) entries; /* Queue */
164 };
165 CIRCLEQ_HEAD(circlehead, entry);
167 int
169 main(void)
170 {
171 struct entry *n1, *n2, *n3, *np;
172 struct circlehead head; /* Queue head */
173 int i;
174 CIRCLEQ_INIT(&head); /* Initialize the queue */
176 n1 = malloc(sizeof(struct entry)); /* Insert at the head */
178 CIRCLEQ_INSERT_HEAD(&head, n1, entries);
179 n1 = malloc(sizeof(struct entry)); /* Insert at the tail */
181 CIRCLEQ_INSERT_TAIL(&head, n1, entries);
182 n2 = malloc(sizeof(struct entry)); /* Insert after */
184 CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
185 n3 = malloc(sizeof(struct entry)); /* Insert before */
187 CIRCLEQ_INSERT_BEFORE(&head, n2, n3, entries);
188 CIRCLEQ_REMOVE(&head, n2, entries); /* Deletion */
190 free(n2);
191 /* Forward traversal */
192 i = 0;
193 CIRCLEQ_FOREACH(np, &head, entries)
194 np->data = i++;
195 /* Reverse traversal */
196 CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
197 printf("%i\n", np->data);
198 /* Queue deletion */
199 n1 = CIRCLEQ_FIRST(&head);
200 while (n1 != (void *)&head) {
201 n2 = CIRCLEQ_NEXT(n1, entries);
202 free(n1);
203 n1 = n2;
204 }
205 CIRCLEQ_INIT(&head);
206 exit(EXIT_SUCCESS);
208 }
209
211 insque(3), queue(7)
212
214 This page is part of release 5.12 of the Linux man-pages project. A
215 description of the project, information about reporting bugs, and the
216 latest version of this page, can be found at
217 https://www.kernel.org/doc/man-pages/.
218GNU 2021-03-22 CIRCLEQ(3)