Debian Codegraph @

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