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
18 * Helper macro that returns a new uninitialized list element by either
19 * fetching one from the free-list or allocating a new one on the lists
21 * @param list the list for which to allocate the element.
22 * @return the newly allocated, uninitialized element.
24 static plist_element_t *allocate_element(plist_t* list) {
25 plist_element_t *new_element;
27 if (list->first_free_element != NULL) {
28 new_element = list->first_free_element;
29 list->first_free_element = new_element->next;
30 new_element->next = NULL;
33 new_element = obstack_alloc(list->obst, sizeof(*new_element));
39 plist_t* plist_new(void) {
40 plist_t* list = xmalloc(sizeof(*list));
42 obstack_init(list->obst);
43 list->foreign_obstack = 0;
44 list->first_element = NULL;
45 list->last_element = NULL;
46 list->first_free_element = NULL;
47 list->element_count = 0;
52 plist_t *plist_obstack_new(struct obstack *obst) {
53 plist_t *list = obstack_alloc(obst, sizeof(*list));
56 list->foreign_obstack = 1;
57 list->first_element = NULL;
58 list->last_element = NULL;
59 list->first_free_element = NULL;
60 list->element_count = 0;
65 void plist_free(plist_t *list) {
66 list->first_element = NULL;
67 list->last_element = NULL;
68 list->first_free_element = NULL;
69 list->element_count = 0;
71 if (! list->foreign_obstack) {
72 obstack_free(list->obst, NULL);
77 void plist_insert_back(plist_t* list, void* value) {
78 if (list->last_element != NULL) {
79 plist_insert_after(list, list->last_element, value);
82 plist_element_t* newElement = allocate_element(list);
84 newElement->data = value;
85 newElement->prev = NULL;
86 newElement->next = NULL;
87 list->first_element = list->last_element = newElement;
88 list->element_count = 1;
92 void plist_insert_front(plist_t* list, void* value) {
93 if (list->first_element != NULL) {
94 plist_insert_before(list, list->first_element, value);
97 plist_element_t* newElement = allocate_element(list);
99 newElement->data = value;
100 newElement->prev = NULL;
101 newElement->next = NULL;
102 list->first_element = list->last_element = newElement;
103 list->element_count = 1;
107 void plist_insert_before(plist_t* list, plist_element_t* element, void* value) {
108 plist_element_t* prevElement;
109 plist_element_t* newElement = allocate_element(list);
111 newElement->data = value;
112 newElement->next = element;
113 prevElement = element->prev;
114 newElement->prev = prevElement;
116 if (prevElement != NULL) {
117 prevElement->next = newElement;
120 list->first_element = newElement;
123 element->prev = newElement;
124 ++list->element_count;
127 void plist_insert_after(plist_t* list, plist_element_t* element, void* value) {
128 plist_element_t* nextElement;
129 plist_element_t* newElement = allocate_element(list);
131 newElement->data = value;
132 newElement->prev = element;
133 nextElement = element->next;
134 newElement->next = nextElement;
136 if (nextElement != NULL) {
137 nextElement->prev = newElement;
140 list->last_element = newElement;
143 element->next = newElement;
144 ++list->element_count;
147 void plist_erase(plist_t *list, plist_element_t *element) {
148 plist_element_t *next_element = element->next;
149 plist_element_t *prev_element = element->prev;
151 if (next_element != NULL) {
152 next_element->prev = prev_element;
155 list->last_element = prev_element;
158 if (prev_element != NULL) {
159 prev_element->next = next_element;
162 list->first_element = next_element;
165 --list->element_count;
167 /* Clean the element and prepend it to the free list */
168 element->prev = NULL; /* The allocation code expects prev to be NULL */
169 element->next = list->first_free_element;
170 list->first_free_element = element;
173 void plist_clear(plist_t *list) {
174 plist_element_t *curr_element = list->first_element;
176 while (curr_element != NULL) {
177 curr_element->prev = NULL;
178 curr_element = curr_element->next;
181 curr_element = list->last_element;
183 if (curr_element != NULL) {
184 curr_element->next = list->first_free_element;
187 list->first_free_element = list->first_element;
188 list->first_element = 0;
189 list->last_element = 0;
190 list->element_count = 0;