GG_CIRCLEQ_FIRST(3)

1gg-queue(3)                           GGI                          gg-queue(3)
2
3
4

NAME

6       gg-queue,   GG_SLIST_HEAD,  GG_SLIST_HEAD_INITIALIZER,  GG_SLIST_ENTRY,
7       GG_SLIST_INIT2,      GG_SLIST_INSERT_AFTER,       GG_SLIST_INSERT_HEAD,
8       GG_SLIST_REMOVE_HEAD,         GG_SLIST_REMOVE,        GG_SLIST_FOREACH,
9       GG_SLIST_EMPTY, GG_SLIST_FIRST, GG_SLIST_NEXT, GG_SIMPLEQ_HEAD, GG_SIM‐
10       PLEQ_HEAD_INITIALIZER,   GG_SIMPLEQ_ENTRY,   GG_SIMPLEQ_INIT,   GG_SIM‐
11       PLEQ_INSERT_HEAD,   GG_SIMPLEQ_INSERT_TAIL,    GG_SIMPLEQ_INSERT_AFTER,
12       GG_SIMPLEQ_REMOVE_HEAD,  GG_SIMPLEQ_REMOVE, GG_SIMPLEQ_FOREACH, GG_SIM‐
13       PLEQ_EMPTY,    GG_SIMPLEQ_FIRST,     GG_SIMPLEQ_NEXT,     GG_LIST_HEAD,
14       GG_LIST_HEAD_INITIALIZER,          GG_LIST_ENTRY,         GG_LIST_INIT,
15       GG_LIST_INSERT_AFTER,    GG_LIST_INSERT_BEFORE,    GG_LIST_INSERT_HEAD,
16       GG_LIST_REMOVE,    GG_LIST_FOREACH,    GG_LIST_EMPTY,    GG_LIST_FIRST,
17       GG_LIST_NEXT, GG_TAILQ_HEAD, GG_TAILQ_HEAD_INITIALIZER, GG_TAILQ_ENTRY,
18       GG_TAILQ_INIT,        GG_TAILQ_INSERT_HEAD,       GG_TAILQ_INSERT_TAIL,
19       GG_TAILQ_INSERT_AFTER,     GG_TAILQ_INSERT_BEFORE,     GG_TAILQ_REMOVE,
20       GG_TAILQ_FOREACH,       GG_TAILQ_FOREACH_REVERSE,       GG_TAILQ_EMPTY,
21       GG_TAILQ_FIRST, GG_TAILQ_NEXT,  GG_TAILQ_LAST,  GG_TAILQ_PREV,  GG_CIR‐
22       CLEQ_HEAD,   GG_CIRCLEQ_HEAD_INITIALIZER,   GG_CIRCLEQ_ENTRY,   GG_CIR‐
23       CLEQ_INIT, GG_CIRCLEQ_INSERT_AFTER,  GG_CIRCLEQ_INSERT_BEFORE,  GG_CIR‐
24       CLEQ_INSERT_HEAD,  GG_CIRCLEQ_INSERT_TAIL,  GG_CIRCLEQ_REMOVE,  GG_CIR‐
25       CLEQ_FOREACH,  GG_CIRCLEQ_FOREACH_REVERSE,  GG_CIRCLEQ_EMPTY,   GG_CIR‐
26       CLEQ_FIRST,  GG_CIRCLEQ_LAST, GG_CIRCLEQ_NEXT, GG_CIRCLEQ_PREV : imple‐
27       mentations of singly-linked lists, simple queues, lists,  tail  queues,
28       and circular queues
29

SYNOPSIS

