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 14.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
  14 #include "plist.h"
  15
  16 /**
  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
  19  * obstack.
  20  * @param list the list for which to allocate the element.
  21  * @return the newly allocated, uninitialized element.
  22  */
  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;
  29         } else {
  30                 newElement = obstack_alloc(&list->obst, sizeof(*newElement));
  31         }
  32         return newElement;
  33 }
  34
  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;
  42         return list;
  43 }
  44
  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;
  51         xfree(list);
  52 }
  53
  54 void plist_insert_back(PList* list, void* value) {
  55         if (list->lastElement != NULL) {
  56                 plist_insert_after(list, list->lastElement, value);
  57         } else {
  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;
  64         }
  65 }
  66
  67 void plist_insert_front(PList* list, void* value) {
  68         if (list->firstElement != NULL) {
  69                 plist_insert_before(list, list->firstElement, value);
  70         } else {
  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;
  77         }
  78 }
  79
  80 void plist_insert_before(PList* list, PListElement* element, void* value) {
  81         PListElement* prevElement;
  82         PListElement* newElement = allocate_element(list);
  83
  84         newElement->data = value;
  85         newElement->next = element;
  86         prevElement = element->prev;
  87         newElement->prev = prevElement;
  88         if (prevElement != NULL) {
  89                 prevElement->next = newElement;
  90         } else {
  91                 list->firstElement = newElement;
  92         }
  93         element->prev = newElement;
  94         ++list->elementCount;
  95 }
  96
  97 void plist_insert_after(PList* list, PListElement* element, void* value) {
  98         PListElement* nextElement;
  99         PListElement* newElement = allocate_element(list);
 100
 101         newElement->data = value;
 102         newElement->prev = element;
 103         nextElement = element->next;
 104         newElement->next = nextElement;
 105         if (nextElement != NULL) {
 106                 nextElement->prev = newElement;
 107         } else {
 108                 list->lastElement = newElement;
 109         }
 110         element->next = newElement;
 111         ++list->elementCount;
 112 }
 113
 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;
 119         } else {
 120                 list->lastElement = prevElement;
 121         }
 122         if (prevElement != NULL) {
 123                 prevElement->next = nextElement;
 124         } else {
 125                 list->firstElement = nextElement;
 126         }
 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;
 132 }
 133
 134 void plist_clear(PList* list) {
 135         PListElement* currentElement = list->firstElement;
 136         while (currentElement != NULL) {
 137                 currentElement->prev = NULL;
 138                 currentElement = currentElement->next;
 139         }
 140         currentElement = list->lastElement;
 141         if (currentElement != NULL) {
 142                 currentElement->next = list->firstFreeElement;
 143         }
 144         list->firstFreeElement = list->firstElement;
 145         list->firstElement = list->lastElement = 0;
 146         list->elementCount = 0;
 147 }