1STAILQ(3) Library Functions 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 Standard C library (libc, -lc)
17
19 #include <sys/queue.h>
20 STAILQ_ENTRY(TYPE);
22 STAILQ_HEAD(HEADNAME, TYPE);
24 STAILQ_HEAD STAILQ_HEAD_INITIALIZER(STAILQ_HEAD head);
25 void STAILQ_INIT(STAILQ_HEAD *head);
26 int STAILQ_EMPTY(STAILQ_HEAD *head);
28 void STAILQ_INSERT_HEAD(STAILQ_HEAD *head,
30 struct TYPE *elm, STAILQ_ENTRY NAME);
31 void STAILQ_INSERT_TAIL(STAILQ_HEAD *head,
32 struct TYPE *elm, STAILQ_ENTRY NAME);
33 void STAILQ_INSERT_AFTER(STAILQ_HEAD *head, struct TYPE *listelm,
34 struct TYPE *elm, STAILQ_ENTRY NAME);
35 struct TYPE *STAILQ_FIRST(STAILQ_HEAD *head);
37 struct TYPE *STAILQ_NEXT(struct TYPE *elm, STAILQ_ENTRY NAME);
38 STAILQ_FOREACH(struct TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME);
40 void STAILQ_REMOVE(STAILQ_HEAD *head, struct TYPE *elm, TYPE,
42 STAILQ_ENTRY NAME);
43 void STAILQ_REMOVE_HEAD(STAILQ_HEAD *head,
44 STAILQ_ENTRY NAME);
45 void STAILQ_CONCAT(STAILQ_HEAD *head1, STAILQ_HEAD *head2);
47 Note: Identical macros prefixed with SIMPLEQ instead of STAILQ exist;
48 see NOTES.
49
51 These macros define and operate on singly linked tail queues.
52 In the macro definitions, TYPE is the name of a user-defined structure,
54 that must contain a field of type STAILQ_ENTRY, named NAME. The argu‐
55 ment HEADNAME is the name of a user-defined structure that must be de‐
56 clared using the macro STAILQ_HEAD().
57 Creation
59 A singly linked tail queue is headed by a structure defined by the
60 STAILQ_HEAD() macro. This structure contains a pair of pointers, one
61 to the first element in the tail queue and the other to the last ele‐
62 ment in the tail queue. The elements are singly linked for minimum
63 space and pointer manipulation overhead at the expense of O(n) removal
64 for arbitrary elements. New elements can be added to the tail queue
65 after an existing element, at the head of the tail queue, or at the end
66 of the tail queue. A STAILQ_HEAD structure is declared as follows:
67 STAILQ_HEAD(HEADNAME, TYPE) head;
69 where struct HEADNAME is the structure to be defined, and struct TYPE
71 is the type of the elements to be linked into the tail queue. A
72 pointer to the head of the tail queue can later be declared as:
73 struct HEADNAME *headp;
75 (The names head and headp are user selectable.)
77 STAILQ_ENTRY() declares a structure that connects the elements in the
79 tail queue.
80 STAILQ_HEAD_INITIALIZER() evaluates to an initializer for the tail
82 queue head.
83 STAILQ_INIT() initializes the tail queue referenced by head.
85 STAILQ_EMPTY() evaluates to true if there are no items on the tail
87 queue.
88 Insertion
90 STAILQ_INSERT_HEAD() inserts the new element elm at the head of the
91 tail queue.
92 STAILQ_INSERT_TAIL() inserts the new element elm at the end of the tail
94 queue.
95 STAILQ_INSERT_AFTER() inserts the new element elm after the element
97 listelm.
98 Traversal
100 STAILQ_FIRST() returns the first item on the tail queue or NULL if the
101 tail queue is empty.
102 STAILQ_NEXT() returns the next item on the tail queue, or NULL this
104 item is the last.
105 STAILQ_FOREACH() traverses the tail queue referenced by head in the
107 forward direction, assigning each element in turn to var.
108 Removal
110 STAILQ_REMOVE() removes the element elm from the tail queue.
111 STAILQ_REMOVE_HEAD() removes the element at the head of the tail queue.
113 For optimum efficiency, elements being removed from the head of the
114 tail queue should use this macro explicitly rather than the generic
115 STAILQ_REMOVE() macro.
116 Other features
118 STAILQ_CONCAT() concatenates the tail queue headed by head2 onto the
119 end of the one headed by head1 removing all entries from the former.
120
122 STAILQ_EMPTY() returns nonzero if the queue is empty, and zero if the
123 queue contains at least one entry.
124 STAILQ_FIRST(), and STAILQ_NEXT() return a pointer to the first or next
126 TYPE structure, respectively.
127 STAILQ_HEAD_INITIALIZER() returns an initializer that can be assigned
129 to the queue head.
130
132 Some BSDs provide SIMPLEQ instead of STAILQ. They are identical, but
133 for historical reasons they were named differently on different BSDs.
134 STAILQ originated on FreeBSD, and SIMPLEQ originated on NetBSD. For
135 compatibility reasons, some systems provide both sets of macros. glibc
136 provides both STAILQ and SIMPLEQ, which are identical except for a
137 missing SIMPLEQ equivalent to STAILQ_CONCAT().
138
140 STAILQ_FOREACH() doesn't allow var to be removed or freed within the
141 loop, as it would interfere with the traversal. STAILQ_FOREACH_SAFE(),
142 which is present on the BSDs but is not present in glibc, fixes this
143 limitation by allowing var to safely be removed from the list and freed
144 from within the loop without interfering with the traversal.
145
147 BSD.
148
150 4.4BSD.
151
153 #include <stddef.h>
154 #include <stdio.h>
155 #include <stdlib.h>
156 #include <sys/queue.h>
157 struct entry {
159 int data;
160 STAILQ_ENTRY(entry) entries; /* Singly linked tail queue */
161 };
162 STAILQ_HEAD(stailhead, entry);
164 int
166 main(void)
167 {
168 struct entry *n1, *n2, *n3, *np;
169 struct stailhead head; /* Singly linked tail queue
170 head */
171 STAILQ_INIT(&head); /* Initialize the queue */
173 n1 = malloc(sizeof(struct entry)); /* Insert at the head */
175 STAILQ_INSERT_HEAD(&head, n1, entries);
176 n1 = malloc(sizeof(struct entry)); /* Insert at the tail */
178 STAILQ_INSERT_TAIL(&head, n1, entries);
179 n2 = malloc(sizeof(struct entry)); /* Insert after */
181 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
182 STAILQ_REMOVE(&head, n2, entry, entries); /* Deletion */
184 free(n2);
185 n3 = STAILQ_FIRST(&head);
187 STAILQ_REMOVE_HEAD(&head, entries); /* Deletion from the head */
188 free(n3);
189 n1 = STAILQ_FIRST(&head);
191 n1->data = 0;
192 for (unsigned int i = 1; i < 5; i++) {
193 n1 = malloc(sizeof(struct entry));
194 STAILQ_INSERT_HEAD(&head, n1, entries);
195 n1->data = i;
196 }
197 /* Forward traversal */
198 STAILQ_FOREACH(np, &head, entries)
199 printf("%i\n", np->data);
200 /* TailQ deletion */
201 n1 = STAILQ_FIRST(&head);
202 while (n1 != NULL) {
203 n2 = STAILQ_NEXT(n1, entries);
204 free(n1);
205 n1 = n2;
206 }
207 STAILQ_INIT(&head);
208 exit(EXIT_SUCCESS);
210 }
211
213 insque(3), queue(7)
214Linux man-pages 6.05 2023-05-03 STAILQ(3)