TAILQ_INIT(3)

1TAILQ(3)                   Library Functions Manual                   TAILQ(3)
2
3
4

NAME

6       TAILQ_CONCAT,  TAILQ_EMPTY,  TAILQ_ENTRY,  TAILQ_FIRST,  TAILQ_FOREACH,
7       TAILQ_FOREACH_REVERSE, TAILQ_HEAD, TAILQ_HEAD_INITIALIZER,  TAILQ_INIT,
8       TAILQ_INSERT_AFTER,  TAILQ_INSERT_BEFORE,  TAILQ_INSERT_HEAD, TAILQ_IN‐
9       SERT_TAIL, TAILQ_LAST, TAILQ_NEXT, TAILQ_PREV, TAILQ_REMOVE - implemen‐
10       tation of a doubly linked tail queue
11

LIBRARY

13       Standard C library (libc, -lc)
14

SYNOPSIS

16       #include <sys/queue.h>
17
18       TAILQ_ENTRY(TYPE);
19
20       TAILQ_HEAD(HEADNAME, TYPE);
21       TAILQ_HEAD TAILQ_HEAD_INITIALIZER(TAILQ_HEAD head);
22       void TAILQ_INIT(TAILQ_HEAD *head);
23
24       int TAILQ_EMPTY(TAILQ_HEAD *head);
25
26       void TAILQ_INSERT_HEAD(TAILQ_HEAD *head,
27                                struct TYPE *elm, TAILQ_ENTRY NAME);
28       void TAILQ_INSERT_TAIL(TAILQ_HEAD *head,
29                                struct TYPE *elm, TAILQ_ENTRY NAME);
30       void TAILQ_INSERT_BEFORE(struct TYPE *listelm,
31                                struct TYPE *elm, TAILQ_ENTRY NAME);
32       void TAILQ_INSERT_AFTER(TAILQ_HEAD *head, struct TYPE *listelm,
33                                struct TYPE *elm, TAILQ_ENTRY NAME);
34
35       struct TYPE *TAILQ_FIRST(TAILQ_HEAD *head);
36       struct TYPE *TAILQ_LAST(TAILQ_HEAD *head, HEADNAME);
37       struct TYPE *TAILQ_PREV(struct TYPE *elm, HEADNAME, TAILQ_ENTRY NAME);
38       struct TYPE *TAILQ_NEXT(struct TYPE *elm, TAILQ_ENTRY NAME);
39
40       TAILQ_FOREACH(struct TYPE *var, TAILQ_HEAD *head,
41                                TAILQ_ENTRY NAME);
42       TAILQ_FOREACH_REVERSE(struct TYPE *var, TAILQ_HEAD *head, HEADNAME,
43                                TAILQ_ENTRY NAME);
44
45       void TAILQ_REMOVE(TAILQ_HEAD *head, struct TYPE *elm,
46                                TAILQ_ENTRY NAME);
47
48       void TAILQ_CONCAT(TAILQ_HEAD *head1, TAILQ_HEAD *head2,
49                                TAILQ_ENTRY NAME);
50

DESCRIPTION

