1LIST(3)                    Linux Programmer's Manual                   LIST(3)
2
3
4

NAME

6       LIST_EMPTY,    LIST_ENTRY,    LIST_FIRST,    LIST_FOREACH,   LIST_HEAD,
7       LIST_HEAD_INITIALIZER,  LIST_INIT,  LIST_INSERT_AFTER,  LIST_INSERT_BE‐
8       FORE,  LIST_INSERT_HEAD,  LIST_NEXT,  LIST_REMOVE - implementation of a
9       doubly linked list
10

SYNOPSIS

12       #include <sys/queue.h>
13
14       int LIST_EMPTY(LIST_HEAD *head);
15
16       LIST_ENTRY(TYPE);
17
18       struct TYPE *LIST_FIRST(LIST_HEAD *head);
19
20       LIST_FOREACH(struct TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME);
21
22       LIST_HEAD(HEADNAME, TYPE);
23
24       LIST_HEAD LIST_HEAD_INITIALIZER(LIST_HEAD head);
25
26       void LIST_INIT(LIST_HEAD *head);
27
28       void LIST_INSERT_AFTER(struct TYPE *listelm, struct TYPE *elm,
29                       LIST_ENTRY NAME);
30
31       void LIST_INSERT_BEFORE(struct TYPE *listelm, struct TYPE *elm,
32                       LIST_ENTRY NAME);
33
34       void LIST_INSERT_HEAD(LIST_HEAD *head, struct TYPE *elm,
35                       LIST_ENTRY NAME);
36
37       struct TYPE *LIST_NEXT(struct TYPE *elm, LIST_ENTRY NAME);
38
39       void LIST_REMOVE(struct TYPE *elm, LIST_ENTRY NAME);
40

DESCRIPTION

42       These macros define and operate on doubly linked lists.
43
44       In the macro definitions, TYPE is the name of a user-defined structure,
45       that must contain a field of type LIST_ENTRY, named NAME.  The argument
46       HEADNAME is the name of a user-defined structure that must be  declared
47       using the macro LIST_HEAD().
48
49       A list is headed by a structure defined by the LIST_HEAD() macro.  This
50       structure contains a single pointer to the first element on  the  list.
51       The  elements are doubly linked so that an arbitrary element can be re‐
52       moved without traversing the list.  New elements can be  added  to  the
53       list  after  an existing element, before an existing element, or at the
54       head of the list.  A LIST_HEAD structure is declared as follows:
55
56           LIST_HEAD(HEADNAME, TYPE) head;
57
58       where struct HEADNAME is the structure to be defined, and  struct  TYPE
59       is  the  type of the elements to be linked into the list.  A pointer to
60       the head of the list can later be declared as:
61
62           struct HEADNAME *headp;
63
64       (The names head and headp are user selectable.)
65
66       The macro LIST_HEAD_INITIALIZER() evaluates to an initializer  for  the
67       list head.
68
69       The  macro  LIST_EMPTY()  evaluates to true if there are no elements in
70       the list.
71
72       The macro LIST_ENTRY() declares a structure that connects the  elements
73       in the list.
74
75       The macro LIST_FIRST() returns the first element in the list or NULL if
76       the list is empty.
77
78       The macro LIST_FOREACH() traverses the list referenced by head  in  the
79       forward direction, assigning each element in turn to var.
80
81       The macro LIST_INIT() initializes the list referenced by head.
82
83       The macro LIST_INSERT_HEAD() inserts the new element elm at the head of
84       the list.
85
86       The macro LIST_INSERT_AFTER() inserts the new element elm after the el‐
87       ement listelm.
88
89       The  macro  LIST_INSERT_BEFORE() inserts the new element elm before the
90       element listelm.
91
92       The macro LIST_NEXT() returns the next element in the list, or NULL  if
93       this is the last.
94
95       The macro LIST_REMOVE() removes the element elm from the list.
96

RETURN VALUE

98       LIST_EMPTY() returns nonzero if the list is empty, and zero if the list
99       contains at least one entry.
100
101       LIST_FIRST(), and LIST_NEXT() return a pointer to  the  first  or  next
102       TYPE structure, respectively.
103
104       LIST_HEAD_INITIALIZER()  returns an initializer that can be assigned to
105       the list head.
106

CONFORMING TO

108       Not in POSIX.1, POSIX.1-2001 or  POSIX.1-2008.   Present  on  the  BSDs
109       (LIST macros first appeared in 4.4BSD).
110

BUGS

112       The  macro  LIST_FOREACH()  doesn't  allow  var  to be removed or freed
113       within the loop, as it would interfere with the traversal.   The  macro
114       LIST_FOREACH_SAFE(), which is present on the BSDs but is not present in
115       glibc, fixes this limitation by allowing var to safely be removed  from
116       the  list  and  freed from within the loop without interfering with the
117       traversal.
118

EXAMPLES

120       #include <stddef.h>
121       #include <stdio.h>
122       #include <stdlib.h>
123       #include <sys/queue.h>
124
125       struct entry {
126           int data;
127           LIST_ENTRY(entry) entries;              /* List. */
128       };
129
130       LIST_HEAD(listhead, entry);
131
132       int
133       main(void)
134       {
135           struct entry *n1, *n2, *n3, *np;
136           struct listhead head;                   /* List head. */
137           int i;
138
139           LIST_INIT(&head);                       /* Initialize the list. */
140
141           n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
142           LIST_INSERT_HEAD(&head, n1, entries);
143
144           n2 = malloc(sizeof(struct entry));      /* Insert after. */
145           LIST_INSERT_AFTER(n1, n2, entries);
146
147           n3 = malloc(sizeof(struct entry));      /* Insert before. */
148           LIST_INSERT_BEFORE(n2, n3, entries);
149
150           i = 0;                                  /* Forward traversal. */
151           LIST_FOREACH(np, &head, entries)
152               np->data = i++;
153
154           LIST_REMOVE(n2, entries);               /* Deletion. */
155           free(n2);
156                                                   /* Forward traversal. */
157           LIST_FOREACH(np, &head, entries)
158               printf("%i\n", np->data);
159                                                   /* List Deletion. */
160           n1 = LIST_FIRST(&head);
161           while (n1 != NULL) {
162               n2 = LIST_NEXT(n1, entries);
163               free(n1);
164               n1 = n2;
165           }
166           LIST_INIT(&head);
167
168           exit(EXIT_SUCCESS);
169       }
170

SEE ALSO

172       insque(3), queue(7)
173

COLOPHON

175       This page is part of release 5.10 of the Linux  man-pages  project.   A
176       description  of  the project, information about reporting bugs, and the
177       latest    version    of    this    page,    can     be     found     at
178       https://www.kernel.org/doc/man-pages/.
179
180
181
182GNU                               2020-12-21                           LIST(3)
Impressum