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