Chombo + EB  3.0
BitSet.H
Go to the documentation of this file.
1 #ifdef CH_LANG_CC
2 /*
3  * _______ __
4  * / ___/ / ___ __ _ / / ___
5  * / /__/ _ \/ _ \/ V \/ _ \/ _ \
6  * \___/_//_/\___/_/_/_/_.__/\___/
7  * Please refer to Copyright.txt, in Chombo's root directory.
8  */
9 #endif
10 
11 #ifndef _BITSET_H_
12 #define _BITSET_H_
13 
14 //
15 // Arch dependant setting for what a BITSETWORD should be
16 // BITSETWORD is the smallest efficiently accessible memory
17 // object. BITSETWORD_BITS is the size, in bits, of this object
18 //
19 // Later I can make this object use a Pool, and we can
20 // avoid all the memory system call overhead for creation and
21 // use placement new.
22 //
23 
24 #include "CH_assert.H"
25 #include <iostream>
26 #include "CH_Timer.H"
27 #include "BaseNamespaceHeader.H"
28 
29 #define BITSETWORD unsigned int
30 const int BITSETWORDSIZE = 8*sizeof(unsigned int);
31 // BITSETWORDSIZE is not the same as sizeof(BITSETWORD). This is the number of bits, not chars
32 
33 using std::ostream;
34 
35 class BitSetIterator;
36 
37 ///
38 /* stores a contiguous memory chunk and represents true with a 1 bit
39  and false with a 0 bit.
40 
41  example: 35 bits, set to true, BITSETWORDSIZE=8:
42 
43  m_index = 5 (need at least 5 BITSETWORDS to hold that many bits)
44  m_size = 35
45 
46  +-------+-------+-------+-------+-------+
47  1111111111111111111111111111111111111111
48 
49  now, set bit 35 to 0
50 
51  index = 35/BITSETWORDSIZE = 4 , hence, we are in the fourth BITSETWORD.
52  mask = 35 - 4*BITSETWORDSIZE = 3 hence, we are in the third bit of the fourth word
53 
54  now, we can use the masks:
55 static BITSETWORD trueMasks[BITSETWORDSIZE]; //10000000, 01000000, 00100000, ....
56 
57  word[index] = word[index] & ~trueMasks[mask] (~trueMasks[3] = 11101111)
58 
59  now we have:
60 
61  +-------+-------+-------+-------+-------+
62  1111111111111111111111111111111111101111
63 */
64 class BitSet
65 {
66 public:
67  ///
68  BitSet();
69 
70  ///
71  BitSet(int bits, bool init);
72 
73  ///
74  void define(int bits, bool init);
75 
76  ///
77  BitSet(const BitSet& rhs);
78 
79  ///
80  BitSet& operator=(const BitSet& rhs);
81 
82  ///
83  /**
84  Primary criterion: m_length.
85  Secondary criterion: BITSETWORD-by-BITSETWORD lexicographic comparison
86  of *m_bits.
87  */
88  bool operator<(const BitSet& rhs) const;
89 
90  ///
91  ~BitSet();
92 
93  // somewhat slow random access. Fast iterating done
94  // with BitSetIterator
95  bool operator[](int i) const;
96 
97  /*
98  logic operations
99  */
100 
101  ///
102  void setTrue(int i); // set bit to 1
103 
104  ///
105  void setFalse(int i); // set bit to 0
106 
107  ///
108  void setAllTrue(); // set all bits to 1
109 
110  ///
111  void setAllFalse(); // set all bits to 0
112 
113  ///
114  /**
115  returns 'true' if the entire bitset is zero
116  */
117  bool isEmpty() const;
118 
119  ///
120  /**
121  returns 'true' if entire bitset is 1
122  */
123  bool isFull() const;
124 
125  ///
126  int size() const;
127  static int initialize();
128 
129  int linearSize() const;
130 
131  void linearIn(const void* const inBuf);
132 
133  void linearOut(void* const a_outBuf) const;
134 
135  // not for public, used by memory tracker.
136  static long int bytes;
137  static long int peak;
138 
139 private:
140  friend class BitSetIterator;
141  friend class BitSetTrueIterator;
142 
144  int m_size;
145  int m_length; //length of char array, not bit length
146 
147  static BITSETWORD trueMasks[BITSETWORDSIZE]; //10000000, 01000000, 00100000, ....
148 };
149 
150 // somewhat slow random access. Fast iterating done
151 // with BitSetIterator
152 inline bool BitSet::operator[](int i) const
153 {
154  CH_assert(i>=0);
155  CH_assert(i<m_size);
156  int index = i/BITSETWORDSIZE;
157  CH_assert(index < m_length);
158  int remainder = i-BITSETWORDSIZE*index;
159  BITSETWORD tmp = m_bits[index] & trueMasks[remainder];
160  return tmp > 0;
161 }
162 
163 inline int BitSet::size() const
164 {
165  return m_size;
166 }
167 
168 ///
169 /* Iterate over bits in a BitSet. return true if bit is 1
170 
171  example: 35 bits in bitset, BITSETWORDSIZE=8:
172 
173  currently at the 22nd bit: (bit # =21)
174 
175  |-m_index = 2---|
176  +-------+-------+-------+-------+-------+
177  1111111110001111111100011111111100011111
178  ^ ^
179  m_remainder |----| = 6 ^ ^
180  |--| m_partialBits = 3
181 
182  returns: false for operator()
183 .
184 */
186 {
187 public:
188  ///
189  BitSetIterator();
190 
191  ///
192  BitSetIterator(const BitSet& bitset);
193 
194  // copy and assign should be fine
195 
196  ///
197  bool operator()() const;
198 
199  ///
200  bool ok() const;
201 
202  ///
203  void operator++();
204 
205  ///
206  void operator--();
207 
208  ///
209  void setpos(const int i);
210 
211  ///
212  void begin();
213 
214  ///
215  void end();
216 
217 private:
218  int m_index;
220  int m_length;
221 
223  const BitSet* m_bitset;
225 };
226 
227 inline
229  :
230  m_index(0),
231  m_remainder(0),
232  m_length(0),
233  m_partialBits(0),
234  m_bitset(&emptyBitSet)
235 {
236 }
237 
238 inline
240  :m_index(0), m_remainder(0), m_length(a_bitset.m_length - 1),
241  m_partialBits(a_bitset.m_size - BITSETWORDSIZE*(a_bitset.m_length - 1)),
242  m_bitset(&a_bitset)
243 {
245  {
246  m_partialBits = 0;
247  m_length++;
248  }
249 }
250 
251 inline
253 {
255 }
256 
257 inline
258 bool BitSetIterator::ok() const
259 {
260  if (m_index < m_length) return true;
261  if (m_remainder < m_partialBits) return true;
262  return false;
263 }
264 
265 inline
267 {
268  ++m_remainder;
270  {
271  m_remainder = 0;
272  ++m_index;
273  }
274 }
275 
276 inline
278 {
279  if (m_remainder == 0)
280  {
282  --m_index; // Warning: ok() doesn't check for < 0
283  }
284  --m_remainder;
285 }
286 
287 inline
288 void BitSetIterator::setpos(const int i)
289 {
292  CH_assert(ok());
293 }
294 
295 ///
296 /* Iterate only over bits set to 1 in a BitSet. Returns positions of the set
297  bits.
298 
299  In operator++(), the first non-zero word is found and stored in m_wordCache.
300  Next, m_wordCache is left-shifted to find the positions of the 1 bits.
301 
302  example: 35 bits in bitset, BITSETWORDSIZE=8:
303 
304  currently at the 19th bit: (bit # =18)
305 
306  |-m_index = 2---|
307  +-------+-------+-------+-------+-------+
308  1111111110001111111100011111111100011111
309  ^ ^ ^
310  Original |-+----| | m_size
311  m_wordCache | m_pos
312 
313  current m_wordCache 10000000 (Only the 20th bit left)
314 
315  Note: operator--() is not supported.
316 */
318 {
319 public:
320 
321  ///
323 
324  ///
325  BitSetTrueIterator(const BitSet& bitset);
326 
327  // copy and assign should be fine
328 
329  void define(const BitSet& a_bitset);
330 
331  ///
332  int operator()() const;
333 
334  ///
335  bool ok() const;
336 
337  ///
338  void operator++();
339 
340  ///
341  void begin();
342 
343  ///
344  void end();
345 
346 private:
349  int m_size;
350  int m_length;
351  int m_pos;
352  int m_index;
353 };
354 
355 inline
357  :
358  m_bits(0),
359  m_wordCache(0),
360  m_size(0),
361  m_length(0),
362  m_pos(0),
363  m_index(0)
364 {
365 }
366 
367 inline
369  :
370  m_bits(a_bitset.m_bits),
371  m_wordCache(0),
372  m_size(a_bitset.m_size),
373  m_length(a_bitset.m_length)
374 {
375  // Check for empty BitSet
376  for (int i = 0; i < m_length; ++i)
377  {
378  if (m_bits[i] > 0)
379  {
380  m_index = i;
381  this->operator++();
382  return;
383  }
384  }
385  end(); // All empty
386 }
387 
388 inline void
390 {
391  m_bits = a_bitset.m_bits;
392  m_wordCache = 0;
393  m_size = a_bitset.m_size;
394  m_length = a_bitset.m_length;
395  // Check for empty BitSet
396  for (int i = 0; i < m_length; ++i)
397  {
398  if (m_bits[i] > 0)
399  {
400  m_index = i;
401  this->operator++();
402  return;
403  }
404  }
405  end(); // All empty
406 }
407 
408 inline int
410 {
411  return m_pos;
412 }
413 
414 inline bool
416 {
417  return (m_pos < m_size);
418 }
419 
420 inline void
422 {
423  ++m_pos;
424  if (!m_wordCache) // Find the next non-zero word
425  {
426  int i;
427  // Using the temporary 'i' in this loop is quite faster than using
428  // 'm_index' directly, at least for Gnu.
429  for (i = m_index; i != m_length; ++i)
430  {
431  if (m_bits[i] > 0) break;
432  }
433  if (i == m_length)
434  {
435  m_pos = m_size;
436  return;
437  }
438  m_wordCache = m_bits[i];
439  m_pos = i*BITSETWORDSIZE;
440  m_index = i+1;
441  // At this point, m_wordCache *must* be > 1
442  }
443  while (!(m_wordCache & BitSet::trueMasks[0]))
444  {
445  m_wordCache <<= 1;
446  ++m_pos;
447  }
448  m_wordCache <<= 1; // Bump off the bit in m_pos (m_pos is advanced the next
449  // time we enter this routine)
450 }
451 
452 inline void
454 {
455  m_wordCache = 0;
456  m_index = 0;
457  this->operator++();
458 }
459 
460 inline void
462 {
463  m_wordCache = 0;
464  m_index = m_length;
465  m_pos = m_size;
466 }
467 
468 #include "BaseNamespaceFooter.H"
469 #endif
Definition: BitSet.H:317
bool operator<(const BitSet &rhs) const
bool operator()() const
Definition: BitSet.H:252
void end()
Definition: BitSet.H:461
const int BITSETWORDSIZE
Definition: BitSet.H:30
#define CH_assert(cond)
Definition: CHArray.H:37
void define(int bits, bool init)
static BitSet emptyBitSet
Definition: BitSet.H:224
void begin()
Definition: BitSet.H:453
BitSet & operator=(const BitSet &rhs)
friend class BitSetIterator
Definition: BitSet.H:140
void setpos(const int i)
Definition: BitSet.H:288
int m_size
Definition: BitSet.H:144
int m_index
Definition: BitSet.H:352
bool isEmpty() const
void setAllTrue()
static long int bytes
Definition: BitSet.H:136
void define(const BitSet &a_bitset)
Definition: BitSet.H:389
static long int peak
Definition: BitSet.H:137
int m_length
Definition: BitSet.H:145
const BitSet * m_bitset
Definition: BitSet.H:223
int m_length
Definition: BitSet.H:220
BitSetIterator()
Definition: BitSet.H:228
BitSetTrueIterator()
Definition: BitSet.H:356
BITSETWORD * m_bits
Definition: BitSet.H:143
void operator++()
Definition: BitSet.H:266
bool isFull() const
void linearIn(const void *const inBuf)
BITSETWORD m_wordCache
Definition: BitSet.H:348
int operator()() const
Definition: BitSet.H:409
int m_size
Definition: BitSet.H:349
Definition: BitSet.H:64
#define BITSETWORD
Definition: BitSet.H:29
int linearSize() const
void setFalse(int i)
bool ok() const
Definition: BitSet.H:258
bool operator[](int i) const
Definition: BitSet.H:152
void setTrue(int i)
static int initialize()
const BITSETWORD * m_bits
Definition: BitSet.H:347
int m_partialBits
Definition: BitSet.H:222
void linearOut(void *const a_outBuf) const
bool ok() const
Definition: BitSet.H:415
int m_length
Definition: BitSet.H:350
int m_index
Definition: BitSet.H:218
int size() const
Definition: BitSet.H:163
void operator++()
Definition: BitSet.H:421
int m_pos
Definition: BitSet.H:351
static BITSETWORD trueMasks[BITSETWORDSIZE]
Definition: BitSet.H:147
Definition: BitSet.H:185
void setAllFalse()
void operator--()
Definition: BitSet.H:277
int m_remainder
Definition: BitSet.H:219