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* newElement;
27 if (list->first_free_element != NULL) {
28 newElement = list->first_free_element;
29 list->first_free_element = newElement->next;
30 newElement->next = NULL;
33 newElement = obstack_alloc(&list->obst, sizeof(*newElement));
39 plist_t* plist_new(void) {
40 plist_t* list = xmalloc(sizeof(*list));
42 obstack_init(&list->obst);
43 list->first_element = NULL;
44 list->last_element = NULL;
45 list->first_free_element = NULL;
46 list->element_count = 0;
51 void plist_free(plist_t* list) {
52 obstack_free(&list->obst, NULL);
54 list->first_element = NULL;
55 list->last_element = NULL;
56 list->first_free_element = NULL;
57 list->element_count = 0;
61 void plist_insert_back(plist_t* list, void* value) {
62 if (list->last_element != NULL) {
63 plist_insert_after(list, list->last_element, value);
66 plist_element_t* newElement = allocate_element(list);
68 newElement->data = value;
69 newElement->prev = NULL;
70 newElement->next = NULL;
71 list->first_element = list->last_element = newElement;
72 list->element_count = 1;
76 void plist_insert_front(plist_t* list, void* value) {
77 if (list->first_element != NULL) {
78 plist_insert_before(list, list->first_element, value);
81 plist_element_t* newElement = allocate_element(list);
83 newElement->data = value;
84 newElement->prev = NULL;
85 newElement->next = NULL;
86 list->first_element = list->last_element = newElement;
87 list->element_count = 1;
91 void plist_insert_before(plist_t* list, plist_element_t* element, void* value) {
92 plist_element_t* prevElement;
93 plist_element_t* newElement = allocate_element(list);
95 newElement->data = value;
96 newElement->next = element;
97 prevElement = element->prev;
98 newElement->prev = prevElement;
100 if (prevElement != NULL) {
101 prevElement->next = newElement;
104 list->first_element = newElement;
107 element->prev = newElement;
108 ++list->element_count;
111 void plist_insert_after(plist_t* list, plist_element_t* element, void* value) {
112 plist_element_t* nextElement;
113 plist_element_t* newElement = allocate_element(list);
115 newElement->data = value;
116 newElement->prev = element;
117 nextElement = element->next;
118 newElement->next = nextElement;
120 if (nextElement != NULL) {
121 nextElement->prev = newElement;
124 list->last_element = newElement;
127 element->next = newElement;
128 ++list->element_count;
131 void plist_erase(plist_t* list, plist_element_t* element) {
132 plist_element_t* nextElement = element->next;
133 plist_element_t* prevElement = element->prev;
135 if (nextElement != NULL) {
136 nextElement->prev = prevElement;
139 list->last_element = prevElement;
142 if (prevElement != NULL) {
143 prevElement->next = nextElement;
146 list->first_element = nextElement;
149 --list->element_count;
151 /* Clean the element and prepend it to the free list */
152 element->prev = NULL; /* The allocation code expects prev to be NULL */
153 element->next = list->first_free_element;
154 list->first_free_element = element;
157 void plist_clear(plist_t* list) {
158 plist_element_t* currentElement = list->first_element;
160 while (currentElement != NULL) {
161 currentElement->prev = NULL;
162 currentElement = currentElement->next;
165 currentElement = list->last_element;
167 if (currentElement != NULL) {
168 currentElement->next = list->first_free_element;
171 list->first_free_element = list->first_element;
172 list->first_element = 0;
173 list->last_element = 0;
174 list->element_count = 0;