man3/circleq.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 CIRCLEQ 3 (date) "Linux man-pages (unreleased)"
   9 .SH NAME
  10 CIRCLEQ_EMPTY,
  11 CIRCLEQ_ENTRY,
  12 CIRCLEQ_FIRST,
  13 CIRCLEQ_FOREACH,
  14 CIRCLEQ_FOREACH_REVERSE,
  15 CIRCLEQ_HEAD,
  16 CIRCLEQ_HEAD_INITIALIZER,
  17 CIRCLEQ_INIT,
  18 CIRCLEQ_INSERT_AFTER,
  19 CIRCLEQ_INSERT_BEFORE,
  20 CIRCLEQ_INSERT_HEAD,
  21 CIRCLEQ_INSERT_TAIL,
  22 CIRCLEQ_LAST,
  23 CIRCLEQ_LOOP_NEXT,
  24 CIRCLEQ_LOOP_PREV,
  25 CIRCLEQ_NEXT,
  26 CIRCLEQ_PREV,
  27 CIRCLEQ_REMOVE
  28 \- implementation of a doubly linked circular queue
  29 .SH LIBRARY
  30 Standard C library
  31 .RI ( libc ", " \-lc )
  32 .SH SYNOPSIS
  33 .nf
  34 .B #include <sys/queue.h>
  35 .P
  36 .B CIRCLEQ_ENTRY(TYPE);
  37 .P
  38 .B CIRCLEQ_HEAD(HEADNAME, TYPE);
  39 .BI "CIRCLEQ_HEAD CIRCLEQ_HEAD_INITIALIZER(CIRCLEQ_HEAD " head );
  40 .BI "void CIRCLEQ_INIT(CIRCLEQ_HEAD *" head );
  41 .P
  42 .BI "int CIRCLEQ_EMPTY(CIRCLEQ_HEAD *" head );
  43 .P
  44 .BI "void CIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *" head ,
  45 .BI "                           struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
  46 .BI "void CIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *" head ,
  47 .BI "                           struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
  48 .BI "void CIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *" head ", struct TYPE *" listelm ,
  49 .BI "                           struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
  50 .BI "void CIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *" head ", struct TYPE *" listelm ,
  51 .BI "                           struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
  52 .P
  53 .BI "struct TYPE *CIRCLEQ_FIRST(CIRCLEQ_HEAD *" head );
  54 .BI "struct TYPE *CIRCLEQ_LAST(CIRCLEQ_HEAD *" head );
  55 .BI "struct TYPE *CIRCLEQ_PREV(struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
  56 .BI "struct TYPE *CIRCLEQ_NEXT(struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
  57 .BI "struct TYPE *CIRCLEQ_LOOP_PREV(CIRCLEQ_HEAD *" head ,
  58 .BI "                           struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
  59 .BI "struct TYPE *CIRCLEQ_LOOP_NEXT(CIRCLEQ_HEAD *" head ,
  60 .BI "                           struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
  61 .P
  62 .BI "CIRCLEQ_FOREACH(struct TYPE *" var ", CIRCLEQ_HEAD *" head ,
  63 .BI "                           CIRCLEQ_ENTRY " NAME );
  64 .BI "CIRCLEQ_FOREACH_REVERSE(struct TYPE *" var ", CIRCLEQ_HEAD *" head ,
  65 .BI "                           CIRCLEQ_ENTRY " NAME );
  66 .P
  67 .BI "void CIRCLEQ_REMOVE(CIRCLEQ_HEAD *" head ", struct TYPE *" elm ,
  68 .BI "                           CIRCLEQ_ENTRY " NAME );
  69 .fi
  70 .SH DESCRIPTION
  71 These macros define and operate on doubly linked circular queues.
  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 CIRCLEQ_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 CIRCLEQ_HEAD ().
  85 .SS Creation
  86 A circular queue is headed by a structure defined by the
  87 .BR CIRCLEQ_HEAD ()
  88 macro.
  89 This structure contains a pair of pointers,
  90 one to the first element in the queue
  91 and the other to the last element in the queue.
  92 The elements are doubly linked
  93 so that an arbitrary element can be removed without traversing the queue.
  94 New elements can be added to the queue
  95 after an existing element,
  96 before an existing element,
  97 at the head of the queue,
  98 or at the end of the queue.
  99 A
 100 .I CIRCLEQ_HEAD
 101 structure is declared as follows:
 102 .P
 103 .in +4
 104 .EX
 105 CIRCLEQ_HEAD(HEADNAME, TYPE) head;
 106 .EE
 107 .in
 108 .P
 109 where
 110 .I struct HEADNAME
 111 is the structure to be defined, and
 112 .I struct TYPE
 113 is the type of the elements to be linked into the queue.
 114 A pointer to the head of the queue can later be declared as:
 115 .P
 116 .in +4
 117 .EX
 118 struct HEADNAME *headp;
 119 .EE
 120 .in
 121 .P
 122 (The names
 123 .I head
 124 and
 125 .I headp
 126 are user selectable.)
 127 .P
 128 .BR CIRCLEQ_ENTRY ()
 129 declares a structure that connects the elements in the queue.
 130 .P
 131 .BR CIRCLEQ_HEAD_INITIALIZER ()
 132 evaluates to an initializer for the queue
 133 .IR head .
 134 .P
 135 .BR CIRCLEQ_INIT ()
 136 initializes the queue referenced by
 137 .IR head .
 138 .P
 139 .BR CIRCLEQ_EMPTY ()
 140 evaluates to true if there are no items on the queue.
 141 .SS Insertion
 142 .BR CIRCLEQ_INSERT_HEAD ()
 143 inserts the new element
 144 .I elm
 145 at the head of the queue.
 146 .P
 147 .BR CIRCLEQ_INSERT_TAIL ()
 148 inserts the new element
 149 .I elm
 150 at the end of the queue.
 151 .P
 152 .BR CIRCLEQ_INSERT_BEFORE ()
 153 inserts the new element
 154 .I elm
 155 before the element
 156 .IR listelm .
 157 .P
 158 .BR CIRCLEQ_INSERT_AFTER ()
 159 inserts the new element
 160 .I elm
 161 after the element
 162 .IR listelm .
 163 .SS Traversal
 164 .BR CIRCLEQ_FIRST ()
 165 returns the first item on the queue.
 166 .P
 167 .BR CIRCLEQ_LAST ()
 168 returns the last item on the queue.
 169 .P
 170 .BR CIRCLEQ_PREV ()
 171 returns the previous item on the queue, or
 172 .I &head
 173 if this item is the first one.
 174 .P
 175 .BR CIRCLEQ_NEXT ()
 176 returns the next item on the queue, or
 177 .I &head
 178 if this item is the last one.
 179 .P
 180 .BR CIRCLEQ_LOOP_PREV ()
 181 returns the previous item on the queue.
 182 If
 183 .I elm
 184 is the first element on the queue, the last element is returned.
 185 .P
 186 .BR CIRCLEQ_LOOP_NEXT ()
 187 returns the next item on the queue.
 188 If
 189 .I elm
 190 is the last element on the queue, the first element is returned.
 191 .P
 192 .BR CIRCLEQ_FOREACH ()
 193 traverses the queue referenced by
 194 .I head
 195 in the forward direction, assigning each element in turn to
 196 .IR var .
 197 .I var
 198 is set to
 199 .I &head
 200 if the loop completes normally, or if there were no elements.
 201 .P
 202 .BR CIRCLEQ_FOREACH_REVERSE ()
 203 traverses the queue referenced by
 204 .I head
 205 in the reverse direction,
 206 assigning each element in turn to
 207 .IR var .
 208 .SS Removal
 209 .BR CIRCLEQ_REMOVE ()
 210 removes the element
 211 .I elm
 212 from the queue.
 213 .SH RETURN VALUE
 214 .BR CIRCLEQ_EMPTY ()
 215 returns nonzero if the queue is empty,
 216 and zero if the queue contains at least one entry.
 217 .P
 218 .BR CIRCLEQ_FIRST (),
 219 .BR CIRCLEQ_LAST (),
 220 .BR CIRCLEQ_LOOP_PREV (),
 221 and
 222 .BR CIRCLEQ_LOOP_NEXT ()
 223 return a pointer to the first, last, previous, or next
 224 .I TYPE
 225 structure, respectively.
 226 .P
 227 .BR CIRCLEQ_PREV (),
 228 and
 229 .BR CIRCLEQ_NEXT ()
 230 are similar to their
 231 .BR CIRCLEQ_LOOP_* ()
 232 counterparts,
 233 except that if the argument is the first or last element, respectively,
 234 they return
 235 .IR &head .
 236 .P
 237 .BR CIRCLEQ_HEAD_INITIALIZER ()
 238 returns an initializer that can be assigned to the queue
 239 .IR head .
 240 .SH STANDARDS
 241 BSD.
 242 .SH BUGS
 243 .BR CIRCLEQ_FOREACH ()
 244 and
 245 .BR CIRCLEQ_FOREACH_REVERSE ()
 246 don't allow
 247 .I var
 248 to be removed or freed within the loop,
 249 as it would interfere with the traversal.
 250 .BR CIRCLEQ_FOREACH_SAFE ()
 251 and
 252 .BR CIRCLEQ_FOREACH_REVERSE_SAFE (),
 253 which are present on the BSDs but are not present in glibc,
 254 fix this limitation by allowing
 255 .I var
 256 to safely be removed from the list and freed from within the loop
 257 without interfering with the traversal.
 258 .SH EXAMPLES
 259 .\" SRC BEGIN (circleq.c)
 260 .EX
 261 #include <stddef.h>
 262 #include <stdio.h>
 263 #include <stdlib.h>
 264 #include <sys/queue.h>
 265 \&
 266 struct entry {
 267     int data;
 268     CIRCLEQ_ENTRY(entry) entries;           /* Queue */
 269 };
 270 \&
 271 CIRCLEQ_HEAD(circlehead, entry);
 272 \&
 273 int
 274 main(void)
 275 {
 276     struct entry *n1, *n2, *n3, *np;
 277     struct circlehead head;                 /* Queue head */
 278     int i;
 279 \&
 280     CIRCLEQ_INIT(&head);                    /* Initialize the queue */
 281 \&
 282     n1 = malloc(sizeof(struct entry));      /* Insert at the head */
 283     CIRCLEQ_INSERT_HEAD(&head, n1, entries);
 284 \&
 285     n1 = malloc(sizeof(struct entry));      /* Insert at the tail */
 286     CIRCLEQ_INSERT_TAIL(&head, n1, entries);
 287 \&
 288     n2 = malloc(sizeof(struct entry));      /* Insert after */
 289     CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
 290 \&
 291     n3 = malloc(sizeof(struct entry));      /* Insert before */
 292     CIRCLEQ_INSERT_BEFORE(&head, n2, n3, entries);
 293 \&
 294     CIRCLEQ_REMOVE(&head, n2, entries);     /* Deletion */
 295     free(n2);
 296                                             /* Forward traversal */
 297     i = 0;
 298     CIRCLEQ_FOREACH(np, &head, entries)
 299         np\->data = i++;
 300                                             /* Reverse traversal */
 301     CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
 302         printf("%i\en", np\->data);
 303                                             /* Queue deletion */
 304     n1 = CIRCLEQ_FIRST(&head);
 305     while (n1 != (void *)&head) {
 306         n2 = CIRCLEQ_NEXT(n1, entries);
 307         free(n1);
 308         n1 = n2;
 309     }
 310     CIRCLEQ_INIT(&head);
 311 \&
 312     exit(EXIT_SUCCESS);
 313 }
 314 .EE
 315 .\" SRC END
 316 .SH SEE ALSO
 317 .BR insque (3),
 318 .BR queue (7)