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