|
Packit |
7cfc04 |
.\" peter memishian -- meem@gnu.ai.mit.edu
|
|
Packit |
7cfc04 |
.\" $Id: insque.3,v 1.2 1996/10/30 21:03:39 meem Exp meem $
|
|
Packit |
7cfc04 |
.\" and Copyright (c) 2010, Michael Kerrisk <mtk.manpages@gmail.com>
|
|
Packit |
7cfc04 |
.\"
|
|
Packit |
7cfc04 |
.\" %%%LICENSE_START(VERBATIM)
|
|
Packit |
7cfc04 |
.\" Permission is granted to make and distribute verbatim copies of this
|
|
Packit |
7cfc04 |
.\" manual provided the copyright notice and this permission notice are
|
|
Packit |
7cfc04 |
.\" preserved on all copies.
|
|
Packit |
7cfc04 |
.\"
|
|
Packit |
7cfc04 |
.\" Permission is granted to copy and distribute modified versions of this
|
|
Packit |
7cfc04 |
.\" manual under the conditions for verbatim copying, provided that the
|
|
Packit |
7cfc04 |
.\" entire resulting derived work is distributed under the terms of a
|
|
Packit |
7cfc04 |
.\" permission notice identical to this one.
|
|
Packit |
7cfc04 |
.\"
|
|
Packit |
7cfc04 |
.\" Since the Linux kernel and libraries are constantly changing, this
|
|
Packit |
7cfc04 |
.\" manual page may be incorrect or out-of-date. The author(s) assume no
|
|
Packit |
7cfc04 |
.\" responsibility for errors or omissions, or for damages resulting from
|
|
Packit |
7cfc04 |
.\" the use of the information contained herein. The author(s) may not
|
|
Packit |
7cfc04 |
.\" have taken the same level of care in the production of this manual,
|
|
Packit |
7cfc04 |
.\" which is licensed free of charge, as they might when working
|
|
Packit |
7cfc04 |
.\" professionally.
|
|
Packit |
7cfc04 |
.\"
|
|
Packit |
7cfc04 |
.\" Formatted or processed versions of this manual, if unaccompanied by
|
|
Packit |
7cfc04 |
.\" the source, must acknowledge the copyright and authors of this work.
|
|
Packit |
7cfc04 |
.\" %%%LICENSE_END
|
|
Packit |
7cfc04 |
.\"
|
|
Packit |
7cfc04 |
.\" References consulted:
|
|
Packit |
7cfc04 |
.\" Linux libc source code (5.4.7)
|
|
Packit |
7cfc04 |
.\" Solaris 2.x, OSF/1, and HP-UX manpages
|
|
Packit |
7cfc04 |
.\" Curry's "UNIX Systems Programming for SVR4" (O'Reilly & Associates 1996)
|
|
Packit |
7cfc04 |
.\"
|
|
Packit |
7cfc04 |
.\" Changed to POSIX, 2003-08-11, aeb+wh
|
|
Packit |
7cfc04 |
.\" mtk, 2010-09-09: Noted glibc 2.4 bug, added info on circular
|
|
Packit |
7cfc04 |
.\" lists, added example program
|
|
Packit |
7cfc04 |
.\"
|
|
Packit |
7cfc04 |
.TH INSQUE 3 2017-09-15 "" "Linux Programmer's Manual"
|
|
Packit |
7cfc04 |
.SH NAME
|
|
Packit |
7cfc04 |
insque, remque \- insert/remove an item from a queue
|
|
Packit |
7cfc04 |
.SH SYNOPSIS
|
|
Packit |
7cfc04 |
.nf
|
|
Packit |
7cfc04 |
.B #include <search.h>
|
|
Packit |
7cfc04 |
.PP
|
|
Packit |
7cfc04 |
.BI "void insque(void *" elem ", void *" prev );
|
|
Packit |
7cfc04 |
.PP
|
|
Packit |
7cfc04 |
.BI "void remque(void *" elem );
|
|
Packit |
7cfc04 |
.fi
|
|
Packit |
7cfc04 |
.PP
|
|
Packit |
7cfc04 |
.in -4n
|
|
Packit |
7cfc04 |
Feature Test Macro Requirements for glibc (see
|
|
Packit |
7cfc04 |
.BR feature_test_macros (7)):
|
|
Packit |
7cfc04 |
.in
|
|
Packit |
7cfc04 |
.PP
|
|
Packit |
7cfc04 |
.ad l
|
|
Packit |
7cfc04 |
.BR insque (),
|
|
Packit |
7cfc04 |
.BR remque ():
|
|
Packit |
7cfc04 |
.RS 4
|
|
Packit |
7cfc04 |
_XOPEN_SOURCE\ >=\ 500
|
|
Packit |
7cfc04 |
.\" || _XOPEN_SOURCE\ &&\ _XOPEN_SOURCE_EXTENDED
|
|
Packit |
7cfc04 |
|| /* Glibc since 2.19: */ _DEFAULT_SOURCE
|
|
Packit |
7cfc04 |
|| /* Glibc versions <= 2.19: */ _SVID_SOURCE
|
|
Packit |
7cfc04 |
.RE
|
|
Packit |
7cfc04 |
.ad
|
|
Packit |
7cfc04 |
.SH DESCRIPTION
|
|
Packit |
7cfc04 |
The
|
|
Packit |
7cfc04 |
.BR insque ()
|
|
Packit |
7cfc04 |
and
|
|
Packit |
7cfc04 |
.BR remque ()
|
|
Packit |
7cfc04 |
functions manipulate doubly-linked lists.
|
|
Packit |
7cfc04 |
Each element in the list is a structure of
|
|
Packit |
7cfc04 |
which the first two elements are a forward and a
|
|
Packit |
7cfc04 |
backward pointer.
|
|
Packit |
7cfc04 |
The linked list may be linear (i.e., NULL forward pointer at
|
|
Packit |
7cfc04 |
the end of the list and NULL backward pointer at the start of the list)
|
|
Packit |
7cfc04 |
or circular.
|
|
Packit |
7cfc04 |
.PP
|
|
Packit |
7cfc04 |
The
|
|
Packit |
7cfc04 |
.BR insque ()
|
|
Packit |
7cfc04 |
function inserts the element pointed to by \fIelem\fP
|
|
Packit |
7cfc04 |
immediately after the element pointed to by \fIprev\fP.
|
|
Packit |
7cfc04 |
.PP
|
|
Packit |
7cfc04 |
If the list is linear, then the call
|
|
Packit |
7cfc04 |
.I "insque(elem, NULL)"
|
|
Packit |
7cfc04 |
can be used to insert the initial list element,
|
|
Packit |
7cfc04 |
and the call sets the forward and backward pointers of
|
|
Packit |
7cfc04 |
.I elem
|
|
Packit |
7cfc04 |
to NULL.
|
|
Packit |
7cfc04 |
.PP
|
|
Packit |
7cfc04 |
If the list is circular,
|
|
Packit |
7cfc04 |
the caller should ensure that the forward and backward pointers of the
|
|
Packit |
7cfc04 |
first element are initialized to point to that element,
|
|
Packit |
7cfc04 |
and the
|
|
Packit |
7cfc04 |
.I prev
|
|
Packit |
7cfc04 |
argument of the
|
|
Packit |
7cfc04 |
.BR insque ()
|
|
Packit |
7cfc04 |
call should also point to the element.
|
|
Packit |
7cfc04 |
.PP
|
|
Packit |
7cfc04 |
The
|
|
Packit |
7cfc04 |
.BR remque ()
|
|
Packit |
7cfc04 |
function removes the element pointed to by \fIelem\fP from the
|
|
Packit |
7cfc04 |
doubly-linked list.
|
|
Packit |
7cfc04 |
.SH ATTRIBUTES
|
|
Packit |
7cfc04 |
For an explanation of the terms used in this section, see
|
|
Packit |
7cfc04 |
.BR attributes (7).
|
|
Packit |
7cfc04 |
.TS
|
|
Packit |
7cfc04 |
allbox;
|
|
Packit |
7cfc04 |
lb lb lb
|
|
Packit |
7cfc04 |
l l l.
|
|
Packit |
7cfc04 |
Interface Attribute Value
|
|
Packit |
7cfc04 |
T{
|
|
Packit |
7cfc04 |
.BR insque (),
|
|
Packit |
7cfc04 |
.BR remque ()
|
|
Packit |
7cfc04 |
T} Thread safety MT-Safe
|
|
Packit |
7cfc04 |
.TE
|
|
Packit |
7cfc04 |
.sp 1
|
|
Packit |
7cfc04 |
.SH CONFORMING TO
|
|
Packit |
7cfc04 |
POSIX.1-2001, POSIX.1-2008.
|
|
Packit |
7cfc04 |
.SH NOTES
|
|
Packit |
7cfc04 |
On ancient systems,
|
|
Packit |
7cfc04 |
.\" e.g., SunOS, Linux libc4 and libc5
|
|
Packit |
7cfc04 |
the arguments of these functions were of type \fIstruct qelem *\fP,
|
|
Packit |
7cfc04 |
defined as:
|
|
Packit |
7cfc04 |
.PP
|
|
Packit |
7cfc04 |
.in +4n
|
|
Packit |
7cfc04 |
.EX
|
|
Packit |
7cfc04 |
struct qelem {
|
|
Packit |
7cfc04 |
struct qelem *q_forw;
|
|
Packit |
7cfc04 |
struct qelem *q_back;
|
|
Packit |
7cfc04 |
char q_data[1];
|
|
Packit |
7cfc04 |
};
|
|
Packit |
7cfc04 |
.EE
|
|
Packit |
7cfc04 |
.in
|
|
Packit |
7cfc04 |
.PP
|
|
Packit |
7cfc04 |
This is still what you will get if
|
|
Packit |
7cfc04 |
.B _GNU_SOURCE
|
|
Packit |
7cfc04 |
is defined before
|
|
Packit |
7cfc04 |
including \fI<search.h>\fP.
|
|
Packit |
7cfc04 |
.PP
|
|
Packit |
7cfc04 |
The location of the prototypes for these functions differs among several
|
|
Packit |
7cfc04 |
versions of UNIX.
|
|
Packit |
7cfc04 |
The above is the POSIX version.
|
|
Packit |
7cfc04 |
Some systems place them in \fI<string.h>\fP.
|
|
Packit |
7cfc04 |
.\" Linux libc4 and libc 5 placed them
|
|
Packit |
7cfc04 |
.\" in \fI<stdlib.h>\fP.
|
|
Packit |
7cfc04 |
.SH BUGS
|
|
Packit |
7cfc04 |
In glibc 2.4 and earlier, it was not possible to specify
|
|
Packit |
7cfc04 |
.I prev
|
|
Packit |
7cfc04 |
as NULL.
|
|
Packit |
7cfc04 |
Consequently, to build a linear list, the caller had to build a list
|
|
Packit |
7cfc04 |
using an initial call that contained the first two elements of the list,
|
|
Packit |
7cfc04 |
with the forward and backward pointers in each element suitably initialized.
|
|
Packit |
7cfc04 |
.SH EXAMPLE
|
|
Packit |
7cfc04 |
The program below demonstrates the use of
|
|
Packit |
7cfc04 |
.BR insque ().
|
|
Packit |
7cfc04 |
Here is an example run of the program:
|
|
Packit |
7cfc04 |
.PP
|
|
Packit |
7cfc04 |
.in +4n
|
|
Packit |
7cfc04 |
.EX
|
|
Packit |
7cfc04 |
.RB "$ " "./a.out -c a b c"
|
|
Packit |
7cfc04 |
Traversing completed list:
|
|
Packit |
7cfc04 |
a
|
|
Packit |
7cfc04 |
b
|
|
Packit |
7cfc04 |
c
|
|
Packit |
7cfc04 |
That was a circular list
|
|
Packit |
7cfc04 |
.EE
|
|
Packit |
7cfc04 |
.in
|
|
Packit |
7cfc04 |
.SS Program source
|
|
Packit |
7cfc04 |
\&
|
|
Packit |
7cfc04 |
.EX
|
|
Packit |
7cfc04 |
#include <stdio.h>
|
|
Packit |
7cfc04 |
#include <stdlib.h>
|
|
Packit |
7cfc04 |
#include <unistd.h>
|
|
Packit |
7cfc04 |
#include <search.h>
|
|
Packit |
7cfc04 |
|
|
Packit |
7cfc04 |
struct element {
|
|
Packit |
7cfc04 |
struct element *forward;
|
|
Packit |
7cfc04 |
struct element *backward;
|
|
Packit |
7cfc04 |
char *name;
|
|
Packit |
7cfc04 |
};
|
|
Packit |
7cfc04 |
|
|
Packit |
7cfc04 |
static struct element *
|
|
Packit |
7cfc04 |
new_element(void)
|
|
Packit |
7cfc04 |
{
|
|
Packit |
7cfc04 |
struct element *e;
|
|
Packit |
7cfc04 |
|
|
Packit |
7cfc04 |
e = malloc(sizeof(struct element));
|
|
Packit |
7cfc04 |
if (e == NULL) {
|
|
Packit |
7cfc04 |
fprintf(stderr, "malloc() failed\\n");
|
|
Packit |
7cfc04 |
exit(EXIT_FAILURE);
|
|
Packit |
7cfc04 |
}
|
|
Packit |
7cfc04 |
|
|
Packit |
7cfc04 |
return e;
|
|
Packit |
7cfc04 |
}
|
|
Packit |
7cfc04 |
|
|
Packit |
7cfc04 |
int
|
|
Packit |
7cfc04 |
main(int argc, char *argv[])
|
|
Packit |
7cfc04 |
{
|
|
Packit |
7cfc04 |
struct element *first, *elem, *prev;
|
|
Packit |
7cfc04 |
int circular, opt, errfnd;
|
|
Packit |
7cfc04 |
|
|
Packit |
7cfc04 |
/* The "\-c" command\-line option can be used to specify that the
|
|
Packit |
7cfc04 |
list is circular */
|
|
Packit |
7cfc04 |
|
|
Packit |
7cfc04 |
errfnd = 0;
|
|
Packit |
7cfc04 |
circular = 0;
|
|
Packit |
7cfc04 |
while ((opt = getopt(argc, argv, "c")) != \-1) {
|
|
Packit |
7cfc04 |
switch (opt) {
|
|
Packit |
7cfc04 |
case 'c':
|
|
Packit |
7cfc04 |
circular = 1;
|
|
Packit |
7cfc04 |
break;
|
|
Packit |
7cfc04 |
default:
|
|
Packit |
7cfc04 |
errfnd = 1;
|
|
Packit |
7cfc04 |
break;
|
|
Packit |
7cfc04 |
}
|
|
Packit |
7cfc04 |
}
|
|
Packit |
7cfc04 |
|
|
Packit |
7cfc04 |
if (errfnd || optind >= argc) {
|
|
Packit |
7cfc04 |
fprintf(stderr, "Usage: %s [\-c] string...\\n", argv[0]);
|
|
Packit |
7cfc04 |
exit(EXIT_FAILURE);
|
|
Packit |
7cfc04 |
}
|
|
Packit |
7cfc04 |
|
|
Packit |
7cfc04 |
/* Create first element and place it in the linked list */
|
|
Packit |
7cfc04 |
|
|
Packit |
7cfc04 |
elem = new_element();
|
|
Packit |
7cfc04 |
first = elem;
|
|
Packit |
7cfc04 |
|
|
Packit |
7cfc04 |
elem\->name = argv[optind];
|
|
Packit |
7cfc04 |
|
|
Packit |
7cfc04 |
if (circular) {
|
|
Packit |
7cfc04 |
elem\->forward = elem;
|
|
Packit |
7cfc04 |
elem\->backward = elem;
|
|
Packit |
7cfc04 |
insque(elem, elem);
|
|
Packit |
7cfc04 |
} else {
|
|
Packit |
7cfc04 |
insque(elem, NULL);
|
|
Packit |
7cfc04 |
}
|
|
Packit |
7cfc04 |
|
|
Packit |
7cfc04 |
/* Add remaining command\-line arguments as list elements */
|
|
Packit |
7cfc04 |
|
|
Packit |
7cfc04 |
while (++optind < argc) {
|
|
Packit |
7cfc04 |
prev = elem;
|
|
Packit |
7cfc04 |
|
|
Packit |
7cfc04 |
elem = new_element();
|
|
Packit |
7cfc04 |
elem\->name = argv[optind];
|
|
Packit |
7cfc04 |
insque(elem, prev);
|
|
Packit |
7cfc04 |
}
|
|
Packit |
7cfc04 |
|
|
Packit |
7cfc04 |
/* Traverse the list from the start, printing element names */
|
|
Packit |
7cfc04 |
|
|
Packit |
7cfc04 |
printf("Traversing completed list:\\n");
|
|
Packit |
7cfc04 |
elem = first;
|
|
Packit |
7cfc04 |
do {
|
|
Packit |
7cfc04 |
printf(" %s\\n", elem\->name);
|
|
Packit |
7cfc04 |
elem = elem\->forward;
|
|
Packit |
7cfc04 |
} while (elem != NULL && elem != first);
|
|
Packit |
7cfc04 |
|
|
Packit |
7cfc04 |
if (elem == first)
|
|
Packit |
7cfc04 |
printf("That was a circular list\\n");
|
|
Packit |
7cfc04 |
|
|
Packit |
7cfc04 |
exit(EXIT_SUCCESS);
|
|
Packit |
7cfc04 |
}
|
|
Packit |
7cfc04 |
.EE
|
|
Packit |
7cfc04 |
.SH SEE ALSO
|
|
Packit |
7cfc04 |
.BR queue (3)
|
|
Packit |
7cfc04 |
.SH COLOPHON
|
|
Packit |
7cfc04 |
This page is part of release 4.15 of the Linux
|
|
Packit |
7cfc04 |
.I man-pages
|
|
Packit |
7cfc04 |
project.
|
|
Packit |
7cfc04 |
A description of the project,
|
|
Packit |
7cfc04 |
information about reporting bugs,
|
|
Packit |
7cfc04 |
and the latest version of this page,
|
|
Packit |
7cfc04 |
can be found at
|
|
Packit |
7cfc04 |
\%https://www.kernel.org/doc/man\-pages/.
|