31       #include <ggi/gg-queue.h>
32
33       GG_SLIST_HEAD(HEADNAME, TYPE);
34
35       GG_SLIST_HEAD_INITIALIZER(head);
36
37       GG_SLIST_ENTRY(TYPE);
38
39       GG_SLIST_INIT(GG_SLIST_HEAD *head);
40
41       GG_SLIST_INSERT_AFTER(TYPE *listelm, TYPE *elm, GG_SLIST_ENTRY NAME);
42
43       GG_SLIST_INSERT_HEAD(GG_SLIST_HEAD *head, TYPE *elm, GG_SLIST_ENTRY NAME);
44
45       GG_SLIST_REMOVE_HEAD(GG_SLIST_HEAD *head, GG_SLIST_ENTRY NAME);
46
47       GG_SLIST_REMOVE(GG_SLIST_HEAD *head, TYPE *elm, TYPE, GG_SLIST_ENTRY NAME);
48
49       GG_SLIST_FOREACH(TYPE *var, GG_SLIST_HEAD *head, GG_SLIST_ENTRY NAME);
50
51       int
52       GG_SLIST_EMPTY(GG_SLIST_HEAD *head);
53
54       TYPE *
55       GG_SLIST_FIRST(GG_SLIST_HEAD *head);
56
57       TYPE *
58       GG_SLIST_NEXT(TYPE *elm, GG_SLIST_ENTRY NAME);
59
60       GG_SIMPLEQ_HEAD(HEADNAME, TYPE);
61
62       GG_SIMPLEQ_HEAD_INITIALIZER(head);
63
64       GG_SIMPLEQ_ENTRY(TYPE);
65
66       GG_SIMPLEQ_INIT(GG_SIMPLEQ_HEAD *head);
67
68       GG_SIMPLEQ_INSERT_HEAD(GG_SIMPLEQ_HEAD *head, TYPE *elm, GG_SIMPLEQ_ENTRY NAME);
69
70       GG_SIMPLEQ_INSERT_TAIL(GG_SIMPLEQ_HEAD *head, TYPE *elm, GG_SIMPLEQ_ENTRY NAME);
71
72       GG_SIMPLEQ_INSERT_AFTER(GG_SIMPLEQ_HEAD *head, TYPE *listelm, TYPE *elm,
73                  GG_SIMPLEQ_ENTRY NAME);
74
75       GG_SIMPLEQ_REMOVE_HEAD(GG_SIMPLEQ_HEAD *head, GG_SIMPLEQ_ENTRY NAME);
76
77       GG_SIMPLEQ_REMOVE(GG_SIMPLEQ_HEAD *head, TYPE *elm, TYPE, GG_SIMPLEQ_ENTRY NAME);
78
79       GG_SIMPLEQ_FOREACH(TYPE *var, GG_SIMPLEQ_HEAD *head, GG_SIMPLEQ_ENTRY NAME);
80
81       int
82       GG_SIMPLEQ_EMPTY(GG_SIMPLEQ_HEAD *head);
83
84       TYPE *
85       GG_SIMPLEQ_FIRST(GG_SIMPLEQ_HEAD *head);
86
87       TYPE *
88       GG_SIMPLEQ_NEXT(TYPE *elm, GG_SIMPLEQ_ENTRY NAME);
89
90       GG_LIST_HEAD(HEADNAME, TYPE);
91
92       GG_LIST_HEAD_INITIALIZER(head);
93
94       GG_LIST_ENTRY(TYPE);
95
96       GG_LIST_INIT(GG_LIST_HEAD *head);
97
98       GG_LIST_INSERT_AFTER(TYPE *listelm, TYPE *elm, GG_LIST_ENTRY NAME);
99
100       GG_LIST_INSERT_BEFORE(TYPE *listelm, TYPE *elm, GG_LIST_ENTRY NAME);
101
102       GG_LIST_INSERT_HEAD(GG_LIST_HEAD *head, TYPE *elm, GG_LIST_ENTRY NAME);
103
104       GG_LIST_REMOVE(TYPE *elm, GG_LIST_ENTRY NAME);
105
106       GG_LIST_FOREACH(TYPE *var, GG_LIST_HEAD *head, GG_LIST_ENTRY NAME);
107
108       int
109       GG_LIST_EMPTY(GG_LIST_HEAD *head);
110
111       TYPE *
112       GG_LIST_FIRST(GG_LIST_HEAD *head);
113
114       TYPE *
115       GG_LIST_NEXT(TYPE *elm, GG_LIST_ENTRY NAME);
116
117       GG_TAILQ_HEAD(HEADNAME, TYPE);
118
119       GG_TAILQ_HEAD_INITIALIZER(head);
120
121       GG_TAILQ_ENTRY(TYPE);
122
123       GG_TAILQ_INIT(GG_TAILQ_HEAD *head);
124
125       GG_TAILQ_INSERT_HEAD(GG_TAILQ_HEAD *head, TYPE *elm, GG_TAILQ_ENTRY NAME);
126
127       GG_TAILQ_INSERT_TAIL(GG_TAILQ_HEAD *head, TYPE *elm, GG_TAILQ_ENTRY NAME);
128
129       GG_TAILQ_INSERT_AFTER(GG_TAILQ_HEAD *head, TYPE *listelm, TYPE *elm,
130                  GG_TAILQ_ENTRY NAME);
131
132       GG_TAILQ_INSERT_BEFORE(TYPE *listelm, TYPE *elm, GG_TAILQ_ENTRY NAME);
133
134       GG_TAILQ_REMOVE(GG_TAILQ_HEAD *head, TYPE *elm, GG_TAILQ_ENTRY NAME);
135
136       GG_TAILQ_FOREACH(TYPE *var, GG_TAILQ_HEAD *head, GG_TAILQ_ENTRY NAME);
137
138       GG_TAILQ_FOREACH_REVERSE(TYPE *var, GG_TAILQ_HEAD *head, HEADNAME,
139                  GG_TAILQ_ENTRY NAME);
140
141       int
142       GG_TAILQ_EMPTY(GG_TAILQ_HEAD *head);
143
144       TYPE *
145       GG_TAILQ_FIRST(GG_TAILQ_HEAD *head);
146
147       TYPE *
148       GG_TAILQ_NEXT(TYPE *elm, GG_TAILQ_ENTRY NAME);
149
150       TYPE *
151       GG_TAILQ_LAST(GG_TAILQ_HEAD *head, HEADNAME);
152
153       TYPE *
154       GG_TAILQ_PREV(TYPE *elm, HEADNAME, GG_TAILQ_ENTRY NAME);
155
156       GG_CIRCLEQ_HEAD(HEADNAME, TYPE);
157
158       GG_CIRCLEQ_HEAD_INITIALIZER(head);
159
160       GG_CIRCLEQ_ENTRY(TYPE);
161
162       GG_CIRCLEQ_INIT(GG_CIRCLEQ_HEAD *head);
163
164       GG_CIRCLEQ_INSERT_AFTER(GG_CIRCLEQ_HEAD *head, TYPE *listelm, TYPE *elm,
165                  GG_CIRCLEQ_ENTRY NAME);
166
167       GG_CIRCLEQ_INSERT_BEFORE(GG_CIRCLEQ_HEAD *head, TYPE *listelm, TYPE *elm,
168                  GG_CIRCLEQ_ENTRY NAME);
169
170       GG_CIRCLEQ_INSERT_HEAD(GG_CIRCLEQ_HEAD *head, TYPE *elm, GG_CIRCLEQ_ENTRY NAME);
171
172       GG_CIRCLEQ_INSERT_TAIL(GG_CIRCLEQ_HEAD *head, TYPE *elm, GG_CIRCLEQ_ENTRY NAME);
173
174       GG_CIRCLEQ_REMOVE(GG_CIRCLEQ_HEAD *head, TYPE *elm, GG_CIRCLEQ_ENTRY NAME);
175
176       GG_CIRCLEQ_FOREACH(TYPE *var, GG_CIRCLEQ_HEAD *head, GG_CIRCLEQ_ENTRY NAME);
177
178       GG_CIRCLEQ_FOREACH_REVERSE(TYPE *var, GG_CIRCLEQ_HEAD *head,
179                  GG_CIRCLEQ_ENTRY NAME);
180
181       int
182       GG_CIRCLEQ_EMPTY(GG_CIRCLEQ_HEAD *head);
183
184       TYPE *
185       GG_CIRCLEQ_FIRST(GG_CIRCLEQ_HEAD *head);
186
187       TYPE *
188       GG_CIRCLEQ_LAST(GG_CIRCLEQ_HEAD *head);
189
190       TYPE *
191       GG_CIRCLEQ_NEXT(TYPE *elm, GG_CIRCLEQ_ENTRY NAME);
192
193       TYPE *
194       GG_CIRCLEQ_PREV(TYPE *elm, GG_CIRCLEQ_ENTRY NAME);
195
196

