2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @author Matthias Braun
10 * @brief A nodeset. This should be prefered over a simple pset, because it
11 * tries to guarantee deterministic behavior. (and is faster)
12 * @note Actually the bits to make the behaviour deterministic are not
15 #ifndef _FIRM_IRNODESET_H_
16 #define _FIRM_IRNODESET_H_
19 #include "firm_types.h"
22 #define HashSet ir_nodeset_t
23 #define HashSetIterator ir_nodeset_iterator_t
24 #define ValueType ir_node*
31 #undef HashSetIterator
34 typedef struct ir_nodeset_t ir_nodeset_t;
35 typedef struct ir_nodeset_iterator_t ir_nodeset_iterator_t;
38 * Initializes a nodeset with default size.
40 * @param nodeset Pointer to allocated space for the nodeset
42 void ir_nodeset_init(ir_nodeset_t *nodeset);
45 * Initializes a nodeset
47 * @param nodeset Pointer to allocated space for the nodeset
48 * @param expected_elements Number of elements expected in the nodeset (roughly)
50 void ir_nodeset_init_size(ir_nodeset_t *nodeset, size_t expected_elements);
53 * Destroys a nodeset and frees the memory allocated for hashtable. The memory of
54 * the nodeset itself is not freed.
56 * @param nodeset Pointer to the nodeset
58 void ir_nodeset_destroy(ir_nodeset_t *nodeset);
61 * Allocates memory for a nodeset and initializes the set.
63 * @param expected_elements Number of elements expected in the nodeset (roughly)
64 * @return The initialized nodeset
66 static inline ir_nodeset_t *ir_nodeset_new(size_t expected_elements) {
67 ir_nodeset_t *res = XMALLOC(ir_nodeset_t);
68 ir_nodeset_init_size(res, expected_elements);
73 * Destroys a nodeset and frees the memory of the nodeset itself.
75 static inline void ir_nodeset_del(ir_nodeset_t *nodeset) {
76 ir_nodeset_destroy(nodeset);
81 * Inserts a node into a nodeset.
83 * @param nodeset Pointer to the nodeset
84 * @param node node to insert into the nodeset
85 * @returns true if the element has been inserted,
86 * false if it was already there
88 bool ir_nodeset_insert(ir_nodeset_t *nodeset, ir_node *node);
92 * Removes a node from a nodeset. Does nothing if the nodeset doesn't contain
95 * @param nodeset Pointer to the nodeset
96 * @param node Node to remove from the nodeset
98 void ir_nodeset_remove(ir_nodeset_t *nodeset, const ir_node *node);
101 * Tests whether a nodeset contains a specific node
103 * @param nodeset Pointer to the nodeset
104 * @param node The pointer to find
106 bool ir_nodeset_contains(const ir_nodeset_t *nodeset, const ir_node *node);
109 * Returns the number of pointers contained in the nodeset
111 * @param nodeset Pointer to the nodeset
112 * @returns Number of pointers contained in the nodeset
114 size_t ir_nodeset_size(const ir_nodeset_t *nodeset);
117 * Initializes a nodeset iterator. Sets the iterator before the first element in
120 * @param iterator Pointer to already allocated iterator memory
121 * @param nodeset Pointer to the nodeset
123 void ir_nodeset_iterator_init(ir_nodeset_iterator_t *iterator,
124 const ir_nodeset_t *nodeset);
127 * Advances the iterator and returns the current element or NULL if all elements
128 * in the nodeset have been processed.
129 * @attention It is not allowed to use nodeset_insert or nodeset_remove while
130 * iterating over a nodeset.
132 * @param iterator Pointer to the nodeset iterator.
133 * @returns Next element in the nodeset or NULL
135 ir_node *ir_nodeset_iterator_next(ir_nodeset_iterator_t *iterator);
138 * Removes the element the iterator currently points to
140 * @param nodeset Pointer to the nodeset
141 * @param iterator Pointer to the nodeset iterator.
143 void ir_nodeset_remove_iterator(ir_nodeset_t *nodeset,
144 const ir_nodeset_iterator_t *iterator);
146 static inline ir_node *ir_nodeset_first(ir_nodeset_t const *const nodeset)
148 ir_nodeset_iterator_t iter;
149 ir_nodeset_iterator_init(&iter, nodeset);
150 return ir_nodeset_iterator_next(&iter);
153 #define foreach_ir_nodeset(nodeset, irn, iter) \
154 for (bool irn##__once = true; irn##__once;) \
155 for (ir_nodeset_iterator_t iter; irn##__once;) \
156 for (ir_node *irn; irn##__once; irn##__once = false) \
157 for (ir_nodeset_iterator_init(&iter, nodeset); (irn = ir_nodeset_iterator_next(&iter));)