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

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