1QUEUE(3) BSD Library Functions Manual QUEUE(3)
2
4 LIST_ENTRY, LIST_HEAD, LIST_INIT, LIST_INSERT_AFTER, LIST_INSERT_HEAD,
5 LIST_REMOVE, TAILQ_ENTRY, TAILQ_HEAD, TAILQ_INIT, TAILQ_INSERT_AFTER,
6 TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, TAILQ_REMOVE, CIRCLEQ_ENTRY,
7 CIRCLEQ_HEAD, CIRCLEQ_INIT, CIRCLEQ_INSERT_AFTER, CIRCLEQ_INSERT_BEFORE,
8 CIRCLEQ_INSERT_HEAD, CIRCLEQ_INSERT_TAIL, CIRCLEQ_REMOVE — implementa‐
9 tions of lists, tail queues, and circular queues
10
12 #include <sys/queue.h>
13 LIST_ENTRY(TYPE);
15 LIST_HEAD(HEADNAME, TYPE);
17 LIST_INIT(LIST_HEAD *head);
19 LIST_INSERT_AFTER(LIST_ENTRY *listelm, TYPE *elm, LIST_ENTRY NAME);
21 LIST_INSERT_HEAD(LIST_HEAD *head, TYPE *elm, LIST_ENTRY NAME);
23 LIST_REMOVE(TYPE *elm, LIST_ENTRY NAME);
25 TAILQ_ENTRY(TYPE);
27 TAILQ_HEAD(HEADNAME, TYPE);
29 TAILQ_INIT(TAILQ_HEAD *head);
31 TAILQ_INSERT_AFTER(TAILQ_HEAD *head, TYPE *listelm, TYPE *elm,
33 TAILQ_ENTRY NAME);
34 TAILQ_INSERT_HEAD(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);
36 TAILQ_INSERT_TAIL(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);
38 TAILQ_REMOVE(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);
40 CIRCLEQ_ENTRY(TYPE);
42 CIRCLEQ_HEAD(HEADNAME, TYPE);
44 CIRCLEQ_INIT(CIRCLEQ_HEAD *head);
46 CIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *head, TYPE *listelm, TYPE *elm,
48 CIRCLEQ_ENTRY NAME);
49 CIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *head, TYPE *listelm, TYPE *elm,
51 CIRCLEQ_ENTRY NAME);
52 CIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *head, TYPE *elm, CIRCLEQ_ENTRY NAME);
54 CIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *head, TYPE *elm, CIRCLEQ_ENTRY NAME);
56 CIRCLEQ_REMOVE(CIRCLEQ_HEAD *head, TYPE *elm, CIRCLEQ_ENTRY NAME);
58
60 These macros define and operate on three types of data structures: lists,
61 tail queues, and circular queues. All three structures support the fol‐
62 lowing functionality:
63 1. Insertion of a new entry at the head of the list.
64 2. Insertion of a new entry after any element in the list.
65 3. Removal of any entry in the list.
66 4. Forward traversal through the list.
67 Lists are the simplest of the three data structures and support only the
69 above functionality.
70 Tail queues add the following functionality:
72 1. Entries can be added at the end of a list.
73 However:
74 1. All list insertions and removals must specify the head of the
75 list.
76 2. Each head entry requires two pointers rather than one.
77 3. Code size is about 15% greater and operations run about 20%
78 slower than lists.
79 Circular queues add the following functionality:
81 1. Entries can be added at the end of a list.
82 2. Entries can be added before another entry.
83 3. They may be traversed backwards, from tail to head.
84 However:
85 1. All list insertions and removals must specify the head of the
86 list.
87 2. Each head entry requires two pointers rather than one.
88 3. The termination condition for traversal is more complex.
89 4. Code size is about 40% greater and operations run about 45%
90 slower than lists.
91 In the macro definitions, TYPE is the name of a user defined structure,
93 that must contain a field of type LIST_ENTRY, TAILQ_ENTRY, or
94 CIRCLEQ_ENTRY, named NAME. The argument HEADNAME is the name of a user
95 defined structure that must be declared using the macros LIST_HEAD,
96 TAILQ_HEAD, or CIRCLEQ_HEAD. See the examples below for further explana‐
97 tion of how these macros are used.
98
100 A list is headed by a structure defined by the LIST_HEAD macro. This
101 structure contains a single pointer to the first element on the list.
102 The elements are doubly linked so that an arbitrary element can be
103 removed without traversing the list. New elements can be added to the
104 list after an existing element or at the head of the list. A LIST_HEAD
105 structure is declared as follows:
106 LIST_HEAD(HEADNAME, TYPE) head;
108 where HEADNAME is the name of the structure to be defined, and TYPE is
110 the type of the elements to be linked into the list. A pointer to the
111 head of the list can later be declared as:
112 struct HEADNAME *headp;
114 (The names head and headp are user selectable.)
116 The macro LIST_ENTRY declares a structure that connects the elements in
118 the list.
119 The macro LIST_INIT initializes the list referenced by head.
121 The macro LIST_INSERT_HEAD inserts the new element elm at the head of the
123 list.
124 The macro LIST_INSERT_AFTER inserts the new element elm after the element
126 listelm.
127 The macro LIST_REMOVE removes the element elm from the list.
129
131 LIST_HEAD(listhead, entry) head;
132 struct listhead *headp; /* List head. */
133 struct entry {
134 ...
135 LIST_ENTRY(entry) entries; /* List. */
136 ...
137 } *n1, *n2, *np;
138 LIST_INIT(&head); /* Initialize the list. */
140 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
142 LIST_INSERT_HEAD(&head, n1, entries);
143 n2 = malloc(sizeof(struct entry)); /* Insert after. */
145 LIST_INSERT_AFTER(n1, n2, entries);
146 /* Forward traversal. */
147 for (np = head.lh_first; np != NULL; np = np->entries.le_next)
148 np-> ...
149 while (head.lh_first != NULL) /* Delete. */
151 LIST_REMOVE(head.lh_first, entries);
152
154 A tail queue is headed by a structure defined by the TAILQ_HEAD macro.
155 This structure contains a pair of pointers, one to the first element in
156 the tail queue and the other to the last element in the tail queue. The
157 elements are doubly linked so that an arbitrary element can be removed
158 without traversing the tail queue. New elements can be added to the tail
159 queue after an existing element, at the head of the tail queue, or at the
160 end of the tail queue. A TAILQ_HEAD structure is declared as follows:
161 TAILQ_HEAD(HEADNAME, TYPE) head;
163 where HEADNAME is the name of the structure to be defined, and TYPE is
165 the type of the elements to be linked into the tail queue. A pointer to
166 the head of the tail queue can later be declared as:
167 struct HEADNAME *headp;
169 (The names head and headp are user selectable.)
171 The macro TAILQ_ENTRY declares a structure that connects the elements in
173 the tail queue.
174 The macro TAILQ_INIT initializes the tail queue referenced by head.
176 The macro TAILQ_INSERT_HEAD inserts the new element elm at the head of
178 the tail queue.
179 The macro TAILQ_INSERT_TAIL inserts the new element elm at the end of the
181 tail queue.
182 The macro TAILQ_INSERT_AFTER inserts the new element elm after the ele‐
184 ment listelm.
185 The macro TAILQ_REMOVE removes the element elm from the tail queue.
187
189 TAILQ_HEAD(tailhead, entry) head;
190 struct tailhead *headp; /* Tail queue head. */
191 struct entry {
192 ...
193 TAILQ_ENTRY(entry) entries; /* Tail queue. */
194 ...
195 } *n1, *n2, *np;
196 TAILQ_INIT(&head); /* Initialize the queue. */
198 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
200 TAILQ_INSERT_HEAD(&head, n1, entries);
201 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
203 TAILQ_INSERT_TAIL(&head, n1, entries);
204 n2 = malloc(sizeof(struct entry)); /* Insert after. */
206 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
207 /* Forward traversal. */
208 for (np = head.tqh_first; np != NULL; np = np->entries.tqe_next)
209 np-> ...
210 /* Delete. */
211 while (head.tqh_first != NULL)
212 TAILQ_REMOVE(&head, head.tqh_first, entries);
213
215 A circular queue is headed by a structure defined by the CIRCLEQ_HEAD
216 macro. This structure contains a pair of pointers, one to the first ele‐
217 ment in the circular queue and the other to the last element in the cir‐
218 cular queue. The elements are doubly linked so that an arbitrary element
219 can be removed without traversing the queue. New elements can be added
220 to the queue after an existing element, before an existing element, at
221 the head of the queue, or at the end of the queue. A CIRCLEQ_HEAD struc‐
222 ture is declared as follows:
223 CIRCLEQ_HEAD(HEADNAME, TYPE) head;
225 where HEADNAME is the name of the structure to be defined, and TYPE is
227 the type of the elements to be linked into the circular queue. A pointer
228 to the head of the circular queue can later be declared as:
229 struct HEADNAME *headp;
231 (The names head and headp are user selectable.)
233 The macro CIRCLEQ_ENTRY declares a structure that connects the elements
235 in the circular queue.
236 The macro CIRCLEQ_INIT initializes the circular queue referenced by head.
238 The macro CIRCLEQ_INSERT_HEAD inserts the new element elm at the head of
240 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 ele‐
246 ment 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 queue.
252
254 CIRCLEQ_HEAD(circleq, entry) head;
255 struct circleq *headp; /* Circular queue head. */
256 struct entry {
257 ...
258 CIRCLEQ_ENTRY(entry) entries; /* Circular queue. */
259 ...
260 } *n1, *n2, *np;
261 CIRCLEQ_INIT(&head); /* Initialize the circular queue. */
263 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
265 CIRCLEQ_INSERT_HEAD(&head, n1, entries);
266 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
268 CIRCLEQ_INSERT_TAIL(&head, n1, entries);
269 n2 = malloc(sizeof(struct entry)); /* Insert after. */
271 CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
272 n2 = malloc(sizeof(struct entry)); /* Insert before. */
274 CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
275 /* Forward traversal. */
276 for (np = head.cqh_first; np != (void *)&head; np = np->entries.cqe_next)
277 np-> ...
278 /* Reverse traversal. */
279 for (np = head.cqh_last; np != (void *)&head; np = np->entries.cqe_prev)
280 np-> ...
281 /* Delete. */
282 while (head.cqh_first != (void *)&head)
283 CIRCLEQ_REMOVE(&head, head.cqh_first, entries);
284
286 Not in POSIX.1-2001. Present on the BSDs. The queue functions first
287 appeared in 4.4BSD.
2884BSD January 24, 1994 4BSD