]>
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 | .\" |
1d767b55 | 16 | .TH INSQUE 3 2021-03-22 "" "Linux Programmer's Manual" |
fea681da MK |
17 | .SH NAME |
18 | insque, remque \- insert/remove an item from a queue | |
19 | .SH SYNOPSIS | |
20 | .nf | |
21 | .B #include <search.h> | |
68e4db0a | 22 | .PP |
fea681da MK |
23 | .BI "void insque(void *" elem ", void *" prev ); |
24 | .BI "void remque(void *" elem ); | |
cc4615cc | 25 | .fi |
68e4db0a | 26 | .PP |
d39ad78f | 27 | .RS -4 |
cc4615cc MK |
28 | Feature Test Macro Requirements for glibc (see |
29 | .BR feature_test_macros (7)): | |
d39ad78f | 30 | .RE |
68e4db0a | 31 | .PP |
cc4615cc MK |
32 | .BR insque (), |
33 | .BR remque (): | |
9d2adbae | 34 | .nf |
5c10d2c5 MK |
35 | _XOPEN_SOURCE >= 500 |
36 | .\" || _XOPEN_SOURCE && _XOPEN_SOURCE_EXTENDED | |
9d2adbae MK |
37 | || /* Glibc since 2.19: */ _DEFAULT_SOURCE |
38 | || /* Glibc <= 2.19: */ _SVID_SOURCE | |
39 | .fi | |
fea681da | 40 | .SH DESCRIPTION |
c1d4c8a3 | 41 | The |
60a90ecd MK |
42 | .BR insque () |
43 | and | |
44 | .BR remque () | |
11fd5e7c | 45 | functions manipulate doubly linked lists. |
c13182ef | 46 | Each element in the list is a structure of |
c1d4c8a3 | 47 | which the first two elements are a forward and a |
fea681da | 48 | backward pointer. |
c1d4c8a3 MK |
49 | The linked list may be linear (i.e., NULL forward pointer at |
50 | the end of the list and NULL backward pointer at the start of the list) | |
51 | or circular. | |
847e0d88 | 52 | .PP |
c1d4c8a3 | 53 | The |
60a90ecd | 54 | .BR insque () |
c1d4c8a3 MK |
55 | function inserts the element pointed to by \fIelem\fP |
56 | immediately after the element pointed to by \fIprev\fP. | |
847e0d88 | 57 | .PP |
c1d4c8a3 MK |
58 | If the list is linear, then the call |
59 | .I "insque(elem, NULL)" | |
60 | can be used to insert the initial list element, | |
61 | and the call sets the forward and backward pointers of | |
62 | .I elem | |
63 | to NULL. | |
847e0d88 | 64 | .PP |
c1d4c8a3 MK |
65 | If the list is circular, |
66 | the caller should ensure that the forward and backward pointers of the | |
67 | first element are initialized to point to that element, | |
68 | and the | |
69 | .I prev | |
70 | argument of the | |
71 | .BR insque () | |
72 | call should also point to the element. | |
847e0d88 | 73 | .PP |
c1d4c8a3 | 74 | The |
60a90ecd | 75 | .BR remque () |
c1d4c8a3 | 76 | function removes the element pointed to by \fIelem\fP from the |
11fd5e7c | 77 | doubly linked list. |
a19859cd MS |
78 | .SH ATTRIBUTES |
79 | For an explanation of the terms used in this section, see | |
80 | .BR attributes (7). | |
c466875e MK |
81 | .ad l |
82 | .nh | |
a19859cd MS |
83 | .TS |
84 | allbox; | |
c466875e | 85 | lbx lb lb |
a19859cd MS |
86 | l l l. |
87 | Interface Attribute Value | |
88 | T{ | |
89 | .BR insque (), | |
90 | .BR remque () | |
91 | T} Thread safety MT-Safe | |
92 | .TE | |
c466875e MK |
93 | .hy |
94 | .ad | |
847e0d88 | 95 | .sp 1 |
47297adb | 96 | .SH CONFORMING TO |
b1da9a54 | 97 | POSIX.1-2001, POSIX.1-2008. |
47297adb | 98 | .SH NOTES |
5a9fb6b6 MK |
99 | On ancient systems, |
100 | .\" e.g., SunOS, Linux libc4 and libc5 | |
9f4d7f9e | 101 | the arguments of these functions were of type \fIstruct qelem *\fP, |
be9c618d | 102 | defined as: |
847e0d88 | 103 | .PP |
bd191423 | 104 | .in +4n |
b8302363 | 105 | .EX |
fea681da | 106 | struct qelem { |
cc4615cc MK |
107 | struct qelem *q_forw; |
108 | struct qelem *q_back; | |
109 | char q_data[1]; | |
fea681da | 110 | }; |
b8302363 | 111 | .EE |
bd191423 | 112 | .in |
847e0d88 | 113 | .PP |
c3dfd2c8 MK |
114 | This is still what you will get if |
115 | .B _GNU_SOURCE | |
116 | is defined before | |
c84371c6 | 117 | including \fI<search.h>\fP. |
847e0d88 | 118 | .PP |
fea681da | 119 | The location of the prototypes for these functions differs among several |
008f1ecc | 120 | versions of UNIX. |
c13182ef | 121 | The above is the POSIX version. |
c84371c6 | 122 | Some systems place them in \fI<string.h>\fP. |
2e0a7024 MK |
123 | .\" Linux libc4 and libc 5 placed them |
124 | .\" in \fI<stdlib.h>\fP. | |
60f4b757 MK |
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. | |
a14af333 | 132 | .SH EXAMPLES |
d26b9289 MK |
133 | The program below demonstrates the use of |
134 | .BR insque (). | |
135 | Here is an example run of the program: | |
e646a1ba | 136 | .PP |
be034959 | 137 | .in +4n |
e646a1ba | 138 | .EX |
86d93b3e | 139 | .RB "$ " "./a.out \-c a b c" |
d26b9289 MK |
140 | Traversing completed list: |
141 | a | |
142 | b | |
143 | c | |
144 | That was a circular list | |
b8302363 | 145 | .EE |
be034959 | 146 | .in |
d26b9289 MK |
147 | .SS Program source |
148 | \& | |
e7d0bb47 | 149 | .EX |
d26b9289 MK |
150 | #include <stdio.h> |
151 | #include <stdlib.h> | |
152 | #include <unistd.h> | |
153 | #include <search.h> | |
154 | ||
155 | struct element { | |
156 | struct element *forward; | |
157 | struct element *backward; | |
158 | char *name; | |
159 | }; | |
160 | ||
161 | static struct element * | |
162 | new_element(void) | |
163 | { | |
48d05103 | 164 | struct element *e = malloc(sizeof(*e)); |
d26b9289 | 165 | if (e == NULL) { |
d1a71985 | 166 | fprintf(stderr, "malloc() failed\en"); |
d26b9289 MK |
167 | exit(EXIT_FAILURE); |
168 | } | |
169 | ||
170 | return e; | |
171 | } | |
172 | ||
173 | int | |
174 | main(int argc, char *argv[]) | |
175 | { | |
176 | struct element *first, *elem, *prev; | |
177 | int circular, opt, errfnd; | |
178 | ||
179 | /* The "\-c" command\-line option can be used to specify that the | |
46b20ca1 | 180 | list is circular. */ |
d26b9289 MK |
181 | |
182 | errfnd = 0; | |
183 | circular = 0; | |
184 | while ((opt = getopt(argc, argv, "c")) != \-1) { | |
185 | switch (opt) { | |
861d36ba | 186 | case \(aqc\(aq: |
d26b9289 MK |
187 | circular = 1; |
188 | break; | |
189 | default: | |
190 | errfnd = 1; | |
191 | break; | |
192 | } | |
193 | } | |
194 | ||
195 | if (errfnd || optind >= argc) { | |
d1a71985 | 196 | fprintf(stderr, "Usage: %s [\-c] string...\en", argv[0]); |
d26b9289 MK |
197 | exit(EXIT_FAILURE); |
198 | } | |
199 | ||
46b20ca1 | 200 | /* Create first element and place it in the linked list. */ |
d26b9289 MK |
201 | |
202 | elem = new_element(); | |
203 | first = elem; | |
204 | ||
205 | elem\->name = argv[optind]; | |
f6b326eb | 206 | |
d26b9289 MK |
207 | if (circular) { |
208 | elem\->forward = elem; | |
209 | elem\->backward = elem; | |
210 | insque(elem, elem); | |
211 | } else { | |
212 | insque(elem, NULL); | |
213 | } | |
214 | ||
46b20ca1 | 215 | /* Add remaining command\-line arguments as list elements. */ |
d26b9289 MK |
216 | |
217 | while (++optind < argc) { | |
218 | prev = elem; | |
219 | ||
220 | elem = new_element(); | |
221 | elem\->name = argv[optind]; | |
222 | insque(elem, prev); | |
223 | } | |
224 | ||
46b20ca1 | 225 | /* Traverse the list from the start, printing element names. */ |
d26b9289 | 226 | |
d1a71985 | 227 | printf("Traversing completed list:\en"); |
d26b9289 MK |
228 | elem = first; |
229 | do { | |
d1a71985 | 230 | printf(" %s\en", elem\->name); |
d26b9289 MK |
231 | elem = elem\->forward; |
232 | } while (elem != NULL && elem != first); | |
233 | ||
234 | if (elem == first) | |
d1a71985 | 235 | printf("That was a circular list\en"); |
d26b9289 MK |
236 | |
237 | exit(EXIT_SUCCESS); | |
238 | } | |
e7d0bb47 | 239 | .EE |
e9d4c9a0 | 240 | .SH SEE ALSO |
083d4e6a | 241 | .BR queue (7) |