1TAILQ(3) Linux Programmer's Manual TAILQ(3)
2
3
4
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
13 #include <sys/queue.h>
14
15 void TAILQ_CONCAT(TAILQ_HEAD *head1, TAILQ_HEAD *head2,
16 TAILQ_ENTRY NAME);
17
18 int TAILQ_EMPTY(TAILQ_HEAD *head);
19
20 TAILQ_ENTRY(TYPE);
21
22 struct TYPE *TAILQ_FIRST(TAILQ_HEAD *head);
23
24 TAILQ_FOREACH(struct TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME);
25
26 TAILQ_FOREACH_REVERSE(struct TYPE *var, TAILQ_HEAD *head, HEADNAME,
27 TAILQ_ENTRY NAME);
28
29 TAILQ_HEAD(HEADNAME, TYPE);
30
31 TAILQ_HEAD TAILQ_HEAD_INITIALIZER(TAILQ_HEAD head);
32
33 void TAILQ_INIT(TAILQ_HEAD *head);
34
35 void TAILQ_INSERT_AFTER(TAILQ_HEAD *head, struct TYPE *listelm,
36 struct TYPE *elm, TAILQ_ENTRY NAME);
37
38 void TAILQ_INSERT_BEFORE(struct TYPE *listelm, struct TYPE *elm,
39 TAILQ_ENTRY NAME);
40
41 void TAILQ_INSERT_HEAD(TAILQ_HEAD *head, struct TYPE *elm,
42 TAILQ_ENTRY NAME);
43
44 void TAILQ_INSERT_TAIL(TAILQ_HEAD *head, struct TYPE *elm,
45 TAILQ_ENTRY NAME);
46
47 struct TYPE *TAILQ_LAST(TAILQ_HEAD *head, HEADNAME);
48
49 struct TYPE *TAILQ_NEXT(struct TYPE *elm, TAILQ_ENTRY NAME);
50
51 struct TYPE *TAILQ_PREV(struct TYPE *elm, HEADNAME, TAILQ_ENTRY NAME);
52
53 void TAILQ_REMOVE(TAILQ_HEAD *head, struct TYPE *elm, TAILQ_ENTRY NAME);
54
56 These macros define and operate on doubly linked tail queues.
57
58 In the macro definitions, TYPE is the name of a user defined structure,
59 that must contain a field of type TAILQ_ENTRY, named NAME. The argu‐
60 ment HEADNAME is the name of a user defined structure that must be de‐
61 clared using the macro TAILQ_HEAD().
62
63 A tail queue is headed by a structure defined by the TAILQ_HEAD()
64 macro. This structure contains a pair of pointers, one to the first
65 element in the tail queue and the other to the last element in the tail
66 queue. The elements are doubly linked so that an arbitrary element can
67 be removed without traversing the tail queue. New elements can be
68 added to the tail queue after an existing element, before an existing
69 element, at the head of the tail queue, or at the end of the tail
70 queue. A TAILQ_HEAD structure is declared as follows:
71
72 TAILQ_HEAD(HEADNAME, TYPE) head;
73
74 where struct HEADNAME is the structure to be defined, and struct TYPE
75 is the type of the elements to be linked into the tail queue. A
76 pointer to the head of the tail queue can later be declared as:
77
78 struct HEADNAME *headp;
79
80 (The names head and headp are user selectable.)
81
82 The macro TAILQ_HEAD_INITIALIZER() evaluates to an initializer for the
83 tail queue head.
84
85 The macro TAILQ_CONCAT() concatenates the tail queue headed by head2
86 onto the end of the one headed by head1 removing all entries from the
87 former.
88
89 The macro TAILQ_EMPTY() evaluates to true if there are no items on the
90 tail queue.
91
92 The macro TAILQ_ENTRY() declares a structure that connects the elements
93 in the tail queue.
94
95 The macro TAILQ_FIRST() returns the first item on the tail queue or
96 NULL if the tail queue is empty.
97
98 The macro TAILQ_FOREACH() traverses the tail queue referenced by head
99 in the forward direction, assigning each element in turn to var. var
100 is set to NULL if the loop completes normally, or if there were no ele‐
101 ments.
102
103 The macro TAILQ_FOREACH_REVERSE() traverses the tail queue referenced
104 by head in the reverse direction, assigning each element in turn to
105 var.
106
107 The macro TAILQ_INIT() initializes the tail queue referenced by head.
108
109 The macro TAILQ_INSERT_HEAD() inserts the new element elm at the head
110 of the tail queue.
111
112 The macro TAILQ_INSERT_TAIL() inserts the new element elm at the end of
113 the tail queue.
114
115 The macro TAILQ_INSERT_AFTER() inserts the new element elm after the
116 element listelm.
117
118 The macro TAILQ_INSERT_BEFORE() inserts the new element elm before the
119 element listelm.
120
121 The macro TAILQ_LAST() returns the last item on the tail queue. If the
122 tail queue is empty the return value is NULL.
123
124 The macro TAILQ_NEXT() returns the next item on the tail queue, or NULL
125 if this item is the last.
126
127 The macro TAILQ_PREV() returns the previous item on the tail queue, or
128 NULL if this item is the first.
129
130 The macro TAILQ_REMOVE() removes the element elm from the tail queue.
131
133 TAILQ_EMPTY() returns nonzero if the queue is empty, and zero if the
134 queue contains at least one entry.
135
136 TAILQ_FIRST(), TAILQ_LAST(), TAILQ_NEXT(), and TAILQ_PREV() return a
137 pointer to the first, last, next or previous TYPE structure, respec‐
138 tively.
139
140 TAILQ_HEAD_INITIALIZER() returns an initializer that can be assigned to
141 the queue head.
142
144 Not in POSIX.1, POSIX.1-2001 or POSIX.1-2008. Present on the BSDs.
145 (TAILQ functions first appeared in 4.4BSD).
146
148 The macros TAILQ_FOREACH() and TAILQ_FOREACH_REVERSE() don't allow var
149 to be removed or freed within the loop, as it would interfere with the
150 traversal. The macros TAILQ_FOREACH_SAFE() and TAILQ_FOREACH_RE‐
151 VERSE_SAFE(), which are present on the BSDs but are not present in
152 glibc, fix this limitation by allowing var to safely be removed from
153 the list and freed from within the loop without interfering with the
154 traversal.
155
157 #include <stddef.h>
158 #include <stdio.h>
159 #include <stdlib.h>
160 #include <sys/queue.h>
161
162 struct entry {
163 int data;
164 TAILQ_ENTRY(entry) entries; /* Tail queue. */
165 };
166
167 TAILQ_HEAD(tailhead, entry);
168
169 int
170 main(void)
171 {
172 struct entry *n1, *n2, *n3, *np;
173 struct tailhead head; /* Tail queue head. */
174 int i;
175
176 TAILQ_INIT(&head); /* Initialize the queue. */
177
178 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
179 TAILQ_INSERT_HEAD(&head, n1, entries);
180
181 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
182 TAILQ_INSERT_TAIL(&head, n1, entries);
183
184 n2 = malloc(sizeof(struct entry)); /* Insert after. */
185 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
186
187 n3 = malloc(sizeof(struct entry)); /* Insert before. */
188 TAILQ_INSERT_BEFORE(n2, n3, entries);
189
190 TAILQ_REMOVE(&head, n2, entries); /* Deletion. */
191 free(n2);
192 /* Forward traversal. */
193 i = 0;
194 TAILQ_FOREACH(np, &head, entries)
195 np->data = i++;
196 /* Reverse traversal. */
197 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
198 printf("%i\n", np->data);
199 /* TailQ Deletion. */
200 n1 = TAILQ_FIRST(&head);
201 while (n1 != NULL) {
202 n2 = TAILQ_NEXT(n1, entries);
203 free(n1);
204 n1 = n2;
205 }
206 TAILQ_INIT(&head);
207
208 exit(EXIT_SUCCESS);
209 }
210
212 insque(3), queue(7)
213
215 This page is part of release 5.10 of the Linux man-pages project. A
216 description of the project, information about reporting bugs, and the
217 latest version of this page, can be found at
218 https://www.kernel.org/doc/man-pages/.
219
220
221
222GNU 2020-12-21 TAILQ(3)