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 <colomar.6.4.3@gmail.com>
   4 .\"
   5 .\" %%%LICENSE_START(BSD_3_CLAUSE_UCB)
   6 .\" Redistribution and use in source and binary forms, with or without
   7 .\" modification, are permitted provided that the following conditions
   8 .\" are met:
   9 .\" 1. Redistributions of source code must retain the above copyright
  10 .\"    notice, this list of conditions and the following disclaimer.
  11 .\" 2. Redistributions in binary form must reproduce the above copyright
  12 .\"    notice, this list of conditions and the following disclaimer in the
  13 .\"    documentation and/or other materials provided with the distribution.
  14 .\" 3. Neither the name of the University nor the names of its contributors
  15 .\"    may be used to endorse or promote products derived from this software
  16 .\"    without specific prior written permission.
  17 .\"
  18 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  19 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  21 .\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  22 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  23 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  24 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  25 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  26 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  27 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  28 .\" SUCH DAMAGE.
  29 .\" %%%LICENSE_END
  30 .\"
  31 .\"
  32 .TH SLIST 3 2021-03-22 "GNU" "Linux Programmer's Manual"
  33 .SH NAME
  34 SLIST_EMPTY,
  35 SLIST_ENTRY,
  36 SLIST_FIRST,
  37 SLIST_FOREACH,
  38 .\"SLIST_FOREACH_FROM,
  39 .\"SLIST_FOREACH_FROM_SAFE,
  40 .\"SLIST_FOREACH_SAFE,
  41 SLIST_HEAD,
  42 SLIST_HEAD_INITIALIZER,
  43 SLIST_INIT,
  44 SLIST_INSERT_AFTER,
  45 SLIST_INSERT_HEAD,
  46 SLIST_NEXT,
  47 SLIST_REMOVE,
  48 .\"SLIST_REMOVE_AFTER,
  49 SLIST_REMOVE_HEAD
  50 .\"SLIST_SWAP
  51 \- implementation of a singly linked list
  52 .SH SYNOPSIS
  53 .nf
  54 .B #include <sys/queue.h>
  55 .PP
  56 .B SLIST_ENTRY(TYPE);
  57 .PP
  58 .B SLIST_HEAD(HEADNAME, TYPE);
  59 .BI "SLIST_HEAD SLIST_HEAD_INITIALIZER(SLIST_HEAD " head );
  60 .BI "void SLIST_INIT(SLIST_HEAD *" head );
  61 .PP
  62 .BI "int SLIST_EMPTY(SLIST_HEAD *" head );
  63 .PP
  64 .BI "void SLIST_INSERT_HEAD(SLIST_HEAD *" head ,
  65 .BI "                        struct TYPE *" elm ", SLIST_ENTRY " NAME );
  66 .BI "void SLIST_INSERT_AFTER(struct TYPE *" listelm ,
  67 .BI "                        struct TYPE *" elm ", SLIST_ENTRY " NAME );
  68 .PP
  69 .BI "struct TYPE *SLIST_FIRST(SLIST_HEAD *" head );
  70 .BI "struct TYPE *SLIST_NEXT(struct TYPE *" elm ", SLIST_ENTRY " NAME );
  71 .PP
  72 .BI "SLIST_FOREACH(struct TYPE *" var ", SLIST_HEAD *" head ", SLIST_ENTRY " NAME );
  73 .\" .BI "SLIST_FOREACH_FROM(struct TYPE *" var ", SLIST_HEAD *" head ,
  74 .\" .BI "                        SLIST_ENTRY " NAME );
  75 .\" .PP
  76 .\" .BI "SLIST_FOREACH_SAFE(struct TYPE *" var ", SLIST_HEAD *" head ,
  77 .\" .BI "                        SLIST_ENTRY " NAME ", struct TYPE *" temp_var );
  78 .\" .BI "SLIST_FOREACH_FROM_SAFE(struct TYPE *" var ", SLIST_HEAD *" head ,
  79 .\" .BI "                        SLIST_ENTRY " NAME ", struct TYPE *" temp_var );
  80 .PP
  81 .BI "void SLIST_REMOVE(SLIST_HEAD *" head ", struct TYPE *" elm ,
  82 .BI "                        SLIST_ENTRY " NAME );
  83 .BI "void SLIST_REMOVE_HEAD(SLIST_HEAD *" head ,
  84 .BI "                        SLIST_ENTRY " NAME );
  85 .\" .BI "void SLIST_REMOVE_AFTER(struct TYPE *" elm ,
  86 .\" .BI "                        SLIST_ENTRY " NAME );
  87 .\" .PP
  88 .\" .BI "void SLIST_SWAP(SLIST_HEAD *" head1 ", SLIST_HEAD *" head2 ,
  89 .\" .BI "                        SLIST_ENTRY " NAME );
  90 .fi
  91 .SH DESCRIPTION
  92 These macros define and operate on doubly linked lists.
  93 .PP
  94 In the macro definitions,
  95 .I TYPE
  96 is the name of a user-defined structure,
  97 that must contain a field of type
  98 .IR SLIST_ENTRY ,
  99 named
 100 .IR NAME .
 101 The argument
 102 .IR HEADNAME
 103 is the name of a user-defined structure
 104 that must be declared using the macro
 105 .BR SLIST_HEAD ().
 106 .SS Creation
 107 A singly linked list is headed by a structure defined by the
 108 .BR SLIST_HEAD ()
 109 macro.
 110 This structure contains a single pointer to the first element on the list.
 111 The elements are singly linked
 112 for minimum space and pointer manipulation overhead
 113 at the expense of O(n) removal for arbitrary elements.
 114 New elements can be added to the list
 115 after an existing element
 116 or at the head of the list.
 117 An
 118 .I SLIST_HEAD
 119 structure is declared as follows:
 120 .PP
 121 .in +4
 122 .EX
 123 SLIST_HEAD(HEADNAME, TYPE) head;
 124 .EE
 125 .in
 126 .PP
 127 where
 128 .I struct HEADNAME
 129 is the structure to be defined, and
 130 .I struct TYPE
 131 is the type of the elements to be linked into the list.
 132 A pointer to the head of the list can later be declared as:
 133 .PP
 134 .in +4
 135 .EX
 136 struct HEADNAME *headp;
 137 .EE
 138 .in
 139 .PP
 140 (The names
 141 .I head
 142 and
 143 .I headp
 144 are user selectable.)
 145 .PP
 146 .BR SLIST_ENTRY ()
 147 declares a structure that connects the elements in
 148 the list.
 149 .PP
 150 .BR SLIST_HEAD_INITIALIZER ()
 151 evaluates to an initializer for the list
 152 .IR head .
 153 .PP
 154 .BR SLIST_INIT ()
 155 initializes the list referenced by
 156 .IR head .
 157 .PP
 158 .BR SLIST_EMPTY ()
 159 evaluates to true if there are no elements in the list.
 160 .SS Insertion
 161 .BR SLIST_INSERT_HEAD ()
 162 inserts the new element
 163 .I elm
 164 at the head of the list.
 165 .PP
 166 .BR SLIST_INSERT_AFTER ()
 167 inserts the new element
 168 .I elm
 169 after the element
 170 .IR listelm .
 171 .SS Traversal
 172 .BR SLIST_FIRST ()
 173 returns the first element in the list, or NULL if the list is empty.
 174 .PP
 175 .BR SLIST_NEXT ()
 176 returns the next element in the list.
 177 .PP
 178 .BR SLIST_FOREACH ()
 179 traverses the list referenced by
 180 .I head
 181 in the forward direction,
 182 assigning each element in turn to
 183 .IR var .
 184 .\" .PP
 185 .\" .BR SLIST_FOREACH_FROM ()
 186 .\" behaves identically to
 187 .\" .BR SLIST_FOREACH ()
 188 .\" when
 189 .\" .I var
 190 .\" is NULL, else it treats
 191 .\" .I var
 192 .\" as a previously found SLIST element and begins the loop at
 193 .\" .I var
 194 .\" instead of the first element in the SLIST referenced by
 195 .\" .IR head .
 196 .\" .Pp
 197 .\" .BR SLIST_FOREACH_SAFE ()
 198 .\" traverses the list referenced by
 199 .\" .I head
 200 .\" in the forward direction, assigning each element in
 201 .\" turn to
 202 .\" .IR var .
 203 .\" However, unlike
 204 .\" .BR SLIST_FOREACH ()
 205 .\" here it is permitted to both remove
 206 .\" .I var
 207 .\" as well as free it from within the loop safely without interfering with the
 208 .\" traversal.
 209 .\" .PP
 210 .\" .BR SLIST_FOREACH_FROM_SAFE ()
 211 .\" behaves identically to
 212 .\" .BR SLIST_FOREACH_SAFE ()
 213 .\" when
 214 .\" .I var
 215 .\" is NULL, else it treats
 216 .\" .I var
 217 .\" as a previously found SLIST element and begins the loop at
 218 .\" .I var
 219 .\" instead of the first element in the SLIST referenced by
 220 .\" .IR head .
 221 .SS Removal
 222 .BR SLIST_REMOVE ()
 223 removes the element
 224 .I elm
 225 from the list.
 226 .PP
 227 .BR SLIST_REMOVE_HEAD ()
 228 removes the element
 229 .I elm
 230 from the head of the list.
 231 For optimum efficiency,
 232 elements being removed from the head of the list
 233 should explicitly use this macro instead of the generic
 234 .BR SLIST_REMOVE ().
 235 .\" .PP
 236 .\" .BR SLIST_REMOVE_AFTER ()
 237 .\" removes the element after
 238 .\" .I elm
 239 .\" from the list.
 240 .\" Unlike
 241 .\" .IR SLIST_REMOVE ,
 242 .\" this macro does not traverse the entire list.
 243 .\" .SS Other features
 244 .\" .BR SLIST_SWAP ()
 245 .\" swaps the contents of
 246 .\" .I head1
 247 .\" and
 248 .\" .IR head2 .
 249 .SH RETURN VALUE
 250 .BR SLIST_EMPTY ()
 251 returns nonzero if the list is empty,
 252 and zero if the list contains at least one entry.
 253 .PP
 254 .BR SLIST_FIRST (),
 255 and
 256 .BR SLIST_NEXT ()
 257 return a pointer to the first or next
 258 .I TYPE
 259 structure, respectively.
 260 .PP
 261 .BR SLIST_HEAD_INITIALIZER ()
 262 returns an initializer that can be assigned to the list
 263 .IR head .
 264 .SH CONFORMING TO
 265 Not in POSIX.1, POSIX.1-2001, or POSIX.1-2008.
 266 Present on the BSDs
 267 (SLIST macros first appeared in 4.4BSD).
 268 .SH BUGS
 269 .BR SLIST_FOREACH ()
 270 doesn't allow
 271 .I var
 272 to be removed or freed within the loop,
 273 as it would interfere with the traversal.
 274 .BR SLIST_FOREACH_SAFE (),
 275 which is present on the BSDs but is not present in glibc,
 276 fixes this limitation by allowing
 277 .I var
 278 to safely be removed from the list and freed from within the loop
 279 without interfering with the traversal.
 280 .SH EXAMPLES
 281 .EX
 282 #include <stddef.h>
 283 #include <stdio.h>
 284 #include <stdlib.h>
 285 #include <sys/queue.h>
 286
 287 struct entry {
 288     int data;
 289     SLIST_ENTRY(entry) entries;             /* Singly linked list */
 290 };
 291
 292 SLIST_HEAD(slisthead, entry);
 293
 294 int
 295 main(void)
 296 {
 297     struct entry *n1, *n2, *n3, *np;
 298     struct slisthead head;                  /* Singly linked list
 299                                                head */
 300
 301     SLIST_INIT(&head);                      /* Initialize the queue */
 302
 303     n1 = malloc(sizeof(struct entry));      /* Insert at the head */
 304     SLIST_INSERT_HEAD(&head, n1, entries);
 305
 306     n2 = malloc(sizeof(struct entry));      /* Insert after */
 307     SLIST_INSERT_AFTER(n1, n2, entries);
 308
 309     SLIST_REMOVE(&head, n2, entry, entries);/* Deletion */
 310     free(n2);
 311
 312     n3 = SLIST_FIRST(&head);
 313     SLIST_REMOVE_HEAD(&head, entries);      /* Deletion from the head */
 314     free(n3);
 315
 316     for (int i = 0; i < 5; i++) {
 317         n1 = malloc(sizeof(struct entry));
 318         SLIST_INSERT_HEAD(&head, n1, entries);
 319         n1\->data = i;
 320     }
 321
 322                                             /* Forward traversal */
 323     SLIST_FOREACH(np, &head, entries)
 324         printf("%i\en", np\->data);
 325
 326     while (!SLIST_EMPTY(&head)) {           /* List deletion */
 327         n1 = SLIST_FIRST(&head);
 328         SLIST_REMOVE_HEAD(&head, entries);
 329         free(n1);
 330     }
 331     SLIST_INIT(&head);
 332
 333     exit(EXIT_SUCCESS);
 334 }
 335 .EE
 336 .SH SEE ALSO
 337 .BR insque (3),
 338 .BR queue (7)