2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Simple, non circular, double linked pointer list.
9 * @note Created because the properties of the standard circular list were not
10 * very well suited for the interference graph implementation.
11 * This list uses an obstack and a free-list to efficiently manage its
13 * @author Kimon Hoffmann
21 * Helper macro that returns a new uninitialized list element by either
22 * fetching one from the free-list or allocating a new one on the lists
24 * @param list the list for which to allocate the element.
25 * @return the newly allocated, uninitialized element.
27 static plist_element_t *allocate_element(plist_t* list)
29 plist_element_t *new_element;
31 if (list->first_free_element != NULL) {
32 new_element = list->first_free_element;
33 list->first_free_element = new_element->next;
34 new_element->next = NULL;
37 new_element = OALLOC(list->obst, plist_element_t);
43 plist_t *plist_new(void)
45 plist_t *list = (plist_t*) xmalloc(sizeof(*list) + sizeof(*list->obst));
47 list->obst = (struct obstack *)&list[1];
48 list->foreign_obstack = 0;
49 list->first_element = NULL;
50 list->last_element = NULL;
51 list->first_free_element = NULL;
52 list->element_count = 0;
54 obstack_init(list->obst);
58 plist_t *plist_obstack_new(struct obstack *obst)
60 plist_t *list = OALLOC(obst, plist_t);
63 list->foreign_obstack = 1;
64 list->first_element = NULL;
65 list->last_element = NULL;
66 list->first_free_element = NULL;
67 list->element_count = 0;
72 void plist_free(plist_t *list)
74 list->first_element = NULL;
75 list->last_element = NULL;
76 list->first_free_element = NULL;
77 list->element_count = 0;
79 if (! list->foreign_obstack) {
80 obstack_free(list->obst, NULL);
85 void plist_insert_back(plist_t *list, void *value)
87 if (list->last_element != NULL) {
88 plist_insert_after(list, list->last_element, value);
91 plist_element_t *newElement = allocate_element(list);
93 newElement->data = value;
94 newElement->prev = NULL;
95 newElement->next = NULL;
96 list->first_element = list->last_element = newElement;
97 list->element_count = 1;
101 void plist_insert_front(plist_t *list, void *value)
103 if (list->first_element != NULL) {
104 plist_insert_before(list, list->first_element, value);
107 plist_element_t *newElement = allocate_element(list);
109 newElement->data = value;
110 newElement->prev = NULL;
111 newElement->next = NULL;
112 list->first_element = list->last_element = newElement;
113 list->element_count = 1;
117 void plist_insert_before(plist_t *list, plist_element_t *element, void *value)
119 plist_element_t *prevElement;
120 plist_element_t *newElement = allocate_element(list);
122 newElement->data = value;
123 newElement->next = element;
124 prevElement = element->prev;
125 newElement->prev = prevElement;
127 if (prevElement != NULL) {
128 prevElement->next = newElement;
131 list->first_element = newElement;
134 element->prev = newElement;
135 ++list->element_count;
138 void plist_insert_after(plist_t* list, plist_element_t* element, void* value)
140 plist_element_t *nextElement;
141 plist_element_t *newElement = allocate_element(list);
143 newElement->data = value;
144 newElement->prev = element;
145 nextElement = element->next;
146 newElement->next = nextElement;
148 if (nextElement != NULL) {
149 nextElement->prev = newElement;
152 list->last_element = newElement;
155 element->next = newElement;
156 ++list->element_count;
159 int plist_has_value(plist_t *list, void *value)
161 plist_element_t *iter;
163 for (iter = plist_first(list); iter; iter = plist_element_get_next(iter)) {
164 if (plist_element_get_value(iter) == value)
171 plist_element_t *plist_find_value(plist_t *list, void *value)
173 plist_element_t *iter;
175 for (iter = plist_first(list); iter; iter = plist_element_get_next(iter)) {
176 if (plist_element_get_value(iter) == value)
183 void plist_erase(plist_t *list, plist_element_t *element)
185 plist_element_t *next_element = element->next;
186 plist_element_t *prev_element = element->prev;
188 if (next_element != NULL) {
189 next_element->prev = prev_element;
192 list->last_element = prev_element;
195 if (prev_element != NULL) {
196 prev_element->next = next_element;
199 list->first_element = next_element;
202 --list->element_count;
204 /* Clean the element and prepend it to the free list */
205 element->prev = NULL; /* The allocation code expects prev to be NULL */
206 element->next = list->first_free_element;
207 list->first_free_element = element;
210 void plist_clear(plist_t *list)
212 plist_element_t *curr_element = list->first_element;
214 while (curr_element != NULL) {
215 curr_element->prev = NULL;
216 curr_element = curr_element->next;
219 curr_element = list->last_element;
221 if (curr_element != NULL) {
222 curr_element->next = list->first_free_element;
225 list->first_free_element = list->first_element;
226 list->first_element = 0;
227 list->last_element = 0;
228 list->element_count = 0;