summaryrefslogtreecommitdiffstats
path: root/man3/insque.3
diff options
context:
space:
mode:
Diffstat (limited to 'man3/insque.3')
-rw-r--r--man3/insque.3249
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)