nsz Git - libfirm/blob - ir/adt/bitset_std.h

   1
   2 /** Use ordinary ints as unit types. */
   3 typedef unsigned int bitset_unit_t;
   4
   5 #define BITSET_UNIT_FMT "%0x"
   6 #define BITSET_UNIT_ALL_ONE ((unsigned int) -1)
   7
   8 /**
   9  * Units needed for a given highest bit.
  10  * This implementation always allocates units in a multiple of 16 bytes.
  11  * @param size The size of the bitset in bits.
  12  * @return The number of units needed.
  13  */
  14 #define _bitset_units(size) (round_up2(size, BS_UNIT_SIZE_BITS) / BS_UNIT_SIZE_BITS)
  15
  16 /**
  17  * Compute the size in bytes needed for a bitseti, overall.
  18  * This also include the size for the bitset data structure.
  19  * This implementation computes the size in wat, that the bitset units
  20  * can be aligned to 16 bytes.
  21  * @param size The size of the bitset in bits.
  22  * @return The overall amount of bytes needed for that bitset.
  23  */
  24 #define _bitset_overall_size(bitset_base_size,size) \
  25         (bitset_base_size + _bitset_units(size) * BS_UNIT_SIZE)
  26
  27 /**
  28  * calculate the pointer to the data space of the bitset.
  29  * @param data The base address of the allocated memory
  30  * @param bitset_base_size The size of the basical bitset data structure
  31  * which has to be taken into account.
  32  * @param size The size of the bitset in bits.
  33  */
  34 #define _bitset_data_ptr(data,bitset_base_size,size) \
  35         ((bitset_unit_t *) ((char *) data + bitset_base_size))
  36
  37
  38 /**
  39  * Clear some units from a certain address on.
  40  * @param addr The address from where to clear.
  41  * @param n The number of units to set to 0.
  42  */
  43 #define _bitset_inside_clear_units(addr,n) \
  44         memset(addr, 0, n * BS_UNIT_SIZE)
  45
  46 /**
  47  * Set a bit in a unit.
  48  * @param unit A pointer to the unit.
  49  * @param bit which bit to set.
  50  */
  51 #define _bitset_inside_set(unit_ptr,bit) (*unit_ptr) |= (1 << (bit))
  52
  53 /**
  54  * Clear a bit in a unit.
  55  * @param unit A pointer to the unit.
  56  * @param bit which bit to set.
  57  */
  58 #define _bitset_inside_clear(unit_ptr,bit) (*unit_ptr) &= ~(1 << (bit))
  59
  60 /**
  61  * Flip a bit in a unit.
  62  * @param unit A pointer to the unit.
  63  * @param bit which bit to set.
  64  */
  65 #define _bitset_inside_flip(unit_ptr,bit) (*unit_ptr) ^= ~(1 << (bit))
  66
  67 /**
  68  * Flip a whole unit.
  69  * @param unit_ptr The pointer to the unit.
  70  */
  71 #define _bitset_inside_flip_unit(unit_ptr) (*unit_ptr) = ~(*unit_ptr)
  72
  73 /**
  74  * Count the number of leading zeroes in a unit.
  75  * @param unit A pointer to the unit.
  76  * @return The Number of leading zeroes.
  77  */
  78 #define _bitset_inside_nlz(unit_ptr) (nlz(*unit_ptr))
  79
  80
  81 /**
  82  * Count the number of trailing zeroes in a unit.
  83  * @param unit A pointer to the unit.
  84  * @return The Number of leading zeroes.
  85  */
  86 #define _bitset_inside_ntz(unit_ptr) _bitset_std_inside_ntz(unit_ptr)
  87 static INLINE bitset_pos_t _bitset_std_inside_ntz(bitset_unit_t *unit_ptr)
  88 {
  89         unsigned long data = *unit_ptr;
  90         return 32 - (bitset_pos_t) nlz(~data & (data - 1));
  91 }
  92
  93 /**
  94  * Count the number of trailing zeroes in a unit (whereas the unit is no
  95  * pointer but a value).
  96  * @param unit A unit.
  97  * @return The Number of leading zeroes.
  98  */
  99 #define _bitset_inside_ntz_value(unit) (32 - nlz(~(unit) & ((unit) - 1)))
 100
 101 /**
 102  * test if a bit is set in a unit.
 103  * @param unit_ptr The pointer to the unit.
 104  * @param bit The bit to check.
 105  * @return 1, if the bit is set, 0 otherise.
 106  */
 107 #define _bitset_inside_is_set(unit_ptr,bit) \
 108         (((*unit_ptr) & (1 << (bit))) != 0)
 109
 110 /**
 111  * count the number of bits set in a unit.
 112  * @param unit_ptr The pointer to a unit.
 113  * @return The number of bits set in the unit.
 114  */
 115 #define _bitset_inside_pop(unit_ptr) (popcnt(*unit_ptr))
 116
 117 #define _BITSET_BINOP_UNITS_INC 1
 118
 119 #define _bitset_inside_binop_and(tgt,src) ((*tgt) &= (*src))
 120 #define _bitset_inside_binop_andnot(tgt,src) ((*tgt) &= ~(*src))
 121 #define _bitset_inside_binop_or(tgt,src) ((*tgt) |= (*src))
 122 #define _bitset_inside_binop_xor(tgt,src) ((*tgt) ^= (*src))