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 _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 ATTRIBUTES
 100 For an explanation of the terms used in this section, see
 101 .BR attributes (7).
 102 .TS
 103 allbox;
 104 lb lb lb
 105 l l l.
 106 Interface       Attribute       Value
 107 T{
 108 .BR insque (),
 109 .BR remque ()
 110 T}      Thread safety   MT-Safe
 111 .TE
 112
 113 .SH CONFORMING TO
 114 POSIX.1-2001, POSIX.1-2008.
 115 .SH NOTES
 116 Traditionally (e.g., SunOS, Linux libc4 and libc5),
 117 the arguments of these functions were of type \fIstruct qelem *\fP,
 118 defined as:
 119
 120 .in +4n
 121 .nf
 122 struct qelem {
 123     struct qelem *q_forw;
 124     struct qelem *q_back;
 125     char          q_data[1];
 126 };
 127 .fi
 128 .in
 129
 130 This is still what you will get if
 131 .B _GNU_SOURCE
 132 is defined before
 133 including \fI<search.h>\fP.
 134
 135 The location of the prototypes for these functions differs among several
 136 versions of UNIX.
 137 The above is the POSIX version.
 138 Some systems place them in \fI<string.h>\fP.
 139 .\" Linux libc4 and libc 5 placed them
 140 .\" in \fI<stdlib.h>\fP.
 141 .SH BUGS
 142 In glibc 2.4 and earlier, it was not possible to specify
 143 .I prev
 144 as NULL.
 145 Consequently, to build a linear list, the caller had to build a list
 146 using an initial call that contained the first two elements of the list,
 147 with the forward and backward pointers in each element suitably initialized.
 148 .SH EXAMPLE
 149 The program below demonstrates the use of
 150 .BR insque ().
 151 Here is an example run of the program:
 152 .in +4n
 153 .nf
 154
 155 .RB "$ " "./a.out -c a b c"
 156 Traversing completed list:
 157     a
 158     b
 159     c
 160 That was a circular list
 161 .fi
 162 .in
 163 .SS Program source
 164 \&
 165 .nf
 166 #include <stdio.h>
 167 #include <stdlib.h>
 168 #include <unistd.h>
 169 #include <search.h>
 170
 171 struct element {
 172     struct element *forward;
 173     struct element *backward;
 174     char *name;
 175 };
 176
 177 static struct element *
 178 new_element(void)
 179 {
 180     struct element *e;
 181
 182     e = malloc(sizeof(struct element));
 183     if (e == NULL) {
 184         fprintf(stderr, "malloc() failed\\n");
 185         exit(EXIT_FAILURE);
 186     }
 187
 188     return e;
 189 }
 190
 191 int
 192 main(int argc, char *argv[])
 193 {
 194     struct element *first, *elem, *prev;
 195     int circular, opt, errfnd;
 196
 197     /* The "\-c" command\-line option can be used to specify that the
 198        list is circular */
 199
 200     errfnd = 0;
 201     circular = 0;
 202     while ((opt = getopt(argc, argv, "c")) != \-1) {
 203         switch (opt) {
 204         case 'c':
 205             circular = 1;
 206             break;
 207         default:
 208             errfnd = 1;
 209             break;
 210         }
 211     }
 212
 213     if (errfnd || optind >= argc) {
 214         fprintf(stderr,  "Usage: %s [\-c] string...\\n", argv[0]);
 215         exit(EXIT_FAILURE);
 216     }
 217
 218     /* Create first element and place it in the linked list */
 219
 220     elem = new_element();
 221     first = elem;
 222
 223     elem\->name = argv[optind];
 224
 225     if (circular) {
 226         elem\->forward = elem;
 227         elem\->backward = elem;
 228         insque(elem, elem);
 229     } else {
 230         insque(elem, NULL);
 231     }
 232
 233     /* Add remaining command\-line arguments as list elements */
 234
 235     while (++optind < argc) {
 236         prev = elem;
 237
 238         elem = new_element();
 239         elem\->name = argv[optind];
 240         insque(elem, prev);
 241     }
 242
 243     /* Traverse the list from the start, printing element names */
 244
 245     printf("Traversing completed list:\\n");
 246     elem = first;
 247     do {
 248         printf("    %s\\n", elem\->name);
 249         elem = elem\->forward;
 250     } while (elem != NULL && elem != first);
 251
 252     if (elem == first)
 253         printf("That was a circular list\\n");
 254
 255     exit(EXIT_SUCCESS);
 256 }
 257 .fi