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