From a45bb55ccc2bd1c781195b5ec2ee8ec73ab43c1b Mon Sep 17 00:00:00 2001 From: Michael Beck Date: Thu, 3 Jul 2008 16:09:59 +0000 Subject: [PATCH] linked versions of irnodeset and irnodemap [r20331] --- ir/ir/irlinkednodemap.c | 181 ++++++++++++++++++++++++++++++++++++++ ir/ir/irlinkednodemap.h | 188 ++++++++++++++++++++++++++++++++++++++++ ir/ir/irlinkednodeset.c | 179 ++++++++++++++++++++++++++++++++++++++ ir/ir/irlinkednodeset.h | 187 +++++++++++++++++++++++++++++++++++++++ 4 files changed, 735 insertions(+) create mode 100644 ir/ir/irlinkednodemap.c create mode 100644 ir/ir/irlinkednodemap.h create mode 100644 ir/ir/irlinkednodeset.c create mode 100644 ir/ir/irlinkednodeset.h diff --git a/ir/ir/irlinkednodemap.c b/ir/ir/irlinkednodemap.c new file mode 100644 index 000000000..d3ce4922c --- /dev/null +++ b/ir/ir/irlinkednodemap.c @@ -0,0 +1,181 @@ +/* + * 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. + */ + +/** + * @file + * @author Michael Beck + * @brief A linked nodemap. + * @version $Id$ + */ +#include "config.h" + +#include "irlinkednodemap.h" +#include "irnode_t.h" +#include "hashptr.h" + +static ir_lnk_nodemap_entry_t null_nodemap_entry; + +#define DO_REHASH +#define HashSet ir_lnk_nodemap_t +#define HashSetIterator ir_lnk_nodemap_iterator_t +#define ValueType ir_lnk_nodemap_entry_t +#define NullValue null_nodemap_entry +#define KeyType ir_node* +#define ConstKeyType const ir_node* +#define GetKey(value) (value).node +#define InitData(self,value,key) do { (value).node = (key); (value).list.next = NULL; (value).list.prev = NULL; } while(0) +#ifdef DEBUG_libfirm +#define Hash(self,key) ((unsigned)((key)->node_nr)) +#else +#define Hash(self,key) HASH_PTR(key) +#endif +#define KeysEqual(self,key1,key2) (key1) == (key2) +#define SetRangeEmpty(ptr,size) memset(ptr, 0, (size) * sizeof((ptr)[0])) +#define EntrySetEmpty(value) (value).node = NULL +#define EntrySetDeleted(value) do { (value).node = (ir_node*) -1; list_del(&(value).list); } while(0) +#define EntryIsEmpty(value) ((value).node == NULL) +#define EntryIsDeleted(value) ((value).node == (ir_node*)-1) + +#define hashset_init ir_lnk_nodemap_init +#define hashset_init_size ir_lnk_nodemap_init_size +#define hashset_destroy ir_lnk_nodemap_destroy +#define hashset_insert _ir_lnk_nodemap_insert +#define hashset_remove ir_lnk_nodemap_remove +#define hashset_find _ir_lnk_nodemap_find +#define hashset_size ir_lnk_nodemap_size + +#define ADDITIONAL_INIT INIT_LIST_HEAD(&self->elem_list); INIT_LIST_HEAD(&self->all_iters); +#define ADDITIONAL_TERM INIT_LIST_HEAD(&self->elem_list); INIT_LIST_HEAD(&self->all_iters); + +#define NO_ITERATOR +#define HAVE_OWN_RESIZE + +#include "hashset.c" + +/** + * Resize the hashset + * @internal + */ +static INLINE +void resize(HashSet *self, size_t new_size) +{ + size_t num_buckets = self->num_buckets; + HashSetEntry *old_entries = self->entries; + HashSetEntry *new_entries; + list_head list = self->elem_list; + HashSetEntry *entry; + int res = 1; + + /* allocate a new array with double size */ + new_entries = Alloc(new_size); + SetRangeEmpty(new_entries, new_size); + + /* use the new array */ + self->entries = new_entries; + self->num_buckets = new_size; + self->num_elements = 0; + self->num_deleted = 0; +#ifndef NDEBUG + self->entries_version++; +#endif + reset_thresholds(self); + + assert(!list_empty(&self->elem_list)); + list.next->prev = &list; + list.prev->next = &list; + + /* reinsert all elements */ + INIT_LIST_HEAD(&self->elem_list); + list_for_each_entry(ValueType, entry, &list, list) { + res &= ir_lnk_nodemap_put(self, EntryGetValue(*entry).node, EntryGetValue(*entry).data); + } + /* all re-inserted data must be new, if not, we found a node twice ... */ + assert(res == 1); + + /* now we can free the old array */ + Free(old_entries); +} + + +int ir_lnk_nodemap_put(ir_lnk_nodemap_t *nodemap, ir_node *node, void *data) +{ + ir_lnk_nodemap_entry_t *entry = _ir_lnk_nodemap_insert(nodemap, node); + + entry->data = data; + if (entry->list.next == NULL) { + /* we have added a new element */ + list_add_tail(&entry->list, &nodemap->elem_list); + return 1; + } + return 0; +} + +void *ir_lnk_nodemap_get(const ir_lnk_nodemap_t *nodemap, const ir_node *node) +{ + ir_lnk_nodemap_entry_t *entry = _ir_lnk_nodemap_find(nodemap, node); + return entry->data; +} + +/** + * Initializes a nodemap iterator. Sets the iterator before the first element in + * the linked nodemap. + * + * @param iterator Pointer to already allocated iterator memory + * @param nodemap Pointer to the nodemap + */ +void ir_lnk_nodemap_iterator_init(ir_lnk_nodemap_iterator_t *iterator, + const ir_lnk_nodemap_t *nodemap) { + iterator->iter = nodemap->elem_list.next; + iterator->nodemap = nodemap; +} + +/** + * Advances the iterator and returns the current element or NULL if all elements + * in the linked nodemap have been processed. + * @attention It is not allowed to use ir_lnk_nodemap_insert or ir_lnk_nodemap_remove while + * iterating over a nodemap. + * + * @param iterator Pointer to the nodemap iterator. + * @returns Next element in the nodemap or NULL + */ +ir_node *ir_lnk_nodemap_iterator_next(ir_lnk_nodemap_iterator_t *iterator) { + ir_node *res; + if (iterator->iter == &iterator->nodemap->elem_list) + return NULL; + + res = list_entry(iterator->iter, ir_lnk_nodemap_entry_t, list)->node; + iterator->iter = iterator->iter->next; + + return res; +} + +/** + * Removes the element the iterator currently points to. + * + * @param nodemap Pointer to the linked nodemap + * @param iterator Pointer to the nodemap iterator. + */ +void ir_lnk_nodemap_remove_iterator(ir_lnk_nodemap_t *nodemap, + ir_lnk_nodemap_iterator_t *iterator) { + ir_lnk_nodemap_entry_t *rem = list_entry(iterator->iter, ir_lnk_nodemap_entry_t, list); + + iterator->iter = rem->list.prev; + + ir_lnk_nodemap_remove(nodemap, rem->node); +} diff --git a/ir/ir/irlinkednodemap.h b/ir/ir/irlinkednodemap.h new file mode 100644 index 000000000..da18b51e4 --- /dev/null +++ b/ir/ir/irlinkednodemap.h @@ -0,0 +1,188 @@ +/* + * 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. + */ + +/** + * @file + * @author Michael Beck + * @brief A linked nodemap. + * @version $Id$ + */ +#ifndef _FIRM_IRLINKEDNODEMAP_H_ +#define _FIRM_IRLINKEDNODEMAP_H_ + +#include "firm_config.h" + +#include "firm_types.h" +#include "xmalloc.h" +#include "list.h" + +/* + * sebastian experimental: + * use ordered arrays as node sets. + * the guys here have made good experiences with that. + * Internally we use normal Firm arrays and binary + * search for locating the elements. Using arrays should + * give the sets a small footprint. + */ +#undef IR_nodemap_USE_ORDERED_SETS + +typedef struct ir_lnk_nodemap_entry_t { + ir_node *node; /**< the node itself */ + void *data; /**< associated data */ + list_head list; /**< link field for the list iterator */ +} ir_lnk_nodemap_entry_t; + +#define HashSet ir_lnk_nodemap_t +#define HashSetIterator ir_lnk_nodemap_iterator_t +#define ValueType ir_lnk_nodemap_entry_t +#define ADDITIONAL_DATA list_head elem_list; list_head all_iters; +#define DO_REHASH +#define NO_ITERATOR + +#include "hashset.h" + +#undef NO_ITERATOR +#undef DO_REHASH +#undef ADDITIONAL_DATA +#undef ValueType +#undef HashSetIterator +#undef HashSet + +typedef struct ir_lnk_nodemap_t ir_lnk_nodemap_t; +typedef struct ir_lnk_nodemap_iterator_t { + list_head *iter; /**< points to the list head of the last element */ + const ir_lnk_nodemap_t *nodemap; /**< lithe nodemap of this iterator. */ +} ir_lnk_nodemap_iterator_t; + +/** + * Initializes a linked nodemap with default size. + * + * @param nodemap Pointer to allocated space for the nodemap + */ +void ir_lnk_nodemap_init(ir_lnk_nodemap_t *nodemap); + +/** + * Initializes a linked nodemap. + * + * @param nodemap Pointer to allocated space for the nodemap + * @param expected_elements Number of elements expected in the nodemap (roughly) + */ +void ir_lnk_nodemap_init_size(ir_lnk_nodemap_t *nodemap, size_t expected_elements); + +/** + * Destroys a nodemap and frees the memory allocated for hashtable. The memory of + * the nodemap itself is not freed. + * + * @param nodemap Pointer to the nodemap + */ +void ir_lnk_nodemap_destroy(ir_lnk_nodemap_t *nodemap); + +/** + * Allocates memory for a linked nodemap and initializes the set. + * + * @param expected_elements Number of elements expected in the nodemap (roughly) + * @return The initialized nodemap + */ +static INLINE ir_lnk_nodemap_t *ir_lnk_nodemap_new(size_t expected_elements) { + ir_lnk_nodemap_t *res = xmalloc(sizeof(*res)); + ir_lnk_nodemap_init_size(res, expected_elements); + return res; +} + +/** + * Destroys a linked nodemap and frees the memory of the nodemap itself. + */ +static INLINE void ir_lnk_nodemap_del(ir_lnk_nodemap_t *nodemap) { + ir_lnk_nodemap_destroy(nodemap); + xfree(nodemap); +} + +/** + * Inserts a node into a linked nodemap. + * + * @param nodemap Pointer to the nodemap + * @param node node to insert into the nodemap + * @param data data to associate with the node + * @returns 1 if the element has been inserted, + * 0 if it was already there + */ +int ir_lnk_nodemap_put(ir_lnk_nodemap_t *nodemap, ir_node *node, void *data); + +/** + * Get the associated value of a specific node + * + * @param nodemap Pointer to the nodemap + * @param node The pointer to find + * @returns the associated data of the node or NULL + */ +void *ir_lnk_nodemap_get(const ir_lnk_nodemap_t *nodemap, const ir_node *node); + +/** + * Removes a node from a linked nodemap. Does nothing if the nodemap doesn't contain + * the node. + * + * @param nodemap Pointer to the nodemap + * @param node Node to remove from the nodemap + */ +void ir_lnk_nodemap_remove(ir_lnk_nodemap_t *nodemap, const ir_node *node); + +/** + * Returns the number of nodes contained in the linked nodemap. + * + * @param nodemap Pointer to the nodemap + * @returns Number of nodes contained in the linked nodemap + */ +size_t ir_lnk_nodemap_size(const ir_lnk_nodemap_t *nodemap); + +/** + * Initializes a nodemap iterator. Sets the iterator before the first element in + * the linked nodemap. + * + * @param iterator Pointer to already allocated iterator memory + * @param nodemap Pointer to the nodemap + */ +void ir_lnk_nodemap_iterator_init(ir_lnk_nodemap_iterator_t *iterator, + const ir_lnk_nodemap_t *nodemap); + +/** + * Advances the iterator and returns the current element or NULL if all elements + * in the linked nodemap have been processed. + * @attention It is not allowed to use ir_lnk_nodemap_insert or ir_lnk_nodemap_remove while + * iterating over a nodemap. + * + * @param iterator Pointer to the nodemap iterator. + * @returns Next element in the nodemap or NULL + */ +ir_node *ir_lnk_nodemap_iterator_next(ir_lnk_nodemap_iterator_t *iterator); + +/** + * Removes the element the iterator currently points to. + * + * @param nodemap Pointer to the linked nodemap + * @param iterator Pointer to the linked nodemap iterator. + */ +void ir_lnk_nodemap_remove_iterator(ir_lnk_nodemap_t *nodemap, + ir_lnk_nodemap_iterator_t *iterator); + +#define foreach_ir_lnk_nodemap(nodemap, irn, iter) \ + for (ir_lnk_nodemap_iterator_init(&iter, nodemap), \ + irn = ir_lnk_nodemap_iterator_next(&iter); \ + irn != NULL; irn = ir_lnk_nodemap_iterator_next(&iter)) + +#endif diff --git a/ir/ir/irlinkednodeset.c b/ir/ir/irlinkednodeset.c new file mode 100644 index 000000000..0a04dd4ea --- /dev/null +++ b/ir/ir/irlinkednodeset.c @@ -0,0 +1,179 @@ +/* + * 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. + */ + +/** + * @file + * @author Michael Beck + * @brief A linked nodeset. + * @version $Id$ + */ +#include "config.h" + +#include "irlinkednodeset.h" +#include "irnode_t.h" +#include "hashptr.h" + +static ir_lnk_nodeset_entry_t null_nodeset_entry; + +#define DO_REHASH +#define HashSet ir_lnk_nodeset_t +#define HashSetIterator ir_lnk_nodeset_iterator_t +#define ValueType ir_lnk_nodeset_entry_t +#define NullValue null_nodeset_entry +#define KeyType ir_node* +#define ConstKeyType const ir_node* +#define GetKey(value) (value).node +#define InitData(self,value,key) do { (value).node = (key); (value).list.next = NULL; (value).list.prev = NULL; } while(0) +#ifdef DEBUG_libfirm +#define Hash(self,key) ((unsigned)((key)->node_nr)) +#else +#define Hash(self,key) HASH_PTR(key) +#endif +#define KeysEqual(self,key1,key2) (key1) == (key2) +#define SetRangeEmpty(ptr,size) memset(ptr, 0, (size) * sizeof((ptr)[0])) +#define EntrySetEmpty(value) (value).node = NULL +#define EntrySetDeleted(value) do { (value).node = (ir_node*) -1; list_del(&(value).list); } while(0) +#define EntryIsEmpty(value) ((value).node == NULL) +#define EntryIsDeleted(value) ((value).node == (ir_node*)-1) + +#define hashset_init ir_lnk_nodeset_init +#define hashset_init_size ir_lnk_nodeset_init_size +#define hashset_destroy ir_lnk_nodeset_destroy +#define hashset_insert _ir_lnk_nodeset_insert +#define hashset_remove ir_lnk_nodeset_remove +#define hashset_find _ir_lnk_nodeset_find +#define hashset_size ir_lnk_nodeset_size + +#define ADDITIONAL_INIT INIT_LIST_HEAD(&self->elem_list); INIT_LIST_HEAD(&self->all_iters); +#define ADDITIONAL_TERM INIT_LIST_HEAD(&self->elem_list); INIT_LIST_HEAD(&self->all_iters); + +#define NO_ITERATOR +#define HAVE_OWN_RESIZE + +#include "hashset.c" + +/** + * Resize the hashset + * @internal + */ +static INLINE +void resize(HashSet *self, size_t new_size) +{ + size_t num_buckets = self->num_buckets; + HashSetEntry *old_entries = self->entries; + HashSetEntry *new_entries; + list_head list = self->elem_list; + HashSetEntry *entry; + int res = 1; + + /* allocate a new array with double size */ + new_entries = Alloc(new_size); + SetRangeEmpty(new_entries, new_size); + + /* use the new array */ + self->entries = new_entries; + self->num_buckets = new_size; + self->num_elements = 0; + self->num_deleted = 0; +#ifndef NDEBUG + self->entries_version++; +#endif + reset_thresholds(self); + + assert(!list_empty(&self->elem_list)); + list.next->prev = &list; + list.prev->next = &list; + + /* reinsert all elements */ + INIT_LIST_HEAD(&self->elem_list); + list_for_each_entry(ValueType, entry, &list, list) { + res &= ir_lnk_nodeset_insert(self, EntryGetValue(*entry).node); + } + /* all re-inserted data must be new, if not, we found a node twice ... */ + assert(res == 1); + + /* now we can free the old array */ + Free(old_entries); +} + + +/* Inserts a node into a linked nodeset. */ +int ir_lnk_nodeset_insert(ir_lnk_nodeset_t *nodeset, ir_node *node) { + ir_lnk_nodeset_entry_t *entry = _ir_lnk_nodeset_insert(nodeset, node); + + if (entry->list.next == NULL) { + /* we have added a new element */ + list_add_tail(&entry->list, &nodeset->elem_list); + return 1; + } + return 0; +} + +int ir_lnk_nodeset_contains(const ir_lnk_nodeset_t *nodeset, const ir_node *node) +{ + return _ir_lnk_nodeset_find(nodeset, node) != NULL; +} + +/** + * Initializes a nodeset iterator. Sets the iterator before the first element in + * the linked nodeset. + * + * @param iterator Pointer to already allocated iterator memory + * @param nodeset Pointer to the nodeset + */ +void ir_lnk_nodeset_iterator_init(ir_lnk_nodeset_iterator_t *iterator, + const ir_lnk_nodeset_t *nodeset) { + iterator->iter = nodeset->elem_list.next; + iterator->nodeset = nodeset; +} + +/** + * Advances the iterator and returns the current element or NULL if all elements + * in the linked nodeset have been processed. + * @attention It is not allowed to use ir_lnk_nodeset_insert or ir_lnk_nodeset_remove while + * iterating over a nodeset. + * + * @param iterator Pointer to the nodeset iterator. + * @returns Next element in the nodeset or NULL + */ +ir_node *ir_lnk_nodeset_iterator_next(ir_lnk_nodeset_iterator_t *iterator) { + ir_node *res; + if (iterator->iter == &iterator->nodeset->elem_list) + return NULL; + + res = list_entry(iterator->iter, ir_lnk_nodeset_entry_t, list)->node; + iterator->iter = iterator->iter->next; + + return res; +} + +/** + * Removes the element the iterator currently points to. + * + * @param nodeset Pointer to the linked nodeset + * @param iterator Pointer to the nodeset iterator. + */ +void ir_lnk_nodeset_remove_iterator(ir_lnk_nodeset_t *nodeset, + ir_lnk_nodeset_iterator_t *iterator) { + ir_lnk_nodeset_entry_t *rem = list_entry(iterator->iter, ir_lnk_nodeset_entry_t, list); + + iterator->iter = rem->list.prev; + + ir_lnk_nodeset_remove(nodeset, rem->node); +} diff --git a/ir/ir/irlinkednodeset.h b/ir/ir/irlinkednodeset.h new file mode 100644 index 000000000..624a174ea --- /dev/null +++ b/ir/ir/irlinkednodeset.h @@ -0,0 +1,187 @@ +/* + * 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. + */ + +/** + * @file + * @author Michael Beck + * @brief A linked nodeset. + * @version $Id$ + */ +#ifndef _FIRM_IRLINKEDNODESET_H_ +#define _FIRM_IRLINKEDNODESET_H_ + +#include "firm_config.h" + +#include "firm_types.h" +#include "xmalloc.h" +#include "list.h" + +/* + * sebastian experimental: + * use ordered arrays as node sets. + * the guys here have made good experiences with that. + * Internally we use normal Firm arrays and binary + * search for locating the elements. Using arrays should + * give the sets a small footprint. + */ +#undef IR_NODESET_USE_ORDERED_SETS + +typedef struct ir_lnk_nodeset_entry_t { + ir_node *node; /**< the node itself */ + list_head list; /**< link field for the list iterator */ +} ir_lnk_nodeset_entry_t; + +#define HashSet ir_lnk_nodeset_t +#define HashSetIterator ir_lnk_nodeset_iterator_t +#define ValueType ir_lnk_nodeset_entry_t +#define ADDITIONAL_DATA list_head elem_list; list_head all_iters; +#define DO_REHASH +#define NO_ITERATOR + +#include "hashset.h" + +#undef NO_ITERATOR +#undef DO_REHASH +#undef ADDITIONAL_DATA +#undef ValueType +#undef HashSetIterator +#undef HashSet + +typedef struct ir_lnk_nodeset_t ir_lnk_nodeset_t; +typedef struct ir_lnk_nodeset_iterator_t { + list_head *iter; /**< points to the list head of the last element */ + const ir_lnk_nodeset_t *nodeset; /**< lithe nodeset of this iterator. */ +} ir_lnk_nodeset_iterator_t; + +/** + * Initializes a linked nodeset with default size. + * + * @param nodeset Pointer to allocated space for the nodeset + */ +void ir_lnk_nodeset_init(ir_lnk_nodeset_t *nodeset); + +/** + * Initializes a linked nodeset. + * + * @param nodeset Pointer to allocated space for the nodeset + * @param expected_elements Number of elements expected in the nodeset (roughly) + */ +void ir_lnk_nodeset_init_size(ir_lnk_nodeset_t *nodeset, size_t expected_elements); + +/** + * Destroys a nodeset and frees the memory allocated for hashtable. The memory of + * the nodeset itself is not freed. + * + * @param nodeset Pointer to the nodeset + */ +void ir_lnk_nodeset_destroy(ir_lnk_nodeset_t *nodeset); + +/** + * Allocates memory for a linked nodeset and initializes the set. + * + * @param expected_elements Number of elements expected in the nodeset (roughly) + * @return The initialized nodeset + */ +static INLINE ir_lnk_nodeset_t *ir_lnk_nodeset_new(size_t expected_elements) { + ir_lnk_nodeset_t *res = xmalloc(sizeof(*res)); + ir_lnk_nodeset_init_size(res, expected_elements); + return res; +} + +/** + * Destroys a linked nodeset and frees the memory of the nodeset itself. + */ +static INLINE void ir_lnk_nodeset_del(ir_lnk_nodeset_t *nodeset) { + ir_lnk_nodeset_destroy(nodeset); + xfree(nodeset); +} + +/** + * Inserts a node into a linked nodeset. + * + * @param nodeset Pointer to the nodeset + * @param node node to insert into the nodeset + * @returns 1 if the element has been inserted, + * 0 if it was already there + */ +int ir_lnk_nodeset_insert(ir_lnk_nodeset_t *nodeset, ir_node *node); + + +/** + * Removes a node from a linked nodeset. Does nothing if the nodeset doesn't contain + * the node. + * + * @param nodeset Pointer to the nodeset + * @param node Node to remove from the nodeset + */ +void ir_lnk_nodeset_remove(ir_lnk_nodeset_t *nodeset, const ir_node *node); + +/** + * Tests whether a linked nodeset contains a specific node. + * + * @param nodeset Pointer to the nodeset + * @param node The pointer to find + * @returns 1 if nodeset contains the node, 0 else + */ +int ir_lnk_nodeset_contains(const ir_lnk_nodeset_t *nodeset, const ir_node *node); + +/** + * Returns the number of nodes contained in the linked nodeset. + * + * @param nodeset Pointer to the nodeset + * @returns Number of nodes contained in the linked nodeset + */ +size_t ir_lnk_nodeset_size(const ir_lnk_nodeset_t *nodeset); + +/** + * Initializes a nodeset iterator. Sets the iterator before the first element in + * the linked nodeset. + * + * @param iterator Pointer to already allocated iterator memory + * @param nodeset Pointer to the nodeset + */ +void ir_lnk_nodeset_iterator_init(ir_lnk_nodeset_iterator_t *iterator, + const ir_lnk_nodeset_t *nodeset); + +/** + * Advances the iterator and returns the current element or NULL if all elements + * in the linked nodeset have been processed. + * @attention It is not allowed to use ir_lnk_nodeset_insert or ir_lnk_nodeset_remove while + * iterating over a nodeset. + * + * @param iterator Pointer to the nodeset iterator. + * @returns Next element in the nodeset or NULL + */ +ir_node *ir_lnk_nodeset_iterator_next(ir_lnk_nodeset_iterator_t *iterator); + +/** + * Removes the element the iterator currently points to. + * + * @param nodeset Pointer to the linked nodeset + * @param iterator Pointer to the linked nodeset iterator. + */ +void ir_lnk_nodeset_remove_iterator(ir_lnk_nodeset_t *nodeset, + ir_lnk_nodeset_iterator_t *iterator); + +#define foreach_ir_lnk_nodeset(nodeset, irn, iter) \ + for (ir_lnk_nodeset_iterator_init(&iter, nodeset), \ + irn = ir_lnk_nodeset_iterator_next(&iter); \ + irn != NULL; irn = ir_lnk_nodeset_iterator_next(&iter)) + +#endif -- 2.20.1