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