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 *new_element;
  26
  27         if (list->first_free_element != NULL) {
  28                 new_element              = list->first_free_element;
  29                 list->first_free_element = new_element->next;
  30                 new_element->next        = NULL;
  31         }
  32         else {
  33                 new_element = obstack_alloc(list->obst, sizeof(*new_element));
  34         }
  35
  36         return new_element;
  37 }
  38
  39 plist_t* plist_new(void) {
  40         plist_t* list = xmalloc(sizeof(*list));
  41
  42         obstack_init(list->obst);
  43         list->foreign_obstack    = 0;
  44         list->first_element      = NULL;
  45         list->last_element       = NULL;
  46         list->first_free_element = NULL;
  47         list->element_count      = 0;
  48
  49         return list;
  50 }
  51
  52 plist_t *plist_obstack_new(struct obstack *obst) {
  53         plist_t *list = obstack_alloc(obst, sizeof(*list));
  54
  55         list->obst               = obst;
  56         list->foreign_obstack    = 1;
  57         list->first_element      = NULL;
  58         list->last_element       = NULL;
  59         list->first_free_element = NULL;
  60         list->element_count      = 0;
  61
  62         return list;
  63 }
  64
  65 void plist_free(plist_t *list) {
  66         list->first_element      = NULL;
  67         list->last_element       = NULL;
  68         list->first_free_element = NULL;
  69         list->element_count      = 0;
  70
  71         if (! list->foreign_obstack) {
  72                 obstack_free(list->obst, NULL);
  73                 xfree(list);
  74         }
  75 }
  76
  77 void plist_insert_back(plist_t* list, void* value) {
  78         if (list->last_element != NULL) {
  79                 plist_insert_after(list, list->last_element, value);
  80         }
  81         else {
  82                 plist_element_t* newElement = allocate_element(list);
  83
  84                 newElement->data    = value;
  85                 newElement->prev    = NULL;
  86                 newElement->next    = NULL;
  87                 list->first_element = list->last_element = newElement;
  88                 list->element_count = 1;
  89         }
  90 }
  91
  92 void plist_insert_front(plist_t* list, void* value) {
  93         if (list->first_element != NULL) {
  94                 plist_insert_before(list, list->first_element, value);
  95         }
  96         else {
  97                 plist_element_t* newElement = allocate_element(list);
  98
  99                 newElement->data    = value;
 100                 newElement->prev    = NULL;
 101                 newElement->next    = NULL;
 102                 list->first_element = list->last_element = newElement;
 103                 list->element_count = 1;
 104         }
 105 }
 106
 107 void plist_insert_before(plist_t* list, plist_element_t* element, void* value) {
 108         plist_element_t* prevElement;
 109         plist_element_t* newElement = allocate_element(list);
 110
 111         newElement->data = value;
 112         newElement->next = element;
 113         prevElement      = element->prev;
 114         newElement->prev = prevElement;
 115
 116         if (prevElement != NULL) {
 117                 prevElement->next = newElement;
 118         }
 119         else {
 120                 list->first_element = newElement;
 121         }
 122
 123         element->prev = newElement;
 124         ++list->element_count;
 125 }
 126
 127 void plist_insert_after(plist_t* list, plist_element_t* element, void* value) {
 128         plist_element_t* nextElement;
 129         plist_element_t* newElement = allocate_element(list);
 130
 131         newElement->data = value;
 132         newElement->prev = element;
 133         nextElement      = element->next;
 134         newElement->next = nextElement;
 135
 136         if (nextElement != NULL) {
 137                 nextElement->prev = newElement;
 138         }
 139         else {
 140                 list->last_element = newElement;
 141         }
 142
 143         element->next = newElement;
 144         ++list->element_count;
 145 }
 146
 147 void plist_erase(plist_t *list, plist_element_t *element) {
 148         plist_element_t *next_element = element->next;
 149         plist_element_t *prev_element = element->prev;
 150
 151         if (next_element != NULL) {
 152                 next_element->prev = prev_element;
 153         }
 154         else {
 155                 list->last_element = prev_element;
 156         }
 157
 158         if (prev_element != NULL) {
 159                 prev_element->next = next_element;
 160         }
 161         else {
 162                 list->first_element = next_element;
 163         }
 164
 165         --list->element_count;
 166
 167         /* Clean the element and prepend it to the free list */
 168         element->prev            = NULL; /* The allocation code expects prev to be NULL */
 169         element->next            = list->first_free_element;
 170         list->first_free_element = element;
 171 }
 172
 173 void plist_clear(plist_t *list) {
 174         plist_element_t *curr_element = list->first_element;
 175
 176         while (curr_element != NULL) {
 177                 curr_element->prev = NULL;
 178                 curr_element       = curr_element->next;
 179         }
 180
 181         curr_element = list->last_element;
 182
 183         if (curr_element != NULL) {
 184                 curr_element->next = list->first_free_element;
 185         }
 186
 187         list->first_free_element = list->first_element;
 188         list->first_element      = 0;
 189         list->last_element       = 0;
 190         list->element_count      = 0;
 191 }