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 SLIST_ENTRY(TYPE);
15 SLIST_HEAD(HEADNAME, TYPE);
17 SLIST_HEAD SLIST_HEAD_INITIALIZER(SLIST_HEAD head);
18 void SLIST_INIT(SLIST_HEAD *head);
19 int SLIST_EMPTY(SLIST_HEAD *head);
21 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 struct TYPE *SLIST_FIRST(SLIST_HEAD *head);
28 struct TYPE *SLIST_NEXT(struct TYPE *elm, SLIST_ENTRY NAME);
29 SLIST_FOREACH(struct TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME);
31 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
38 These macros define and operate on doubly linked lists.
39 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 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 SLIST_HEAD(HEADNAME, TYPE) head;
55 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 struct HEADNAME *headp;
61 (The names head and headp are user selectable.)
63 SLIST_ENTRY() declares a structure that connects the elements in the
65 list.
66 SLIST_HEAD_INITIALIZER() evaluates to an initializer for the list head.
68 SLIST_INIT() initializes the list referenced by head.
70 SLIST_EMPTY() evaluates to true if there are no elements in the list.
72 Insertion
74 SLIST_INSERT_HEAD() inserts the new element elm at the head of the
75 list.
76 SLIST_INSERT_AFTER() inserts the new element elm after the element lis‐
78 telm.
79 Traversal
81 SLIST_FIRST() returns the first element in the list, or NULL if the
82 list is empty.
83 SLIST_NEXT() returns the next element in the list.
85 SLIST_FOREACH() traverses the list referenced by head in the forward
87 direction, assigning each element in turn to var.
88 Removal
90 SLIST_REMOVE() removes the element elm from the list.
91 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
98 SLIST_EMPTY() returns nonzero if the list is empty, and zero if the
99 list contains at least one entry.
100 SLIST_FIRST(), and SLIST_NEXT() return a pointer to the first or next
102 TYPE structure, respectively.
103 SLIST_HEAD_INITIALIZER() returns an initializer that can be assigned to
105 the list head.
106
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
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
119 #include <stddef.h>
120 #include <stdio.h>
121 #include <stdlib.h>
122 #include <sys/queue.h>
123 struct entry {
125 int data;
126 SLIST_ENTRY(entry) entries; /* Singly linked list */
127 };
128 SLIST_HEAD(slisthead, entry);
130 int
132 main(void)
133 {
134 struct entry *n1, *n2, *n3, *np;
135 struct slisthead head; /* Singly linked list
136 head */
137 SLIST_INIT(&head); /* Initialize the queue */
139 n1 = malloc(sizeof(struct entry)); /* Insert at the head */
141 SLIST_INSERT_HEAD(&head, n1, entries);
142 n2 = malloc(sizeof(struct entry)); /* Insert after */
144 SLIST_INSERT_AFTER(n1, n2, entries);
145 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion */
147 free(n2);
148 n3 = SLIST_FIRST(&head);
150 SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head */
151 free(n3);
152 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 /* Forward traversal */
160 SLIST_FOREACH(np, &head, entries)
161 printf("%i\n", np->data);
162 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 exit(EXIT_SUCCESS);
171 }
172
174 insque(3), queue(7)
175
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/.
181GNU 2021-03-22 SLIST(3)