DESCRIPTION

198       These  macros  define  and  operate  on  five types of data structures:
199       singly- linked lists, simple queues, lists, tail queues,  and  circular
200       queues.  All five structures support the following functionality:
201
202       1   Insertion of a new entry at the head of the list.
203
204       2   Insertion of a new entry before or after any element in the list.
205
206       3   Removal of any entry in the list.
207
208       4   Forward traversal through the list.
209
210       Singly-linked  lists  are  the simplest of the five data structures and
211       support only the above functionality.  Singly-linked  lists  are  ideal
212       for  applications  with  large  datasets and few or no removals, or for
213       implementing a LIFO queue.
214
215       Simple queues add the following functionality:
216
217       1   Entries can be added at the end of a list.
218
219       However:
220
221       1   Entries may not be added before any element in the list.
222
223       2   All list insertions and removals must specify the head of the list.
224
225       3   Each head entry requires two pointers rather than one.
226
227       Simple queues are ideal for applications with large datasets and few or
228       no removals, or for implementing a FIFO  queue.
229
230       All  doubly  linked  types  of data structures (lists, tail queues, and
231       circle queues) additionally allow:
232
233       1   Insertion of a new entry before any element in the list.
234
235       2   O(1) removal of any entry in the list.
236
237       However:
238
239       1   Each element requires two pointers rather than one.
240
241       2   Code size and execution time of operations (except for removal)  is
242           about twice that of the singly-linked data-structures.
243
244       Linked  lists are the simplest of the doubly linked data structures and
245       support only the above functionality over singly-linked lists.
246
247       Tail queues add the following functionality:
248
249       1   Entries can be added at the end of a list.
250
251       However:
252
253       1   All list insertions and removals, except insertion  before  another
254           element, must specify the head of the list.
255
256       2   Each head entry requires two pointers rather than one.
257
258       3   Code  size is about 15% greater and operations run about 20% slower
259           than lists.
260
261       Circular queues add the following functionality:
262
263       1   Entries can be added at the end of a list.
264
265       2   They may be traversed backwards, from tail to head.
266
267       However:
268
269       1   All list insertions and removals must specify the head of the list.
270
271       2   Each head entry requires two pointers rather than one.
272
273       3   The termination condition for traversal is more complex.
274
275       4   Code size is about 40% greater and operations run about 45%  slower
276           than lists.
277
278       In the macro definitions, TYPE is the name of a user defined structure,
279       that must contain a  field  of  type  GG_LIST_ENTRY,  GG_SIMPLEQ_ENTRY,
280       GG_SLIST_ENTRY,  GG_TAILQ_ENTRY,  or  GG_CIRCLEQ_ENTRY, named NAME. The
281       argument HEADNAME is the name of a user defined structure that must  be
282       declared using the macros GG_LIST_HEAD, GG_SIMPLEQ_HEAD, GG_SLIST_HEAD,
283       GG_TAILQ_HEAD, or GG_CIRCLEQ_HEAD. See the examples below  for  further
284       explanation of how these macros are used.
285

