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