2 .\" The Regents of the University of California. All rights reserved.
3 .\" and Copyright (c) 2020 by Alejandro Colomar <alx@kernel.org>
5 .\" SPDX-License-Identifier: BSD-3-Clause
8 .TH SLIST 3 (date) "Linux man-pages (unreleased)"
14 .\"SLIST_FOREACH_FROM,
15 .\"SLIST_FOREACH_FROM_SAFE,
16 .\"SLIST_FOREACH_SAFE,
18 SLIST_HEAD_INITIALIZER,
24 .\"SLIST_REMOVE_AFTER,
27 \- implementation of a singly linked list
30 .RI ( libc ", " \-lc )
33 .B #include <sys/queue.h>
37 .B SLIST_HEAD(HEADNAME, TYPE);
38 .BI "SLIST_HEAD SLIST_HEAD_INITIALIZER(SLIST_HEAD " head );
39 .BI "void SLIST_INIT(SLIST_HEAD *" head );
41 .BI "int SLIST_EMPTY(SLIST_HEAD *" head );
43 .BI "void SLIST_INSERT_HEAD(SLIST_HEAD *" head ,
44 .BI " struct TYPE *" elm ", SLIST_ENTRY " NAME );
45 .BI "void SLIST_INSERT_AFTER(struct TYPE *" listelm ,
46 .BI " struct TYPE *" elm ", SLIST_ENTRY " NAME );
48 .BI "struct TYPE *SLIST_FIRST(SLIST_HEAD *" head );
49 .BI "struct TYPE *SLIST_NEXT(struct TYPE *" elm ", SLIST_ENTRY " NAME );
51 .BI "SLIST_FOREACH(struct TYPE *" var ", SLIST_HEAD *" head ", SLIST_ENTRY " NAME );
52 .\" .BI "SLIST_FOREACH_FROM(struct TYPE *" var ", SLIST_HEAD *" head ,
53 .\" .BI " SLIST_ENTRY " NAME );
55 .\" .BI "SLIST_FOREACH_SAFE(struct TYPE *" var ", SLIST_HEAD *" head ,
56 .\" .BI " SLIST_ENTRY " NAME ", struct TYPE *" temp_var );
57 .\" .BI "SLIST_FOREACH_FROM_SAFE(struct TYPE *" var ", SLIST_HEAD *" head ,
58 .\" .BI " SLIST_ENTRY " NAME ", struct TYPE *" temp_var );
60 .BI "void SLIST_REMOVE(SLIST_HEAD *" head ", struct TYPE *" elm ,
61 .BI " SLIST_ENTRY " NAME );
62 .BI "void SLIST_REMOVE_HEAD(SLIST_HEAD *" head ,
63 .BI " SLIST_ENTRY " NAME );
64 .\" .BI "void SLIST_REMOVE_AFTER(struct TYPE *" elm ,
65 .\" .BI " SLIST_ENTRY " NAME );
67 .\" .BI "void SLIST_SWAP(SLIST_HEAD *" head1 ", SLIST_HEAD *" head2 ,
68 .\" .BI " SLIST_ENTRY " NAME );
71 These macros define and operate on doubly linked lists.
73 In the macro definitions,
75 is the name of a user-defined structure,
76 that must contain a field of type
82 is the name of a user-defined structure
83 that must be declared using the macro
86 A singly linked list is headed by a structure defined by the
89 This structure contains a single pointer to the first element on the list.
90 The elements are singly linked
91 for minimum space and pointer manipulation overhead
92 at the expense of O(n) removal for arbitrary elements.
93 New elements can be added to the list
94 after an existing element
95 or at the head of the list.
98 structure is declared as follows:
102 SLIST_HEAD(HEADNAME, TYPE) head;
108 is the structure to be defined, and
110 is the type of the elements to be linked into the list.
111 A pointer to the head of the list can later be declared as:
115 struct HEADNAME *headp;
123 are user selectable.)
126 declares a structure that connects the elements in
129 .BR SLIST_HEAD_INITIALIZER ()
130 evaluates to an initializer for the list
134 initializes the list referenced by
138 evaluates to true if there are no elements in the list.
140 .BR SLIST_INSERT_HEAD ()
141 inserts the new element
143 at the head of the list.
145 .BR SLIST_INSERT_AFTER ()
146 inserts the new element
152 returns the first element in the list, or NULL if the list is empty.
155 returns the next element in the list.
158 traverses the list referenced by
160 in the forward direction,
161 assigning each element in turn to
164 .\" .BR SLIST_FOREACH_FROM ()
165 .\" behaves identically to
166 .\" .BR SLIST_FOREACH ()
169 .\" is NULL, else it treats
171 .\" as a previously found SLIST element and begins the loop at
173 .\" instead of the first element in the SLIST referenced by
176 .\" .BR SLIST_FOREACH_SAFE ()
177 .\" traverses the list referenced by
179 .\" in the forward direction, assigning each element in
183 .\" .BR SLIST_FOREACH ()
184 .\" here it is permitted to both remove
186 .\" as well as free it from within the loop safely without interfering with the
189 .\" .BR SLIST_FOREACH_FROM_SAFE ()
190 .\" behaves identically to
191 .\" .BR SLIST_FOREACH_SAFE ()
194 .\" is NULL, else it treats
196 .\" as a previously found SLIST element and begins the loop at
198 .\" instead of the first element in the SLIST referenced by
206 .BR SLIST_REMOVE_HEAD ()
209 from the head of the list.
210 For optimum efficiency,
211 elements being removed from the head of the list
212 should explicitly use this macro instead of the generic
215 .\" .BR SLIST_REMOVE_AFTER ()
216 .\" removes the element after
220 .\" .IR SLIST_REMOVE ,
221 .\" this macro does not traverse the entire list.
222 .\" .SS Other features
223 .\" .BR SLIST_SWAP ()
224 .\" swaps the contents of
230 returns nonzero if the list is empty,
231 and zero if the list contains at least one entry.
236 return a pointer to the first or next
238 structure, respectively.
240 .BR SLIST_HEAD_INITIALIZER ()
241 returns an initializer that can be assigned to the list
251 to be removed or freed within the loop,
252 as it would interfere with the traversal.
253 .BR SLIST_FOREACH_SAFE (),
254 which is present on the BSDs but is not present in glibc,
255 fixes this limitation by allowing
257 to safely be removed from the list and freed from within the loop
258 without interfering with the traversal.
260 .\" SRC BEGIN (slist.c)
265 #include <sys/queue.h>
269 SLIST_ENTRY(entry) entries; /* Singly linked list */
272 SLIST_HEAD(slisthead, entry);
277 struct entry *n1, *n2, *n3, *np;
278 struct slisthead head; /* Singly linked list
281 SLIST_INIT(&head); /* Initialize the queue */
283 n1 = malloc(sizeof(struct entry)); /* Insert at the head */
284 SLIST_INSERT_HEAD(&head, n1, entries);
286 n2 = malloc(sizeof(struct entry)); /* Insert after */
287 SLIST_INSERT_AFTER(n1, n2, entries);
289 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion */
292 n3 = SLIST_FIRST(&head);
293 SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head */
296 for (unsigned int i = 0; i < 5; i++) {
297 n1 = malloc(sizeof(struct entry));
298 SLIST_INSERT_HEAD(&head, n1, entries);
302 /* Forward traversal */
303 SLIST_FOREACH(np, &head, entries)
304 printf("%i\en", np\->data);
306 while (!SLIST_EMPTY(&head)) { /* List deletion */
307 n1 = SLIST_FIRST(&head);
308 SLIST_REMOVE_HEAD(&head, entries);