Debian Codegraph @

upstream/debian-trixie/man3/list.3

raw
1 .\" Copyright (c) 1993
2 .\" The Regents of the University of California. All rights reserved.
3 .\" and Copyright (c) 2020 by Alejandro Colomar <[email protected]>
4 .\"
5 .\" SPDX-License-Identifier: BSD-3-Clause
6 .\"
7 .\"
8 .TH LIST 3 2024-06-15 "Linux man-pages 6.9.1"
9 .SH NAME
10 LIST_EMPTY,
11 LIST_ENTRY,
12 LIST_FIRST,
13 LIST_FOREACH,
14 .\"LIST_FOREACH_FROM,
15 .\"LIST_FOREACH_SAFE,
16 .\"LIST_FOREACH_FROM_SAFE,
17 LIST_HEAD,
18 LIST_HEAD_INITIALIZER,
19 LIST_INIT,
20 LIST_INSERT_AFTER,
21 LIST_INSERT_BEFORE,
22 LIST_INSERT_HEAD,
23 LIST_NEXT,
24 .\"LIST_PREV,
25 LIST_REMOVE
26 .\"LIST_SWAP
27 \- implementation of a doubly linked list
28 .SH LIBRARY
29 Standard C library
30 .RI ( libc ", " \-lc )
31 .SH SYNOPSIS
32 .nf
33 .B #include <sys/queue.h>
34 .P
35 .B LIST_ENTRY(TYPE);
36 .P
37 .B LIST_HEAD(HEADNAME, TYPE);
38 .BI "LIST_HEAD LIST_HEAD_INITIALIZER(LIST_HEAD " head );
39 .BI "void LIST_INIT(LIST_HEAD *" head );
40 .P
41 .BI "int LIST_EMPTY(LIST_HEAD *" head );
42 .P
43 .BI "void LIST_INSERT_HEAD(LIST_HEAD *" head ,
44 .BI " struct TYPE *" elm ", LIST_ENTRY " NAME );
45 .BI "void LIST_INSERT_BEFORE(struct TYPE *" listelm ,
46 .BI " struct TYPE *" elm ", LIST_ENTRY " NAME );
47 .BI "void LIST_INSERT_AFTER(struct TYPE *" listelm ,
48 .BI " struct TYPE *" elm ", LIST_ENTRY " NAME );
49 .P
50 .BI "struct TYPE *LIST_FIRST(LIST_HEAD *" head );
51 .\" .BI "struct TYPE *LIST_PREV(struct TYPE *" elm ", LIST_HEAD *" head ,
52 .\" .BI " struct TYPE, LIST_ENTRY " NAME );
53 .BI "struct TYPE *LIST_NEXT(struct TYPE *" elm ", LIST_ENTRY " NAME );
54 .P
55 .BI "LIST_FOREACH(struct TYPE *" var ", LIST_HEAD *" head ", LIST_ENTRY " NAME );
56 .\" .BI "LIST_FOREACH_FROM(struct TYPE *" var ", LIST_HEAD *" head ", LIST_ENTRY " NAME );
57 .\" .P
58 .\" .BI "LIST_FOREACH_SAFE(struct TYPE *" var ", LIST_HEAD *" head ,
59 .\" .BI " LIST_ENTRY " NAME ", struct TYPE *" temp_var );
60 .\" .BI "LIST_FOREACH_FROM_SAFE(struct TYPE *" var ", LIST_HEAD *" head ,
61 .\" .BI " LIST_ENTRY " NAME ", struct TYPE *" temp_var );
62 .P
63 .BI "void LIST_REMOVE(struct TYPE *" elm ", LIST_ENTRY " NAME );
64 .\" .P
65 .\" .BI "void LIST_SWAP(LIST_HEAD *" head1 ", LIST_HEAD *" head2 ,
66 .\" .BI " struct TYPE, LIST_ENTRY " NAME );
67 .fi
68 .SH DESCRIPTION
69 These macros define and operate on doubly 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 LIST_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 LIST_HEAD ().
83 .SS Creation
84 A list is headed by a structure defined by the
85 .BR LIST_HEAD ()
86 macro.
87 This structure contains a single pointer to the first element on the list.
88 The elements are doubly linked
89 so that an arbitrary element can be removed without traversing the list.
90 New elements can be added to the list
91 after an existing element,
92 before an existing element,
93 or at the head of the list.
94 A
95 .I LIST_HEAD
96 structure is declared as follows:
97 .P
98 .in +4
99 .EX
100 LIST_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 LIST_ENTRY ()
124 declares a structure that connects the elements in the list.
125 .P
126 .BR LIST_HEAD_INITIALIZER ()
127 evaluates to an initializer for the list
128 .IR head .
129 .P
130 .BR LIST_INIT ()
131 initializes the list referenced by
132 .IR head .
133 .P
134 .BR LIST_EMPTY ()
135 evaluates to true if there are no elements in the list.
136 .SS Insertion
137 .BR LIST_INSERT_HEAD ()
138 inserts the new element
139 .I elm
140 at the head of the list.
141 .P
142 .BR LIST_INSERT_BEFORE ()
143 inserts the new element
144 .I elm
145 before the element
146 .IR listelm .
147 .P
148 .BR LIST_INSERT_AFTER ()
149 inserts the new element
150 .I elm
151 after the element
152 .IR listelm .
153 .SS Traversal
154 .BR LIST_FIRST ()
155 returns the first element in the list, or NULL if the list is empty.
156 .\" .P
157 .\" .BR LIST_PREV ()
158 .\" returns the previous element in the list, or NULL if this is the first.
159 .\" List
160 .\" .I head
161 .\" must contain element
162 .\" .IR elm .
163 .P
164 .BR LIST_NEXT ()
165 returns the next element in the list, or NULL if this is the last.
166 .P
167 .BR LIST_FOREACH ()
168 traverses the list referenced by
169 .I head
170 in the forward direction,
171 assigning each element in turn to
172 .IR var .
173 .\" .P
174 .\" .BR LIST_FOREACH_FROM ()
175 .\" behaves identically to
176 .\" .BR LIST_FOREACH ()
177 .\" when
178 .\" .I var
179 .\" is NULL, else it treats
180 .\" .I var
181 .\" as a previously found LIST element and begins the loop at
182 .\" .I var
183 .\" instead of the first element in the LIST referenced by
184 .\" .IR head .
185 .\" .P
186 .\" .BR LIST_FOREACH_SAFE ()
187 .\" traverses the list referenced by
188 .\" .I head
189 .\" in the forward direction, assigning each element in turn to
190 .\" .IR var .
191 .\" However, unlike
192 .\" .BR LIST_FOREACH ()
193 .\" here it is permitted to both remove
194 .\" .I var
195 .\" as well as free it from within the loop safely without interfering with the
196 .\" traversal.
197 .\" .P
198 .\" .BR LIST_FOREACH_FROM_SAFE ()
199 .\" behaves identically to
200 .\" .BR LIST_FOREACH_SAFE ()
201 .\" when
202 .\" .I var
203 .\" is NULL, else it treats
204 .\" .I var
205 .\" as a previously found LIST element and begins the loop at
206 .\" .I var
207 .\" instead of the first element in the LIST referenced by
208 .\" .IR head .
209 .SS Removal
210 .BR LIST_REMOVE ()
211 removes the element
212 .I elm
213 from the list.
214 .\" .SS Other features
215 .\" .BR LIST_SWAP ()
216 .\" swaps the contents of
217 .\" .I head1
218 .\" and
219 .\" .IR head2 .
220 .SH RETURN VALUE
221 .BR LIST_EMPTY ()
222 returns nonzero if the list is empty,
223 and zero if the list contains at least one entry.
224 .P
225 .BR LIST_FIRST (),
226 and
227 .BR LIST_NEXT ()
228 return a pointer to the first or next
229 .I TYPE
230 structure, respectively.
231 .P
232 .BR LIST_HEAD_INITIALIZER ()
233 returns an initializer that can be assigned to the list
234 .IR head .
235 .SH STANDARDS
236 BSD.
237 .SH HISTORY
238 4.4BSD.
239 .SH BUGS
240 .BR LIST_FOREACH ()
241 doesn't allow
242 .I var
243 to be removed or freed within the loop,
244 as it would interfere with the traversal.
245 .BR LIST_FOREACH_SAFE (),
246 which is present on the BSDs but is not present in glibc,
247 fixes this limitation by allowing
248 .I var
249 to safely be removed from the list and freed from within the loop
250 without interfering with the traversal.
251 .SH EXAMPLES
252 .\" SRC BEGIN (list.c)
253 .EX
254 #include <stddef.h>
255 #include <stdio.h>
256 #include <stdlib.h>
257 #include <sys/queue.h>
258 \&
259 struct entry {
260 int data;
261 LIST_ENTRY(entry) entries; /* List */
262 };
263 \&
264 LIST_HEAD(listhead, entry);
265 \&
266 int
267 main(void)
268 {
269 struct entry *n1, *n2, *n3, *np;
270 struct listhead head; /* List head */
271 int i;
272 \&
273 LIST_INIT(&head); /* Initialize the list */
274 \&
275 n1 = malloc(sizeof(struct entry)); /* Insert at the head */
276 LIST_INSERT_HEAD(&head, n1, entries);
277 \&
278 n2 = malloc(sizeof(struct entry)); /* Insert after */
279 LIST_INSERT_AFTER(n1, n2, entries);
280 \&
281 n3 = malloc(sizeof(struct entry)); /* Insert before */
282 LIST_INSERT_BEFORE(n2, n3, entries);
283 \&
284 i = 0; /* Forward traversal */
285 LIST_FOREACH(np, &head, entries)
286 np\->data = i++;
287 \&
288 LIST_REMOVE(n2, entries); /* Deletion */
289 free(n2);
290 /* Forward traversal */
291 LIST_FOREACH(np, &head, entries)
292 printf("%i\[rs]n", np\->data);
293 /* List deletion */
294 n1 = LIST_FIRST(&head);
295 while (n1 != NULL) {
296 n2 = LIST_NEXT(n1, entries);
297 free(n1);
298 n1 = n2;
299 }
300 LIST_INIT(&head);
301 \&
302 exit(EXIT_SUCCESS);
303 }
304 .EE
305 .\" SRC END
306 .SH SEE ALSO
307 .BR insque (3),
308 .BR queue (7)