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 * @brief Simple, non circular, double linked pointer list.
23 * @note Created because the properties of the standard circular list were not
24 * very well suited for the interference graph implementation.
25 * This list uses an obstack and a free-list to efficiently manage its
27 * @author Kimon Hoffmann
35 * Helper macro that returns a new uninitialized list element by either
36 * fetching one from the free-list or allocating a new one on the lists
38 * @param list the list for which to allocate the element.
39 * @return the newly allocated, uninitialized element.
41 static plist_element_t *allocate_element(plist_t* list)
43 plist_element_t *new_element;
45 if (list->first_free_element != NULL) {
46 new_element = list->first_free_element;
47 list->first_free_element = new_element->next;
48 new_element->next = NULL;
51 new_element = OALLOC(list->obst, plist_element_t);
57 plist_t *plist_new(void)
59 plist_t *list = (plist_t*) xmalloc(sizeof(*list) + sizeof(*list->obst));
61 list->obst = (struct obstack *)&list[1];
62 list->foreign_obstack = 0;
63 list->first_element = NULL;
64 list->last_element = NULL;
65 list->first_free_element = NULL;
66 list->element_count = 0;
68 obstack_init(list->obst);
72 plist_t *plist_obstack_new(struct obstack *obst)
74 plist_t *list = OALLOC(obst, plist_t);
77 list->foreign_obstack = 1;
78 list->first_element = NULL;
79 list->last_element = NULL;
80 list->first_free_element = NULL;
81 list->element_count = 0;
86 void plist_free(plist_t *list)
88 list->first_element = NULL;
89 list->last_element = NULL;
90 list->first_free_element = NULL;
91 list->element_count = 0;
93 if (! list->foreign_obstack) {
94 obstack_free(list->obst, NULL);
99 void plist_insert_back(plist_t *list, void *value)
101 if (list->last_element != NULL) {
102 plist_insert_after(list, list->last_element, value);
105 plist_element_t *newElement = allocate_element(list);
107 newElement->data = value;
108 newElement->prev = NULL;
109 newElement->next = NULL;
110 list->first_element = list->last_element = newElement;
111 list->element_count = 1;
115 void plist_insert_front(plist_t *list, void *value)
117 if (list->first_element != NULL) {
118 plist_insert_before(list, list->first_element, value);
121 plist_element_t *newElement = allocate_element(list);
123 newElement->data = value;
124 newElement->prev = NULL;
125 newElement->next = NULL;
126 list->first_element = list->last_element = newElement;
127 list->element_count = 1;
131 void plist_insert_before(plist_t *list, plist_element_t *element, void *value)
133 plist_element_t *prevElement;
134 plist_element_t *newElement = allocate_element(list);
136 newElement->data = value;
137 newElement->next = element;
138 prevElement = element->prev;
139 newElement->prev = prevElement;
141 if (prevElement != NULL) {
142 prevElement->next = newElement;
145 list->first_element = newElement;
148 element->prev = newElement;
149 ++list->element_count;
152 void plist_insert_after(plist_t* list, plist_element_t* element, void* value)
154 plist_element_t *nextElement;
155 plist_element_t *newElement = allocate_element(list);
157 newElement->data = value;
158 newElement->prev = element;
159 nextElement = element->next;
160 newElement->next = nextElement;
162 if (nextElement != NULL) {
163 nextElement->prev = newElement;
166 list->last_element = newElement;
169 element->next = newElement;
170 ++list->element_count;
173 int plist_has_value(plist_t *list, void *value)
175 plist_element_t *iter;
177 for (iter = plist_first(list); iter; iter = plist_element_get_next(iter)) {
178 if (plist_element_get_value(iter) == value)
185 plist_element_t *plist_find_value(plist_t *list, void *value)
187 plist_element_t *iter;
189 for (iter = plist_first(list); iter; iter = plist_element_get_next(iter)) {
190 if (plist_element_get_value(iter) == value)
197 void plist_erase(plist_t *list, plist_element_t *element)
199 plist_element_t *next_element = element->next;
200 plist_element_t *prev_element = element->prev;
202 if (next_element != NULL) {
203 next_element->prev = prev_element;
206 list->last_element = prev_element;
209 if (prev_element != NULL) {
210 prev_element->next = next_element;
213 list->first_element = next_element;
216 --list->element_count;
218 /* Clean the element and prepend it to the free list */
219 element->prev = NULL; /* The allocation code expects prev to be NULL */
220 element->next = list->first_free_element;
221 list->first_free_element = element;
224 void plist_clear(plist_t *list)
226 plist_element_t *curr_element = list->first_element;
228 while (curr_element != NULL) {
229 curr_element->prev = NULL;
230 curr_element = curr_element->next;
233 curr_element = list->last_element;
235 if (curr_element != NULL) {
236 curr_element->next = list->first_free_element;
239 list->first_free_element = list->first_element;
240 list->first_element = 0;
241 list->last_element = 0;
242 list->element_count = 0;