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:
   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 dp  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 dq   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 dq   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 #endif /* _PDEQ_H_ */