]>
Commit | Line | Data |
---|---|---|
fea681da MK |
1 | .\" peter memishian -- meem@gnu.ai.mit.edu |
2 | .\" $Id: insque.3,v 1.2 1996/10/30 21:03:39 meem Exp meem $ | |
c1d4c8a3 | 3 | .\" and Copyright (c) 2010, Michael Kerrisk <mtk.manpages@gmail.com> |
fea681da | 4 | .\" |
5fbde956 | 5 | .\" SPDX-License-Identifier: Linux-man-pages-copyleft |
fea681da MK |
6 | .\" |
7 | .\" References consulted: | |
8 | .\" Linux libc source code (5.4.7) | |
9 | .\" Solaris 2.x, OSF/1, and HP-UX manpages | |
10 | .\" Curry's "UNIX Systems Programming for SVR4" (O'Reilly & Associates 1996) | |
11 | .\" | |
12 | .\" Changed to POSIX, 2003-08-11, aeb+wh | |
60f4b757 MK |
13 | .\" mtk, 2010-09-09: Noted glibc 2.4 bug, added info on circular |
14 | .\" lists, added example program | |
fea681da | 15 | .\" |
4c1c5274 | 16 | .TH insque 3 (date) "Linux man-pages (unreleased)" |
fea681da MK |
17 | .SH NAME |
18 | insque, remque \- insert/remove an item from a queue | |
4508f8a0 AC |
19 | .SH LIBRARY |
20 | Standard C library | |
8fc3b2cf | 21 | .RI ( libc ", " \-lc ) |
fea681da MK |
22 | .SH SYNOPSIS |
23 | .nf | |
24 | .B #include <search.h> | |
68e4db0a | 25 | .PP |
fea681da MK |
26 | .BI "void insque(void *" elem ", void *" prev ); |
27 | .BI "void remque(void *" elem ); | |
cc4615cc | 28 | .fi |
68e4db0a | 29 | .PP |
d39ad78f | 30 | .RS -4 |
cc4615cc MK |
31 | Feature Test Macro Requirements for glibc (see |
32 | .BR feature_test_macros (7)): | |
d39ad78f | 33 | .RE |
68e4db0a | 34 | .PP |
cc4615cc MK |
35 | .BR insque (), |
36 | .BR remque (): | |
9d2adbae | 37 | .nf |
5c10d2c5 MK |
38 | _XOPEN_SOURCE >= 500 |
39 | .\" || _XOPEN_SOURCE && _XOPEN_SOURCE_EXTENDED | |
9d2adbae MK |
40 | || /* Glibc since 2.19: */ _DEFAULT_SOURCE |
41 | || /* Glibc <= 2.19: */ _SVID_SOURCE | |
42 | .fi | |
fea681da | 43 | .SH DESCRIPTION |
c1d4c8a3 | 44 | The |
60a90ecd MK |
45 | .BR insque () |
46 | and | |
47 | .BR remque () | |
11fd5e7c | 48 | functions manipulate doubly linked lists. |
c13182ef | 49 | Each element in the list is a structure of |
c1d4c8a3 | 50 | which the first two elements are a forward and a |
fea681da | 51 | backward pointer. |
c1d4c8a3 MK |
52 | The linked list may be linear (i.e., NULL forward pointer at |
53 | the end of the list and NULL backward pointer at the start of the list) | |
54 | or circular. | |
847e0d88 | 55 | .PP |
c1d4c8a3 | 56 | The |
60a90ecd | 57 | .BR insque () |
c1d4c8a3 MK |
58 | function inserts the element pointed to by \fIelem\fP |
59 | immediately after the element pointed to by \fIprev\fP. | |
847e0d88 | 60 | .PP |
c1d4c8a3 MK |
61 | If the list is linear, then the call |
62 | .I "insque(elem, NULL)" | |
63 | can be used to insert the initial list element, | |
64 | and the call sets the forward and backward pointers of | |
65 | .I elem | |
66 | to NULL. | |
847e0d88 | 67 | .PP |
c1d4c8a3 MK |
68 | If the list is circular, |
69 | the caller should ensure that the forward and backward pointers of the | |
70 | first element are initialized to point to that element, | |
71 | and the | |
72 | .I prev | |
73 | argument of the | |
74 | .BR insque () | |
75 | call should also point to the element. | |
847e0d88 | 76 | .PP |
c1d4c8a3 | 77 | The |
60a90ecd | 78 | .BR remque () |
c1d4c8a3 | 79 | function removes the element pointed to by \fIelem\fP from the |
11fd5e7c | 80 | doubly linked list. |
a19859cd MS |
81 | .SH ATTRIBUTES |
82 | For an explanation of the terms used in this section, see | |
83 | .BR attributes (7). | |
c466875e MK |
84 | .ad l |
85 | .nh | |
a19859cd MS |
86 | .TS |
87 | allbox; | |
c466875e | 88 | lbx lb lb |
a19859cd MS |
89 | l l l. |
90 | Interface Attribute Value | |
91 | T{ | |
92 | .BR insque (), | |
93 | .BR remque () | |
94 | T} Thread safety MT-Safe | |
95 | .TE | |
c466875e MK |
96 | .hy |
97 | .ad | |
847e0d88 | 98 | .sp 1 |
3113c7f3 | 99 | .SH STANDARDS |
b1da9a54 | 100 | POSIX.1-2001, POSIX.1-2008. |
47297adb | 101 | .SH NOTES |
5a9fb6b6 MK |
102 | On ancient systems, |
103 | .\" e.g., SunOS, Linux libc4 and libc5 | |
9f4d7f9e | 104 | the arguments of these functions were of type \fIstruct qelem *\fP, |
be9c618d | 105 | defined as: |
847e0d88 | 106 | .PP |
bd191423 | 107 | .in +4n |
b8302363 | 108 | .EX |
fea681da | 109 | struct qelem { |
cc4615cc MK |
110 | struct qelem *q_forw; |
111 | struct qelem *q_back; | |
112 | char q_data[1]; | |
fea681da | 113 | }; |
b8302363 | 114 | .EE |
bd191423 | 115 | .in |
847e0d88 | 116 | .PP |
c3dfd2c8 MK |
117 | This is still what you will get if |
118 | .B _GNU_SOURCE | |
119 | is defined before | |
c84371c6 | 120 | including \fI<search.h>\fP. |
847e0d88 | 121 | .PP |
fea681da | 122 | The location of the prototypes for these functions differs among several |
008f1ecc | 123 | versions of UNIX. |
c13182ef | 124 | The above is the POSIX version. |
c84371c6 | 125 | Some systems place them in \fI<string.h>\fP. |
2e0a7024 MK |
126 | .\" Linux libc4 and libc 5 placed them |
127 | .\" in \fI<stdlib.h>\fP. | |
60f4b757 MK |
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. | |
a14af333 | 135 | .SH EXAMPLES |
d26b9289 MK |
136 | The program below demonstrates the use of |
137 | .BR insque (). | |
138 | Here is an example run of the program: | |
e646a1ba | 139 | .PP |
be034959 | 140 | .in +4n |
e646a1ba | 141 | .EX |
86d93b3e | 142 | .RB "$ " "./a.out \-c a b c" |
d26b9289 MK |
143 | Traversing completed list: |
144 | a | |
145 | b | |
146 | c | |
147 | That was a circular list | |
b8302363 | 148 | .EE |
be034959 | 149 | .in |
d26b9289 MK |
150 | .SS Program source |
151 | \& | |
b0b6ab4e | 152 | .\" SRC BEGIN (insque.c) |
e7d0bb47 | 153 | .EX |
ad3868f0 | 154 | #include <search.h> |
d26b9289 MK |
155 | #include <stdio.h> |
156 | #include <stdlib.h> | |
157 | #include <unistd.h> | |
d26b9289 MK |
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 | { | |
0f6f10d5 AC |
168 | struct element *e; |
169 | ||
170 | e = malloc(sizeof(*e)); | |
d26b9289 | 171 | if (e == NULL) { |
d1a71985 | 172 | fprintf(stderr, "malloc() failed\en"); |
d26b9289 MK |
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 | |
46b20ca1 | 186 | list is circular. */ |
d26b9289 MK |
187 | |
188 | errfnd = 0; | |
189 | circular = 0; | |
190 | while ((opt = getopt(argc, argv, "c")) != \-1) { | |
191 | switch (opt) { | |
861d36ba | 192 | case \(aqc\(aq: |
d26b9289 MK |
193 | circular = 1; |
194 | break; | |
195 | default: | |
196 | errfnd = 1; | |
197 | break; | |
198 | } | |
199 | } | |
200 | ||
201 | if (errfnd || optind >= argc) { | |
d1a71985 | 202 | fprintf(stderr, "Usage: %s [\-c] string...\en", argv[0]); |
d26b9289 MK |
203 | exit(EXIT_FAILURE); |
204 | } | |
205 | ||
46b20ca1 | 206 | /* Create first element and place it in the linked list. */ |
d26b9289 MK |
207 | |
208 | elem = new_element(); | |
209 | first = elem; | |
210 | ||
211 | elem\->name = argv[optind]; | |
f6b326eb | 212 | |
d26b9289 MK |
213 | if (circular) { |
214 | elem\->forward = elem; | |
215 | elem\->backward = elem; | |
216 | insque(elem, elem); | |
217 | } else { | |
218 | insque(elem, NULL); | |
219 | } | |
220 | ||
46b20ca1 | 221 | /* Add remaining command\-line arguments as list elements. */ |
d26b9289 MK |
222 | |
223 | while (++optind < argc) { | |
224 | prev = elem; | |
225 | ||
226 | elem = new_element(); | |
227 | elem\->name = argv[optind]; | |
228 | insque(elem, prev); | |
229 | } | |
230 | ||
46b20ca1 | 231 | /* Traverse the list from the start, printing element names. */ |
d26b9289 | 232 | |
d1a71985 | 233 | printf("Traversing completed list:\en"); |
d26b9289 MK |
234 | elem = first; |
235 | do { | |
d1a71985 | 236 | printf(" %s\en", elem\->name); |
d26b9289 MK |
237 | elem = elem\->forward; |
238 | } while (elem != NULL && elem != first); | |
239 | ||
240 | if (elem == first) | |
d1a71985 | 241 | printf("That was a circular list\en"); |
d26b9289 MK |
242 | |
243 | exit(EXIT_SUCCESS); | |
244 | } | |
e7d0bb47 | 245 | .EE |
b0b6ab4e | 246 | .\" SRC END |
e9d4c9a0 | 247 | .SH SEE ALSO |
083d4e6a | 248 | .BR queue (7) |