1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
|
'\" et
.TH INSQUE "3P" 2017 "IEEE/The Open Group" "POSIX Programmer's Manual"
.\"
.SH PROLOG
This manual page is part of the POSIX Programmer's Manual.
The Linux implementation of this interface may differ (consult
the corresponding Linux manual page for details of Linux behavior),
or the interface may not be implemented on Linux.
.\"
.SH NAME
insque,
remque
\(em insert or remove an element in a queue
.SH SYNOPSIS
.LP
.nf
#include <search.h>
.P
void insque(void *\fIelement\fP, void *\fIpred\fP);
void remque(void *\fIelement\fP);
.fi
.SH DESCRIPTION
The
\fIinsque\fR()
and
\fIremque\fR()
functions shall manipulate queues built from doubly-linked lists.
The queue can be either circular or linear. An application using
\fIinsque\fR()
or
\fIremque\fR()
shall ensure it defines a structure in which the first two members of
the structure are pointers to the same type of structure, and any
further members are application-specific. The first member of the
structure is a forward pointer to the next entry in the queue. The
second member is a backward pointer to the previous entry in the queue.
If the queue is linear, the queue is terminated with null pointers. The
names of the structure and of the pointer members are not subject to
any special restriction.
.P
The
\fIinsque\fR()
function shall insert the element pointed to by
.IR element
into a queue immediately after the element pointed to by
.IR pred .
.P
The
\fIremque\fR()
function shall remove the element pointed to by
.IR element
from a queue.
.P
If the queue is to be used as a linear list, invoking
\fIinsque\fP(&\fIelement\fP, NULL), where
.IR element
is the initial element of the queue, shall initialize the forward
and backward pointers of
.IR element
to null pointers.
.P
If the queue is to be used as a circular list, the application shall
ensure it initializes the forward pointer and the backward pointer of
the initial element of the queue to the element's own address.
.SH "RETURN VALUE"
The
\fIinsque\fR()
and
\fIremque\fR()
functions do not return a value.
.SH ERRORS
No errors are defined.
.LP
.IR "The following sections are informative."
.SH EXAMPLES
.SS "Creating a Linear Linked List"
.P
The following example creates a linear linked list.
.sp
.RS 4
.nf
#include <search.h>
\&...
struct myque element1;
struct myque element2;
.P
char *data1 = "DATA1";
char *data2 = "DATA2";
\&...
element1.data = data1;
element2.data = data2;
.P
insque (&element1, NULL);
insque (&element2, &element1);
.fi
.P
.RE
.SS "Creating a Circular Linked List"
.P
The following example creates a circular linked list.
.sp
.RS 4
.nf
#include <search.h>
\&...
struct myque element1;
struct myque element2;
.P
char *data1 = "DATA1";
char *data2 = "DATA2";
\&...
element1.data = data1;
element2.data = data2;
.P
element1.fwd = &element1;
element1.bck = &element1;
.P
insque (&element2, &element1);
.fi
.P
.RE
.SS "Removing an Element"
.P
The following example removes the element pointed to by
.IR element1 .
.sp
.RS 4
.nf
#include <search.h>
\&...
struct myque element1;
\&...
remque (&element1);
.fi
.P
.RE
.SH "APPLICATION USAGE"
The historical implementations of these functions described the
arguments as being of type
.BR "struct qelem *"
rather than as being of type
.BR "void *"
as defined here. In those implementations,
.BR "struct qelem"
was commonly defined in
.IR <search.h>
as:
.sp
.RS 4
.nf
struct qelem {
struct qelem *q_forw;
struct qelem *q_back;
};
.fi
.P
.RE
.P
Applications using these functions, however, were never able to use
this structure directly since it provided no room for the actual data
contained in the elements. Most applications defined structures that
contained the two pointers as the initial elements and also provided
space for, or pointers to, the object's data. Applications that used
these functions to update more than one type of table also had the
problem of specifying two or more different structures with the same
name, if they literally used
.BR "struct qelem"
as specified.
.P
As described here, the implementations were actually expecting a
structure type where the first two members were forward and backward
pointers to structures. With C compilers that didn't provide function
prototypes, applications used structures as specified in the
DESCRIPTION above and the compiler did what the application expected.
.P
If this method had been carried forward with an ISO\ C standard compiler and the
historical function prototype, most applications would have to be
modified to cast pointers to the structures actually used to be
pointers to
.BR "struct qelem"
to avoid compilation warnings. By specifying
.BR "void *"
as the argument type, applications do not need to change (unless
they specifically referenced
.BR "struct qelem"
and depended on it being defined in
.IR <search.h> ).
.SH RATIONALE
None.
.SH "FUTURE DIRECTIONS"
None.
.SH "SEE ALSO"
The Base Definitions volume of POSIX.1\(hy2017,
.IR "\fB<search.h>\fP"
.\"
.SH COPYRIGHT
Portions of this text are reprinted and reproduced in electronic form
from IEEE Std 1003.1-2017, Standard for Information Technology
-- Portable Operating System Interface (POSIX), The Open Group Base
Specifications Issue 7, 2018 Edition,
Copyright (C) 2018 by the Institute of
Electrical and Electronics Engineers, Inc and The Open Group.
In the event of any discrepancy between this version and the original IEEE and
The Open Group Standard, the original IEEE and The Open Group Standard
is the referee document. The original Standard can be obtained online at
http://www.opengroup.org/unix/online.html .
.PP
Any typographical or formatting errors that appear
in this page are most likely
to have been introduced during the conversion of the source files to
man page format. To report such errors, see
https://www.kernel.org/doc/man-pages/reporting_bugs.html .
|
