Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

BitSet.H

Go to the documentation of this file.
00001 /* _______              __
00002   / ___/ /  ___  __ _  / /  ___
00003  / /__/ _ \/ _ \/  ' \/ _ \/ _ \
00004  \___/_//_/\___/_/_/_/_.__/\___/ 
00005 */
00006 //
00007 // This software is copyright (C) by the Lawrence Berkeley
00008 // National Laboratory.  Permission is granted to reproduce
00009 // this software for non-commercial purposes provided that
00010 // this notice is left intact.
00011 // 
00012 // It is acknowledged that the U.S. Government has rights to
00013 // this software under Contract DE-AC03-765F00098 between
00014 // the U.S.  Department of Energy and the University of
00015 // California.
00016 //
00017 // This software is provided as a professional and academic
00018 // contribution for joint exchange. Thus it is experimental,
00019 // is provided ``as is'', with no warranties of any kind
00020 // whatsoever, no support, no promise of updates, or printed
00021 // documentation. By using this software, you acknowledge
00022 // that the Lawrence Berkeley National Laboratory and
00023 // Regents of the University of California shall have no
00024 // liability with respect to the infringement of other
00025 // copyrights by any part of this software.
00026 //
00027 
00028 
00029 // arch dependant setting for what a WORD should be
00030 // WORD is the smallest efficiently accessible memory
00031 // object.  WORD_BITS is the size, in bits, of this object
00032 //
00033 //  Later I can make this object use a Pool, and we can
00034 // avoid all the memory system call overhead for creation and
00035 // use placement new.
00036 
00037 #define WORD unsigned int
00038 const int  WORDSIZE = 8*sizeof(unsigned int);
00039 
00040 // WORDSIZE is no the same as sizeof(WORD).  This is the number of bits, not chars
00041 #include <assert.h>
00042 #include <iostream>
00043 
00044 using std::ostream;
00045 
00046 
00047 class BitSetIterator;
00048 
00050 /* stores a contiguous memory chunk and represents true with a 1 bit
00051    and false with a 0 bit. 
00052 
00053    example: 35 bits, set to true, WORDSIZE=8:
00054 
00055    m_index = 5 (need at least 5 WORDS to hold that many bits)
00056    m_size  = 35
00057 
00058    +-------+-------+-------+-------+-------+
00059    1111111111111111111111111111111111111111
00060 
00061    now, set bit 35 to 0
00062 
00063    index = 35/WORDSIZE = 4       , hence, we are in the fourth WORD.
00064    mask  = 35 - 4*WORDSIZE =  3    hence, we are in the third bit of the fourth word
00065 
00066    now, we can use the masks:
00067 static WORD trueMasks[WORDSIZE]; //10000000, 01000000, 00100000, ....
00068 
00069    word[index] = word[index] & ~trueMasks[mask]  (~trueMasks[3] = 11101111)
00070 
00071    now we have:
00072 
00073    +-------+-------+-------+-------+-------+
00074    1111111111111111111111111111111111101111
00075 */
00076 class BitSet
00077 {
00078 public:
00080   BitSet();
00081 
00083   BitSet(int bits, bool init);
00084 
00086   void define(int bits, bool init);
00087 
00089   BitSet(const BitSet& rhs);
00090 
00092   BitSet& operator=(const BitSet& rhs);
00093 
00095   ~BitSet();
00096 
00097   // somewhat slow random access. Fast iterating done
00098   // with BitSetIterator
00099   bool operator[](int i) const;
00100 
00101   /* 
00102       logic operations 
00103   */
00104 
00106   void setTrue(int i); // set bit to 1
00107 
00109   void setFalse(int i); // set bit to 0
00110 
00112 
00115   bool isEmpty() const;
00116 
00118 
00121   bool isFull() const;
00122 
00124   int size() const;
00125   static int initialize();
00126 
00127   // not for public, used by memory tracker.
00128   static long int bytes;
00129   static long int peak;
00130 
00131 private:
00132   friend class BitSetIterator;
00133 
00134   WORD* m_bits;
00135   int   m_size;
00136   int   m_length;  //length of char array, not bit length
00137 
00138   static WORD trueMasks[WORDSIZE]; //10000000, 01000000, 00100000, ....
00139 };
00140 
00141 // somewhat slow random access. Fast iterating done
00142 // with BitSetIterator
00143 inline bool BitSet::operator[](int i) const
00144 {
00145   assert(i>=0);
00146   assert(i<m_size);
00147   int index = i/WORDSIZE;
00148   assert(index < m_length);
00149   int remainder = i-WORDSIZE*index;
00150   WORD tmp = m_bits[index] & trueMasks[remainder];
00151   return tmp > 0;
00152 }
00153 
00154 inline int BitSet::size() const
00155 {
00156   return m_size;
00157 }
00158 
00160 /* Iterate over bits in a BitSet.  return true if bit is 1
00161 
00162    example: 35 bits in bitset, WORDSIZE=8:
00163 
00164    currently at the 22nd bit: (bit # =21)
00165 
00166    |-m_index = 2---|
00167    +-------+-------+-------+-------+-------+
00168    1111111110001111111100011111111100011111
00169                    ^    ^   
00170        m_remainder |----| = 6      ^  ^
00171                                    |--| m_partialBits = 3
00172 
00173   returns: false for operator()
00174 .
00175 */   
00176 class BitSetIterator
00177 {
00178 public:
00180   BitSetIterator();
00181 
00183   BitSetIterator(const BitSet& bitset);
00184 
00185   // copy and assign should be fine
00186 
00188   bool operator()() const;
00189 
00191   bool ok() const;
00192 
00194   void operator++();
00195 
00197   void begin();
00198 
00200   void end();
00201 
00202 private:
00203   int m_index;
00204   int m_remainder;
00205   int m_length;
00206 
00207   int m_partialBits;
00208   const BitSet* m_bitset;
00209   static BitSet emptyBitSet;
00210 };
00211 
00212 inline
00213 BitSetIterator::BitSetIterator()
00214   : m_index(0), m_remainder(0), m_length(0), m_partialBits(0), m_bitset(&emptyBitSet)
00215 {;}
00216 
00217 inline
00218 BitSetIterator::BitSetIterator(const BitSet& a_bitset)
00219   :m_index(0), m_remainder(0), m_length(a_bitset.m_length - 1),
00220    m_partialBits(a_bitset.m_size - WORDSIZE*(a_bitset.m_length - 1)),
00221    m_bitset(&a_bitset)
00222 {
00223   if(m_partialBits == WORDSIZE)
00224     { 
00225       m_partialBits = 0;
00226       m_length++;
00227     }
00228 }
00229 
00230 inline
00231 bool BitSetIterator::operator()() const
00232 {
00233   return (m_bitset->m_bits[m_index] & BitSet::trueMasks[m_remainder] ) > 0;
00234 }
00235 
00236 inline
00237 bool BitSetIterator::ok() const
00238 {
00239   if(m_index < m_length) return true;
00240   if(m_remainder < m_partialBits) return true;
00241   return false;
00242 }
00243 
00244 inline
00245 void BitSetIterator::operator++()
00246 {
00247   ++m_remainder;
00248   if(m_remainder == WORDSIZE)
00249     {
00250       m_remainder = 0;
00251       ++m_index;
00252     }
00253 }

Generated on Tue Jul 2 10:42:19 2002 for Chombo by doxygen1.2.16