nsz Git - libfirm/blob - include/libfirm/adt/pdeq.h

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   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.
  10  *
  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.
  14  *
  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
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief       double ended queue of generic pointers.
  23  * @author      Christian von Roques
  24  * @version     $Id$
  25  */
  26 #ifndef FIRM_ADT_PDEQ_H
  27 #define FIRM_ADT_PDEQ_H
  28
  29 /**
  30  * The type of the pointer compare function.
  31  *
  32  * @param elem  The list element.
  33  * @param key   The user supplied key.
  34  *
  35  * @return 0 if the element matches the key, non-zero else.
  36  */
  37 typedef int (*cmp_fun)(const void *elem, const void *key);
  38
  39 /**
  40  * The pointer double ended queue (list).
  41  */
  42 typedef struct pdeq pdeq;
  43
  44 /**
  45  * Creates a new double ended pointer list.
  46  *
  47  * @return A new list.
  48  */
  49 pdeq *new_pdeq(void);
  50
  51 /**
  52  * Creates a new double ended pointer list and puts an initial pointer element in.
  53  *
  54  * @param x   The pointer element to put in.
  55  *
  56  * @return The new list.
  57  */
  58 pdeq *new_pdeq1(const void *x);
  59
  60 /**
  61  * Delete a double ended pointer list.
  62  *
  63  * @param dq   The list to be deleted.
  64  */
  65 void del_pdeq(pdeq *dq);
  66
  67 /**
  68  * Returns the lenght of a double ended pointer list.
  69  *
  70  * @param dq   The list.
  71  */
  72 int pdeq_len(pdeq *dq);
  73
  74 /**
  75  * Checks if a list is empty.
  76  *
  77  * @param dq   The list.
  78  *
  79  * @return  non-zero if the list is empty.
  80  */
  81 int pdeq_empty(pdeq *dq);
  82
  83 /**
  84  * Returns non-zero if a double ended pointer list
  85  * contains a pointer x.
  86  *
  87  * @param dq  The list.
  88  * @param x   The pointer to be searched for.
  89  */
  90 int pdeq_contains(pdeq *dq, const void *x);
  91
  92 /**
  93  * Search a key in a double ended pointer list, the search
  94  * is controlled by a compare function.
  95  * An element is found, if the compare function returns 0.
  96  * The search is started from the left site of the list.
  97  *
  98  * @param qp   The list.
  99  * @param cmp  The compare function.
 100  * @param key  The search key.
 101  *
 102  * @return The address of the element entry if the key was found,
 103  *         NULL else.
 104  */
 105 void *pdeq_search(pdeq *qp, cmp_fun cmp, const void *key);
 106
 107 /**
 108  * Convert the double ended pointer list into a linear array beginning from
 109  * left, the first element in the linear array will be the left one.
 110  *
 111  * @param qp   The list.
 112  * @param dst  A pointer to a pointer array with must be at least
 113  *             pdeq_len(dq) * sizeof(void *)
 114  *
 115  * @return  dst
 116  */
 117 void **pdeq_copyl(pdeq *qp, const void **dst);
 118
 119 /**
 120  * Convert the double ended pointer list into a linear array beginning from
 121  * right, the first element in the linear array will be the right one.
 122  *
 123  * @param qp   The list.
 124  * @param dst  A pointer to a pointer array with must be at least
 125  *             pdeq_len(dq) * sizeof(void *)
 126  *
 127  * @return  dst
 128  */
 129 void **pdeq_copyr(pdeq *qp, const void **dst);
 130
 131 /**
 132  * Add a pointer to the left side of a double ended pointer list.
 133  *
 134  * @param dq  The list to add a pointer to.
 135  * @param x   The pointer element to be added
 136  *
 137  * @return The list.
 138  */
 139 pdeq *pdeq_putl(pdeq *dq, const void *x);
 140
 141 /**
 142  * Add a pointer to the right side of a double ended pointer list.
 143  *
 144  * @param dq  The list to add a pointer to.
 145  * @param x   The pointer element to be added
 146  *
 147  * @return The list.
 148  */
 149 pdeq *pdeq_putr(pdeq *dq, const void *x);
 150
 151 /**
 152  * Retrieve (and remove) a pointer from the left site of a double ended pointer
 153  * list.
 154  *
 155  * @param dq   The list
 156  * @return The pointer element.
 157  * @remark This function will fail if the list is empty.
 158  */
 159 void *pdeq_getl(pdeq *dq);
 160
 161 /**
 162  * Retrieve (and remove) a pointer from the right site of a double ended pointer
 163  * list.
 164  *
 165  * @param dq   The list
 166  * @return The pointer element.
 167  * @remark This function will fail if the list is empty.
 168  */
 169 void *pdeq_getr(pdeq *dq);
 170
 171 #ifdef NDEBUG
 172 #define PDEQ_VRFY(deq) ((void)0)
 173 #else
 174 #define PDEQ_VRFY(deq) _pdeq_vrfy ((deq))
 175 void _pdeq_vrfy(pdeq *dq);
 176 #endif
 177
 178 /**
 179  * The pdeq is often used as a wait queue. A helper
 180  * type to support this.
 181  */
 182 typedef pdeq waitq;
 183
 184 /**
 185  * Creates a new pointer wait queue (fifo).
 186  *
 187  * @return A new queue.
 188  */
 189 #define new_waitq()  new_pdeq()
 190
 191 /**
 192  * Delete a wait queue (fifo)
 193  *
 194  * @param wq   The wait queue.
 195  */
 196 #define del_waitq(wq) del_pdeq(wq)
 197
 198 /**
 199  * Retrieve a pointer from the wait queue (fifo).
 200  *
 201  * @param wq   The wait queue.
 202  *
 203  * @return The pointer element.
 204  *
 205  * @remark This function will fail if the queue is empty.
 206  */
 207 #define waitq_get(wq)  pdeq_getl(wq)
 208
 209 /**
 210  * Add a pointer to the wait queue (fifo).
 211  *
 212  * @param wq  The wait queue
 213  * @param x   The pointer element to be added
 214  *
 215  * @return The wait queue.
 216  */
 217 #define waitq_put(wq, x) pdeq_putr((wq), (x))
 218
 219 /**
 220  * Checks if a wait queue is empty.
 221  *
 222  * @param wq   The wait queue.
 223  *
 224  * @return  non-zero if the queue is empty.
 225  */
 226 #define waitq_empty(wq) pdeq_empty(wq)
 227
 228 /**
 229  * The pdeq can be used as a stack. A helper
 230  * type to support this.
 231  */
 232 typedef pdeq stack;
 233
 234 /**
 235  * Creates a new pointer stack (lifo).
 236  *
 237  * @return A new stack.
 238  */
 239 #define new_stack()  new_pdeq()
 240
 241 /**
 242  * Pop a pointer from the stack (lifo).
 243  *
 244  * @param st   The stack.
 245  *
 246  * @return The pointer element.
 247  *
 248  * @remark This function will fail if the stack is empty.
 249  */
 250 #define stack_pop(st)  pdeq_getr(st)
 251
 252 /**
 253  * Push a pointer to the stack (lifo).
 254  *
 255  * @param st  The stack.
 256  * @param x   The pointer element to be added
 257  *
 258  * @return The stack.
 259  */
 260 #define stack_push(st, x) pdeq_putr((st), (x))
 261
 262 /**
 263  * Checks if a stack is empty.
 264  *
 265  * @param st   The stack.
 266  *
 267  * @return  non-zero if the stack is empty.
 268  */
 269 #define stack_empty(st) pdeq_empty(wq)
 270
 271 #endif