|
|
include <search.h>void insque(void *elem, void *pred); void remque(void *elem);
remque- remove an entry from a queue
insque(S) and remque(S) manipulate queues built from doubly linked lists. The queues can be either linear or circular.
An application that uses insque( ) or remque( ) must define a structure in which the first two members are pointers to the same type of structure, and any other members are application-specific. The first member 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, it terminates with null pointers.
The names of the structure and members are not restricted in any special way.
Each element in the queue must be in the following form:
struct qelem { struct qelem *q_forw; struct qelem *q_back; char q_data[]; }; insque(elem, pred) struct qelem *elem, *pred;insque( ) inserts the element pointed to by elem into a queue immediately after the preceding element, pred. remque( ) removes the entry pointed to by elem from a queue.remque(elem) struct qelem *elem;
For a linear list,
you can initialize the forward and backward pointers of
elem
to null pointers by invoking:
insque (&element,NULL)
For a circular list, the application must initialize the forward and backward pointers of the initial element to their own addresses.
struct qelem { struct qelem *q_forw; struct qelem *q_back; };This structure provided no room for actual data in the elements, so applications using insque( ) or remque( ) could not use the structure directly. Therefore, most applications had to define structures that contained the two pointers as initial elements and also provided space for, or pointers to, the object's data. Applications that updated more than one type of table also had the problem of specifying two or more different structures with the same name, if they used struct qelem * literally as specified.
As described here, the implementations actually expected a structure type where the first two members were forward and backward pointers to structures. With C compilers that did not provide function prototypes, applications used structures as specified in ``Description'', above, and the compiler did what the application expected.
If this method had been used with an ANSI compiler and the historical function prototype, to avoid compiler warnings you would have to modify most applications to cast pointers to the structures actually used, to cast pointers to struct qelem *. However, if applications specify an argument type of void *, you do not need to change them unless they refer to struct qelem * and depend on its being defined in search.h.
X/Open CAE Specification, System Interfaces and Headers, Issue 4, Version 2. .