bitvector.hh

Go to the documentation of this file.

// -*- c-basic-offset: 4; related-file-name: "../../lib/bitvector.cc" -*-
#ifndef CLICK_BITVECTOR_HH
#define CLICK_BITVECTOR_HH
#include <click/string.hh>
#include <click/glue.hh>
CLICK_DECLS
 
class Bitvector {
  public:
 
    class Bit;
    typedef bool (Bitvector::*unspecified_bool_type)() const;
 
    typedef uint32_t word_type;
    enum { wbits = 32, wshift = 5, wmask = 31 };
 
    inline Bitvector();
    explicit inline Bitvector(int n);
    explicit inline Bitvector(bool bit);
    inline Bitvector(int n, bool bit);
    inline Bitvector(const Bitvector &x);
    inline ~Bitvector();
 
    inline int size() const;
    inline Bit operator[](int i);
    inline bool operator[](int i) const;
    inline Bit force_bit(int i);
 
    inline int word_size() const;
    inline int max_word() const;
    inline word_type *words();
    inline const word_type *words() const;
 
    bool zero() const;
    inline operator unspecified_bool_type() const;
    inline bool operator!() const;
 
    Bitvector &assign(int n, bool bit);
    Bitvector &operator=(const Bitvector &x);
    void clear();
    void resize(int n);
 
    friend inline bool operator==(const Bitvector &a, const Bitvector &b);
    friend inline bool operator!=(const Bitvector &a, const Bitvector &b);
    bool nonzero_intersection(const Bitvector &x) const;
 
    inline Bitvector operator~() const;
    friend inline Bitvector operator&(Bitvector a, const Bitvector &b);
    friend inline Bitvector operator|(Bitvector a, const Bitvector &b);
    friend inline Bitvector operator^(Bitvector a, const Bitvector &b);
    friend inline Bitvector operator-(Bitvector a, const Bitvector &b);
 
    void flip();
    inline void negate();
    Bitvector &operator&=(const Bitvector &x);
    Bitvector &operator|=(const Bitvector &x);
    Bitvector &operator^=(const Bitvector &x);
    inline Bitvector &operator-=(const Bitvector &x);
    void offset_or(const Bitvector &x, int offset);
    void or_with_difference(const Bitvector &x, Bitvector &difference);
 
    void swap(Bitvector &x);
    void set_range(int start, int length, bool value);
    bool range(int start, int length);
 
    inline int weight() const;
    inline int popcnt() const;
    inline int weight_range(int start, int length) const;
 
    inline int clz() const;
 
    bool parse(const String &str, int min_val, int max_val, int offset = 0);
    String unparse(int read_offset = 0, int output_offset = 0) const;
 
    typedef word_type data_word_type CLICK_DEPRECATED;
    enum { data_word_bits = wbits };
    inline word_type *data_words() CLICK_DEPRECATED;
    inline const word_type *data_words() const CLICK_DEPRECATED;
    static Bitvector from_mask(unsigned long mask);
 
  private:
 
    enum { ninline = 2, inlinebits = ninline * wbits };
 
    int _max;
    word_type *_data;
    word_type _f[ninline];
 
    void finish_copy_constructor(const Bitvector &);
    inline void clear_last();
    void hard_resize(int, bool);
 
};
 
 
class Bitvector::Bit { public:
 
    inline Bit( const Bit & ) = default; 
    inline Bit(Bitvector::word_type &w, int bit_offset);
 
    inline operator bool() const;
 
    inline Bit &operator=(bool x);
    inline Bit &operator=(const Bit &x);
    inline void flip();
 
    inline Bit &operator&=(bool x);
    inline Bit &operator|=(bool x);
    inline Bit &operator^=(bool x);
    inline Bit &operator-=(bool x);
 
  private:
 
    Bitvector::word_type &_p;
    Bitvector::word_type _mask;
 
};
 
 
inline Bitvector::Bitvector()
    : _max(-1), _data(_f) {
    _f[0] = 0;
}
 
inline Bitvector::Bitvector(int n)
    : _data(_f) {
    assert(n >= 0);
    if (n <= inlinebits) {
        _max = n - 1;
        memset(_f, 0, sizeof(_f));
    } else {
        _max = -1;
        resize(n);
    }
}
 
inline Bitvector::Bitvector(bool bit)
    : _max(0), _data(_f) {
    _f[0] = bit;
}
 
inline Bitvector::Bitvector(int n, bool b)
    : _max(-1), _data(_f) {
    assign(n, b);
}
 
inline Bitvector::Bitvector(const Bitvector &x)
    : _max(x._max), _data(_f) {
    if (_max < inlinebits)
        memcpy(_data, x._data, ninline * sizeof(word_type));
    else
        finish_copy_constructor(x);
}
 
inline Bitvector::~Bitvector() {
    if (_data != _f)
        delete[] _data;
}
 
inline int Bitvector::size() const {
    return _max + 1;
}
 
