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