SINGLY-LINKED LISTS

287       A singly-linked list is headed by a structure defined by the SLIST_HEAD
288       macro. This structure contains a single pointer to the first element on
289       the  list. The elements are singly linked for minimum space and pointer
290       manipulation overhead at the expense of O(n) removal for arbitrary ele‐
291       ments.  New elements can be added to the list after an existing element
292       or at the head of the list.  An GG_SLIST_HEAD structure is declared  as
293       follows:
294
295       GG_SLIST_HEAD(HEADNAME, TYPE) head;
296
297       where  HEADNAME is the name of the structure to be defined, and TYPE is
298       the type of the elements to be linked into the list.  A pointer to  the
299       head of the list can later be declared as:
300
301       struct HEADNAME *headp;
302
303       (The names head and headp are user selectable.)
304
305       The macro GG_SLIST_HEAD_INITIALIZER evaluates to an initializer for the
306       list head.
307
308       The macro GG_SLIST_EMPTY evaluates to true if there are no elements  in
309       the list.
310
311       The  macro  GG_SLIST_ENTRY  declares a structure that connects the ele‐
312       ments in the list.
313
314       The macro GG_SLIST_FIRST returns the first element in the list or  NULL
315       if the list is empty.
316
317       The macro GG_SLIST_FOREACH traverses the list referenced by head in the
318       forward direction, assigning each element in turn to var.
319
320       The macro GG_SLIST_INIT initializes the list referenced by head.
321
322       The macro GG_SLIST_INSERT_HEAD inserts the new element elm at the  head
323       of the list.
324
325       The  macro  GG_SLIST_INSERT_AFTER inserts the new element elm after the
326       element listelm.
327
328       The macro GG_SLIST_NEXT returns the next element in the list.
329
330       The macro GG_SLIST_REMOVE removes the element elm from the list.
331
332       The macro GG_SLIST_REMOVE_HEAD removes the first element from the  head
333       of  the  list.  For optimum efficiency, elements being removed from the
334       head of the list should  explicitly  use  this  macro  instead  of  the
335       generic GG_SLIST_REMOVE macro.
336

