2 .\" The Regents of the University of California. All rights reserved.
3 .\" and Copyright (c) 2020 by Alejandro Colomar <colomar.6.4.3@gmail.com>
5 .\" %%%LICENSE_START(BSD_3_CLAUSE_UCB)
6 .\" Redistribution and use in source and binary forms, with or without
7 .\" modification, are permitted provided that the following conditions
9 .\" 1. Redistributions of source code must retain the above copyright
10 .\" notice, this list of conditions and the following disclaimer.
11 .\" 2. Redistributions in binary form must reproduce the above copyright
12 .\" notice, this list of conditions and the following disclaimer in the
13 .\" documentation and/or other materials provided with the distribution.
14 .\" 3. Neither the name of the University nor the names of its contributors
15 .\" may be used to endorse or promote products derived from this software
16 .\" without specific prior written permission.
18 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
19 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 .\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
22 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 .TH SLIST 3 2021-03-22 "GNU" "Linux Programmer's Manual"
38 .\"SLIST_FOREACH_FROM,
39 .\"SLIST_FOREACH_FROM_SAFE,
40 .\"SLIST_FOREACH_SAFE,
42 SLIST_HEAD_INITIALIZER,
48 .\"SLIST_REMOVE_AFTER,
51 \- implementation of a singly linked list
54 .B #include <sys/queue.h>
58 .B SLIST_HEAD(HEADNAME, TYPE);
59 .BI "SLIST_HEAD SLIST_HEAD_INITIALIZER(SLIST_HEAD " head );
60 .BI "void SLIST_INIT(SLIST_HEAD *" head );
62 .BI "int SLIST_EMPTY(SLIST_HEAD *" head );
64 .BI "void SLIST_INSERT_HEAD(SLIST_HEAD *" head ,
65 .BI " struct TYPE *" elm ", SLIST_ENTRY " NAME );
66 .BI "void SLIST_INSERT_AFTER(struct TYPE *" listelm ,
67 .BI " struct TYPE *" elm ", SLIST_ENTRY " NAME );
69 .BI "struct TYPE *SLIST_FIRST(SLIST_HEAD *" head );
70 .BI "struct TYPE *SLIST_NEXT(struct TYPE *" elm ", SLIST_ENTRY " NAME );
72 .BI "SLIST_FOREACH(struct TYPE *" var ", SLIST_HEAD *" head ", SLIST_ENTRY " NAME );
73 .\" .BI "SLIST_FOREACH_FROM(struct TYPE *" var ", SLIST_HEAD *" head ,
74 .\" .BI " SLIST_ENTRY " NAME );
76 .\" .BI "SLIST_FOREACH_SAFE(struct TYPE *" var ", SLIST_HEAD *" head ,
77 .\" .BI " SLIST_ENTRY " NAME ", struct TYPE *" temp_var );
78 .\" .BI "SLIST_FOREACH_FROM_SAFE(struct TYPE *" var ", SLIST_HEAD *" head ,
79 .\" .BI " SLIST_ENTRY " NAME ", struct TYPE *" temp_var );
81 .BI "void SLIST_REMOVE(SLIST_HEAD *" head ", struct TYPE *" elm ,
82 .BI " SLIST_ENTRY " NAME );
83 .BI "void SLIST_REMOVE_HEAD(SLIST_HEAD *" head ,
84 .BI " SLIST_ENTRY " NAME );
85 .\" .BI "void SLIST_REMOVE_AFTER(struct TYPE *" elm ,
86 .\" .BI " SLIST_ENTRY " NAME );
88 .\" .BI "void SLIST_SWAP(SLIST_HEAD *" head1 ", SLIST_HEAD *" head2 ,
89 .\" .BI " SLIST_ENTRY " NAME );
92 These macros define and operate on doubly linked lists.
94 In the macro definitions,
96 is the name of a user-defined structure,
97 that must contain a field of type
103 is the name of a user-defined structure
104 that must be declared using the macro
107 A singly linked list is headed by a structure defined by the
110 This structure contains a single pointer to the first element on the list.
111 The elements are singly linked
112 for minimum space and pointer manipulation overhead
113 at the expense of O(n) removal for arbitrary elements.
114 New elements can be added to the list
115 after an existing element
116 or at the head of the list.
119 structure is declared as follows:
123 SLIST_HEAD(HEADNAME, TYPE) head;
129 is the structure to be defined, and
131 is the type of the elements to be linked into the list.
132 A pointer to the head of the list can later be declared as:
136 struct HEADNAME *headp;
144 are user selectable.)
147 declares a structure that connects the elements in
150 .BR SLIST_HEAD_INITIALIZER ()
151 evaluates to an initializer for the list
155 initializes the list referenced by
159 evaluates to true if there are no elements in the list.
161 .BR SLIST_INSERT_HEAD ()
162 inserts the new element
164 at the head of the list.
166 .BR SLIST_INSERT_AFTER ()
167 inserts the new element
173 returns the first element in the list, or NULL if the list is empty.
176 returns the next element in the list.
179 traverses the list referenced by
181 in the forward direction,
182 assigning each element in turn to
185 .\" .BR SLIST_FOREACH_FROM ()
186 .\" behaves identically to
187 .\" .BR SLIST_FOREACH ()
190 .\" is NULL, else it treats
192 .\" as a previously found SLIST element and begins the loop at
194 .\" instead of the first element in the SLIST referenced by
197 .\" .BR SLIST_FOREACH_SAFE ()
198 .\" traverses the list referenced by
200 .\" in the forward direction, assigning each element in
204 .\" .BR SLIST_FOREACH ()
205 .\" here it is permitted to both remove
207 .\" as well as free it from within the loop safely without interfering with the
210 .\" .BR SLIST_FOREACH_FROM_SAFE ()
211 .\" behaves identically to
212 .\" .BR SLIST_FOREACH_SAFE ()
215 .\" is NULL, else it treats
217 .\" as a previously found SLIST element and begins the loop at
219 .\" instead of the first element in the SLIST referenced by
227 .BR SLIST_REMOVE_HEAD ()
230 from the head of the list.
231 For optimum efficiency,
232 elements being removed from the head of the list
233 should explicitly use this macro instead of the generic
236 .\" .BR SLIST_REMOVE_AFTER ()
237 .\" removes the element after
241 .\" .IR SLIST_REMOVE ,
242 .\" this macro does not traverse the entire list.
243 .\" .SS Other features
244 .\" .BR SLIST_SWAP ()
245 .\" swaps the contents of
251 returns nonzero if the list is empty,
252 and zero if the list contains at least one entry.
257 return a pointer to the first or next
259 structure, respectively.
261 .BR SLIST_HEAD_INITIALIZER ()
262 returns an initializer that can be assigned to the list
265 Not in POSIX.1, POSIX.1-2001, or POSIX.1-2008.
267 (SLIST macros first appeared in 4.4BSD).
272 to be removed or freed within the loop,
273 as it would interfere with the traversal.
274 .BR SLIST_FOREACH_SAFE (),
275 which is present on the BSDs but is not present in glibc,
276 fixes this limitation by allowing
278 to safely be removed from the list and freed from within the loop
279 without interfering with the traversal.
285 #include <sys/queue.h>
289 SLIST_ENTRY(entry) entries; /* Singly linked list */
292 SLIST_HEAD(slisthead, entry);
297 struct entry *n1, *n2, *n3, *np;
298 struct slisthead head; /* Singly linked list
301 SLIST_INIT(&head); /* Initialize the queue */
303 n1 = malloc(sizeof(struct entry)); /* Insert at the head */
304 SLIST_INSERT_HEAD(&head, n1, entries);
306 n2 = malloc(sizeof(struct entry)); /* Insert after */
307 SLIST_INSERT_AFTER(n1, n2, entries);
309 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion */
312 n3 = SLIST_FIRST(&head);
313 SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head */
316 for (int i = 0; i < 5; i++) {
317 n1 = malloc(sizeof(struct entry));
318 SLIST_INSERT_HEAD(&head, n1, entries);
322 /* Forward traversal */
323 SLIST_FOREACH(np, &head, entries)
324 printf("%i\en", np\->data);
326 while (!SLIST_EMPTY(&head)) { /* List deletion */
327 n1 = SLIST_FIRST(&head);
328 SLIST_REMOVE_HEAD(&head, entries);