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 obastack 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 numner 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 newlyallocated, 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* newElement = allocate_element(list);
 120         newElement->data = value;
 121         newElement->next = element;
 122         PListElement* prevElement = element->prev;
 123         newElement->prev = prevElement;
 124         if (prevElement != NULL) {
 125                 prevElement->next = newElement;
 126         } else {
 127                 list->firstElement = newElement;
 128         }
 129         element->prev = newElement;
 130         ++list->elementCount;
 131 }
 132
 133 void plist_insert_after(PList* list, PListElement* element, void* value) {
 134         PListElement* newElement = allocate_element(list);
 135         newElement->data = value;
 136         newElement->prev = element;
 137         PListElement* nextElement = element->next;
 138         newElement->next = nextElement;
 139         if (nextElement != NULL) {
 140                 nextElement->prev = newElement;
 141         } else {
 142                 list->lastElement = newElement;
 143         }
 144         element->next = newElement;
 145         ++list->elementCount;
 146 }
 147
 148 void plist_erase(PList* list, PListElement* element) {
 149         PListElement* nextElement = element->next;
 150         PListElement* prevElement = element->prev;
 151         if (nextElement != NULL) {
 152                 nextElement->prev = prevElement;
 153         } else {
 154                 list->lastElement = prevElement;
 155         }
 156         if (prevElement != NULL) {
 157                 prevElement->next = nextElement;
 158         } else {
 159                 list->firstElement = nextElement;
 160         }
 161         --list->elementCount;
 162         /* Clean the element and prepend it to the free list */
 163         element->prev = NULL; /* The allocation code exprects prev to be NULL */
 164         element->next = list->firstFreeElement;
 165         list->firstFreeElement = element;
 166 }
 167
 168 void plist_clear(PList* list) {
 169         PListElement* currentElement = list->firstElement;
 170         while (currentElement != NULL) {
 171                 currentElement->prev = NULL;
 172                 currentElement = currentElement->next;
 173         }
 174         currentElement = list->lastElement;
 175         if (currentElement != NULL) {
 176                 currentElement->next = list->firstFreeElement;
 177         }
 178         list->firstFreeElement = list->firstElement;
 179         list->firstElement = list->lastElement = 0;
 180         list->elementCount = 0;
 181 }