SINGLY-LINKED LIST EXAMPLE

338       GG_SLIST_HEAD(slisthead, entry) head =
339           GG_SLIST_HEAD_INITIALIZER(head);
340       struct slisthead *headp;                /* Singly-linked List head. */
341       struct entry {
342               ...
343               GG_SLIST_ENTRY(entry) entries;  /* Singly-linked List. */
344               ...
345       } *n1, *n2, *n3, *np;
346
347       GG_SLIST_INIT(&head);                   /* Initialize the list. */
348
349       n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
350       GG_SLIST_INSERT_HEAD(&head, n1, entries);
351
352       n2 = malloc(sizeof(struct entry));      /* Insert after. */
353       GG_SLIST_INSERT_AFTER(n1, n2, entries);
354
355       GG_SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
356       free(n2);
357
358       n3 = GG_SLIST_FIRST(&head);
359       GG_SLIST_REMOVE_HEAD(&head, entries);   /* Deletion from the head. */
360       free(n3);
361                                               /* Forward traversal. */
362       GG_SLIST_FOREACH(np, &head, entries)
363               np-> ...
364
365       while (!GG_SLIST_EMPTY(&head)) {        /* List Deletion. */
366               n1 = GG_SLIST_FIRST(&head);
367               GG_SLIST_REMOVE_HEAD(&head, entries);
368               free(n1);
369       }
370
371

SIMPLE QUEUES

373       A  simple queue is headed by a structure defined by the GG_SIMPLEQ_HEAD
374       macro.  This structure contains a pair of pointers, one  to  the  first
375       element  in  the  simple queue and the other to the last element in the
376       simple queue.  The elements are singly linked  for  minimum  space  and
377       pointer  manipulation overhead at the expense of O(n) removal for arbi‐
378       trary elements.  New elements can be added to the queue after an exist‐
379       ing  element,  at  the head of the queue, or at the end of the queue. A
380       GG_SIMPLEQ_HEAD structure is declared as follows:
381
382       GG_SIMPLEQ_HEAD(HEADNAME, TYPE) head;
383
384       where HEADNAME is the name of the structure to be defined, and TYPE  is
385       the type of the elements to be linked into the simple queue.  A pointer
386       to the head of the simple queue can later be declared as:
387
388       struct HEADNAME *headp;
389
390       (The names head and headp are user selectable.)
391
392       The macro GG_SIMPLEQ_ENTRYk declares a structure that connects the ele‐
393       ments in the simple queue.
394
395       The  macro  GG_SIMPLEQ_HEAD_INITIALIZER  provides  a value which can be
396       used to initialize a simple queue head at compile time, and is used  at
397       the point that the simple queue head variable is declared, like:
398
399       struct HEADNAME head = GG_SIMPLEQ_HEAD_INITIALIZER(head);
400
401       The  macro  GG_SIMPLEQ_INIT  initializes the simple queue referenced by
402       head.
403
404       The macro GG_SIMPLEQ_INSERT_HEAD inserts the new  element  elm  at  the
405       head of the simple queue.
406
407       The macro GG_SIMPLEQ_INSERT_TAIL inserts the new element elm at the end
408       of the simple queue.
409
410       The macro GG_SIMPLEQ_INSERT_AFTER inserts the new element elm after the
411       ele- ment listelm.
412
413       The macro GG_SIMPLEQ_REMOVE removes elm from the simple queue.
414
415       The  macro  GG_SIMPLEQ_REMOVE_HEAD  removes  the first element from the
416       head of the simple  queue.   For  optimum  efficiency,  elements  being
417       removed  from  the  head  of the queue should explicitly use this macro
418       instead of the generic GG_SIMPLQ_REMOVE macro.
419
420       The macro GG_SIMPLEQ_EMPTY return true if the simple queue head has  no
421       elements.
422
423       The  macro  GG_SIMPLEQ_FIRST  returns  the  first element of the simple
424       queue head.
425
426       The macro GG_SIMPLEQ_FOREACH traverses the  tail  queue  referenced  by
427       head in the forward direction, assigning each element in turn to var.
428
429       The macro GG_SIMPLEQ_NEXT returns the element after the element elm.
430

