X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fadt%2Fbitset.h;h=5eb3490d164e434fbd4b064827185cf69f8f8954;hb=c496fb7a06926c15967ea635fd95a9c78e74d6bc;hp=ad920a840d74df018996856faaa524ba3ce5eb05;hpb=07d33d22fcc65609a2c31c516604bda6e615bf72;p=libfirm diff --git a/ir/adt/bitset.h b/ir/adt/bitset.h index ad920a840..5eb3490d1 100644 --- a/ir/adt/bitset.h +++ b/ir/adt/bitset.h @@ -1,40 +1,60 @@ -/** - * @file bitset.h - * @date 15.10.2004 - * @author Sebastian Hack - * @brief A bitset implementation. +/* + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. + * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. */ -#ifndef __FIRM_BITSET_H -#define __FIRM_BITSET_H +/** + * @file + * @brief A bitset implementation. + * @author Sebastian Hack + * @date 15.10.2004 + * @version $Id$ + */ +#ifndef FIRM_ADT_BITSET_H +#define FIRM_ADT_BITSET_H #include #include #include #include -#include "firm_config.h" +#include "xmalloc.h" #include "bitfiddle.h" typedef unsigned int bitset_pos_t; #include "bitset_std.h" -/* #if defined(__GNUC__) && defined(__i386__) #include "bitset_ia32.h" #endif -*/ typedef struct _bitset_t { bitset_pos_t units; - bitset_pos_t size; - bitset_unit_t *data; + bitset_pos_t size; } bitset_t; -#define BS_UNIT_SIZE sizeof(bitset_unit_t) -#define BS_UNIT_SIZE_BITS (BS_UNIT_SIZE * 8) -#define BS_UNIT_MASK (BS_UNIT_SIZE_BITS - 1) +#define BS_UNIT_SIZE sizeof(bitset_unit_t) +#define BS_UNIT_SIZE_BITS (BS_UNIT_SIZE * 8) +#define BS_UNIT_MASK (BS_UNIT_SIZE_BITS - 1) + +#define BS_DATA(bs) ((bitset_unit_t *) ((char *) (bs) + sizeof(bitset_t))) +#define BS_UNITS(bits) (round_up2(bits, BS_UNIT_SIZE_BITS) / BS_UNIT_SIZE_BITS) +#define BS_TOTAL_SIZE(bits) (sizeof(bitset_t) + BS_UNITS(bits) * BS_UNIT_SIZE) /** * Initialize a bitset. @@ -55,13 +75,12 @@ typedef struct _bitset_t { * @param size The size of the bitset in bits. * @return A pointer to the initialized bitset. */ -static INLINE bitset_t *_bitset_prepare(void *area, bitset_pos_t size) +static inline bitset_t *_bitset_prepare(void *area, bitset_pos_t size) { bitset_t *ptr = area; - memset(area, 0, _bitset_overall_size(sizeof(bitset_t), size)); - ptr->units = _bitset_units(size); - ptr->size = size; - ptr->data = _bitset_data_ptr(area, sizeof(bitset_t), size); + memset(ptr, 0, BS_TOTAL_SIZE(size)); + ptr->units = BS_UNITS(size); + ptr->size = size; return ptr; } @@ -71,11 +90,11 @@ static INLINE bitset_t *_bitset_prepare(void *area, bitset_pos_t size) * @param bs The bitset. * @return The masked bitset. */ -static INLINE bitset_t *_bitset_mask_highest(bitset_t *bs) +static inline bitset_t *_bitset_mask_highest(bitset_t *bs) { bitset_pos_t rest = bs->size & BS_UNIT_MASK; if (rest) - bs->data[bs->units - 1] &= (1 << rest) - 1; + BS_DATA(bs)[bs->units - 1] &= (1 << rest) - 1; return bs; } @@ -101,7 +120,7 @@ static INLINE bitset_t *_bitset_mask_highest(bitset_t *bs) * @return A pointer to an empty initialized bitset. */ #define bitset_obstack_alloc(obst,size) \ - _bitset_prepare(obstack_alloc(obst, _bitset_overall_size(sizeof(bitset_t), size)), size) + _bitset_prepare(obstack_alloc(obst, BS_TOTAL_SIZE(size)), size) /** * Allocate a bitset via malloc. @@ -109,7 +128,7 @@ static INLINE bitset_t *_bitset_mask_highest(bitset_t *bs) * @return A pointer to an empty initialized bitset. */ #define bitset_malloc(size) \ - _bitset_prepare(xmalloc(_bitset_overall_size(sizeof(bitset_t), size)), size) + _bitset_prepare(xmalloc(BS_TOTAL_SIZE(size)), size) /** * Free a bitset allocated with bitset_malloc(). @@ -123,7 +142,7 @@ static INLINE bitset_t *_bitset_mask_highest(bitset_t *bs) * @return A pointer to an empty initialized bitset. */ #define bitset_alloca(size) \ - _bitset_prepare(alloca(_bitset_overall_size(sizeof(bitset_t), size)), size) + _bitset_prepare(alloca(BS_TOTAL_SIZE(size)), size) /** @@ -133,11 +152,10 @@ static INLINE bitset_t *_bitset_mask_highest(bitset_t *bs) * @param bit The bit. * @return A pointer to the unit containing the bit. */ -static INLINE bitset_unit_t *_bitset_get_unit(const bitset_t *bs, bitset_pos_t bit) +static inline bitset_unit_t *_bitset_get_unit(const bitset_t *bs, bitset_pos_t bit) { - /* assert(bit < bs->units * BS_UNIT_SIZE_BITS && "Bit too large"); */ - assert(bit <= bs->size && "Bit to large"); - return bs->data + bit / BS_UNIT_SIZE_BITS; + assert(bit <= bs->size && "Bit to large"); + return BS_DATA(bs) + bit / BS_UNIT_SIZE_BITS; } /** @@ -145,7 +163,7 @@ static INLINE bitset_unit_t *_bitset_get_unit(const bitset_t *bs, bitset_pos_t b * @param bs The bitset. * @param bit The bit to set. */ -static INLINE void bitset_set(bitset_t *bs, bitset_pos_t bit) +static inline void bitset_set(bitset_t *bs, bitset_pos_t bit) { bitset_unit_t *unit = _bitset_get_unit(bs, bit); _bitset_inside_set(unit, bit & BS_UNIT_MASK); @@ -156,7 +174,7 @@ static INLINE void bitset_set(bitset_t *bs, bitset_pos_t bit) * @param bs The bitset. * @param bit The bit to clear. */ -static INLINE void bitset_clear(bitset_t *bs, bitset_pos_t bit) +static inline void bitset_clear(bitset_t *bs, bitset_pos_t bit) { bitset_unit_t *unit = _bitset_get_unit(bs, bit); _bitset_inside_clear(unit, bit & BS_UNIT_MASK); @@ -168,7 +186,7 @@ static INLINE void bitset_clear(bitset_t *bs, bitset_pos_t bit) * @param bit The bit to check for. * @return 1, if the bit was set, 0 if not. */ -static INLINE int bitset_is_set(const bitset_t *bs, bitset_pos_t bit) +static inline int bitset_is_set(const bitset_t *bs, bitset_pos_t bit) { bitset_unit_t *unit = _bitset_get_unit(bs, bit); return _bitset_inside_is_set(unit, bit & BS_UNIT_MASK); @@ -179,7 +197,7 @@ static INLINE int bitset_is_set(const bitset_t *bs, bitset_pos_t bit) * @param bs The bitset. * @param bit The bit to flip. */ -static INLINE void bitset_flip(bitset_t *bs, bitset_pos_t bit) +static inline void bitset_flip(bitset_t *bs, bitset_pos_t bit) { bitset_unit_t *unit = _bitset_get_unit(bs, bit); _bitset_inside_flip(unit, bit & BS_UNIT_MASK); @@ -189,11 +207,11 @@ static INLINE void bitset_flip(bitset_t *bs, bitset_pos_t bit) * Flip the whole bitset. * @param bs The bitset. */ -static INLINE void bitset_flip_all(bitset_t *bs) +static inline void bitset_flip_all(bitset_t *bs) { bitset_pos_t i; for(i = 0; i < bs->units; i++) - _bitset_inside_flip_unit(&bs->data[i]); + _bitset_inside_flip_unit(&BS_DATA(bs)[i]); _bitset_mask_highest(bs); } @@ -203,57 +221,17 @@ static INLINE void bitset_flip_all(bitset_t *bs) * @param src The source bitset. * @return The target bitset. */ -static INLINE bitset_t *bitset_copy(bitset_t *tgt, const bitset_t *src) +static inline bitset_t *bitset_copy(bitset_t *tgt, const bitset_t *src) { bitset_pos_t tu = tgt->units; bitset_pos_t su = src->units; bitset_pos_t min_units = tu < su ? tu : su; - memcpy(tgt->data, src->data, min_units * BS_UNIT_SIZE); + memcpy(BS_DATA(tgt), BS_DATA(src), min_units * BS_UNIT_SIZE); if(tu > min_units) - memset(tgt->data + min_units, 0, BS_UNIT_SIZE * (tu - min_units)); + memset(BS_DATA(tgt) + min_units, 0, BS_UNIT_SIZE * (tu - min_units)); return _bitset_mask_highest(tgt); } -/** - * Find the smallest bit set in the bitset. - * @param bs The bitset. - * @return The smallest bit set in the bitset. - */ -static INLINE bitset_pos_t bitset_min(const bitset_t *bs) -{ - bitset_pos_t i, ofs = 0; - - for(i = 0; i < bs->units; ++i) { - bitset_unit_t *unit = &bs->data[i]; - bitset_pos_t pos = _bitset_inside_ntz(unit); - if(pos > 0) - return ofs + pos; - ofs += BS_UNIT_SIZE_BITS; - } - - return 0; -} - -/** - * Find the greatest bit set in the bitset. - * @param bs The bitset. - * @return The greatest bit set in the bitset. - */ -static INLINE bitset_pos_t bitset_max(const bitset_t *bs) -{ - bitset_pos_t i, max = 0, ofs = 0; - - for(i = 0; i < bs->units; ++i) { - bitset_unit_t *unit = &bs->data[i]; - bitset_pos_t pos = _bitset_inside_nlz(unit); - if(pos > 0) - max = ofs + pos; - ofs += BS_UNIT_SIZE_BITS; - } - - return max; -} - /** * Find the next set bit from a given bit. * @note Note that if pos is set, pos is returned. @@ -262,12 +240,13 @@ static INLINE bitset_pos_t bitset_max(const bitset_t *bs) * @return The next set bit from pos on, or -1, if no set bit was found * after pos. */ -static INLINE bitset_pos_t _bitset_next(const bitset_t *bs, +static inline bitset_pos_t _bitset_next(const bitset_t *bs, bitset_pos_t pos, int set) { bitset_pos_t unit_number = pos / BS_UNIT_SIZE_BITS; + bitset_pos_t res; - if(unit_number >= bs->units) + if(pos >= bs->size) return -1; { @@ -278,7 +257,7 @@ static INLINE bitset_pos_t _bitset_next(const bitset_t *bs, * Mask out the bits smaller than pos in the current unit. * We are only interested in bits set higher than pos. */ - bitset_unit_t curr_unit = bs->data[unit_number]; + bitset_unit_t curr_unit = BS_DATA(bs)[unit_number]; /* * Find the next bit set in the unit. @@ -289,19 +268,23 @@ static INLINE bitset_pos_t _bitset_next(const bitset_t *bs, _bitset_inside_ntz_value((set ? curr_unit : ~curr_unit) & ~in_unit_mask); /* If there is a bit set in the current unit, exit. */ - if(next_in_this_unit < BS_UNIT_SIZE_BITS) - return next_in_this_unit + unit_number * BS_UNIT_SIZE_BITS; + if (next_in_this_unit < BS_UNIT_SIZE_BITS) { + res = next_in_this_unit + unit_number * BS_UNIT_SIZE_BITS; + return res < bs->size ? res : (bitset_pos_t) -1; + } /* Else search for set bits in the next units. */ else { bitset_pos_t i; for(i = unit_number + 1; i < bs->units; ++i) { - bitset_unit_t data = bs->data[i]; + bitset_unit_t data = BS_DATA(bs)[i]; bitset_pos_t first_set = _bitset_inside_ntz_value(set ? data : ~data); - if(first_set < BS_UNIT_SIZE_BITS) - return first_set + i * BS_UNIT_SIZE_BITS; + if (first_set < BS_UNIT_SIZE_BITS) { + res = first_set + i * BS_UNIT_SIZE_BITS; + return res < bs->size ? res : (bitset_pos_t) -1; + } } } } @@ -318,11 +301,11 @@ static INLINE bitset_pos_t _bitset_next(const bitset_t *bs, * @param elm A unsigned long variable. */ #define bitset_foreach(bitset,elm) \ - for(elm = bitset_next_set(bitset,0); elm != -1; elm = bitset_next_set(bitset,elm+1)) + for(elm = bitset_next_set(bitset,0); elm != (bitset_pos_t) -1; elm = bitset_next_set(bitset,elm+1)) #define bitset_foreach_clear(bitset,elm) \ - for(elm = bitset_next_clear(bitset,0); elm != -1; elm = bitset_next_clear(bitset,elm+1)) + for(elm = bitset_next_clear(bitset,0); elm != (bitset_pos_t) -1; elm = bitset_next_clear(bitset,elm+1)) /** * Count the bits set. @@ -330,12 +313,13 @@ static INLINE bitset_pos_t _bitset_next(const bitset_t *bs, * @param bs The bitset. * @return The number of bits set in the bitset. */ -static INLINE bitset_pos_t bitset_popcnt(const bitset_t *bs) +static inline unsigned bitset_popcnt(const bitset_t *bs) { - bitset_pos_t i, pop = 0; + bitset_pos_t i; bitset_unit_t *unit; + unsigned pop = 0; - for(i = 0, unit = bs->data; i < bs->units; ++i, ++unit) + for (i = 0, unit = BS_DATA(bs); i < bs->units; ++i, ++unit) pop += _bitset_inside_pop(unit); return pop; @@ -346,10 +330,10 @@ static INLINE bitset_pos_t bitset_popcnt(const bitset_t *bs) * This sets all bits to zero. * @param bs The bitset. */ -static INLINE bitset_t *bitset_clear_all(bitset_t *bs) +static inline bitset_t *bitset_clear_all(bitset_t *bs) { - memset(bs->data, 0, BS_UNIT_SIZE * bs->units); - return bs; + memset(BS_DATA(bs), 0, BS_UNIT_SIZE * bs->units); + return bs; } /** @@ -357,10 +341,10 @@ static INLINE bitset_t *bitset_clear_all(bitset_t *bs) * This sets all bits to one. * @param bs The bitset. */ -static INLINE bitset_t *bitset_set_all(bitset_t *bs) +static inline bitset_t *bitset_set_all(bitset_t *bs) { - memset(bs->data, -1, bs->units * BS_UNIT_SIZE); - return _bitset_mask_highest(bs); + memset(BS_DATA(bs), -1, bs->units * BS_UNIT_SIZE); + return _bitset_mask_highest(bs); } /** @@ -370,14 +354,14 @@ static INLINE bitset_t *bitset_set_all(bitset_t *bs) * @param rhs Another bitset. * @return 1, if all bits in lhs are also set in rhs, 0 otherwise. */ -static INLINE int bitset_contains(const bitset_t *lhs, const bitset_t *rhs) +static inline int bitset_contains(const bitset_t *lhs, const bitset_t *rhs) { bitset_pos_t n = lhs->units < rhs->units ? lhs->units : rhs->units; bitset_pos_t i; for(i = 0; i < n; ++i) { - bitset_unit_t lu = lhs->data[i]; - bitset_unit_t ru = rhs->data[i]; + bitset_unit_t lu = BS_DATA(lhs)[i]; + bitset_unit_t ru = BS_DATA(rhs)[i]; if((lu | ru) & ~ru) return 0; @@ -389,7 +373,7 @@ static INLINE int bitset_contains(const bitset_t *lhs, const bitset_t *rhs) */ if(lhs->units > n) { for(i = n; i < lhs->units; ++i) { - if(lhs->data[i] != 0) + if(BS_DATA(lhs)[i] != 0) return 0; } } @@ -402,65 +386,197 @@ static INLINE int bitset_contains(const bitset_t *lhs, const bitset_t *rhs) * @param bs The bitset. * @return The same bitset. */ -static INLINE void bitset_minus1(bitset_t *bs) +static inline void bitset_minus1(bitset_t *bs) { #define _SH (sizeof(bitset_unit_t) * 8 - 1) - bitset_pos_t i; + bitset_pos_t i; - for(i = 0; i < bs->units; ++i) { - bitset_unit_t unit = bs->data[i]; - bitset_unit_t um1 = unit - 1; + for(i = 0; i < bs->units; ++i) { + bitset_unit_t unit = BS_DATA(bs)[i]; + bitset_unit_t um1 = unit - 1; - bs->data[i] = um1; + BS_DATA(bs)[i] = um1; - if(((unit >> _SH) ^ (um1 >> _SH)) == 0) - break; - } + if(((unit >> _SH) ^ (um1 >> _SH)) == 0) + break; + } #undef _SH } +/** + * Check if two bitsets intersect. + * @param a The first bitset. + * @param b The second bitset. + * @return 1 if they have a bit in common, 0 if not. + */ +static inline int bitset_intersect(const bitset_t *a, const bitset_t *b) +{ + bitset_pos_t n = a->units < b->units ? a->units : b->units; + bitset_pos_t i; + + for (i = 0; i < n; ++i) + if (BS_DATA(a)[i] & BS_DATA(b)[i]) + return 1; + + return 0; +} + +/** + * set or clear all bits in the range [from;to[. + * @param a The bitset. + * @param from The first index to set to one. + * @param to The last index plus one to set to one. + * @param do_set If 1 the bits are set, if 0, they are cleared. + */ +static inline void bitset_mod_range(bitset_t *a, bitset_pos_t from, bitset_pos_t to, int do_set) +{ + bitset_pos_t from_unit, to_unit, i; + bitset_unit_t from_unit_mask, to_unit_mask; + + if (from == to) + return; + + if (to < from) { + bitset_pos_t tmp = from; + from = to; + to = tmp; + } + + if (to > a->size) + to = a->size; + + /* + * A small example (for cleaning bits in the same unit). + * from = 7 + * to = 19 + * do_set = 0 + * result: xxxxxxx000000000000xxxxxxxxxxxxx + * from_unit_mask: 00000001111111111111111111111111 + * to_unit_mask: 11111111111111111110000000000000 + * scale: 01234567890123456789012345678901 + * 1 2 3 + */ + + from_unit = from / BS_UNIT_SIZE_BITS; + from_unit_mask = ~((1 << from) - 1); + from = from & BS_UNIT_MASK; + + to_unit = to / BS_UNIT_SIZE_BITS; + to_unit_mask = (1 << to) - 1; + to = to & BS_UNIT_MASK; + + /* do we want to set the bits in the range? */ + if (do_set) { + /* If from and to are in the same unit: */ + if (from_unit == to_unit) + BS_DATA(a)[from_unit] |= from_unit_mask & to_unit_mask; + + /* Else, we have to treat the from and to units seperately */ + else { + BS_DATA(a)[from_unit] |= from_unit_mask; + BS_DATA(a)[to_unit] |= to_unit_mask; + for (i = from_unit + 1; i < to_unit; i++) + BS_DATA(a)[i] = BITSET_UNIT_ALL_ONE; + } + } + + /* ... or clear them? */ + else { + if (from_unit == to_unit) + BS_DATA(a)[from_unit] &= ~(from_unit_mask & to_unit_mask); + + else { + BS_DATA(a)[from_unit] &= ~from_unit_mask; + BS_DATA(a)[to_unit] &= ~to_unit_mask; + for (i = from_unit + 1; i < to_unit; i++) + BS_DATA(a)[i] = 0; + } + } +} + +#define bitset_set_range(bs, from, to) bitset_mod_range((bs), (from), (to), 1) +#define bitset_clear_range(bs, from, to) bitset_mod_range((bs), (from), (to), 0) + +/** + * Check, if a bitset is empty. + * @param a The bitset. + * @return 1, if the bitset is empty, 0 if not. + */ +static inline int bitset_is_empty(const bitset_t *a) +{ + bitset_pos_t i; + for (i = 0; i < a->units; ++i) + if (BS_DATA(a)[i] != 0) + return 0; + return 1; +} + /** * Print a bitset to a stream. - * The bitset is printed as a comma seperated list of bits set. + * The bitset is printed as a comma separated list of bits set. * @param file The stream. * @param bs The bitset. */ -static INLINE void bitset_fprint(FILE *file, const bitset_t *bs) +static inline void bitset_fprint(FILE *file, const bitset_t *bs) { const char *prefix = ""; int i; - putc('[', file); + putc('{', file); for(i = bitset_next_set(bs, 0); i != -1; i = bitset_next_set(bs, i + 1)) { fprintf(file, "%s%u", prefix, i); prefix = ","; } - putc(']', file); + putc('}', file); } -static INLINE void bitset_debug_fprint(FILE *file, const bitset_t *bs) +static inline void bitset_debug_fprint(FILE *file, const bitset_t *bs) { bitset_pos_t i; fprintf(file, "%u:", bs->units); for(i = 0; i < bs->units; ++i) - fprintf(file, " " BITSET_UNIT_FMT, bs->data[i]); + fprintf(file, " " BITSET_UNIT_FMT, BS_DATA(bs)[i]); } +/** + * Perform tgt = tgt \ src operation. + * @param tgt The target bitset. + * @param src The source bitset. + * @return the tgt set. + */ +static inline bitset_t *bitset_andnot(bitset_t *tgt, const bitset_t *src); + +/** + * Perform Union, tgt = tgt u src operation. + * @param tgt The target bitset. + * @param src The source bitset. + * @return the tgt set. + */ +static inline bitset_t *bitset_or(bitset_t *tgt, const bitset_t *src); + +/** + * Perform tgt = tgt ^ ~src operation. + * @param tgt The target bitset. + * @param src The source bitset. + * @return the tgt set. + */ +static inline bitset_t *bitset_xor(bitset_t *tgt, const bitset_t *src); + /* * Here, the binary operations follow. * And, Or, And Not, Xor are available. */ #define BINARY_OP(op) \ -static INLINE bitset_t *bitset_ ## op(bitset_t *tgt, const bitset_t *src) \ +static inline bitset_t *bitset_ ## op(bitset_t *tgt, const bitset_t *src) \ { \ bitset_pos_t i; \ bitset_pos_t n = tgt->units > src->units ? src->units : tgt->units; \ for(i = 0; i < n; i += _BITSET_BINOP_UNITS_INC) \ - _bitset_inside_binop_ ## op(&tgt->data[i], &src->data[i]); \ + _bitset_inside_binop_ ## op(&BS_DATA(tgt)[i], &BS_DATA(src)[i]); \ if(n < tgt->units) \ - _bitset_clear_rest(&tgt->data[i], tgt->units - i); \ + _bitset_clear_rest(&BS_DATA(tgt)[i], tgt->units - i); \ return _bitset_mask_highest(tgt); \ } @@ -476,7 +592,7 @@ static INLINE bitset_t *bitset_ ## op(bitset_t *tgt, const bitset_t *src) \ #define _bitset_clear_rest(data,n) _bitset_inside_clear_units(data, n) BINARY_OP(and) #undef _bitset_clear_rest -#define _bitset_clear_rest(data,n) +#define _bitset_clear_rest(data,n) do { } while(0) BINARY_OP(andnot) BINARY_OP(or)