BitSet.H

Go to the documentation of this file.

/*   _______              __
    / ___/ /  ___  __ _  / /  ___
   / /__/ _ \/ _ \/  V \/ _ \/ _ \
   \___/_//_/\___/_/_/_/_.__/\___/
*/
// CHOMBO Copyright (c) 2000-2004, The Regents of the University of
// California, through Lawrence Berkeley National Laboratory (subject to
// receipt of any required approvals from U.S. Dept. of Energy).  All
// rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// (1) Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
// (2) Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
// (3) Neither the name of Lawrence Berkeley National Laboratory, U.S.
// Dept. of Energy nor the names of its contributors may be used to endorse
// or promote products derived from this software without specific prior
// written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
// TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
// PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
// OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// You are under no obligation whatsoever to provide any bug fixes,
// patches, or upgrades to the features, functionality or performance of
// the source code ("Enhancements") to anyone; however, if you choose to
// make your Enhancements available either publicly, or directly to
// Lawrence Berkeley National Laboratory, without imposing a separate
// written license agreement for such Enhancements, then you hereby grant
// the following license: a non-exclusive, royalty-free perpetual license
// to install, use, modify, prepare derivative works, incorporate into
// other computer software, distribute, and sublicense such Enhancements or
// derivative works thereof, in binary and source code form.
//
// TRADEMARKS. Product and company names mentioned herein may be the
// trademarks of their respective owners.  Any rights not expressly granted
// herein are reserved.
//

#ifndef _BITSET_H_
#define _BITSET_H_

//
// Arch dependant setting for what a BITSETWORD should be
// BITSETWORD is the smallest efficiently accessible memory
// object.  BITSETWORD_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 BITSETWORD unsigned int
const int  BITSETWORDSIZE = 8*sizeof(unsigned int);

// BITSETWORDSIZE is no the same as sizeof(BITSETWORD).  This is the number of bits, not chars
#include "SPACE.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, BITSETWORDSIZE=8:

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

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

   now, set bit 35 to 0

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

   now, we can use the masks:
static BITSETWORD trueMasks[BITSETWORDSIZE]; //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);


  bool operator<(const BitSet& rhs) const;

  ~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();

  int linearSize() const;

  void linearIn(const void* const inBuf);

  void linearOut(void* const a_outBuf) const;

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

private:
  friend class BitSetIterator;

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

  static BITSETWORD trueMasks[BITSETWORDSIZE]; //10000000, 01000000, 00100000, ....
};

// somewhat slow random access. Fast iterating done
// with BitSetIterator
inline bool BitSet::operator[](int i) const
{
 CH_assert(i>=0);
 CH_assert(i<m_size);
  int index = i/BITSETWORDSIZE;
 CH_assert(index < m_length);
  int remainder = i-BITSETWORDSIZE*index;
  BITSETWORD 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, BITSETWORDSIZE=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 - BITSETWORDSIZE*(a_bitset.m_length - 1)),
   m_bitset(&a_bitset)
{
  if(m_partialBits == BITSETWORDSIZE)
    {
      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 == BITSETWORDSIZE)
    {
      m_remainder = 0;
      ++m_index;
    }
}

#endif

---