---

BitSet.H

Go to the documentation of this file.

/* _______              __
  / ___/ /  ___  __ _  / /  ___
 / /__/ _ \/ _ \/  ' \/ _ \/ _ \
 \___/_//_/\___/_/_/_/_.__/\___/ 
*/
//
// This software is copyright (C) by the Lawrence Berkeley
// National Laboratory.  Permission is granted to reproduce
// this software for non-commercial purposes provided that
// this notice is left intact.
// 
// It is acknowledged that the U.S. Government has rights to
// this software under Contract DE-AC03-765F00098 between
// the U.S.  Department of Energy and the University of
// California.
//
// This software is provided as a professional and academic
// contribution for joint exchange. Thus it is experimental,
// is provided ``as is'', with no warranties of any kind
// whatsoever, no support, no promise of updates, or printed
// documentation. By using this software, you acknowledge
// that the Lawrence Berkeley National Laboratory and
// Regents of the University of California shall have no
// liability with respect to the infringement of other
// copyrights by any part of this software.
//


// arch dependant setting for what a WORD should be
// WORD is the smallest efficiently accessible memory
// object.  WORD_BITS is the size, in bits, of this object
//
//  Later I can make this object use a Pool, and we can
// avoid all the memory system call overhead for creation and
// use placement new.

#define WORD unsigned int
const int  WORDSIZE = 8*sizeof(unsigned int);

// WORDSIZE is no the same as sizeof(WORD).  This is the number of bits, not chars
#include <assert.h>
#include <iostream>

using std::ostream;


class BitSetIterator;

/* stores a contiguous memory chunk and represents true with a 1 bit
   and false with a 0 bit. 

   example: 35 bits, set to true, WORDSIZE=8:

   m_index = 5 (need at least 5 WORDS to hold that many bits)
   m_size  = 35

   +-------+-------+-------+-------+-------+
   1111111111111111111111111111111111111111

   now, set bit 35 to 0

   index = 35/WORDSIZE = 4       , hence, we are in the fourth WORD.
   mask  = 35 - 4*WORDSIZE =  3    hence, we are in the third bit of the fourth word

   now, we can use the masks:
static WORD trueMasks[WORDSIZE]; //10000000, 01000000, 00100000, ....

   word[index] = word[index] & ~trueMasks[mask]  (~trueMasks[3] = 11101111)

   now we have:

   +-------+-------+-------+-------+-------+
   1111111111111111111111111111111111101111
*/
class BitSet
{
public:
  BitSet();

  BitSet(int bits, bool init);

  void define(int bits, bool init);

  BitSet(const BitSet& rhs);

  BitSet& operator=(const BitSet& rhs);

  ~BitSet();

  // somewhat slow random access. Fast iterating done
  // with BitSetIterator
  bool operator[](int i) const;

  /* 
      logic operations 
  */

  void setTrue(int i); // set bit to 1

  void setFalse(int i); // set bit to 0


  bool isEmpty() const;


  bool isFull() const;

  int size() const;
  static int initialize();

  // not for public, used by memory tracker.
  static long int bytes;
  static long int peak;

private:
  friend class BitSetIterator;

  WORD* m_bits;
  int   m_size;
  int   m_length;  //length of char array, not bit length

  static WORD trueMasks[WORDSIZE]; //10000000, 01000000, 00100000, ....
};

// somewhat slow random access. Fast iterating done
// with BitSetIterator
inline bool BitSet::operator[](int i) const
{
  assert(i>=0);
  assert(i<m_size);
  int index = i/WORDSIZE;
  assert(index < m_length);
  int remainder = i-WORDSIZE*index;
  WORD tmp = m_bits[index] & trueMasks[remainder];
  return tmp > 0;
}

inline int BitSet::size() const
{
  return m_size;
}

/* Iterate over bits in a BitSet.  return true if bit is 1

   example: 35 bits in bitset, WORDSIZE=8:

   currently at the 22nd bit: (bit # =21)

   |-m_index = 2---|
   +-------+-------+-------+-------+-------+
   1111111110001111111100011111111100011111
                   ^    ^   
       m_remainder |----| = 6      ^  ^
                                   |--| m_partialBits = 3

  returns: false for operator()
.
*/   
class BitSetIterator
{
public:
  BitSetIterator();

  BitSetIterator(const BitSet& bitset);

  // copy and assign should be fine

  bool operator()() const;

  bool ok() const;

  void operator++();

  void begin();

  void end();

private:
  int m_index;
  int m_remainder;
  int m_length;

  int m_partialBits;
  const BitSet* m_bitset;
  static BitSet emptyBitSet;
};

inline
BitSetIterator::BitSetIterator()
  : m_index(0), m_remainder(0), m_length(0), m_partialBits(0), m_bitset(&emptyBitSet)
{;}

inline
BitSetIterator::BitSetIterator(const BitSet& a_bitset)
  :m_index(0), m_remainder(0), m_length(a_bitset.m_length - 1),
   m_partialBits(a_bitset.m_size - WORDSIZE*(a_bitset.m_length - 1)),
   m_bitset(&a_bitset)
{
  if(m_partialBits == WORDSIZE)
    { 
      m_partialBits = 0;
      m_length++;
    }
}

inline
bool BitSetIterator::operator()() const
{
  return (m_bitset->m_bits[m_index] & BitSet::trueMasks[m_remainder] ) > 0;
}

inline
bool BitSetIterator::ok() const
{
  if(m_index < m_length) return true;
  if(m_remainder < m_partialBits) return true;
  return false;
}

inline
void BitSetIterator::operator++()
{
  ++m_remainder;
  if(m_remainder == WORDSIZE)
    {
      m_remainder = 0;
      ++m_index;
    }
}

---