man3/insque.3

   1 .\" peter memishian -- meem@gnu.ai.mit.edu
   2 .\" $Id: insque.3,v 1.2 1996/10/30 21:03:39 meem Exp meem $
   3 .\" and Copyright (c) 2010, Michael Kerrisk <mtk.manpages@gmail.com>
   4 .\"
   5 .\" %%%LICENSE_START(VERBATIM)
   6 .\" Permission is granted to make and distribute verbatim copies of this
   7 .\" manual provided the copyright notice and this permission notice are
   8 .\" preserved on all copies.
   9 .\"
  10 .\" Permission is granted to copy and distribute modified versions of this
  11 .\" manual under the conditions for verbatim copying, provided that the
  12 .\" entire resulting derived work is distributed under the terms of a
  13 .\" permission notice identical to this one.
  14 .\"
  15 .\" Since the Linux kernel and libraries are constantly changing, this
  16 .\" manual page may be incorrect or out-of-date.  The author(s) assume no
  17 .\" responsibility for errors or omissions, or for damages resulting from
  18 .\" the use of the information contained herein.  The author(s) may not
  19 .\" have taken the same level of care in the production of this manual,
  20 .\" which is licensed free of charge, as they might when working
  21 .\" professionally.
  22 .\"
  23 .\" Formatted or processed versions of this manual, if unaccompanied by
  24 .\" the source, must acknowledge the copyright and authors of this work.
  25 .\" %%%LICENSE_END
  26 .\"
  27 .\" References consulted:
  28 .\"   Linux libc source code (5.4.7)
  29 .\"   Solaris 2.x, OSF/1, and HP-UX manpages
  30 .\"   Curry's "UNIX Systems Programming for SVR4" (O'Reilly & Associates 1996)
  31 .\"
  32 .\" Changed to POSIX, 2003-08-11, aeb+wh
  33 .\" mtk, 2010-09-09: Noted glibc 2.4 bug, added info on circular
  34 .\"     lists, added example program
  35 .\"
  36 .TH INSQUE 3  2021-03-22 "" "Linux Programmer's Manual"
  37 .SH NAME
  38 insque, remque \- insert/remove an item from a queue
  39 .SH SYNOPSIS
  40 .nf
  41 .B #include <search.h>
  42 .PP
  43 .BI "void insque(void *" elem ", void *" prev );
  44 .BI "void remque(void *" elem );
  45 .fi
  46 .PP
  47 .RS -4
  48 Feature Test Macro Requirements for glibc (see
  49 .BR feature_test_macros (7)):
  50 .RE
  51 .PP
  52 .BR insque (),
  53 .BR remque ():
  54 .nf
  55     _XOPEN_SOURCE >= 500
  56 .\"    || _XOPEN_SOURCE && _XOPEN_SOURCE_EXTENDED
  57         || /* Glibc since 2.19: */ _DEFAULT_SOURCE
  58         || /* Glibc <= 2.19: */ _SVID_SOURCE
  59 .fi
  60 .SH DESCRIPTION
  61 The
  62 .BR insque ()
  63 and
  64 .BR remque ()
  65 functions manipulate doubly linked lists.
  66 Each element in the list is a structure of
  67 which the first two elements are a forward and a
  68 backward pointer.
  69 The linked list may be linear (i.e., NULL forward pointer at
  70 the end of the list and NULL backward pointer at the start of the list)
  71 or circular.
  72 .PP
  73 The
  74 .BR insque ()
  75 function inserts the element pointed to by \fIelem\fP
  76 immediately after the element pointed to by \fIprev\fP.
  77 .PP
  78 If the list is linear, then the call
  79 .I "insque(elem, NULL)"
  80 can be used to insert the initial list element,
  81 and the call sets the forward and backward pointers of
  82 .I elem
  83 to NULL.
  84 .PP
  85 If the list is circular,
  86 the caller should ensure that the forward and backward pointers of the
  87 first element are initialized to point to that element,
  88 and the
  89 .I prev
  90 argument of the
  91 .BR insque ()
  92 call should also point to the element.
  93 .PP
  94 The
  95 .BR remque ()
  96 function removes the element pointed to by \fIelem\fP from the
  97 doubly linked list.
  98 .SH ATTRIBUTES
  99 For an explanation of the terms used in this section, see
 100 .BR attributes (7).
 101 .ad l
 102 .nh
 103 .TS
 104 allbox;
 105 lbx lb lb
 106 l l l.
 107 Interface       Attribute       Value
 108 T{
 109 .BR insque (),
 110 .BR remque ()
 111 T}      Thread safety   MT-Safe
 112 .TE
 113 .hy
 114 .ad
 115 .sp 1
 116 .SH CONFORMING TO
 117 POSIX.1-2001, POSIX.1-2008.
 118 .SH NOTES
 119 On ancient systems,
 120 .\" e.g., SunOS, Linux libc4 and libc5
 121 the arguments of these functions were of type \fIstruct qelem *\fP,
 122 defined as:
 123 .PP
 124 .in +4n
 125 .EX
 126 struct qelem {
 127     struct qelem *q_forw;
 128     struct qelem *q_back;
 129     char          q_data[1];
 130 };
 131 .EE
 132 .in
 133 .PP
 134 This is still what you will get if
 135 .B _GNU_SOURCE
 136 is defined before
 137 including \fI<search.h>\fP.
 138 .PP
 139 The location of the prototypes for these functions differs among several
 140 versions of UNIX.
 141 The above is the POSIX version.
 142 Some systems place them in \fI<string.h>\fP.
 143 .\" Linux libc4 and libc 5 placed them
 144 .\" in \fI<stdlib.h>\fP.
 145 .SH BUGS
 146 In glibc 2.4 and earlier, it was not possible to specify
 147 .I prev
 148 as NULL.
 149 Consequently, to build a linear list, the caller had to build a list
 150 using an initial call that contained the first two elements of the list,
 151 with the forward and backward pointers in each element suitably initialized.
 152 .SH EXAMPLES
 153 The program below demonstrates the use of
 154 .BR insque ().
 155 Here is an example run of the program:
 156 .PP
 157 .in +4n
 158 .EX
 159 .RB "$ " "./a.out \-c a b c"
 160 Traversing completed list:
 161     a
 162     b
 163     c
 164 That was a circular list
 165 .EE
 166 .in
 167 .SS Program source
 168 \&
 169 .EX
 170 #include <stdio.h>
 171 #include <stdlib.h>
 172 #include <unistd.h>
 173 #include <search.h>
 174
 175 struct element {
 176     struct element *forward;
 177     struct element *backward;
 178     char *name;
 179 };
 180
 181 static struct element *
 182 new_element(void)
 183 {
 184     struct element *e = malloc(sizeof(*e));
 185     if (e == NULL) {
 186         fprintf(stderr, "malloc() failed\en");
 187         exit(EXIT_FAILURE);
 188     }
 189
 190     return e;
 191 }
 192
 193 int
 194 main(int argc, char *argv[])
 195 {
 196     struct element *first, *elem, *prev;
 197     int circular, opt, errfnd;
 198
 199     /* The "\-c" command\-line option can be used to specify that the
 200        list is circular. */
 201
 202     errfnd = 0;
 203     circular = 0;
 204     while ((opt = getopt(argc, argv, "c")) != \-1) {
 205         switch (opt) {
 206         case \(aqc\(aq:
 207             circular = 1;
 208             break;
 209         default:
 210             errfnd = 1;
 211             break;
 212         }
 213     }
 214
 215     if (errfnd || optind >= argc) {
 216         fprintf(stderr,  "Usage: %s [\-c] string...\en", argv[0]);
 217         exit(EXIT_FAILURE);
 218     }
 219
 220     /* Create first element and place it in the linked list. */
 221
 222     elem = new_element();
 223     first = elem;
 224
 225     elem\->name = argv[optind];
 226
 227     if (circular) {
 228         elem\->forward = elem;
 229         elem\->backward = elem;
 230         insque(elem, elem);
 231     } else {
 232         insque(elem, NULL);
 233     }
 234
 235     /* Add remaining command\-line arguments as list elements. */
 236
 237     while (++optind < argc) {
 238         prev = elem;
 239
 240         elem = new_element();
 241         elem\->name = argv[optind];
 242         insque(elem, prev);
 243     }
 244
 245     /* Traverse the list from the start, printing element names. */
 246
 247     printf("Traversing completed list:\en");
 248     elem = first;
 249     do {
 250         printf("    %s\en", elem\->name);
 251         elem = elem\->forward;
 252     } while (elem != NULL && elem != first);
 253
 254     if (elem == first)
 255         printf("That was a circular list\en");
 256
 257     exit(EXIT_SUCCESS);
 258 }
 259 .EE
 260 .SH SEE ALSO
 261 .BR queue (7)