2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @author Michael Beck
23 * @brief A linked nodeset.
25 #ifndef _FIRM_IRLINKEDNODESET_H_
26 #define _FIRM_IRLINKEDNODESET_H_
28 #include "firm_types.h"
33 * sebastian experimental:
34 * use ordered arrays as node sets.
35 * the guys here have made good experiences with that.
36 * Internally we use normal Firm arrays and binary
37 * search for locating the elements. Using arrays should
38 * give the sets a small footprint.
40 #undef IR_NODESET_USE_ORDERED_SETS
42 typedef struct ir_lnk_nodeset_entry_t {
43 ir_node *node; /**< the node itself */
44 list_head list; /**< link field for the list iterator */
45 } ir_lnk_nodeset_entry_t;
47 #define HashSet ir_lnk_nodeset_t
48 #define HashSetIterator ir_lnk_nodeset_iterator_t
49 #define ValueType ir_lnk_nodeset_entry_t
50 #define ADDITIONAL_DATA list_head elem_list; list_head all_iters;
58 #undef ADDITIONAL_DATA
60 #undef HashSetIterator
63 typedef struct ir_lnk_nodeset_t ir_lnk_nodeset_t;
64 typedef struct ir_lnk_nodeset_iterator_t {
65 list_head *iter; /**< points to the list head of the last element */
66 const ir_lnk_nodeset_t *nodeset; /**< lithe nodeset of this iterator. */
67 } ir_lnk_nodeset_iterator_t;
70 * Initializes a linked nodeset with default size.
72 * @param nodeset Pointer to allocated space for the nodeset
74 void ir_lnk_nodeset_init(ir_lnk_nodeset_t *nodeset);
77 * Initializes a linked nodeset.
79 * @param nodeset Pointer to allocated space for the nodeset
80 * @param expected_elements Number of elements expected in the nodeset (roughly)
82 void ir_lnk_nodeset_init_size(ir_lnk_nodeset_t *nodeset, size_t expected_elements);
85 * Destroys a nodeset and frees the memory allocated for hashtable. The memory of
86 * the nodeset itself is not freed.
88 * @param nodeset Pointer to the nodeset
90 void ir_lnk_nodeset_destroy(ir_lnk_nodeset_t *nodeset);
93 * Allocates memory for a linked nodeset and initializes the set.
95 * @param expected_elements Number of elements expected in the nodeset (roughly)
96 * @return The initialized nodeset
98 static inline ir_lnk_nodeset_t *ir_lnk_nodeset_new(size_t expected_elements) {
99 ir_lnk_nodeset_t *res = XMALLOC(ir_lnk_nodeset_t);
100 ir_lnk_nodeset_init_size(res, expected_elements);
105 * Destroys a linked nodeset and frees the memory of the nodeset itself.
107 static inline void ir_lnk_nodeset_del(ir_lnk_nodeset_t *nodeset) {
108 ir_lnk_nodeset_destroy(nodeset);
113 * Inserts a node into a linked nodeset.
115 * @param nodeset Pointer to the nodeset
116 * @param node node to insert into the nodeset
117 * @returns 1 if the element has been inserted,
118 * 0 if it was already there
120 int ir_lnk_nodeset_insert(ir_lnk_nodeset_t *nodeset, ir_node *node);
124 * Removes a node from a linked nodeset. Does nothing if the nodeset doesn't contain
127 * @param nodeset Pointer to the nodeset
128 * @param node Node to remove from the nodeset
130 void ir_lnk_nodeset_remove(ir_lnk_nodeset_t *nodeset, const ir_node *node);
133 * Tests whether a linked nodeset contains a specific node.
135 * @param nodeset Pointer to the nodeset
136 * @param node The pointer to find
137 * @returns 1 if nodeset contains the node, 0 else
139 int ir_lnk_nodeset_contains(const ir_lnk_nodeset_t *nodeset, const ir_node *node);
142 * Returns the number of nodes contained in the linked nodeset.
144 * @param nodeset Pointer to the nodeset
145 * @returns Number of nodes contained in the linked nodeset
147 size_t ir_lnk_nodeset_size(const ir_lnk_nodeset_t *nodeset);
150 * Initializes a nodeset iterator. Sets the iterator before the first element in
151 * the linked nodeset.
153 * @param iterator Pointer to already allocated iterator memory
154 * @param nodeset Pointer to the nodeset
156 void ir_lnk_nodeset_iterator_init(ir_lnk_nodeset_iterator_t *iterator,
157 const ir_lnk_nodeset_t *nodeset);
160 * Advances the iterator and returns the current element or NULL if all elements
161 * in the linked nodeset have been processed.
162 * @attention It is not allowed to use ir_lnk_nodeset_insert or ir_lnk_nodeset_remove while
163 * iterating over a nodeset.
165 * @param iterator Pointer to the nodeset iterator.
166 * @returns Next element in the nodeset or NULL
168 ir_node *ir_lnk_nodeset_iterator_next(ir_lnk_nodeset_iterator_t *iterator);
171 * Removes the element the iterator currently points to.
173 * @param nodeset Pointer to the linked nodeset
174 * @param iterator Pointer to the linked nodeset iterator.
176 void ir_lnk_nodeset_remove_iterator(ir_lnk_nodeset_t *nodeset,
177 ir_lnk_nodeset_iterator_t *iterator);
179 #define foreach_ir_lnk_nodeset(nodeset, irn, iter) \
180 for (ir_lnk_nodeset_iterator_init(&iter, nodeset), \
181 irn = ir_lnk_nodeset_iterator_next(&iter); \
182 irn != NULL; irn = ir_lnk_nodeset_iterator_next(&iter))