3 * File name: ir/adt/pdeq.h
4 * Purpose: Declarations for pdeq.
5 * Author: Christian von Roques
6 * Modified by: Michael Beck
7 * Created: 1999 by getting from fiasco
9 * Copyright: (c) 1995, 1996 Christian von Roques
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
18 * Declarations for double ended queue/list of generic pointers.
22 * The type of the pointer compare function.
24 * @param elem The list element.
25 * @param key The user supplied key.
27 * @return 0 if the element matches the key, non-zero else.
29 typedef int (*cmp_fun)(const void *elem, const void *key);
32 * The pointer double ended queue (list).
34 typedef struct pdeq pdeq;
37 * Creates a new double ended pointer list.
44 * Creates a new double ended pointer list and puts an initial pointer element in.
46 * @param x The pointer element to put in.
48 * @return The new list.
50 pdeq *new_pdeq1(const void *x);
53 * Delete a double ended pointer list.
55 * @param dq The list to be deleted.
57 void del_pdeq(pdeq *dq);
60 * Returns the lenght of a double ended pointer list.
64 int pdeq_len(pdeq *dq);
67 * Checks if a list is empty.
71 * @return non-zero if the list is empty.
73 int pdeq_empty(pdeq *dq);
76 * Returns non-zero if a double ended pointer list
77 * contains a pointer x.
80 * @param x The pointer to be searched for.
82 int pdeq_contains(pdeq *dq, const void *x);
85 * Search a key in a double ended pointer list, the search
86 * is controlled by a compare function.
87 * An element is found, if the compare function returns 0.
88 * The search is started from the left site of the list.
91 * @param cmp The compare function.
92 * @param key The search key.
94 * @return The address of the element entry if the key was found,
97 void *pdeq_search(pdeq *qp, cmp_fun cmp, const void *key);
100 * Convert the double ended pointer list into a linear array beginning from
101 * left, the first element in the linear array will be the left one.
103 * @param qp The list.
104 * @param dst A pointer to a pointer array with must be at least
105 * pdeq_len(dq) * sizeof(void *)
109 void **pdeq_copyl(pdeq *qp, const void **dst);
112 * Convert the double ended pointer list into a linear array beginning from
113 * right, the first element in the linear array will be the right one.
115 * @param qp The list.
116 * @param dst A pointer to a pointer array with must be at least
117 * pdeq_len(dq) * sizeof(void *)
121 void **pdeq_copyr(pdeq *qp, const void **dst);
124 * Add a pointer to the left side of a double ended pointer list.
126 * @param dq The list to add a pointer to.
127 * @param x The pointer element to be added
131 pdeq *pdeq_putl(pdeq *dq, const void *x);
134 * Add a pointer to the right side of a double ended pointer list.
136 * @param dq The list to add a pointer to.
137 * @param x The pointer element to be added
141 pdeq *pdeq_putr(pdeq *dq, const void *x);
144 * Retrieve a pointer from the left site of a double ended pointer list.
148 * @return The pointer element.
150 * @remark This function will fail if the list is empty.
152 void *pdeq_getl(pdeq *dq);
155 * Retrieve a pointer from the right site of a double ended pointer list.
159 * @return The pointer element.
161 * @remark This function will fail if the list is empty.
163 void *pdeq_getr(pdeq *dq);
166 #define PDEQ_VRFY(deq) ((void)0)
168 #define PDEQ_VRFY(deq) _pdeq_vrfy ((deq))
169 void _pdeq_vrfy(pdeq *dq);
173 * The pdeq is often used as a wait queue. A helper
174 * type to support this.
179 * Creates a new pointer wait queue (fifo).
181 * @return A new queue.
183 #define new_waitq() new_pdeq()
186 * Delete a wait queue (fifo)
188 * @param wq The wait queue.
190 #define del_waitq(wq) del_pdeq(wq)
193 * Retrieve a pointer from the wait queue (fifo).
195 * @param wq The wait queue.
197 * @return The pointer element.
199 * @remark This function will fail if the queue is empty.
201 #define waitq_get(wq) pdeq_getl(wq)
204 * Add a pointer to the wait queue (fifo).
206 * @param wq The wait queue
207 * @param x The pointer element to be added
209 * @return The wait queue.
211 #define waitq_put(wq, x) pdeq_putr((wq), (x))
214 * Checks if a wait queue is empty.
216 * @param wq The wait queue.
218 * @return non-zero if the queue is empty.
220 #define waitq_empty(wq) pdeq_empty(wq)
223 * The pdeq can be used as a stack. A helper
224 * type to support this.
229 * Creates a new pointer stack (lifo).
231 * @return A new stack.
233 #define new_stack() new_pdeq()
236 * Pop a pointer from the stack (lifo).
238 * @param st The stack.
240 * @return The pointer element.
242 * @remark This function will fail if the stack is empty.
244 #define stack_pop(st) pdeq_getr(st)
247 * Push a pointer to the stack (lifo).
249 * @param st The stack.
250 * @param x The pointer element to be added
254 #define stack_push(st, x) pdeq_putr((st), (x))
257 * Checks if a stack is empty.
259 * @param st The stack.
261 * @return non-zero if the stack is empty.
263 #define stack_empty(st) pdeq_empty(wq)
265 #endif /* _PDEQ_H_ */