Debian Codegraph @

upstream/debian-unstable/man3/insque.3

raw
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)