1STAILQ(3) Linux Programmer's Manual STAILQ(3)
2
6 SIMPLEQ_EMPTY, SIMPLEQ_ENTRY, SIMPLEQ_FIRST, SIMPLEQ_FOREACH, SIM‐
7 PLEQ_HEAD, SIMPLEQ_HEAD_INITIALIZER, SIMPLEQ_INIT, SIMPLEQ_INSERT_AF‐
8 TER, SIMPLEQ_INSERT_HEAD, SIMPLEQ_INSERT_TAIL, SIMPLEQ_NEXT, SIM‐
9 PLEQ_REMOVE, SIMPLEQ_REMOVE_HEAD, STAILQ_CONCAT, STAILQ_EMPTY,
10 STAILQ_ENTRY, STAILQ_FIRST, STAILQ_FOREACH, STAILQ_HEAD,
11 STAILQ_HEAD_INITIALIZER, STAILQ_INIT, STAILQ_INSERT_AFTER, STAILQ_IN‐
12 SERT_HEAD, STAILQ_INSERT_TAIL, STAILQ_NEXT, STAILQ_REMOVE, STAILQ_RE‐
13 MOVE_HEAD, - implementation of a singly linked tail queue
14
16 #include <sys/queue.h>
17 STAILQ_ENTRY(TYPE);
19 STAILQ_HEAD(HEADNAME, TYPE);
21 STAILQ_HEAD STAILQ_HEAD_INITIALIZER(STAILQ_HEAD head);
22 void STAILQ_INIT(STAILQ_HEAD *head);
23 int STAILQ_EMPTY(STAILQ_HEAD *head);
25 void STAILQ_INSERT_HEAD(STAILQ_HEAD *head,
27 struct TYPE *elm, STAILQ_ENTRY NAME);
28 void STAILQ_INSERT_TAIL(STAILQ_HEAD *head,
29 struct TYPE *elm, STAILQ_ENTRY NAME);
30 void STAILQ_INSERT_AFTER(STAILQ_HEAD *head, struct TYPE *listelm,
31 struct TYPE *elm, STAILQ_ENTRY NAME);
32 struct TYPE *STAILQ_FIRST(STAILQ_HEAD *head);
34 struct TYPE *STAILQ_NEXT(struct TYPE *elm, STAILQ_ENTRY NAME);
35 STAILQ_FOREACH(struct TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME);
37 void STAILQ_REMOVE(STAILQ_HEAD *head, struct TYPE *elm, TYPE,
39 STAILQ_ENTRY NAME);
40 void STAILQ_REMOVE_HEAD(STAILQ_HEAD *head,
41 STAILQ_ENTRY NAME);
42 void STAILQ_CONCAT(STAILQ_HEAD *head1, STAILQ_HEAD *head2);
44 Note: Identical macros prefixed with SIMPLEQ instead of STAILQ exist;
45 see NOTES.
46
48 These macros define and operate on singly linked tail queues.
49 In the macro definitions, TYPE is the name of a user-defined structure,
51 that must contain a field of type STAILQ_ENTRY, named NAME. The argu‐
52 ment HEADNAME is the name of a user-defined structure that must be de‐
53 clared using the macro STAILQ_HEAD().
54 Creation
56 A singly linked tail queue is headed by a structure defined by the
57 STAILQ_HEAD() macro. This structure contains a pair of pointers, one
58 to the first element in the tail queue and the other to the last ele‐
59 ment in the tail queue. The elements are singly linked for minimum
60 space and pointer manipulation overhead at the expense of O(n) removal
61 for arbitrary elements. New elements can be added to the tail queue
62 after an existing element, at the head of the tail queue, or at the end
63 of the tail queue. A STAILQ_HEAD structure is declared as follows:
64 STAILQ_HEAD(HEADNAME, TYPE) head;
66 where struct HEADNAME is the structure to be defined, and struct TYPE
68 is the type of the elements to be linked into the tail queue. A
69 pointer to the head of the tail queue can later be declared as:
70 struct HEADNAME *headp;
72 (The names head and headp are user selectable.)
74 STAILQ_ENTRY() declares a structure that connects the elements in the
76 tail queue.
77 STAILQ_HEAD_INITIALIZER() evaluates to an initializer for the tail
79 queue head.
80 STAILQ_INIT() initializes the tail queue referenced by head.
82 STAILQ_EMPTY() evaluates to true if there are no items on the tail
84 queue.
85 Insertion
87 STAILQ_INSERT_HEAD() inserts the new element elm at the head of the
88 tail queue.
89 STAILQ_INSERT_TAIL() inserts the new element elm at the end of the tail
91 queue.
92 STAILQ_INSERT_AFTER() inserts the new element elm after the element
94 listelm.
95 Traversal
97 STAILQ_FIRST() returns the first item on the tail queue or NULL if the
98 tail queue is empty.
99 STAILQ_NEXT() returns the next item on the tail queue, or NULL this
101 item is the last.
102 STAILQ_FOREACH() traverses the tail queue referenced by head in the
104 forward direction, assigning each element in turn to var.
105 Removal
107 STAILQ_REMOVE() removes the element elm from the tail queue.
108 STAILQ_REMOVE_HEAD() removes the element at the head of the tail queue.
110 For optimum efficiency, elements being removed from the head of the
111 tail queue should use this macro explicitly rather than the generic
112 STAILQ_REMOVE() macro.
113 Other features
115 STAILQ_CONCAT() concatenates the tail queue headed by head2 onto the
116 end of the one headed by head1 removing all entries from the former.
117
119 STAILQ_EMPTY() returns nonzero if the queue is empty, and zero if the
120 queue contains at least one entry.
121 STAILQ_FIRST(), and STAILQ_NEXT() return a pointer to the first or next
123 TYPE structure, respectively.
124 STAILQ_HEAD_INITIALIZER() returns an initializer that can be assigned
126 to the queue head.
127
129 Not in POSIX.1, POSIX.1-2001, or POSIX.1-2008. Present on the BSDs
130 (STAILQ macros first appeared in 4.4BSD).
131
133 STAILQ_FOREACH() doesn't allow var to be removed or freed within the
134 loop, as it would interfere with the traversal. STAILQ_FOREACH_SAFE(),
135 which is present on the BSDs but is not present in glibc, fixes this
136 limitation by allowing var to safely be removed from the list and freed
137 from within the loop without interfering with the traversal.
138
140 Some BSDs provide SIMPLEQ instead of STAILQ. They are identical, but
141 for historical reasons they were named differently on different BSDs.
142 STAILQ originated on FreeBSD, and SIMPLEQ originated on NetBSD. For
143 compatibility reasons, some systems provide both sets of macros. Glibc
144 provides both STAILQ and SIMPLEQ, which are identical except for a
145 missing SIMPLEQ equivalent to STAILQ_CONCAT().
146
148 #include <stddef.h>
149 #include <stdio.h>
150 #include <stdlib.h>
151 #include <sys/queue.h>
152 struct entry {
154 int data;
155 STAILQ_ENTRY(entry) entries; /* Singly linked tail queue */
156 };
157 STAILQ_HEAD(stailhead, entry);
159 int
161 main(void)
162 {
163 struct entry *n1, *n2, *n3, *np;
164 struct stailhead head; /* Singly linked tail queue
165 head */
166 STAILQ_INIT(&head); /* Initialize the queue */
168 n1 = malloc(sizeof(struct entry)); /* Insert at the head */
170 STAILQ_INSERT_HEAD(&head, n1, entries);
171 n1 = malloc(sizeof(struct entry)); /* Insert at the tail */
173 STAILQ_INSERT_TAIL(&head, n1, entries);
174 n2 = malloc(sizeof(struct entry)); /* Insert after */
176 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
177 STAILQ_REMOVE(&head, n2, entry, entries); /* Deletion */
179 free(n2);
180 n3 = STAILQ_FIRST(&head);
182 STAILQ_REMOVE_HEAD(&head, entries); /* Deletion from the head */
183 free(n3);
184 n1 = STAILQ_FIRST(&head);
186 n1->data = 0;
187 for (int i = 1; i < 5; i++) {
188 n1 = malloc(sizeof(struct entry));
189 STAILQ_INSERT_HEAD(&head, n1, entries);
190 n1->data = i;
191 }
192 /* Forward traversal */
193 STAILQ_FOREACH(np, &head, entries)
194 printf("%i\n", np->data);
195 /* TailQ deletion */
196 n1 = STAILQ_FIRST(&head);
197 while (n1 != NULL) {
198 n2 = STAILQ_NEXT(n1, entries);
199 free(n1);
200 n1 = n2;
201 }
202 STAILQ_INIT(&head);
203 exit(EXIT_SUCCESS);
205 }
206
208 insque(3), queue(7)
209
211 This page is part of release 5.12 of the Linux man-pages project. A
212 description of the project, information about reporting bugs, and the
213 latest version of this page, can be found at
214 https://www.kernel.org/doc/man-pages/.
215GNU 2021-03-22 STAILQ(3)