nsz Git - libfirm/blob - ir/ir/irlinkednodemap.h

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   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.
  10  *
  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.
  14  *
  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
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @author    Michael Beck
  23  * @brief     A linked nodemap.
  24  * @version   $Id$
  25  */
  26 #ifndef _FIRM_IRLINKEDNODEMAP_H_
  27 #define _FIRM_IRLINKEDNODEMAP_H_
  28
  29 #include "firm_config.h"
  30
  31 #include "firm_types.h"
  32 #include "xmalloc.h"
  33 #include "list.h"
  34
  35 /*
  36  * sebastian experimental:
  37  * use ordered arrays as node sets.
  38  * the guys here have made good experiences with that.
  39  * Internally we use normal Firm arrays and binary
  40  * search for locating the elements. Using arrays should
  41  * give the sets a small footprint.
  42  */
  43 #undef IR_nodemap_USE_ORDERED_SETS
  44
  45 typedef struct ir_lnk_nodemap_entry_t {
  46         ir_node     *node;  /**< the node itself */
  47         void        *data;  /**< associated data */
  48         list_head   list;   /**< link field for the list iterator */
  49 } ir_lnk_nodemap_entry_t;
  50
  51 #define HashSet          ir_lnk_nodemap_t
  52 #define HashSetIterator  ir_lnk_nodemap_iterator_t
  53 #define ValueType        ir_lnk_nodemap_entry_t
  54 #define ADDITIONAL_DATA  list_head elem_list; list_head all_iters;
  55 #define DO_REHASH
  56 #define NO_ITERATOR
  57
  58 #include "hashset.h"
  59
  60 #undef NO_ITERATOR
  61 #undef DO_REHASH
  62 #undef ADDITIONAL_DATA
  63 #undef ValueType
  64 #undef HashSetIterator
  65 #undef HashSet
  66
  67 typedef struct ir_lnk_nodemap_t ir_lnk_nodemap_t;
  68 typedef struct ir_lnk_nodemap_iterator_t {
  69         list_head              *iter;       /**< points to the list head of the last element */
  70         const ir_lnk_nodemap_t *nodemap;    /**< lithe nodemap of this iterator. */
  71 } ir_lnk_nodemap_iterator_t;
  72
  73 /**
  74  * Initializes a linked nodemap with default size.
  75  *
  76  * @param nodemap      Pointer to allocated space for the nodemap
  77  */
  78 void ir_lnk_nodemap_init(ir_lnk_nodemap_t *nodemap);
  79
  80 /**
  81  * Initializes a linked nodemap.
  82  *
  83  * @param nodemap             Pointer to allocated space for the nodemap
  84  * @param expected_elements   Number of elements expected in the nodemap (roughly)
  85  */
  86 void ir_lnk_nodemap_init_size(ir_lnk_nodemap_t *nodemap, size_t expected_elements);
  87
  88 /**
  89  * Destroys a nodemap and frees the memory allocated for hashtable. The memory of
  90  * the nodemap itself is not freed.
  91  *
  92  * @param nodemap   Pointer to the nodemap
  93  */
  94 void ir_lnk_nodemap_destroy(ir_lnk_nodemap_t *nodemap);
  95
  96 /**
  97  * Allocates memory for a linked nodemap and initializes the set.
  98  *
  99  * @param expected_elements   Number of elements expected in the nodemap (roughly)
 100  * @return The initialized nodemap
 101  */
 102 static INLINE ir_lnk_nodemap_t *ir_lnk_nodemap_new(size_t expected_elements) {
 103         ir_lnk_nodemap_t *res = XMALLOC(ir_lnk_nodemap_t);
 104         ir_lnk_nodemap_init_size(res, expected_elements);
 105         return res;
 106 }
 107
 108 /**
 109  * Destroys a linked nodemap and frees the memory of the nodemap itself.
 110  */
 111 static INLINE void ir_lnk_nodemap_del(ir_lnk_nodemap_t *nodemap) {
 112         ir_lnk_nodemap_destroy(nodemap);
 113         xfree(nodemap);
 114 }
 115
 116 /**
 117  * Inserts a node into a linked nodemap.
 118  *
 119  * @param nodemap   Pointer to the nodemap
 120  * @param node      node to insert into the nodemap
 121  * @param data      data to associate with the node
 122  * @returns         1 if the element has been inserted,
 123  *                  0 if it was already there
 124  */
 125 int ir_lnk_nodemap_put(ir_lnk_nodemap_t *nodemap, ir_node *node, void *data);
 126
 127 /**
 128  * Get the associated value of a specific node
 129  *
 130  * @param nodemap   Pointer to the nodemap
 131  * @param node      The pointer to find
 132  * @returns         the associated data of the node or NULL
 133  */
 134 void *ir_lnk_nodemap_get(const ir_lnk_nodemap_t *nodemap, const ir_node *node);
 135
 136 /**
 137  * Removes a node from a linked nodemap. Does nothing if the nodemap doesn't contain
 138  * the node.
 139  *
 140  * @param nodemap  Pointer to the nodemap
 141  * @param node     Node to remove from the nodemap
 142  */
 143 void ir_lnk_nodemap_remove(ir_lnk_nodemap_t *nodemap, const ir_node *node);
 144
 145 /**
 146  * Returns the number of nodes contained in the linked nodemap.
 147  *
 148  * @param nodemap   Pointer to the nodemap
 149  * @returns         Number of nodes contained in the linked nodemap
 150  */
 151 size_t ir_lnk_nodemap_size(const ir_lnk_nodemap_t *nodemap);
 152
 153 /**
 154  * Initializes a nodemap iterator. Sets the iterator before the first element in
 155  * the linked nodemap.
 156  *
 157  * @param iterator   Pointer to already allocated iterator memory
 158  * @param nodemap       Pointer to the nodemap
 159  */
 160 void ir_lnk_nodemap_iterator_init(ir_lnk_nodemap_iterator_t *iterator,
 161                                   const ir_lnk_nodemap_t *nodemap);
 162
 163 /**
 164  * Advances the iterator and returns the current element or NULL if all elements
 165  * in the linked nodemap have been processed.
 166  * @attention It is not allowed to use ir_lnk_nodemap_insert or ir_lnk_nodemap_remove while
 167  *            iterating over a nodemap.
 168  *
 169  * @param iterator  Pointer to the nodemap iterator.
 170  * @returns         Next element in the nodemap or NULL
 171  */
 172 ir_node *ir_lnk_nodemap_iterator_next(ir_lnk_nodemap_iterator_t *iterator);
 173
 174 /**
 175  * Removes the element the iterator currently points to.
 176  *
 177  * @param nodemap   Pointer to the linked nodemap
 178  * @param iterator  Pointer to the linked nodemap iterator.
 179  */
 180 void ir_lnk_nodemap_remove_iterator(ir_lnk_nodemap_t *nodemap,
 181                                     ir_lnk_nodemap_iterator_t *iterator);
 182
 183 #define foreach_ir_lnk_nodemap(nodemap, irn, iter) \
 184         for (ir_lnk_nodemap_iterator_init(&iter, nodemap), \
 185         irn = ir_lnk_nodemap_iterator_next(&iter);    \
 186                 irn != NULL; irn = ir_lnk_nodemap_iterator_next(&iter))
 187
 188 #endif