1SLIST(3) Linux Programmer's Manual SLIST(3)
2
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
12 #include <sys/queue.h>
13 int SLIST_EMPTY(SLIST_HEAD *head);
15 SLIST_ENTRY(TYPE);
17 struct TYPE *SLIST_FIRST(SLIST_HEAD *head);
19 SLIST_FOREACH(struct TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME);
21 SLIST_HEAD(HEADNAME, TYPE);
23 SLIST_HEAD SLIST_HEAD_INITIALIZER(SLIST_HEAD head);
25 void SLIST_INIT(SLIST_HEAD *head);
27 void SLIST_INSERT_AFTER(struct TYPE *listelm, struct TYPE *elm,
29 SLIST_ENTRY NAME);
30 void SLIST_INSERT_HEAD(SLIST_HEAD *head, struct TYPE *elm,
32 SLIST_ENTRY NAME);
33 struct TYPE *SLIST_NEXT(struct TYPE *elm, SLIST_ENTRY NAME);
35 void SLIST_REMOVE(SLIST_HEAD *head, struct TYPE *elm, SLIST_ENTRY NAME);
37 void SLIST_REMOVE_HEAD(SLIST_HEAD *head, SLIST_ENTRY NAME);
39
41 These macros define and operate on doubly linked lists.
42 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 A singly linked list is headed by a structure defined by the
49 SLIST_HEAD() macro. This structure contains a single pointer to the
50 first element on the list. The elements are singly linked for minimum
51 space and pointer manipulation overhead at the expense of O(n) removal
52 for arbitrary elements. New elements can be added to the list after an
53 existing element or at the head of the list. An SLIST_HEAD structure
54 is declared as follows:
55 SLIST_HEAD(HEADNAME, TYPE) head;
57 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 struct HEADNAME *headp;
63 (The names head and headp are user selectable.)
65 The macro SLIST_HEAD_INITIALIZER() evaluates to an initializer for the
67 list head.
68 The macro SLIST_EMPTY() evaluates to true if there are no elements in
70 the list.
71 The macro SLIST_ENTRY() declares a structure that connects the elements
73 in the list.
74 The macro SLIST_FIRST() returns the first element in the list or NULL
76 if the list is empty.
77 The macro SLIST_FOREACH() traverses the list referenced by head in the
79 forward direction, assigning each element in turn to var.
80 The macro SLIST_INIT() initializes the list referenced by head.
82 The macro SLIST_INSERT_HEAD() inserts the new element elm at the head
84 of the list.
85 The macro SLIST_INSERT_AFTER() inserts the new element elm after the
87 element listelm.
88 The macro SLIST_NEXT() returns the next element in the list.
90 The macro SLIST_REMOVE_HEAD() removes the element elm from the head of
92 the list. For optimum efficiency, elements being removed from the head
93 of the list should explicitly use this macro instead of the generic
94 SLIST_REMOVE macro.
95 The macro SLIST_REMOVE() removes the element elm from the list.
97
99 SLIST_EMPTY() returns nonzero if the list is empty, and zero if the
100 list contains at least one entry.
101 SLIST_FIRST(), and SLIST_NEXT() return a pointer to the first or next
103 TYPE structure, respectively.
104 SLIST_HEAD_INITIALIZER() returns an initializer that can be assigned to
106 the list head.
107
109 Not in POSIX.1, POSIX.1-2001 or POSIX.1-2008. Present on the BSDs
110 (SLIST macros first appeared in 4.4BSD).
111
113 The macro SLIST_FOREACH() doesn't allow var to be removed or freed
114 within the loop, as it would interfere with the traversal. The macro
115 SLIST_FOREACH_SAFE(), which is present on the BSDs but is not present
116 in glibc, fixes this limitation by allowing var to safely be removed
117 from the list and freed from within the loop without interfering with
118 the traversal.
119
121 #include <stddef.h>
122 #include <stdio.h>
123 #include <stdlib.h>
124 #include <sys/queue.h>
125 struct entry {
127 int data;
128 SLIST_ENTRY(entry) entries; /* Singly linked List. */
129 };
130 SLIST_HEAD(slisthead, entry);
132 int
134 main(void)
135 {
136 struct entry *n1, *n2, *n3, *np;
137 struct slisthead head; /* Singly linked List
138 head. */
139 SLIST_INIT(&head); /* Initialize the queue. */
141 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
143 SLIST_INSERT_HEAD(&head, n1, entries);
144 n2 = malloc(sizeof(struct entry)); /* Insert after. */
146 SLIST_INSERT_AFTER(n1, n2, entries);
147 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
149 free(n2);
150 n3 = SLIST_FIRST(&head);
152 SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */
153 free(n3);
154 for (int i = 0; i < 5; i++) {
156 n1 = malloc(sizeof(struct entry));
157 SLIST_INSERT_HEAD(&head, n1, entries);
158 n1->data = i;
159 }
160 /* Forward traversal. */
162 SLIST_FOREACH(np, &head, entries)
163 printf("%i\n", np->data);
164 while (!SLIST_EMPTY(&head)) { /* List Deletion. */
166 n1 = SLIST_FIRST(&head);
167 SLIST_REMOVE_HEAD(&head, entries);
168 free(n1);
169 }
170 SLIST_INIT(&head);
171 exit(EXIT_SUCCESS);
173 }
174
176 insque(3), queue(7)
177
179 This page is part of release 5.10 of the Linux man-pages project. A
180 description of the project, information about reporting bugs, and the
181 latest version of this page, can be found at
182 https://www.kernel.org/doc/man-pages/.
183GNU 2020-10-21 SLIST(3)