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
9 * @note Until now the code is entirely untested so it probably contains
18 * Structure for one entry of the double linked pointer list.
31 * The obstack used for all allocations.
35 * First element in the list.
37 PListElement* firstElement;
39 * Last element in the list.
41 PListElement* lastElement;
43 * Current number of elements in the list.
47 * First element in the free list.
48 * Please note that the free list is a single linked list and all back
49 * references are invalid.
51 PListElement* firstFreeElement;
55 * Helper macro that returns a new uninitialized list element by either
56 * fetching one from the free-list or allocating a new one on the lists
58 * @param list the list for which to allocate the element.
59 * @return the newly allocated, uninitialized element.
61 static PListElement* allocate_element(PList* list) {
62 PListElement* newElement;
63 if (list->firstFreeElement != NULL) {
64 newElement = list->firstFreeElement;
65 list->firstFreeElement = newElement->next;
66 newElement->next = NULL;
68 newElement = obstack_alloc(&list->obst, sizeof(*newElement));
73 PList* plist_new(void) {
74 PList* list = xmalloc(sizeof(*list));
75 obstack_init(&list->obst);
76 list->firstElement = NULL;
77 list->lastElement = NULL;
78 list->firstFreeElement = NULL;
79 list->elementCount = 0;
83 void plist_free(PList* list) {
84 obstack_free(&list->obst, NULL);
85 list->firstElement = NULL;
86 list->lastElement = NULL;
87 list->firstFreeElement = NULL;
88 list->elementCount = 0;
92 void plist_insert_back(PList* list, void* value) {
93 if (list->lastElement != NULL) {
94 plist_insert_after(list, list->lastElement, value);
96 PListElement* newElement = allocate_element(list);
97 newElement->data = value;
98 newElement->prev = NULL;
99 newElement->next = NULL;
100 list->firstElement = list->lastElement = newElement;
101 list->elementCount = 1;
105 void plist_insert_front(PList* list, void* value) {
106 if (list->firstElement != NULL) {
107 plist_insert_before(list, list->firstElement, value);
109 PListElement* newElement = allocate_element(list);
110 newElement->data = value;
111 newElement->prev = NULL;
112 newElement->next = NULL;
113 list->firstElement = list->lastElement = newElement;
114 list->elementCount = 1;
118 void plist_insert_before(PList* list, PListElement* element, void* value) {
119 PListElement* prevElement;
120 PListElement* newElement = allocate_element(list);
122 newElement->data = value;
123 newElement->next = element;
124 prevElement = element->prev;
125 newElement->prev = prevElement;
126 if (prevElement != NULL) {
127 prevElement->next = newElement;
129 list->firstElement = newElement;
131 element->prev = newElement;
132 ++list->elementCount;
135 void plist_insert_after(PList* list, PListElement* element, void* value) {
136 PListElement* nextElement;
137 PListElement* newElement = allocate_element(list);
139 newElement->data = value;
140 newElement->prev = element;
141 nextElement = element->next;
142 newElement->next = nextElement;
143 if (nextElement != NULL) {
144 nextElement->prev = newElement;
146 list->lastElement = newElement;
148 element->next = newElement;
149 ++list->elementCount;
152 void plist_erase(PList* list, PListElement* element) {
153 PListElement* nextElement = element->next;
154 PListElement* prevElement = element->prev;
155 if (nextElement != NULL) {
156 nextElement->prev = prevElement;
158 list->lastElement = prevElement;
160 if (prevElement != NULL) {
161 prevElement->next = nextElement;
163 list->firstElement = nextElement;
165 --list->elementCount;
166 /* Clean the element and prepend it to the free list */
167 element->prev = NULL; /* The allocation code expects prev to be NULL */
168 element->next = list->firstFreeElement;
169 list->firstFreeElement = element;
172 void plist_clear(PList* list) {
173 PListElement* currentElement = list->firstElement;
174 while (currentElement != NULL) {
175 currentElement->prev = NULL;
176 currentElement = currentElement->next;
178 currentElement = list->lastElement;
179 if (currentElement != NULL) {
180 currentElement->next = list->firstFreeElement;
182 list->firstFreeElement = list->firstElement;
183 list->firstElement = list->lastElement = 0;
184 list->elementCount = 0;