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

   1 /**
   2  * Simple, non circular, double linked pointer list.
   3  * Created because the properties of the standard circular list were not
   4  * very well suited for the interference graph implementation.
   5  * This list uses an obstack and a free-list to efficiently manage its
   6  * elements.
   7  * @author Kimon Hoffmann
   8  * @date   14.07.2005
   9  * @cvs-id $Id$
  10  * @note Until now the code is entirely untested so it probably contains
  11  *              plenty of errors.
  12  */
  13 #ifndef _PLIST_H_
  14 #define _PLIST_H_
  15
  16 #include <stddef.h>
  17 #include "obst.h"
  18
  19 typedef struct _plist_element plist_element_t;
  20 typedef struct _plist plist_t;
  21
  22 /**
  23  * The plist data type.
  24  */
  25 struct _plist {
  26         /**
  27          * The obstack used for all allocations.
  28          */
  29         struct obstack *obst;
  30
  31         /* Set to 1 if plist uses a foreign obstack  */
  32         unsigned foreign_obstack : 1;
  33
  34         /**
  35          * First element in the list.
  36          */
  37         plist_element_t *first_element;
  38
  39         /**
  40          * Last element in the list.
  41          */
  42         plist_element_t *last_element;
  43
  44         /**
  45          * Current number of elements in the list.
  46          */
  47         int element_count;
  48
  49         /**
  50          * First element in the free list.
  51          * Please note that the free list is a single linked list and all back
  52          * references are invalid.
  53          */
  54         plist_element_t* first_free_element;
  55 };
  56
  57 /**
  58  * An element in the pointer list.
  59  */
  60 struct _plist_element {
  61         plist_element_t *next;
  62         plist_element_t *prev;
  63         void *data;
  64 };
  65
  66 /**
  67  * Creates a new pointer list and initializes it.
  68  * @return The newly created pointer list.
  69  */
  70 plist_t *plist_new(void);
  71
  72 /**
  73  * Creates a new pointer list and initializes it.
  74  * Uses the given obstack instead of creating one.
  75  * @param obst  The obstack to use
  76  * @return The newly created pointer list.
  77  */
  78 plist_t *plist_obstack_new(struct obstack *obst);
  79
  80 /**
  81  * Frees the passed pointer list.
  82  * After a call to this function all references to the list and any of
  83  * its elements are invalid.
  84  */
  85 void plist_free(plist_t *list);
  86
  87 /**
  88  * Returns the number of elements in a pointer list.
  89  * @param list the pointer list
  90  * @return The number of elements in a pointer list.
  91  */
  92 #define plist_count(list) \
  93         ((list)->element_count)
  94
  95 /**
  96  * Inserts an element at the back of a pointer list.
  97  * @param list the pointer list to append the new element to.
  98  * @param value the element value to append.
  99  */
 100 void plist_insert_back(plist_t *list, void *value);
 101
 102 /**
 103  * Inserts an element at the front of a pointer list.
 104  * @param list the pointer list to prepend the new element to.
 105  * @param value the element value to prepend.
 106  */
 107 void plist_insert_front(plist_t *list, void *value);
 108
 109 /**
 110  * Inserts an element into a pointer list before the specified element,
 111  * which must be non null.
 112  * @param list the pointer list to insert the new element into.
 113  * @param element the list element before which the new element should
 114  *              be inserted. This element must be a part of @p list.
 115  * @param value the element value to insert.
 116  */
 117 void plist_insert_before(plist_t *list, plist_element_t *element, void *value);
 118
 119 /**
 120  * Inserts an element into a pointer list after the specified element,
 121  * which must be non null.
 122  * @param list the pointer list to insert the new element into.
 123  * @param element the list element after which the new element should
 124  *              be inserted. This element must be a part of @p list.
 125  * @param value the element value to insert.
 126  */
 127 void plist_insert_after(plist_t *list, plist_element_t *element, void *value);
 128
 129 /**
 130  * Checks if list has an element with the given data pointer.
 131  * @param list   the list to check
 132  * @param value  the data pointer to look for
 133  * @return 1 if element with data pointer found, 0 otherwise
 134  */
 135 int plist_has_value(plist_t *list, void *value);
 136
 137 /**
 138  * Tries to find list element associated to the given data pointer.
 139  * @param list   the list to check
 140  * @param value  the data pointer to look for
 141  * @return The first list element associated to data pointer if found, NULL otherwise
 142  */
 143 plist_element_t *plist_find_value(plist_t *list, void *value);
 144
 145 /**
 146  * Erases the specified element from the pointer list.
 147  * @param list the pointer list from which the element should be erased.
 148  * @param element the list element to erase. This element must be a part
 149  *              of @p list.
 150  */
 151 void plist_erase(plist_t *list, plist_element_t *element);
 152
 153 /**
 154  * Erases all elements from the specified pointer list.
 155  * @param list the pointer list that should be cleared.
 156  */
 157 void plist_clear(plist_t *list);
 158
 159 /**
 160  * Returns the first element of a pointer list.
 161  * @param list the pointer list to iterate
 162  * @return a pointer to the element or NULL if the list is empty
 163  */
 164  #define plist_first(list) \
 165         ((list)->first_element)
 166
 167 /**
 168  * Returns the last element of a pointer list.
 169  * @param list the pointer list to iterate
 170  * @return a pointer to the element or NULL if the list is empty
 171  */
 172  #define plist_last(list) \
 173         ((list)->last_element)
 174
 175 /**
 176  * Checks whether a pointer list element has a successor or not.
 177  * @param element the list element that should be queried for existence
 178  *              of a successor.
 179  * @return TRUE if @p element has a successor, otherwise FALSE.
 180  */
 181 #define plist_element_has_next(element) \
 182         ((element)->next != NULL)
 183
 184 /**
 185  * Checks whether a pointer list element has a predecessor or not.
 186  * @param element the list element that should be queried for existence
 187  *              of a predecessor.
 188  * @return TRUE if @p element has a successor, otherwise FALSE.
 189  */
 190 #define plist_element_has_prev(element) \
 191         ((element)->prev != NULL)
 192
 193 /**
 194  * Gets the successor of the passed list element.
 195  * @param element the list element to return the successor of.
 196  * @return The successor of @p element or NULL if @p element is the last
 197  *              element in the sequence.
 198  */
 199 #define plist_element_get_next(element) \
 200         ((element)->next)
 201
 202 /**
 203  * Gets the predecessor of the passed list element.
 204  * @param element the list element to return the predecessor of.
 205  * @return The predecessor of @p element or NULL if @p element is the last
 206  *              element in the sequence.
 207  */
 208 #define plist_element_get_prev(element) \
 209         ((element)->prev)
 210
 211 /**
 212  * Gets the value stored in the passed list element.
 213  * @param element the list element to return the value of.
 214  * @return The value stored in @p element.
 215  */
 216 #define plist_element_get_value(element) \
 217         ((element)->data)
 218
 219 /**
 220  * Convenience macro to iterate over a plist.
 221  */
 222 #define foreach_plist(list, el) \
 223         for (el = plist_first(list); el; el = plist_element_get_next(el))
 224
 225 #endif /*_PLIST_H_*/