From cedd573630a6ad0eca287cc3cb5ed10e4c1423be Mon Sep 17 00:00:00 2001 From: Kimon Hoffmann Date: Thu, 14 Jul 2005 15:05:16 +0000 Subject: [PATCH] Added plist data type. Has yet to be tested. [r6228] --- ir/adt/Makefile.in | 5 +- ir/adt/plist.c | 181 +++++++++++++++++++++++++++++++++++++++++++++ ir/adt/plist.h | 156 ++++++++++++++++++++++++++++++++++++++ 3 files changed, 340 insertions(+), 2 deletions(-) create mode 100644 ir/adt/plist.c create mode 100644 ir/adt/plist.h diff --git a/ir/adt/Makefile.in b/ir/adt/Makefile.in index bd311c178..51c715325 100644 --- a/ir/adt/Makefile.in +++ b/ir/adt/Makefile.in @@ -16,11 +16,12 @@ topdir = ../.. subdir := ir/adt disable_libiberty := @disable_libiberty@ -INSTALL_HEADERS_ADT = pset.h set.h pmap.h eset.h hashptr.h array.h pdeq.h iterator.h align.h fourcc.h util.h +INSTALL_HEADERS_ADT = pset.h set.h pmap.h eset.h hashptr.h array.h pdeq.h iterator.h align.h fourcc.h util.h plist.h SOURCES = Makefile.in \ array.c obst.h pdeq.c \ - set.c pmap.c eset.c iterator.c xmalloc.h + set.c pmap.c eset.c iterator.c xmalloc.h \ + plist.c ifeq ($(disable_libiberty),no) SOURCES += xmalloc.c diff --git a/ir/adt/plist.c b/ir/adt/plist.c new file mode 100644 index 000000000..b18b34235 --- /dev/null +++ b/ir/adt/plist.c @@ -0,0 +1,181 @@ +/** + * 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 17.07.2005 + * @note Until now the code is entirely untested so it probably contains + * plenty of errors. + */ +#include +#include "obst.h" + +#include "plist.h" + +/** + * Structure for one entry of the double linked pointer list. + */ +struct PListElement { + PListElement* next; + PListElement* prev; + void* data; +}; + +/** + * The list data type. + */ +struct PList { + /** + * The obastack used for all allocations. + */ + struct obstack obst; + /** + * First element in the list. + */ + PListElement* firstElement; + /** + * Last element in the list. + */ + PListElement* lastElement; + /** + * Current numner of elements in the list. + */ + int elementCount; + /** + * First element in the free list. + * Please note that the free list is a single linked list and all back + * references are invalid. + */ + PListElement* firstFreeElement; +}; + +/** + * Helper macro that returns a new uninitialized list element by either + * fetching one from the free-list or allocating a new one on the lists + * obstack. + * @param list the list for which to allocate the element. + * @return the newlyallocated, uninitialized element. + */ +static PListElement* allocate_element(PList* list) { + PListElement* newElement; + if (list->firstFreeElement != NULL) { + newElement = list->firstFreeElement; + list->firstFreeElement = newElement->next; + newElement->next = NULL; + } else { + newElement = obstack_alloc(&list->obst, sizeof(*newElement)); + } + return newElement; +} + +PList* plist_new(void) { + PList* list = xmalloc(sizeof(*list)); + obstack_init(&list->obst); + list->firstElement = NULL; + list->lastElement = NULL; + list->firstFreeElement = NULL; + list->elementCount = 0; + return list; +} + +void plist_free(PList* list) { + obstack_free(&list->obst, NULL); + list->firstElement = NULL; + list->lastElement = NULL; + list->firstFreeElement = NULL; + list->elementCount = 0; + xfree(list); +} + +void plist_insert_back(PList* list, void* value) { + if (list->lastElement != NULL) { + plist_insert_after(list, list->lastElement, value); + } else { + PListElement* newElement = allocate_element(list); + newElement->data = value; + newElement->prev = NULL; + newElement->next = NULL; + list->firstElement = list->lastElement = newElement; + list->elementCount = 1; + } +} + +void plist_insert_front(PList* list, void* value) { + if (list->firstElement != NULL) { + plist_insert_before(list, list->firstElement, value); + } else { + PListElement* newElement = allocate_element(list); + newElement->data = value; + newElement->prev = NULL; + newElement->next = NULL; + list->firstElement = list->lastElement = newElement; + list->elementCount = 1; + } +} + +void plist_insert_before(PList* list, PListElement* element, void* value) { + PListElement* newElement = allocate_element(list); + newElement->data = value; + newElement->next = element; + PListElement* prevElement = element->prev; + newElement->prev = prevElement; + if (prevElement != NULL) { + prevElement->next = newElement; + } else { + list->firstElement = newElement; + } + element->prev = newElement; + ++list->elementCount; +} + +void plist_insert_after(PList* list, PListElement* element, void* value) { + PListElement* newElement = allocate_element(list); + newElement->data = value; + newElement->prev = element; + PListElement* nextElement = element->next; + newElement->next = nextElement; + if (nextElement != NULL) { + nextElement->prev = newElement; + } else { + list->lastElement = newElement; + } + element->next = newElement; + ++list->elementCount; +} + +void plist_erase(PList* list, PListElement* element) { + PListElement* nextElement = element->next; + PListElement* prevElement = element->prev; + if (nextElement != NULL) { + nextElement->prev = prevElement; + } else { + list->lastElement = prevElement; + } + if (prevElement != NULL) { + prevElement->next = nextElement; + } else { + list->firstElement = nextElement; + } + --list->elementCount; + /* Clean the element and prepend it to the free list */ + element->prev = NULL; /* The allocation code exprects prev to be NULL */ + element->next = list->firstFreeElement; + list->firstFreeElement = element; +} + +void plist_clear(PList* list) { + PListElement* currentElement = list->firstElement; + while (currentElement != NULL) { + currentElement->prev = NULL; + currentElement = currentElement->next; + } + currentElement = list->lastElement; + if (currentElement != NULL) { + currentElement->next = list->firstFreeElement; + } + list->firstFreeElement = list->firstElement; + list->firstElement = list->lastElement = 0; + list->elementCount = 0; +} diff --git a/ir/adt/plist.h b/ir/adt/plist.h new file mode 100644 index 000000000..bba83d6f2 --- /dev/null +++ b/ir/adt/plist.h @@ -0,0 +1,156 @@ +/** + * 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 17.07.2005 + * @note Until now the code is entirely untested so it probably contains + * plenty of errors. + */ +#ifndef _PLIST_H_ +#define _PLIST_H_ + +#include + +/** + * The Plist data type. + */ +typedef struct PList PList; + +/** + * An element in the pointer list. + */ +typedef struct PListElement PListElement; + +/** + * Creates a new pointer list. + * @return The newly created pointer list. + */ +PList* plist_new(void); + +/** + * Frees the passed pointer list. + * After a call to this function all references to the list and any of + * its elements are invalid. + */ +void plist_free(PList* list); + +/** + * Returns the number of elements in a pointer list. + * @param list the pointer list + * @return The number of elements in a pointer list. + */ +#define plist_count(list) \ + ((list)->elementCount) + +/** + * Inserts an element at the back of a pointer list. + * @param list the pointer list to append the new element to. + * @param value the element value to append. + */ +void plist_insert_back(PList* list, void* value); + +/** + * Inserts an element at the front of a pointer list. + * @param list the pointer list to prepend the new element to. + * @param value the element value to prepend. + */ +void plist_insert_front(PList* list, void* value); + +/** + * Inserts an element into a pointer list before the specified element, + * which must be non null. + * @param list the pointer list to insert the new element into. + * @param element the list element before which the new element should + * be inserted. This element must be a part of @p list. + * @param value the element value to insert. + */ +void plist_insert_before(PList* list, PListElement* element, void* value); + +/** + * Inserts an element into a pointer list after the specified element, + * which must be non null. + * @param list the pointer list to insert the new element into. + * @param element the list element after which the new element should + * be inserted. This element must be a part of @p list. + * @param value the element value to insert. + */ +void plist_insert_after(PList* list, PListElement* element, void* value); + +/** + * Erases the specified element from the pointer list. + * @param list the pointer list from which the lement should be erased. + * @param element the list element to erase. This element must be a part + * of @p list. + */ +void plist_erase(PList* list, PListElement* element); + +/** + * Erases all elements from the specified pointer list. + * @param list the pointer list that should be cleard. + */ +void plist_clear(PList* list); + +/** + * Returns the first element of a pointer list. + * @param list the pointer list to iterate + * @return a pointer to the element or NULL if the list is empty + */ + #define plist_first(list) \ + ((list)->firstElement) + +/** + * Returns the last element of a pointer list. + * @param list the pointer list to iterate + * @return a pointer to the element or NULL if the list is empty + */ + #define plist_last(list) \ + ((list)->lastElement) + +/** + * Checks whether a pointer list element has a successor or not. + * @param element the list element that should be queried for existance + * of a successor. + * @return TRUE if @p element has a successor, otherwise FALSE. + */ +#define plist_element_has_next(element) \ + ((element)->next != NULL) + +/** + * Checks whether a pointer list element has a predecessor or not. + * @param element the list element that should be queried for existance + * of a predecessor. + * @return TRUE if @p element has a successor, otherwise FALSE. + */ +#define plist_element_has_prev(element) \ + ((element)->prev != NULL) + +/** + * Gets the successor of the passed list element. + * @param element the list element to return the successor of. + * @return The successor of @p element or NULL if @p element is the last + * element in the sequence. + */ +#define plist_element_get_next(element) \ + ((element)->next) + +/** + * Gets the predecessor of the passed list element. + * @param element the list element to return the predecessor of. + * @return The predecessor of @p element or NULL if @p element is the last + * element in the sequence. + */ +#define plist_element_get_prev(element) \ + ((element)->prev) + +/** + * Gets the value stored in the passed list element. + * @param element the list element to return the value of. + * @return The value stored in @p element. + */ +#define plist_element_get_value(element) \ + ((element)->data) + +#endif /*_PLIST_H_*/ -- 2.20.1