| blob | 7b119bae67a38a3ea6e650a24f41996fc219c16f |
1 .\" $NetBSD: gcq.3,v 1.2 2009/05/27 17:47:46 snj Exp $
2 .\"
3 .\" Not (c) 2007 Matthew Orgass
4 .\" This file is public domain, meaning anyone can make any use of part or all
5 .\" of this file including copying into other works without credit. Any use,
6 .\" modified or not, is solely the responsibility of the user. If this file
7 .\" is part of a collection then use in the collection is governed by the
8 .\" terms of the collection.
9 .\"
10 .Dd May 1, 2007
11 .Dt GCQ 3
12 .Os
13 .Sh NAME
14 .Nm GCQ_INIT ,
15 .Nm GCQ_INIT_HEAD ,
16 .Nm gcq_init ,
17 .Nm gcq_init_head ,
18 .Nm gcq_q ,
19 .Nm gcq_hq ,
20 .Nm gcq_head ,
21 .Nm gcq_remove ,
22 .Nm gcq_onlist ,
23 .Nm gcq_empty ,
24 .Nm gcq_linked ,
25 .Nm gcq_insert_after ,
26 .Nm gcq_insert_before ,
27 .Nm gcq_insert_head ,
28 .Nm gcq_insert_tail ,
29 .Nm gcq_tie ,
30 .Nm gcq_tie_after ,
31 .Nm gcq_tie_before ,
32 .Nm gcq_merge ,
33 .Nm gcq_merge_head ,
34 .Nm gcq_merge_tail ,
35 .Nm gcq_clear ,
36 .Nm gcq_remove_all ,
37 .Nm GCQ_ITEM ,
38 .Nm GCQ_GOT_FIRST ,
39 .Nm GCQ_GOT_LAST ,
40 .Nm GCQ_GOT_NEXT ,
41 .Nm GCQ_GOT_PREV ,
42 .Nm GCQ_DEQUEUED_FIRST ,
43 .Nm GCQ_DEQUEUED_LAST ,
44 .Nm GCQ_DEQUEUED_NEXT ,
45 .Nm GCQ_DEQUEUED_PREV ,
46 .Nm GCQ_GOT_FIRST_TYPED ,
47 .Nm GCQ_GOT_LAST_TYPED ,
48 .Nm GCQ_GOT_NEXT_TYPED ,
49 .Nm GCQ_GOT_PREV_TYPED ,
50 .Nm GCQ_DEQUEUED_FIRST_TYPED ,
51 .Nm GCQ_DEQUEUED_LAST_TYPED ,
52 .Nm GCQ_DEQUEUED_NEXT_TYPED ,
53 .Nm GCQ_DEQUEUED_PREV_TYPED ,
54 .Nm GCQ_GOT_FIRST_COND ,
55 .Nm GCQ_GOT_LAST_COND ,
56 .Nm GCQ_GOT_NEXT_COND ,
57 .Nm GCQ_GOT_PREV_COND ,
58 .Nm GCQ_DEQUEUED_FIRST_COND ,
59 .Nm GCQ_DEQUEUED_LAST_COND ,
60 .Nm GCQ_DEQUEUED_NEXT_COND ,
61 .Nm GCQ_DEQUEUED_PREV_COND ,
62 .Nm GCQ_GOT_FIRST_COND_TYPED ,
63 .Nm GCQ_GOT_LAST_COND_TYPED ,
64 .Nm GCQ_GOT_NEXT_COND_TYPED ,
65 .Nm GCQ_GOT_PREV_COND_TYPED ,
66 .Nm GCQ_DEQUEUED_FIRST_COND_TYPED ,
67 .Nm GCQ_DEQUEUED_LAST_COND_TYPED ,
68 .Nm GCQ_DEQUEUED_NEXT_COND_TYPED ,
69 .Nm GCQ_DEQUEUED_PREV_COND_TYPED ,
70 .Nm GCQ_FOREACH ,
71 .Nm GCQ_FOREACH_REV ,
72 .Nm GCQ_FOREACH_NVAR ,
73 .Nm GCQ_FOREACH_NVAR_REV ,
74 .Nm GCQ_FOREACH_RO ,
75 .Nm GCQ_FOREACH_RO_REV ,
76 .Nm GCQ_FOREACH_DEQUEUED ,
77 .Nm GCQ_FOREACH_DEQUEUED_REV ,
78 .Nm GCQ_FOREACH_TYPED ,
79 .Nm GCQ_FOREACH_REV_TYPED ,
80 .Nm GCQ_FOREACH_NVAR_TYPED ,
81 .Nm GCQ_FOREACH_NVAR_REV_TYPED ,
82 .Nm GCQ_FOREACH_RO_TYPED ,
83 .Nm GCQ_FOREACH_RO_REV_TYPED ,
84 .Nm GCQ_FOREACH_DEQUEUED_TYPED ,
85 .Nm GCQ_FOREACH_DEQUEUED_REV_TYPED ,
86 .Nm GCQ_FIND ,
87 .Nm GCQ_FIND_REV ,
88 .Nm GCQ_FIND_TYPED ,
89 .Nm GCQ_FIND_REV_TYPED
90 .Nd "Generic Circular Queues"
91 .Sh SYNOPSIS
92 .In sys/gcq.h
93 .Pp
94 .Vt struct gcq ;
95 .Vt struct gcq_head ;
96 .Pp
97 .Fn GCQ_INIT name
98 .Fn GCQ_INIT_HEAD name
99 .Pp
100 .Ft static inline void
101 .Fn gcq_init "struct gcq *q"
102 .Ft static inline void
103 .Fn gcq_init_head "struct gcq_head *head"
104 .Ft static inline struct gcq *
105 .Fn gcq_q "struct gcq_head *head"
106 .Ft static inline struct gcq *
107 .Fn gcq_hq "struct gcq_head *head"
108 .Ft static inline struct gcq_head *
109 .Fn gcq_head "struct gcq *q"
110 .Ft static inline struct gcq *
111 .Fn gcq_remove "struct gcq *q"
112 .Ft static inline bool
113 .Fn gcq_onlist "struct gcq *q"
114 .Ft static inline bool
115 .Fn gcq_empty "struct gcq_head *head"
116 .Ft static inline bool
117 .Fn gcq_linked "struct gcq *prev" "struct gcq *next"
118 .Ft static inline void
119 .Fn gcq_insert_after "struct gcq *on" "struct gcq *off"
120 .Ft static inline void
121 .Fn gcq_insert_before "struct gcq *on" "struct gcq *off"
122 .Ft static inline void
123 .Fn gcq_insert_head "struct gcq_head *head" "struct gcq *q"
124 .Ft static inline void
125 .Fn gcq_insert_tail "struct gcq_head *head" "struct gcq *q"
126 .Ft static inline void
127 .Fn gcq_tie "struct gcq *dst" "struct gcq *src"
128 .Ft static inline void
129 .Fn gcq_tie_after "struct gcq *dst" "struct gcq *src"
130 .Ft static inline void
131 .Fn gcq_tie_before "struct gcq *dst" "struct gcq *src"
132 .Ft static inline void
133 .Fn gcq_merge "struct gcq *dst" "struct gcq *src"
134 .Ft static inline void
135 .Fn gcq_merge_tail "struct gcq_head *dst" "struct gcq_head *src"
136 .Ft static inline void
137 .Fn gcq_merge_head "struct gcq_head *dst" "struct gcq_head *src"
138 .Ft static inline void
139 .Fn gcq_clear "struct gcq *q"
140 .Ft static inline void
141 .Fn gcq_remove_all "struct gcq_head *head"
142 .Pp
143 .Ft type *
144 .Fn GCQ_ITEM q type name
145 .Ft bool
146 .Fn GCQ_GOT_FIRST var head
147 .Ft bool
148 .Fn GCQ_GOT_LAST var head
149 .Ft bool
150 .Fn GCQ_GOT_NEXT var current head start
151 .Ft bool
152 .Fn GCQ_GOT_PREV var current head start
153 .Ft bool
154 .Fn GCQ_DEQUEUED_FIRST var head
155 .Ft bool
156 .Fn GCQ_DEQUEUED_LAST var head
157 .Ft bool
158 .Fn GCQ_DEQUEUED_NEXT var current head start
159 .Ft bool
160 .Fn GCQ_DEQUEUED_PREV var current head start
161 .Ft bool
162 .Fn GCQ_GOT_FIRST_TYPED tvar head type name
163 .Ft bool
164 .Fn GCQ_GOT_LAST_TYPED tvar head type name
165 .Ft bool
166 .Fn GCQ_GOT_NEXT_TYPED tvar current head start type name
167 .Ft bool
168 .Fn GCQ_GOT_PREV_TYPED tvar current head start type name
169 .Ft bool
170 .Fn GCQ_DEQUEUED_FIRST_TYPED tvar head type name
171 .Ft bool
172 .Fn GCQ_DEQUEUED_LAST_TYPED tvar head type name
173 .Ft bool
174 .Fn GCQ_DEQUEUED_NEXT_TYPED tvar current head start type name
175 .Ft bool
176 .Fn GCQ_DEQUEUED_PREV_TYPED tvar current head start type name
177 .Ft bool
178 .Fn GCQ_GOT_FIRST_COND var head cond
179 .Ft bool
180 .Fn GCQ_GOT_LAST_COND var head cond
181 .Ft bool
182 .Fn GCQ_GOT_NEXT_COND var current head start cond
183 .Ft bool
184 .Fn GCQ_GOT_PREV_COND var current head start cond
185 .Ft bool
186 .Fn GCQ_DEQUEUED_FIRST_COND var head cond
187 .Ft bool
188 .Fn GCQ_DEQUEUED_LAST_COND var head cond
189 .Ft bool
190 .Fn GCQ_DEQUEUED_NEXT_COND var current head start cond
191 .Ft bool
192 .Fn GCQ_DEQUEUED_PREV_COND var current head start cond
193 .Ft bool
194 .Fn GCQ_GOT_FIRST_COND_TYPED tvar head type name cond
195 .Ft bool
196 .Fn GCQ_GOT_LAST_COND_TYPED tvar head type name cond
197 .Ft bool
198 .Fn GCQ_GOT_NEXT_COND_TYPED tvar current head start type name cond
199 .Ft bool
200 .Fn GCQ_GOT_PREV_COND_TYPED tvar current head start type name cond
201 .Ft bool
202 .Fn GCQ_DEQUEUED_FIRST_COND_TYPED tvar head type name cond
203 .Ft bool
204 .Fn GCQ_DEQUEUED_LAST_COND_TYPED tvar head type name cond
205 .Ft bool
206 .Fn GCQ_DEQUEUED_NEXT_COND_TYPED tvar current head start type name cond
207 .Ft bool
208 .Fn GCQ_DEQUEUED_PREV_COND_TYPED tvar current head start type name cond
209 .Fn GCQ_FOREACH var head
210 .Fn GCQ_FOREACH_REV var head
211 .Fn GCQ_FOREACH_NVAR var nvar head
212 .Fn GCQ_FOREACH_NVAR_REV var nvar head
213 .Fn GCQ_FOREACH_RO var nvar head
214 .Fn GCQ_FOREACH_RO_REV var nvar head
215 .Fn GCQ_FOREACH_DEQUEUED var nvar head
216 .Fn GCQ_FOREACH_DEQUEUED_REV var nvar head
217 .Fn GCQ_FOREACH_TYPED var head tvar type name
218 .Fn GCQ_FOREACH_REV_TYPED var head tvar type name
219 .Fn GCQ_FOREACH_NVAR_TYPED var nvar head tvar type name
220 .Fn GCQ_FOREACH_NVAR_REV_TYPED var nvar head tvar type name
221 .Fn GCQ_FOREACH_RO_TYPED var nvar head tvar type name
222 .Fn GCQ_FOREACH_RO_REV_TYPED var nvar head tvar type name
223 .Fn GCQ_FOREACH_DEQUEUED_TYPED var nvar head tvar type name
224 .Fn GCQ_FOREACH_DEQUEUED_REV_TYPED var nvar head tvar type name
225 .Fn GCQ_FIND var head cond
226 .Fn GCQ_FIND_REV var head cond
227 .Fn GCQ_FIND_TYPED var head tvar type name cond
228 .Fn GCQ_FIND_REV_TYPED var head tvar type name cond
229 .Fn GCQ_ASSERT cond
230 .Sh DESCRIPTION
231 The generic circular queue is a doubly linked list designed for efficient
232 merge operations and unconditional removal.
233 All basic operations can be performed with or without use of a separate head,
234 allowing easy replacement of any pointers where efficient removal is desired.
235 The meaning of the data type will not change; direct use and defined
236 operations can be mixed when convenient.
237 The basic type is:
238 .Bd -literal -offset indent
239 struct gcq {
240 struct gcq *q_next;
241 struct gcq *q_prev;
242 };
243 .Ed
244 .Pp
245 The structure must first be initialized such that the
246 .Va q_next
247 and
248 .Va q_prev
249 members point to the beginning of the
250 .Vt struct gcq .
251 This can be done with
252 .Fn gcq_init
253 and
254 .Fn gcq_init_head
255 or with constant initializers
256 .Fn GCQ_INIT
257 and
258 .Fn GCQ_INIT_HEAD .
259 A
260 .Vt struct gcq
261 should
262 .Em never
263 be given
264 .Dv NULL
265 values.
266 .Pp
267 The structure containing the
268 .Vt struct gcq
269 can be retrieved by pointer arithmetic in the
270 .Fn GCQ_ITEM
271 macro.
272 List traversal normally requires knowledge of the list head to safely
273 retrieve list items.
274 .Pp
275 Capitalized operation names are macros and should be assumed to cause multiple
276 evaluation of arguments.
277 .Li TYPED
278 variants of macros set a typed pointer variable instead of or in addition to
279 .Vt struct gcq *
280 arguments.
281 Additional type specific inlines and macros around some GCQ operations can be
282 useful.
283 .Pp
284 A few assertions are provided when
285 .Dv DIAGNOSTIC
286 is defined in the kernel or
287 .Dv _DIAGNOSTIC
288 is defined in userland.
289 If
290 .Dv GCQ_USE_ASSERT
291 is defined prior to header inclusions
292 then
293 .Fn assert
294 will be used for assertions and
295 .Dv NDEBUG
296 can be used to turn them off.
297 .Fn GCQ_ASSERT
298 is a wrapper around the used assertion function.
299 None of the operations accept
300 .Dv NULL
301 arguments, however this is not tested by assertion.
302 .Pp
303 The head is separately named for type checking but contains only a
304 .Vt struct gcq ,
305 a pointer to which can be retrieved via
306 .Fn gcq_hq .
307 The reverse operation is performed by
308 .Fn gcq_head ,
309 turning the supplied
310 .Vt struct gcq *
311 into
312 .Vt struct gcq_head * .
313 .Fn gcq_q
314 returns its
315 .Vt struct gcq *
316 argument and is used for type checking in
317 .Fn GCQ_ITEM .
318 There are no functions for retrieving the raw
319 .Va q_prev
320 and
321 .Va q_next
322 pointers as these are usually clearer when used directly (if at all).
323 .Pp
324 .Fn gcq_remove
325 returns the element removed and is always a valid operation after
326 initialization.
327 .Fn gcq_onlist
328 returns
329 .Dv false
330 if the structure links to itself and
331 .Dv true
332 otherwise.
333 .Fn gcq_empty
334 is the negation of this operation performed on a head.
335 .Fn gcq_linked
336 tests if
337 .Li "prev-\*[Gt]q_next == next \*[Am]\*[Am] next-\*[Gt]q_prev == prev" .
338 .Pp
339 .Fn gcq_tie
340 ties
341 .Va src
342 after
343 .Va dst
344 such that that if the old lists are DST, DST2 and SRC, SRC2, the new list is
345 DST, SRC, SRC2, DST2.
346 If
347 .Va dst
348 and
349 .Va src
350 are on the same list then any elements between but not including
351 .Va dst
352 and
353 .Va src
354 are cut from the list.
355 If
356 .Li dst == src
357 then the result is the same as
358 .Fn gcq_remove .
359 .Fn gcq_tie
360 is equivalent to
361 .Fn gcq_tie_after
362 except that the latter must only be used with arguments on separate lists or
363 not on lists and asserts that
364 .Li "src != dst \*[Am]\*[Am] dst-\*[Gt]q_prev != src" .
365 .Fn gcq_tie_before
366 performs the same operation on
367 .Li dst-\*[Gt]q_prev .
368 .Pp
369 .Fn gcq_merge
370 moves any elements on list
371 .Va src
372 (but not
373 .Va src
374 itself) to list
375 .Va dst .
376 It is normally used with two heads via
377 .Fn gcq_merge_head
378 or
379 .Fn gcq_merge_tail .
380 If
381 .Dv GCQ_UNCONDITIONAL_MERGE
382 is defined prior to header inclusion then the merge operations will always
383 perform a tie then remove
384 .Va src
385 from the new list, which may reduce code size slightly.
386 .Pp
387 .Fn gcq_clear
388 initializes all elements currently linked with
389 .Va q
390 and is normally used with a head as
391 .Fn gcq_remove_all .
392 .Pp
393 .Fn gcq_insert_after
394 and
395 .Fn gcq_insert_before
396 are slightly optimized versions of
397 .Fn gcq_tie
398 for the case where
399 .Va off
400 is not on a list and include assertions to this effect, which are also useful
401 to detect missing initialization.
402 .Fn gcq_insert_head
403 and
404 .Fn gcq_insert_tail
405 are the same operations applied to a head.
406 .Pp
407 .Fn GCQ_GOT_FIRST
408 and
409 .Fn GCQ_GOT_LAST
410 set
411 .Va var
412 to a pointer to the first or last
413 .Vt struct gcq
414 in the list
415 or
416 .Dv NULL
417 if the list is empty and return
418 .Dv false
419 if empty and
420 .Dv true
421 otherwise.
422 The boolean return is to emphasise that it is not normally safe and useful to
423 directly pass the raw first/next/etc. pointer to another function.
424 The macros are written such that the
425 .Dv NULL
426 values will be optimized out if not otherwise used.
427 .Li DEQUEUED
428 variants also remove the member from the list.
429 .Li COND
430 variants take an additional condition that is evaluated when the macro would
431 otherwise return
432 .Dv true .
433 If the condition is false
434 .Va var
435 or
436 .Va tvar
437 is set to
438 .Dv NULL
439 and no dequeue is performed.
440 .Pp
441 .Fn GCQ_GOT_NEXT
442 and variants take pointers to the current position, list head, and starting
443 point as arguments.
444 The list head will be skipped when it is reached unless it is equal to the
445 starting point; upon reaching the starting point
446 .Va var
447 will be set to
448 .Dv NULL
449 and the macro will return
450 .Dv false .
451 The next and prev macros also assert that
452 .Va current
453 is on the list unless it is equal to
454 .Va start .
455 These macros are the only provided method for iterating through the list from
456 an arbitrary point.
457 Traversal macros are only provided for list heads, however
458 .Fn gcq_head
459 can be used to treat any item as a head.
460 .Pp
461 Foreach variants contain an embedded
462 .Li for
463 statement for iterating over a list.
464 Those containing
465 .Li REV
466 use the
467 .Va q_prev
468 pointer for traversal, others use
469 .Va q_next .
470 The plain
471 .Fn GCQ_FOREACH
472 uses a single variable.
473 .Li NVAR
474 variants save the next pointer at the top of the loop so that the current
475 element can be removed without adjusting
476 .Va var .
477 This is useful when
478 .Va var
479 is passed to a function that might remove it but will not otherwise modify
480 the list.
481 When the head is reached both
482 .Va var
483 and
484 .Va nvar
485 elements are left pointing to the list head.
486 .Li FOREACH
487 asserts that
488 .Va var ,
489 and
490 .Li NVAR
491 asserts that
492 .Va nvar
493 does not point to itself when starting the next loop.
494 This assertion takes place after the variable is tested against the head so
495 it is safe to remove all elements from the list.
496 .Li RO
497 variants also set
498 .Va nvar
499 but assert that the two variables are linked at the end of each iteration.
500 This is useful when calling a function that is not supposed to remove the
501 element passed.
502 .Li DEQUEUED
503 variants are like
504 .Li NVAR
505 but remove each element before the code block is executed.
506 .Li TYPED
507 variants are equivalent to the untyped versions except that they take three
508 extra arguments: a typed pointer, the type name, and the member name of the
509 .Vt struct gcq
510 used in this list.
511 .Va tvar
512 is set to
513 .Dv NULL
514 when the head is reached.
515 .Pp
516 .Fn GCQ_FIND
517 is a foreach loop that does nothing except break when the supplied condition
518 is true.
519 .Li REV
520 and
521 .Li TYPED
522 variants are available.
523 .\" .Sh EXAMPLES
524 .Sh SEE ALSO
525 .Xr gcc 1 ,
526 .Xr _DIAGASSERT 3 ,
527 .Xr assert 3 ,
528 .Xr queue 3 ,
529 .Xr KASSERT 9
530 .Sh HISTORY
531 GCQ appeared in
532 .Nx 5.0 .