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