1QUEUE(3) Linux Programmer's Manual QUEUE(3)
2
3
4
6 LIST_ENTRY, LIST_HEAD, LIST_INIT, LIST_INSERT_AFTER, LIST_INSERT_HEAD,
7 LIST_REMOVE, TAILQ_ENTRY, TAILQ_HEAD, TAILQ_INIT, TAILQ_INSERT_AFTER,
8 TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, TAILQ_REMOVE, CIRCLEQ_ENTRY, CIR‐
9 CLEQ_HEAD, CIRCLEQ_INIT, CIRCLEQ_INSERT_AFTER, CIRCLEQ_INSERT_BEFORE,
10 CIRCLEQ_INSERT_HEAD, CIRCLEQ_INSERT_TAIL, CIRCLEQ_REMOVE - implementa‐
11 tions of lists, tail queues, and circular queues
12
14 #include <sys/queue.h>
15
16 LIST_ENTRY(TYPE);
17 LIST_HEAD(HEADNAME, TYPE);
18 LIST_INIT(LIST_HEAD *head);
19 LIST_INSERT_AFTER(LIST_ENTRY *listelm,
20 TYPE *elm, LIST_ENTRY NAME);
21 LIST_INSERT_HEAD(LIST_HEAD *head,
22 TYPE *elm, LIST_ENTRY NAME);
23 LIST_REMOVE(TYPE *elm, LIST_ENTRY NAME);
24
25 TAILQ_ENTRY(TYPE);
26 TAILQ_HEAD(HEADNAME, TYPE);
27 TAILQ_INIT(TAILQ_HEAD *head);
28 TAILQ_INSERT_AFTER(TAILQ_HEAD *head, TYPE *listelm,
29 TYPE *elm, TAILQ_ENTRY NAME);
30 TAILQ_INSERT_HEAD(TAILQ_HEAD *head,
31 TYPE *elm, TAILQ_ENTRY NAME);
32 TAILQ_INSERT_TAIL(TAILQ_HEAD *head,
33 TYPE *elm, TAILQ_ENTRY NAME);
34 TAILQ_REMOVE(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);
35
36 CIRCLEQ_ENTRY(TYPE);
37 CIRCLEQ_HEAD(HEADNAME, TYPE);
38 CIRCLEQ_INIT(CIRCLEQ_HEAD *head);
39 CIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *head, TYPE *listelm,
40 TYPE *elm, CIRCLEQ_ENTRY NAME);
41 CIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *head, TYPE *listelm,
42 TYPE *elm, CIRCLEQ_ENTRY NAME);
43 CIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *head,
44 TYPE *elm, CIRCLEQ_ENTRY NAME);
45 CIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *head,
46 TYPE *elm, CIRCLEQ_ENTRY NAME);
47 CIRCLEQ_REMOVE(CIRCLEQ_HEAD *head,
48 TYPE *elm, CIRCLEQ_ENTRY NAME);
49
51 These macros define and operate on three types of data structures:
52 lists, tail queues, and circular queues. All three structures support
53 the following functionality:
54
55 * Insertion of a new entry at the head of the list.
56 * Insertion of a new entry after any element in the list.
57 * Removal of any entry in the list.
58 * Forward traversal through the list.
59
60 Lists are the simplest of the three data structures and support only
61 the above functionality.
62
63 Tail queues add the following functionality:
64
65 * Entries can be added at the end of a list.
66
67 However:
68
69 1. All list insertions and removals must specify the head of the
70 list.
71 2. Each head entry requires two pointers rather than one.
72 3. Code size is about 15% greater and operations run about 20%
73 slower than lists.
74
75 Circular queues add the following functionality:
76
77 * Entries can be added at the end of a list.
78 * Entries can be added before another entry.
79 * They may be traversed backward, from tail to head.
80
81 However:
82
83 1. All list insertions and removals must specify the head of the
84 list.
85 2. Each head entry requires two pointers rather than one.
86 3. The termination condition for traversal is more complex.
87 4. Code size is about 40% greater and operations run about 45%
88 slower than lists.
89
90 In the macro definitions, TYPE is the name of a user-defined structure,
91 that must contain a field of type LIST_ENTRY, TAILQ_ENTRY, or CIR‐
92 CLEQ_ENTRY, named NAME. The argument HEADNAME is the name of a user-
93 defined structure that must be declared using the macros LIST_HEAD,
94 TAILQ_HEAD, or CIRCLEQ_HEAD. See the examples below for further expla‐
95 nation of how these macros are used.
96
97 Lists
98 A list is headed by a structure defined by the LIST_HEAD macro. This
99 structure contains a single pointer to the first element on the list.
100 The elements are doubly linked so that an arbitrary element can be
101 removed without traversing the list. New elements can be added to the
102 list after an existing element or at the head of the list. A LIST_HEAD
103 structure is declared as follows:
104
105 LIST_HEAD(HEADNAME, TYPE) head;
106
107 where HEADNAME is the name of the structure to be defined, and TYPE is
108 the type of the elements to be linked into the list. A pointer to the
109 head of the list can later be declared as:
110
111 struct HEADNAME *headp;
112
113 (The names head and headp are user selectable.)
114
115 The macro LIST_ENTRY declares a structure that connects the elements in
116 the list.
117
118 The macro LIST_INIT initializes the list referenced by head.
119
120 The macro LIST_INSERT_HEAD inserts the new element elm at the head of
121 the list.
122
123 The macro LIST_INSERT_AFTER inserts the new element elm after the ele‐
124 ment listelm.
125
126 The macro LIST_REMOVE removes the element elm from the list.
127
128 List example
129 LIST_HEAD(listhead, entry) head;
130 struct listhead *headp; /* List head. */
131 struct entry {
132 ...
133 LIST_ENTRY(entry) entries; /* List. */
134 ...
135 } *n1, *n2, *np;
136
137 LIST_INIT(&head); /* Initialize the list. */
138
139 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
140 LIST_INSERT_HEAD(&head, n1, entries);
141
142 n2 = malloc(sizeof(struct entry)); /* Insert after. */
143 LIST_INSERT_AFTER(n1, n2, entries);
144 /* Forward traversal. */
145 for (np = head.lh_first; np != NULL; np = np->entries.le_next)
146 np-> ...
147
148 while (head.lh_first != NULL) /* Delete. */
149 LIST_REMOVE(head.lh_first, entries);
150
151 Tail queues
152 A tail queue is headed by a structure defined by the TAILQ_HEAD macro.
153 This structure contains a pair of pointers, one to the first element in
154 the tail queue and the other to the last element in the tail queue.
155 The elements are doubly linked so that an arbitrary element can be
156 removed without traversing the tail queue. New elements can be added
157 to the tail queue after an existing element, at the head of the tail
158 queue, or at the end of the tail queue. A TAILQ_HEAD structure is
159 declared as follows:
160
161 TAILQ_HEAD(HEADNAME, TYPE) head;
162
163 where HEADNAME is the name of the structure to be defined, and TYPE is
164 the type of the elements to be linked into the tail queue. A pointer
165 to the head of the tail queue can later be declared as:
166
167 struct HEADNAME *headp;
168
169 (The names head and headp are user selectable.)
170
171 The macro TAILQ_ENTRY declares a structure that connects the elements
172 in the tail queue.
173
174 The macro TAILQ_INIT initializes the tail queue referenced by head.
175
176 The macro TAILQ_INSERT_HEAD inserts the new element elm at the head of
177 the tail queue.
178
179 The macro TAILQ_INSERT_TAIL inserts the new element elm at the end of
180 the tail queue.
181
182 The macro TAILQ_INSERT_AFTER inserts the new element elm after the ele‐
183 ment listelm.
184
185 The macro TAILQ_REMOVE removes the element elm from the tail queue.
186
187 Tail queue example
188 TAILQ_HEAD(tailhead, entry) head;
189 struct tailhead *headp; /* Tail queue head. */
190 struct entry {
191 ...
192 TAILQ_ENTRY(entry) entries; /* Tail queue. */
193 ...
194 } *n1, *n2, *np;
195
196 TAILQ_INIT(&head); /* Initialize the queue. */
197
198 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
199 TAILQ_INSERT_HEAD(&head, n1, entries);
200
201 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
202 TAILQ_INSERT_TAIL(&head, n1, entries);
203
204 n2 = malloc(sizeof(struct entry)); /* Insert after. */
205 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
206 /* Forward traversal. */
207 for (np = head.tqh_first; np != NULL; np = np->entries.tqe_next)
208 np-> ...
209 /* Delete. */
210 while (head.tqh_first != NULL)
211 TAILQ_REMOVE(&head, head.tqh_first, entries);
212
213 Circular queues
214 A circular queue is headed by a structure defined by the CIRCLEQ_HEAD
215 macro. This structure contains a pair of pointers, one to the first
216 element in the circular queue and the other to the last element in the
217 circular queue. The elements are doubly linked so that an arbitrary
218 element can be removed without traversing the queue. New elements can
219 be added to the queue after an existing element, before an existing
220 element, at the head of the queue, or at the end of the queue. A CIR‐
221 CLEQ_HEAD structure is declared as follows:
222
223 CIRCLEQ_HEAD(HEADNAME, TYPE) head;
224
225 where HEADNAME is the name of the structure to be defined, and TYPE is
226 the type of the elements to be linked into the circular queue. A
227 pointer to the head of the circular queue can later be declared as:
228
229 struct HEADNAME *headp;
230
231 (The names head and headp are user selectable.)
232
233 The macro CIRCLEQ_ENTRY declares a structure that connects the elements
234 in the circular queue.
235
236 The macro CIRCLEQ_INIT initializes the circular queue referenced by
237 head.
238
239 The macro CIRCLEQ_INSERT_HEAD inserts the new element elm at the head
240 of the circular queue.
241
242 The macro CIRCLEQ_INSERT_TAIL inserts the new element elm at the end of
243 the circular queue.
244
245 The macro CIRCLEQ_INSERT_AFTER inserts the new element elm after the
246 element listelm.
247
248 The macro CIRCLEQ_INSERT_BEFORE inserts the new element elm before the
249 element listelm.
250
251 The macro CIRCLEQ_REMOVE removes the element elm from the circular
252 queue.
253
254 Circular queue example
255 CIRCLEQ_HEAD(circleq, entry) head;
256 struct circleq *headp; /* Circular queue head. */
257 struct entry {
258 ...
259 CIRCLEQ_ENTRY(entry) entries; /* Circular queue. */
260 ...
261 } *n1, *n2, *np;
262
263 CIRCLEQ_INIT(&head); /* Initialize the circular queue. */
264
265 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
266 CIRCLEQ_INSERT_HEAD(&head, n1, entries);
267
268 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
269 CIRCLEQ_INSERT_TAIL(&head, n1, entries);
270
271 n2 = malloc(sizeof(struct entry)); /* Insert after. */
272 CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
273
274 n2 = malloc(sizeof(struct entry)); /* Insert before. */
275 CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
276 /* Forward traversal. */
277 for (np = head.cqh_first; np != (void *)&head;
278 np = np->entries.cqe_next)
279 np-> ...
280 /* Reverse traversal. */
281 for (np = head.cqh_last; np != (void *)&head; np = np->entries.cqe_prev)
282 np-> ...
283 /* Delete. */
284 while (head.cqh_first != (void *)&head)
285 CIRCLEQ_REMOVE(&head, head.cqh_first, entries);
286
288 Not in POSIX.1-2001. Present on the BSDs. The queue functions first
289 appeared in 4.4BSD.
290
292 This page is part of release 3.53 of the Linux man-pages project. A
293 description of the project, and information about reporting bugs, can
294 be found at http://www.kernel.org/doc/man-pages/.
295
296
297
298Linux 2007-12-28 QUEUE(3)