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

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @author    Matthias Braun
   9  * @date      30.03.2007
  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
  13  *            implemented yet...
  14  */
  15 #ifndef _FIRM_IRNODESET_H_
  16 #define _FIRM_IRNODESET_H_
  17
  18 #include <stdbool.h>
  19 #include "firm_types.h"
  20 #include "xmalloc.h"
  21
  22 #define HashSet          ir_nodeset_t
  23 #define HashSetIterator  ir_nodeset_iterator_t
  24 #define ValueType        ir_node*
  25 #define DO_REHASH
  26
  27 #include "hashset.h"
  28
  29 #undef DO_REHASH
  30 #undef ValueType
  31 #undef HashSetIterator
  32 #undef HashSet
  33
  34 typedef struct ir_nodeset_t          ir_nodeset_t;
  35 typedef struct ir_nodeset_iterator_t ir_nodeset_iterator_t;
  36
  37 /**
  38  * Initializes a nodeset with default size.
  39  *
  40  * @param nodeset      Pointer to allocated space for the nodeset
  41  */
  42 void ir_nodeset_init(ir_nodeset_t *nodeset);
  43
  44 /**
  45  * Initializes a nodeset
  46  *
  47  * @param nodeset             Pointer to allocated space for the nodeset
  48  * @param expected_elements   Number of elements expected in the nodeset (roughly)
  49  */
  50 void ir_nodeset_init_size(ir_nodeset_t *nodeset, size_t expected_elements);
  51
  52 /**
  53  * Destroys a nodeset and frees the memory allocated for hashtable. The memory of
  54  * the nodeset itself is not freed.
  55  *
  56  * @param nodeset   Pointer to the nodeset
  57  */
  58 void ir_nodeset_destroy(ir_nodeset_t *nodeset);
  59
  60 /**
  61  * Allocates memory for a nodeset and initializes the set.
  62  *
  63  * @param expected_elements   Number of elements expected in the nodeset (roughly)
  64  * @return The initialized nodeset
  65  */
  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);
  69         return res;
  70 }
  71
  72 /**
  73  * Destroys a nodeset and frees the memory of the nodeset itself.
  74  */
  75 static inline void ir_nodeset_del(ir_nodeset_t *nodeset) {
  76         ir_nodeset_destroy(nodeset);
  77         xfree(nodeset);
  78 }
  79
  80 /**
  81  * Inserts a node into a nodeset.
  82  *
  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
  87  */
  88 bool ir_nodeset_insert(ir_nodeset_t *nodeset, ir_node *node);
  89
  90
  91 /**
  92  * Removes a node from a nodeset. Does nothing if the nodeset doesn't contain
  93  * the node.
  94  *
  95  * @param nodeset  Pointer to the nodeset
  96  * @param node     Node to remove from the nodeset
  97  */
  98 void ir_nodeset_remove(ir_nodeset_t *nodeset, const ir_node *node);
  99
 100 /**
 101  * Tests whether a nodeset contains a specific node
 102  *
 103  * @param nodeset   Pointer to the nodeset
 104  * @param node      The pointer to find
 105  */
 106 bool ir_nodeset_contains(const ir_nodeset_t *nodeset, const ir_node *node);
 107
 108 /**
 109  * Returns the number of pointers contained in the nodeset
 110  *
 111  * @param nodeset   Pointer to the nodeset
 112  * @returns       Number of pointers contained in the nodeset
 113  */
 114 size_t ir_nodeset_size(const ir_nodeset_t *nodeset);
 115
 116 /**
 117  * Initializes a nodeset iterator. Sets the iterator before the first element in
 118  * the nodeset.
 119  *
 120  * @param iterator   Pointer to already allocated iterator memory
 121  * @param nodeset       Pointer to the nodeset
 122  */
 123 void ir_nodeset_iterator_init(ir_nodeset_iterator_t *iterator,
 124                               const ir_nodeset_t *nodeset);
 125
 126 /**
 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.
 131  *
 132  * @param iterator  Pointer to the nodeset iterator.
 133  * @returns         Next element in the nodeset or NULL
 134  */
 135 ir_node *ir_nodeset_iterator_next(ir_nodeset_iterator_t *iterator);
 136
 137 /**
 138  * Removes the element the iterator currently points to
 139  *
 140  * @param nodeset   Pointer to the nodeset
 141  * @param iterator  Pointer to the nodeset iterator.
 142  */
 143 void ir_nodeset_remove_iterator(ir_nodeset_t *nodeset,
 144                                 const ir_nodeset_iterator_t *iterator);
 145
 146 static inline ir_node *ir_nodeset_first(ir_nodeset_t const *const nodeset)
 147 {
 148         ir_nodeset_iterator_t iter;
 149         ir_nodeset_iterator_init(&iter, nodeset);
 150         return ir_nodeset_iterator_next(&iter);
 151 }
 152
 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));)
 158
 159 #endif