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  2019-03-06 "" "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 .PP
  45 .BI "void remque(void *" elem );
  46 .fi
  47 .PP
  48 .in -4n
  49 Feature Test Macro Requirements for glibc (see
  50 .BR feature_test_macros (7)):
  51 .in
  52 .PP
  53 .ad l
  54 .BR insque (),
  55 .BR remque ():
  56 .RS 4
  57 _XOPEN_SOURCE\ >=\ 500
  58 .\"    || _XOPEN_SOURCE\ &&\ _XOPEN_SOURCE_EXTENDED
  59     || /* Glibc since 2.19: */ _DEFAULT_SOURCE
  60     || /* Glibc versions <= 2.19: */ _SVID_SOURCE
  61 .RE
  62 .ad
  63 .SH DESCRIPTION
  64 The
  65 .BR insque ()
  66 and
  67 .BR remque ()
  68 functions manipulate doubly-linked lists.
  69 Each element in the list is a structure of
  70 which the first two elements are a forward and a
  71 backward pointer.
  72 The linked list may be linear (i.e., NULL forward pointer at
  73 the end of the list and NULL backward pointer at the start of the list)
  74 or circular.
  75 .PP
  76 The
  77 .BR insque ()
  78 function inserts the element pointed to by \fIelem\fP
  79 immediately after the element pointed to by \fIprev\fP.
  80 .PP
  81 If the list is linear, then the call
  82 .I "insque(elem, NULL)"
  83 can be used to insert the initial list element,
  84 and the call sets the forward and backward pointers of
  85 .I elem
  86 to NULL.
  87 .PP
  88 If the list is circular,
  89 the caller should ensure that the forward and backward pointers of the
  90 first element are initialized to point to that element,
  91 and the
  92 .I prev
  93 argument of the
  94 .BR insque ()
  95 call should also point to the element.
  96 .PP
  97 The
  98 .BR remque ()
  99 function removes the element pointed to by \fIelem\fP from the
 100 doubly-linked list.
 101 .SH ATTRIBUTES
 102 For an explanation of the terms used in this section, see
 103 .BR attributes (7).
 104 .TS
 105 allbox;
 106 lb lb lb
 107 l l l.
 108 Interface       Attribute       Value
 109 T{
 110 .BR insque (),
 111 .BR remque ()
 112 T}      Thread safety   MT-Safe
 113 .TE
 114 .sp 1
 115 .SH CONFORMING TO
 116 POSIX.1-2001, POSIX.1-2008.
 117 .SH NOTES
 118 On ancient systems,
 119 .\" e.g., SunOS, Linux libc4 and libc5
 120 the arguments of these functions were of type \fIstruct qelem *\fP,
 121 defined as:
 122 .PP
 123 .in +4n
 124 .EX
 125 struct qelem {
 126     struct qelem *q_forw;
 127     struct qelem *q_back;
 128     char          q_data[1];
 129 };
 130 .EE
 131 .in
 132 .PP
 133 This is still what you will get if
 134 .B _GNU_SOURCE
 135 is defined before
 136 including \fI<search.h>\fP.
 137 .PP
 138 The location of the prototypes for these functions differs among several
 139 versions of UNIX.
 140 The above is the POSIX version.
 141 Some systems place them in \fI<string.h>\fP.
 142 .\" Linux libc4 and libc 5 placed them
 143 .\" in \fI<stdlib.h>\fP.
 144 .SH BUGS
 145 In glibc 2.4 and earlier, it was not possible to specify
 146 .I prev
 147 as NULL.
 148 Consequently, to build a linear list, the caller had to build a list
 149 using an initial call that contained the first two elements of the list,
 150 with the forward and backward pointers in each element suitably initialized.
 151 .SH EXAMPLES
 152 The program below demonstrates the use of
 153 .BR insque ().
 154 Here is an example run of the program:
 155 .PP
 156 .in +4n
 157 .EX
 158 .RB "$ " "./a.out -c a b c"
 159 Traversing completed list:
 160     a
 161     b
 162     c
 163 That was a circular list
 164 .EE
 165 .in
 166 .SS Program source
 167 \&
 168 .EX
 169 #include <stdio.h>
 170 #include <stdlib.h>
 171 #include <unistd.h>
 172 #include <search.h>
 173
 174 struct element {
 175     struct element *forward;
 176     struct element *backward;
 177     char *name;
 178 };
 179
 180 static struct element *
 181 new_element(void)
 182 {
 183     struct element *e;
 184
 185     e = malloc(sizeof(struct element));
 186     if (e == NULL) {
 187         fprintf(stderr, "malloc() failed\en");
 188         exit(EXIT_FAILURE);
 189     }
 190
 191     return e;
 192 }
 193
 194 int
 195 main(int argc, char *argv[])
 196 {
 197     struct element *first, *elem, *prev;
 198     int circular, opt, errfnd;
 199
 200     /* The "\-c" command\-line option can be used to specify that the
 201        list is circular */
 202
 203     errfnd = 0;
 204     circular = 0;
 205     while ((opt = getopt(argc, argv, "c")) != \-1) {
 206         switch (opt) {
 207         case 'c':
 208             circular = 1;
 209             break;
 210         default:
 211             errfnd = 1;
 212             break;
 213         }
 214     }
 215
 216     if (errfnd || optind >= argc) {
 217         fprintf(stderr,  "Usage: %s [\-c] string...\en", argv[0]);
 218         exit(EXIT_FAILURE);
 219     }
 220
 221     /* Create first element and place it in the linked list */
 222
 223     elem = new_element();
 224     first = elem;
 225
 226     elem\->name = argv[optind];
 227
 228     if (circular) {
 229         elem\->forward = elem;
 230         elem\->backward = elem;
 231         insque(elem, elem);
 232     } else {
 233         insque(elem, NULL);
 234     }
 235
 236     /* Add remaining command\-line arguments as list elements */
 237
 238     while (++optind < argc) {
 239         prev = elem;
 240
 241         elem = new_element();
 242         elem\->name = argv[optind];
 243         insque(elem, prev);
 244     }
 245
 246     /* Traverse the list from the start, printing element names */
 247
 248     printf("Traversing completed list:\en");
 249     elem = first;
 250     do {
 251         printf("    %s\en", elem\->name);
 252         elem = elem\->forward;
 253     } while (elem != NULL && elem != first);
 254
 255     if (elem == first)
 256         printf("That was a circular list\en");
 257
 258     exit(EXIT_SUCCESS);
 259 }
 260 .EE
 261 .SH SEE ALSO
 262 .BR queue (3)