SIMPLE QUEUE EXAMPLE

432       GG_SIMPLEQ_HEAD(simplehead, entry) head;
433       struct simplehead *headp;               /* Simple queue head. */
434       struct entry {
435               ...
436               GG_SIMPLEQ_ENTRY(entry) entries;/* Simple queue. */
437               ...
438       } *n1, *n2, *np;
439
440       GG_SIMPLEQ_INIT(&head);                 /* Initialize the queue. */
441
442       n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
443       GG_SIMPLEQ_INSERT_HEAD(&head, n1, entries);
444
445       n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
446       GG_SIMPLEQ_INSERT_TAIL(&head, n1, entries);
447
448       n2 = malloc(sizeof(struct entry));      /* Insert after. */
449       GG_SIMPLEQ_INSERT_AFTER(&head, n1, n2, entries);
450                                               /* Forward traversal. */
451       GG_SIMPLEQ_FOREACH(np, &head, entries)
452               np-> ...
453                                               /* Delete. */
454       while (GG_SIMPLEQ_FIRST(&head) != NULL)
455               GG_SIMPLEQ_REMOVE_HEAD(&head, entries);
456       if (GG_SIMPLEQ_EMPTY(&head))            /* Test for emptiness. */
457               printf("nothing to do\n");
458
459

LISTS

461       A  list  is  headed  by  a structure defined by the GG_LIST_HEAD macro.
462       This structure contains a single pointer to the first  element  on  the
463       list.   The elements are doubly linked so that an arbitrary element can
464       be removed without traversing the list.  New elements can be  added  to
465       the  list  after an existing element, before an existing element, or at
466       the head of the list. A LIST_HEAD structure is declared as follows:
467
468       GG_LIST_HEAD(HEADNAME, TYPE) head;
469
470       where HEADNAME is the name of the structure to be defined, and TYPE  is
471       the  type of the elements to be linked into the list.  A pointer to the
472       head of the list can later be declared as:
473
474       struct HEADNAME *headp;
475
476       (The names head and headp are user selectable.)
477
478       The macro GG_LIST_ENTRY declares a structure that connects the elements
479       in the list.
480
481       The  macro  GG_LIST_HEAD_INITIALIZER provides a value which can be used
482       to initialize a list head at compile time, and is  used  at  the  point
483       that the list head variable is declared, like:
484
485       struct HEADNAME head = GG_LIST_HEAD_INITIALIZER(head);
486
487       The macro GG_LIST_INIT initializes the list referenced by head.
488
489       The  macro  GG_LIST_INSERT_HEAD inserts the new element elm at the head
490       of the list.
491
492       The macro GG_LIST_INSERT_AFTER inserts the new element  elm  after  the
493       element listelm.
494
495       The  macro GG_LIST_INSERT_BEFORE inserts the new element elm before the
496       element listelm.
497
498       The macro GG_LIST_REMOVE removes the element elm from the list.
499
500       The macro GG_LIST_EMPTY return true if the list head has no elements.
501
502       The macro GG_LIST_FIRST returns the first element of the list head.
503
504       The macro GG_LIST_FOREACH traverses the list referenced by head in  the
505       forward direction, assigning each element in turn to var.
506
507       The macro GG_LIST_NEXT returns the element after the element elm.
508

LIST EXAMPLE

510       GG_LIST_HEAD(listhead, entry) head;
511       struct listhead *headp;                 /* List head. */
512       struct entry {
513               ...
514               GG_LIST_ENTRY(entry) entries;   /* List. */
515               ...
516       } *n1, *n2, *np;
517
518       GG_LIST_INIT(&head);                    /* Initialize the list. */
519
520       n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
521       GG_LIST_INSERT_HEAD(&head, n1, entries);
522
523       n2 = malloc(sizeof(struct entry));      /* Insert after. */
524       GG_LIST_INSERT_AFTER(n1, n2, entries);
525
526       n2 = malloc(sizeof(struct entry));      /* Insert before. */
527       GG_LIST_INSERT_BEFORE(n1, n2, entries);
528                                               /* Forward traversal. */
529       GG_LIST_FOREACH(np, &head, entries)
530               np-> ...
531                                               /* Delete. */
532       while (GG_LIST_FIRST(&head) != NULL)
533               GG_LIST_REMOVE(LIST_FIRST(&head), entries);
534       if (GG_LIST_EMPTY(&head))               /* Test for emptiness. */
535               printf("nothing to do\n");
536
537

