LIST_INSERT_BEFORE(3)

1LIST(3)                    Library Functions 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

LIBRARY

12       Standard C library (libc, -lc)
13

SYNOPSIS

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

DESCRIPTION

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

RETURN VALUE

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

STANDARDS

107       BSD.
108

HISTORY

110       4.4BSD.
111

BUGS

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