w_bitvector.h

/* -*- mode:C++; c-basic-offset:4 -*-
     Shore-MT -- Multi-threaded port of the SHORE storage manager
   
                       Copyright (c) 2007-2009
      Data Intensive Applications and Systems Labaratory (DIAS)
               Ecole Polytechnique Federale de Lausanne
   
                         All Rights Reserved.
   
   Permission to use, copy, modify and distribute this software and
   its documentation is hereby granted, provided that both the
   copyright notice and this permission notice appear in all copies of
   the software, derivative works or modified versions, and any
   portions thereof, and that both notices appear in supporting
   documentation.
   
   This code is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS
   DISCLAIM ANY LIABILITY OF ANY KIND FOR ANY DAMAGES WHATSOEVER
   RESULTING FROM THE USE OF THIS SOFTWARE.
*/

/*<std-header orig-src='shore' incl-file-exclusion='W_BASE_H'>

 $Id: w_bitvector.h,v 1.3 2012/01/02 17:02:13 nhall Exp $

SHORE -- Scalable Heterogeneous Object REpository

Copyright (c) 1994-99 Computer Sciences Department, University of
                      Wisconsin -- Madison
All Rights Reserved.

Permission to use, copy, modify and distribute this software and its
documentation is hereby granted, provided that both the copyright
notice and this permission notice appear in all copies of the
software, derivative works or modified versions, and any portions
thereof, and that both notices appear in supporting documentation.

THE AUTHORS AND THE COMPUTER SCIENCES DEPARTMENT OF THE UNIVERSITY
OF WISCONSIN - MADISON ALLOW FREE USE OF THIS SOFTWARE IN ITS
"AS IS" CONDITION, AND THEY DISCLAIM ANY LIABILITY OF ANY KIND
FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.

This software was developed with support by the Advanced Research
Project Agency, ARPA order number 018 (formerly 8230), monitored by
the U.S. Army Research Laboratory under contract DAAB07-91-C-Q518.
Further funding for this work was provided by DARPA through
Rome Research Laboratory Contract No. F30602-97-2-0247.

*/
#include <w.h>

/**\brief Templated bitmap for arbitrary size in bits
 *
 */
template<int BIT_COUNT>
class w_bitvector_t 
{
public:
    enum { BITS = BIT_COUNT };
    typedef unsigned long Word;
private:
    enum { BITS_PER_WORD=8*sizeof(Word) };
    enum { WORDS = (BITS+BITS_PER_WORD-1)/BITS_PER_WORD };
    unsigned long data[WORDS];

public:

    w_bitvector_t() { clear(); }

    /// return size in bits
    int num_bits() const { 
        return BIT_COUNT;
    }

    /// return size in words (unsigned long)
    int num_words() const { 
        int n= sizeof(data)/sizeof(data[0]); 
        w_assert1(n==WORDS);
        return n;
    }

    /** \brief OR-together and return merged vector.
     *
     * OR-together this bitmap with other bitmap and stuff result into
     * merged.
     * Return true if this entire bitmap is found in the other.
     */
    bool overlap(w_bitvector_t &merged, const w_bitvector_t &other)  const
    {
        return words_overlap(merged, other) == num_words();
    }

    /** \brief OR-together and return merged vector.
     *
     * OR-together this bitmap with other bitmap and stuff result into
     * merged.
     * Return the number of words in which this bitmap is found in
     * the other bitmap.  
     */
    int words_overlap(w_bitvector_t &merged, const w_bitvector_t &other)  const
    {
        const unsigned long *mine=&data[0];
        const unsigned long *theirs=&other.data[0];
        unsigned long *newvec=&merged.data[0];

        int matches=0;
        for(int i=0; i < num_words(); i++)
        {
            if (*mine == (*mine & *theirs)) matches++;
            *newvec = (*mine | *theirs);
            newvec++;
            mine++;
            theirs++;
        }
        return matches;
    }

    ostream &print(ostream &o) const 
    {
        {
            int s = num_bits_set();
            const char *sep="";
            o << "set " << s << "/" << num_bits()  << " bits={";
            for(int i=0; i < BITS; i++) 
            {
                if(is_set(i)) { o << sep << i; sep="."; }
            }
            o << "}";
        }
        return o;
    }

    /// clear all bits
    void clear() {
        for(long i=0; i < WORDS; i++)
            data[i] = 0;
    }

    /// true if all bits are clear
    bool is_empty() const {
        Word hash = 0;
        for(long i=0; i < WORDS; i++)
            hash |= data[i];
        return hash == 0;
    }

    /// true if all bits are set - used in unit tests
    bool is_full() const {
        Word hash = ~0x0;
        for(long i=0; i < WORDS; i++) {
            if(hash & data[i] != hash) {
                w_assert3( num_bits_set() < BIT_COUNT);
                return false;
            }
        }
        w_assert3( num_bits_set() == BIT_COUNT);
        return true;
    }

    int num_bits_set() const {
        int j=0;
        for(int i=0; i < WORDS; i++) 
        {
            j+= w_base_t::pop_count(data[i]);
        }
        return j;
    }

    /// copy operator
    void copy(const w_bitvector_t &other)  {
        for(long i=0; i < WORDS; i++)
            data[i] = other.data[i];
    }

#define BIT_VECTOR_PROLOGUE(idx)        \
    w_assert1(idx < BITS);                \
    Word wdex = idx / BITS_PER_WORD;        \
    Word bdex = idx % BITS_PER_WORD
    
    /// Should use is_set()
    Word get_bit(Word idx) const {
        BIT_VECTOR_PROLOGUE(idx);
        return (data[wdex] >> bdex) & 0x1;
    }
    /// true if bit at index idx is set
    bool is_set(Word idx) const {
        return (get_bit(idx) == 0x1);
    }
    /// set bit at index idx 
    void set_bit(Word idx) {
        BIT_VECTOR_PROLOGUE(idx);
        data[wdex] |= (1ul << bdex);
    }
    /// clear bit at index idx 
    void clear_bit(Word idx) {
        BIT_VECTOR_PROLOGUE(idx);
        data[wdex] &= ~(1ul << bdex);
    }
#undef BIT_VECTOR_PROLOGUE
};

---