X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fadt%2Fplist.c;h=fae710a9c1c69aa257dc1b62c11faea2f56189a8;hb=ce6161a7e42a48f7422b7babcc64d8ace18e2687;hp=4cbe15082f9effa73ace1be658c772f0a21d59f9;hpb=f75cc6830ea0864b6f91eaa61da4f654db33929f;p=libfirm diff --git a/ir/adt/plist.c b/ir/adt/plist.c index 4cbe15082..fae710a9c 100644 --- a/ir/adt/plist.c +++ b/ir/adt/plist.c @@ -1,14 +1,32 @@ +/* + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. + * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. + */ + /** - * Simple, non circular, double linked pointer list. - * Created because the properties of the standard circular list were not - * very well suited for the interference graph implementation. - * This list uses an obstack and a free-list to efficiently manage its - * elements. - * @author Kimon Hoffmann - * @date 14.07.2005 - * @cvs-id $Id$ - * @note Until now the code is entirely untested so it probably contains - * plenty of errors. + * @file + * @brief Simple, non circular, double linked pointer list. + * @note Created because the properties of the standard circular list were not + * very well suited for the interference graph implementation. + * This list uses an obstack and a free-list to efficiently manage its + * elements. + * @author Kimon Hoffmann + * @date 14.07.2005 + * @version $Id$ */ #include @@ -21,49 +39,71 @@ * @param list the list for which to allocate the element. * @return the newly allocated, uninitialized element. */ -static plist_element_t* allocate_element(plist_t* list) { - plist_element_t* newElement; +static plist_element_t *allocate_element(plist_t* list) +{ + plist_element_t *new_element; if (list->first_free_element != NULL) { - newElement = list->first_free_element; - list->first_free_element = newElement->next; - newElement->next = NULL; + new_element = list->first_free_element; + list->first_free_element = new_element->next; + new_element->next = NULL; } else { - newElement = obstack_alloc(&list->obst, sizeof(*newElement)); + new_element = OALLOC(list->obst, plist_element_t); } - return newElement; + return new_element; } -plist_t* plist_new(void) { - plist_t* list = xmalloc(sizeof(*list)); +plist_t *plist_new(void) +{ + plist_t *list = (plist_t*) xmalloc(sizeof(*list) + sizeof(*list->obst)); - obstack_init(&list->obst); + list->obst = (struct obstack *)&list[1]; + list->foreign_obstack = 0; list->first_element = NULL; list->last_element = NULL; list->first_free_element = NULL; list->element_count = 0; + obstack_init(list->obst); return list; } -void plist_free(plist_t* list) { - obstack_free(&list->obst, NULL); +plist_t *plist_obstack_new(struct obstack *obst) +{ + plist_t *list = OALLOC(obst, plist_t); + + list->obst = obst; + list->foreign_obstack = 1; + list->first_element = NULL; + list->last_element = NULL; + list->first_free_element = NULL; + list->element_count = 0; + + return list; +} +void plist_free(plist_t *list) +{ list->first_element = NULL; list->last_element = NULL; list->first_free_element = NULL; list->element_count = 0; - xfree(list); + + if (! list->foreign_obstack) { + obstack_free(list->obst, NULL); + xfree(list); + } } -void plist_insert_back(plist_t* list, void* value) { +void plist_insert_back(plist_t *list, void *value) +{ if (list->last_element != NULL) { plist_insert_after(list, list->last_element, value); } else { - plist_element_t* newElement = allocate_element(list); + plist_element_t *newElement = allocate_element(list); newElement->data = value; newElement->prev = NULL; @@ -73,12 +113,13 @@ void plist_insert_back(plist_t* list, void* value) { } } -void plist_insert_front(plist_t* list, void* value) { +void plist_insert_front(plist_t *list, void *value) +{ if (list->first_element != NULL) { plist_insert_before(list, list->first_element, value); } else { - plist_element_t* newElement = allocate_element(list); + plist_element_t *newElement = allocate_element(list); newElement->data = value; newElement->prev = NULL; @@ -88,9 +129,10 @@ void plist_insert_front(plist_t* list, void* value) { } } -void plist_insert_before(plist_t* list, plist_element_t* element, void* value) { - plist_element_t* prevElement; - plist_element_t* newElement = allocate_element(list); +void plist_insert_before(plist_t *list, plist_element_t *element, void *value) +{ + plist_element_t *prevElement; + plist_element_t *newElement = allocate_element(list); newElement->data = value; newElement->next = element; @@ -104,13 +146,14 @@ void plist_insert_before(plist_t* list, plist_element_t* element, void* value) { list->first_element = newElement; } - element->prev = newElement; + element->prev = newElement; ++list->element_count; } -void plist_insert_after(plist_t* list, plist_element_t* element, void* value) { - plist_element_t* nextElement; - plist_element_t* newElement = allocate_element(list); +void plist_insert_after(plist_t* list, plist_element_t* element, void* value) +{ + plist_element_t *nextElement; + plist_element_t *newElement = allocate_element(list); newElement->data = value; newElement->prev = element; @@ -128,22 +171,47 @@ void plist_insert_after(plist_t* list, plist_element_t* element, void* value) { ++list->element_count; } -void plist_erase(plist_t* list, plist_element_t* element) { - plist_element_t* nextElement = element->next; - plist_element_t* prevElement = element->prev; +int plist_has_value(plist_t *list, void *value) +{ + plist_element_t *iter; - if (nextElement != NULL) { - nextElement->prev = prevElement; + for (iter = plist_first(list); iter; iter = plist_element_get_next(iter)) { + if (plist_element_get_value(iter) == value) + return 1; + } + + return 0; +} + +plist_element_t *plist_find_value(plist_t *list, void *value) +{ + plist_element_t *iter; + + for (iter = plist_first(list); iter; iter = plist_element_get_next(iter)) { + if (plist_element_get_value(iter) == value) + return iter; + } + + return NULL; +} + +void plist_erase(plist_t *list, plist_element_t *element) +{ + plist_element_t *next_element = element->next; + plist_element_t *prev_element = element->prev; + + if (next_element != NULL) { + next_element->prev = prev_element; } else { - list->last_element = prevElement; + list->last_element = prev_element; } - if (prevElement != NULL) { - prevElement->next = nextElement; + if (prev_element != NULL) { + prev_element->next = next_element; } else { - list->first_element = nextElement; + list->first_element = next_element; } --list->element_count; @@ -154,18 +222,19 @@ void plist_erase(plist_t* list, plist_element_t* element) { list->first_free_element = element; } -void plist_clear(plist_t* list) { - plist_element_t* currentElement = list->first_element; +void plist_clear(plist_t *list) +{ + plist_element_t *curr_element = list->first_element; - while (currentElement != NULL) { - currentElement->prev = NULL; - currentElement = currentElement->next; + while (curr_element != NULL) { + curr_element->prev = NULL; + curr_element = curr_element->next; } - currentElement = list->last_element; + curr_element = list->last_element; - if (currentElement != NULL) { - currentElement->next = list->first_free_element; + if (curr_element != NULL) { + curr_element->next = list->first_free_element; } list->first_free_element = list->first_element;