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 nodemap.
25 #ifndef _FIRM_IRLINKEDNODEMAP_H_
26 #define _FIRM_IRLINKEDNODEMAP_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_nodemap_USE_ORDERED_SETS
42 typedef struct ir_lnk_nodemap_entry_t {
43 ir_node *node; /**< the node itself */
44 void *data; /**< associated data */
45 list_head list; /**< link field for the list iterator */
46 } ir_lnk_nodemap_entry_t;
48 #define HashSet ir_lnk_nodemap_t
49 #define ValueType ir_lnk_nodemap_entry_t
50 #define ADDITIONAL_DATA list_head elem_list; list_head all_iters;
56 #undef ADDITIONAL_DATA
60 typedef struct ir_lnk_nodemap_t ir_lnk_nodemap_t;
61 typedef struct ir_lnk_nodemap_iterator_t {
62 list_head *iter; /**< points to the list head of the last element */
63 const ir_lnk_nodemap_t *nodemap; /**< lithe nodemap of this iterator. */
64 } ir_lnk_nodemap_iterator_t;
67 * Initializes a linked nodemap with default size.
69 * @param nodemap Pointer to allocated space for the nodemap
71 void ir_lnk_nodemap_init(ir_lnk_nodemap_t *nodemap);
74 * Initializes a linked nodemap.
76 * @param nodemap Pointer to allocated space for the nodemap
77 * @param expected_elements Number of elements expected in the nodemap (roughly)
79 void ir_lnk_nodemap_init_size(ir_lnk_nodemap_t *nodemap, size_t expected_elements);
82 * Destroys a nodemap and frees the memory allocated for hashtable. The memory of
83 * the nodemap itself is not freed.
85 * @param nodemap Pointer to the nodemap
87 void ir_lnk_nodemap_destroy(ir_lnk_nodemap_t *nodemap);
90 * Allocates memory for a linked nodemap and initializes the set.
92 * @param expected_elements Number of elements expected in the nodemap (roughly)
93 * @return The initialized nodemap
95 static inline ir_lnk_nodemap_t *ir_lnk_nodemap_new(size_t expected_elements) {
96 ir_lnk_nodemap_t *res = XMALLOC(ir_lnk_nodemap_t);
97 ir_lnk_nodemap_init_size(res, expected_elements);
102 * Destroys a linked nodemap and frees the memory of the nodemap itself.
104 static inline void ir_lnk_nodemap_del(ir_lnk_nodemap_t *nodemap) {
105 ir_lnk_nodemap_destroy(nodemap);
110 * Inserts a node into a linked nodemap.
112 * @param nodemap Pointer to the nodemap
113 * @param node node to insert into the nodemap
114 * @param data data to associate with the node
115 * @returns 1 if the element has been inserted,
116 * 0 if it was already there
118 int ir_lnk_nodemap_put(ir_lnk_nodemap_t *nodemap, ir_node *node, void *data);
121 * Get the associated value of a specific node
123 * @param nodemap Pointer to the nodemap
124 * @param node The pointer to find
125 * @returns the associated data of the node or NULL
127 void *ir_lnk_nodemap_get(const ir_lnk_nodemap_t *nodemap, const ir_node *node);
130 * Removes a node from a linked nodemap. Does nothing if the nodemap doesn't contain
133 * @param nodemap Pointer to the nodemap
134 * @param node Node to remove from the nodemap
136 void ir_lnk_nodemap_remove(ir_lnk_nodemap_t *nodemap, const ir_node *node);
139 * Returns the number of nodes contained in the linked nodemap.
141 * @param nodemap Pointer to the nodemap
142 * @returns Number of nodes contained in the linked nodemap
144 size_t ir_lnk_nodemap_size(const ir_lnk_nodemap_t *nodemap);
147 * Initializes a nodemap iterator. Sets the iterator before the first element in
148 * the linked nodemap.
150 * @param iterator Pointer to already allocated iterator memory
151 * @param nodemap Pointer to the nodemap
153 void ir_lnk_nodemap_iterator_init(ir_lnk_nodemap_iterator_t *iterator,
154 const ir_lnk_nodemap_t *nodemap);
157 * Advances the iterator and returns the current element or NULL if all elements
158 * in the linked nodemap have been processed.
159 * @attention It is not allowed to use ir_lnk_nodemap_insert or ir_lnk_nodemap_remove while
160 * iterating over a nodemap.
162 * @param iterator Pointer to the nodemap iterator.
163 * @returns Next element in the nodemap or NULL
165 ir_node *ir_lnk_nodemap_iterator_next(ir_lnk_nodemap_iterator_t *iterator);
168 * Removes the element the iterator currently points to.
170 * @param nodemap Pointer to the linked nodemap
171 * @param iterator Pointer to the linked nodemap iterator.
173 void ir_lnk_nodemap_remove_iterator(ir_lnk_nodemap_t *nodemap,
174 ir_lnk_nodemap_iterator_t *iterator);
176 #define foreach_ir_lnk_nodemap(nodemap, irn, iter) \
177 for (ir_lnk_nodemap_iterator_init(&iter, nodemap), \
178 irn = ir_lnk_nodemap_iterator_next(&iter); \
179 irn != NULL; irn = ir_lnk_nodemap_iterator_next(&iter))