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