1QUEUE(3) Linux Programmer's Manual QUEUE(3)
2
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 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 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 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 * 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 Lists are the simplest of the three data structures and support only
61 the above functionality.
62 Tail queues add the following functionality:
64 * Entries can be added at the end of a list.
66 However:
68 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 Circular queues add the following functionality:
76 * 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 However:
82 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 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 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 LIST_HEAD(HEADNAME, TYPE) head;
106 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 struct HEADNAME *headp;
112 (The names head and headp are user selectable.)
114 The macro LIST_ENTRY declares a structure that connects the elements in
116 the list.
117 The macro LIST_INIT initializes the list referenced by head.
119 The macro LIST_INSERT_HEAD inserts the new element elm at the head of
121 the list.
122 The macro LIST_INSERT_AFTER inserts the new element elm after the ele‐
124 ment listelm.
125 The macro LIST_REMOVE removes the element elm from the list.
127 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 LIST_INIT(&head); /* Initialize the list. */
138 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
140 LIST_INSERT_HEAD(&head, n1, entries);
141 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 while (head.lh_first != NULL) /* Delete. */
149 LIST_REMOVE(head.lh_first, entries);
150 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 TAILQ_HEAD(HEADNAME, TYPE) head;
162 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 struct HEADNAME *headp;
168 (The names head and headp are user selectable.)
170 The macro TAILQ_ENTRY declares a structure that connects the elements
172 in the tail queue.
173 The macro TAILQ_INIT initializes the tail queue referenced by head.
175 The macro TAILQ_INSERT_HEAD inserts the new element elm at the head of
177 the tail queue.
178 The macro TAILQ_INSERT_TAIL inserts the new element elm at the end of
180 the tail queue.
181 The macro TAILQ_INSERT_AFTER inserts the new element elm after the ele‐
183 ment listelm.
184 The macro TAILQ_REMOVE removes the element elm from the tail queue.
186 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 TAILQ_INIT(&head); /* Initialize the queue. */
197 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
199 TAILQ_INSERT_HEAD(&head, n1, entries);
200 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
202 TAILQ_INSERT_TAIL(&head, n1, entries);
203 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 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 CIRCLEQ_HEAD(HEADNAME, TYPE) head;
224 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 struct HEADNAME *headp;
230 (The names head and headp are user selectable.)
232 The macro CIRCLEQ_ENTRY declares a structure that connects the elements
234 in the circular queue.
235 The macro CIRCLEQ_INIT initializes the circular queue referenced by
237 head.
238 The macro CIRCLEQ_INSERT_HEAD inserts the new element elm at the head
240 of the circular queue.
241 The macro CIRCLEQ_INSERT_TAIL inserts the new element elm at the end of
243 the circular queue.
244 The macro CIRCLEQ_INSERT_AFTER inserts the new element elm after the
246 element listelm.
247 The macro CIRCLEQ_INSERT_BEFORE inserts the new element elm before the
249 element listelm.
250 The macro CIRCLEQ_REMOVE removes the element elm from the circular
252 queue.
253 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 CIRCLEQ_INIT(&head); /* Initialize the circular queue. */
264 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
266 CIRCLEQ_INSERT_HEAD(&head, n1, entries);
267 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
269 CIRCLEQ_INSERT_TAIL(&head, n1, entries);
270 n2 = malloc(sizeof(struct entry)); /* Insert after. */
272 CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
273 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/.
295Linux 2007-12-28 QUEUE(3)