TAIL QUEUES

539       A  tail  queue  is  headed  by a structure defined by the GG_TAILQ_HEAD
540       macro.  This structure contains a pair of pointers, one  to  the  first
541       element in the tail queue and the other to the last element in the tail
542       queue. The elements are doubly linked so that an arbitrary element  can
543       be removed without traversing the tail queue. New elements can be added
544       to the queue after an existing element, before an existing element,  at
545       the  head of the queue, or at the end the queue. A GG_TAILQ_HEAD struc‐
546       ture is declared as follows:
547
548       TAILQ_HEAD(HEADNAME, TYPE) head;
549
550       where HEADNAME is the name of the structure to be defined, and TYPE  is
551       the  type  of the elements to be linked into the tail queue.  A pointer
552       to the head of the tail queue can later be declared as:
553
554       struct HEADNAME *headp;
555
556       (The names head and headp are user selectable.)
557
558       The macro GG_TAILQ_ENTRY declares a structure that  connects  the  ele‐
559       ments in the tail queue.
560
561       The  macro GG_TAILQ_HEAD_INITIALIZER provides a value which can be used
562       to initialize a tail queue head at compile time, and  is  used  at  the
563       point that the tail queue head variable is declared, like:
564
565       struct HEADNAME head = GG_TAILQ_HEAD_INITIALIZER(head);
566
567       The macro GG_TAILQ_INIT initializes the tail queue referenced by head.
568
569       The  macro GG_TAILQ_INSERT_HEAD inserts the new element elm at the head
570       of the tail queue.
571
572       The macro GG_TAILQ_INSERT_TAIL inserts the new element elm at  the  end
573       of the tail queue.
574
575       The  macro  GG_TAILQ_INSERT_AFTER inserts the new element elm after the
576       element listelm.
577
578       The macro GG_TAILQ_INSERT_BEFORE inserts the new element elm before the
579       element listelm.
580
581       The macro GG_TAILQ_REMOVE removes the element elm from the tail queue.
582
583       The macro GG_TAILQ_EMPTY return true if the tail queue head has no ele‐
584       ments.
585
586       The macro GG_TAILQ_FIRST returns the first element of  the  tail  queue
587       head.
588
589       The  macro GG_TAILQ_FOREACH traverses the tail queue referenced by head
590       in the forward direction, assigning each element in turn to var.
591
592       The macro GG_TAILQ_FOREACH_REVERSE traverses the tail queue  referenced
593       by  head  in  the  reverse direction, assigning each element in turn to
594       var.
595
596       The macro GG_TAILQ_NEXT returns the element after the element elm
597

TAIL QUEUE EXAMPLE

599       GG_TAILQ_HEAD(tailhead, entry) head;
600       struct tailhead *headp;                 /* Tail queue head. */
601       struct entry {
602               ...
603               GG_TAILQ_ENTRY(entry) entries;  /* Tail queue. */
604               ...
605       } *n1, *n2, *np;
606
607       GG_TAILQ_INIT(&head);                   /* Initialize the queue. */
608
609       n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
610       GG_TAILQ_INSERT_HEAD(&head, n1, entries);
611
612       n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
613       GG_TAILQ_INSERT_TAIL(&head, n1, entries);
614
615       n2 = malloc(sizeof(struct entry));      /* Insert after. */
616       GG_TAILQ_INSERT_AFTER(&head, n1, n2, entries);
617
618       n2 = malloc(sizeof(struct entry));      /* Insert before. */
619       GG_TAILQ_INSERT_BEFORE(n1, n2, entries);
620                                               /* Forward traversal. */
621       GG_TAILQ_FOREACH(np, &head, entries)
622               np-> ...
623                                               /* Reverse traversal. */
624       GG_TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
625               np-> ...
626                                               /* Delete. */
627       while (GG_TAILQ_FIRST(&head) != NULL)
628               GG_TAILQ_REMOVE(&head, GG_TAILQ_FIRST(&head), entries);
629       if (GG_TAILQ_EMPTY(&head))              /* Test for emptiness. */
630               printf("nothing to do\n");
631
632

CIRCULAR QUEUES