inline Bitvector::operator unspecified_bool_type() const {
    return !zero() ? &Bitvector::zero : 0;
}
 
inline bool Bitvector::operator!() const {
    return zero();
}
 
inline Bitvector::Bit Bitvector::operator[](int i) {
    assert(i >= 0 && i <= _max);
    return Bit(_data[i>>wshift], i & wmask);
}
 
inline bool Bitvector::operator[](int i) const {
    assert(i >= 0 && i <= _max);
    return (_data[i>>wshift] & (word_type(1) << (i & wmask))) != 0;
}
 
inline Bitvector::Bit Bitvector::force_bit(int i) {
    assert(i >= 0);
    if (i > _max)
        resize(i + 1);
    return Bit(_data[i>>wshift], i & wmask);
}
 
inline int Bitvector::word_size() const {
    return (_max + wbits) >> wshift;
}
 
inline int Bitvector::max_word() const {
    return (_max < 0 ? -1 : _max >> wshift);
}
 
inline Bitvector::word_type *Bitvector::words() {
    return _data;
}
 
inline const Bitvector::word_type *Bitvector::words() const {
    return _data;
}
 
inline Bitvector::word_type *Bitvector::data_words() {
    return _data;
}
inline const Bitvector::word_type *Bitvector::data_words() const {
    return _data;
}
inline bool operator==(const Bitvector &a, const Bitvector &b) {
    return a.size() == b.size()
        && memcmp(a.words(), b.words(), a.word_size() * sizeof(Bitvector::word_type)) == 0;
}
 
inline bool operator!=(const Bitvector &a, const Bitvector &b) {
    return !(a == b);
}
 
inline Bitvector &Bitvector::operator-=(const Bitvector &x) {
    return *this &= ~x;
}
 
inline void Bitvector::negate() {
    flip();
}
 
inline Bitvector Bitvector::operator~() const {
    Bitvector m = *this;
    m.flip();
    return m;
}
 
inline Bitvector operator&(Bitvector a, const Bitvector &b) {
    return a &= b;
}
 
inline Bitvector operator|(Bitvector a, const Bitvector &b) {
    return a |= b;
}
 
inline Bitvector operator^(Bitvector a, const Bitvector &b) {
    return a ^= b;
}
 
inline Bitvector operator-(Bitvector a, const Bitvector &b) {
    return a & ~b;
}
 
inline void click_swap(Bitvector &a, Bitvector &b) {
    a.swap(b);
}
 
inline void assign_consume(Bitvector &a, Bitvector &b) {
    a.swap(b);
}
 
 
inline Bitvector::Bit::Bit(Bitvector::word_type &w, int bit_offset)
    : _p(w), _mask(Bitvector::word_type(1) << bit_offset) {
}
 
inline Bitvector::Bit::operator bool() const {
    return (_p & _mask) != 0;
}
 
inline Bitvector::Bit &Bitvector::Bit::operator=(bool x) {
    if (x)
        _p |= _mask;
    else
        _p &= ~_mask;
    return *this;
}
 
inline Bitvector::Bit &Bitvector::Bit::operator=(const Bit &x) {
    if (x._p & x._mask)
        _p |= _mask;
    else
        _p &= ~_mask;
    return *this;
}
 
inline void Bitvector::Bit::flip() {
    _p ^= _mask;
}
 
inline Bitvector::Bit &Bitvector::Bit::operator&=(bool x) {
    if (!x)
        _p &= ~_mask;
    return *this;
}
 
inline Bitvector::Bit &Bitvector::Bit::operator|=(bool x) {
    if (x)
        _p |= _mask;
    return *this;
}
 
inline Bitvector::Bit &Bitvector::Bit::operator^=(bool x) {
    if (x)
        _p ^= _mask;
    return *this;
}
 
inline Bitvector::Bit &Bitvector::Bit::operator-=(bool x) {
    if (x)
        _p &= ~_mask;
    return *this;
}
 
inline int Bitvector::weight() const {
        int n = 0;
#if HAVE___BUILTIN_POPCOUNT
        for (int i =0 ; i < (_max + wbits)>>wshift; i++) {
                n+= __builtin_popcount(_data[i]);
        }
#else
        for (int i = 0; i < size(); i++)
          if ((*this)[i])
                n++;
#endif
        return n;
}
 
inline int Bitvector::popcnt() const {
        return weight();
}
 
inline int Bitvector::weight_range(int start, int length) const {
        assert(start+length < _max);
        int w = 0;
        for (int i = start; i < start + length; i++)
                if ((*this)[i])
                        w++;
        return w;
}
 
inline int Bitvector::clz() const {
        int n = 0;
        for (int i =0 ; i < (_max + wbits)>>wshift; i++) {
                if (!_data[i])
                        n+=wbits;
                else {
#if HAVE___BUILTIN_CTZ
                        return n + __builtin_ctz(_data[i]);
#else
                        while (!(*this)[n])
                                n++;
                        return n;
#endif
                }
        }
        return size();
}
 
 
CLICK_ENDDECLS
#endif