nsz Git - libfirm/blob - ir/adt/bitset_std.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  * @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  * Clear some units from a certain address on.
  38  * @param addr The address from where to clear.
  39  * @param n The number of units to set to 0.
  40  */
  41 #define _bitset_inside_clear_units(addr,n) \
  42         memset(addr, 0, n * BS_UNIT_SIZE)
  43
  44 /**
  45  * Set a bit in a unit.
  46  * @param unit A pointer to the unit.
  47  * @param bit which bit to set.
  48  */
  49 #define _bitset_inside_set(unit_ptr,bit) (*unit_ptr) |= (1 << (bit))
  50
  51 /**
  52  * Clear a bit in a unit.
  53  * @param unit A pointer to the unit.
  54  * @param bit which bit to set.
  55  */
  56 #define _bitset_inside_clear(unit_ptr,bit) (*unit_ptr) &= ~(1 << (bit))
  57
  58 /**
  59  * Flip a bit in a unit.
  60  * @param unit A pointer to the unit.
  61  * @param bit which bit to set.
  62  */
  63 #define _bitset_inside_flip(unit_ptr,bit) (*unit_ptr) ^= (1 << (bit))
  64
  65 /**
  66  * Flip a whole unit.
  67  * @param unit_ptr The pointer to the unit.
  68  */
  69 #define _bitset_inside_flip_unit(unit_ptr) (*unit_ptr) = ~(*unit_ptr)
  70
  71 /**
  72  * Count the number of leading zeroes in a unit.
  73  * @param unit A pointer to the unit.
  74  * @return The Number of leading zeroes.
  75  */
  76 #define _bitset_inside_nlz(unit_ptr) (nlz(*unit_ptr))
  77
  78
  79 /**
  80  * Count the number of trailing zeroes in a unit.
  81  * @param unit A pointer to the unit.
  82  * @return The Number of leading zeroes.
  83  */
  84 #define _bitset_inside_ntz(unit_ptr) _bitset_std_inside_ntz(unit_ptr)
  85 static inline unsigned _bitset_std_inside_ntz(bitset_unit_t *unit_ptr)
  86 {
  87         unsigned long data = *unit_ptr;
  88         return 32 - (unsigned) nlz(~data & (data - 1));
  89 }
  90
  91 /**
  92  * Count the number of trailing zeroes in a unit (whereas the unit is no
  93  * pointer but a value).
  94  * @param unit A unit.
  95  * @return The Number of leading zeroes.
  96  */
  97 #define _bitset_inside_ntz_value(unit) (32 - nlz(~(unit) & ((unit) - 1)))
  98
  99 /**
 100  * test if a bit is set in a unit.
 101  * @param unit_ptr The pointer to the unit.
 102  * @param bit The bit to check.
 103  * @return 1, if the bit is set, 0 otherise.
 104  */
 105 #define _bitset_inside_is_set(unit_ptr,bit) \
 106         (((*unit_ptr) & (1 << (bit))) != 0)
 107
 108 /**
 109  * count the number of bits set in a unit.
 110  * @param unit_ptr The pointer to a unit.
 111  * @return The number of bits set in the unit.
 112  */
 113 #define _bitset_inside_pop(unit_ptr) (popcnt(*unit_ptr))
 114
 115 #define _BITSET_BINOP_UNITS_INC 1
 116
 117 #define _bitset_inside_binop_and(tgt,src) ((*tgt) &= (*src))
 118 #define _bitset_inside_binop_andnot(tgt,src) ((*tgt) &= ~(*src))
 119 #define _bitset_inside_binop_or(tgt,src) ((*tgt) |= (*src))
 120 #define _bitset_inside_binop_xor(tgt,src) ((*tgt) ^= (*src))
 121
 122 #endif