man3/slist.3

   1 .\" Copyright (c) 1993
   2 .\"    The Regents of the University of California.  All rights reserved.
   3 .\" and Copyright (c) 2020 by Alejandro Colomar <alx@kernel.org>
   4 .\"
   5 .\" SPDX-License-Identifier: BSD-3-Clause
   6 .\"
   7 .\"
   8 .TH SLIST 3 (date) "Linux man-pages (unreleased)"
   9 .SH NAME
  10 SLIST_EMPTY,
  11 SLIST_ENTRY,
  12 SLIST_FIRST,
  13 SLIST_FOREACH,
  14 .\"SLIST_FOREACH_FROM,
  15 .\"SLIST_FOREACH_FROM_SAFE,
  16 .\"SLIST_FOREACH_SAFE,
  17 SLIST_HEAD,
  18 SLIST_HEAD_INITIALIZER,
  19 SLIST_INIT,
  20 SLIST_INSERT_AFTER,
  21 SLIST_INSERT_HEAD,
  22 SLIST_NEXT,
  23 SLIST_REMOVE,
  24 .\"SLIST_REMOVE_AFTER,
  25 SLIST_REMOVE_HEAD
  26 .\"SLIST_SWAP
  27 \- implementation of a singly linked list
  28 .SH LIBRARY
  29 Standard C library
  30 .RI ( libc ", " \-lc )
  31 .SH SYNOPSIS
  32 .nf
  33 .B #include <sys/queue.h>
  34 .P
  35 .B SLIST_ENTRY(TYPE);
  36 .P
  37 .B SLIST_HEAD(HEADNAME, TYPE);
  38 .BI "SLIST_HEAD SLIST_HEAD_INITIALIZER(SLIST_HEAD " head );
  39 .BI "void SLIST_INIT(SLIST_HEAD *" head );
  40 .P
  41 .BI "int SLIST_EMPTY(SLIST_HEAD *" head );
  42 .P
  43 .BI "void SLIST_INSERT_HEAD(SLIST_HEAD *" head ,
  44 .BI "                        struct TYPE *" elm ", SLIST_ENTRY " NAME );
  45 .BI "void SLIST_INSERT_AFTER(struct TYPE *" listelm ,
  46 .BI "                        struct TYPE *" elm ", SLIST_ENTRY " NAME );
  47 .P
  48 .BI "struct TYPE *SLIST_FIRST(SLIST_HEAD *" head );
  49 .BI "struct TYPE *SLIST_NEXT(struct TYPE *" elm ", SLIST_ENTRY " NAME );
  50 .P
  51 .BI "SLIST_FOREACH(struct TYPE *" var ", SLIST_HEAD *" head ", SLIST_ENTRY " NAME );
  52 .\" .BI "SLIST_FOREACH_FROM(struct TYPE *" var ", SLIST_HEAD *" head ,
  53 .\" .BI "                        SLIST_ENTRY " NAME );
  54 .\" .P
  55 .\" .BI "SLIST_FOREACH_SAFE(struct TYPE *" var ", SLIST_HEAD *" head ,
  56 .\" .BI "                        SLIST_ENTRY " NAME ", struct TYPE *" temp_var );
  57 .\" .BI "SLIST_FOREACH_FROM_SAFE(struct TYPE *" var ", SLIST_HEAD *" head ,
  58 .\" .BI "                        SLIST_ENTRY " NAME ", struct TYPE *" temp_var );
  59 .P
  60 .BI "void SLIST_REMOVE(SLIST_HEAD *" head ", struct TYPE *" elm ,
  61 .BI "                        SLIST_ENTRY " NAME );
  62 .BI "void SLIST_REMOVE_HEAD(SLIST_HEAD *" head ,
  63 .BI "                        SLIST_ENTRY " NAME );
  64 .\" .BI "void SLIST_REMOVE_AFTER(struct TYPE *" elm ,
  65 .\" .BI "                        SLIST_ENTRY " NAME );
  66 .\" .P
  67 .\" .BI "void SLIST_SWAP(SLIST_HEAD *" head1 ", SLIST_HEAD *" head2 ,
  68 .\" .BI "                        SLIST_ENTRY " NAME );
  69 .fi
  70 .SH DESCRIPTION
  71 These macros define and operate on doubly linked lists.
  72 .P
  73 In the macro definitions,
  74 .I TYPE
  75 is the name of a user-defined structure,
  76 that must contain a field of type
  77 .IR SLIST_ENTRY ,
  78 named
  79 .IR NAME .
  80 The argument
  81 .I HEADNAME
  82 is the name of a user-defined structure
  83 that must be declared using the macro
  84 .BR SLIST_HEAD ().
  85 .SS Creation
  86 A singly linked list is headed by a structure defined by the
  87 .BR SLIST_HEAD ()
  88 macro.
  89 This structure contains a single pointer to the first element on the list.
  90 The elements are singly linked
  91 for minimum space and pointer manipulation overhead
  92 at the expense of O(n) removal for arbitrary elements.
  93 New elements can be added to the list
  94 after an existing element
  95 or at the head of the list.
  96 An
  97 .I SLIST_HEAD
  98 structure is declared as follows:
  99 .P
 100 .in +4
 101 .EX
 102 SLIST_HEAD(HEADNAME, TYPE) head;
 103 .EE
 104 .in
 105 .P
 106 where
 107 .I struct HEADNAME
 108 is the structure to be defined, and
 109 .I struct TYPE
 110 is the type of the elements to be linked into the list.
 111 A pointer to the head of the list can later be declared as:
 112 .P
 113 .in +4
 114 .EX
 115 struct HEADNAME *headp;
 116 .EE
 117 .in
 118 .P
 119 (The names
 120 .I head
 121 and
 122 .I headp
 123 are user selectable.)
 124 .P
 125 .BR SLIST_ENTRY ()
 126 declares a structure that connects the elements in
 127 the list.
 128 .P
 129 .BR SLIST_HEAD_INITIALIZER ()
 130 evaluates to an initializer for the list
 131 .IR head .
 132 .P
 133 .BR SLIST_INIT ()
 134 initializes the list referenced by
 135 .IR head .
 136 .P
 137 .BR SLIST_EMPTY ()
 138 evaluates to true if there are no elements in the list.
 139 .SS Insertion
 140 .BR SLIST_INSERT_HEAD ()
 141 inserts the new element
 142 .I elm
 143 at the head of the list.
 144 .P
 145 .BR SLIST_INSERT_AFTER ()
 146 inserts the new element
 147 .I elm
 148 after the element
 149 .IR listelm .
 150 .SS Traversal
 151 .BR SLIST_FIRST ()
 152 returns the first element in the list, or NULL if the list is empty.
 153 .P
 154 .BR SLIST_NEXT ()
 155 returns the next element in the list.
 156 .P
 157 .BR SLIST_FOREACH ()
 158 traverses the list referenced by
 159 .I head
 160 in the forward direction,
 161 assigning each element in turn to
 162 .IR var .
 163 .\" .P
 164 .\" .BR SLIST_FOREACH_FROM ()
 165 .\" behaves identically to
 166 .\" .BR SLIST_FOREACH ()
 167 .\" when
 168 .\" .I var
 169 .\" is NULL, else it treats
 170 .\" .I var
 171 .\" as a previously found SLIST element and begins the loop at
 172 .\" .I var
 173 .\" instead of the first element in the SLIST referenced by
 174 .\" .IR head .
 175 .\" .Pp
 176 .\" .BR SLIST_FOREACH_SAFE ()
 177 .\" traverses the list referenced by
 178 .\" .I head
 179 .\" in the forward direction, assigning each element in
 180 .\" turn to
 181 .\" .IR var .
 182 .\" However, unlike
 183 .\" .BR SLIST_FOREACH ()
 184 .\" here it is permitted to both remove
 185 .\" .I var
 186 .\" as well as free it from within the loop safely without interfering with the
 187 .\" traversal.
 188 .\" .P
 189 .\" .BR SLIST_FOREACH_FROM_SAFE ()
 190 .\" behaves identically to
 191 .\" .BR SLIST_FOREACH_SAFE ()
 192 .\" when
 193 .\" .I var
 194 .\" is NULL, else it treats
 195 .\" .I var
 196 .\" as a previously found SLIST element and begins the loop at
 197 .\" .I var
 198 .\" instead of the first element in the SLIST referenced by
 199 .\" .IR head .
 200 .SS Removal
 201 .BR SLIST_REMOVE ()
 202 removes the element
 203 .I elm
 204 from the list.
 205 .P
 206 .BR SLIST_REMOVE_HEAD ()
 207 removes the element
 208 .I elm
 209 from the head of the list.
 210 For optimum efficiency,
 211 elements being removed from the head of the list
 212 should explicitly use this macro instead of the generic
 213 .BR SLIST_REMOVE ().
 214 .\" .P
 215 .\" .BR SLIST_REMOVE_AFTER ()
 216 .\" removes the element after
 217 .\" .I elm
 218 .\" from the list.
 219 .\" Unlike
 220 .\" .IR SLIST_REMOVE ,
 221 .\" this macro does not traverse the entire list.
 222 .\" .SS Other features
 223 .\" .BR SLIST_SWAP ()
 224 .\" swaps the contents of
 225 .\" .I head1
 226 .\" and
 227 .\" .IR head2 .
 228 .SH RETURN VALUE
 229 .BR SLIST_EMPTY ()
 230 returns nonzero if the list is empty,
 231 and zero if the list contains at least one entry.
 232 .P
 233 .BR SLIST_FIRST (),
 234 and
 235 .BR SLIST_NEXT ()
 236 return a pointer to the first or next
 237 .I TYPE
 238 structure, respectively.
 239 .P
 240 .BR SLIST_HEAD_INITIALIZER ()
 241 returns an initializer that can be assigned to the list
 242 .IR head .
 243 .SH STANDARDS
 244 BSD.
 245 .SH HISTORY
 246 4.4BSD.
 247 .SH BUGS
 248 .BR SLIST_FOREACH ()
 249 doesn't allow
 250 .I var
 251 to be removed or freed within the loop,
 252 as it would interfere with the traversal.
 253 .BR SLIST_FOREACH_SAFE (),
 254 which is present on the BSDs but is not present in glibc,
 255 fixes this limitation by allowing
 256 .I var
 257 to safely be removed from the list and freed from within the loop
 258 without interfering with the traversal.
 259 .SH EXAMPLES
 260 .\" SRC BEGIN (slist.c)
 261 .EX
 262 #include <stddef.h>
 263 #include <stdio.h>
 264 #include <stdlib.h>
 265 #include <sys/queue.h>
 266 \&
 267 struct entry {
 268     int data;
 269     SLIST_ENTRY(entry) entries;             /* Singly linked list */
 270 };
 271 \&
 272 SLIST_HEAD(slisthead, entry);
 273 \&
 274 int
 275 main(void)
 276 {
 277     struct entry *n1, *n2, *n3, *np;
 278     struct slisthead head;                  /* Singly linked list
 279                                                head */
 280 \&
 281     SLIST_INIT(&head);                      /* Initialize the queue */
 282 \&
 283     n1 = malloc(sizeof(struct entry));      /* Insert at the head */
 284     SLIST_INSERT_HEAD(&head, n1, entries);
 285 \&
 286     n2 = malloc(sizeof(struct entry));      /* Insert after */
 287     SLIST_INSERT_AFTER(n1, n2, entries);
 288 \&
 289     SLIST_REMOVE(&head, n2, entry, entries);/* Deletion */
 290     free(n2);
 291 \&
 292     n3 = SLIST_FIRST(&head);
 293     SLIST_REMOVE_HEAD(&head, entries);      /* Deletion from the head */
 294     free(n3);
 295 \&
 296     for (unsigned int i = 0; i < 5; i++) {
 297         n1 = malloc(sizeof(struct entry));
 298         SLIST_INSERT_HEAD(&head, n1, entries);
 299         n1\->data = i;
 300     }
 301 \&
 302                                             /* Forward traversal */
 303     SLIST_FOREACH(np, &head, entries)
 304         printf("%i\en", np\->data);
 305 \&
 306     while (!SLIST_EMPTY(&head)) {           /* List deletion */
 307         n1 = SLIST_FIRST(&head);
 308         SLIST_REMOVE_HEAD(&head, entries);
 309         free(n1);
 310     }
 311     SLIST_INIT(&head);
 312 \&
 313     exit(EXIT_SUCCESS);
 314 }
 315 .EE
 316 .\" SRC END
 317 .SH SEE ALSO
 318 .BR insque (3),
 319 .BR queue (7)