]>
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 | .\" |
93015253 | 5 | .\" %%%LICENSE_START(VERBATIM) |
fea681da MK |
6 | .\" Permission is granted to make and distribute verbatim copies of this |
7 | .\" manual provided the copyright notice and this permission notice are | |
8 | .\" preserved on all copies. | |
9 | .\" | |
10 | .\" Permission is granted to copy and distribute modified versions of this | |
11 | .\" manual under the conditions for verbatim copying, provided that the | |
12 | .\" entire resulting derived work is distributed under the terms of a | |
13 | .\" permission notice identical to this one. | |
c13182ef | 14 | .\" |
fea681da MK |
15 | .\" Since the Linux kernel and libraries are constantly changing, this |
16 | .\" manual page may be incorrect or out-of-date. The author(s) assume no | |
17 | .\" responsibility for errors or omissions, or for damages resulting from | |
18 | .\" the use of the information contained herein. The author(s) may not | |
19 | .\" have taken the same level of care in the production of this manual, | |
20 | .\" which is licensed free of charge, as they might when working | |
21 | .\" professionally. | |
c13182ef | 22 | .\" |
fea681da MK |
23 | .\" Formatted or processed versions of this manual, if unaccompanied by |
24 | .\" the source, must acknowledge the copyright and authors of this work. | |
4b72fb64 | 25 | .\" %%%LICENSE_END |
fea681da MK |
26 | .\" |
27 | .\" References consulted: | |
28 | .\" Linux libc source code (5.4.7) | |
29 | .\" Solaris 2.x, OSF/1, and HP-UX manpages | |
30 | .\" Curry's "UNIX Systems Programming for SVR4" (O'Reilly & Associates 1996) | |
31 | .\" | |
32 | .\" Changed to POSIX, 2003-08-11, aeb+wh | |
60f4b757 MK |
33 | .\" mtk, 2010-09-09: Noted glibc 2.4 bug, added info on circular |
34 | .\" lists, added example program | |
fea681da | 35 | .\" |
4b8c67d9 | 36 | .TH INSQUE 3 2017-09-15 "" "Linux Programmer's Manual" |
fea681da MK |
37 | .SH NAME |
38 | insque, remque \- insert/remove an item from a queue | |
39 | .SH SYNOPSIS | |
40 | .nf | |
41 | .B #include <search.h> | |
68e4db0a | 42 | .PP |
fea681da | 43 | .BI "void insque(void *" elem ", void *" prev ); |
f90f031e | 44 | .PP |
fea681da | 45 | .BI "void remque(void *" elem ); |
cc4615cc | 46 | .fi |
68e4db0a | 47 | .PP |
cc4615cc MK |
48 | .in -4n |
49 | Feature Test Macro Requirements for glibc (see | |
50 | .BR feature_test_macros (7)): | |
51 | .in | |
68e4db0a | 52 | .PP |
665f7784 | 53 | .ad l |
cc4615cc MK |
54 | .BR insque (), |
55 | .BR remque (): | |
665f7784 | 56 | .RS 4 |
d59161f9 | 57 | _XOPEN_SOURCE\ >=\ 500 |
cf7fa0a1 | 58 | .\" || _XOPEN_SOURCE\ &&\ _XOPEN_SOURCE_EXTENDED |
d59161f9 MK |
59 | || /* Glibc since 2.19: */ _DEFAULT_SOURCE |
60 | || /* Glibc versions <= 2.19: */ _SVID_SOURCE | |
665f7784 MK |
61 | .RE |
62 | .ad | |
fea681da | 63 | .SH DESCRIPTION |
c1d4c8a3 | 64 | The |
60a90ecd MK |
65 | .BR insque () |
66 | and | |
67 | .BR remque () | |
c1d4c8a3 | 68 | functions manipulate doubly-linked lists. |
c13182ef | 69 | Each element in the list is a structure of |
c1d4c8a3 | 70 | which the first two elements are a forward and a |
fea681da | 71 | backward pointer. |
c1d4c8a3 MK |
72 | The linked list may be linear (i.e., NULL forward pointer at |
73 | the end of the list and NULL backward pointer at the start of the list) | |
74 | or circular. | |
847e0d88 | 75 | .PP |
c1d4c8a3 | 76 | The |
60a90ecd | 77 | .BR insque () |
c1d4c8a3 MK |
78 | function inserts the element pointed to by \fIelem\fP |
79 | immediately after the element pointed to by \fIprev\fP. | |
847e0d88 | 80 | .PP |
c1d4c8a3 MK |
81 | If the list is linear, then the call |
82 | .I "insque(elem, NULL)" | |
83 | can be used to insert the initial list element, | |
84 | and the call sets the forward and backward pointers of | |
85 | .I elem | |
86 | to NULL. | |
847e0d88 | 87 | .PP |
c1d4c8a3 MK |
88 | If the list is circular, |
89 | the caller should ensure that the forward and backward pointers of the | |
90 | first element are initialized to point to that element, | |
91 | and the | |
92 | .I prev | |
93 | argument of the | |
94 | .BR insque () | |
95 | call should also point to the element. | |
847e0d88 | 96 | .PP |
c1d4c8a3 | 97 | The |
60a90ecd | 98 | .BR remque () |
c1d4c8a3 | 99 | function removes the element pointed to by \fIelem\fP from the |
fea681da | 100 | doubly-linked list. |
a19859cd MS |
101 | .SH ATTRIBUTES |
102 | For an explanation of the terms used in this section, see | |
103 | .BR attributes (7). | |
104 | .TS | |
105 | allbox; | |
106 | lb lb lb | |
107 | l l l. | |
108 | Interface Attribute Value | |
109 | T{ | |
110 | .BR insque (), | |
111 | .BR remque () | |
112 | T} Thread safety MT-Safe | |
113 | .TE | |
847e0d88 | 114 | .sp 1 |
47297adb | 115 | .SH CONFORMING TO |
b1da9a54 | 116 | POSIX.1-2001, POSIX.1-2008. |
47297adb | 117 | .SH NOTES |
5a9fb6b6 MK |
118 | On ancient systems, |
119 | .\" e.g., SunOS, Linux libc4 and libc5 | |
9f4d7f9e | 120 | the arguments of these functions were of type \fIstruct qelem *\fP, |
be9c618d | 121 | defined as: |
847e0d88 | 122 | .PP |
bd191423 | 123 | .in +4n |
b8302363 | 124 | .EX |
fea681da | 125 | struct qelem { |
cc4615cc MK |
126 | struct qelem *q_forw; |
127 | struct qelem *q_back; | |
128 | char q_data[1]; | |
fea681da | 129 | }; |
b8302363 | 130 | .EE |
bd191423 | 131 | .in |
847e0d88 | 132 | .PP |
c3dfd2c8 MK |
133 | This is still what you will get if |
134 | .B _GNU_SOURCE | |
135 | is defined before | |
c84371c6 | 136 | including \fI<search.h>\fP. |
847e0d88 | 137 | .PP |
fea681da | 138 | The location of the prototypes for these functions differs among several |
008f1ecc | 139 | versions of UNIX. |
c13182ef | 140 | The above is the POSIX version. |
c84371c6 | 141 | Some systems place them in \fI<string.h>\fP. |
2e0a7024 MK |
142 | .\" Linux libc4 and libc 5 placed them |
143 | .\" in \fI<stdlib.h>\fP. | |
60f4b757 MK |
144 | .SH BUGS |
145 | In glibc 2.4 and earlier, it was not possible to specify | |
146 | .I prev | |
147 | as NULL. | |
148 | Consequently, to build a linear list, the caller had to build a list | |
149 | using an initial call that contained the first two elements of the list, | |
150 | with the forward and backward pointers in each element suitably initialized. | |
d26b9289 MK |
151 | .SH EXAMPLE |
152 | The program below demonstrates the use of | |
153 | .BR insque (). | |
154 | Here is an example run of the program: | |
e646a1ba | 155 | .PP |
be034959 | 156 | .in +4n |
e646a1ba | 157 | .EX |
be034959 | 158 | .RB "$ " "./a.out -c a b c" |
d26b9289 MK |
159 | Traversing completed list: |
160 | a | |
161 | b | |
162 | c | |
163 | That was a circular list | |
b8302363 | 164 | .EE |
be034959 | 165 | .in |
d26b9289 MK |
166 | .SS Program source |
167 | \& | |
e7d0bb47 | 168 | .EX |
d26b9289 MK |
169 | #include <stdio.h> |
170 | #include <stdlib.h> | |
171 | #include <unistd.h> | |
172 | #include <search.h> | |
173 | ||
174 | struct element { | |
175 | struct element *forward; | |
176 | struct element *backward; | |
177 | char *name; | |
178 | }; | |
179 | ||
180 | static struct element * | |
181 | new_element(void) | |
182 | { | |
183 | struct element *e; | |
184 | ||
185 | e = malloc(sizeof(struct element)); | |
186 | if (e == NULL) { | |
187 | fprintf(stderr, "malloc() failed\\n"); | |
188 | exit(EXIT_FAILURE); | |
189 | } | |
190 | ||
191 | return e; | |
192 | } | |
193 | ||
194 | int | |
195 | main(int argc, char *argv[]) | |
196 | { | |
197 | struct element *first, *elem, *prev; | |
198 | int circular, opt, errfnd; | |
199 | ||
200 | /* The "\-c" command\-line option can be used to specify that the | |
201 | list is circular */ | |
202 | ||
203 | errfnd = 0; | |
204 | circular = 0; | |
205 | while ((opt = getopt(argc, argv, "c")) != \-1) { | |
206 | switch (opt) { | |
207 | case 'c': | |
208 | circular = 1; | |
209 | break; | |
210 | default: | |
211 | errfnd = 1; | |
212 | break; | |
213 | } | |
214 | } | |
215 | ||
216 | if (errfnd || optind >= argc) { | |
217 | fprintf(stderr, "Usage: %s [\-c] string...\\n", argv[0]); | |
218 | exit(EXIT_FAILURE); | |
219 | } | |
220 | ||
221 | /* Create first element and place it in the linked list */ | |
222 | ||
223 | elem = new_element(); | |
224 | first = elem; | |
225 | ||
226 | elem\->name = argv[optind]; | |
f6b326eb | 227 | |
d26b9289 MK |
228 | if (circular) { |
229 | elem\->forward = elem; | |
230 | elem\->backward = elem; | |
231 | insque(elem, elem); | |
232 | } else { | |
233 | insque(elem, NULL); | |
234 | } | |
235 | ||
236 | /* Add remaining command\-line arguments as list elements */ | |
237 | ||
238 | while (++optind < argc) { | |
239 | prev = elem; | |
240 | ||
241 | elem = new_element(); | |
242 | elem\->name = argv[optind]; | |
243 | insque(elem, prev); | |
244 | } | |
245 | ||
246 | /* Traverse the list from the start, printing element names */ | |
247 | ||
248 | printf("Traversing completed list:\\n"); | |
249 | elem = first; | |
250 | do { | |
251 | printf(" %s\\n", elem\->name); | |
252 | elem = elem\->forward; | |
253 | } while (elem != NULL && elem != first); | |
254 | ||
255 | if (elem == first) | |
256 | printf("That was a circular list\\n"); | |
257 | ||
258 | exit(EXIT_SUCCESS); | |
259 | } | |
e7d0bb47 | 260 | .EE |
e9d4c9a0 MK |
261 | .SH SEE ALSO |
262 | .BR queue (3) |