1INSQUE(P) POSIX Programmer's Manual INSQUE(P)
2
6 insque, remque - insert or remove an element in a queue
7
9 #include <search.h>
10 void insque(void *element, void *pred);
12 void remque(void *element);
13
16 The insque() and remque() functions shall manipulate queues built from
17 doubly-linked lists. The queue can be either circular or linear. An
18 application using insque() or remque() shall ensure it defines a struc‐
19 ture in which the first two members of the structure are pointers to
20 the same type of structure, and any further members are application-
21 specific. The first member of the structure is a forward pointer to
22 the next entry in the queue. The second member is a backward pointer to
23 the previous entry in the queue. If the queue is linear, the queue is
24 terminated with null pointers. The names of the structure and of the
25 pointer members are not subject to any special restriction.
26 The insque() function shall insert the element pointed to by element
28 into a queue immediately after the element pointed to by pred.
29 The remque() function shall remove the element pointed to by element
31 from a queue.
32 If the queue is to be used as a linear list, invoking insque(&element,
34 NULL), where element is the initial element of the queue, shall ini‐
35 tialize the forward and backward pointers of element to null pointers.
36 If the queue is to be used as a circular list, the application shall
38 ensure it initializes the forward pointer and the backward pointer of
39 the initial element of the queue to the element's own address.
40
42 The insque() and remque() functions do not return a value.
43
45 No errors are defined.
46 The following sections are informative.
48
50 Creating a Linear Linked List
51 The following example creates a linear linked list.
52 #include <search.h>
55 ...
56 struct myque element1;
57 struct myque element2;
58 char *data1 = "DATA1";
61 char *data2 = "DATA2";
62 ...
63 element1.data = data1;
64 element2.data = data2;
65 insque (&element1, NULL);
68 insque (&element2, &element1);
69 Creating a Circular Linked List
71 The following example creates a circular linked list.
72 #include <search.h>
75 ...
76 struct myque element1;
77 struct myque element2;
78 char *data1 = "DATA1";
81 char *data2 = "DATA2";
82 ...
83 element1.data = data1;
84 element2.data = data2;
85 element1.fwd = &element1;
88 element1.bck = &element1;
89 insque (&element2, &element1);
92 Removing an Element
94 The following example removes the element pointed to by element1.
95 #include <search.h>
98 ...
99 struct myque element1;
100 ...
101 remque (&element1);
102
104 The historical implementations of these functions described the argu‐
105 ments as being of type struct qelem * rather than as being of type void
106 * as defined here. In those implementations, struct qelem was commonly
107 defined in <search.h> as:
108 struct qelem {
111 struct qelem *q_forw;
112 struct qelem *q_back;
113 };
114 Applications using these functions, however, were never able to use
116 this structure directly since it provided no room for the actual data
117 contained in the elements. Most applications defined structures that
118 contained the two pointers as the initial elements and also provided
119 space for, or pointers to, the object's data. Applications that used
120 these functions to update more than one type of table also had the
121 problem of specifying two or more different structures with the same
122 name, if they literally used struct qelem as specified.
123 As described here, the implementations were actually expecting a struc‐
125 ture type where the first two members were forward and backward point‐
126 ers to structures. With C compilers that didn't provide function proto‐
127 types, applications used structures as specified in the DESCRIPTION
128 above and the compiler did what the application expected.
129 If this method had been carried forward with an ISO C standard compiler
131 and the historical function prototype, most applications would have to
132 be modified to cast pointers to the structures actually used to be
133 pointers to struct qelem to avoid compilation warnings. By specifying
134 void * as the argument type, applications do not need to change (unless
135 they specifically referenced struct qelem and depended on it being
136 defined in <search.h>).
137
139 None.
140
142 None.
143
145 The Base Definitions volume of IEEE Std 1003.1-2001, <search.h>
146
148 Portions of this text are reprinted and reproduced in electronic form
149 from IEEE Std 1003.1, 2003 Edition, Standard for Information Technology
150 -- Portable Operating System Interface (POSIX), The Open Group Base
151 Specifications Issue 6, Copyright (C) 2001-2003 by the Institute of
152 Electrical and Electronics Engineers, Inc and The Open Group. In the
153 event of any discrepancy between this version and the original IEEE and
154 The Open Group Standard, the original IEEE and The Open Group Standard
155 is the referee document. The original Standard can be obtained online
156 at http://www.opengroup.org/unix/online.html .
157IEEE/The Open Group 2003 INSQUE(P)