LIST_ENTRY(3)

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       LIST_ENTRY(TYPE);
15
16       LIST_HEAD(HEADNAME, TYPE);
17       LIST_HEAD LIST_HEAD_INITIALIZER(LIST_HEAD head);
18       void LIST_INIT(LIST_HEAD *head);
19
20       int LIST_EMPTY(LIST_HEAD *head);
21
22       void LIST_INSERT_HEAD(LIST_HEAD *head,
23                               struct TYPE *elm, LIST_ENTRY NAME);
24       void LIST_INSERT_BEFORE(struct TYPE *listelm,
25                               struct TYPE *elm, LIST_ENTRY NAME);
26       void LIST_INSERT_AFTER(struct TYPE *listelm,
27                               struct TYPE *elm, LIST_ENTRY NAME);
28
29       struct TYPE *LIST_FIRST(LIST_HEAD *head);
30       struct TYPE *LIST_NEXT(struct TYPE *elm, LIST_ENTRY NAME);
31
32       LIST_FOREACH(struct TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME);
33
34       void LIST_REMOVE(struct TYPE *elm, LIST_ENTRY NAME);
35

DESCRIPTION

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

RETURN VALUE

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

CONFORMING TO

104       Not  in  POSIX.1,  POSIX.1-2001,  or POSIX.1-2008.  Present on the BSDs
105       (LIST macros first appeared in 4.4BSD).
106

BUGS

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

EXAMPLES

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

COLOPHON

170       This page is part of release 5.12 of the Linux  man-pages  project.   A
171       description  of  the project, information about reporting bugs, and the
172       latest    version    of    this    page,    can     be     found     at
173       https://www.kernel.org/doc/man-pages/.
174
175
176
177GNU                               2021-03-22                           LIST(3)