Debian Codegraph @

upstream/debian-unstable/man3/circleq.3

raw
1 .\" Copyright 1993, The Regents of the University of California.
2 .\" Copyright, the authors of the Linux man-pages project
3 .\"
4 .\" SPDX-License-Identifier: BSD-3-Clause
5 .\"
6 .TH CIRCLEQ 3 2025-05-17 "Linux man-pages 6.18"
7 .SH NAME
8 CIRCLEQ_EMPTY,
9 CIRCLEQ_ENTRY,
10 CIRCLEQ_FIRST,
11 CIRCLEQ_FOREACH,
12 CIRCLEQ_FOREACH_REVERSE,
13 CIRCLEQ_HEAD,
14 CIRCLEQ_HEAD_INITIALIZER,
15 CIRCLEQ_INIT,
16 CIRCLEQ_INSERT_AFTER,
17 CIRCLEQ_INSERT_BEFORE,
18 CIRCLEQ_INSERT_HEAD,
19 CIRCLEQ_INSERT_TAIL,
20 CIRCLEQ_LAST,
21 CIRCLEQ_LOOP_NEXT,
22 CIRCLEQ_LOOP_PREV,
23 CIRCLEQ_NEXT,
24 CIRCLEQ_PREV,
25 CIRCLEQ_REMOVE
26 \- implementation of a doubly linked circular queue
27 .SH LIBRARY
28 Standard C library
29 .RI ( libc ,\~ \-lc )
30 .SH SYNOPSIS
31 .nf
32 .B #include <sys/queue.h>
33 .P
34 .B CIRCLEQ_ENTRY(TYPE);
35 .P
36 .B CIRCLEQ_HEAD(HEADNAME, TYPE);
37 .BI "CIRCLEQ_HEAD CIRCLEQ_HEAD_INITIALIZER(CIRCLEQ_HEAD " head );
38 .BI "void CIRCLEQ_INIT(CIRCLEQ_HEAD *" head );
39 .P
40 .BI "int CIRCLEQ_EMPTY(CIRCLEQ_HEAD *" head );
41 .P
42 .BI "void CIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *" head ,
43 .BI " struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
44 .BI "void CIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *" head ,
45 .BI " struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
46 .BI "void CIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *" head ", struct TYPE *" listelm ,
47 .BI " struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
48 .BI "void CIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *" head ", struct TYPE *" listelm ,
49 .BI " struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
50 .P
51 .BI "struct TYPE *CIRCLEQ_FIRST(CIRCLEQ_HEAD *" head );
52 .BI "struct TYPE *CIRCLEQ_LAST(CIRCLEQ_HEAD *" head );
53 .BI "struct TYPE *CIRCLEQ_PREV(struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
54 .BI "struct TYPE *CIRCLEQ_NEXT(struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
55 .BI "struct TYPE *CIRCLEQ_LOOP_PREV(CIRCLEQ_HEAD *" head ,
56 .BI " struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
57 .BI "struct TYPE *CIRCLEQ_LOOP_NEXT(CIRCLEQ_HEAD *" head ,
58 .BI " struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
59 .P
60 .BI "CIRCLEQ_FOREACH(struct TYPE *" var ", CIRCLEQ_HEAD *" head ,
61 .BI " CIRCLEQ_ENTRY " NAME );
62 .BI "CIRCLEQ_FOREACH_REVERSE(struct TYPE *" var ", CIRCLEQ_HEAD *" head ,
63 .BI " CIRCLEQ_ENTRY " NAME );
64 .P
65 .BI "void CIRCLEQ_REMOVE(CIRCLEQ_HEAD *" head ", struct TYPE *" elm ,
66 .BI " CIRCLEQ_ENTRY " NAME );
67 .fi
68 .SH DESCRIPTION
69 These macros define and operate on doubly linked circular queues.
70 .P
71 In the macro definitions,
72 .I TYPE
73 is the name of a user-defined structure,
74 that must contain a field of type
75 .IR CIRCLEQ_ENTRY ,
76 named
77 .IR NAME .
78 The argument
79 .I HEADNAME
80 is the name of a user-defined structure
81 that must be declared using the macro
82 .BR CIRCLEQ_HEAD ().
83 .SS Creation
84 A circular queue is headed by a structure defined by the
85 .BR CIRCLEQ_HEAD ()
86 macro.
87 This structure contains a pair of pointers,
88 one to the first element in the queue
89 and the other to the last element in the queue.
90 The elements are doubly linked
91 so that an arbitrary element can be removed without traversing the queue.
92 New elements can be added to the queue
93 after an existing element,
94 before an existing element,
95 at the head of the queue,
96 or at the end of the queue.
97 A
98 .I CIRCLEQ_HEAD
99 structure is declared as follows:
100 .P
101 .in +4
102 .EX
103 CIRCLEQ_HEAD(HEADNAME, TYPE) head;
104 .EE
105 .in
106 .P
107 where
108 .I struct HEADNAME
109 is the structure to be defined, and
110 .I struct TYPE
111 is the type of the elements to be linked into the queue.
112 A pointer to the head of the queue can later be declared as:
113 .P
114 .in +4
115 .EX
116 struct HEADNAME *headp;
117 .EE
118 .in
119 .P
120 (The names
121 .I head
122 and
123 .I headp
124 are user selectable.)
125 .P
126 .BR CIRCLEQ_ENTRY ()
127 declares a structure that connects the elements in the queue.
128 .P
129 .BR CIRCLEQ_HEAD_INITIALIZER ()
130 evaluates to an initializer for the queue
131 .IR head .
132 .P
133 .BR CIRCLEQ_INIT ()
134 initializes the queue referenced by
135 .IR head .
136 .P
137 .BR CIRCLEQ_EMPTY ()
138 evaluates to true if there are no items on the queue.
139 .SS Insertion
140 .BR CIRCLEQ_INSERT_HEAD ()
141 inserts the new element
142 .I elm
143 at the head of the queue.
144 .P
145 .BR CIRCLEQ_INSERT_TAIL ()
146 inserts the new element
147 .I elm
148 at the end of the queue.
149 .P
150 .BR CIRCLEQ_INSERT_BEFORE ()
151 inserts the new element
152 .I elm
153 before the element
154 .IR listelm .
155 .P
156 .BR CIRCLEQ_INSERT_AFTER ()
157 inserts the new element
158 .I elm
159 after the element
160 .IR listelm .
161 .SS Traversal
162 .BR CIRCLEQ_FIRST ()
163 returns the first item on the queue.
164 .P
165 .BR CIRCLEQ_LAST ()
166 returns the last item on the queue.
167 .P
168 .BR CIRCLEQ_PREV ()
169 returns the previous item on the queue, or
170 .I &head
171 if this item is the first one.
172 .P
173 .BR CIRCLEQ_NEXT ()
174 returns the next item on the queue, or
175 .I &head
176 if this item is the last one.
177 .P
178 .BR CIRCLEQ_LOOP_PREV ()
179 returns the previous item on the queue.
180 If
181 .I elm
182 is the first element on the queue, the last element is returned.
183 .P
184 .BR CIRCLEQ_LOOP_NEXT ()
185 returns the next item on the queue.
186 If
187 .I elm
188 is the last element on the queue, the first element is returned.
189 .P
190 .BR CIRCLEQ_FOREACH ()
191 traverses the queue referenced by
192 .I head
193 in the forward direction, assigning each element in turn to
194 .IR var .
195 .I var
196 is set to
197 .I &head
198 if the loop completes normally, or if there were no elements.
199 .P
200 .BR CIRCLEQ_FOREACH_REVERSE ()
201 traverses the queue referenced by
202 .I head
203 in the reverse direction,
204 assigning each element in turn to
205 .IR var .
206 .SS Removal
207 .BR CIRCLEQ_REMOVE ()
208 removes the element
209 .I elm
210 from the queue.
211 .SH RETURN VALUE
212 .BR CIRCLEQ_EMPTY ()
213 returns nonzero if the queue is empty,
214 and zero if the queue contains at least one entry.
215 .P
216 .BR CIRCLEQ_FIRST (),
217 .BR CIRCLEQ_LAST (),
218 .BR CIRCLEQ_LOOP_PREV (),
219 and
220 .BR CIRCLEQ_LOOP_NEXT ()
221 return a pointer to the first, last, previous, or next
222 .I TYPE
223 structure, respectively.
224 .P
225 .BR CIRCLEQ_PREV (),
226 and
227 .BR CIRCLEQ_NEXT ()
228 are similar to their
229 .BR CIRCLEQ_LOOP_* ()
230 counterparts,
231 except that if the argument is the first or last element, respectively,
232 they return
233 .IR &head .
234 .P
235 .BR CIRCLEQ_HEAD_INITIALIZER ()
236 returns an initializer that can be assigned to the queue
237 .IR head .
238 .SH STANDARDS
239 BSD.
240 .SH BUGS
241 .BR CIRCLEQ_FOREACH ()
242 and
243 .BR CIRCLEQ_FOREACH_REVERSE ()
244 don't allow
245 .I var
246 to be removed or freed within the loop,
247 as it would interfere with the traversal.
248 .BR CIRCLEQ_FOREACH_SAFE ()
249 and
250 .BR CIRCLEQ_FOREACH_REVERSE_SAFE (),
251 which are present on the BSDs but are not present in glibc,
252 fix this limitation by allowing
253 .I var
254 to safely be removed from the list and freed from within the loop
255 without interfering with the traversal.
256 .SH EXAMPLES
257 .\" SRC BEGIN (circleq.c)
258 .EX
259 #include <stddef.h>
260 #include <stdio.h>
261 #include <stdlib.h>
262 #include <sys/queue.h>
263 \&
264 struct entry {
265 int data;
266 CIRCLEQ_ENTRY(entry) entries; /* Queue */
267 };
268 \&
269 CIRCLEQ_HEAD(circlehead, entry);
270 \&
271 int
272 main(void)
273 {
274 struct entry *n1, *n2, *n3, *np;
275 struct circlehead head; /* Queue head */
276 int i;
277 \&
278 CIRCLEQ_INIT(&head); /* Initialize the queue */
279 \&
280 n1 = malloc(sizeof(struct entry)); /* Insert at the head */
281 CIRCLEQ_INSERT_HEAD(&head, n1, entries);
282 \&
283 n1 = malloc(sizeof(struct entry)); /* Insert at the tail */
284 CIRCLEQ_INSERT_TAIL(&head, n1, entries);
285 \&
286 n2 = malloc(sizeof(struct entry)); /* Insert after */
287 CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
288 \&
289 n3 = malloc(sizeof(struct entry)); /* Insert before */
290 CIRCLEQ_INSERT_BEFORE(&head, n2, n3, entries);
291 \&
292 CIRCLEQ_REMOVE(&head, n2, entries); /* Deletion */
293 free(n2);
294 /* Forward traversal */
295 i = 0;
296 CIRCLEQ_FOREACH(np, &head, entries)
297 np\->data = i++;
298 /* Reverse traversal */
299 CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
300 printf("%i\[rs]n", np\->data);
301 /* Queue deletion */
302 n1 = CIRCLEQ_FIRST(&head);
303 while (n1 != (void *)&head) {
304 n2 = CIRCLEQ_NEXT(n1, entries);
305 free(n1);
306 n1 = n2;
307 }
308 CIRCLEQ_INIT(&head);
309 \&
310 exit(EXIT_SUCCESS);
311 }
312 .EE
313 .\" SRC END
314 .SH SEE ALSO
315 .BR insque (3),
316 .BR queue (7)