NCBI C++ ToolKit
bm.h
Go to the documentation of this file.

Go to the SVN repository for this file.

1 #ifndef BM__H__INCLUDED__
2 #define BM__H__INCLUDED__
3 /*
4 Copyright(c) 2002-2010 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
5 
6 Permission is hereby granted, free of charge, to any person
7 obtaining a copy of this software and associated documentation
8 files (the "Software"), to deal in the Software without restriction,
9 including without limitation the rights to use, copy, modify, merge,
10 publish, distribute, sublicense, and/or sell copies of the Software,
11 and to permit persons to whom the Software is furnished to do so,
12 subject to the following conditions:
13 
14 The above copyright notice and this permission notice shall be included
15 in all copies or substantial portions of the Software.
16 
17 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
19 OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
20 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
21 DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
22 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
23 OTHER DEALINGS IN THE SOFTWARE.
24 
25 For more information please visit: http://bmagic.sourceforge.net
26 
27 */
28 
29 
30 // define BM_NO_STL if you use BM in "STL free" environment and want
31 // to disable any references to STL headers
32 #ifndef BM_NO_STL
33 # include <iterator>
34 #endif
35 
36 #ifdef _MSC_VER
37 #pragma warning( push )
38 #pragma warning( disable : 4311 4312 4127)
39 #endif
40 
41 
42 #ifdef BMSSE42OPT
43 # ifdef BM64OPT
44 # undef BM64OPT
45 # define BM64_SSE4
46 # endif
47 # undef BMSSE2OPT
48 #endif
49 
50 
51 #include "bmconst.h"
52 #include "bmdef.h"
53 
54 
55 #ifdef BMSSE42OPT
56 # define BMVECTOPT
57 # include "bmsse4.h"
58 #endif
59 
60 #ifdef BMSSE2OPT
61 # undef BM64OPT
62 # define BMVECTOPT
63 # include "bmsse2.h"
64 #endif
65 
66 
67 #include "bmfwd.h"
68 #include "bmfunc.h"
69 #include "encoding.h"
70 #include "bmalloc.h"
71 #include "bmblocks.h"
72 
73 namespace bm
74 {
75 
76 
77 #ifdef BMCOUNTOPT
78 
79 # define BMCOUNT_INC ++count_;
80 # define BMCOUNT_DEC --count_;
81 # define BMCOUNT_VALID(x) count_is_valid_ = x;
82 # define BMCOUNT_SET(x) count_ = x; count_is_valid_ = true;
83 # define BMCOUNT_ADJ(x) if (x) ++count_; else --count_;
84 
85 #else
86 
87 # define BMCOUNT_INC
88 # define BMCOUNT_DEC
89 # define BMCOUNT_VALID(x)
90 # define BMCOUNT_SET(x)
91 # define BMCOUNT_ADJ(x)
92 
93 #endif
94 
95 
96 
97 //typedef bm::miniset<bm::block_allocator, bm::set_total_blocks> mem_save_set;
98 
99 
100 /** @defgroup bmagic BitMagic C++ Library
101  * For more information please visit: http://bmagic.sourceforge.net
102  *
103  */
104 
105 
106 /** @defgroup bvector The Main bvector<> Group
107  * This is the main group. It includes bvector template: front end of the bm library.
108  * @ingroup bmagic
109  */
110 
111 
112 
113 
114 /*!
115  @brief bitvector with runtime compression of bits.
116  @ingroup bvector
117 */
118 
119 template<class Alloc>
120 class bvector
121 {
122 public:
123 
126  /** Type used to count bits in the bit vector */
127  typedef bm::id_t size_type;
128 
129  /** Statistical information about bitset's memory allocation details. */
130  struct statistics : public bv_statistics
131  {};
132 
133  /**
134  @brief Class reference implements an object for bit assignment.
135  Since C++ does not provide with build-in bit type supporting l-value
136  operations we have to emulate it.
137 
138  @ingroup bvector
139  */
140  class reference
141  {
142  public:
144  : bv_(bv),
145  position_(position)
146  {}
147 
148  reference(const reference& ref)
149  : bv_(ref.bv_),
150  position_(ref.position_)
151  {
152  bv_.set(position_, ref.bv_.get_bit(position_));
153  }
154 
155  operator bool() const
156  {
157  return bv_.get_bit(position_);
158  }
159 
160  const reference& operator=(const reference& ref) const
161  {
162  bv_.set(position_, (bool)ref);
163  return *this;
164  }
165 
166  const reference& operator=(bool value) const
167  {
168  bv_.set(position_, value);
169  return *this;
170  }
171 
172  bool operator==(const reference& ref) const
173  {
174  return bool(*this) == bool(ref);
175  }
176 
177  /*! Bitwise AND. Performs operation: bit = bit AND value */
178  const reference& operator&=(bool value) const
179  {
180  bv_.set_bit_and(position_, value);
181  return *this;
182  }
183 
184  /*! Bitwise OR. Performs operation: bit = bit OR value */
185  const reference& operator|=(bool value) const
186  {
187  if (value != bv_.get_bit(position_))
188  {
189  bv_.set_bit(position_);
190  }
191  return *this;
192  }
193 
194  /*! Bitwise exclusive-OR (XOR). Performs operation: bit = bit XOR value */
195  const reference& operator^=(bool value) const
196  {
197  bv_.set(position_, value != bv_.get_bit(position_));
198  return *this;
199  }
200 
201  /*! Logical Not operator */
202  bool operator!() const
203  {
204  return !bv_.get_bit(position_);
205  }
206 
207  /*! Bit Not operator */
208  bool operator~() const
209  {
210  return !bv_.get_bit(position_);
211  }
212 
213  /*! Negates the bit value */
215  {
216  bv_.flip(position_);
217  return *this;
218  }
219 
220  private:
221  bvector<Alloc>& bv_; //!< Reference variable on the parent.
222  bm::id_t position_; //!< Position in the parent bitvector.
223  };
224 
225  typedef bool const_reference;
226 
227  /*!
228  @brief Base class for all iterators.
229  @ingroup bvector
230  */
232  {
233  friend class bvector;
234  public:
236 
237  bool operator==(const iterator_base& it) const
238  {
239  return (position_ == it.position_) && (bv_ == it.bv_);
240  }
241 
242  bool operator!=(const iterator_base& it) const
243  {
244  return ! operator==(it);
245  }
246 
247  bool operator < (const iterator_base& it) const
248  {
249  return position_ < it.position_;
250  }
251 
252  bool operator <= (const iterator_base& it) const
253  {
254  return position_ <= it.position_;
255  }
256 
257  bool operator > (const iterator_base& it) const
258  {
259  return position_ > it.position_;
260  }
261 
262  bool operator >= (const iterator_base& it) const
263  {
264  return position_ >= it.position_;
265  }
266 
267  /**
268  \fn bool bm::bvector::iterator_base::valid() const
269  \brief Checks if iterator is still valid. Analog of != 0 comparison for pointers.
270  \returns true if iterator is valid.
271  */
272  bool valid() const
273  {
274  return position_ != bm::id_max;
275  }
276 
277  /**
278  \fn bool bm::bvector::iterator_base::invalidate()
279  \brief Turns iterator into an invalid state.
280  */
281  void invalidate()
282  {
284  }
285 
286  public:
287 
288  /** Information about current bitblock. */
290  {
291  const bm::word_t* ptr; //!< Word pointer.
292  unsigned bits[32]; //!< Unpacked list of ON bits
293  unsigned idx; //!< Current position in the bit list
294  unsigned cnt; //!< Number of ON bits
295  bm::id_t pos; //!< Last bit position before
296  };
297 
298  /** Information about current DGAP block. */
299  struct dgap_descr
300  {
301  const gap_word_t* ptr; //!< Word pointer.
302  gap_word_t gap_len; //!< Current dgap length.
303  };
304 
305  protected:
306  bm::bvector<Alloc>* bv_; //!< Pointer on parent bitvector
307  bm::id_t position_; //!< Bit position (bit idx)
308  const bm::word_t* block_; //!< Block pointer.(NULL-invalid)
309  unsigned block_type_; //!< Type of block. 0-Bit, 1-GAP
310  unsigned block_idx_; //!< Block index
311 
312  /*! Block type dependent information for current block. */
314  {
315  bitblock_descr bit_; //!< BitBlock related info.
316  dgap_descr gap_; //!< DGAP block related info.
317  } bdescr_;
318  };
319 
320  /*!
321  @brief Output iterator iterator designed to set "ON" bits based on
322  input sequence of integers (bit indeces).
323 
324  STL container can be converted to bvector using this iterator
325  Insert iterator guarantees the vector will be dynamically resized
326  (set_bit does not do that).
327 
328  @note
329  If you have many bits to set it is a good idea to use output iterator
330  instead of explicitly calling set, because iterator may implement
331  some performance specific tricks to make sure bulk insert is fast.
332 
333  @ingroup bvector
334  */
336  {
337  public:
338 #ifndef BM_NO_STL
339  typedef std::output_iterator_tag iterator_category;
340 #endif
341  typedef unsigned value_type;
342  typedef void difference_type;
343  typedef void pointer;
344  typedef void reference;
345 
347  : bvect_(bvect),
348  max_bit_(bvect.size())
349  {
350  }
351 
353  {
354  BM_ASSERT(n < bm::id_max);
355 
356  if (n >= max_bit_)
357  {
358  max_bit_ = n;
359  if (n >= bvect_.size())
360  {
361  bvect_.resize(n + 1);
362  }
363  }
364 
365  bvect_.set(n);
366  return *this;
367  }
368 
369  /*! Returns *this without doing anything (no-op) */
370  insert_iterator& operator*() { return *this; }
371  /*! Returns *this. This iterator does not move (no-op) */
372  insert_iterator& operator++() { return *this; }
373  /*! Returns *this. This iterator does not move (no-op)*/
374  insert_iterator& operator++(int) { return *this; }
375  //private:
376  //insert_iterator(const insert_iterator&);
377  //insert_iterator& operator=(const insert_iterator& );
378 
379  protected:
382  };
383 
384  /*!
385  @brief Constant input iterator designed to enumerate "ON" bits
386  @ingroup bvector
387  */
388  class enumerator : public iterator_base
389  {
390  public:
391 #ifndef BM_NO_STL
392  typedef std::input_iterator_tag iterator_category;
393 #endif
394  typedef unsigned value_type;
395  typedef unsigned difference_type;
396  typedef unsigned* pointer;
397  typedef unsigned& reference;
398 
399  public:
401  enumerator(const bvector<Alloc>* bvect, int position)
402  : iterator_base()
403  {
404  this->bv_ = const_cast<bvector<Alloc>*>(bvect);
405  if (position == 0)
406  {
407  go_first();
408  }
409  else
410  {
411  this->invalidate();
412  }
413  }
414 
416  {
417  return this->position_;
418  }
419 
420  bm::id_t value() const
421  {
422  return this->position_;
423  }
424 
426  {
427  return this->go_up();
428  }
429 
431  {
432  enumerator tmp = *this;
433  this->go_up();
434  return tmp;
435  }
436 
437 
438  void go_first()
439  {
440  BM_ASSERT(this->bv_);
441 
442  #ifdef BMCOUNTOPT
443  if (this->bv_->count_is_valid_ &&
444  this->bv_->count_ == 0)
445  {
446  this->invalidate();
447  return;
448  }
449  #endif
450 
451  blocks_manager_type* bman = &(this->bv_->blockman_);
452  bm::word_t*** blk_root = bman->blocks_root();
453 
454  this->block_idx_ = this->position_= 0;
455  unsigned i, j;
456 
457  for (i = 0; i < bman->top_block_size(); ++i)
458  {
459  bm::word_t** blk_blk = blk_root[i];
460 
461  if (blk_blk == 0) // not allocated
462  {
464  this->position_ += bm::bits_in_array;
465  continue;
466  }
467 
468 
469  for (j = 0; j < bm::set_array_size; ++j,++(this->block_idx_))
470  {
471  this->block_ = blk_blk[j];
472 
473  if (this->block_ == 0)
474  {
475  this->position_ += bits_in_block;
476  continue;
477  }
478 
479  if (BM_IS_GAP(this->block_))
480  {
481  this->block_type_ = 1;
482  if (search_in_gapblock())
483  {
484  return;
485  }
486  }
487  else
488  {
489  this->block_type_ = 0;
490  if (search_in_bitblock())
491  {
492  return;
493  }
494  }
495 
496  } // for j
497 
498  } // for i
499 
500  this->invalidate();
501  }
502 
504  {
505  // Current block search.
506  ++this->position_;
507  typedef typename iterator_base::block_descr block_descr_type;
508 
509  block_descr_type* bdescr = &(this->bdescr_);
510 
511  switch (this->block_type_)
512  {
513  case 0: // BitBlock
514  {
515 
516  // check if we can get the value from the
517  // bits cache
518 
519  unsigned idx = ++(bdescr->bit_.idx);
520  if (idx < bdescr->bit_.cnt)
521  {
522  this->position_ = bdescr->bit_.pos +
523  bdescr->bit_.bits[idx];
524  return *this;
525  }
526  this->position_ += 31 - bdescr->bit_.bits[--idx];
527 
528  const bm::word_t* pend = this->block_ + bm::set_block_size;
529 
530  while (++(bdescr->bit_.ptr) < pend)
531  {
532  bm::word_t w = *(bdescr->bit_.ptr);
533  if (w)
534  {
535  bdescr->bit_.idx = 0;
536  bdescr->bit_.pos = this->position_;
537  bdescr->bit_.cnt = bm::bit_list_4(w, bdescr->bit_.bits);
538  this->position_ += bdescr->bit_.bits[0];
539  return *this;
540  }
541  else
542  {
543  this->position_ += 32;
544  }
545  }
546 
547  }
548  break;
549 
550  case 1: // DGAP Block
551  {
552  if (--(bdescr->gap_.gap_len))
553  {
554  return *this;
555  }
556 
557  // next gap is "OFF" by definition.
558  if (*(bdescr->gap_.ptr) == bm::gap_max_bits - 1)
559  {
560  break;
561  }
562  gap_word_t prev = *(bdescr->gap_.ptr);
563  unsigned int val = *(++(bdescr->gap_.ptr));
564 
565  this->position_ += val - prev;
566  // next gap is now "ON"
567 
568  if (*(bdescr->gap_.ptr) == bm::gap_max_bits - 1)
569  {
570  break;
571  }
572  prev = *(bdescr->gap_.ptr);
573  val = *(++(bdescr->gap_.ptr));
574  bdescr->gap_.gap_len = (gap_word_t)val - prev;
575  return *this; // next "ON" found;
576  }
577 
578  default:
579  BM_ASSERT(0);
580 
581  } // switch
582 
583 
584  // next bit not present in the current block
585  // keep looking in the next blocks.
586  ++(this->block_idx_);
587  unsigned i = this->block_idx_ >> bm::set_array_shift;
588  unsigned top_block_size = this->bv_->blockman_.top_block_size();
589  for (; i < top_block_size; ++i)
590  {
591  bm::word_t** blk_blk = this->bv_->blockman_.blocks_root()[i];
592  if (blk_blk == 0)
593  {
595  this->position_ += bm::bits_in_array;
596  continue;
597  }
598 
599  unsigned j = this->block_idx_ & bm::set_array_mask;
600 
601  for(; j < bm::set_array_size; ++j, ++(this->block_idx_))
602  {
603  this->block_ = blk_blk[j];
604 
605  if (this->block_ == 0)
606  {
607  this->position_ += bm::bits_in_block;
608  continue;
609  }
610 
611  if (BM_IS_GAP(this->block_))
612  {
613  this->block_type_ = 1;
614  if (search_in_gapblock())
615  {
616  return *this;
617  }
618  }
619  else
620  {
621  this->block_type_ = 0;
622  if (search_in_bitblock())
623  {
624  return *this;
625  }
626  }
627 
628 
629  } // for j
630 
631  } // for i
632 
633 
634  this->invalidate();
635  return *this;
636  }
637 
638 
639  private:
641  {
642  BM_ASSERT(this->block_type_ == 0);
643 
644  typedef typename iterator_base::block_descr block_descr_type;
645  block_descr_type* bdescr = &(this->bdescr_);
646 
647  // now lets find the first bit in block.
648  bdescr->bit_.ptr = this->block_;
649 
650  const word_t* ptr_end = this->block_ + bm::set_block_size;
651 
652  do
653  {
654  register bm::word_t w = *(bdescr->bit_.ptr);
655 
656  if (w)
657  {
658  bdescr->bit_.idx = 0;
659  bdescr->bit_.pos = this->position_;
660  bdescr->bit_.cnt =
661  bm::bit_list_4(w, bdescr->bit_.bits);
662  this->position_ += bdescr->bit_.bits[0];
663 
664  return true;
665  }
666  else
667  {
668  this->position_ += 32;
669  }
670 
671  }
672  while (++(bdescr->bit_.ptr) < ptr_end);
673 
674  return false;
675  }
676 
678  {
679  BM_ASSERT(this->block_type_ == 1);
680 
681  typedef typename iterator_base::block_descr block_descr_type;
682  block_descr_type* bdescr = &(this->bdescr_);
683 
684  bdescr->gap_.ptr = BMGAP_PTR(this->block_);
685  unsigned bitval = *(bdescr->gap_.ptr) & 1;
686 
687  ++(bdescr->gap_.ptr);
688 
689  for (;true;)
690  {
691  register unsigned val = *(bdescr->gap_.ptr);
692 
693  if (bitval)
694  {
695  gap_word_t* first = BMGAP_PTR(this->block_) + 1;
696  if (bdescr->gap_.ptr == first)
697  {
698  bdescr->gap_.gap_len = (gap_word_t)val + 1;
699  }
700  else
701  {
702  bdescr->gap_.gap_len =
703  (gap_word_t)(val - *(bdescr->gap_.ptr-1));
704  }
705 
706  return true;
707  }
708  this->position_ += val + 1;
709 
710  if (val == bm::gap_max_bits - 1)
711  {
712  break;
713  }
714 
715  bitval ^= 1;
716  ++(bdescr->gap_.ptr);
717 
718  }
719 
720  return false;
721  }
722 
723  };
724 
725  /*!
726  @brief Constant input iterator designed to enumerate "ON" bits
727  counted_enumerator keeps bitcount, ie number of ON bits starting
728  from the position 0 in the bit string up to the currently enumerated bit
729 
730  When increment operator called current position is increased by 1.
731 
732  @ingroup bvector
733  */
735  {
736  public:
737 #ifndef BM_NO_STL
738  typedef std::input_iterator_tag iterator_category;
739 #endif
741 
743  : enumerator(en)
744  {
745  if (this->valid())
746  bit_count_ = 1;
747  }
748 
750  {
751  enumerator* me = this;
752  *me = en;
753  if (this->valid())
754  this->bit_count_ = 1;
755  return *this;
756  }
757 
759  {
760  this->go_up();
761  if (this->valid())
762  ++(this->bit_count_);
763  return *this;
764  }
765 
767  {
768  counted_enumerator tmp(*this);
769  this->go_up();
770  if (this->valid())
771  ++bit_count_;
772  return tmp;
773  }
774 
775  /*! @brief Number of bits ON starting from the .
776 
777  Method returns number of ON bits fromn the bit 0 to the current bit
778  For the first bit in bitvector it is 1, for the second 2
779  */
780  bm::id_t count() const { return bit_count_; }
781 
782  private:
784  };
785 
786  friend class iterator_base;
787  friend class enumerator;
788 
789 public:
790 
791 #ifdef BMCOUNTOPT
792  bvector(strategy strat = BM_BIT,
793  const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
794  size_type bv_size = bm::id_max,
795  const Alloc& alloc = Alloc())
796  : count_(0),
797  count_is_valid_(true),
798  blockman_(glevel_len, bv_size, alloc),
799  new_blocks_strat_(strat),
800  size_(bv_size)
801  {}
802 
803  bvector(size_type bv_size,
804  bm::strategy strat = BM_BIT,
805  const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
806  const Alloc& alloc = Alloc())
807  : count_(0),
808  count_is_valid_(true),
809  blockman_(glevel_len, bv_size, alloc),
810  new_blocks_strat_(strat),
811  size_(bv_size)
812  {}
813 
814 
816  : count_(bvect.count_),
817  count_is_valid_(bvect.count_is_valid_),
818  blockman_(bvect.blockman_),
820  size_(bvect.size_)
821  {}
822 
823 #else
824  /*!
825  \brief Constructs bvector class
826  \param strat - operation mode strategy,
827  BM_BIT - default strategy, bvector use plain bitset
828  blocks, (performance oriented strategy).
829  BM_GAP - memory effitent strategy, bvector allocates
830  blocks as array of intervals(gaps) and convert blocks
831  into plain bitsets only when enthropy grows.
832  \param glevel_len
833  - pointer on C-style array keeping GAP block sizes.
834  (Put bm::gap_len_table_min<true>::_len for GAP memory saving mode)
835  \param bv_size
836  - bvector size (number of bits addressable by bvector), bm::id_max means
837  "no limits" (recommended).
838  bit vector allocates this space dynamically on demand.
839 
840  \sa bm::gap_len_table bm::gap_len_table_min set_new_blocks_strat
841  */
843  const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
844  size_type bv_size = bm::id_max,
845  const Alloc& alloc = Alloc())
846  : blockman_(glevel_len, bv_size, alloc),
847  new_blocks_strat_(strat),
848  size_(bv_size)
849  {}
850 
851  /*!
852  \brief Constructs bvector class
853  */
854  bvector(size_type bv_size,
855  strategy strat = BM_BIT,
856  const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
857  const Alloc& alloc = Alloc())
858  : blockman_(glevel_len, bv_size, alloc),
859  new_blocks_strat_(strat),
860  size_(bv_size)
861  {}
862 
863 
865  : blockman_(bvect.blockman_),
867  size_(bvect.size_)
868  {}
869 
870 #endif
871 
873  {
874  clear(true); // memory free cleaning
875  resize(bvect.size());
876  bit_or(bvect);
877  return *this;
878  }
879 
880  reference operator[](bm::id_t n)
881  {
882  BM_ASSERT(n < size_);
883  return reference(*this, n);
884  }
885 
886 
887  bool operator[](bm::id_t n) const
888  {
889  BM_ASSERT(n < size_);
890  return get_bit(n);
891  }
892 
894  {
895  bit_and(bvect);
896  }
897 
899  {
900  bit_xor(bvect);
901  }
902 
904  {
905  bit_or(bvect);
906  }
907 
909  {
910  bit_sub(bvect);
911  }
912 
913  bool operator < (const bvector<Alloc>& bvect) const
914  {
915  return compare(bvect) < 0;
916  }
917 
918  bool operator <= (const bvector<Alloc>& bvect) const
919  {
920  return compare(bvect) <= 0;
921  }
922 
923  bool operator > (const bvector<Alloc>& bvect) const
924  {
925  return compare(bvect) > 0;
926  }
927 
928  bool operator >= (const bvector<Alloc>& bvect) const
929  {
930  return compare(bvect) >= 0;
931  }
932 
933  bool operator == (const bvector<Alloc>& bvect) const
934  {
935  return compare(bvect) == 0;
936  }
937 
938  bool operator != (const bvector<Alloc>& bvect) const
939  {
940  return compare(bvect) != 0;
941  }
942 
944  {
945  return bvector<Alloc>(*this).invert();
946  }
947 
949  {
950  return blockman_.get_allocator();
951  }
952 
953 
954  /*!
955  \brief Sets bit n.
956  \param n - index of the bit to be set.
957  \param val - new bit value
958  \return TRUE if bit was changed
959  */
960  bool set_bit(bm::id_t n, bool val = true)
961  {
962  BM_ASSERT(n < size_);
963  return set_bit_no_check(n, val);
964  }
965 
966  /*!
967  \brief Sets bit n using bit AND with the provided value.
968  \param n - index of the bit to be set.
969  \param val - new bit value
970  \return TRUE if bit was changed
971  */
972  bool set_bit_and(bm::id_t n, bool val = true)
973  {
974  BM_ASSERT(n < size_);
975  return and_bit_no_check(n, val);
976  }
977 
978  /*!
979  \brief Sets bit n only if current value is equal to the condition
980  \param n - index of the bit to be set.
981  \param val - new bit value
982  \param condition - expected current value
983  \return TRUE if bit was changed
984  */
985  bool set_bit_conditional(bm::id_t n, bool val, bool condition)
986  {
987  BM_ASSERT(n < size_);
988  if (val == condition) return false;
989  return set_bit_conditional_impl(n, val, condition);
990  }
991 
992 
993  /*!
994  \brief Sets bit n if val is true, clears bit n if val is false
995  \param n - index of the bit to be set
996  \param val - new bit value
997  \return *this
998  */
999  bvector<Alloc>& set(bm::id_t n, bool val = true)
1000  {
1001  set_bit(n, val);
1002  return *this;
1003  }
1004 
1005 
1006 
1007  /*!
1008  \brief Sets every bit in this bitset to 1.
1009  \return *this
1010  */
1012  {
1013  BMCOUNT_VALID(false)
1014  set_range(0, size_ - 1, true);
1015  return *this;
1016  }
1017 
1018 
1019  /*!
1020  \brief Sets all bits in the specified closed interval [left,right]
1021  Interval must be inside the bvector's size.
1022  This method DOES NOT resize vector.
1023 
1024  \param left - interval start
1025  \param right - interval end (closed interval)
1026  \param value - value to set interval in
1027 
1028  \return *this
1029  */
1031  bm::id_t right,
1032  bool value = true);
1033 
1034 
1035  /*! Function erturns insert iterator for this bitvector */
1036  insert_iterator inserter()
1037  {
1038  return insert_iterator(*this);
1039  }
1040 
1041 
1042  /*!
1043  \brief Clears bit n.
1044  \param n - bit's index to be cleaned.
1045  */
1047  {
1048  set(n, false);
1049  }
1050 
1051 
1052  /*!
1053  \brief Clears every bit in the bitvector.
1054 
1055  \param free_mem if "true" (default) bvector frees the memory,
1056  otherwise sets blocks to 0.
1057  */
1058  void clear(bool free_mem = false)
1059  {
1060  blockman_.set_all_zero(free_mem);
1061  BMCOUNT_SET(0);
1062  }
1063 
1064  /*!
1065  \brief Clears every bit in the bitvector.
1066  \return *this;
1067  */
1069  {
1070  clear();
1071  return *this;
1072  }
1073 
1074 
1075  /*!
1076  \brief Returns count of bits which are 1.
1077  \return Total number of bits ON.
1078  */
1079  bm::id_t count() const;
1080 
1081  /**
1082  \brief Returns bvector's capacity (number of bits it can store)
1083  */
1084  size_type capacity() const
1085  {
1086  return blockman_.capacity();
1087  }
1088 
1089  /*!
1090  \brief return current size of the vector (bits)
1091  */
1092  size_type size() const
1093  {
1094  return size_;
1095  }
1096 
1097  /*!
1098  \brief Change size of the bvector
1099  \param new_size - new size in bits
1100  */
1101  void resize(size_type new_size);
1102 
1103  /*! \brief Computes bitcount values for all bvector blocks
1104  \param arr - pointer on array of block bit counts
1105  \return Index of the last block counted.
1106  This number +1 gives you number of arr elements initialized during the
1107  function call.
1108  */
1109  unsigned count_blocks(unsigned* arr) const
1110  {
1111  bm::word_t*** blk_root = blockman_.get_rootblock();
1112  typename blocks_manager_type::block_count_arr_func func(blockman_, &(arr[0]));
1114  func);
1115  return func.last_block();
1116  }
1117 
1118  /*!
1119  \brief Returns count of 1 bits in the given diapason.
1120  \param left - index of first bit start counting from
1121  \param right - index of last bit
1122  \param block_count_arr - optional parameter (bitcount by bvector blocks)
1123  calculated by count_blocks method. Used to improve performance of
1124  wide range searches
1125  \return Total number of bits ON.
1126  */
1128  bm::id_t right,
1129  unsigned* block_count_arr=0) const;
1130 
1131 
1133  {
1134  BMCOUNT_VALID(false)
1135  return count();
1136  }
1137 
1138  /*!
1139  Disables count cache. Next call to count() or recalc_count()
1140  restores count caching.
1141 
1142  @note Works only if BMCOUNTOPT enabled(defined).
1143  Othewise does nothing.
1144  */
1146  {
1147  BMCOUNT_VALID(false)
1148  }
1149 
1150  /*!
1151  \brief Inverts all bits.
1152  */
1154 
1155 
1156  /*!
1157  \brief returns true if bit n is set and false is bit n is 0.
1158  \param n - Index of the bit to check.
1159  \return Bit value (1 or 0)
1160  */
1161  bool get_bit(bm::id_t n) const;
1162 
1163  /*!
1164  \brief returns true if bit n is set and false is bit n is 0.
1165  \param n - Index of the bit to check.
1166  \return Bit value (1 or 0)
1167  */
1168  bool test(bm::id_t n) const
1169  {
1170  return get_bit(n);
1171  }
1172 
1173  /*!
1174  \brief Returns true if any bits in this bitset are set, and otherwise returns false.
1175  \return true if any bit is set
1176  */
1177  bool any() const
1178  {
1179  #ifdef BMCOUNTOPT
1180  if (count_is_valid_)
1181  return count_ != 0;
1182  #endif
1183 
1184  word_t*** blk_root = blockman_.get_rootblock();
1185  if (!blk_root)
1186  return false;
1187  typename blocks_manager_type::block_any_func func(blockman_);
1188  return for_each_nzblock_if(blk_root,
1190  func);
1191  }
1192 
1193  /*!
1194  \brief Returns true if no bits are set, otherwise returns false.
1195  */
1196  bool none() const
1197  {
1198  return !any();
1199  }
1200 
1201  /*!
1202  \brief Flips bit n
1203  \return *this
1204  */
1206  {
1207  set(n, !get_bit(n));
1208  return *this;
1209  }
1210 
1211  /*!
1212  \brief Flips all bits
1213  \return *this
1214  */
1216  {
1217  return invert();
1218  }
1219 
1220  /*! \brief Exchanges content of bv and this bitvector.
1221  */
1223  {
1224  if (this != &bv)
1225  {
1226  blockman_.swap(bv.blockman_);
1227  bm::xor_swap(size_,bv.size_);
1228  #ifdef BMCOUNTOPT
1229  BMCOUNT_VALID(false)
1230  bv.recalc_count();
1231  #endif
1232  }
1233  }
1234 
1235 
1236  /*!
1237  \fn bm::id_t bvector::get_first() const
1238  \brief Gets number of first bit which is ON.
1239  \return Index of the first 1 bit.
1240  \sa get_next, extract_next
1241  */
1242  bm::id_t get_first() const { return check_or_next(0); }
1243 
1244  /*!
1245  \fn bm::id_t bvector::get_next(bm::id_t prev) const
1246  \brief Finds the number of the next bit ON.
1247  \param prev - Index of the previously found bit.
1248  \return Index of the next bit which is ON or 0 if not found.
1249  \sa get_first, extract_next
1250  */
1252  {
1253  return (++prev == bm::id_max) ? 0 : check_or_next(prev);
1254  }
1255 
1256  /*!
1257  \fn bm::id_t bvector::extract_next(bm::id_t prev)
1258  \brief Finds the number of the next bit ON and sets it to 0.
1259  \param prev - Index of the previously found bit.
1260  \return Index of the next bit which is ON or 0 if not found.
1261  \sa get_first, get_next,
1262  */
1264  {
1265  return (++prev == bm::id_max) ? 0 : check_or_next_extract(prev);
1266  }
1267 
1268 
1269  /*!
1270  @brief Calculates bitvector statistics.
1271 
1272  @param st - pointer on statistics structure to be filled in.
1273 
1274  Function fills statistics structure containing information about how
1275  this vector uses memory and estimation of max. amount of memory
1276  bvector needs to serialize itself.
1277 
1278  @sa statistics
1279  */
1280  void calc_stat(struct bm::bvector<Alloc>::statistics* st) const;
1281 
1282  /*!
1283  \brief Logical OR operation.
1284  \param vect - Argument vector.
1285  */
1287  {
1288  BMCOUNT_VALID(false);
1289  combine_operation(vect, BM_OR);
1290  return *this;
1291  }
1292 
1293  /*!
1294  \brief Logical AND operation.
1295  \param vect - Argument vector.
1296  */
1298  {
1299  BMCOUNT_VALID(false);
1300  combine_operation(vect, BM_AND);
1301  return *this;
1302  }
1303 
1304  /*!
1305  \brief Logical XOR operation.
1306  \param vect - Argument vector.
1307  */
1309  {
1310  BMCOUNT_VALID(false);
1311  combine_operation(vect, BM_XOR);
1312  return *this;
1313  }
1314 
1315  /*!
1316  \brief Logical SUB operation.
1317  \param vect - Argument vector.
1318  */
1320  {
1321  BMCOUNT_VALID(false);
1322  combine_operation(vect, BM_SUB);
1323  return *this;
1324  }
1325 
1326 
1327  /*!
1328  \brief Sets new blocks allocation strategy.
1329  \param strat - Strategy code 0 - bitblocks allocation only.
1330  1 - Blocks mutation mode (adaptive algorithm)
1331  */
1333  {
1334  new_blocks_strat_ = strat;
1335  }
1336 
1337  /*!
1338  \brief Returns blocks allocation strategy.
1339  \return - Strategy code 0 - bitblocks allocation only.
1340  1 - Blocks mutation mode (adaptive algorithm)
1341  \sa set_new_blocks_strat
1342  */
1344  {
1345  return new_blocks_strat_;
1346  }
1347 
1348 
1349  /*!
1350  \brief Optimization mode
1351  Every next level means additional checks (better compression vs time)
1352  \sa optimize
1353  */
1354  enum optmode
1355  {
1356  opt_free_0 = 1, ///< Free unused 0 blocks
1357  opt_free_01 = 2, ///< Free unused 0 and 1 blocks
1358  opt_compress = 3 ///< compress blocks when possible
1359  };
1360 
1361  /*!
1362  \brief Optimize memory bitvector's memory allocation.
1363 
1364  Function analyze all blocks in the bitvector, compresses blocks
1365  with a regular structure, frees some memory. This function is recommended
1366  after a bulk modification of the bitvector using set_bit, clear_bit or
1367  logical operations.
1368 
1369  Optionally function can calculate vector post optimization statistics
1370 
1371  @sa optmode, optimize_gap_size
1372  */
1373  void optimize(bm::word_t* temp_block = 0,
1374  optmode opt_mode = opt_compress,
1375  statistics* stat = 0);
1376 
1377  /*!
1378  \brief Optimize sizes of GAP blocks
1379 
1380  This method runs an analysis to find optimal GAP levels for the
1381  specific vector. Current GAP compression algorithm uses several fixed
1382  GAP sizes. By default bvector uses some reasonable preset.
1383  */
1384  void optimize_gap_size();
1385 
1386 
1387  /*!
1388  @brief Sets new GAP lengths table. All GAP blocks will be reallocated
1389  to match the new scheme.
1390 
1391  @param glevel_len - pointer on C-style array keeping GAP block sizes.
1392  */
1393  void set_gap_levels(const gap_word_t* glevel_len);
1394 
1395  /*!
1396  \brief Lexicographical comparison with a bitvector.
1397 
1398  Function compares current bitvector with the provided argument
1399  bit by bit and returns -1 if our bitvector less than the argument,
1400  1 - greater, 0 - equal.
1401  */
1402  int compare(const bvector<Alloc>& bvect) const;
1403 
1404  /*! @brief Allocates temporary block of memory.
1405 
1406  Temp block can be passed to bvector functions requiring some temp memory
1407  for their operation. (like serialize)
1408 
1409  @note method is marked const, but it's not quite true, since
1410  it can in some cases modify the state of the block allocator
1411  (if it has a state). (Can be important in MT programs).
1412 
1413  @sa free_tempblock
1414  */
1416  {
1417  blocks_manager_type* bm =
1418  const_cast<blocks_manager_type*>(&blockman_);
1419  return bm->get_allocator().alloc_bit_block();
1420  }
1421 
1422  /*! @brief Frees temporary block of memory.
1423 
1424  @note method is marked const, but it's not quite true, since
1425  it can in some cases modify the state of the block allocator
1426  (if it has a state). (Can be important in MT programs).
1427 
1428  @sa allocate_tempblock
1429  */
1430  void free_tempblock(bm::word_t* block) const
1431  {
1432  blocks_manager_type* bm =
1433  const_cast<blocks_manager_type*>(&blockman_);
1434  bm->get_allocator().free_bit_block(block);
1435  }
1436 
1437  /**
1438  \brief Returns enumerator pointing on the first non-zero bit.
1439  */
1441  {
1442  typedef typename bvector<Alloc>::enumerator enumerator_type;
1443  return enumerator_type(this, 0);
1444  }
1445 
1446  /**
1447  \fn bvector::enumerator bvector::end() const
1448  \brief Returns enumerator pointing on the next bit after the last.
1449  */
1450  enumerator end() const
1451  {
1452  typedef typename bvector<Alloc>::enumerator enumerator_type;
1453  return enumerator_type(this, 1);
1454  }
1455 
1456 
1457  const bm::word_t* get_block(unsigned nb) const
1458  {
1459  return blockman_.get_block(nb);
1460  }
1461 
1463  bm::operation opcode);
1464 
1465 private:
1466 
1467  bm::id_t check_or_next(bm::id_t prev) const;
1468 
1469  /// check if specified bit is 1, and set it to 0
1470  /// if specified bit is 0, scan for the next 1 and returns it
1471  /// if no 1 found returns 0
1473 
1474  /**
1475  \brief Set specified bit without checking preconditions (size, etc)
1476  */
1477  bool set_bit_no_check(bm::id_t n, bool val);
1478 
1479  /**
1480  \brief AND specified bit without checking preconditions (size, etc)
1481  */
1482  bool and_bit_no_check(bm::id_t n, bool val);
1483 
1484  bool set_bit_conditional_impl(bm::id_t n, bool val, bool condition);
1485 
1486 
1487  void combine_operation_with_block(unsigned nb,
1488  bool gap,
1489  bm::word_t* blk,
1490  const bm::word_t* arg_blk,
1491  bool arg_gap,
1492  bm::operation opcode);
1493 public:
1495  const bm::word_t* arg_blk,
1496  bool arg_gap,
1497  bm::operation opcode)
1498  {
1499  bm::word_t* blk = const_cast<bm::word_t*>(get_block(nb));
1500  bool gap = BM_IS_GAP(blk);
1501  combine_operation_with_block(nb, gap, blk, arg_blk, arg_gap, opcode);
1502  }
1503 private:
1504 #if 0 // unused, needs non-existent 6-arg variant
1505  void combine_count_operation_with_block(unsigned nb,
1506  const bm::word_t* arg_blk,
1507  int arg_gap,
1508  bm::operation opcode)
1509  {
1510  const bm::word_t* blk = get_block(nb);
1511  bool gap = BM_IS_GAP(blk);
1512  combine_count_operation_with_block(nb, gap, blk, arg_blk, arg_gap, opcode);
1513  }
1514 #endif
1515 
1516 
1517  /**
1518  \brief Extends GAP block to the next level or converts it to bit block.
1519  \param nb - Block's linear index.
1520  \param blk - Blocks's pointer
1521  */
1522  void extend_gap_block(unsigned nb, gap_word_t* blk)
1523  {
1524  blockman_.extend_gap_block(nb, blk);
1525  }
1526 
1527  /**
1528  \brief Set range without validity checking
1529  */
1530  void set_range_no_check(bm::id_t left,
1531  bm::id_t right,
1532  bool value);
1533 public:
1534 
1535  const blocks_manager_type& get_blocks_manager() const
1536  {
1537  return blockman_;
1538  }
1539 
1540  blocks_manager_type& get_blocks_manager()
1541  {
1542  return blockman_;
1543  }
1544 
1545 
1546 private:
1547 
1548 // This block defines two additional hidden variables used for bitcount
1549 // optimization, in rare cases can make bitvector thread unsafe.
1550 #ifdef BMCOUNTOPT
1551  mutable id_t count_; //!< number of 1 bits in the vector
1552  mutable bool count_is_valid_; //!< actualization flag
1553 #endif
1554 
1555  blocks_manager_type blockman_; //!< bitblocks manager
1556  strategy new_blocks_strat_; //!< block allocation strategy
1557  size_type size_; //!< size in bits
1558 };
1559 
1560 
1561 
1562 
1563 
1564 //---------------------------------------------------------------------
1565 
1566 template<class Alloc>
1568  const bvector<Alloc>& v2)
1569 {
1570 #ifdef BM_USE_EXPLICIT_TEMP
1571  bvector<Alloc, MS> ret(v1);
1572  ret.bit_and(v2);
1573  return ret;
1574 #else
1575  return bvector<Alloc>(v1).bit_and(v2);
1576 #endif
1577 }
1578 
1579 //---------------------------------------------------------------------
1580 
1581 template<class Alloc>
1583  const bvector<Alloc>& v2)
1584 {
1585 #ifdef BM_USE_EXPLICIT_TEMP
1586  bvector<Alloc, MS> ret(v1);
1587  ret.bit_or(v2);
1588  return ret;
1589 #else
1590  return bvector<Alloc>(v1).bit_or(v2);
1591 #endif
1592 }
1593 
1594 //---------------------------------------------------------------------
1595 
1596 template<class Alloc>
1598  const bvector<Alloc>& v2)
1599 {
1600 #ifdef BM_USE_EXPLICIT_TEMP
1601  bvector<Alloc, MS> ret(v1);
1602  ret.bit_xor(v2);
1603  return ret;
1604 #else
1605  return bvector<Alloc>(v1).bit_xor(v2);
1606 #endif
1607 }
1608 
1609 //---------------------------------------------------------------------
1610 
1611 template<class Alloc>
1613  const bvector<Alloc>& v2)
1614 {
1615 #ifdef BM_USE_EXPLICIT_TEMP
1616  bvector<Alloc, MS> ret(v1);
1617  ret.bit_sub(v2);
1618  return ret;
1619 #else
1620  return bvector<Alloc>(v1).bit_sub(v2);
1621 #endif
1622 }
1623 
1624 
1625 
1626 
1627 // -----------------------------------------------------------------------
1628 
1629 template<typename Alloc>
1631  bm::id_t right,
1632  bool value)
1633 {
1634  if (right < left)
1635  {
1636  return set_range(right, left, value);
1637  }
1638 
1639  BM_ASSERT(left < size_);
1640  BM_ASSERT(right < size_);
1641 
1642  BMCOUNT_VALID(false)
1644 
1645  set_range_no_check(left, right, value);
1646 
1647  return *this;
1648 }
1649 
1650 // -----------------------------------------------------------------------
1651 
1652 template<typename Alloc>
1654 {
1655 #ifdef BMCOUNTOPT
1656  if (count_is_valid_) return count_;
1657 #endif
1658  word_t*** blk_root = blockman_.get_rootblock();
1659  if (!blk_root)
1660  {
1661  BMCOUNT_SET(0);
1662  return 0;
1663  }
1664  typename blocks_manager_type::block_count_func func(blockman_);
1665  for_each_nzblock2(blk_root, blockman_.effective_top_block_size(),
1666  func);
1667 
1668  BMCOUNT_SET(func.count());
1669  return func.count();
1670 }
1671 
1672 // -----------------------------------------------------------------------
1673 
1674 template<typename Alloc>
1675 void bvector<Alloc>::resize(size_type new_size)
1676 {
1677  if (size_ == new_size) return; // nothing to do
1678  if (size_ < new_size) // size grows
1679  {
1680  blockman_.reserve(new_size);
1681  size_ = new_size;
1682  }
1683  else // shrink
1684  {
1685  set_range(new_size, size_ - 1, false); // clear the tail
1686  size_ = new_size;
1687  }
1688 }
1689 
1690 // -----------------------------------------------------------------------
1691 
1692 template<typename Alloc>
1694  bm::id_t right,
1695  unsigned* block_count_arr) const
1696 {
1697  BM_ASSERT(left <= right);
1698 
1699  unsigned count = 0;
1700 
1701  // calculate logical number of start and destination blocks
1702  unsigned nblock_left = unsigned(left >> bm::set_block_shift);
1703  unsigned nblock_right = unsigned(right >> bm::set_block_shift);
1704 
1705  const bm::word_t* block = blockman_.get_block(nblock_left);
1706  bool left_gap = BM_IS_GAP(block);
1707 
1708  unsigned nbit_left = unsigned(left & bm::set_block_mask);
1709  unsigned nbit_right = unsigned(right & bm::set_block_mask);
1710 
1711  unsigned r =
1712  (nblock_left == nblock_right) ? nbit_right : (bm::bits_in_block-1);
1713 
1714  typename blocks_manager_type::block_count_func func(blockman_);
1715 
1716  if (block)
1717  {
1718  if ((nbit_left == 0) && (r == (bm::bits_in_block-1))) // whole block
1719  {
1720  if (block_count_arr)
1721  {
1722  count += block_count_arr[nblock_left];
1723  }
1724  else
1725  {
1726  func(block);//, nblock_left);
1727  }
1728  }
1729  else
1730  {
1731  if (left_gap)
1732  {
1733  count += gap_bit_count_range(BMGAP_PTR(block),
1734  (gap_word_t)nbit_left,
1735  (gap_word_t)r);
1736  }
1737  else
1738  {
1739  count += bit_block_calc_count_range(block, nbit_left, r);
1740  }
1741  }
1742  }
1743 
1744  if (nblock_left == nblock_right) // in one block
1745  {
1746  return count + func.count();
1747  }
1748 
1749  for (unsigned nb = nblock_left+1; nb < nblock_right; ++nb)
1750  {
1751  block = blockman_.get_block(nb);
1752  if (block_count_arr)
1753  {
1754  count += block_count_arr[nb];
1755  }
1756  else
1757  {
1758  if (block)
1759  func(block);
1760  }
1761  }
1762  count += func.count();
1763 
1764  block = blockman_.get_block(nblock_right);
1765  bool right_gap = BM_IS_GAP(block);
1766 
1767  if (block)
1768  {
1769  if (right_gap)
1770  {
1771  count += gap_bit_count_range(BMGAP_PTR(block),
1772  (gap_word_t)0,
1773  (gap_word_t)nbit_right);
1774  }
1775  else
1776  {
1777  count += bit_block_calc_count_range(block, 0, nbit_right);
1778  }
1779  }
1780 
1781  return count;
1782 }
1783 
1784 // -----------------------------------------------------------------------
1785 
1786 template<typename Alloc>
1788 {
1789  BMCOUNT_VALID(false)
1791 
1792  bm::word_t*** blk_root = blockman_.get_rootblock();
1793  typename blocks_manager_type::block_invert_func func(blockman_);
1794  for_each_block(blk_root, blockman_.top_block_size(), func);
1795  if (size_ == bm::id_max)
1796  {
1797  set_bit_no_check(bm::id_max, false);
1798  }
1799  else
1800  {
1801  set_range_no_check(size_, bm::id_max, false);
1802  }
1803 
1804  return *this;
1805 }
1806 
1807 // -----------------------------------------------------------------------
1808 
1809 template<typename Alloc>
1811 {
1812  BM_ASSERT(n < size_);
1813 
1814  // calculate logical block number
1815  unsigned nblock = unsigned(n >> bm::set_block_shift);
1816 
1817  const bm::word_t* block = blockman_.get_block(nblock);
1818 
1819  if (block)
1820  {
1821  // calculate word number in block and bit
1822  unsigned nbit = unsigned(n & bm::set_block_mask);
1823  unsigned is_set;
1824 
1825  if (BM_IS_GAP(block))
1826  {
1827  is_set = gap_test(BMGAP_PTR(block), nbit);
1828  }
1829  else
1830  {
1831  unsigned nword = unsigned(nbit >> bm::set_word_shift);
1832  nbit &= bm::set_word_mask;
1833 
1834  is_set = (block[nword] & (((bm::word_t)1) << nbit));
1835  }
1836  return is_set != 0;
1837  }
1838  return false;
1839 }
1840 
1841 // -----------------------------------------------------------------------
1842 
1843 template<typename Alloc>
1845  optmode opt_mode,
1846  statistics* stat)
1847 {
1848  word_t*** blk_root = blockman_.blocks_root();
1849 
1850  if (!temp_block)
1851  temp_block = blockman_.check_allocate_tempblock();
1852 
1853  typename
1854  blocks_manager_type::block_opt_func opt_func(blockman_,
1855  temp_block,
1856  (int)opt_mode,
1857  stat);
1858  if (stat)
1859  {
1860  stat->bit_blocks = stat->gap_blocks
1861  = stat->max_serialize_mem
1862  = stat->memory_used
1863  = 0;
1864  ::memcpy(stat->gap_levels,
1865  blockman_.glen(), sizeof(gap_word_t) * bm::gap_levels);
1866  stat->max_serialize_mem = sizeof(id_t) * 4;
1867 
1868  }
1869 
1870  for_each_nzblock(blk_root, blockman_.effective_top_block_size(),
1871  opt_func);
1872 
1873  if (stat)
1874  {
1875  unsigned safe_inc = stat->max_serialize_mem / 10; // 10% increment
1876  if (!safe_inc) safe_inc = 256;
1877  stat->max_serialize_mem += safe_inc;
1878  stat->memory_used += sizeof(*this) - sizeof(blockman_);
1879  stat->memory_used += blockman_.mem_used();
1880  }
1881 }
1882 
1883 // -----------------------------------------------------------------------
1884 
1885 template<typename Alloc>
1887 {
1888  struct bvector<Alloc>::statistics st;
1889  calc_stat(&st);
1890 
1891  if (!st.gap_blocks)
1892  return;
1893 
1894  gap_word_t opt_glen[bm::gap_levels];
1895  ::memcpy(opt_glen, st.gap_levels, bm::gap_levels * sizeof(*opt_glen));
1896 
1897  improve_gap_levels(st.gap_length,
1898  st.gap_length + st.gap_blocks,
1899  opt_glen);
1900 
1901  set_gap_levels(opt_glen);
1902 }
1903 
1904 // -----------------------------------------------------------------------
1905 
1906 template<typename Alloc>
1907 void bvector<Alloc>::set_gap_levels(const gap_word_t* glevel_len)
1908 {
1909  word_t*** blk_root = blockman_.blocks_root();
1910  typename
1911  blocks_manager_type::gap_level_func gl_func(blockman_, glevel_len);
1912  for_each_nzblock(blk_root, blockman_.top_block_size(),gl_func);
1913 
1914  blockman_.set_glen(glevel_len);
1915 }
1916 
1917 // -----------------------------------------------------------------------
1918 
1919 template<typename Alloc>
1921 {
1922  int res;
1923  unsigned bn = 0;
1924 
1925  unsigned top_blocks = blockman_.effective_top_block_size();
1926  unsigned bvect_top_blocks = bvect.blockman_.effective_top_block_size();
1927 
1928  if (bvect_top_blocks > top_blocks) top_blocks = bvect_top_blocks;
1929 
1930  for (unsigned i = 0; i < top_blocks; ++i)
1931  {
1932  const bm::word_t* const* blk_blk = blockman_.get_topblock(i);
1933  const bm::word_t* const* arg_blk_blk =
1934  bvect.blockman_.get_topblock(i);
1935 
1936  if (blk_blk == arg_blk_blk)
1937  {
1938  bn += bm::set_array_size;
1939  continue;
1940  }
1941 
1942  for (unsigned j = 0; j < bm::set_array_size; ++j, ++bn)
1943  {
1944  const bm::word_t* arg_blk = arg_blk_blk ? arg_blk_blk[j] : 0;
1945  const bm::word_t* blk = blk_blk ? blk_blk[j] : 0;
1946  if (blk == arg_blk) continue;
1947 
1948  // If one block is zero we check if the other one has at least
1949  // one bit ON
1950 
1951  if (!blk || !arg_blk)
1952  {
1953  const bm::word_t* pblk;
1954  bool is_gap;
1955 
1956  if (blk)
1957  {
1958  pblk = blk;
1959  res = 1;
1960  is_gap = BM_IS_GAP(blk);
1961  }
1962  else
1963  {
1964  pblk = arg_blk;
1965  res = -1;
1966  is_gap = BM_IS_GAP(arg_blk);
1967  }
1968 
1969  if (is_gap)
1970  {
1972  {
1973  return res;
1974  }
1975  }
1976  else
1977  {
1978  bm::wordop_t* blk1 = (wordop_t*)pblk;
1979  bm::wordop_t* blk2 =
1980  (wordop_t*)(pblk + bm::set_block_size);
1981  if (!bit_is_all_zero(blk1, blk2))
1982  {
1983  return res;
1984  }
1985  }
1986 
1987  continue;
1988  }
1989 
1990  bool arg_gap = BM_IS_GAP(arg_blk);
1991  bool gap = BM_IS_GAP(blk);
1992 
1993  if (arg_gap != gap)
1994  {
1996  bm::wordop_t* blk1;
1997  bm::wordop_t* blk2;
1998 
1999  if (gap)
2000  {
2001  gap_convert_to_bitset((bm::word_t*)temp_blk,
2002  BMGAP_PTR(blk));
2003 
2004  blk1 = (bm::wordop_t*)temp_blk;
2005  blk2 = (bm::wordop_t*)arg_blk;
2006  }
2007  else
2008  {
2009  gap_convert_to_bitset((bm::word_t*)temp_blk,
2010  BMGAP_PTR(arg_blk));
2011 
2012  blk1 = (bm::wordop_t*)blk;
2013  blk2 = (bm::wordop_t*)temp_blk;
2014 
2015  }
2016  res = bitcmp(blk1, blk2, bm::set_block_size_op);
2017 
2018  }
2019  else
2020  {
2021  if (gap)
2022  {
2023  res = gapcmp(BMGAP_PTR(blk), BMGAP_PTR(arg_blk));
2024  }
2025  else
2026  {
2027  res = bitcmp((bm::wordop_t*)blk,
2028  (bm::wordop_t*)arg_blk,
2030  }
2031  }
2032 
2033  if (res != 0)
2034  {
2035  return res;
2036  }
2037 
2038 
2039  } // for j
2040 
2041  } // for i
2042 
2043  return 0;
2044 }
2045 
2046 
2047 // -----------------------------------------------------------------------
2048 
2049 template<typename Alloc>
2051 {
2052  st->bit_blocks = st->gap_blocks
2053  = st->max_serialize_mem
2054  = st->memory_used = 0;
2055 
2056  ::memcpy(st->gap_levels,
2057  blockman_.glen(), sizeof(gap_word_t) * bm::gap_levels);
2058 
2059  unsigned empty_blocks = 0;
2060  unsigned blocks_memory = 0;
2061  gap_word_t* gapl_ptr = st->gap_length;
2062 
2063  st->max_serialize_mem = sizeof(id_t) * 4;
2064 
2065  unsigned block_idx = 0;
2066 
2067  unsigned top_size = blockman_.effective_top_block_size();
2068  // Walk the blocks, calculate statistics.
2069  for (unsigned i = 0; i < top_size; ++i)
2070  {
2071  const bm::word_t* const* blk_blk = blockman_.get_topblock(i);
2072 
2073  if (!blk_blk)
2074  {
2075  block_idx += bm::set_array_size;
2076  st->max_serialize_mem += sizeof(unsigned) + 1;
2077  continue;
2078  }
2079 
2080  for (unsigned j = 0;j < bm::set_array_size; ++j, ++block_idx)
2081  {
2082  const bm::word_t* blk = blk_blk[j];
2083  if (IS_VALID_ADDR(blk))
2084  {
2085  st->max_serialize_mem += empty_blocks << 2;
2086  empty_blocks = 0;
2087 
2088  if (BM_IS_GAP(blk))
2089  {
2090  ++(st->gap_blocks);
2091 
2092  bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
2093 
2094  unsigned mem_used =
2095  bm::gap_capacity(gap_blk, blockman_.glen())
2096  * sizeof(gap_word_t);
2097 
2098  *gapl_ptr = gap_length(gap_blk);
2099 
2100  st->max_serialize_mem += *gapl_ptr * sizeof(gap_word_t);
2101  blocks_memory += mem_used;
2102 
2103  ++gapl_ptr;
2104  }
2105  else // bit block
2106  {
2107  ++(st->bit_blocks);
2108  unsigned mem_used = sizeof(bm::word_t) * bm::set_block_size;
2109  st->max_serialize_mem += mem_used;
2110  blocks_memory += mem_used;
2111  }
2112  }
2113  else
2114  {
2115  ++empty_blocks;
2116  }
2117  }
2118  }
2119 
2120  unsigned safe_inc = st->max_serialize_mem / 10; // 10% increment
2121  if (!safe_inc) safe_inc = 256;
2122  st->max_serialize_mem += safe_inc;
2123 
2124  // Calc size of different odd and temporary things.
2125 
2126  st->memory_used += sizeof(*this) - sizeof(blockman_);
2127  st->memory_used += blockman_.mem_used();
2128  st->memory_used += blocks_memory;
2129 }
2130 
2131 
2132 // -----------------------------------------------------------------------
2133 
2134 
2135 template<class Alloc>
2137 {
2138  // calculate logical block number
2139  unsigned nblock = unsigned(n >> bm::set_block_shift);
2140 
2141  int block_type;
2142 
2143  bm::word_t* blk =
2144  blockman_.check_allocate_block(nblock,
2145  val,
2146  get_new_blocks_strat(),
2147  &block_type);
2148 
2149  if (!blk) return false;
2150 
2151  // calculate word number in block and bit
2152  unsigned nbit = unsigned(n & bm::set_block_mask);
2153 
2154  if (block_type == 1) // gap
2155  {
2156  unsigned is_set;
2157  unsigned new_block_len;
2158 
2159  new_block_len =
2160  gap_set_value(val, BMGAP_PTR(blk), nbit, &is_set);
2161  if (is_set)
2162  {
2163  BMCOUNT_ADJ(val)
2164 
2165  unsigned threshold =
2166  bm::gap_limit(BMGAP_PTR(blk), blockman_.glen());
2167 
2168  if (new_block_len > threshold)
2169  {
2170  extend_gap_block(nblock, BMGAP_PTR(blk));
2171  }
2172  return true;
2173  }
2174  }
2175  else // bit block
2176  {
2177  unsigned nword = unsigned(nbit >> bm::set_word_shift);
2178  nbit &= bm::set_word_mask;
2179 
2180  bm::word_t* word = blk + nword;
2181  bm::word_t mask = (((bm::word_t)1) << nbit);
2182 
2183  if (val)
2184  {
2185  if ( ((*word) & mask) == 0 )
2186  {
2187  *word |= mask; // set bit
2188  BMCOUNT_INC;
2189  return true;
2190  }
2191  }
2192  else
2193  {
2194  if ((*word) & mask)
2195  {
2196  *word &= ~mask; // clear bit
2197  BMCOUNT_DEC;
2198  return true;
2199  }
2200  }
2201  }
2202  return false;
2203 }
2204 
2205 // -----------------------------------------------------------------------
2206 
2207 template<class Alloc>
2209  bool val,
2210  bool condition)
2211 {
2212  // calculate logical block number
2213  unsigned nblock = unsigned(n >> bm::set_block_shift);
2214 
2215  int block_type;
2216  bm::word_t* blk =
2217  blockman_.check_allocate_block(nblock,
2218  val,
2219  get_new_blocks_strat(),
2220  &block_type);
2221  if (!blk)
2222  return false;
2223 
2224  // calculate word number in block and bit
2225  unsigned nbit = unsigned(n & bm::set_block_mask);
2226 
2227  if (block_type == 1) // gap
2228  {
2229  bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
2230  bool old_val = (gap_test(gap_blk, nbit) != 0);
2231 
2232  if (old_val != condition)
2233  {
2234  return false;
2235  }
2236 
2237  if (val != old_val)
2238  {
2239  unsigned is_set;
2240  unsigned new_block_len =
2241  gap_set_value(val, gap_blk, nbit, &is_set);
2242  BM_ASSERT(is_set);
2243  BMCOUNT_ADJ(val)
2244 
2245  unsigned threshold =
2246  bm::gap_limit(gap_blk, blockman_.glen());
2247  if (new_block_len > threshold)
2248  {
2249  extend_gap_block(nblock, gap_blk);
2250  }
2251  return true;
2252  }
2253  }
2254  else // bit block
2255  {
2256  unsigned nword = unsigned(nbit >> bm::set_word_shift);
2257  nbit &= bm::set_word_mask;
2258 
2259  bm::word_t* word = blk + nword;
2260  bm::word_t mask = (((bm::word_t)1) << nbit);
2261  bool is_set = ((*word) & mask) != 0;
2262 
2263  if (is_set != condition)
2264  {
2265  return false;
2266  }
2267  if (is_set != val) // need to change bit
2268  {
2269  if (val) // set bit
2270  {
2271  *word |= mask;
2272  BMCOUNT_INC;
2273  }
2274  else // clear bit
2275  {
2276  *word &= ~mask;
2277  BMCOUNT_DEC;
2278  }
2279  return true;
2280  }
2281  }
2282  return false;
2283 
2284 }
2285 
2286 // -----------------------------------------------------------------------
2287 
2288 
2289 template<class Alloc>
2291 {
2292  // calculate logical block number
2293  unsigned nblock = unsigned(n >> bm::set_block_shift);
2294 
2295  int block_type;
2296  bm::word_t* blk =
2297  blockman_.check_allocate_block(nblock,
2298  val,
2299  get_new_blocks_strat(),
2300  &block_type);
2301  if (!blk) return false;
2302 
2303  // calculate word number in block and bit
2304  unsigned nbit = unsigned(n & bm::set_block_mask);
2305 
2306  if (block_type == 1) // gap
2307  {
2308  bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
2309  bool old_val = (gap_test(gap_blk, nbit) != 0);
2310 
2311  bool new_val = val & old_val;
2312  if (new_val != old_val)
2313  {
2314  unsigned is_set;
2315  unsigned new_block_len =
2316  gap_set_value(new_val, gap_blk, nbit, &is_set);
2317  BM_ASSERT(is_set);
2318  BMCOUNT_ADJ(val)
2319 
2320  unsigned threshold =
2321  bm::gap_limit(gap_blk, blockman_.glen());
2322  if (new_block_len > threshold)
2323  {
2324  extend_gap_block(nblock, gap_blk);
2325  }
2326  return true;
2327  }
2328  }
2329  else // bit block
2330  {
2331  unsigned nword = unsigned(nbit >> bm::set_word_shift);
2332  nbit &= bm::set_word_mask;
2333 
2334  bm::word_t* word = blk + nword;
2335  bm::word_t mask = (((bm::word_t)1) << nbit);
2336  bool is_set = ((*word) & mask) != 0;
2337 
2338  bool new_val = is_set & val;
2339  if (new_val != val) // need to change bit
2340  {
2341  if (new_val) // set bit
2342  {
2343  *word |= mask;
2344  BMCOUNT_INC;
2345  }
2346  else // clear bit
2347  {
2348  *word &= ~mask;
2349  BMCOUNT_DEC;
2350  }
2351  return true;
2352  }
2353  }
2354  return false;
2355 }
2356 
2357 
2358 //---------------------------------------------------------------------
2359 
2360 template<class Alloc>
2362 {
2363  for (;;)
2364  {
2365  unsigned nblock = unsigned(prev >> bm::set_block_shift);
2366  if (nblock >= bm::set_total_blocks)
2367  break;
2368 
2369  if (blockman_.is_subblock_null(nblock >> bm::set_array_shift))
2370  {
2371  prev += (bm::set_blkblk_mask + 1) -
2372  (prev & bm::set_blkblk_mask);
2373  }
2374  else
2375  {
2376  unsigned nbit = unsigned(prev & bm::set_block_mask);
2377  int no_more_blocks;
2378  const bm::word_t* block =
2379  blockman_.get_block(nblock, &no_more_blocks);
2380 
2381  if (no_more_blocks)
2382  {
2383  BM_ASSERT(block == 0);
2384  break;
2385  }
2386 
2387  if (block)
2388  {
2389  if (IS_FULL_BLOCK(block)) return prev;
2390  if (BM_IS_GAP(block))
2391  {
2392  if (bm::gap_find_in_block(BMGAP_PTR(block),
2393  nbit,
2394  &prev))
2395  {
2396  return prev;
2397  }
2398  }
2399  else
2400  {
2401  if (bm::bit_find_in_block(block, nbit, &prev))
2402  {
2403  return prev;
2404  }
2405  }
2406  }
2407  else
2408  {
2409  prev += (bm::set_block_mask + 1) -
2410  (prev & bm::set_block_mask);
2411  }
2412 
2413  }
2414  if (!prev) break;
2415  }
2416 
2417  return 0;
2418 }
2419 
2420 
2421 //---------------------------------------------------------------------
2422 
2423 template<class Alloc>
2425 {
2426  for (;;)
2427  {
2428  unsigned nblock = unsigned(prev >> bm::set_block_shift);
2429  if (nblock >= bm::set_total_blocks) break;
2430 
2431  if (blockman_.is_subblock_null(nblock >> bm::set_array_shift))
2432  {
2433  prev += (bm::set_blkblk_mask + 1) -
2434  (prev & bm::set_blkblk_mask);
2435  }
2436  else
2437  {
2438  unsigned nbit = unsigned(prev & bm::set_block_mask);
2439 
2440  int no_more_blocks;
2441  bm::word_t* block =
2442  blockman_.get_block(nblock, &no_more_blocks);
2443 
2444  if (no_more_blocks)
2445  {
2446  BM_ASSERT(block == 0);
2447  break;
2448  }
2449 
2450 
2451  if (block)
2452  {
2453  if (IS_FULL_BLOCK(block))
2454  {
2455  set(prev, false);
2456  return prev;
2457  }
2458  if (BM_IS_GAP(block))
2459  {
2460  unsigned is_set;
2461  unsigned new_block_len =
2462  gap_set_value(0, BMGAP_PTR(block), nbit, &is_set);
2463  if (is_set) {
2464  BMCOUNT_DEC
2465  unsigned threshold =
2466  bm::gap_limit(BMGAP_PTR(block), blockman_.glen());
2467  if (new_block_len > threshold)
2468  {
2469  extend_gap_block(nblock, BMGAP_PTR(block));
2470  }
2471  return prev;
2472  } else {
2473  if (bm::gap_find_in_block(BMGAP_PTR(block),
2474  nbit,
2475  &prev))
2476  {
2477  set(prev, false);
2478  return prev;
2479  }
2480  }
2481  }
2482  else // bit block
2483  {
2484  if (bm::bit_find_in_block(block, nbit, &prev))
2485  {
2486  BMCOUNT_DEC
2487 
2488  unsigned nbit =
2489  unsigned(prev & bm::set_block_mask);
2490  unsigned nword =
2491  unsigned(nbit >> bm::set_word_shift);
2492  nbit &= bm::set_word_mask;
2493  bm::word_t* word = block + nword;
2494  bm::word_t mask = ((bm::word_t)1) << nbit;
2495  *word &= ~mask;
2496 
2497  return prev;
2498  }
2499  }
2500  }
2501  else
2502  {
2503  prev += (bm::set_block_mask + 1) -
2504  (prev & bm::set_block_mask);
2505  }
2506 
2507  }
2508  if (!prev) break;
2509  }
2510 
2511  return 0;
2512 }
2513 
2514 //---------------------------------------------------------------------
2515 
2516 template<class Alloc>
2518  const bm::bvector<Alloc>& bvect,
2519  bm::operation opcode)
2520 {
2521 
2522  unsigned top_blocks = blockman_.top_block_size();
2523  unsigned bvect_top_blocks = bvect.blockman_.top_block_size();
2524 
2525  if (size_ == bvect.size_)
2526  {
2527  BM_ASSERT(top_blocks >= bvect_top_blocks);
2528  }
2529  else
2530  if (size_ < bvect.size_) // this vect shorter than the arg.
2531  {
2532  size_ = bvect.size_;
2533  // stretch our capacity
2534  blockman_.reserve_top_blocks(bvect_top_blocks);
2535  top_blocks = blockman_.top_block_size();
2536  }
2537  else
2538  if (size_ > bvect.size_) // this vector larger
2539  {
2540  if (opcode == BM_AND) // clear the tail with zeros
2541  {
2542  set_range(bvect.size_, size_ - 1, false);
2543  if (bvect_top_blocks < top_blocks)
2544  {
2545  // not to scan blocks we already swiped
2546  top_blocks = bvect_top_blocks;
2547  }
2548  }
2549  }
2550 
2551  bm::word_t*** blk_root = blockman_.blocks_root();
2552  unsigned block_idx = 0;
2553  unsigned i, j;
2554 
2556 
2557  // calculate effective top size to avoid overscan
2558  top_blocks = blockman_.effective_top_block_size();
2559  if (top_blocks < bvect.blockman_.effective_top_block_size())
2560  {
2561  if (opcode != BM_AND)
2562  {
2563  top_blocks = bvect.blockman_.effective_top_block_size();
2564  }
2565  }
2566 
2567  for (i = 0; i < top_blocks; ++i)
2568  {
2569  bm::word_t** blk_blk = blk_root[i];
2570  if (blk_blk == 0) // not allocated
2571  {
2572  if (opcode == BM_AND) // 0 AND anything == 0
2573  {
2574  block_idx += bm::set_array_size;
2575  continue;
2576  }
2577  const bm::word_t* const* bvbb = bvect.blockman_.get_topblock(i);
2578  if (bvbb == 0) // skip it because 0 OP 0 == 0
2579  {
2580  block_idx += bm::set_array_size;
2581  continue;
2582  }
2583  // 0 - self, non-zero argument
2584  unsigned r = i * bm::set_array_size;
2585  for (j = 0; j < bm::set_array_size; ++j)
2586  {
2587  const bm::word_t* arg_blk = bvect.blockman_.get_block(i, j);
2588  if (arg_blk )
2589  combine_operation_with_block(r + j,
2590  0, 0,
2591  arg_blk, BM_IS_GAP(arg_blk),
2592  opcode);
2593  } // for j
2594  continue;
2595  }
2596 
2597  if (opcode == BM_AND)
2598  {
2599  unsigned r = i * bm::set_array_size;
2600  for (j = 0; j < bm::set_array_size; ++j)
2601  {
2602  bm::word_t* blk = blk_blk[j];
2603  if (blk)
2604  {
2605  const bm::word_t* arg_blk = bvect.blockman_.get_block(i, j);
2606  if (arg_blk)
2607  combine_operation_with_block(r + j,
2608  BM_IS_GAP(blk), blk,
2609  arg_blk, BM_IS_GAP(arg_blk),
2610  opcode);
2611  else
2612  blockman_.zero_block(i, j);
2613  }
2614 
2615  } // for j
2616  }
2617  else // OR, SUB, XOR
2618  {
2619  unsigned r = i * bm::set_array_size;
2620  for (j = 0; j < bm::set_array_size; ++j)
2621  {
2622  bm::word_t* blk = blk_blk[j];
2623  const bm::word_t* arg_blk = bvect.blockman_.get_block(i, j);
2624  if (arg_blk || blk)
2625  combine_operation_with_block(r + j, BM_IS_GAP(blk), blk,
2626  arg_blk, BM_IS_GAP(arg_blk),
2627  opcode);
2628  } // for j
2629  }
2630  } // for i
2631 
2632 }
2633 
2634 
2635 //---------------------------------------------------------------------
2636 
2637 
2638 template<class Alloc>
2639 void
2641  bool gap,
2642  bm::word_t* blk,
2643  const bm::word_t* arg_blk,
2644  bool arg_gap,
2645  bm::operation opcode)
2646 {
2647  gap_word_t tmp_buf[bm::gap_equiv_len * 3]; // temporary result
2648  const bm::gap_word_t* res;
2649  unsigned res_len;
2650  int level;
2651  unsigned threshold;
2652 
2653 
2654  if (opcode == BM_OR || opcode == BM_XOR)
2655  {
2656  if (!blk && arg_gap)
2657  {
2658  res = BMGAP_PTR(arg_blk);
2659  res_len = bm::gap_length(res);
2660  level = -1;
2661  threshold = 0;
2662  goto assign_gap_result;
2663  }
2664  }
2665 
2666  if (gap) // our block GAP-type
2667  {
2668  if (arg_gap) // both blocks GAP-type
2669  {
2670  {
2671  gap_operation_func_type gfunc =
2673  BM_ASSERT(gfunc);
2674  res = (*gfunc)(BMGAP_PTR(blk),
2675  BMGAP_PTR(arg_blk),
2676  tmp_buf,
2677  res_len);
2678  }
2679  BM_ASSERT(res == tmp_buf);
2680  ++res_len;// = bm::gap_length(res);
2681 
2682  BM_ASSERT(!(res == tmp_buf && res_len == 0));
2683 
2684  // if as a result of the operation gap block turned to zero
2685  // we can now replace it with NULL
2687  {
2688  blockman_.zero_block(nb);
2689  return;
2690  }
2691 
2692  // mutation check
2693 
2694  level = gap_level(BMGAP_PTR(blk));
2695  threshold = blockman_.glen(level)-4;
2696 
2697  assign_gap_result:
2698  int new_level = gap_calc_level(res_len, blockman_.glen());
2699  if (new_level == -1)
2700  {
2701  blockman_.convert_gap2bitset(nb, res, res_len-1);
2702  return;
2703  }
2704 
2705  if (res_len > threshold)
2706  {
2707  gap_word_t* new_blk =
2708  blockman_.allocate_gap_block(new_level, res);
2709  set_gap_level(new_blk, new_level);
2710 
2711  bm::word_t* p = (bm::word_t*)new_blk;
2712  BMSET_PTRGAP(p);
2713 
2714  if (blk)
2715  {
2716  blockman_.set_block_ptr(nb, p);
2717  blockman_.get_allocator().free_gap_block(BMGAP_PTR(blk),
2718  blockman_.glen());
2719  }
2720  else
2721  {
2722  blockman_.set_block(nb, p, true); // set GAP block
2723  }
2724  return;
2725  }
2726 
2727  // gap operation result is in the temporary buffer
2728  // we copy it back to the gap_block
2729 
2730  BM_ASSERT(blk);
2731 
2732  set_gap_level(tmp_buf, level);
2733  ::memcpy(BMGAP_PTR(blk), tmp_buf, res_len * sizeof(gap_word_t));
2734  return;
2735  }
2736  else // argument is BITSET-type (own block is GAP)
2737  {
2738  // since we can not combine blocks of mixed type
2739  // we need to convert our block to bitset
2740 
2741  if (arg_blk == 0) // Combining against an empty block
2742  {
2743  switch (opcode)
2744  {
2745  case BM_AND: // ("Value" AND 0) == 0
2746  blockman_.zero_block(nb);
2747  return;
2748  case BM_OR: case BM_SUB: case BM_XOR:
2749  return; // nothing to do
2750  }
2751  }
2752  gap_word_t* gap_blk = BMGAP_PTR(blk);
2753  if (opcode == BM_AND)
2754  {
2755  unsigned gap_cnt = gap_bit_count(gap_blk);
2756  if (gap_cnt < 128)
2757  {
2758  gap_word_t tmp_buf[bm::gap_equiv_len * 3];
2759  gap_word_t arr_len =
2760  gap_convert_to_arr(tmp_buf, gap_blk,
2761  bm::gap_equiv_len-10);
2762  BM_ASSERT(gap_cnt == arr_len);
2763  blockman_.zero_block(nb);
2764  unsigned arr_i = 0;
2765  int block_type;
2766  blk =
2767  blockman_.check_allocate_block(nb,
2768  true,
2769  BM_GAP,
2770  &block_type,
2771  false //no null return
2772  );
2773  BM_ASSERT(block_type==1); // GAP
2774  gap_blk = BMGAP_PTR(blk);
2775  unsigned threshold = bm::gap_limit(gap_blk, blockman_.glen());
2776  for (; arr_i < arr_len; ++arr_i)
2777  {
2778  gap_word_t bit_idx = tmp_buf[arr_i];
2779  if (bm::test_bit(arg_blk, bit_idx))
2780  {
2781  unsigned is_set;
2782  unsigned new_block_len =
2783  gap_set_value(true, gap_blk, bit_idx, &is_set);
2784  BM_ASSERT(is_set);
2785  if (new_block_len > threshold)
2786  {
2787  gap_blk =
2788  blockman_.extend_gap_block(nb, gap_blk);
2789  if (gap_blk == 0) // mutated into bit-block
2790  {
2791  blk = blockman_.check_allocate_block(
2792  nb,
2793  true,
2794  this->get_new_blocks_strat(),
2795  &block_type,
2796  false // no null return
2797  );
2798  BM_ASSERT(block_type == 0); // BIT
2799  // target block degraded into plain bit-block
2800  for (++arr_i; arr_i < arr_len; ++arr_i)
2801  {
2802  bit_idx = tmp_buf[arr_i];
2803  if (bm::test_bit(arg_blk, bit_idx))
2804  {
2805  or_bit_block(blk, bit_idx, 1);
2806  }
2807  } // for arr_i
2808  return;
2809  } // if gap mutated
2810  }
2811  } // for arr_i
2812  }
2813 
2814  return;
2815  }
2816  } // BM_AND
2817 
2818  blk = blockman_.convert_gap2bitset(nb, gap_blk);
2819  }
2820  }
2821  else // our block is BITSET-type
2822  {
2823  if (arg_gap) // argument block is GAP-type
2824  {
2825  if (IS_VALID_ADDR(blk))
2826  {
2827  // special case, maybe we can do the job without
2828  // converting the GAP argument to bitblock
2831  BM_ASSERT(gfunc);
2832  (*gfunc)(blk, BMGAP_PTR(arg_blk));
2833  return;
2834  }
2835 
2836  // the worst case we need to convert argument block to
2837  // bitset type.
2838  gap_word_t* temp_blk = (gap_word_t*) blockman_.check_allocate_tempblock();
2839  arg_blk =
2841  BMGAP_PTR(arg_blk),
2843 
2844  }
2845  }
2846 
2847  // Now here we combine two plain bitblocks using supplied bit function.
2848  bm::word_t* dst = blk;
2849 
2850  bm::word_t* ret;
2851  if (dst == 0 && arg_blk == 0)
2852  {
2853  return;
2854  }
2855 
2856  switch (opcode)
2857  {
2858  case BM_AND:
2859  ret = bit_operation_and(dst, arg_blk);
2860  goto copy_block;
2861  case BM_XOR:
2862  ret = bit_operation_xor(dst, arg_blk);
2863  if (ret && (ret == arg_blk) && IS_FULL_BLOCK(dst))
2864  {
2865  ret = blockman_.get_allocator().alloc_bit_block();
2866 #ifdef BMVECTOPT
2867  VECT_XOR_ARR_2_MASK(ret,
2868  arg_blk,
2869  arg_blk + bm::set_block_size,
2871 #else
2872  bm::wordop_t* dst_ptr = (wordop_t*)ret;
2873  const bm::wordop_t* wrd_ptr = (wordop_t*) arg_blk;
2874  const bm::wordop_t* wrd_end =
2875  (wordop_t*) (arg_blk + bm::set_block_size);
2876 
2877  do
2878  {
2879  dst_ptr[0] = bm::all_bits_mask ^ wrd_ptr[0];
2880  dst_ptr[1] = bm::all_bits_mask ^ wrd_ptr[1];
2881  dst_ptr[2] = bm::all_bits_mask ^ wrd_ptr[2];
2882  dst_ptr[3] = bm::all_bits_mask ^ wrd_ptr[3];
2883 
2884  dst_ptr+=4;
2885  wrd_ptr+=4;
2886 
2887  } while (wrd_ptr < wrd_end);
2888 #endif
2889  break;
2890  }
2891  goto copy_block;
2892  case BM_OR:
2893  ret = bit_operation_or(dst, arg_blk);
2894  copy_block:
2895  if (ret && (ret == arg_blk) && !IS_FULL_BLOCK(ret))
2896  {
2897  ret = blockman_.get_allocator().alloc_bit_block();
2898  bit_block_copy(ret, arg_blk);
2899  }
2900  break;
2901 
2902  case BM_SUB:
2903  ret = bit_operation_sub(dst, arg_blk);
2904  if (ret && ret == arg_blk)
2905  {
2906  ret = blockman_.get_allocator().alloc_bit_block();
2907 #ifdef BMVECTOPT
2909  arg_blk,
2910  arg_blk + bm::set_block_size,
2912 #else
2913 
2914  bm::wordop_t* dst_ptr = (wordop_t*)ret;
2915  const bm::wordop_t* wrd_ptr = (wordop_t*) arg_blk;
2916  const bm::wordop_t* wrd_end =
2917  (wordop_t*) (arg_blk + bm::set_block_size);
2918 
2919  do
2920  {
2921  dst_ptr[0] = bm::all_bits_mask & ~wrd_ptr[0];
2922  dst_ptr[1] = bm::all_bits_mask & ~wrd_ptr[1];
2923  dst_ptr[2] = bm::all_bits_mask & ~wrd_ptr[2];
2924  dst_ptr[3] = bm::all_bits_mask & ~wrd_ptr[3];
2925 
2926  dst_ptr+=4;
2927  wrd_ptr+=4;
2928 
2929  } while (wrd_ptr < wrd_end);
2930 #endif
2931  }
2932  break;
2933  default:
2934  BM_ASSERT(0);
2935  ret = 0;
2936  }
2937 
2938  if (ret != dst) // block mutation
2939  {
2940  blockman_.set_block(nb, ret);
2941  blockman_.get_allocator().free_bit_block(dst);
2942  }
2943 }
2944 
2945 //---------------------------------------------------------------------
2946 
2947 template<class Alloc>
2949  bm::id_t right,
2950  bool value)
2951 {
2952  // calculate logical number of start and destination blocks
2953  unsigned nblock_left = unsigned(left >> bm::set_block_shift);
2954  unsigned nblock_right = unsigned(right >> bm::set_block_shift);
2955 
2956  bm::word_t* block = blockman_.get_block(nblock_left);
2957  bool left_gap = BM_IS_GAP(block);
2958 
2959  unsigned nbit_left = unsigned(left & bm::set_block_mask);
2960  unsigned nbit_right = unsigned(right & bm::set_block_mask);
2961 
2962  unsigned r =
2963  (nblock_left == nblock_right) ? nbit_right :(bm::bits_in_block-1);
2964 
2965  bm::gap_word_t tmp_gap_blk[5] = {0,};
2966 
2967  // Set bits in the starting block
2968 
2969  unsigned nb;
2970  if ((nbit_left == 0) && (r == bm::bits_in_block - 1)) // full block
2971  {
2972  nb = nblock_left;
2973  }
2974  else
2975  {
2976  gap_init_range_block<gap_word_t>(tmp_gap_blk,
2977  (gap_word_t)nbit_left,
2978  (gap_word_t)r,
2979  (gap_word_t)value,
2981 
2982  combine_operation_with_block(nblock_left,
2983  left_gap,
2984  block,
2985  (bm::word_t*) tmp_gap_blk,
2986  1,
2987  value ? BM_OR : BM_AND);
2988 
2989  if (nblock_left == nblock_right) // in one block
2990  return;
2991  nb = nblock_left+1;
2992  }
2993 
2994  // Set (or clear) all full blocks between left and right
2995 
2996  unsigned nb_to = nblock_right + (nbit_right ==(bm::bits_in_block-1));
2997 
2998  if (value)
2999  {
3000  for (; nb < nb_to; ++nb)
3001  {
3002  block = blockman_.get_block(nb);
3003  if (IS_FULL_BLOCK(block))
3004  continue;
3005 
3006  blockman_.set_block(nb, FULL_BLOCK_ADDR);
3007  blockman_.free_block(block);
3008  } // for
3009  }
3010  else // value == 0
3011  {
3012  for (; nb < nb_to; ++nb)
3013  {
3014  block = blockman_.get_block(nb);
3015  if (block == 0) // nothing to do
3016  continue;
3017  blockman_.set_block(nb, 0, false /*bit*/);
3018  blockman_.free_block(block);
3019 
3020  } // for
3021  } // if value else
3022 
3023  if (nb_to > nblock_right)
3024  return;
3025 
3026  block = blockman_.get_block(nblock_right);
3027  bool right_gap = BM_IS_GAP(block);
3028 
3029  gap_init_range_block<gap_word_t>(tmp_gap_blk,
3030  (gap_word_t)0,
3031  (gap_word_t)nbit_right,
3032  (gap_word_t)value,
3034 
3035  combine_operation_with_block(nblock_right,
3036  right_gap,
3037  block,
3038  (bm::word_t*) tmp_gap_blk,
3039  1,
3040  value ? BM_OR : BM_AND);
3041 
3042 }
3043 
3044 //---------------------------------------------------------------------
3045 
3046 
3047 } // namespace
3048 
3049 #include "bmundef.h"
3050 
3051 #ifdef _MSC_VER
3052 #pragma warning( pop )
3053 #endif
3054 
3055 
3056 #endif
bitvector with runtime compression of bits.
Definition: bm.h:120
unsigned gap_capacity(const T *buf, const T *glevel_len)
Returs GAP block capacity.
Definition: bmfunc.h:2399
friend class enumerator
Definition: bm.h:787
unsigned max_serialize_mem
Estimated maximum of memory required for serialization.
Definition: bmfunc.h:62
bvector< Alloc > & reset()
Clears every bit in the bitvector.
Definition: bm.h:1068
unsigned gap_level(const T *buf)
Returs GAP blocks capacity level.
Definition: bmfunc.h:2427
unsigned count_blocks(unsigned *arr) const
Computes bitcount values for all bvector blocks.
Definition: bm.h:1109
void bit_block_copy(bm::word_t *dst, const bm::word_t *src)
Bitblock copy operation.
Definition: bmfunc.h:3433
unsigned block_idx_
Block index.
Definition: bm.h:310
unsigned memory_used
Memory used by bitvector including temp and service blocks.
Definition: bmfunc.h:64
gap_word_t gap_length[bm::set_total_blocks]
Array of all GAP block lengths in the bvector.
Definition: bmfunc.h:66
Bitblock invert functor.
Definition: bmblocks.h:493
enumerator & go_up()
Definition: bm.h:503
static void * Alloc(size_t size)
Definition: asntypes.cpp:59
counted_enumerator & operator++()
Definition: bm.h:758
const reference & operator^=(bool value) const
Definition: bm.h:195
void operator|=(const bvector< Alloc > &bvect)
Definition: bm.h:903
std::output_iterator_tag iterator_category
Definition: bm.h:339
bm::id_t check_or_next_extract(bm::id_t prev)
check if specified bit is 1, and set it to 0 if specified bit is 0, scan for the next 1 and returns i...
Definition: bm.h:2424
const unsigned set_block_size
Definition: bmconst.h:52
void clear_bit(bm::id_t n)
Clears bit n.
Definition: bm.h:1046
unsigned gap_bit_count_range(const T *buf, T left, T right)
Counts 1 bits in GAP buffer in the closed [left, right] diapason.
Definition: bmfunc.h:721
operation
Bit operations enumeration.
Definition: bmfunc.h:281
bool
Definition: cgiapp.hpp:405
bm::bvector< Alloc > & bit_or(const bm::bvector< Alloc > &vect)
Logical OR operation.
Definition: bm.h:1286
bvector< Alloc > operator-(const bvector< Alloc > &v1, const bvector< Alloc > &v2)
Definition: bm.h:1612
const unsigned set_word_shift
Definition: bmconst.h:62
unsigned gap_blocks
Number of GAP blocks.
Definition: bmfunc.h:60
void operator&=(const bvector< Alloc > &bvect)
Definition: bm.h:893
bool search_in_gapblock()
Definition: bm.h:677
bvector< Alloc > & set()
Sets every bit in this bitset to 1.
Definition: bm.h:1011
insert_iterator(bvector< Alloc > &bvect)
Definition: bm.h:346
unsigned gap_bit_count(const T *buf, unsigned dsize=0)
Calculates number of bits ON in GAP buffer.
Definition: bmfunc.h:685
void optimize_gap_size()
Optimize sizes of GAP blocks.
Definition: bm.h:1886
bool set_bit_conditional(bm::id_t n, bool val, bool condition)
Sets bit n only if current value is equal to the condition.
Definition: bm.h:985
void set_all_zero(bool free_mem)
Fills all blocks with 0.
Definition: bmblocks.h:989
void free_tempblock(bm::word_t *block) const
Frees temporary block of memory.
Definition: bm.h:1430
const unsigned set_array_shift
Definition: bmconst.h:82
bvector< Alloc > operator|(const bvector< Alloc > &v1, const bvector< Alloc > &v2)
Definition: bm.h:1582
#define IS_VALID_ADDR(addr)
Definition: bmdef.h:62
Information about current bitblock.
Definition: bm.h:289
#define VECT_XOR_ARR_2_MASK(dst, src, src_end, mask)
Definition: bmsse2.h:190
bm::word_t * bit_operation_and(bm::word_t *dst, const bm::word_t *src)
bitblock AND operation.
Definition: bmfunc.h:3809
bm::bvector< Alloc > & bvect_
Definition: bm.h:380
void set_glen(const gap_word_t *glevel_len)
Definition: bmblocks.h:1348
int gap_calc_level(int len, const T *glevel_len)
Calculates GAP block capacity level.
Definition: bmfunc.h:2457
gap_word_t gap_len
Current dgap length.
Definition: bm.h:302
bool operator>=(const bvector< Alloc > &bvect) const
Definition: bm.h:928
enumerator operator++(int)
Definition: bm.h:430
local void copy_block(deflate_state *s, charf *buf, unsigned len, int header)
Definition: trees.c:1205
D gap_convert_to_arr(D *dest, const T *buf, unsigned dest_len, bool invert=false)
Convert gap block into array of ints corresponding to 1 bits.
Definition: bmfunc.h:2674
strategy get_new_blocks_strat() const
Returns blocks allocation strategy.
Definition: bm.h:1343
bm::id_t count_range(bm::id_t left, bm::id_t right, unsigned *block_count_arr=0) const
Returns count of 1 bits in the given diapason.
Definition: bm.h:1693
void calc_stat(struct bm::bvector< Alloc >::statistics *st) const
Calculates bitvector statistics.
Definition: bm.h:2050
bm::id_t size_type
Type used to count bits in the bit vector.
Definition: bm.h:127
void optimize(bm::word_t *temp_block=0, optmode opt_mode=opt_compress, statistics *stat=0)
Optimize memory bitvector's memory allocation.
Definition: bm.h:1844
void invalidate()
Turns iterator into an invalid state.
Definition: bm.h:281
unsigned bits[32]
Unpacked list of ON bits.
Definition: bm.h:292
bm::bvector< Alloc > & bit_sub(const bm::bvector< Alloc > &vect)
Logical SUB operation.
Definition: bm.h:1319
const word_t all_bits_mask
Definition: bmconst.h:102
Definition: bm.h:73
bm::id_t check_or_next(bm::id_t prev) const
Definition: bm.h:2361
#define BMCOUNT_INC
Definition: bm.h:87
bool search_in_bitblock()
Definition: bm.h:640
T gap_length(const T *buf)
Returs GAP block length.
Definition: bmfunc.h:2385
insert_iterator inserter()
Definition: bm.h:1036
const unsigned gap_equiv_len
Definition: bmconst.h:73
bool any() const
Returns true if any bits in this bitset are set, and otherwise returns false.
Definition: bm.h:1177
counted_enumerator(const enumerator &en)
Definition: bm.h:742
void gap_convert_to_bitset(unsigned *dest, const T *buf)
GAP block to bitblock conversion.
Definition: bmfunc.h:2151
bool const_reference
Definition: bm.h:225
bm::word_t * get_block(unsigned nb) const
Finds block in 2-level blocks array.
Definition: bmblocks.h:719
bm::bvector< Alloc > & bit_xor(const bm::bvector< Alloc > &vect)
Logical XOR operation.
Definition: bm.h:1308
const blocks_manager_type & get_blocks_manager() const
Definition: bm.h:1535
const bm::word_t * ptr
Word pointer.
Definition: bm.h:291
enumerator end() const
Returns enumerator pointing on the next bit after the last.
Definition: bm.h:1450
bool operator!=(const bvector< Alloc > &bvect) const
Definition: bm.h:938
bvector< Alloc > operator^(const bvector< Alloc > &v1, const bvector< Alloc > &v2)
Definition: bm.h:1597
const bm::word_t * block_
Block pointer.(NULL-invalid)
Definition: bm.h:308
insert_iterator & operator++(int)
Definition: bm.h:374
optmode
Optimization mode Every next level means additional checks (better compression vs time) ...
Definition: bm.h:1354
size_type size_
size in bits
Definition: bm.h:1557
bm::word_t *** blocks_root()
Definition: bmblocks.h:1397
void set_new_blocks_strat(strategy strat)
Sets new blocks allocation strategy.
Definition: bm.h:1332
bitblock_descr bit_
BitBlock related info.
Definition: bm.h:315
bool none() const
Returns true if no bits are set, otherwise returns false.
Definition: bm.h:1196
GAP compression is ON.
Definition: bmconst.h:118
reference(const reference &ref)
Definition: bm.h:148
void xor_swap(W &x, W &y)
XOR swap two scalar variables.
Definition: bmfunc.h:328
bool set_bit_and(bm::id_t n, bool val=true)
Sets bit n using bit AND with the provided value.
Definition: bm.h:972
bool for_each_nzblock_if(T ***root, unsigned size1, F &f)
Definition: bmfunc.h:600
bool operator>(const iterator_base &it) const
Definition: bm.h:257
bm::id_t position_
Position in the parent bitvector.
Definition: bm.h:222
int i
Constant input iterator designed to enumerate "ON" bits counted_enumerator keeps bitcount, ie number of ON bits starting from the position 0 in the bit string up to the currently enumerated bit.
Definition: bm.h:734
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
Definition: bm.h:1440
bool gap_is_all_zero(const T *buf, unsigned set_max)
Temporary inverts all bits in the GAP buffer.
Definition: bmfunc.h:2359
const unsigned id_max
Definition: bmconst.h:48
Statistical information about bitset's memory allocation details.
Definition: bm.h:130
Free unused 0 and 1 blocks.
Definition: bm.h:1357
counted_enumerator & operator=(const enumerator &en)
Definition: bm.h:749
void forget_count()
Definition: bm.h:1145
bool operator~() const
Definition: bm.h:208
compress blocks when possible
Definition: bm.h:1358
#define BMSET_PTRGAP(ptr)
Definition: bmdef.h:88
bool operator==(const bvector< Alloc > &bvect) const
Definition: bm.h:933
bvector< Alloc > & flip()
Flips all bits.
Definition: bm.h:1215
void operator^=(const bvector< Alloc > &bvect)
Definition: bm.h:898
bm::bvector< Alloc > & bit_and(const bm::bvector< Alloc > &vect)
Logical AND operation.
Definition: bm.h:1297
int compare(const bvector< Alloc > &bvect) const
Lexicographical comparison with a bitvector.
Definition: bm.h:1920
enumerator(const bvector< Alloc > *bvect, int position)
Definition: bm.h:401
const CVect2< U > &v2 return(v1[0]*v2[0]+v1[1]*v2[1])
int bit_find_in_block(const bm::word_t *data, unsigned nbit, bm::id_t *prev)
Searches for the next 1 bit in the BIT block.
Definition: bmfunc.h:4452
bm::word_t * alloc_bit_block(unsigned alloc_factor=1)
Allocates and returns bit block.
Definition: bmalloc.h:173
Alloc allocator_type
Definition: bm.h:124
size_type capacity() const
Returns bvector's capacity (number of bits it can store)
Definition: bm.h:1084
bool bit_is_all_zero(const bm::wordop_t *start, const bm::wordop_t *end)
Returns "true" if all bits in the block are 0.
Definition: bmfunc.h:3130
void set_range_no_check(bm::id_t left, bm::id_t right, bool value)
Set range without validity checking.
Definition: bm.h:2948
unsigned gap_test(const T *buf, unsigned pos)
Tests if bit = pos is true.
Definition: bmfunc.h:496
int bitcmp(const T *buf1, const T *buf2, unsigned len)
Lexicographical comparison of BIT buffers.
Definition: bmfunc.h:2496
bm::id_t pos
Last bit position before.
Definition: bm.h:295
unsigned & reference
Definition: bm.h:397
reference & flip()
Definition: bm.h:214
unsigned int word_t
Definition: bmconst.h:43
bvector(const bvector< Alloc > &bvect)
Definition: bm.h:864
#define IS_FULL_BLOCK(addr)
Definition: bmdef.h:63
allocator_type & get_allocator()
Returns reference on the allocator.
Definition: bmblocks.h:1491
bool test(bm::id_t n) const
returns true if bit n is set and false is bit n is 0.
Definition: bm.h:1168
bool get_bit(bm::id_t n) const
returns true if bit n is set and false is bit n is 0.
Definition: bm.h:1810
bm::bvector bvect
Definition: stress.cpp:318
bvector< Alloc > & set(bm::id_t n, bool val=true)
Sets bit n if val is true, clears bit n if val is false.
Definition: bm.h:999
insert_iterator & operator=(bm::id_t n)
Definition: bm.h:352
bool operator[](bm::id_t n) const
Definition: bm.h:887
void for_each_nzblock2(T ***root, unsigned size1, F &f)
Definition: bmfunc.h:571
bvector(strategy strat=BM_BIT, const gap_word_t *glevel_len=bm::gap_len_table< true >::_len, size_type bv_size=bm::id_max, const Alloc &alloc=Alloc())
Constructs bvector class.
Definition: bm.h:842
unsigned gap_set_value(unsigned val, T *buf, unsigned pos, unsigned *is_set)
Sets or clears bit in the GAP buffer.
Definition: bmfunc.h:1175
bvector< Alloc > & set_range(bm::id_t left, bm::id_t right, bool value=true)
Sets all bits in the specified closed interval [left,right] Interval must be inside the bvector's siz...
Definition: bm.h:1630
bool and_bit_no_check(bm::id_t n, bool val)
AND specified bit without checking preconditions (size, etc)
Definition: bm.h:2290
bvector< Alloc > operator~() const
Definition: bm.h:943
reference(bvector< Alloc > &bv, bm::id_t position)
Definition: bm.h:143
#define VECT_ANDNOT_ARR_2_MASK(dst, src, src_end, mask)
Definition: bmsse2.h:193
No GAP compression strategy. All new blocks are bit blocks.
Definition: bmconst.h:117
const reference & operator|=(bool value) const
Definition: bm.h:185
bm::id_t get_next(bm::id_t prev) const
Finds the number of the next bit ON.
Definition: bm.h:1251
counted_enumerator operator++(int)
Definition: bm.h:766
bm::word_t * bit_operation_sub(bm::word_t *dst, const bm::word_t *src)
bitblock SUB operation.
Definition: bmfunc.h:4203
bm::id_t bit_block_calc_count_range(const bm::word_t *block, bm::word_t left, bm::word_t right)
Definition: bmfunc.h:2957
const gap_word_t * ptr
Word pointer.
Definition: bm.h:301
const reference & operator&=(bool value) const
Definition: bm.h:178
const unsigned gap_levels
Definition: bmconst.h:75
Default GAP lengths table.
Definition: bmfunc.h:109
unsigned idx
Current position in the bit list.
Definition: bm.h:293
const unsigned set_array_mask
Definition: bmconst.h:83
insert_iterator & operator*()
Definition: bm.h:370
bm::bvector< Alloc > * bv_
Pointer on parent bitvector.
Definition: bm.h:306
bm::id_t capacity() const
Returns current capacity (bits)
Definition: bmblocks.h:707
unsigned short gap_word_t
Definition: bmconst.h:68
unsigned value_type
Definition: bm.h:394
bool operator<(const iterator_base &it) const
Definition: bm.h:247
friend class iterator_base
Definition: bm.h:786
int gap_find_in_block(const T *buf, unsigned nbit, bm::id_t *prev)
Searches for the next 1 bit in the GAP block.
Definition: bmfunc.h:1443
blocks_manager< Alloc > blocks_manager_type
Definition: bm.h:125
bool operator<=(const iterator_base &it) const
Definition: bm.h:252
const unsigned bits_in_array
Definition: bmconst.h:87
const unsigned set_blkblk_mask
Definition: bmconst.h:55
void set_gap_levels(const gap_word_t *glevel_len)
Sets new GAP lengths table. All GAP blocks will be reallocated to match the new scheme.
Definition: bm.h:1907
#define FULL_BLOCK_ADDR
Definition: bmdef.h:61
void swap(bvector< Alloc > &bv)
Exchanges content of bv and this bitvector.
Definition: bm.h:1222
bm::id_t count() const
Number of bits ON starting from the .
Definition: bm.h:780
dgap_descr gap_
DGAP block related info.
Definition: bm.h:316
unsigned * pointer
Definition: bm.h:396
void(* gap_operation_to_bitset_func_type)(unsigned *, const gap_word_t *)
Definition: bmfunc.h:5194
bm::id_t operator*() const
Definition: bm.h:415
bvector(size_type bv_size, strategy strat=BM_BIT, const gap_word_t *glevel_len=bm::gap_len_table< true >::_len, const Alloc &alloc=Alloc())
Constructs bvector class.
Definition: bm.h:854
if(yy_accept[yy_current_state])
bm::id_t position_
Bit position (bit idx)
Definition: bm.h:307
std::input_iterator_tag iterator_category
Definition: bm.h:738
static gap_operation_to_bitset_func_type gap_op_to_bit(unsigned i)
Definition: bmfunc.h:5220
#define BMCOUNT_ADJ(x)
Definition: bm.h:91
gap_word_t *(* gap_operation_func_type)(const gap_word_t *, const gap_word_t *, gap_word_t *, unsigned &)
Definition: bmfunc.h:5198
bm::id_t value() const
Definition: bm.h:420
Information about current DGAP block.
Definition: bm.h:299
bm::word_t * allocate_tempblock() const
Allocates temporary block of memory.
Definition: bm.h:1415
const CVect3< U > & v2
Definition: globals.hpp:449
enumerator & operator++()
Definition: bm.h:425
#define BMCOUNT_VALID(x)
Definition: bm.h:89
ncbi::TMaskedQueryRegions mask
bm::word_t * bit_operation_or(bm::word_t *dst, const bm::word_t *src)
Block OR operation. Makes analysis if block is 0 or FULL.
Definition: bmfunc.h:4105
void combine_operation_with_block(unsigned nb, const bm::word_t *arg_blk, bool arg_gap, bm::operation opcode)
Definition: bm.h:1494
bool operator>=(const iterator_base &it) const
Definition: bm.h:262
bm::word_t *** get_rootblock() const
Returns root block in the tree.
Definition: bmblocks.h:819
unsigned difference_type
Definition: bm.h:395
Alloc get_allocator() const
Definition: bm.h:948
bm::gap_word_t * extend_gap_block(unsigned nb, gap_word_t *blk)
Extends GAP block to the next level or converts it to bit block.
Definition: bmblocks.h:1232
const reference & operator=(const reference &ref) const
Definition: bm.h:160
const unsigned bits_in_block
Definition: bmconst.h:86
const unsigned set_block_size_op
Definition: bmconst.h:105
bool set_bit_conditional_impl(bm::id_t n, bool val, bool condition)
Definition: bm.h:2208
bvector< Alloc > & flip(bm::id_t n)
Flips bit n.
Definition: bm.h:1205
unsigned effective_top_block_size() const
Returns effective size of the top block array in the tree Effective size excludes NULL pointers at th...
Definition: bmblocks.h:1449
union bm::bvector::iterator_base::block_descr bdescr_
bool operator==(const iterator_base &it) const
Definition: bm.h:237
bool operator!=(const iterator_base &it) const
Definition: bm.h:242
const bm::word_t * get_block(unsigned nb) const
Definition: bm.h:1457
bool operator==(const reference &ref) const
Definition: bm.h:172
const unsigned gap_max_bits
Definition: bmconst.h:72
#define BM_IS_GAP(ptr)
Definition: bmdef.h:89
Class reference implements an object for bit assignment.
Definition: bm.h:140
void combine_operation_with_block(unsigned nb, bool gap, bm::word_t *blk, const bm::word_t *arg_blk, bool arg_gap, bm::operation opcode)
Definition: bm.h:2640
bvector< Alloc > & bv_
Reference variable on the parent.
Definition: bm.h:221
bitvector blocks manager Embedded class managing bit-blocks on very low level. Includes number of fun...
Definition: bmblocks.h:51
void or_bit_block(unsigned *dest, unsigned bitpos, unsigned bitcount)
Sets bits to 1 in the bitblock.
Definition: bmfunc.h:1498
#define BM_SET_MMX_GUARD
Definition: bmdef.h:122
bool improve_gap_levels(const T *length, const T *length_end, T *glevel_len)
Finds optimal gap blocks lengths.
Definition: bmfunc.h:4881
const unsigned set_block_mask
Definition: bmconst.h:54
#define BMCOUNT_SET(x)
Definition: bm.h:90
unsigned bit_blocks
Number of bit blocks.
Definition: bmfunc.h:58
insert_iterator & operator++()
Definition: bm.h:372
const reference & operator=(bool value) const
Definition: bm.h:166
Constant input iterator designed to enumerate "ON" bits.
Definition: bm.h:388
const GenericPointer< typename T::ValueType > T2 value
Definition: pointer.h:1185
strategy new_blocks_strat_
block allocation strategy
Definition: bm.h:1556
#define BMGAP_PTR(ptr)
Definition: bmdef.h:87
void resize(size_type new_size)
Change size of the bvector.
Definition: bm.h:1675
reference operator[](bm::id_t n)
Definition: bm.h:880
const unsigned set_array_size
Definition: bmconst.h:81
void for_each_block(T ***root, unsigned size1, F &f)
Definition: bmfunc.h:624
yy_size_t n
const unsigned set_word_mask
Definition: bmconst.h:63
bvector< Alloc > & invert()
Inverts all bits.
Definition: bm.h:1787
bool operator!() const
Definition: bm.h:202
word_t wordop_t
Definition: bmconst.h:101
unsigned int id_t
Definition: bmconst.h:42
gap_word_t gap_levels[bm::gap_levels]
GAP lengths used by bvector.
Definition: bmfunc.h:68
unsigned gap_limit(const T *buf, const T *glevel_len)
Returs GAP block capacity limit.
Definition: bmfunc.h:2414
bvector & operator=(const bvector< Alloc > &bvect)
Definition: bm.h:872
bool set_bit(bm::id_t n, bool val=true)
Sets bit n.
Definition: bm.h:960
unsigned * gap_convert_to_bitset_smart(unsigned *dest, const T *buf, id_t set_max)
Smart GAP block to bitblock conversion.
Definition: bmfunc.h:2203
void extend_gap_block(unsigned nb, gap_word_t *blk)
Extends GAP block to the next level or converts it to bit block.
Definition: bm.h:1522
bvector< Alloc > operator&(const bvector< Alloc > &v1, const bvector< Alloc > &v2)
Definition: bm.h:1567
void combine_count_operation_with_block(const bm::word_t *blk, const bm::word_t *arg_blk, distance_metric_descriptor *dmit, distance_metric_descriptor *dmit_end)
Internal function computes different distance metrics.
Definition: bmalgo_impl.h:116
void swap(blocks_manager &bm)
Swaps content.
Definition: bmblocks.h:1420
void clear(bool free_mem=false)
Clears every bit in the bitvector.
Definition: bm.h:1058
double r(size_t dimension_, const Int4 *score_, const double *prob_, double theta_)
Base class for all iterators.
Definition: bm.h:231
bm::id_t extract_next(bm::id_t prev)
Finds the number of the next bit ON and sets it to 0.
Definition: bm.h:1263
#define BM_ASSERT
Definition: bmdef.h:51
static gap_operation_func_type gap_operation(unsigned i)
Definition: bmfunc.h:5226
const unsigned set_total_blocks
Definition: bmconst.h:84
size_type size() const
return current size of the vector (bits)
Definition: bm.h:1092
Output iterator iterator designed to set "ON" bits based on input sequence of integers (bit indeces)...
Definition: bm.h:335
void combine_operation(const bm::bvector< Alloc > &bvect, bm::operation opcode)
Definition: bm.h:2517
#define BMCOUNT_DEC
Definition: bm.h:88
blocks_manager_type & get_blocks_manager()
Definition: bm.h:1540
Structure with statistical information about bitset's memory allocation details.
Definition: bmfunc.h:55
const unsigned set_block_shift
Definition: bmconst.h:53
Free unused 0 blocks.
Definition: bm.h:1356
strategy
Block allocation strategies.
Definition: bmconst.h:115
bm::id_t count() const
Returns count of bits which are 1.
Definition: bm.h:1653
std::input_iterator_tag iterator_category
Definition: bm.h:392
unsigned test_bit(const unsigned *block, unsigned bitpos)
Test 1 bit in a block.
Definition: bmfunc.h:1481
unsigned cnt
Number of ON bits.
Definition: bm.h:294
Definition: set.hpp:44
void for_each_nzblock(T ***root, unsigned size1, F &f)
Definition: bmfunc.h:535
void set_gap_level(T *buf, unsigned level)
Sets GAP block capacity level.
Definition: bmfunc.h:2441
ESERV_Flag val
blocks_manager_type blockman_
bitblocks manager
Definition: bm.h:1555
bm::word_t * bit_operation_xor(bm::word_t *dst, const bm::word_t *src)
bitblock XOR operation.
Definition: bmfunc.h:4299
bool set_bit_no_check(bm::id_t n, bool val)
Set specified bit without checking preconditions (size, etc)
Definition: bm.h:2136
int gapcmp(const T *buf1, const T *buf2)
Lexicographical comparison of GAP buffers.
Definition: bmfunc.h:873
bool operator>(const bvector< Alloc > &bvect) const
Definition: bm.h:923
unsigned top_block_size() const
Returns size of the top block array in the tree.
Definition: bmblocks.h:1441
bool valid() const
Checks if iterator is still valid.
Definition: bm.h:272
unsigned block_type_
Type of block. 0-Bit, 1-GAP.
Definition: bm.h:309
void operator-=(const bvector< Alloc > &bvect)
Definition: bm.h:908
void free_bit_block(bm::word_t *block, unsigned alloc_factor=1)
Frees bit block allocated by alloc_bit_block.
Definition: bmalloc.h:180
bm::id_t get_first() const
Gets number of first bit which is ON.
Definition: bm.h:1242
unsigned bit_list_4(T w, B *bits)
Unpacks word into list of ON bit indexes (quad-bit based)
Definition: bmfunc.h:4692
bm::id_t recalc_count()
Definition: bm.h:1132
Modified on Sat Jul 04 12:46:32 2015 by modify_doxy.py rev. 426318