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
|
.\" Copyright (c) 2001-2003 The Open Group, All Rights Reserved
.TH "INSQUE" P 2003 "IEEE/The Open Group" "POSIX Programmer's Manual"
.\" insque
.SH NAME
insque, remque \- insert or remove an element in a queue
.SH SYNOPSIS
.LP
\fB#include <search.h>
.br
.sp
void insque(void *\fP\fIelement\fP\fB, void *\fP\fIpred\fP\fB);
.br
void remque(void *\fP\fIelement\fP\fB); \fP
\fB
.br
\fP
.SH DESCRIPTION
.LP
The \fIinsque\fP() and \fIremque\fP() functions shall manipulate queues
built from doubly-linked lists. The queue can be
either circular or linear. An application using \fIinsque\fP() or
\fIremque\fP() 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.
.LP
The \fIinsque\fP() function shall insert the element pointed to by
\fIelement\fP into a queue immediately after the element
pointed to by \fIpred\fP.
.LP
The \fIremque\fP() function shall remove the element pointed to by
\fIelement\fP from a queue.
.LP
If the queue is to be used as a linear list, invoking \fIinsque\fP(&\fIelement\fP,
NULL), where \fIelement\fP is the
initial element of the queue, shall initialize the forward and backward
pointers of \fIelement\fP to null pointers.
.LP
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
.LP
The \fIinsque\fP() and \fIremque\fP() functions do not return a value.
.SH ERRORS
.LP
No errors are defined.
.LP
\fIThe following sections are informative.\fP
.SH EXAMPLES
.SS Creating a Linear Linked List
.LP
The following example creates a linear linked list.
.sp
.RS
.nf
\fB#include <search.h>
\&...
struct myque element1;
struct myque element2;
.sp
char *data1 = "DATA1";
char *data2 = "DATA2";
\&...
element1.data = data1;
element2.data = data2;
.sp
insque (&element1, NULL);
insque (&element2, &element1);
\fP
.fi
.RE
.SS Creating a Circular Linked List
.LP
The following example creates a circular linked list.
.sp
.RS
.nf
\fB#include <search.h>
\&...
struct myque element1;
struct myque element2;
.sp
char *data1 = "DATA1";
char *data2 = "DATA2";
\&...
element1.data = data1;
element2.data = data2;
.sp
element1.fwd = &element1;
element1.bck = &element1;
.sp
insque (&element2, &element1);
\fP
.fi
.RE
.SS Removing an Element
.LP
The following example removes the element pointed to by \fIelement1\fP.
.sp
.RS
.nf
\fB#include <search.h>
\&...
struct myque element1;
\&...
remque (&element1);
\fP
.fi
.RE
.SH APPLICATION USAGE
.LP
The historical implementations of these functions described the arguments
as being of type \fBstruct qelem *\fP rather than as
being of type \fBvoid *\fP as defined here. In those implementations,
\fBstruct qelem\fP was commonly defined in \fI<search.h>\fP as:
.sp
.RS
.nf
\fBstruct qelem {
struct qelem *q_forw;
struct qelem *q_back;
};
\fP
.fi
.RE
.LP
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 \fBstruct
qelem\fP as specified.
.LP
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.
.LP
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 \fBstruct qelem\fP to
avoid compilation warnings. By specifying \fBvoid *\fP as the argument
type, applications do not need to change (unless they
specifically referenced \fBstruct qelem\fP and depended on it being
defined in \fI<search.h>\fP).
.SH RATIONALE
.LP
None.
.SH FUTURE DIRECTIONS
.LP
None.
.SH SEE ALSO
.LP
The Base Definitions volume of IEEE\ Std\ 1003.1-2001, \fI<search.h>\fP
.SH COPYRIGHT
Portions of this text are reprinted and reproduced in electronic form
from IEEE Std 1003.1, 2003 Edition, Standard for Information Technology
-- Portable Operating System Interface (POSIX), The Open Group Base
Specifications Issue 6, Copyright (C) 2001-2003 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 .
|