52       These macros define and operate on doubly linked tail queues.
53
54       In the macro definitions, TYPE is the name of a user defined structure,
55       that must contain a field of type TAILQ_ENTRY, named NAME.   The  argu‐
56       ment  HEADNAME is the name of a user defined structure that must be de‐
57       clared using the macro TAILQ_HEAD().
58
59   Creation
60       A tail queue is headed by  a  structure  defined  by  the  TAILQ_HEAD()
61       macro.   This  structure  contains a pair of pointers, one to the first
62       element in the queue and the other to the last element  in  the  queue.
63       The  elements are doubly linked so that an arbitrary element can be re‐
64       moved without traversing the queue.  New elements can be added  to  the
65       queue  after  an  existing  element, before an existing element, at the
66       head of the queue, or at the end of the queue.  A TAILQ_HEAD  structure
67       is declared as follows:
68
69           TAILQ_HEAD(HEADNAME, TYPE) head;
70
71       where  struct  HEADNAME is the structure to be defined, and struct TYPE
72       is the type of the elements to be linked into the queue.  A pointer  to
73       the head of the queue can later be declared as:
74
75           struct HEADNAME *headp;
76
77       (The names head and headp are user selectable.)
78
79       TAILQ_ENTRY()  declares  a  structure that connects the elements in the
80       queue.
81
82       TAILQ_HEAD_INITIALIZER() evaluates to  an  initializer  for  the  queue
83       head.
84
85       TAILQ_INIT() initializes the queue referenced by
86
87       TAILQ_EMPTY()  evaluates  to  true  if there are no items on the queue.
88       head.
89
90   Insertion
91       TAILQ_INSERT_HEAD() inserts the new element elm  at  the  head  of  the
92       queue.
93
94       TAILQ_INSERT_TAIL()  inserts  the  new  element  elm  at the end of the
95       queue.
96
97       TAILQ_INSERT_BEFORE() inserts the new element elm  before  the  element
98       listelm.
99
100       TAILQ_INSERT_AFTER() inserts the new element elm after the element lis‐
101       telm.
102
103   Traversal
104       TAILQ_FIRST() returns the first item on the queue, or NULL if the queue
105       is empty.
106
107       TAILQ_LAST() returns the last item on the queue.  If the queue is empty
108       the return value is NULL.
109
110       TAILQ_PREV() returns the previous item on the queue, or  NULL  if  this
111       item is the first.
112
113       TAILQ_NEXT()  returns  the next item on the queue, or NULL if this item
114       is the last.
115
116       TAILQ_FOREACH() traverses the queue referenced by head in  the  forward
117       direction,  assigning  each element in turn to var.  var is set to NULL
118       if the loop completes normally, or if there were no elements.
119
120       TAILQ_FOREACH_REVERSE() traverses the queue referenced by head  in  the
121       reverse direction, assigning each element in turn to var.
122
123   Removal
124       TAILQ_REMOVE() removes the element elm from the queue.
125
126   Other features
127       TAILQ_CONCAT()  concatenates  the queue headed by head2 onto the end of
128       the one headed by head1 removing all entries from the former.
129

RETURN VALUE

131       TAILQ_EMPTY() returns nonzero if the queue is empty, and  zero  if  the
132       queue contains at least one entry.
133
134       TAILQ_FIRST(),  TAILQ_LAST(),  TAILQ_PREV(),  and TAILQ_NEXT() return a
135       pointer to the first, last, previous, or next TYPE  structure,  respec‐
136       tively.
137
138       TAILQ_HEAD_INITIALIZER() returns an initializer that can be assigned to
139       the queue head.
140

STANDARDS

142       BSD.
143

HISTORY

145       4.4BSD.
146

CAVEATS

148       TAILQ_FOREACH() and TAILQ_FOREACH_REVERSE() don't allow var to  be  re‐
149       moved  or freed within the loop, as it would interfere with the traver‐
150       sal.  TAILQ_FOREACH_SAFE() and TAILQ_FOREACH_REVERSE_SAFE(), which  are
151       present  on  the BSDs but are not present in glibc, fix this limitation
152       by allowing var to safely be removed  from  the  list  and  freed  from
153       within the loop without interfering with the traversal.
154

EXAMPLES

156       #include <stddef.h>
157       #include <stdio.h>
158       #include <stdlib.h>
159       #include <sys/queue.h>
160
161       struct entry {
162           int data;
163           TAILQ_ENTRY(entry) entries;             /* Tail queue */
164       };
165
166       TAILQ_HEAD(tailhead, entry);
167
168       int
169       main(void)
170       {
171           struct entry *n1, *n2, *n3, *np;
172           struct tailhead head;                   /* Tail queue head */
173           int i;
174
175           TAILQ_INIT(&head);                      /* Initialize the queue */
176
177           n1 = malloc(sizeof(struct entry));      /* Insert at the head */
178           TAILQ_INSERT_HEAD(&head, n1, entries);
179
180           n1 = malloc(sizeof(struct entry));      /* Insert at the tail */
181           TAILQ_INSERT_TAIL(&head, n1, entries);
182
183           n2 = malloc(sizeof(struct entry));      /* Insert after */
184           TAILQ_INSERT_AFTER(&head, n1, n2, entries);
185
186           n3 = malloc(sizeof(struct entry));      /* Insert before */
187           TAILQ_INSERT_BEFORE(n2, n3, entries);
188
189           TAILQ_REMOVE(&head, n2, entries);       /* Deletion */
190           free(n2);
191                                                   /* Forward traversal */
192           i = 0;
193           TAILQ_FOREACH(np, &head, entries)
194               np->data = i++;
195                                                   /* Reverse traversal */
196           TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
197               printf("%i\n", np->data);
198                                                   /* TailQ deletion */
199           n1 = TAILQ_FIRST(&head);
200           while (n1 != NULL) {
201               n2 = TAILQ_NEXT(n1, entries);
202               free(n1);
203               n1 = n2;
204           }
205           TAILQ_INIT(&head);
206
207           exit(EXIT_SUCCESS);
208       }
209