X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fadt%2Fbitset.h;h=5d9aada3f7e48fa37b140a80d54c456476bd29fa;hb=1b4cac3471b02b63e9656cd8c876f067766fe482;hp=8e3b3b93e2d3d736789e5d3f389e885c3eeee834;hpb=eb4781c7307cfa176330b5a46f75ccdfa467fa90;p=libfirm diff --git a/ir/adt/bitset.h b/ir/adt/bitset.h index 8e3b3b93e..5d9aada3f 100644 --- a/ir/adt/bitset.h +++ b/ir/adt/bitset.h @@ -1,127 +1,102 @@ -/** - * @file bitset.h - * @date 15.10.2004 - * @author Sebastian Hack - * @brief A bitset implementation. +/* + * Copyright (C) 1995-2011 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 convenience layer over raw_bitsets (stores number of bits + * with the bitfield) + * @author Matthias Braun + */ +#ifndef FIRM_ADT_BITSET_H +#define FIRM_ADT_BITSET_H #include #include #include #include +#include "irprintf.h" -#ifdef _WIN32 -#include -#else -#include -#endif - -#include "firm_config.h" +#include "xmalloc.h" #include "bitfiddle.h" +#include "raw_bitset.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; +typedef struct bitset_t { + size_t size; /**< size of the bitset in bits */ + unsigned data[1]; /**< data (should be declared data[] but this is only + allowed in C99) */ } 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) - /** - * Initialize a bitset. - * This functions should not be called. - * - * Note that this function needs three macros which must be provided by the - * bitfield implementor: - * - _bitset_overall_size(size) The overall size that must be - * allocated for the bitfield in bytes. - * - _bitset_units(size) The number of units that will be - * present in the bitfield for a given highest bit. - * - _bitset_data_ptr(data, size) This produces as pointer to the - * first unit in the allocated memory area. The main reason for this - * macro is, that some bitset implementors want control over memory - * alignment. - * - * @param area A pointer to memory reserved for the bitset. - * @param size The size of the bitset in bits. - * @return A pointer to the initialized bitset. + * return the number of bytes a bitset would need */ -static INLINE bitset_t *_bitset_prepare(void *area, bitset_pos_t size) +static inline size_t bitset_total_size(size_t n_bits) { - 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); - return ptr; + return sizeof(bitset_t) - sizeof(((bitset_t*)0)->data) + + BITSET_SIZE_BYTES(n_bits); } /** - * Mask out all bits, which are only there, because the number - * of bits in the set didn't match a unit size boundary. - * @param bs The bitset. - * @return The masked bitset. + * initialize a bitset for bitsize size (bitset should point to memory + * with a size calculated by bitset_total_size) */ -static INLINE bitset_t *_bitset_mask_highest(bitset_t *bs) +static inline bitset_t *bitset_init(void *memory, size_t size) { - bitset_pos_t rest = bs->size & BS_UNIT_MASK; - if (rest) - bs->data[bs->units - 1] &= (1 << rest) - 1; - return bs; + bitset_t *result = (bitset_t*) memory; + result->size = size; + rbitset_clear_all(result->data, size); + return result; } -/** - * Get the capacity of the bitset in bits. - * @param bs The bitset. - * @return The capacity in bits of the bitset. - */ -#define bitset_capacity(bs) ((bs)->units * BS_UNIT_SIZE_BITS) - -/** - * Get the size of the bitset in bits. - * @note Note the difference between capacity and size. - * @param bs The bitset. - * @return The highest bit which can be set or cleared plus 1. - */ -#define bitset_size(bs) ((bs)->size) - /** * Allocate a bitset on an obstack. * @param obst The obstack. * @param size The greatest bit that shall be stored in the set. * @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) +static inline bitset_t *bitset_obstack_alloc(struct obstack *obst, + size_t n_bits) +{ + size_t size = bitset_total_size(n_bits); + void *memory = obstack_alloc(obst, size); + return bitset_init(memory, n_bits); +} /** * Allocate a bitset via malloc. * @param size The greatest bit that shall be stored in the set. * @return A pointer to an empty initialized bitset. */ -#define bitset_malloc(size) \ - _bitset_prepare(xmalloc(_bitset_overall_size(sizeof(bitset_t), size)), size) +static inline bitset_t *bitset_malloc(size_t n_bits) +{ + size_t size = bitset_total_size(n_bits); + void *memory = xmalloc(size); + return bitset_init(memory, n_bits); +} /** * Free a bitset allocated with bitset_malloc(). * @param bs The bitset. */ -#define bitset_free(bs) free(bs) +static inline void bitset_free(bitset_t *bitset) +{ + xfree(bitset); +} /** * Allocate a bitset on the stack via alloca. @@ -129,21 +104,17 @@ 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_init(alloca(bitset_total_size(size)), (size)) /** - * Get the unit which contains a specific bit. - * This function is internal. + * Get the size of the bitset in bits. + * @note Note the difference between capacity and size. * @param bs The bitset. - * @param bit The bit. - * @return A pointer to the unit containing the bit. + * @return The highest bit which can be set or cleared plus 1. */ -static INLINE bitset_unit_t *_bitset_get_unit(const bitset_t *bs, bitset_pos_t bit) +static inline size_t bitset_size(const bitset_t *bitset) { - /* 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; + return bitset->size; } /** @@ -151,10 +122,10 @@ 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, size_t bit) { - bitset_unit_t *unit = _bitset_get_unit(bs, bit); - _bitset_inside_set(unit, bit & BS_UNIT_MASK); + assert(bit < bs->size); + rbitset_set(bs->data, bit); } /** @@ -162,10 +133,10 @@ 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, size_t bit) { - bitset_unit_t *unit = _bitset_get_unit(bs, bit); - _bitset_inside_clear(unit, bit & BS_UNIT_MASK); + assert(bit < bs->size); + rbitset_clear(bs->data, bit); } /** @@ -174,10 +145,10 @@ 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 bool bitset_is_set(const bitset_t *bs, size_t bit) { - bitset_unit_t *unit = _bitset_get_unit(bs, bit); - return _bitset_inside_is_set(unit, bit & BS_UNIT_MASK); + assert(bit < bs->size); + return rbitset_is_set(bs->data, bit); } /** @@ -185,79 +156,51 @@ 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, size_t bit) { - bitset_unit_t *unit = _bitset_get_unit(bs, bit); - _bitset_inside_flip(unit, bit & BS_UNIT_MASK); + assert(bit < bs->size); + rbitset_flip(bs->data, 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_mask_highest(bs); + rbitset_flip_all(bs->data, bs->size); } /** - * Copy a bitset to another. + * Copy a bitset to another. Both bitset must be initialized and have the same + * number of bits. * @param tgt The target bitset. * @param src The source bitset. * @return The target bitset. */ -static INLINE bitset_t *bitset_copy(bitset_t *tgt, const bitset_t *src) +static inline void 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); - if(tu > min_units) - memset(tgt->data + min_units, 0, BS_UNIT_SIZE * (tu - min_units)); - return _bitset_mask_highest(tgt); + assert(tgt->size == src->size); + rbitset_copy(tgt->data, src->data, src->size); } -/** - * 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) +static inline void bitset_copy_into(bitset_t *tgt, const bitset_t *src) { - 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; + assert(tgt->size >= src->size); + rbitset_copy_into(tgt->data, src->data, src->size); } /** - * Find the greatest bit set in the bitset. + * Find the next unset bit from a given bit. + * @note Note that if pos is unset, pos is returned. * @param bs The bitset. - * @return The greatest bit set in the bitset. + * @param pos The bit from which to search for the next set bit. + * @return The next set bit from pos on, or (size_t)-1, if no unset bit was + * found after pos. */ -static INLINE bitset_pos_t bitset_max(const bitset_t *bs) +static inline size_t bitset_next_clear(const bitset_t *bs, size_t pos) { - 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; + return rbitset_next_max(bs->data, pos, bs->size, false); } /** @@ -265,69 +208,25 @@ static INLINE bitset_pos_t bitset_max(const bitset_t *bs) * @note Note that if pos is set, pos is returned. * @param bs The bitset. * @param pos The bit from which to search for the next set bit. - * @return The next set bit from pos on, or -1, if no set bit was found - * after pos. + * @return The next set bit from pos on, or (size_t)-1, if no set bit was + * found after pos. */ -static INLINE bitset_pos_t _bitset_next(const bitset_t *bs, - bitset_pos_t pos, int set) +static inline size_t bitset_next_set(const bitset_t *bs, size_t pos) { - if(pos >= bs->size) - return -1; - - { - bitset_pos_t unit_number = pos / BS_UNIT_SIZE_BITS; - bitset_unit_t set_mask = -set; - bitset_pos_t bit_in_unit = pos & BS_UNIT_MASK; - bitset_pos_t in_unit_mask = (1 << bit_in_unit) - 1; - - /* - * 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]; - - /* - * Find the next bit set in the unit. - * Mind that this function returns 0, if the unit is -1 and - * counts the bits from 1 on. - */ - bitset_pos_t next_in_this_unit = - _bitset_inside_ntz_value((set_mask ^ 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; - - /* 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_pos_t first_set = _bitset_inside_ntz_value(set_mask ^ data); - - if(first_set < BS_UNIT_SIZE_BITS) - return first_set + i * BS_UNIT_SIZE_BITS; - } - } - } - - return -1; + return rbitset_next_max(bs->data, pos, bs->size, true); } -#define bitset_next_clear(bs,pos) _bitset_next((bs), (pos), 0) -#define bitset_next_set(bs,pos) _bitset_next((bs), (pos), 1) - /** * Convenience macro for bitset iteration. * @param bitset The bitset. - * @param elm A unsigned long variable. + * @param elm A size_t variable. */ -#define bitset_foreach(bitset,elm) \ - for(elm = bitset_next_set(bitset,0); elm != -1; elm = bitset_next_set(bitset,elm+1)) +#define bitset_foreach(bitset, elm) \ + for (size_t elm = 0; (elm = bitset_next_set((bitset), elm)) != (size_t)-1; ++elm) -#define bitset_foreach_clear(bitset,elm) \ - for(elm = bitset_next_clear(bitset,0); elm != -1; elm = bitset_next_clear(bitset,elm+1)) +#define bitset_foreach_clear(bitset, elm) \ + for (size_t elm = 0; (elm = bitset_next_clear((bitset), elm)) != (size_t)-1; ++elm) /** * Count the bits set. @@ -335,15 +234,9 @@ 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 size_t bitset_popcount(const bitset_t *bs) { - bitset_pos_t i, pop = 0; - bitset_unit_t *unit; - - for(i = 0, unit = bs->data; i < bs->units; ++i, ++unit) - pop += _bitset_inside_pop(unit); - - return pop; + return rbitset_popcount(bs->data, bs->size); } /** @@ -351,10 +244,9 @@ 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 void bitset_clear_all(bitset_t *bs) { - memset(bs->data, 0, BS_UNIT_SIZE * bs->units); - return bs; + rbitset_clear_all(bs->data, bs->size); } /** @@ -362,10 +254,9 @@ 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 void bitset_set_all(bitset_t *bs) { - memset(bs->data, -1, bs->units * BS_UNIT_SIZE); - return _bitset_mask_highest(bs); + rbitset_set_all(bs->data, bs->size); } /** @@ -375,31 +266,10 @@ 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 bool 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]; - - if((lu | ru) & ~ru) - return 0; - } - - /* - * If the left hand sinde is a larger bitset than rhs, - * we have to check, that all extra bits in lhs are 0 - */ - if(lhs->units > n) { - for(i = n; i < lhs->units; ++i) { - if(lhs->data[i] != 0) - return 0; - } - } - - return 1; + assert(lhs->size == rhs->size); + return rbitset_contains(lhs->data, rhs->data, lhs->size); } /** @@ -407,84 +277,135 @@ 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) +{ + rbitset_minus1(bs->data, bs->size); +} + +/** + * 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 bool bitset_intersect(const bitset_t *a, const bitset_t *b) +{ + assert(a->size == b->size); + return rbitsets_have_common(a->data, b->data, a->size); +} + +/** + * 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, size_t from, size_t to, + bool do_set) { -#define _SH (sizeof(bitset_unit_t) * 8 - 1) + if (from == to) + return; - bitset_pos_t i; + if (to < from) { + size_t tmp = from; + from = to; + to = tmp; + } + + if (to > a->size) + to = a->size; - for(i = 0; i < bs->units; ++i) { - bitset_unit_t unit = bs->data[i]; - bitset_unit_t um1 = unit - 1; + rbitset_set_range(a->data, from, to, do_set); +} - bs->data[i] = um1; +#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) - if(((unit >> _SH) ^ (um1 >> _SH)) == 0) - break; - } -#undef _SH +/** + * Check, if a bitset is empty. + * @param a The bitset. + * @return 1, if the bitset is empty, 0 if not. + */ +static inline bool bitset_is_empty(const bitset_t *bs) +{ + return rbitset_is_empty(bs->data, bs->size); } /** * 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; + size_t i; - putc('[', file); - for(i = bitset_next_set(bs, 0); i != -1; i = bitset_next_set(bs, i + 1)) { - fprintf(file, "%s%u", prefix, i); + putc('{', file); + for(i = bitset_next_set(bs, 0); i != (size_t)-1; i = bitset_next_set(bs, i + 1)) { + ir_fprintf(file, "%s%zu", prefix, i); prefix = ","; } - putc(']', file); + putc('}', file); } -static INLINE void bitset_debug_fprint(FILE *file, const bitset_t *bs) +/** + * Perform tgt = tgt & src operation. + * @param tgt The target bitset. + * @param src The source bitset. + * @return the tgt set. + */ +static inline void bitset_and(bitset_t *tgt, const bitset_t *src) { - bitset_pos_t i; + assert(tgt->size == src->size); + rbitset_and(tgt->data, src->data, src->size); +} - fprintf(file, "%u:", bs->units); - for(i = 0; i < bs->units; ++i) - fprintf(file, " " BITSET_UNIT_FMT, bs->data[i]); +/** + * Perform tgt = tgt & ~src operation. + * @param tgt The target bitset. + * @param src The source bitset. + * @return the tgt set. + */ +static inline void bitset_andnot(bitset_t *tgt, const bitset_t *src) +{ + assert(tgt->size == src->size); + rbitset_andnot(tgt->data, src->data, src->size); } -/* - * 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) \ -{ \ - 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]); \ - if(n < tgt->units) \ - _bitset_clear_rest(&tgt->data[i], tgt->units - i); \ - return _bitset_mask_highest(tgt); \ +/** + * Perform Union, tgt = tgt u src operation. + * @param tgt The target bitset. + * @param src The source bitset. + * @return the tgt set. + */ +static inline void bitset_or(bitset_t *tgt, const bitset_t *src) +{ + assert(tgt->size == src->size); + rbitset_or(tgt->data, src->data, src->size); } -/* - * Define the clear rest macro for the and, since it is the only case, - * were non existed (treated as 0) units in the src must be handled. - * For all other operations holds: x Op 0 = x for Op in { Andnot, Or, Xor } - * - * For and, each bitset implementer has to provide the macro - * _bitset_clear_units(data, n), which clears n units from the pointer - * data on. - */ -#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) - -BINARY_OP(andnot) -BINARY_OP(or) -BINARY_OP(xor) +/** + * Perform tgt = tgt ^ src operation. + * @param tgt The target bitset. + * @param src The source bitset. + * @return the tgt set. + */ +static inline void bitset_xor(bitset_t *tgt, const bitset_t *src) +{ + assert(tgt->size == src->size); + rbitset_xor(tgt->data, src->data, src->size); +} + +/** + * Copy a raw bitset into an bitset. + */ +static inline void rbitset_copy_to_bitset(const unsigned *rbitset, + bitset_t *bitset) +{ + rbitset_copy(bitset->data, rbitset, bitset->size); +} #endif