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