diff options
Diffstat (limited to 'man3/insque.3')
| -rw-r--r-- | man3/insque.3 | 249 |
1 files changed, 249 insertions, 0 deletions
diff --git a/man3/insque.3 b/man3/insque.3 new file mode 100644 index 0000000..d3444ce --- /dev/null +++ b/man3/insque.3 @@ -0,0 +1,249 @@ +'\" t +.\" peter memishian -- meem@gnu.ai.mit.edu +.\" $Id: insque.3,v 1.2 1996/10/30 21:03:39 meem Exp meem $ +.\" and Copyright (c) 2010, Michael Kerrisk <mtk.manpages@gmail.com> +.\" +.\" SPDX-License-Identifier: Linux-man-pages-copyleft +.\" +.\" References consulted: +.\" Linux libc source code (5.4.7) +.\" Solaris 2.x, OSF/1, and HP-UX manpages +.\" Curry's "UNIX Systems Programming for SVR4" (O'Reilly & Associates 1996) +.\" +.\" Changed to POSIX, 2003-08-11, aeb+wh +.\" mtk, 2010-09-09: Noted glibc 2.4 bug, added info on circular +.\" lists, added example program +.\" +.TH insque 3 2023-07-20 "Linux man-pages 6.05.01" +.SH NAME +insque, remque \- insert/remove an item from a queue +.SH LIBRARY +Standard C library +.RI ( libc ", " \-lc ) +.SH SYNOPSIS +.nf +.B #include <search.h> +.PP +.BI "void insque(void *" elem ", void *" prev ); +.BI "void remque(void *" elem ); +.fi +.PP +.RS -4 +Feature Test Macro Requirements for glibc (see +.BR feature_test_macros (7)): +.RE +.PP +.BR insque (), +.BR remque (): +.nf + _XOPEN_SOURCE >= 500 +.\" || _XOPEN_SOURCE && _XOPEN_SOURCE_EXTENDED + || /* glibc >= 2.19: */ _DEFAULT_SOURCE + || /* glibc <= 2.19: */ _SVID_SOURCE +.fi +.SH DESCRIPTION +The +.BR insque () +and +.BR remque () +functions manipulate doubly linked lists. +Each element in the list is a structure of +which the first two elements are a forward and a +backward pointer. +The linked list may be linear (i.e., NULL forward pointer at +the end of the list and NULL backward pointer at the start of the list) +or circular. +.PP +The +.BR insque () +function inserts the element pointed to by \fIelem\fP +immediately after the element pointed to by \fIprev\fP. +.PP +If the list is linear, then the call +.I "insque(elem, NULL)" +can be used to insert the initial list element, +and the call sets the forward and backward pointers of +.I elem +to NULL. +.PP +If the list is circular, +the caller should ensure that the forward and backward pointers of the +first element are initialized to point to that element, +and the +.I prev +argument of the +.BR insque () +call should also point to the element. +.PP +The +.BR remque () +function removes the element pointed to by \fIelem\fP from the +doubly linked list. +.SH ATTRIBUTES +For an explanation of the terms used in this section, see +.BR attributes (7). +.TS +allbox; +lbx lb lb +l l l. +Interface Attribute Value +T{ +.na +.nh +.BR insque (), +.BR remque () +T} Thread safety MT-Safe +.TE +.sp 1 +.SH VERSIONS +On ancient systems, +.\" e.g., SunOS, Linux libc4 and libc5 +the arguments of these functions were of type \fIstruct qelem *\fP, +defined as: +.PP +.in +4n +.EX +struct qelem { + struct qelem *q_forw; + struct qelem *q_back; + char q_data[1]; +}; +.EE +.in +.PP +This is still what you will get if +.B _GNU_SOURCE +is defined before +including \fI<search.h>\fP. +.PP +The location of the prototypes for these functions differs among several +versions of UNIX. +The above is the POSIX version. +Some systems place them in \fI<string.h>\fP. +.\" Linux libc4 and libc 5 placed them +.\" in \fI<stdlib.h>\fP. +.SH STANDARDS +POSIX.1-2008. +.SH HISTORY +POSIX.1-2001. +.SH BUGS +In glibc 2.4 and earlier, it was not possible to specify +.I prev +as NULL. +Consequently, to build a linear list, the caller had to build a list +using an initial call that contained the first two elements of the list, +with the forward and backward pointers in each element suitably initialized. +.SH EXAMPLES +The program below demonstrates the use of +.BR insque (). +Here is an example run of the program: +.PP +.in +4n +.EX +.RB "$ " "./a.out \-c a b c" +Traversing completed list: + a + b + c +That was a circular list +.EE +.in +.SS Program source +\& +.\" SRC BEGIN (insque.c) +.EX +#include <search.h> +#include <stdio.h> +#include <stdlib.h> +#include <unistd.h> +\& +struct element { + struct element *forward; + struct element *backward; + char *name; +}; +\& +static struct element * +new_element(void) +{ + struct element *e; +\& + e = malloc(sizeof(*e)); + if (e == NULL) { + fprintf(stderr, "malloc() failed\en"); + exit(EXIT_FAILURE); + } +\& + return e; +} +\& +int +main(int argc, char *argv[]) +{ + struct element *first, *elem, *prev; + int circular, opt, errfnd; +\& + /* The "\-c" command\-line option can be used to specify that the + list is circular. */ +\& + errfnd = 0; + circular = 0; + while ((opt = getopt(argc, argv, "c")) != \-1) { + switch (opt) { + case \[aq]c\[aq]: + circular = 1; + break; + default: + errfnd = 1; + break; + } + } +\& + if (errfnd || optind >= argc) { + fprintf(stderr, "Usage: %s [\-c] string...\en", argv[0]); + exit(EXIT_FAILURE); + } +\& + /* Create first element and place it in the linked list. */ +\& + elem = new_element(); + first = elem; +\& + elem\->name = argv[optind]; +\& + if (circular) { + elem\->forward = elem; + elem\->backward = elem; + insque(elem, elem); + } else { + insque(elem, NULL); + } +\& + /* Add remaining command\-line arguments as list elements. */ +\& + while (++optind < argc) { + prev = elem; +\& + elem = new_element(); + elem\->name = argv[optind]; + insque(elem, prev); + } +\& + /* Traverse the list from the start, printing element names. */ +\& + printf("Traversing completed list:\en"); + elem = first; + do { + printf(" %s\en", elem\->name); + elem = elem\->forward; + } while (elem != NULL && elem != first); +\& + if (elem == first) + printf("That was a circular list\en"); +\& + exit(EXIT_SUCCESS); +} +.EE +.\" SRC END +.SH SEE ALSO +.BR queue (7) |