Debian Codegraph @

upstream/debian-trixie/man3/insque.3

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