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