]>
Commit | Line | Data |
---|---|---|
815041a5 AC |
1 | .\" Copyright (c) 1993 |
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> | |
4 | .\" | |
40fa0ff4 | 5 | .\" SPDX-License-Identifier: BSD-3-Clause |
815041a5 AC |
6 | .\" |
7 | .\" | |
1d767b55 | 8 | .TH LIST 3 2021-03-22 "GNU" "Linux Programmer's Manual" |
815041a5 | 9 | .SH NAME |
87241f17 AC |
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, | |
31121103 | 24 | .\"LIST_PREV, |
87241f17 AC |
25 | LIST_REMOVE |
26 | .\"LIST_SWAP | |
df10ec35 | 27 | \- implementation of a doubly linked list |
bb54ee3e AC |
28 | .SH LIBRARY |
29 | Standard C library | |
8fc3b2cf | 30 | .RI ( libc ", " \-lc ) |
815041a5 | 31 | .SH SYNOPSIS |
87241f17 AC |
32 | .nf |
33 | .B #include <sys/queue.h> | |
34 | .PP | |
87241f17 AC |
35 | .B LIST_ENTRY(TYPE); |
36 | .PP | |
554afbe8 AC |
37 | .B LIST_HEAD(HEADNAME, TYPE); |
38 | .BI "LIST_HEAD LIST_HEAD_INITIALIZER(LIST_HEAD " head ); | |
39 | .BI "void LIST_INIT(LIST_HEAD *" head ); | |
87241f17 | 40 | .PP |
554afbe8 | 41 | .BI "int LIST_EMPTY(LIST_HEAD *" head ); |
87241f17 | 42 | .PP |
554afbe8 AC |
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 ); | |
87241f17 | 49 | .PP |
554afbe8 AC |
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 ); | |
87241f17 | 54 | .PP |
554afbe8 AC |
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 | .\" .PP | |
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 ); | |
87241f17 | 62 | .PP |
554afbe8 AC |
63 | .BI "void LIST_REMOVE(struct TYPE *" elm ", LIST_ENTRY " NAME ); |
64 | .\" .PP | |
65 | .\" .BI "void LIST_SWAP(LIST_HEAD *" head1 ", LIST_HEAD *" head2 , | |
66 | .\" .BI " struct TYPE, LIST_ENTRY " NAME ); | |
87241f17 | 67 | .fi |
815041a5 | 68 | .SH DESCRIPTION |
df10ec35 | 69 | These macros define and operate on doubly linked lists. |
ce6606e1 | 70 | .PP |
481854f5 | 71 | In the macro definitions, |
87241f17 | 72 | .I TYPE |
d3f0057e | 73 | is the name of a user-defined structure, |
481854f5 | 74 | that must contain a field of type |
87241f17 | 75 | .IR LIST_ENTRY , |
481854f5 | 76 | named |
87241f17 | 77 | .IR NAME . |
481854f5 | 78 | The argument |
1ae6b2c7 | 79 | .I HEADNAME |
554afbe8 AC |
80 | is the name of a user-defined structure |
81 | that must be declared using the macro | |
87241f17 | 82 | .BR LIST_HEAD (). |
554afbe8 | 83 | .SS Creation |
13514abe | 84 | A list is headed by a structure defined by the |
87241f17 | 85 | .BR LIST_HEAD () |
13514abe | 86 | macro. |
554afbe8 AC |
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. | |
13514abe | 94 | A |
87241f17 | 95 | .I LIST_HEAD |
13514abe | 96 | structure is declared as follows: |
87241f17 AC |
97 | .PP |
98 | .in +4 | |
99 | .EX | |
13514abe | 100 | LIST_HEAD(HEADNAME, TYPE) head; |
87241f17 AC |
101 | .EE |
102 | .in | |
103 | .PP | |
13514abe | 104 | where |
13e59b96 AC |
105 | .I struct HEADNAME |
106 | is the structure to be defined, and | |
107 | .I struct TYPE | |
13514abe AC |
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: | |
87241f17 AC |
110 | .PP |
111 | .in +4 | |
112 | .EX | |
13514abe | 113 | struct HEADNAME *headp; |
87241f17 AC |
114 | .EE |
115 | .in | |
116 | .PP | |
13514abe | 117 | (The names |
87241f17 | 118 | .I head |
13514abe | 119 | and |
87241f17 | 120 | .I headp |
13514abe | 121 | are user selectable.) |
87241f17 | 122 | .PP |
554afbe8 AC |
123 | .BR LIST_ENTRY () |
124 | declares a structure that connects the elements in the list. | |
125 | .PP | |
87241f17 | 126 | .BR LIST_HEAD_INITIALIZER () |
13514abe | 127 | evaluates to an initializer for the list |
87241f17 AC |
128 | .IR head . |
129 | .PP | |
554afbe8 AC |
130 | .BR LIST_INIT () |
131 | initializes the list referenced by | |
132 | .IR head . | |
133 | .PP | |
87241f17 | 134 | .BR LIST_EMPTY () |
13514abe | 135 | evaluates to true if there are no elements in the list. |
554afbe8 AC |
136 | .SS Insertion |
137 | .BR LIST_INSERT_HEAD () | |
138 | inserts the new element | |
139 | .I elm | |
140 | at the head of the list. | |
87241f17 | 141 | .PP |
554afbe8 AC |
142 | .BR LIST_INSERT_BEFORE () |
143 | inserts the new element | |
144 | .I elm | |
145 | before the element | |
146 | .IR listelm . | |
87241f17 | 147 | .PP |
554afbe8 AC |
148 | .BR LIST_INSERT_AFTER () |
149 | inserts the new element | |
150 | .I elm | |
151 | after the element | |
152 | .IR listelm . | |
153 | .SS Traversal | |
87241f17 | 154 | .BR LIST_FIRST () |
554afbe8 AC |
155 | returns the first element in the list, or NULL if the list is empty. |
156 | .\" .PP | |
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 | .PP | |
164 | .BR LIST_NEXT () | |
165 | returns the next element in the list, or NULL if this is the last. | |
87241f17 | 166 | .PP |
87241f17 | 167 | .BR LIST_FOREACH () |
13514abe | 168 | traverses the list referenced by |
87241f17 | 169 | .I head |
554afbe8 AC |
170 | in the forward direction, |
171 | assigning each element in turn to | |
87241f17 AC |
172 | .IR var . |
173 | .\" .PP | |
87241f17 | 174 | .\" .BR LIST_FOREACH_FROM () |
13514abe | 175 | .\" behaves identically to |
87241f17 | 176 | .\" .BR LIST_FOREACH () |
13514abe | 177 | .\" when |
87241f17 | 178 | .\" .I var |
13514abe | 179 | .\" is NULL, else it treats |
87241f17 | 180 | .\" .I var |
13514abe | 181 | .\" as a previously found LIST element and begins the loop at |
87241f17 | 182 | .\" .I var |
13514abe | 183 | .\" instead of the first element in the LIST referenced by |
87241f17 AC |
184 | .\" .IR head . |
185 | .\" .PP | |
87241f17 | 186 | .\" .BR LIST_FOREACH_SAFE () |
13514abe | 187 | .\" traverses the list referenced by |
87241f17 | 188 | .\" .I head |
13514abe | 189 | .\" in the forward direction, assigning each element in turn to |
87241f17 | 190 | .\" .IR var . |
13514abe | 191 | .\" However, unlike |
87241f17 | 192 | .\" .BR LIST_FOREACH () |
13514abe | 193 | .\" here it is permitted to both remove |
87241f17 | 194 | .\" .I var |
13514abe AC |
195 | .\" as well as free it from within the loop safely without interfering with the |
196 | .\" traversal. | |
87241f17 | 197 | .\" .PP |
87241f17 | 198 | .\" .BR LIST_FOREACH_FROM_SAFE () |
13514abe | 199 | .\" behaves identically to |
87241f17 | 200 | .\" .BR LIST_FOREACH_SAFE () |
13514abe | 201 | .\" when |
87241f17 | 202 | .\" .I var |
13514abe | 203 | .\" is NULL, else it treats |
87241f17 | 204 | .\" .I var |
13514abe | 205 | .\" as a previously found LIST element and begins the loop at |
87241f17 | 206 | .\" .I var |
13514abe | 207 | .\" instead of the first element in the LIST referenced by |
87241f17 | 208 | .\" .IR head . |
554afbe8 | 209 | .SS Removal |
87241f17 | 210 | .BR LIST_REMOVE () |
13514abe | 211 | removes the element |
87241f17 | 212 | .I elm |
13514abe | 213 | from the list. |
554afbe8 | 214 | .\" .SS Other features |
87241f17 | 215 | .\" .BR LIST_SWAP () |
13514abe | 216 | .\" swaps the contents of |
87241f17 | 217 | .\" .I head1 |
13514abe | 218 | .\" and |
87241f17 | 219 | .\" .IR head2 . |
815041a5 | 220 | .SH RETURN VALUE |
ce6606e1 | 221 | .BR LIST_EMPTY () |
a45701ef | 222 | returns nonzero if the list is empty, |
ce6606e1 AC |
223 | and zero if the list contains at least one entry. |
224 | .PP | |
225 | .BR LIST_FIRST (), | |
226 | and | |
227 | .BR LIST_NEXT () | |
228 | return a pointer to the first or next | |
b1db9340 | 229 | .I TYPE |
c460d239 | 230 | structure, respectively. |
ce6606e1 AC |
231 | .PP |
232 | .BR LIST_HEAD_INITIALIZER () | |
233 | returns an initializer that can be assigned to the list | |
234 | .IR head . | |
815041a5 | 235 | .SH CONFORMING TO |
2ddebe1a | 236 | Not in POSIX.1, POSIX.1-2001, or POSIX.1-2008. |
481854f5 | 237 | Present on the BSDs |
87241f17 | 238 | (LIST macros first appeared in 4.4BSD). |
815041a5 | 239 | .SH BUGS |
ce6606e1 AC |
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. | |
ce6606e1 | 245 | .BR LIST_FOREACH_SAFE (), |
7e5e3699 MK |
246 | which is present on the BSDs but is not present in glibc, |
247 | fixes this limitation by allowing | |
ce6606e1 | 248 | .I var |
7e5e3699 | 249 | to safely be removed from the list and freed from within the loop |
ce6606e1 | 250 | without interfering with the traversal. |
815041a5 | 251 | .SH EXAMPLES |
87241f17 | 252 | .EX |
be7973e6 AC |
253 | #include <stddef.h> |
254 | #include <stdio.h> | |
255 | #include <stdlib.h> | |
256 | #include <sys/queue.h> | |
257 | ||
258 | struct entry { | |
259 | int data; | |
c2e81ff9 | 260 | LIST_ENTRY(entry) entries; /* List */ |
be7973e6 AC |
261 | }; |
262 | ||
263 | LIST_HEAD(listhead, entry); | |
264 | ||
265 | int | |
266 | main(void) | |
267 | { | |
ef4138a9 | 268 | struct entry *n1, *n2, *n3, *np; |
c2e81ff9 | 269 | struct listhead head; /* List head */ |
ef4138a9 | 270 | int i; |
be7973e6 | 271 | |
c2e81ff9 | 272 | LIST_INIT(&head); /* Initialize the list */ |
be7973e6 | 273 | |
c2e81ff9 | 274 | n1 = malloc(sizeof(struct entry)); /* Insert at the head */ |
be7973e6 AC |
275 | LIST_INSERT_HEAD(&head, n1, entries); |
276 | ||
c2e81ff9 | 277 | n2 = malloc(sizeof(struct entry)); /* Insert after */ |
be7973e6 AC |
278 | LIST_INSERT_AFTER(n1, n2, entries); |
279 | ||
c2e81ff9 | 280 | n3 = malloc(sizeof(struct entry)); /* Insert before */ |
be7973e6 AC |
281 | LIST_INSERT_BEFORE(n2, n3, entries); |
282 | ||
c2e81ff9 | 283 | i = 0; /* Forward traversal */ |
be7973e6 | 284 | LIST_FOREACH(np, &head, entries) |
d064d41a | 285 | np\->data = i++; |
be7973e6 | 286 | |
c2e81ff9 | 287 | LIST_REMOVE(n2, entries); /* Deletion */ |
be7973e6 | 288 | free(n2); |
c2e81ff9 | 289 | /* Forward traversal */ |
be7973e6 | 290 | LIST_FOREACH(np, &head, entries) |
d064d41a | 291 | printf("%i\en", np\->data); |
f52cb552 | 292 | /* List deletion */ |
be7973e6 AC |
293 | n1 = LIST_FIRST(&head); |
294 | while (n1 != NULL) { | |
295 | n2 = LIST_NEXT(n1, entries); | |
296 | free(n1); | |
297 | n1 = n2; | |
298 | } | |
299 | LIST_INIT(&head); | |
300 | ||
301 | exit(EXIT_SUCCESS); | |
302 | } | |
87241f17 | 303 | .EE |
815041a5 | 304 | .SH SEE ALSO |
ce6606e1 | 305 | .BR insque (3), |
083d4e6a | 306 | .BR queue (7) |