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
17 * Helper macro that returns a new uninitialized list element by either
18 * fetching one from the free-list or allocating a new one on the lists
20 * @param list the list for which to allocate the element.
21 * @return the newly allocated, uninitialized element.
23 static PListElement* allocate_element(PList* list) {
24 PListElement* newElement;
25 if (list->firstFreeElement != NULL) {
26 newElement = list->firstFreeElement;
27 list->firstFreeElement = newElement->next;
28 newElement->next = NULL;
30 newElement = obstack_alloc(&list->obst, sizeof(*newElement));
35 PList* plist_new(void) {
36 PList* list = xmalloc(sizeof(*list));
37 obstack_init(&list->obst);
38 list->firstElement = NULL;
39 list->lastElement = NULL;
40 list->firstFreeElement = NULL;
41 list->elementCount = 0;
45 void plist_free(PList* list) {
46 obstack_free(&list->obst, NULL);
47 list->firstElement = NULL;
48 list->lastElement = NULL;
49 list->firstFreeElement = NULL;
50 list->elementCount = 0;
54 void plist_insert_back(PList* list, void* value) {
55 if (list->lastElement != NULL) {
56 plist_insert_after(list, list->lastElement, value);
58 PListElement* newElement = allocate_element(list);
59 newElement->data = value;
60 newElement->prev = NULL;
61 newElement->next = NULL;
62 list->firstElement = list->lastElement = newElement;
63 list->elementCount = 1;
67 void plist_insert_front(PList* list, void* value) {
68 if (list->firstElement != NULL) {
69 plist_insert_before(list, list->firstElement, value);
71 PListElement* newElement = allocate_element(list);
72 newElement->data = value;
73 newElement->prev = NULL;
74 newElement->next = NULL;
75 list->firstElement = list->lastElement = newElement;
76 list->elementCount = 1;
80 void plist_insert_before(PList* list, PListElement* element, void* value) {
81 PListElement* prevElement;
82 PListElement* newElement = allocate_element(list);
84 newElement->data = value;
85 newElement->next = element;
86 prevElement = element->prev;
87 newElement->prev = prevElement;
88 if (prevElement != NULL) {
89 prevElement->next = newElement;
91 list->firstElement = newElement;
93 element->prev = newElement;
97 void plist_insert_after(PList* list, PListElement* element, void* value) {
98 PListElement* nextElement;
99 PListElement* newElement = allocate_element(list);
101 newElement->data = value;
102 newElement->prev = element;
103 nextElement = element->next;
104 newElement->next = nextElement;
105 if (nextElement != NULL) {
106 nextElement->prev = newElement;
108 list->lastElement = newElement;
110 element->next = newElement;
111 ++list->elementCount;
114 void plist_erase(PList* list, PListElement* element) {
115 PListElement* nextElement = element->next;
116 PListElement* prevElement = element->prev;
117 if (nextElement != NULL) {
118 nextElement->prev = prevElement;
120 list->lastElement = prevElement;
122 if (prevElement != NULL) {
123 prevElement->next = nextElement;
125 list->firstElement = nextElement;
127 --list->elementCount;
128 /* Clean the element and prepend it to the free list */
129 element->prev = NULL; /* The allocation code expects prev to be NULL */
130 element->next = list->firstFreeElement;
131 list->firstFreeElement = element;
134 void plist_clear(PList* list) {
135 PListElement* currentElement = list->firstElement;
136 while (currentElement != NULL) {
137 currentElement->prev = NULL;
138 currentElement = currentElement->next;
140 currentElement = list->lastElement;
141 if (currentElement != NULL) {
142 currentElement->next = list->firstFreeElement;
144 list->firstFreeElement = list->firstElement;
145 list->firstElement = list->lastElement = 0;
146 list->elementCount = 0;