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

NAME

6       SLIST_EMPTY,   SLIST_ENTRY,   SLIST_FIRST,  SLIST_FOREACH,  SLIST_HEAD,
7       SLIST_HEAD_INITIALIZER,   SLIST_INIT,   SLIST_INSERT_AFTER,   SLIST_IN‐
8       SERT_HEAD, SLIST_NEXT, SLIST_REMOVE, SLIST_REMOVE_HEAD - implementation
9       of a singly linked list
10

SYNOPSIS

12       #include <sys/queue.h>
13
14       SLIST_ENTRY(TYPE);
15
16       SLIST_HEAD(HEADNAME, TYPE);
17       SLIST_HEAD SLIST_HEAD_INITIALIZER(SLIST_HEAD head);
18       void SLIST_INIT(SLIST_HEAD *head);
19
20       int SLIST_EMPTY(SLIST_HEAD *head);
21
22       void SLIST_INSERT_HEAD(SLIST_HEAD *head,
23                               struct TYPE *elm, SLIST_ENTRY NAME);
24       void SLIST_INSERT_AFTER(struct TYPE *listelm,
25                               struct TYPE *elm, SLIST_ENTRY NAME);
26
27       struct TYPE *SLIST_FIRST(SLIST_HEAD *head);
28       struct TYPE *SLIST_NEXT(struct TYPE *elm, SLIST_ENTRY NAME);
29
30       SLIST_FOREACH(struct TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME);
31
32       void SLIST_REMOVE(SLIST_HEAD *head, struct TYPE *elm,
33                               SLIST_ENTRY NAME);
34       void SLIST_REMOVE_HEAD(SLIST_HEAD *head,
35                               SLIST_ENTRY NAME);
36

DESCRIPTION

38       These macros define and operate on doubly linked lists.
39
40       In the macro definitions, TYPE is the name of a user-defined structure,
41       that  must  contain a field of type SLIST_ENTRY, named NAME.  The argu‐
42       ment HEADNAME is the name of a user-defined structure that must be  de‐
43       clared using the macro SLIST_HEAD().
44
45   Creation
46       A  singly  linked  list  is  headed  by  a  structure  defined  by  the
47       SLIST_HEAD() macro.  This structure contains a single  pointer  to  the
48       first  element on the list.  The elements are singly linked for minimum
49       space and pointer manipulation overhead at the expense of O(n)  removal
50       for arbitrary elements.  New elements can be added to the list after an
51       existing element or at the head of the list.  An  SLIST_HEAD  structure
52       is declared as follows:
53
54           SLIST_HEAD(HEADNAME, TYPE) head;
55
56       where  struct  HEADNAME is the structure to be defined, and struct TYPE
57       is the type of the elements to be linked into the list.  A  pointer  to
58       the head of the list can later be declared as:
59
60           struct HEADNAME *headp;
61
62       (The names head and headp are user selectable.)
63
64       SLIST_ENTRY()  declares  a  structure that connects the elements in the
65       list.
66
67       SLIST_HEAD_INITIALIZER() evaluates to an initializer for the list head.
68
69       SLIST_INIT() initializes the list referenced by head.
70
71       SLIST_EMPTY() evaluates to true if there are no elements in the list.
72
73   Insertion
74       SLIST_INSERT_HEAD() inserts the new element elm  at  the  head  of  the
75       list.
76
77       SLIST_INSERT_AFTER() inserts the new element elm after the element lis‐
78       telm.
79
80   Traversal
81       SLIST_FIRST() returns the first element in the list,  or  NULL  if  the
82       list is empty.
83
84       SLIST_NEXT() returns the next element in the list.
85
86       SLIST_FOREACH()  traverses  the  list referenced by head in the forward
87       direction, assigning each element in turn to var.
88
89   Removal
90       SLIST_REMOVE() removes the element elm from the list.
91
92       SLIST_REMOVE_HEAD() removes the element elm from the head of the  list.
93       For  optimum  efficiency,  elements  being removed from the head of the
94       list should explicitly use this macro instead of the generic  SLIST_RE‐
95       MOVE().
96

RETURN VALUE

98       SLIST_EMPTY()  returns  nonzero  if  the list is empty, and zero if the
99       list contains at least one entry.
100
101       SLIST_FIRST(), and SLIST_NEXT() return a pointer to the first  or  next
102       TYPE structure, respectively.
103
104       SLIST_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       (SLIST macros first appeared in 4.4BSD).
110

BUGS

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

EXAMPLES

119       #include <stddef.h>
120       #include <stdio.h>
121       #include <stdlib.h>
122       #include <sys/queue.h>
123
124       struct entry {
125           int data;
126           SLIST_ENTRY(entry) entries;             /* Singly linked list */
127       };
128
129       SLIST_HEAD(slisthead, entry);
130
131       int
132       main(void)
133       {
134           struct entry *n1, *n2, *n3, *np;
135           struct slisthead head;                  /* Singly linked list
136                                                      head */
137
138           SLIST_INIT(&head);                      /* Initialize the queue */
139
140           n1 = malloc(sizeof(struct entry));      /* Insert at the head */
141           SLIST_INSERT_HEAD(&head, n1, entries);
142
143           n2 = malloc(sizeof(struct entry));      /* Insert after */
144           SLIST_INSERT_AFTER(n1, n2, entries);
145
146           SLIST_REMOVE(&head, n2, entry, entries);/* Deletion */
147           free(n2);
148
149           n3 = SLIST_FIRST(&head);
150           SLIST_REMOVE_HEAD(&head, entries);      /* Deletion from the head */
151           free(n3);
152
153           for (int i = 0; i < 5; i++) {
154               n1 = malloc(sizeof(struct entry));
155               SLIST_INSERT_HEAD(&head, n1, entries);
156               n1->data = i;
157           }
158
159                                                   /* Forward traversal */
160           SLIST_FOREACH(np, &head, entries)
161               printf("%i\n", np->data);
162
163           while (!SLIST_EMPTY(&head)) {           /* List deletion */
164               n1 = SLIST_FIRST(&head);
165               SLIST_REMOVE_HEAD(&head, entries);
166               free(n1);
167           }
168           SLIST_INIT(&head);
169
170           exit(EXIT_SUCCESS);
171       }
172

SEE ALSO

174       insque(3), queue(7)
175

COLOPHON

177       This  page  is  part of release 5.12 of the Linux man-pages project.  A
178       description of the project, information about reporting bugs,  and  the
179       latest     version     of     this    page,    can    be    found    at
180       https://www.kernel.org/doc/man-pages/.
181
182
183
184GNU                               2021-03-22                          SLIST(3)
Impressum