nsz Git - libfirm/blob - ir/adt/plist.c

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief Simple, non circular, double linked pointer list.
   9  * @note  Created because the properties of the standard circular list were not
  10  *        very well suited for the interference graph implementation.
  11  *        This list uses an obstack and a free-list to efficiently manage its
  12  *        elements.
  13  * @author  Kimon Hoffmann
  14  * @date    14.07.2005
  15  */
  16 #include <stdlib.h>
  17
  18 #include "plist.h"
  19
  20 /**
  21  * Helper macro that returns a new uninitialized list element by either
  22  * fetching one from the free-list or allocating a new one on the lists
  23  * obstack.
  24  * @param list the list for which to allocate the element.
  25  * @return the newly allocated, uninitialized element.
  26  */
  27 static plist_element_t *allocate_element(plist_t* list)
  28 {
  29         plist_element_t *new_element;
  30
  31         if (list->first_free_element != NULL) {
  32                 new_element              = list->first_free_element;
  33                 list->first_free_element = new_element->next;
  34                 new_element->next        = NULL;
  35         }
  36         else {
  37                 new_element = OALLOC(list->obst, plist_element_t);
  38         }
  39
  40         return new_element;
  41 }
  42
  43 plist_t *plist_new(void)
  44 {
  45         plist_t *list = (plist_t*) xmalloc(sizeof(*list) + sizeof(*list->obst));
  46
  47         list->obst               = (struct obstack *)&list[1];
  48         list->foreign_obstack    = 0;
  49         list->first_element      = NULL;
  50         list->last_element       = NULL;
  51         list->first_free_element = NULL;
  52         list->element_count      = 0;
  53
  54         obstack_init(list->obst);
  55         return list;
  56 }
  57
  58 plist_t *plist_obstack_new(struct obstack *obst)
  59 {
  60         plist_t *list = OALLOC(obst, plist_t);
  61
  62         list->obst               = obst;
  63         list->foreign_obstack    = 1;
  64         list->first_element      = NULL;
  65         list->last_element       = NULL;
  66         list->first_free_element = NULL;
  67         list->element_count      = 0;
  68
  69         return list;
  70 }
  71
  72 void plist_free(plist_t *list)
  73 {
  74         list->first_element      = NULL;
  75         list->last_element       = NULL;
  76         list->first_free_element = NULL;
  77         list->element_count      = 0;
  78
  79         if (! list->foreign_obstack) {
  80                 obstack_free(list->obst, NULL);
  81                 xfree(list);
  82         }
  83 }
  84
  85 void plist_insert_back(plist_t *list, void *value)
  86 {
  87         if (list->last_element != NULL) {
  88                 plist_insert_after(list, list->last_element, value);
  89         }
  90         else {
  91                 plist_element_t *newElement = allocate_element(list);
  92
  93                 newElement->data    = value;
  94                 newElement->prev    = NULL;
  95                 newElement->next    = NULL;
  96                 list->first_element = list->last_element = newElement;
  97                 list->element_count = 1;
  98         }
  99 }
 100
 101 void plist_insert_front(plist_t *list, void *value)
 102 {
 103         if (list->first_element != NULL) {
 104                 plist_insert_before(list, list->first_element, value);
 105         }
 106         else {
 107                 plist_element_t *newElement = allocate_element(list);
 108
 109                 newElement->data    = value;
 110                 newElement->prev    = NULL;
 111                 newElement->next    = NULL;
 112                 list->first_element = list->last_element = newElement;
 113                 list->element_count = 1;
 114         }
 115 }
 116
 117 void plist_insert_before(plist_t *list, plist_element_t *element, void *value)
 118 {
 119         plist_element_t *prevElement;
 120         plist_element_t *newElement = allocate_element(list);
 121
 122         newElement->data = value;
 123         newElement->next = element;
 124         prevElement      = element->prev;
 125         newElement->prev = prevElement;
 126
 127         if (prevElement != NULL) {
 128                 prevElement->next = newElement;
 129         }
 130         else {
 131                 list->first_element = newElement;
 132         }
 133
 134         element->prev = newElement;
 135         ++list->element_count;
 136 }
 137
 138 void plist_insert_after(plist_t* list, plist_element_t* element, void* value)
 139 {
 140         plist_element_t *nextElement;
 141         plist_element_t *newElement = allocate_element(list);
 142
 143         newElement->data = value;
 144         newElement->prev = element;
 145         nextElement      = element->next;
 146         newElement->next = nextElement;
 147
 148         if (nextElement != NULL) {
 149                 nextElement->prev = newElement;
 150         }
 151         else {
 152                 list->last_element = newElement;
 153         }
 154
 155         element->next = newElement;
 156         ++list->element_count;
 157 }
 158
 159 int plist_has_value(plist_t *list, void *value)
 160 {
 161         plist_element_t *iter;
 162
 163         for (iter = plist_first(list); iter; iter = plist_element_get_next(iter)) {
 164                 if (plist_element_get_value(iter) == value)
 165                         return 1;
 166         }
 167
 168         return 0;
 169 }
 170
 171 plist_element_t *plist_find_value(plist_t *list, void *value)
 172 {
 173         plist_element_t *iter;
 174
 175         for (iter = plist_first(list); iter; iter = plist_element_get_next(iter)) {
 176                 if (plist_element_get_value(iter) == value)
 177                         return iter;
 178         }
 179
 180         return NULL;
 181 }
 182
 183 void plist_erase(plist_t *list, plist_element_t *element)
 184 {
 185         plist_element_t *next_element = element->next;
 186         plist_element_t *prev_element = element->prev;
 187
 188         if (next_element != NULL) {
 189                 next_element->prev = prev_element;
 190         }
 191         else {
 192                 list->last_element = prev_element;
 193         }
 194
 195         if (prev_element != NULL) {
 196                 prev_element->next = next_element;
 197         }
 198         else {
 199                 list->first_element = next_element;
 200         }
 201
 202         --list->element_count;
 203
 204         /* Clean the element and prepend it to the free list */
 205         element->prev            = NULL; /* The allocation code expects prev to be NULL */
 206         element->next            = list->first_free_element;
 207         list->first_free_element = element;
 208 }
 209
 210 void plist_clear(plist_t *list)
 211 {
 212         plist_element_t *curr_element = list->first_element;
 213
 214         while (curr_element != NULL) {
 215                 curr_element->prev = NULL;
 216                 curr_element       = curr_element->next;
 217         }
 218
 219         curr_element = list->last_element;
 220
 221         if (curr_element != NULL) {
 222                 curr_element->next = list->first_free_element;
 223         }
 224
 225         list->first_free_element = list->first_element;
 226         list->first_element      = 0;
 227         list->last_element       = 0;
 228         list->element_count      = 0;
 229 }