slist(3) - f38

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

LIBRARY

12       Standard C library (libc, -lc)
13

SYNOPSIS

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

DESCRIPTION

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

RETURN VALUE

101       SLIST_EMPTY()  returns  nonzero  if  the list is empty, and zero if the
102       list contains at least one entry.
103
104       SLIST_FIRST(), and SLIST_NEXT() return a pointer to the first  or  next
105       TYPE structure, respectively.
106
107       SLIST_HEAD_INITIALIZER() returns an initializer that can be assigned to
108       the list head.
109

STANDARDS

111       BSD.
112

HISTORY

114       4.4BSD.
115

BUGS

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

EXAMPLES

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