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          * First element in the list.
  32          */
  33         plist_element_t *first_element;
  34         /**
  35          * Last element in the list.
  36          */
  37         plist_element_t *last_element;
  38         /**
  39          * Current number of elements in the list.
  40          */
  41         int element_count;
  42         /**
  43          * First element in the free list.
  44          * Please note that the free list is a single linked list and all back
  45          * references are invalid.
  46          */
  47         plist_element_t* first_free_element;
  48 };
  49
  50 /**
  51  * An element in the pointer list.
  52  */
  53 struct _plist_element {
  54         plist_element_t* next;
  55         plist_element_t* prev;
  56         void* data;
  57 };
  58
  59 /**
  60  * Creates a new pointer list and initializes it.
  61  * @return The newly created pointer list.
  62  */
  63 plist_t* plist_new(void);
  64
  65 /**
  66  * Frees the passed pointer list.
  67  * After a call to this function all references to the list and any of
  68  * its elements are invalid.
  69  */
  70 void plist_free(plist_t* list);
  71
  72 /**
  73  * Returns the number of elements in a pointer list.
  74  * @param list the pointer list
  75  * @return The number of elements in a pointer list.
  76  */
  77 #define plist_count(list) \
  78         ((list)->element_count)
  79
  80 /**
  81  * Inserts an element at the back of a pointer list.
  82  * @param list the pointer list to append the new element to.
  83  * @param value the element value to append.
  84  */
  85 void plist_insert_back(plist_t* list, void* value);
  86
  87 /**
  88  * Inserts an element at the front of a pointer list.
  89  * @param list the pointer list to prepend the new element to.
  90  * @param value the element value to prepend.
  91  */
  92 void plist_insert_front(plist_t* list, void* value);
  93
  94 /**
  95  * Inserts an element into a pointer list before the specified element,
  96  * which must be non null.
  97  * @param list the pointer list to insert the new element into.
  98  * @param element the list element before which the new element should
  99  *              be inserted. This element must be a part of @p list.
 100  * @param value the element value to insert.
 101  */
 102 void plist_insert_before(plist_t* list, plist_element_t* element, void* value);
 103
 104 /**
 105  * Inserts an element into a pointer list after the specified element,
 106  * which must be non null.
 107  * @param list the pointer list to insert the new element into.
 108  * @param element the list element after which the new element should
 109  *              be inserted. This element must be a part of @p list.
 110  * @param value the element value to insert.
 111  */
 112 void plist_insert_after(plist_t* list, plist_element_t* element, void* value);
 113
 114 /**
 115  * Erases the specified element from the pointer list.
 116  * @param list the pointer list from which the lement should be erased.
 117  * @param element the list element to erase. This element must be a part
 118  *              of @p list.
 119  */
 120 void plist_erase(plist_t* list, plist_element_t* element);
 121
 122 /**
 123  * Erases all elements from the specified pointer list.
 124  * @param list the pointer list that should be cleard.
 125  */
 126 void plist_clear(plist_t* list);
 127
 128 /**
 129  * Returns the first element of a pointer list.
 130  * @param list the pointer list to iterate
 131  * @return a pointer to the element or NULL if the list is empty
 132  */
 133  #define plist_first(list) \
 134         ((list)->first_element)
 135
 136 /**
 137  * Returns the last element of a pointer list.
 138  * @param list the pointer list to iterate
 139  * @return a pointer to the element or NULL if the list is empty
 140  */
 141  #define plist_last(list) \
 142         ((list)->last_element)
 143
 144 /**
 145  * Checks whether a pointer list element has a successor or not.
 146  * @param element the list element that should be queried for existance
 147  *              of a successor.
 148  * @return TRUE if @p element has a successor, otherwise FALSE.
 149  */
 150 #define plist_element_has_next(element) \
 151         ((element)->next != NULL)
 152
 153 /**
 154  * Checks whether a pointer list element has a predecessor or not.
 155  * @param element the list element that should be queried for existance
 156  *              of a predecessor.
 157  * @return TRUE if @p element has a successor, otherwise FALSE.
 158  */
 159 #define plist_element_has_prev(element) \
 160         ((element)->prev != NULL)
 161
 162 /**
 163  * Gets the successor of the passed list element.
 164  * @param element the list element to return the successor of.
 165  * @return The successor of @p element or NULL if @p element is the last
 166  *              element in the sequence.
 167  */
 168 #define plist_element_get_next(element) \
 169         ((element)->next)
 170
 171 /**
 172  * Gets the predecessor of the passed list element.
 173  * @param element the list element to return the predecessor of.
 174  * @return The predecessor of @p element or NULL if @p element is the last
 175  *              element in the sequence.
 176  */
 177 #define plist_element_get_prev(element) \
 178         ((element)->prev)
 179
 180 /**
 181  * Gets the value stored in the passed list element.
 182  * @param element the list element to return the value of.
 183  * @return The value stored in @p element.
 184  */
 185 #define plist_element_get_value(element) \
 186         ((element)->data)
 187
 188 /**
 189  * Convenience macro to iterate over a plist.
 190  */
 191 #define foreach_plist(list, el) \
 192         for (el = plist_first(list); el; el = plist_element_get_next(el))
 193
 194 #endif /*_PLIST_H_*/