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  * @cvs-id $Id$
  10  * @note Until now the code is entirely untested so it probably contains
  11  *              plenty of errors.
  12  */
  13 #include <stdlib.h>
  14
  15 #include "plist.h"
  16
  17 /**
  18  * Helper macro that returns a new uninitialized list element by either
  19  * fetching one from the free-list or allocating a new one on the lists
  20  * obstack.
  21  * @param list the list for which to allocate the element.
  22  * @return the newly allocated, uninitialized element.
  23  */
  24 static plist_element_t* allocate_element(plist_t* list) {
  25         plist_element_t* newElement;
  26
  27         if (list->first_free_element != NULL) {
  28                 newElement               = list->first_free_element;
  29                 list->first_free_element = newElement->next;
  30                 newElement->next         = NULL;
  31         }
  32         else {
  33                 newElement = obstack_alloc(&list->obst, sizeof(*newElement));
  34         }
  35
  36         return newElement;
  37 }
  38
  39 plist_t* plist_new(void) {
  40         plist_t* list = xmalloc(sizeof(*list));
  41
  42         obstack_init(&list->obst);
  43         list->first_element      = NULL;
  44         list->last_element       = NULL;
  45         list->first_free_element = NULL;
  46         list->element_count      = 0;
  47
  48         return list;
  49 }
  50
  51 void plist_free(plist_t* list) {
  52         obstack_free(&list->obst, NULL);
  53
  54         list->first_element      = NULL;
  55         list->last_element       = NULL;
  56         list->first_free_element = NULL;
  57         list->element_count      = 0;
  58         xfree(list);
  59 }
  60
  61 void plist_insert_back(plist_t* list, void* value) {
  62         if (list->last_element != NULL) {
  63                 plist_insert_after(list, list->last_element, value);
  64         }
  65         else {
  66                 plist_element_t* newElement = allocate_element(list);
  67
  68                 newElement->data    = value;
  69                 newElement->prev    = NULL;
  70                 newElement->next    = NULL;
  71                 list->first_element = list->last_element = newElement;
  72                 list->element_count = 1;
  73         }
  74 }
  75
  76 void plist_insert_front(plist_t* list, void* value) {
  77         if (list->first_element != NULL) {
  78                 plist_insert_before(list, list->first_element, value);
  79         }
  80         else {
  81                 plist_element_t* newElement = allocate_element(list);
  82
  83                 newElement->data    = value;
  84                 newElement->prev    = NULL;
  85                 newElement->next    = NULL;
  86                 list->first_element = list->last_element = newElement;
  87                 list->element_count = 1;
  88         }
  89 }
  90
  91 void plist_insert_before(plist_t* list, plist_element_t* element, void* value) {
  92         plist_element_t* prevElement;
  93         plist_element_t* newElement = allocate_element(list);
  94
  95         newElement->data = value;
  96         newElement->next = element;
  97         prevElement      = element->prev;
  98         newElement->prev = prevElement;
  99
 100         if (prevElement != NULL) {
 101                 prevElement->next = newElement;
 102         }
 103         else {
 104                 list->first_element = newElement;
 105         }
 106
 107         element->prev = newElement;
 108         ++list->element_count;
 109 }
 110
 111 void plist_insert_after(plist_t* list, plist_element_t* element, void* value) {
 112         plist_element_t* nextElement;
 113         plist_element_t* newElement = allocate_element(list);
 114
 115         newElement->data = value;
 116         newElement->prev = element;
 117         nextElement      = element->next;
 118         newElement->next = nextElement;
 119
 120         if (nextElement != NULL) {
 121                 nextElement->prev = newElement;
 122         }
 123         else {
 124                 list->last_element = newElement;
 125         }
 126
 127         element->next = newElement;
 128         ++list->element_count;
 129 }
 130
 131 void plist_erase(plist_t* list, plist_element_t* element) {
 132         plist_element_t* nextElement = element->next;
 133         plist_element_t* prevElement = element->prev;
 134
 135         if (nextElement != NULL) {
 136                 nextElement->prev = prevElement;
 137         }
 138         else {
 139                 list->last_element = prevElement;
 140         }
 141
 142         if (prevElement != NULL) {
 143                 prevElement->next = nextElement;
 144         }
 145         else {
 146                 list->first_element = nextElement;
 147         }
 148
 149         --list->element_count;
 150
 151         /* Clean the element and prepend it to the free list */
 152         element->prev            = NULL; /* The allocation code expects prev to be NULL */
 153         element->next            = list->first_free_element;
 154         list->first_free_element = element;
 155 }
 156
 157 void plist_clear(plist_t* list) {
 158         plist_element_t* currentElement = list->first_element;
 159
 160         while (currentElement != NULL) {
 161                 currentElement->prev = NULL;
 162                 currentElement       = currentElement->next;
 163         }
 164
 165         currentElement = list->last_element;
 166
 167         if (currentElement != NULL) {
 168                 currentElement->next = list->first_free_element;
 169         }
 170
 171         list->first_free_element = list->first_element;
 172         list->first_element      = 0;
 173         list->last_element       = 0;
 174         list->element_count      = 0;
 175 }