nsz Git - libfirm/blob - ir/adt/plist.c

   1 /**
   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
   6  * elements.
   7  * @author Kimon Hoffmann
   8  * @date 17.07.2005
   9  * @note Until now the code is entirely untested so it probably contains
  10  *              plenty of errors.
  11  */
  12 #include <stdlib.h>
  13 #include "obst.h"
  14
  15 #include "plist.h"
  16
  17 /**
  18  * Structure for one entry of the double linked pointer list.
  19  */
  20 struct PListElement {
  21         PListElement* next;
  22         PListElement* prev;
  23         void* data;
  24 };
  25
  26 /**
  27  * The list data type.
  28  */
  29 struct PList {
  30         /**
  31          * The obstack used for all allocations.
  32          */
  33         struct obstack obst;
  34         /**
  35          * First element in the list.
  36          */
  37         PListElement* firstElement;
  38         /**
  39          * Last element in the list.
  40          */
  41         PListElement* lastElement;
  42         /**
  43          * Current number of elements in the list.
  44          */
  45         int elementCount;
  46         /**
  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.
  50          */
  51         PListElement* firstFreeElement;
  52 };
  53
  54 /**
  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
  57  * obstack.
  58  * @param list the list for which to allocate the element.
  59  * @return the newly allocated, uninitialized element.
  60  */
  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;
  67         } else {
  68                 newElement = obstack_alloc(&list->obst, sizeof(*newElement));
  69         }
  70         return newElement;
  71 }
  72
  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;
  80         return list;
  81 }
  82
  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;
  89         xfree(list);
  90 }
  91
  92 void plist_insert_back(PList* list, void* value) {
  93         if (list->lastElement != NULL) {
  94                 plist_insert_after(list, list->lastElement, value);
  95         } else {
  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;
 102         }
 103 }
 104
 105 void plist_insert_front(PList* list, void* value) {
 106         if (list->firstElement != NULL) {
 107                 plist_insert_before(list, list->firstElement, value);
 108         } else {
 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;
 115         }
 116 }
 117
 118 void plist_insert_before(PList* list, PListElement* element, void* value) {
 119   PListElement* prevElement;
 120         PListElement* newElement = allocate_element(list);
 121
 122         newElement->data = value;
 123         newElement->next = element;
 124         prevElement = element->prev;
 125         newElement->prev = prevElement;
 126         if (prevElement != NULL) {
 127                 prevElement->next = newElement;
 128         } else {
 129                 list->firstElement = newElement;
 130         }
 131         element->prev = newElement;
 132         ++list->elementCount;
 133 }
 134
 135 void plist_insert_after(PList* list, PListElement* element, void* value) {
 136   PListElement* nextElement;
 137         PListElement* newElement = allocate_element(list);
 138
 139         newElement->data = value;
 140         newElement->prev = element;
 141         nextElement = element->next;
 142         newElement->next = nextElement;
 143         if (nextElement != NULL) {
 144                 nextElement->prev = newElement;
 145         } else {
 146                 list->lastElement = newElement;
 147         }
 148         element->next = newElement;
 149         ++list->elementCount;
 150 }
 151
 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;
 157         } else {
 158                 list->lastElement = prevElement;
 159         }
 160         if (prevElement != NULL) {
 161                 prevElement->next = nextElement;
 162         } else {
 163                 list->firstElement = nextElement;
 164         }
 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;
 170 }
 171
 172 void plist_clear(PList* list) {
 173         PListElement* currentElement = list->firstElement;
 174         while (currentElement != NULL) {
 175                 currentElement->prev = NULL;
 176                 currentElement = currentElement->next;
 177         }
 178         currentElement = list->lastElement;
 179         if (currentElement != NULL) {
 180                 currentElement->next = list->firstFreeElement;
 181         }
 182         list->firstFreeElement = list->firstElement;
 183         list->firstElement = list->lastElement = 0;
 184         list->elementCount = 0;
 185 }