Debian Codegraph @

upstream/debian-unstable/man3/slist.3

raw
1 .\" Copyright 1993, The Regents of the University of California.
2 .\" Copyright, the authors of the Linux man-pages project
3 .\"
4 .\" SPDX-License-Identifier: BSD-3-Clause
5 .\"
6 .TH SLIST 3 2025-05-17 "Linux man-pages 6.18"
7 .SH NAME
8 SLIST_EMPTY,
9 SLIST_ENTRY,
10 SLIST_FIRST,
11 SLIST_FOREACH,
12 .\"SLIST_FOREACH_FROM,
13 .\"SLIST_FOREACH_FROM_SAFE,
14 .\"SLIST_FOREACH_SAFE,
15 SLIST_HEAD,
16 SLIST_HEAD_INITIALIZER,
17 SLIST_INIT,
18 SLIST_INSERT_AFTER,
19 SLIST_INSERT_HEAD,
20 SLIST_NEXT,
21 SLIST_REMOVE,
22 .\"SLIST_REMOVE_AFTER,
23 SLIST_REMOVE_HEAD
24 .\"SLIST_SWAP
25 \- implementation of a singly linked list
26 .SH LIBRARY
27 Standard C library
28 .RI ( libc ,\~ \-lc )
29 .SH SYNOPSIS
30 .nf
31 .B #include <sys/queue.h>
32 .P
33 .B SLIST_ENTRY(TYPE);
34 .P
35 .B SLIST_HEAD(HEADNAME, TYPE);
36 .BI "SLIST_HEAD SLIST_HEAD_INITIALIZER(SLIST_HEAD " head );
37 .BI "void SLIST_INIT(SLIST_HEAD *" head );
38 .P
39 .BI "int SLIST_EMPTY(SLIST_HEAD *" head );
40 .P
41 .BI "void SLIST_INSERT_HEAD(SLIST_HEAD *" head ,
42 .BI " struct TYPE *" elm ", SLIST_ENTRY " NAME );
43 .BI "void SLIST_INSERT_AFTER(struct TYPE *" listelm ,
44 .BI " struct TYPE *" elm ", SLIST_ENTRY " NAME );
45 .P
46 .BI "struct TYPE *SLIST_FIRST(SLIST_HEAD *" head );
47 .BI "struct TYPE *SLIST_NEXT(struct TYPE *" elm ", SLIST_ENTRY " NAME );
48 .P
49 .BI "SLIST_FOREACH(struct TYPE *" var ", SLIST_HEAD *" head ", SLIST_ENTRY " NAME );
50 .\" .BI "SLIST_FOREACH_FROM(struct TYPE *" var ", SLIST_HEAD *" head ,
51 .\" .BI " SLIST_ENTRY " NAME );
52 .\" .P
53 .\" .BI "SLIST_FOREACH_SAFE(struct TYPE *" var ", SLIST_HEAD *" head ,
54 .\" .BI " SLIST_ENTRY " NAME ", struct TYPE *" temp_var );
55 .\" .BI "SLIST_FOREACH_FROM_SAFE(struct TYPE *" var ", SLIST_HEAD *" head ,
56 .\" .BI " SLIST_ENTRY " NAME ", struct TYPE *" temp_var );
57 .P
58 .BI "void SLIST_REMOVE(SLIST_HEAD *" head ", struct TYPE *" elm ", TYPE,"
59 .BI " SLIST_ENTRY " NAME );
60 .BI "void SLIST_REMOVE_HEAD(SLIST_HEAD *" head ,
61 .BI " SLIST_ENTRY " NAME );
62 .\" .BI "void SLIST_REMOVE_AFTER(struct TYPE *" elm ,
63 .\" .BI " SLIST_ENTRY " NAME );
64 .\" .P
65 .\" .BI "void SLIST_SWAP(SLIST_HEAD *" head1 ", SLIST_HEAD *" head2 ,
66 .\" .BI " SLIST_ENTRY " NAME );
67 .fi
68 .SH DESCRIPTION
69 These macros define and operate on singly linked lists.
70 .P
71 In the macro definitions,
72 .I TYPE
73 is the name of a user-defined structure,
74 that must contain a field of type
75 .IR SLIST_ENTRY ,
76 named
77 .IR NAME .
78 The argument
79 .I HEADNAME
80 is the name of a user-defined structure
81 that must be declared using the macro
82 .BR SLIST_HEAD ().
83 .SS Creation
84 A singly linked list is headed by a structure defined by the
85 .BR SLIST_HEAD ()
86 macro.
87 This structure contains a single pointer to the first element on the list.
88 The elements are singly linked
89 for minimum space and pointer manipulation overhead
90 at the expense of O(n) removal for arbitrary elements.
91 New elements can be added to the list
92 after an existing element
93 or at the head of the list.
94 An
95 .I SLIST_HEAD
96 structure is declared as follows:
97 .P
98 .in +4
99 .EX
100 SLIST_HEAD(HEADNAME, TYPE) head;
101 .EE
102 .in
103 .P
104 where
105 .I struct HEADNAME
106 is the structure to be defined, and
107 .I struct TYPE
108 is the type of the elements to be linked into the list.
109 A pointer to the head of the list can later be declared as:
110 .P
111 .in +4
112 .EX
113 struct HEADNAME *headp;
114 .EE
115 .in
116 .P
117 (The names
118 .I head
119 and
120 .I headp
121 are user selectable.)
122 .P
123 .BR SLIST_ENTRY ()
124 declares a structure that connects the elements in
125 the list.
126 .P
127 .BR SLIST_HEAD_INITIALIZER ()
128 evaluates to an initializer for the list
129 .IR head .
130 .P
131 .BR SLIST_INIT ()
132 initializes the list referenced by
133 .IR head .
134 .P
135 .BR SLIST_EMPTY ()
136 evaluates to true if there are no elements in the list.
137 .SS Insertion
138 .BR SLIST_INSERT_HEAD ()
139 inserts the new element
140 .I elm
141 at the head of the list.
142 .P
143 .BR SLIST_INSERT_AFTER ()
144 inserts the new element
145 .I elm
146 after the element
147 .IR listelm .
148 .SS Traversal
149 .BR SLIST_FIRST ()
150 returns the first element in the list, or NULL if the list is empty.
151 .P
152 .BR SLIST_NEXT ()
153 returns the next element in the list.
154 .P
155 .BR SLIST_FOREACH ()
156 traverses the list referenced by
157 .I head
158 in the forward direction,
159 assigning each element in turn to
160 .IR var .
161 .\" .P
162 .\" .BR SLIST_FOREACH_FROM ()
163 .\" behaves identically to
164 .\" .BR SLIST_FOREACH ()
165 .\" when
166 .\" .I var
167 .\" is NULL, else it treats
168 .\" .I var
169 .\" as a previously found SLIST element and begins the loop at
170 .\" .I var
171 .\" instead of the first element in the SLIST referenced by
172 .\" .IR head .
173 .\" .Pp
174 .\" .BR SLIST_FOREACH_SAFE ()
175 .\" traverses the list referenced by
176 .\" .I head
177 .\" in the forward direction, assigning each element in
178 .\" turn to
179 .\" .IR var .
180 .\" However, unlike
181 .\" .BR SLIST_FOREACH ()
182 .\" here it is permitted to both remove
183 .\" .I var
184 .\" as well as free it from within the loop safely without interfering with the
185 .\" traversal.
186 .\" .P
187 .\" .BR SLIST_FOREACH_FROM_SAFE ()
188 .\" behaves identically to
189 .\" .BR SLIST_FOREACH_SAFE ()
190 .\" when
191 .\" .I var
192 .\" is NULL, else it treats
193 .\" .I var
194 .\" as a previously found SLIST element and begins the loop at
195 .\" .I var
196 .\" instead of the first element in the SLIST referenced by
197 .\" .IR head .
198 .SS Removal
199 .BR SLIST_REMOVE ()
200 removes the element
201 .I elm
202 from the list.
203 .P
204 .BR SLIST_REMOVE_HEAD ()
205 removes the element
206 .I elm
207 from the head of the list.
208 For optimum efficiency,
209 elements being removed from the head of the list
210 should explicitly use this macro instead of the generic
211 .BR SLIST_REMOVE ().
212 .\" .P
213 .\" .BR SLIST_REMOVE_AFTER ()
214 .\" removes the element after
215 .\" .I elm
216 .\" from the list.
217 .\" Unlike
218 .\" .IR SLIST_REMOVE ,
219 .\" this macro does not traverse the entire list.
220 .\" .SS Other features
221 .\" .BR SLIST_SWAP ()
222 .\" swaps the contents of
223 .\" .I head1
224 .\" and
225 .\" .IR head2 .
226 .SH RETURN VALUE
227 .BR SLIST_EMPTY ()
228 returns nonzero if the list is empty,
229 and zero if the list contains at least one entry.
230 .P
231 .BR SLIST_FIRST (),
232 and
233 .BR SLIST_NEXT ()
234 return a pointer to the first or next
235 .I TYPE
236 structure, respectively.
237 .P
238 .BR SLIST_HEAD_INITIALIZER ()
239 returns an initializer that can be assigned to the list
240 .IR head .
241 .SH STANDARDS
242 BSD.
243 .SH HISTORY
244 4.4BSD.
245 .SH BUGS
246 .BR SLIST_FOREACH ()
247 doesn't allow
248 .I var
249 to be removed or freed within the loop,
250 as it would interfere with the traversal.
251 .BR SLIST_FOREACH_SAFE (),
252 which is present on the BSDs but is not present in glibc,
253 fixes this limitation by allowing
254 .I var
255 to safely be removed from the list and freed from within the loop
256 without interfering with the traversal.
257 .SH EXAMPLES
258 .\" SRC BEGIN (slist.c)
259 .EX
260 #include <stddef.h>
261 #include <stdio.h>
262 #include <stdlib.h>
263 #include <sys/queue.h>
264 \&
265 struct entry {
266 int data;
267 SLIST_ENTRY(entry) entries; /* Singly linked list */
268 };
269 \&
270 SLIST_HEAD(slisthead, entry);
271 \&
272 int
273 main(void)
274 {
275 struct entry *n1, *n2, *n3, *np;
276 struct slisthead head; /* Singly linked list
277 head */
278 \&
279 SLIST_INIT(&head); /* Initialize the queue */
280 \&
281 n1 = malloc(sizeof(struct entry)); /* Insert at the head */
282 SLIST_INSERT_HEAD(&head, n1, entries);
283 \&
284 n2 = malloc(sizeof(struct entry)); /* Insert after */
285 SLIST_INSERT_AFTER(n1, n2, entries);
286 \&
287 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion */
288 free(n2);
289 \&
290 n3 = SLIST_FIRST(&head);
291 SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head */
292 free(n3);
293 \&
294 for (unsigned int i = 0; i < 5; i++) {
295 n1 = malloc(sizeof(struct entry));
296 SLIST_INSERT_HEAD(&head, n1, entries);
297 n1\->data = i;
298 }
299 \&
300 /* Forward traversal */
301 SLIST_FOREACH(np, &head, entries)
302 printf("%i\[rs]n", np\->data);
303 \&
304 while (!SLIST_EMPTY(&head)) { /* List deletion */
305 n1 = SLIST_FIRST(&head);
306 SLIST_REMOVE_HEAD(&head, entries);
307 free(n1);
308 }
309 SLIST_INIT(&head);
310 \&
311 exit(EXIT_SUCCESS);
312 }
313 .EE
314 .\" SRC END
315 .SH SEE ALSO
316 .BR insque (3),
317 .BR queue (7)