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