2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @author Kimon Hoffmann
25 * @brief Simple, non circular, double linked pointer list.
26 * Created because the properties of the standard circular list were
27 * not very well suited for the interference graph implementation.
28 * This list uses an obstack and a free-list to efficiently manage its
30 * @note Until now the code is entirely untested so it probably contains
31 * plenty of errors. (Matze: Is this still true, the code seems to be
32 * used at some places....)
35 #ifndef FIRM_ADT_PLIST_H
36 #define FIRM_ADT_PLIST_H
43 typedef struct plist_element plist_element_t;
44 typedef struct plist plist_t;
47 * The plist data type.
51 * The obstack used for all allocations.
55 /* Set to 1 if plist uses a foreign obstack */
56 unsigned foreign_obstack : 1;
59 * First element in the list.
61 plist_element_t *first_element;
64 * Last element in the list.
66 plist_element_t *last_element;
69 * Current number of elements in the list.
74 * First element in the free list.
75 * Please note that the free list is a single linked list and all back
76 * references are invalid.
78 plist_element_t* first_free_element;
82 * An element in the pointer list.
84 struct plist_element {
85 plist_element_t *next;
86 plist_element_t *prev;
91 * Creates a new pointer list and initializes it.
92 * @return The newly created pointer list.
94 FIRM_API plist_t *plist_new(void);
97 * Creates a new pointer list and initializes it.
98 * Uses the given obstack instead of creating one.
99 * @param obst The obstack to use
100 * @return The newly created pointer list.
102 FIRM_API plist_t *plist_obstack_new(struct obstack *obst);
105 * Frees the passed pointer list.
106 * After a call to this function all references to the list and any of
107 * its elements are invalid.
109 FIRM_API void plist_free(plist_t *list);
112 * Returns the number of elements in a pointer list.
113 * @param list the pointer list
114 * @return The number of elements in a pointer list.
116 #define plist_count(list) \
117 ((list)->element_count)
120 * Inserts an element at the back of a pointer list.
121 * @param list the pointer list to append the new element to.
122 * @param value the element value to append.
124 FIRM_API void plist_insert_back(plist_t *list, void *value);
127 * Inserts an element at the front of a pointer list.
128 * @param list the pointer list to prepend the new element to.
129 * @param value the element value to prepend.
131 FIRM_API void plist_insert_front(plist_t *list, void *value);
134 * Inserts an element into a pointer list before the specified element,
135 * which must be non null.
136 * @param list the pointer list to insert the new element into.
137 * @param element the list element before which the new element should
138 * be inserted. This element must be a part of @p list.
139 * @param value the element value to insert.
141 FIRM_API void plist_insert_before(plist_t *list, plist_element_t *element, void *value);
144 * Inserts an element into a pointer list after the specified element,
145 * which must be non null.
146 * @param list the pointer list to insert the new element into.
147 * @param element the list element after which the new element should
148 * be inserted. This element must be a part of @p list.
149 * @param value the element value to insert.
151 FIRM_API void plist_insert_after(plist_t *list, plist_element_t *element, void *value);
154 * Checks if list has an element with the given data pointer.
155 * @param list the list to check
156 * @param value the data pointer to look for
157 * @return 1 if element with data pointer found, 0 otherwise
159 FIRM_API int plist_has_value(plist_t *list, void *value);
162 * Tries to find list element associated to the given data pointer.
163 * @param list the list to check
164 * @param value the data pointer to look for
165 * @return The first list element associated to data pointer if found, NULL otherwise
167 FIRM_API plist_element_t *plist_find_value(plist_t *list, void *value);
170 * Erases the specified element from the pointer list.
171 * @param list the pointer list from which the element should be erased.
172 * @param element the list element to erase. This element must be a part
175 FIRM_API void plist_erase(plist_t *list, plist_element_t *element);
178 * Erases all elements from the specified pointer list.
179 * @param list the pointer list that should be cleared.
181 FIRM_API void plist_clear(plist_t *list);
184 * Returns the first element of a pointer list.
185 * @param list the pointer list to iterate
186 * @return a pointer to the element or NULL if the list is empty
188 #define plist_first(list) \
189 ((list)->first_element)
192 * Returns the last element of a pointer list.
193 * @param list the pointer list to iterate
194 * @return a pointer to the element or NULL if the list is empty
196 #define plist_last(list) \
197 ((list)->last_element)
200 * Checks whether a pointer list element has a successor or not.
201 * @param element the list element that should be queried for existence
203 * @return TRUE if @p element has a successor, otherwise FALSE.
205 #define plist_element_has_next(element) \
206 ((element)->next != NULL)
209 * Checks whether a pointer list element has a predecessor or not.
210 * @param element the list element that should be queried for existence
212 * @return TRUE if @p element has a successor, otherwise FALSE.
214 #define plist_element_has_prev(element) \
215 ((element)->prev != NULL)
218 * Gets the successor of the passed list element.
219 * @param element the list element to return the successor of.
220 * @return The successor of @p element or NULL if @p element is the last
221 * element in the sequence.
223 #define plist_element_get_next(element) \
227 * Gets the predecessor of the passed list element.
228 * @param element the list element to return the predecessor of.
229 * @return The predecessor of @p element or NULL if @p element is the last
230 * element in the sequence.
232 #define plist_element_get_prev(element) \
236 * Gets the value stored in the passed list element.
237 * @param element the list element to return the value of.
238 * @return The value stored in @p element.
240 #define plist_element_get_value(element) \
244 * Convenience macro to iterate over a plist.
246 #define foreach_plist(list, el) \
247 for (el = plist_first(list); el; el = plist_element_get_next(el))