634       A circular queue is headed  by  a  structure  defined  by  the  GG_CIR‐
635       CLEQ_HEAD  macro.   This  structure contains a pair of pointers, one to
636       the first element in the circular queue and the other to the last  ele‐
637       ment  in the circular queue.  The elements are doubly linked so that an
638       arbitrary element can be removed without  traversing  the  queue.   New
639       elements can be added to the queue after an existing element, before an
640       existing element, at the head of the queue, or at the end of the queue.
641       A GG_CIRCLEQ_HEAD structure is declared as follows:
642
643       GG_CIRCLEQ_HEAD(HEADNAME, TYPE) head;
644
645       where  HEADNAME is the name of the structure to be defined, and TYPE is
646       the type of the elements to be  linked  into  the  circular  queue.   A
647       pointer to the head of the circular queue can later be declared as:
648
649       struct HEADNAME *headp;
650
651       (The names head and headp are user selectable.)
652
653       The  macro GG_CIRCLEQ_ENTRY declares a structure that connects the ele‐
654       ments in the circular queue.
655
656       The macro GG_CIRCLEQ_HEAD_INITIALIZER provides a  value  which  can  be
657       used  to  initialize a circular queue head at compile time, and is used
658       at the point that the circular queue head variable is declared, like:
659
660       struct HEADNAME head = GG_CIRCLEQ_HEAD_INITIALIZER(head);
661
662       The macro GG_CIRCLEQ_INIT initializes the circular queue referenced  by
663       head.
664
665       The  macro  GG_CIRCLEQ_INSERT_HEAD  inserts  the new element elm at the
666       head of the circular queue.
667
668       The macro GG_CIRCLEQ_INSERT_TAIL inserts the new element elm at the end
669       of the circular queue.
670
671       The macro GG_CIRCLEQ_INSERT_AFTER inserts the new element elm after the
672       element listelm.
673
674       The macro GG_CIRCLEQ_INSERT_BEFORE inserts the new element  elm  before
675       the element listelm.
676
677       The  macro  GG_CIRCLEQ_REMOVE removes the element elm from the circular
678       queue.
679
680       The macro GG_CIRCLEQ_EMPTY return true if the circular queue  head  has
681       no elements.
682
683       The  macro  GG_CIRCLEQ_FIRST  returns the first element of the circular
684       queue head.
685
686       The macro GG_CICRLEQ_FOREACH traverses the circle queue  referenced  by
687       head in the forward direction, assigning each element in turn to var.
688
689       The  macro GG_CICRLEQ_FOREACH_REVERSE traverses the circle queue refer‐
690       enced by head in the reverse direction, assigning each element in  turn
691       to var.
692
693       The  macro  GG_CIRCLEQ_LAST  returns  the  last element of the circular
694       queue head.
695
696       The macro GG_CIRCLEQ_NEXT returns the element after the element elm.
697
698       The macro GG_CIRCLEQ_PREV returns the element before the element elm.
699

CIRCULAR QUEUE EXAMPLE

701       GG_CIRCLEQ_HEAD(circleq, entry) head;
702       struct circleq *headp;                  /* Circular queue head. */
703       struct entry {
704              ...
705              GG_CIRCLEQ_ENTRY(entry) entries; /* Circular queue. */
706              ...
707       } *n1, *n2, *np;
708
709       GG_CIRCLEQ_INIT(&head);                 /* Initialize the circular queue. */
710
711       n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
712       GG_CIRCLEQ_INSERT_HEAD(&head, n1, entries);
713
714       n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
715       GG_CIRCLEQ_INSERT_TAIL(&head, n1, entries);
716
717       n2 = malloc(sizeof(struct entry));      /* Insert after. */
718       GG_CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
719
720       n2 = malloc(sizeof(struct entry));      /* Insert before. */
721       GG_CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
722                                               /* Forward traversal. */
723       GG_CIRCLEQ_FOREACH(np, &head, entries)
724               np-> ...
725                                               /* Reverse traversal. */
726       GG_CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
727               np-> ...
728                                               /* Delete. */
729       while (GG_CIRCLEQ_FIRST(&head) != (void *)&head)
730               GG_CIRCLEQ_REMOVE(&head, GG_CIRCLEQ_FIRST(&head), entries);
731       if (GG_CIRCLEQ_EMPTY(&head))            /* Test for emptiness. */
732               printf("nothing to do\n");
733
734