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  2015-08-08 "" "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 .sp
  43 .BI "void insque(void *" elem ", void *" prev );
  44
  45 .BI "void remque(void *" elem );
  46 .fi
  47 .sp
  48 .in -4n
  49 Feature Test Macro Requirements for glibc (see
  50 .BR feature_test_macros (7)):
  51 .in
  52 .sp
  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
  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
  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
  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
  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
 115 .SH CONFORMING TO
 116 POSIX.1-2001, POSIX.1-2008.
 117 .SH NOTES
 118 Traditionally (e.g., SunOS, Linux libc4 and libc5),
 119 the arguments of these functions were of type \fIstruct qelem *\fP,
 120 defined as:
 121
 122 .in +4n
 123 .nf
 124 struct qelem {
 125     struct qelem *q_forw;
 126     struct qelem *q_back;
 127     char          q_data[1];
 128 };
 129 .fi
 130 .in
 131
 132 This is still what you will get if
 133 .B _GNU_SOURCE
 134 is defined before
 135 including \fI<search.h>\fP.
 136
 137 The location of the prototypes for these functions differs among several
 138 versions of UNIX.
 139 The above is the POSIX version.
 140 Some systems place them in \fI<string.h>\fP.
 141 .\" Linux libc4 and libc 5 placed them
 142 .\" in \fI<stdlib.h>\fP.
 143 .SH BUGS
 144 In glibc 2.4 and earlier, it was not possible to specify
 145 .I prev
 146 as NULL.
 147 Consequently, to build a linear list, the caller had to build a list
 148 using an initial call that contained the first two elements of the list,
 149 with the forward and backward pointers in each element suitably initialized.
 150 .SH EXAMPLE
 151 The program below demonstrates the use of
 152 .BR insque ().
 153 Here is an example run of the program:
 154 .in +4n
 155 .nf
 156
 157 .RB "$ " "./a.out -c a b c"
 158 Traversing completed list:
 159     a
 160     b
 161     c
 162 That was a circular list
 163 .fi
 164 .in
 165 .SS Program source
 166 \&
 167 .nf
 168 #include <stdio.h>
 169 #include <stdlib.h>
 170 #include <unistd.h>
 171 #include <search.h>
 172
 173 struct element {
 174     struct element *forward;
 175     struct element *backward;
 176     char *name;
 177 };
 178
 179 static struct element *
 180 new_element(void)
 181 {
 182     struct element *e;
 183
 184     e = malloc(sizeof(struct element));
 185     if (e == NULL) {
 186         fprintf(stderr, "malloc() failed\\n");
 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 'c':
 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...\\n", 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:\\n");
 248     elem = first;
 249     do {
 250         printf("    %s\\n", elem\->name);
 251         elem = elem\->forward;
 252     } while (elem != NULL && elem != first);
 253
 254     if (elem == first)
 255         printf("That was a circular list\\n");
 256
 257     exit(EXIT_SUCCESS);
 258 }
 259 .fi