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
7 * @author Kimon Hoffmann
9 * @note Until now the code is entirely untested so it probably contains
18 typedef struct PListElement PListElement;
19 typedef struct PList PList;
22 * The Plist data type.
26 * The obstack used for all allocations.
30 * First element in the list.
32 PListElement* firstElement;
34 * Last element in the list.
36 PListElement* lastElement;
38 * Current number of elements in the list.
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.
46 PListElement* firstFreeElement;
50 * An element in the pointer list.
59 * Creates a new pointer list and initializes it.
60 * @return The newly created pointer list.
62 PList* plist_new(void);
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.
69 void plist_free(PList* list);
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.
76 #define plist_count(list) \
77 ((list)->elementCount)
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.
84 void plist_insert_back(PList* list, void* value);
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.
91 void plist_insert_front(PList* list, void* value);
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.
101 void plist_insert_before(PList* list, PListElement* element, void* value);
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.
111 void plist_insert_after(PList* list, PListElement* element, void* value);
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
119 void plist_erase(PList* list, PListElement* element);
122 * Erases all elements from the specified pointer list.
123 * @param list the pointer list that should be cleard.
125 void plist_clear(PList* list);
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
132 #define plist_first(list) \
133 ((list)->firstElement)
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
140 #define plist_last(list) \
141 ((list)->lastElement)
144 * Checks whether a pointer list element has a successor or not.
145 * @param element the list element that should be queried for existance
147 * @return TRUE if @p element has a successor, otherwise FALSE.
149 #define plist_element_has_next(element) \
150 ((element)->next != NULL)
153 * Checks whether a pointer list element has a predecessor or not.
154 * @param element the list element that should be queried for existance
156 * @return TRUE if @p element has a successor, otherwise FALSE.
158 #define plist_element_has_prev(element) \
159 ((element)->prev != NULL)
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.
167 #define plist_element_get_next(element) \
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.
176 #define plist_element_get_prev(element) \
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.
184 #define plist_element_get_value(element) \