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