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

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