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
10 * @note Until now the code is entirely untested so it probably contains
19 typedef struct _plist_element plist_element_t;
20 typedef struct _plist plist_t;
23 * The plist data type.
27 * The obstack used for all allocations.
31 /* Set to 1 if plist uses a foreign obstack */
32 unsigned foreign_obstack : 1;
35 * First element in the list.
37 plist_element_t *first_element;
40 * Last element in the list.
42 plist_element_t *last_element;
45 * Current number of elements in the list.
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.
54 plist_element_t* first_free_element;
58 * An element in the pointer list.
60 struct _plist_element {
61 plist_element_t *next;
62 plist_element_t *prev;
67 * Creates a new pointer list and initializes it.
68 * @return The newly created pointer list.
70 plist_t *plist_new(void);
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.
78 plist_t *plist_obstack_new(struct obstack *obst);
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.
85 void plist_free(plist_t *list);
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.
92 #define plist_count(list) \
93 ((list)->element_count)
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.
100 void plist_insert_back(plist_t *list, void *value);
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.
107 void plist_insert_front(plist_t *list, void *value);
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.
117 void plist_insert_before(plist_t *list, plist_element_t *element, void *value);
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.
127 void plist_insert_after(plist_t *list, plist_element_t *element, void *value);
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
135 int plist_has_value(plist_t *list, void *value);
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
143 plist_element_t *plist_find_value(plist_t *list, void *value);
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
151 void plist_erase(plist_t *list, plist_element_t *element);
154 * Erases all elements from the specified pointer list.
155 * @param list the pointer list that should be cleared.
157 void plist_clear(plist_t *list);
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
164 #define plist_first(list) \
165 ((list)->first_element)
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
172 #define plist_last(list) \
173 ((list)->last_element)
176 * Checks whether a pointer list element has a successor or not.
177 * @param element the list element that should be queried for existence
179 * @return TRUE if @p element has a successor, otherwise FALSE.
181 #define plist_element_has_next(element) \
182 ((element)->next != NULL)
185 * Checks whether a pointer list element has a predecessor or not.
186 * @param element the list element that should be queried for existence
188 * @return TRUE if @p element has a successor, otherwise FALSE.
190 #define plist_element_has_prev(element) \
191 ((element)->prev != NULL)
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.
199 #define plist_element_get_next(element) \
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.
208 #define plist_element_get_prev(element) \
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.
216 #define plist_element_get_value(element) \
220 * Convenience macro to iterate over a plist.
222 #define foreach_plist(list, el) \
223 for (el = plist_first(list); el; el = plist_element_get_next(el))