2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief double ended queue of generic pointers.
23 * @author Christian von Roques
26 #ifndef FIRM_ADT_PDEQ_H
27 #define FIRM_ADT_PDEQ_H
34 * The type of the pointer compare function.
36 * @param elem The list element.
37 * @param key The user supplied key.
39 * @return 0 if the element matches the key, non-zero else.
41 typedef int (*cmp_fun)(const void *elem, const void *key);
44 * The pointer double ended queue (list).
46 typedef struct pdeq pdeq;
49 * Creates a new double ended pointer list.
53 FIRM_API pdeq *new_pdeq(void);
56 * Creates a new double ended pointer list and puts an initial pointer element in.
58 * @param x The pointer element to put in.
60 * @return The new list.
62 FIRM_API pdeq *new_pdeq1(const void *x);
65 * Delete a double ended pointer list.
67 * @param dq The list to be deleted.
69 FIRM_API void del_pdeq(pdeq *dq);
72 * Returns the length of a double ended pointer list.
76 FIRM_API size_t pdeq_len(pdeq *dq);
79 * Checks if a list is empty.
83 * @return non-zero if the list is empty.
85 FIRM_API int pdeq_empty(pdeq *dq);
88 * Returns non-zero if a double ended pointer list
89 * contains a pointer x.
92 * @param x The pointer to be searched for.
94 FIRM_API int pdeq_contains(pdeq *dq, const void *x);
97 * Search a key in a double ended pointer list, the search
98 * is controlled by a compare function.
99 * An element is found, if the compare function returns 0.
100 * The search is started from the left site of the list.
102 * @param qp The list.
103 * @param cmp The compare function.
104 * @param key The search key.
106 * @return The address of the element entry if the key was found,
109 FIRM_API void *pdeq_search(pdeq *qp, cmp_fun cmp, const void *key);
112 * Convert the double ended pointer list into a linear array beginning from
113 * left, the first element in the linear array will be the left 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 FIRM_API void **pdeq_copyl(pdeq *qp, const void **dst);
124 * Convert the double ended pointer list into a linear array beginning from
125 * right, the first element in the linear array will be the right one.
127 * @param qp The list.
128 * @param dst A pointer to a pointer array with must be at least
129 * pdeq_len(dq) * sizeof(void *)
133 FIRM_API void **pdeq_copyr(pdeq *qp, const void **dst);
136 * Add a pointer to the left side of a double ended pointer list.
138 * @param dq The list to add a pointer to.
139 * @param x The pointer element to be added
143 FIRM_API pdeq *pdeq_putl(pdeq *dq, const void *x);
146 * Add a pointer to the right side of a double ended pointer list.
148 * @param dq The list to add a pointer to.
149 * @param x The pointer element to be added
153 FIRM_API pdeq *pdeq_putr(pdeq *dq, const void *x);
156 * Retrieve (and remove) a pointer from the left site of a double ended pointer
160 * @return The pointer element.
161 * @remark This function will fail if the list is empty.
163 FIRM_API void *pdeq_getl(pdeq *dq);
166 * Retrieve (and remove) a pointer from the right site of a double ended pointer
170 * @return The pointer element.
171 * @remark This function will fail if the list is empty.
173 FIRM_API void *pdeq_getr(pdeq *dq);
176 #define PDEQ_VRFY(deq) ((void)0)
178 #define PDEQ_VRFY(deq) _pdeq_vrfy ((deq))
179 FIRM_API void _pdeq_vrfy(pdeq *dq);
183 * The pdeq is often used as a wait queue. A helper
184 * type to support this.
189 * Creates a new pointer wait queue (fifo).
191 * @return A new queue.
193 #define new_waitq() new_pdeq()
196 * Delete a wait queue (fifo)
198 * @param wq The wait queue.
200 #define del_waitq(wq) del_pdeq(wq)
203 * Retrieve a pointer from the wait queue (fifo).
205 * @param wq The wait queue.
207 * @return The pointer element.
209 * @remark This function will fail if the queue is empty.
211 #define waitq_get(wq) pdeq_getl(wq)
214 * Add a pointer to the wait queue (fifo).
216 * @param wq The wait queue
217 * @param x The pointer element to be added
219 * @return The wait queue.
221 #define waitq_put(wq, x) pdeq_putr((wq), (x))
224 * Checks if a wait queue is empty.
226 * @param wq The wait queue.
228 * @return non-zero if the queue is empty.
230 #define waitq_empty(wq) pdeq_empty(wq)
233 * The pdeq can be used as a stack. A helper
234 * type to support this.
239 * Creates a new pointer stack (lifo).
241 * @return A new stack.
243 #define new_stack() new_pdeq()
246 * Pop a pointer from the stack (lifo).
248 * @param st The stack.
250 * @return The pointer element.
252 * @remark This function will fail if the stack is empty.
254 #define stack_pop(st) pdeq_getr(st)
257 * Push a pointer to the stack (lifo).
259 * @param st The stack.
260 * @param x The pointer element to be added
264 #define stack_push(st, x) pdeq_putr((st), (x))
267 * Checks if a stack is empty.
269 * @param st The stack.
271 * @return non-zero if the stack is empty.
273 #define stack_empty(st) pdeq_empty(wq)