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

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