2 * Copyright (C) 1995-2007 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 * @summary 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....)
34 #ifndef FIRM_ADT_PLIST_H
35 #define FIRM_ADT_PLIST_H
40 typedef struct _plist_element plist_element_t;
41 typedef struct _plist plist_t;
44 * The plist data type.
48 * The obstack used for all allocations.
52 /* Set to 1 if plist uses a foreign obstack */
53 unsigned foreign_obstack : 1;
56 * First element in the list.
58 plist_element_t *first_element;
61 * Last element in the list.
63 plist_element_t *last_element;
66 * Current number of elements in the list.
71 * First element in the free list.
72 * Please note that the free list is a single linked list and all back
73 * references are invalid.
75 plist_element_t* first_free_element;
79 * An element in the pointer list.
81 struct _plist_element {
82 plist_element_t *next;
83 plist_element_t *prev;
88 * Creates a new pointer list and initializes it.
89 * @return The newly created pointer list.
91 plist_t *plist_new(void);
94 * Creates a new pointer list and initializes it.
95 * Uses the given obstack instead of creating one.
96 * @param obst The obstack to use
97 * @return The newly created pointer list.
99 plist_t *plist_obstack_new(struct obstack *obst);
102 * Frees the passed pointer list.
103 * After a call to this function all references to the list and any of
104 * its elements are invalid.
106 void plist_free(plist_t *list);
109 * Returns the number of elements in a pointer list.
110 * @param list the pointer list
111 * @return The number of elements in a pointer list.
113 #define plist_count(list) \
114 ((list)->element_count)
117 * Inserts an element at the back of a pointer list.
118 * @param list the pointer list to append the new element to.
119 * @param value the element value to append.
121 void plist_insert_back(plist_t *list, void *value);
124 * Inserts an element at the front of a pointer list.
125 * @param list the pointer list to prepend the new element to.
126 * @param value the element value to prepend.
128 void plist_insert_front(plist_t *list, void *value);
131 * Inserts an element into a pointer list before the specified element,
132 * which must be non null.
133 * @param list the pointer list to insert the new element into.
134 * @param element the list element before which the new element should
135 * be inserted. This element must be a part of @p list.
136 * @param value the element value to insert.
138 void plist_insert_before(plist_t *list, plist_element_t *element, void *value);
141 * Inserts an element into a pointer list after the specified element,
142 * which must be non null.
143 * @param list the pointer list to insert the new element into.
144 * @param element the list element after which the new element should
145 * be inserted. This element must be a part of @p list.
146 * @param value the element value to insert.
148 void plist_insert_after(plist_t *list, plist_element_t *element, void *value);
151 * Checks if list has an element with the given data pointer.
152 * @param list the list to check
153 * @param value the data pointer to look for
154 * @return 1 if element with data pointer found, 0 otherwise
156 int plist_has_value(plist_t *list, void *value);
159 * Tries to find list element associated to the given data pointer.
160 * @param list the list to check
161 * @param value the data pointer to look for
162 * @return The first list element associated to data pointer if found, NULL otherwise
164 plist_element_t *plist_find_value(plist_t *list, void *value);
167 * Erases the specified element from the pointer list.
168 * @param list the pointer list from which the element should be erased.
169 * @param element the list element to erase. This element must be a part
172 void plist_erase(plist_t *list, plist_element_t *element);
175 * Erases all elements from the specified pointer list.
176 * @param list the pointer list that should be cleared.
178 void plist_clear(plist_t *list);
181 * Returns the first element of a pointer list.
182 * @param list the pointer list to iterate
183 * @return a pointer to the element or NULL if the list is empty
185 #define plist_first(list) \
186 ((list)->first_element)
189 * Returns the last element of a pointer list.
190 * @param list the pointer list to iterate
191 * @return a pointer to the element or NULL if the list is empty
193 #define plist_last(list) \
194 ((list)->last_element)
197 * Checks whether a pointer list element has a successor or not.
198 * @param element the list element that should be queried for existence
200 * @return TRUE if @p element has a successor, otherwise FALSE.
202 #define plist_element_has_next(element) \
203 ((element)->next != NULL)
206 * Checks whether a pointer list element has a predecessor or not.
207 * @param element the list element that should be queried for existence
209 * @return TRUE if @p element has a successor, otherwise FALSE.
211 #define plist_element_has_prev(element) \
212 ((element)->prev != NULL)
215 * Gets the successor of the passed list element.
216 * @param element the list element to return the successor of.
217 * @return The successor of @p element or NULL if @p element is the last
218 * element in the sequence.
220 #define plist_element_get_next(element) \
224 * Gets the predecessor of the passed list element.
225 * @param element the list element to return the predecessor of.
226 * @return The predecessor of @p element or NULL if @p element is the last
227 * element in the sequence.
229 #define plist_element_get_prev(element) \
233 * Gets the value stored in the passed list element.
234 * @param element the list element to return the value of.
235 * @return The value stored in @p element.
237 #define plist_element_get_value(element) \
241 * Convenience macro to iterate over a plist.
243 #define foreach_plist(list, el) \
244 for (el = plist_first(list); el; el = plist_element_get_next(el))