BitMagic-C++
bm.h
Go to the documentation of this file.
1 
2 #ifndef BM__H__INCLUDED__
3 #define BM__H__INCLUDED__
4 /*
5 Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
6 
7 Licensed under the Apache License, Version 2.0 (the "License");
8 you may not use this file except in compliance with the License.
9 You may obtain a copy of the License at
10 
11  http://www.apache.org/licenses/LICENSE-2.0
12 
13 Unless required by applicable law or agreed to in writing, software
14 distributed under the License is distributed on an "AS IS" BASIS,
15 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 See the License for the specific language governing permissions and
17 limitations under the License.
18 
19 For more information please visit: http://bitmagic.io
20 */
21 
22 /*! \file bm.h
23  \brief Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators
24 */
25 
26 
27 // define BM_NO_STL if you use BM in "STL free" environment and want
28 // to disable any references to STL headers
29 #ifndef BM_NO_STL
30 # include <iterator>
31 # include <initializer_list>
32 # include <stdexcept>
33 #endif
34 
35 #include <limits.h>
36 
37 #ifdef _MSC_VER
38 #pragma warning( push )
39 #pragma warning( disable : 4311 4312 4127)
40 #endif
41 
42 
43 #include "bmdef.h"
44 #include "bmconst.h"
45 #include "bmsimd.h"
46 #include "bmfwd.h"
47 
48 # define BM_DECLARE_TEMP_BLOCK(x) bm::bit_block_t x;
49 
50 #include "bmfunc.h"
51 #include "encoding.h"
52 #include "bmalloc.h"
53 #include "bmblocks.h"
54 
55 
56 extern "C"
57 {
58  /**
59  Callback type to visit (callback style) bits in bit-vector(s)
60 
61  @param handle_ptr - custom pointer to callback specific data
62  @param bit_idx - number/index of visited bit
63 
64  @ingroup bvector
65  */
66  typedef int (*bit_visitor_callback_type)(void* handle_ptr, bm::id_t bit_idx);
67 }
68 
69 
70 namespace bm
71 {
72 
73 /** @defgroup bmagic BitMagic Library
74  BitMagic C++ Library
75  For more information please visit: http://bitmagic.io
76 */
77 
78 
79 /** @defgroup bvector bvector<> container
80  The Main bvector<> Group
81  bvector<> template: front end of the BitMagic library.
82 
83  @ingroup bmagic
84 */
85 
86 /** @defgroup bvit bvector<> iterators
87  Iterators for compressed bit-vector traversal
88  @ingroup bvector
89 */
90 
91 
92 /**
93  @brief Rank-Select acceleration index
94 
95  Index uses two-level acceleration structure:
96  bcount - running total popcount for all (possible) blocks
97  (missing blocks give duplicate counts as POPCNT(N-1) + 0).
98  subcount - sub-count inside blocks
99 
100  @ingroup bvector
101 */
102 struct rs_index
103 {
106  unsigned total_blocks;
107 
108  rs_index() { total_blocks = 0; }
109  rs_index(const rs_index& rsi) BMNOEXEPT;
110 
111  /// init arrays to zeros
112  void init() BMNOEXEPT;
113 
114  /// copy rs index
115  void copy_from(const rs_index& rsi) BMNOEXEPT;
116 
117  /// return bit-count for specified block
118  unsigned count(unsigned nb) const;
119 
120  /// determine the sub-range within a bit-block
121  unsigned find_sub_range(unsigned block_bit_pos) const;
122 
123  /// determine block sub-range for rank search
124  bm::gap_word_t select_sub_range(unsigned nb, unsigned& rank) const;
125 };
126 
127 
128 
129 /*!
130  @brief Bitvector
131  Bit-vector container with runtime compression of bits
132 
133  @ingroup bvector
134 */
135 template<class Alloc>
136 class bvector
137 {
138 public:
139  typedef Alloc allocator_type;
140  typedef typename allocator_type::allocator_pool_type allocator_pool_type;
141  typedef blocks_manager<Alloc> blocks_manager_type;
142  typedef bm::id_t size_type;
143 
144  /** Statistical information about bitset's memory allocation details. */
145  struct statistics : public bv_statistics
146  {};
147 
148  /**
149  @brief Class reference implements an object for bit assignment.
150  Since C++ does not provide with build-in bit type supporting l-value
151  operations we have to emulate it.
152 
153  @ingroup bvector
154  */
155  class reference
156  {
157  public:
159  : bv_(bv),
160  position_(position)
161  {}
162 
163  reference(const reference& ref)
164  : bv_(ref.bv_),
165  position_(ref.position_)
166  {
167  bv_.set(position_, ref.bv_.get_bit(position_));
168  }
169 
170  operator bool() const
171  {
172  return bv_.get_bit(position_);
173  }
174 
175  const reference& operator=(const reference& ref) const
176  {
177  bv_.set(position_, (bool)ref);
178  return *this;
179  }
180 
181  const reference& operator=(bool value) const
182  {
183  bv_.set(position_, value);
184  return *this;
185  }
186 
187  bool operator==(const reference& ref) const
188  {
189  return bool(*this) == bool(ref);
190  }
191 
192  /*! Bitwise AND. Performs operation: bit = bit AND value */
193  const reference& operator&=(bool value) const
194  {
195  bv_.set_bit_and(position_, value);
196  return *this;
197  }
198 
199  /*! Bitwise OR. Performs operation: bit = bit OR value */
200  const reference& operator|=(bool value) const
201  {
202  if (value != bv_.get_bit(position_))
203  {
204  bv_.set_bit(position_);
205  }
206  return *this;
207  }
208 
209  /*! Bitwise exclusive-OR (XOR). Performs operation: bit = bit XOR value */
210  const reference& operator^=(bool value) const
211  {
212  bv_.set(position_, value != bv_.get_bit(position_));
213  return *this;
214  }
215 
216  /*! Logical Not operator */
217  bool operator!() const
218  {
219  return !bv_.get_bit(position_);
220  }
221 
222  /*! Bit Not operator */
223  bool operator~() const
224  {
225  return !bv_.get_bit(position_);
226  }
227 
228  /*! Negates the bit value */
230  {
231  bv_.flip(position_);
232  return *this;
233  }
234 
235  private:
236  bvector<Alloc>& bv_; //!< Reference variable on the parent.
237  bm::id_t position_; //!< Position in the parent bitvector.
238  };
239 
240  typedef bool const_reference;
241 
242  /*!
243  @brief Base class for all iterators.
244  @ingroup bvit
245  */
247  {
248  friend class bvector;
249  public:
250  iterator_base() : bv_(0), position_(bm::id_max), block_(0) {}
251 
252  bool operator==(const iterator_base& it) const
253  {
254  return (position_ == it.position_) && (bv_ == it.bv_);
255  }
256 
257  bool operator!=(const iterator_base& it) const
258  {
259  return ! operator==(it);
260  }
261 
262  bool operator < (const iterator_base& it) const
263  {
264  return position_ < it.position_;
265  }
266 
267  bool operator <= (const iterator_base& it) const
268  {
269  return position_ <= it.position_;
270  }
271 
272  bool operator > (const iterator_base& it) const
273  {
274  return position_ > it.position_;
275  }
276 
277  bool operator >= (const iterator_base& it) const
278  {
279  return position_ >= it.position_;
280  }
281 
282  /**
283  \fn bool bm::bvector::iterator_base::valid() const
284  \brief Checks if iterator is still valid. Analog of != 0 comparison for pointers.
285  \returns true if iterator is valid.
286  */
287  bool valid() const
288  {
289  return position_ != bm::id_max;
290  }
291 
292  /**
293  \fn bool bm::bvector::iterator_base::invalidate()
294  \brief Turns iterator into an invalid state.
295  */
296  void invalidate()
297  {
298  position_ = bm::id_max;
299  }
300 
301  /** \brief Compare FSMs for testing purposes
302  \internal
303  */
304  bool compare_state(const iterator_base& ib) const
305  {
306  if (this->bv_ != ib.bv_) return false;
307  if (this->position_ != ib.position_) return false;
308  if (this->block_ != ib.block_) return false;
309  if (this->block_type_ != ib.block_type_) return false;
310  if (this->block_idx_ != ib.block_idx_) return false;
311 
312  const block_descr& bd = this->bdescr_;
313  const block_descr& ib_db = ib.bdescr_;
314 
315  if (this->block_type_ == 0) // bit block
316  {
317  if (bd.bit_.ptr != ib_db.bit_.ptr) return false;
318  if (bd.bit_.idx != ib_db.bit_.idx) return false;
319  if (bd.bit_.cnt != ib_db.bit_.cnt) return false;
320  if (bd.bit_.pos != ib_db.bit_.pos) return false;
321  for (unsigned i = 0; i < bd.bit_.cnt; ++i)
322  {
323  if (bd.bit_.bits[i] != bd.bit_.bits[i]) return false;
324  }
325  }
326  else // GAP block
327  {
328  if (bd.gap_.ptr != ib_db.gap_.ptr) return false;
329  if (bd.gap_.gap_len != ib_db.gap_.gap_len) return false;
330  }
331  return true;
332  }
333 
334  public:
335 
336  /** Information about current bitblock. */
338  {
339  const bm::word_t* ptr; //!< Word pointer.
340  unsigned char bits[set_bitscan_wave_size*32]; //!< bit list
341  unsigned short idx; //!< Current position in the bit list
342  unsigned short cnt; //!< Number of ON bits
343  bm::id_t pos; //!< Last bit position decode before
344  };
345 
346  /** Information about current DGAP block. */
347  struct dgap_descr
348  {
349  const gap_word_t* ptr; //!< Word pointer.
350  gap_word_t gap_len; //!< Current dgap length.
351  };
352 
353  protected:
354  bm::bvector<Alloc>* bv_; //!< Pointer on parent bitvector
355  bm::id_t position_; //!< Bit position (bit idx)
356  const bm::word_t* block_; //!< Block pointer.(NULL-invalid)
357  unsigned block_type_; //!< Type of block. 0-Bit, 1-GAP
358  unsigned block_idx_; //!< Block index
359 
360  /*! Block type dependent information for current block. */
362  {
363  bitblock_descr bit_; //!< BitBlock related info.
364  dgap_descr gap_; //!< DGAP block related info.
365  } bdescr_;
366  };
367 
368  /*!
369  @brief Output iterator iterator designed to set "ON" bits based on
370  input sequence of integers (bit indeces).
371 
372  STL container can be converted to bvector using this iterator
373  Insert iterator guarantees the vector will be dynamically resized
374  (set_bit does not do that).
375 
376  @note
377  If you have many bits to set it is a good idea to use output iterator
378  instead of explicitly calling set, because iterator may implement
379  some performance specific tricks to make sure bulk insert is fast.
380 
381  @ingroup bvit
382  */
384  {
385  public:
386 #ifndef BM_NO_STL
387  typedef std::output_iterator_tag iterator_category;
388 #endif
389  typedef unsigned value_type;
390  typedef void difference_type;
391  typedef void pointer;
392  typedef void reference;
393 
394  insert_iterator() : bvect_(0), max_bit_(0) {}
395 
397  : bvect_(&bvect),
398  max_bit_(bvect.size())
399  {
400  bvect_->init();
401  }
402 
404  : bvect_(iit.bvect_),
405  max_bit_(iit.max_bit_)
406  {
407  bvect_->init();
408  }
409 
411  {
412  bvect_ = ii.bvect_;
413  max_bit_ = ii.max_bit_;
414  return *this;
415  }
416 
418  {
419  BM_ASSERT(n < bm::id_max);
420  BM_ASSERT_THROW(n < bm::id_max, BM_ERR_RANGE);
421 
422  if (n >= max_bit_)
423  {
424  max_bit_ = n;
425  if (n >= bvect_->size())
426  {
427  bm::id_t new_size = (n == bm::id_max) ? bm::id_max : n + 1;
428  bvect_->resize(new_size);
429  }
430  }
431 
432  bvect_->set_bit_no_check(n);
433  return *this;
434  }
435 
436  /*! Returns *this without doing anything (no-op) */
437  insert_iterator& operator*() { return *this; }
438  /*! Returns *this. This iterator does not move (no-op) */
439  insert_iterator& operator++() { return *this; }
440  /*! Returns *this. This iterator does not move (no-op)*/
441  insert_iterator& operator++(int) { return *this; }
442 
443  protected:
446  };
447 
448 
449  /*! @brief Constant iterator designed to enumerate "ON" bits
450  @ingroup bvit
451  */
452  class enumerator : public iterator_base
453  {
454  public:
455 #ifndef BM_NO_STL
456  typedef std::input_iterator_tag iterator_category;
457 #endif
458  typedef unsigned value_type;
459  typedef unsigned difference_type;
460  typedef unsigned* pointer;
461  typedef unsigned& reference;
462 
463  public:
465  {}
466 
467  /*! @brief Construct enumerator associated with a vector.
468  This construction creates unpositioned iterator with status
469  valid() == false. It can be re-positioned using go_first() or go_to()
470  */
472  : iterator_base()
473  {
474  this->bv_ = const_cast<bvector<Alloc>*>(bv);
475  }
476 
477  /*! @brief Construct enumerator for bit vector
478  @param bv bit-vector pointer
479  @param pos bit position in the vector
480  if position is 0, it finds the next 1 or becomes not valid
481  (en.valid() == false)
482  */
484  : iterator_base()
485  {
486  this->bv_ = const_cast<bvector<Alloc>*>(bv);
487  this->go_to(pos);
488  }
489 
490  /*! \brief Get current position (value) */
492  {
493  return this->position_;
494  }
495 
496  /*! \brief Get current position (value) */
497  bm::id_t value() const
498  {
499  return this->position_;
500  }
501  /*! \brief Advance enumerator forward to the next available bit */
503  {
504  return this->go_up();
505  }
506 
507  /*! \brief Advance enumerator forward to the next available bit.
508  Possibly do NOT use this operator it is slower than the pre-fix increment.
509  */
511  {
512  enumerator tmp = *this;
513  this->go_up();
514  return tmp;
515  }
516 
517 
518  /*! \brief Position enumerator to the first available bit */
519  void go_first()
520  {
521  BM_ASSERT(this->bv_);
522 
523  blocks_manager_type* bman = &(this->bv_->blockman_);
524  if (!bman->is_init())
525  {
526  this->invalidate();
527  return;
528  }
529 
530  bm::word_t*** blk_root = bman->top_blocks_root();
531 
532  this->block_idx_ = this->position_= 0;
533  unsigned i, j;
534 
535  for (i = 0; i < bman->top_block_size(); ++i)
536  {
537  bm::word_t** blk_blk = blk_root[i];
538 
539  if (blk_blk == 0) // not allocated
540  {
541  this->block_idx_ += bm::set_array_size;
542  this->position_ += bm::bits_in_array;
543  continue;
544  }
545 
546  for (j = 0; j < bm::set_array_size; ++j,++(this->block_idx_))
547  {
548  this->block_ = blk_blk[j];
549 
550  if (this->block_ == 0)
551  {
552  this->position_ += bits_in_block;
553  continue;
554  }
555 
556  if (BM_IS_GAP(this->block_))
557  {
558  this->block_type_ = 1;
559  if (search_in_gapblock())
560  {
561  return;
562  }
563  }
564  else
565  {
566  if (this->block_ == FULL_BLOCK_FAKE_ADDR)
567  this->block_ = FULL_BLOCK_REAL_ADDR;
568 
569  this->block_type_ = 0;
570  if (search_in_bitblock())
571  {
572  return;
573  }
574  }
575 
576  } // for j
577 
578  } // for i
579 
580  this->invalidate();
581  }
582 
583  /// advance iterator forward by one
584  void advance() { this->go_up(); }
585 
586 
587  /*! \brief Advance enumerator to the next available bit */
589  {
590  BM_ASSERT(this->valid());
591  BM_ASSERT_THROW(this->valid(), BM_ERR_RANGE);
592 
593  // Current block search.
594  //
595 
596  block_descr_type* bdescr = &(this->bdescr_);
597  switch (this->block_type_)
598  {
599  case 0: // BitBlock
600  {
601  // check if we can get the value from the bits traversal cache
602  unsigned short idx = ++(bdescr->bit_.idx);
603  if (idx < bdescr->bit_.cnt)
604  {
605  this->position_ = bdescr->bit_.pos + bdescr->bit_.bits[idx];
606  return *this;
607  }
608  this->position_ +=
609  (bm::set_bitscan_wave_size * 32) - bdescr->bit_.bits[--idx];
610 
612  if (decode_bit_group(bdescr))
613  {
614  return *this;
615  }
616  }
617  break;
618  case 1: // DGAP Block
619  {
620  ++this->position_;
621  if (--(bdescr->gap_.gap_len))
622  {
623  return *this;
624  }
625 
626  // next gap is "OFF" by definition.
627  if (*(bdescr->gap_.ptr) == bm::gap_max_bits - 1)
628  {
629  break;
630  }
631  gap_word_t prev = *(bdescr->gap_.ptr);
632  unsigned int val = *(++(bdescr->gap_.ptr));
633 
634  this->position_ += val - prev;
635  // next gap is now "ON"
636  if (*(bdescr->gap_.ptr) == bm::gap_max_bits - 1)
637  {
638  break;
639  }
640  prev = *(bdescr->gap_.ptr);
641  val = *(++(bdescr->gap_.ptr));
642  bdescr->gap_.gap_len = (gap_word_t)(val - prev);
643  return *this; // next "ON" found;
644  }
645  default:
646  BM_ASSERT(0);
647 
648  } // switch
649 
650  if (search_in_blocks())
651  return *this;
652 
653  this->invalidate();
654  return *this;
655  }
656 
657  /*!
658  @brief Skip to specified relative rank
659  @param rank - number of ON bits to go for
660  */
662  {
663  --rank;
664  if (!rank)
665  return *this;
666  return skip(rank);
667  }
668 
669  /*!
670  @brief Skip specified number of bits from enumeration
671  @param rank - number of ON bits to skip
672  */
674  {
675  if (!this->valid() || !rank)
676  return *this;
677  for (; rank; --rank)
678  {
679  block_descr_type* bdescr = &(this->bdescr_);
680  switch (this->block_type_)
681  {
682  case 0: // BitBlock
683  for (; rank; --rank)
684  {
685  unsigned short idx = ++(bdescr->bit_.idx);
686  if (idx < bdescr->bit_.cnt)
687  {
688  this->position_ = bdescr->bit_.pos + bdescr->bit_.bits[idx];
689  continue;
690  }
691  this->position_ +=
692  (bm::set_bitscan_wave_size * 32) - bdescr->bit_.bits[--idx];
694 
695  if (!decode_bit_group(bdescr, rank))
696  break;
697  } // for rank
698  break;
699  case 1: // DGAP Block
700  for (; rank; --rank) // TODO: better skip logic
701  {
702  ++this->position_;
703  if (--(bdescr->gap_.gap_len))
704  {
705  continue;
706  }
707 
708  // next gap is "OFF" by definition.
709  if (*(bdescr->gap_.ptr) == bm::gap_max_bits - 1)
710  {
711  break;
712  }
713  gap_word_t prev = *(bdescr->gap_.ptr);
714  unsigned int val = *(++(bdescr->gap_.ptr));
715 
716  this->position_ += val - prev;
717  // next gap is now "ON"
718  if (*(bdescr->gap_.ptr) == bm::gap_max_bits - 1)
719  {
720  break;
721  }
722  prev = *(bdescr->gap_.ptr);
723  val = *(++(bdescr->gap_.ptr));
724  bdescr->gap_.gap_len = (gap_word_t)(val - prev);
725  } // for rank
726  break;
727  default:
728  BM_ASSERT(0);
729  } // switch
730 
731  if (!rank)
732  return *this;
733 
734  if (!search_in_blocks())
735  {
736  this->invalidate();
737  return *this;
738  }
739  } // for rank
740  return *this;
741  }
742 
743  /*!
744  @brief go to a specific position in the bit-vector (or next)
745  */
747  {
748  if (pos == 0)
749  {
750  go_first();
751  return *this;
752  }
753 
754  pos = this->bv_->check_or_next(pos); // find the true pos
755  if (pos == 0) // no bits available
756  {
757  this->invalidate();
758  return *this;
759  }
760 
761  this->position_ = pos;
762  unsigned nb = this->block_idx_ = unsigned(pos >> bm::set_block_shift);
764  this->bv_->get_blocks_manager();
765  unsigned i0 = nb >> bm::set_array_shift; // top block address
766  unsigned j0 = nb & bm::set_array_mask; // address in sub-block
767  this->block_ = bman.get_block(i0, j0);
768 
769  BM_ASSERT(this->block_);
770 
771  this->block_type_ = (bool)BM_IS_GAP(this->block_);
772 
773  block_descr_type* bdescr = &(this->bdescr_);
774  unsigned nbit = unsigned(pos & bm::set_block_mask);
775 
776  if (this->block_type_) // gap
777  {
778  this->position_ = nb * bm::set_block_size * 32;
779  search_in_gapblock();
780 
781  if (this->position_ == pos)
782  {
783  return *this;
784  }
785  this->position_ = pos;
786 
787  gap_word_t* gptr = BMGAP_PTR(this->block_);
788  unsigned is_set;
789  unsigned gpos = bm::gap_bfind(gptr, nbit, &is_set);
790  BM_ASSERT(is_set);
791 
792  bdescr->gap_.ptr = gptr + gpos;
793  if (gpos == 1)
794  {
795  bdescr->gap_.gap_len = bm::gap_word_t(gptr[gpos] - (nbit - 1));
796  }
797  else
798  {
799  bm::gap_word_t interval = bm::gap_word_t(gptr[gpos] - gptr[gpos - 1]);
800  bm::gap_word_t interval2 = bm::gap_word_t(nbit - gptr[gpos - 1]);
801  bdescr->gap_.gap_len = bm::gap_word_t(interval - interval2 + 1);
802  }
803  }
804  else // bit
805  {
806  if (nbit == 0)
807  {
808  search_in_bitblock();
809  return *this;
810  }
811 
812  unsigned nword = unsigned(nbit >> bm::set_word_shift);
813 
814  // check if we need to step back to match the wave
815  unsigned parity = nword % bm::set_bitscan_wave_size;
816  bdescr->bit_.ptr = this->block_ + (nword - parity);
817  bdescr->bit_.cnt = bm::bitscan_wave(bdescr->bit_.ptr, bdescr->bit_.bits);
818  BM_ASSERT(bdescr->bit_.cnt);
819  bdescr->bit_.pos = (nb * bm::set_block_size * 32) + ((nword - parity) * 32);
820  bdescr->bit_.idx = 0;
821  nbit &= bm::set_word_mask;
822  nbit += 32 * parity;
823  for (unsigned i = 0; i < bdescr->bit_.cnt; ++i)
824  {
825  if (bdescr->bit_.bits[i] == nbit)
826  return *this;
827  bdescr->bit_.idx++;
828  } // for
829  BM_ASSERT(0);
830  }
831  return *this;
832  }
833 
834 
835  private:
837 
838 
839  bool decode_wave(block_descr_type* bdescr)
840  {
841  bdescr->bit_.cnt = bm::bitscan_wave(bdescr->bit_.ptr, bdescr->bit_.bits);
842  if (bdescr->bit_.cnt) // found
843  {
844  bdescr->bit_.idx ^= bdescr->bit_.idx; // = 0;
845  bdescr->bit_.pos = this->position_;
846  this->position_ += bdescr->bit_.bits[0];
847  return true;
848  }
849  return false;
850  }
851 
852  bool decode_bit_group(block_descr_type* bdescr)
853  {
854  const word_t* block_end = this->block_ + bm::set_block_size;
855 
856  for (; bdescr->bit_.ptr < block_end;)
857  {
858  if (decode_wave(bdescr))
859  return true;
860  this->position_ += bm::set_bitscan_wave_size * 32; // wave size
862  } // for
863  return false;
864  }
865 
866  bool decode_bit_group(block_descr_type* bdescr, bm::id_t& rank)
867  {
868  const word_t* block_end = this->block_ + bm::set_block_size;
869 
870  for (; bdescr->bit_.ptr < block_end;)
871  {
872  const bm::id64_t* w64_p = (bm::id64_t*)bdescr->bit_.ptr;
873  bm::id64_t w64 = *w64_p;
874  unsigned cnt = bm::word_bitcount64(w64);
875  if (rank > cnt)
876  {
877  rank -= cnt;
878  }
879  else
880  {
881  if (decode_wave(bdescr))
882  return true;
883  }
884  this->position_ += bm::set_bitscan_wave_size * 32; // wave size
886  } // for
887  return false;
888  }
889 
890  bool search_in_bitblock()
891  {
892  BM_ASSERT(this->block_type_ == 0);
893 
894  block_descr_type* bdescr = &(this->bdescr_);
895  bdescr->bit_.ptr = this->block_;
896 
897  return decode_bit_group(bdescr);
898  }
899 
900  bool search_in_gapblock()
901  {
902  BM_ASSERT(this->block_type_ == 1);
903 
904  block_descr_type* bdescr = &(this->bdescr_);
905 
906  bdescr->gap_.ptr = BMGAP_PTR(this->block_);
907  unsigned bitval = *(bdescr->gap_.ptr) & 1;
908 
909  ++(bdescr->gap_.ptr);
910 
911  for (;true;)
912  {
913  BMREGISTER unsigned val = *(bdescr->gap_.ptr);
914 
915  if (bitval)
916  {
917  gap_word_t* first = BMGAP_PTR(this->block_) + 1;
918  if (bdescr->gap_.ptr == first)
919  {
920  bdescr->gap_.gap_len = (gap_word_t)(val + 1);
921  }
922  else
923  {
924  bdescr->gap_.gap_len =
925  (gap_word_t)(val - *(bdescr->gap_.ptr-1));
926  }
927 
928  return true;
929  }
930  this->position_ += val + 1;
931  if (val == bm::gap_max_bits - 1)
932  {
933  break;
934  }
935  bitval ^= 1;
936  ++(bdescr->gap_.ptr);
937  }
938  return false;
939  }
940 
941  bool search_in_blocks()
942  {
943  ++(this->block_idx_);
944  unsigned i = this->block_idx_ >> bm::set_array_shift;
945  unsigned top_block_size = this->bv_->blockman_.top_block_size();
946  for (; i < top_block_size; ++i)
947  {
948  bm::word_t** blk_blk = this->bv_->blockman_.top_blocks_root()[i];
949  if (blk_blk == 0)
950  {
951  this->block_idx_ += bm::set_array_size;
952  this->position_ += bm::bits_in_array;
953  continue;
954  }
955 
956  unsigned j = this->block_idx_ & bm::set_array_mask;
957 
958  for(; j < bm::set_array_size; ++j, ++(this->block_idx_))
959  {
960  this->block_ = blk_blk[j];
961 
962  if (this->block_ == 0)
963  {
964  this->position_ += bm::bits_in_block;
965  continue;
966  }
967 
968  this->block_type_ = BM_IS_GAP(this->block_);
969  if (this->block_type_)
970  {
971  if (search_in_gapblock())
972  return true;
973  }
974  else
975  {
976  if (this->block_ == FULL_BLOCK_FAKE_ADDR)
977  this->block_ = FULL_BLOCK_REAL_ADDR;
978  if (search_in_bitblock())
979  return true;
980  }
981  } // for j
982  } // for i
983  return false;
984  }
985  };
986 
987  /*!
988  @brief Constant iterator designed to enumerate "ON" bits
989  counted_enumerator keeps bitcount, ie number of ON bits starting
990  from the position 0 in the bit string up to the currently enumerated bit
991 
992  When increment operator called current position is increased by 1.
993 
994  @ingroup bvit
995  */
997  {
998  public:
999 #ifndef BM_NO_STL
1000  typedef std::input_iterator_tag iterator_category;
1001 #endif
1002  counted_enumerator() : bit_count_(0){}
1003 
1005  : enumerator(en)
1006  {
1007  if (this->valid())
1008  bit_count_ = 1;
1009  }
1010 
1012  {
1013  enumerator* me = this;
1014  *me = en;
1015  if (this->valid())
1016  this->bit_count_ = 1;
1017  return *this;
1018  }
1019 
1021  {
1022  this->go_up();
1023  if (this->valid())
1024  ++(this->bit_count_);
1025  return *this;
1026  }
1027 
1029  {
1030  counted_enumerator tmp(*this);
1031  this->go_up();
1032  if (this->valid())
1033  ++bit_count_;
1034  return tmp;
1035  }
1036 
1037  /*! @brief Number of bits ON starting from the .
1038 
1039  Method returns number of ON bits fromn the bit 0 to the current bit
1040  For the first bit in bitvector it is 1, for the second 2
1041  */
1042  bm::id_t count() const { return bit_count_; }
1043  private:
1044  /*! Function closed for usage */
1045  counted_enumerator& go_to(bm::id_t pos);
1046 
1047  private:
1048  bm::id_t bit_count_;
1049  };
1050 
1051  /*!
1052  Resource guard for bvector<>::set_allocator_pool()
1053  @ingroup bvector
1054  @internal
1055  */
1057  {
1058  public:
1059  mem_pool_guard() : bv_(0)
1060  {}
1061 
1062  mem_pool_guard(allocator_pool_type& pool, bvector<Alloc>& bv)
1063  : bv_(&bv)
1064  {
1065  bv.set_allocator_pool(&pool);
1066  }
1068  {
1069  if (bv_)
1070  bv_->set_allocator_pool(0);
1071  }
1072 
1073  void assign_if_not_set(allocator_pool_type& pool, bvector<Alloc>& bv)
1074  {
1075  if (bv.get_allocator_pool() == 0) // alloc pool not set yet
1076  {
1077  BM_ASSERT(!bv_);
1078  bv_ = &bv;
1079  bv.set_allocator_pool(&pool);
1080  }
1081  }
1082 
1083  private:
1084  mem_pool_guard(const mem_pool_guard&) = delete;
1085  void operator=(const mem_pool_guard&) = delete;
1086  private:
1087  bvector<Alloc>* bv_; ///< garded object
1088  };
1089 
1090 
1091  friend class iterator_base;
1092  friend class enumerator;
1093  template<class BV> friend class aggregator;
1094 
1095 public:
1096  /*! @brief memory allocation policy
1097 
1098  Defualt memory allocation policy uses BM_BIT, and standard
1099  GAP levels tune-ups
1100  */
1102  {
1105 
1107  const gap_word_t* glevels = bm::gap_len_table<true>::_len)
1108  : strat(s), glevel_len(glevels)
1109  {}
1110  };
1111 
1112 
1113 
1116 public:
1117  /*! @name Construction, initialization, assignment */
1118  //@{
1119 
1120  /*!
1121  \brief Constructs bvector class
1122  \param strat - operation mode strategy,
1123  BM_BIT - default strategy, bvector use plain bitset
1124  blocks, (performance oriented strategy).
1125  BM_GAP - memory effitent strategy, bvector allocates
1126  blocks as array of intervals(gaps) and convert blocks
1127  into plain bitsets only when enthropy grows.
1128  \param glevel_len
1129  - pointer on C-style array keeping GAP block sizes.
1130  bm::gap_len_table<true>::_len - default value set
1131  (use bm::gap_len_table_min<true>::_len for very sparse vectors)
1132  (use bm::gap_len_table_nl<true>::_len non-linear GAP growth)
1133  \param bv_size
1134  - bvector size (number of bits addressable by bvector), bm::id_max means
1135  "no limits" (recommended).
1136  bit vector allocates this space dynamically on demand.
1137  \param alloc - alllocator for this instance
1138 
1139  \sa bm::gap_len_table bm::gap_len_table_min set_new_blocks_strat
1140  */
1142  const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
1143  size_type bv_size = bm::id_max,
1144  const Alloc& alloc = Alloc())
1145  : blockman_(glevel_len, bv_size, alloc),
1146  new_blocks_strat_(strat),
1147  size_(bv_size)
1148  {}
1149 
1150  /*!
1151  \brief Constructs bvector class
1152  */
1153  bvector(size_type bv_size,
1154  strategy strat = BM_BIT,
1155  const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
1156  const Alloc& alloc = Alloc())
1157  : blockman_(glevel_len, bv_size, alloc),
1158  new_blocks_strat_(strat),
1159  size_(bv_size)
1160  {}
1161 
1162  /*!
1163  \brief Copy constructor
1164  */
1166  : blockman_(bvect.blockman_),
1167  new_blocks_strat_(bvect.new_blocks_strat_),
1168  size_(bvect.size_)
1169  {}
1170 
1171  /*!
1172  \brief Copy constructor for range copy [left..right]
1173 
1174  \sa copy_range
1175  */
1177  : blockman_(bvect.blockman_.glevel_len_, bvect.blockman_.max_bits_, bvect.blockman_.alloc_),
1178  new_blocks_strat_(bvect.new_blocks_strat_),
1179  size_(bvect.size_)
1180  {
1181  if (!bvect.blockman_.is_init())
1182  return;
1183  if (left > right)
1184  bm::xor_swap(left, right);
1185  copy_range_no_check(bvect, left, right);
1186  }
1187 
1188 
1190  {}
1191  /*!
1192  \brief Explicit post-construction initialization
1193  */
1194  void init();
1195 
1196  /*!
1197  \brief Copy assignment operator
1198  */
1200  {
1201  if (this != &bvect)
1202  {
1203  blockman_.deinit_tree();
1204  blockman_.copy(bvect.blockman_);
1205  resize(bvect.size());
1206  }
1207  return *this;
1208  }
1209 
1210 #ifndef BM_NO_CXX11
1211  /*!
1212  \brief Move constructor
1213  */
1215  {
1216  blockman_.move_from(bvect.blockman_);
1217  size_ = bvect.size_;
1218  new_blocks_strat_ = bvect.new_blocks_strat_;
1219  }
1220 
1221 
1222  /*!
1223  \brief Brace constructor
1224  */
1225  bvector(std::initializer_list<bm::id_t> il)
1226  : blockman_(bm::gap_len_table<true>::_len, bm::id_max, Alloc()),
1227  new_blocks_strat_(BM_BIT),
1228  size_(bm::id_max)
1229  {
1230  init();
1231  std::initializer_list<bm::id_t>::const_iterator it_start = il.begin();
1232  std::initializer_list<bm::id_t>::const_iterator it_end = il.end();
1233  for (; it_start < it_end; ++it_start)
1234  {
1235  this->set_bit_no_check(*it_start);
1236  }
1237  }
1238 
1239  /*!
1240  \brief Move assignment operator
1241  */
1243  {
1244  this->move_from(bvect);
1245  return *this;
1246  }
1247 #endif
1248  /*!
1249  \brief Move bvector content from another bvector
1250  */
1251  void move_from(bvector<Alloc>& bvect) BMNOEXEPT;
1252 
1253  /*! \brief Exchanges content of bv and this bvector.
1254  */
1255  void swap(bvector<Alloc>& bvect) BMNOEXEPT;
1256 
1257  //@}
1258 
1259 
1260  reference operator[](bm::id_t n)
1261  {
1262  if (n >= size_)
1263  {
1264  bm::id_t new_size = (n == bm::id_max) ? bm::id_max : n + 1;
1265  resize(new_size);
1266  }
1267  return reference(*this, n);
1268  }
1269 
1270 
1271  bool operator[](bm::id_t n) const
1272  {
1273  BM_ASSERT(n < size_);
1274  return get_bit(n);
1275  }
1276 
1277  void operator &= (const bvector<Alloc>& bv)
1278  {
1279  bit_and(bv);
1280  }
1281 
1282  void operator ^= (const bvector<Alloc>& bv)
1283  {
1284  bit_xor(bv);
1285  }
1286 
1287  void operator |= (const bvector<Alloc>& bv)
1288  {
1289  bit_or(bv);
1290  }
1291 
1292  void operator -= (const bvector<Alloc>& bv)
1293  {
1294  bit_sub(bv);
1295  }
1296 
1297  bool operator < (const bvector<Alloc>& bv) const
1298  {
1299  return compare(bv) < 0;
1300  }
1301 
1302  bool operator <= (const bvector<Alloc>& bv) const
1303  {
1304  return compare(bv) <= 0;
1305  }
1306 
1307  bool operator > (const bvector<Alloc>& bv) const
1308  {
1309  return compare(bv) > 0;
1310  }
1311 
1312  bool operator >= (const bvector<Alloc>& bv) const
1313  {
1314  return compare(bv) >= 0;
1315  }
1316 
1317  bool operator == (const bvector<Alloc>& bv) const
1318  {
1319  return compare(bv) == 0;
1320  }
1321 
1322  bool operator != (const bvector<Alloc>& bv) const
1323  {
1324  return compare(bv) != 0;
1325  }
1326 
1328  {
1329  return bvector<Alloc>(*this).invert();
1330  }
1331 
1332  Alloc get_allocator() const
1333  {
1334  return blockman_.get_allocator();
1335  }
1336 
1337  /// Set allocator pool for local (non-threaded)
1338  /// memory cyclic(lots of alloc-free ops) opertations
1339  ///
1340  void set_allocator_pool(allocator_pool_type* pool_ptr)
1341  {
1342  blockman_.get_allocator().set_pool(pool_ptr);
1343  }
1344 
1345  /// Get curent allocator pool (if set)
1346  /// @return pointer to the current pool or NULL
1347  allocator_pool_type* get_allocator_pool()
1348  {
1349  return blockman_.get_allocator().get_pool();
1350  }
1351 
1352  // --------------------------------------------------------------------
1353  /*! @name Bit access/modification methods */
1354  //@{
1355 
1356  /*!
1357  \brief Sets bit n.
1358  \param n - index of the bit to be set.
1359  \param val - new bit value
1360  \return TRUE if bit was changed
1361  */
1362  bool set_bit(bm::id_t n, bool val = true)
1363  {
1364  BM_ASSERT_THROW(n < bm::id_max, BM_ERR_RANGE);
1365 
1366  if (!blockman_.is_init())
1367  blockman_.init_tree();
1368  if (n >= size_)
1369  {
1370  bm::id_t new_size = (n == bm::id_max) ? bm::id_max : n + 1;
1371  resize(new_size);
1372  }
1373 
1374  return set_bit_no_check(n, val);
1375  }
1376 
1377  /*!
1378  \brief Sets bit n using bit AND with the provided value.
1379  \param n - index of the bit to be set.
1380  \param val - new bit value
1381  \return TRUE if bit was changed
1382  */
1383  bool set_bit_and(bm::id_t n, bool val = true)
1384  {
1385  BM_ASSERT(n < size_);
1386  BM_ASSERT_THROW(n < size_, BM_ERR_RANGE);
1387 
1388  if (!blockman_.is_init())
1389  {
1390  blockman_.init_tree();
1391  }
1392  return and_bit_no_check(n, val);
1393  }
1394 
1395  /*!
1396  \brief Increment the specified element
1397 
1398  Bit increment rules:
1399  0 + 1 = 1 (no carry over)
1400  1 + 1 = 0 (with carry over returned)
1401 
1402  \param n - index of the bit to be set
1403  \return TRUE if carry over created (1+1)
1404  */
1405  bool inc(bm::id_t n);
1406 
1407 
1408  /*!
1409  \brief Sets bit n only if current value equals the condition
1410  \param n - index of the bit to be set.
1411  \param val - new bit value
1412  \param condition - expected current value
1413  \return TRUE if bit was changed
1414  */
1415  bool set_bit_conditional(bm::id_t n, bool val, bool condition)
1416  {
1417  if (val == condition) return false;
1418  if (!blockman_.is_init())
1419  blockman_.init_tree();
1420  if (n >= size_)
1421  {
1422  bm::id_t new_size = (n == bm::id_max) ? bm::id_max : n + 1;
1423  resize(new_size);
1424  }
1425 
1426  return set_bit_conditional_impl(n, val, condition);
1427  }
1428 
1429 
1430  /*!
1431  \brief Sets bit n if val is true, clears bit n if val is false
1432  \param n - index of the bit to be set
1433  \param val - new bit value
1434  \return *this
1435  */
1436  bvector<Alloc>& set(bm::id_t n, bool val = true)
1437  {
1438  set_bit(n, val);
1439  return *this;
1440  }
1441 
1442  /*!
1443  \brief Sets every bit in this bitset to 1.
1444  \return *this
1445  */
1447  {
1448  set_range(0, size_ - 1, true);
1449  return *this;
1450  }
1451 
1452  /*!
1453  \brief Set bit without checking preconditions (size, etc)
1454 
1455  Fast set bit method, without safety net.
1456  Make sure you call bvector<>::init() before setting bits with this
1457  function.
1458 
1459  \param n - bit number
1460  */
1461  void set_bit_no_check(bm::id_t n);
1462 
1463 
1464  /*!
1465  \brief Sets all bits in the specified closed interval [left,right]
1466  Interval must be inside the bvector's size.
1467  This method DOES NOT resize vector.
1468 
1469  \param left - interval start
1470  \param right - interval end (closed interval)
1471  \param value - value to set interval in
1472 
1473  \return *this
1474  */
1475  bvector<Alloc>& set_range(bm::id_t left,
1476  bm::id_t right,
1477  bool value = true);
1478 
1479  /*!
1480  \brief Copy all bits in the specified closed interval [left,right]
1481 
1482  \param bvect - source bit-vector
1483  \param left - interval start
1484  \param right - interval end (closed interval)
1485  */
1486  void copy_range(const bvector<Alloc>& bvect,
1487  bm::id_t left,
1488  bm::id_t right);
1489 
1490  /*!
1491  \brief Clears bit n.
1492  \param n - bit's index to be cleaned.
1493  \return true if bit was cleared
1494  */
1495  bool clear_bit(bm::id_t n) { return set_bit(n, false); }
1496 
1497  /*!
1498  \brief Clears bit n without precondiion checks
1499  \param n - bit's index to be cleaned.
1500  */
1501  void clear_bit_no_check(bm::id_t n) { set_bit_no_check(n, false); }
1502 
1503 
1504 
1505  /*!
1506  \brief Clears every bit in the bitvector.
1507 
1508  \param free_mem if "true" (default) bvector frees the memory,
1509  otherwise sets blocks to 0.
1510  */
1511  void clear(bool free_mem = false)
1512  {
1513  blockman_.set_all_zero(free_mem);
1514  }
1515 
1516  /*!
1517  \brief Clears every bit in the bitvector.
1518  \return *this;
1519  */
1521  {
1522  clear(true);
1523  return *this;
1524  }
1525 
1526  /*!
1527  \brief Flips bit n
1528  \return *this
1529  */
1531  {
1532  //set(n, !get_bit(n));
1533  this->inc(n);
1534  return *this;
1535  }
1536 
1537  /*!
1538  \brief Flips all bits
1539  \return *this
1540  @sa invert
1541  */
1543  {
1544  return invert();
1545  }
1546 
1547  //@}
1548  // --------------------------------------------------------------------
1549 
1550 
1551  /*! Function erturns insert iterator for this bitvector */
1552  insert_iterator inserter()
1553  {
1554  return insert_iterator(*this);
1555  }
1556 
1557  // --------------------------------------------------------------------
1558  /*! @name Size and capacity
1559  By default bvector is dynamically sized, manual control methods
1560  available
1561  */
1562  //@{
1563 
1564  /** \brief Returns bvector's capacity (number of bits it can store) */
1565  size_type capacity() const
1566  {
1567  return blockman_.capacity();
1568  }
1569 
1570  /*! \brief return current size of the vector (bits) */
1571  size_type size() const
1572  {
1573  return size_;
1574  }
1575 
1576  /*!
1577  \brief Change size of the bvector
1578  \param new_size - new size in bits
1579  */
1580  void resize(size_type new_size);
1581 
1582  //@}
1583  // --------------------------------------------------------------------
1584 
1585  /*! @name Population counting and ranking methods
1586  */
1587  //@{
1588 
1589  /*!
1590  \brief population cout (count of ON bits)
1591  \return Total number of bits ON.
1592  */
1593  bm::id_t count() const;
1594 
1595  /*! \brief Computes bitcount values for all bvector blocks
1596  \param arr - pointer on array of block bit counts
1597  \return Index of the last block counted.
1598  This number +1 gives you number of arr elements initialized during the
1599  function call.
1600  */
1601  unsigned count_blocks(unsigned* arr) const
1602  {
1603  bm::word_t*** blk_root = blockman_.top_blocks_root();
1604  if (blk_root == 0)
1605  return 0;
1606  typename blocks_manager_type::block_count_arr_func func(blockman_, &(arr[0]));
1607  for_each_nzblock(blk_root, blockman_.top_block_size(), func);
1608  return func.last_block();
1609  }
1610 
1611  /*!
1612  \brief Returns count of 1 bits in the given range
1613 
1614  \param left - index of first bit start counting from
1615  \param right - index of last bit
1616  \param block_count_arr - optional parameter (bitcount by bvector blocks)
1617  calculated by count_blocks method. Used to improve performance of
1618  wide range searches
1619  \return population count in the diapason
1620  */
1621  bm::id_t count_range(bm::id_t left,
1622  bm::id_t right,
1623  const unsigned* block_count_arr=0) const;
1624 
1625  /*! \brief compute running total of all blocks in bit vector
1626  \param blocks_cnt - out pointer to counting structure, holding the array
1627  Function will fill full array of running totals
1628  \sa count_to, select, find_rank
1629  */
1630  void running_count_blocks(rs_index_type* blocks_cnt) const;
1631 
1632  /*! \brief compute running total of all blocks in bit vector (rank-select index)
1633  \param rs_idx - [out] pointer to index / count structure
1634  Function will fill full array of running totals
1635  \sa count_to, select, find_rank
1636  */
1637  void build_rs_index(rs_index_type* rs_idx) const
1638  {
1639  running_count_blocks(rs_idx);
1640  }
1641 
1642  /*!
1643  \brief Returns count of 1 bits (population) in [0..right] range.
1644 
1645  This operation is also known as rank of bit N.
1646 
1647  \param n - index of bit to rank
1648  \param blocks_cnt - block count structure to accelerate search
1649  should be prepared using build_rs_index
1650  \return population count in the range [0..n]
1651  \sa build_rs_index
1652  \sa count_to_test, select, rank
1653  */
1654  bm::id_t count_to(bm::id_t n, const rs_index_type& blocks_cnt) const;
1655 
1656 
1657  /*!
1658  \brief Returns rank of specified bit position
1659 
1660  \param n - index of bit to rank
1661  \param rs_idx - rank-select index
1662  \return population count in the range [0..n]
1663  \sa build_rs_index
1664  \sa count_to_test, select, rank
1665  */
1666  bm::id_t rank(bm::id_t n, const rs_index_type& rs_idx) const
1667  {
1668  return count_to(n, rs_idx);
1669  }
1670 
1671 
1672 
1673  /*!
1674  \brief Returns count of 1 bits (population) in [0..right] range if test(right) == true
1675 
1676  This is conditional rank operation, which is faster than test()
1677  plus count_to()
1678 
1679  \param n - index of bit to test and rank
1680  \param blocks_cnt - block count structure to accelerate search
1681  should be prepared using running_count_blocks
1682 
1683  \return population count in the diapason or 0 if right bit test failed
1684 
1685  \sa running_count_blocks
1686  \sa count_to
1687  */
1688  bm::id_t count_to_test(bm::id_t n, const rs_index_type& blocks_cnt) const;
1689 
1690 
1691  /*! Recalculate bitcount (deprecated)
1692  */
1694  {
1695  return count();
1696  }
1697 
1698  /*!
1699  Disables count cache. (deprecated).
1700  */
1702  {
1703  }
1704  //@}
1705 
1706  // --------------------------------------------------------------------
1707  /*! @name Bit access (read-only) */
1708  //@{
1709 
1710  /*!
1711  \brief returns true if bit n is set and false is bit n is 0.
1712  \param n - Index of the bit to check.
1713  \return Bit value (1 or 0)
1714  */
1715  bool get_bit(bm::id_t n) const;
1716 
1717  /*!
1718  \brief returns true if bit n is set and false is bit n is 0.
1719  \param n - Index of the bit to check.
1720  \return Bit value (1 or 0)
1721  */
1722  bool test(bm::id_t n) const
1723  {
1724  return get_bit(n);
1725  }
1726  //@}
1727 
1728  // --------------------------------------------------------------------
1729  /*! @name Check for empty-ness of container */
1730  //@{
1731 
1732  /*!
1733  \brief Returns true if any bits in this bitset are set, and otherwise returns false.
1734  \return true if any bit is set
1735  */
1736  bool any() const
1737  {
1738  word_t*** blk_root = blockman_.top_blocks_root();
1739  if (!blk_root)
1740  return false;
1741  typename blocks_manager_type::block_any_func func(blockman_);
1742  return for_each_nzblock_if(blk_root, blockman_.top_block_size(), func);
1743  }
1744 
1745  /*!
1746  \brief Returns true if no bits are set, otherwise returns false.
1747  */
1748  bool none() const
1749  {
1750  return !any();
1751  }
1752  //@}
1753  // --------------------------------------------------------------------
1754 
1755 
1756  /*! @name Scan and find bits and indexes */
1757  //@{
1758 
1759  /*!
1760  \fn bool bvector::find(bm::id_t& pos) const
1761  \brief Finds index of first 1 bit
1762  \param pos - index of the found 1 bit
1763  \return true if search returned result
1764  \sa get_first, get_next, extract_next, find_reverse
1765  */
1766  bool find(bm::id_t& pos) const;
1767 
1768  /*!
1769  \fn bool bvector::find(bm::id_t from, bm::id_t& pos) const
1770  \brief Finds index of 1 bit starting from position
1771  \param from - position to start search from
1772  \param pos - index of the found 1 bit
1773  \return true if search returned result
1774  \sa get_first, get_next, extract_next, find_reverse
1775  */
1776  bool find(bm::id_t from, bm::id_t& pos) const;
1777 
1778  /*!
1779  \fn bm::id_t bvector::get_first() const
1780  \brief find first 1 bit in vector.
1781  Function may return 0 and this requires an extra check if bit 0 is
1782  actually set or bit-vector is empty
1783 
1784  \return Index of the first 1 bit, may return 0
1785  \sa get_next, find, extract_next, find_reverse
1786  */
1787  bm::id_t get_first() const { return check_or_next(0); }
1788 
1789  /*!
1790  \fn bm::id_t bvector::get_next(bm::id_t prev) const
1791  \brief Finds the number of the next bit ON.
1792  \param prev - Index of the previously found bit.
1793  \return Index of the next bit which is ON or 0 if not found.
1794  \sa get_first, find, extract_next, find_reverse
1795  */
1797  {
1798  return (++prev == bm::id_max) ? 0 : check_or_next(prev);
1799  }
1800 
1801  /*!
1802  \fn bm::id_t bvector::extract_next(bm::id_t prev)
1803  \brief Finds the number of the next bit ON and sets it to 0.
1804  \param prev - Index of the previously found bit.
1805  \return Index of the next bit which is ON or 0 if not found.
1806  \sa get_first, get_next, find_reverse
1807  */
1809  {
1810  return (++prev == bm::id_max) ? 0 : check_or_next_extract(prev);
1811  }
1812 
1813  /*!
1814  \brief Finds last index of 1 bit
1815  \param pos - index of the last found 1 bit
1816  \return true if search returned result
1817  \sa get_first, get_next, extract_next, find
1818  */
1819  bool find_reverse(bm::id_t& pos) const;
1820 
1821  /*!
1822  \brief Finds dynamic range of bit-vector [first, last]
1823  \param first - index of the first found 1 bit
1824  \param last - index of the last found 1 bit
1825  \return true if search returned result
1826  \sa get_first, get_next, extract_next, find, find_reverse
1827  */
1828  bool find_range(bm::id_t& first, bm::id_t& last) const;
1829 
1830  /*!
1831  \brief Find bit-vector position for the specified rank(bitcount)
1832 
1833  Rank based search, counts number of 1s from specified position until
1834  finds the ranked position relative to start from position.
1835  In other words: range population count between from and pos == rank.
1836 
1837  \param rank - rank to find (bitcount)
1838  \param from - start positioon for rank search
1839  \param pos - position with speciefied rank (relative to from position)
1840 
1841  \return true if requested rank was found
1842  */
1843  bool find_rank(bm::id_t rank, bm::id_t from, bm::id_t& pos) const;
1844 
1845 
1846  /*!
1847  \brief Find bit-vector position for the specified rank(bitcount)
1848 
1849  Rank based search, counts number of 1s from specified position until
1850  finds the ranked position relative to start from position.
1851  In other words: range population count between from and pos == rank.
1852 
1853  \param rank - rank to find (bitcount)
1854  \param from - start positioon for rank search
1855  \param pos - position with speciefied rank (relative to from position)
1856  \param blocks_cnt - block count structure to accelerate rank search
1857  should be prepared using running_count_blocks
1858 
1859  \sa running_count_blocks, select
1860 
1861  \return true if requested rank was found
1862  */
1863  bool find_rank(bm::id_t rank, bm::id_t from, bm::id_t& pos,
1864  const rs_index_type& blocks_cnt) const;
1865 
1866 
1867  /*!
1868  \brief select bit-vector position for the specified rank(bitcount)
1869 
1870  Rank based search, counts number of 1s from specified position until
1871  finds the ranked position relative to start from position.
1872  Uses
1873  In other words: range population count between from and pos == rank.
1874 
1875  \param rank - rank to find (bitcount)
1876  \param pos - position with speciefied rank (relative to from position) [out]
1877  \param blocks_cnt - block count structure to accelerate rank search
1878 
1879  \sa running_count_blocks, find_rank
1880 
1881  \return true if requested rank was found
1882  */
1883  bool select(bm::id_t rank, bm::id_t& pos, const rs_index_type& blocks_cnt) const;
1884 
1885  //@}
1886 
1887 
1888  // --------------------------------------------------------------------
1889  /*! @name Set Algebra operations */
1890  //@{
1891 
1892  /*!
1893  \brief Logical OR operation.
1894  \param vect - Argument vector.
1895  */
1897  {
1898  combine_operation_or(vect);
1899  return *this;
1900  }
1901 
1902  /*!
1903  \brief Logical AND operation.
1904  \param bv - argument vector.
1905  */
1907  {
1908  combine_operation_and(bv);
1909  return *this;
1910  }
1911 
1912  /*!
1913  \brief Logical XOR operation.
1914  \param vect - argument vector.
1915  */
1917  {
1918  combine_operation(vect, BM_XOR);
1919  return *this;
1920  }
1921 
1922  /*!
1923  \brief Logical SUB operation.
1924  \param vect - Argument vector.
1925  */
1927  {
1928  combine_operation_sub(bv);
1929  return *this;
1930  }
1931 
1932  /*!
1933  \brief Inverts all bits.
1934  */
1935  bvector<Alloc>& invert();
1936 
1937  /*! \brief perform a set-algebra operation by operation code
1938  */
1939  void combine_operation(const bm::bvector<Alloc>& bvect,
1940  bm::operation opcode);
1941 
1942  /*! \brief perform a set-algebra operation OR
1943  */
1944  void combine_operation_or(const bm::bvector<Alloc>& bvect);
1945 
1946  /*! \brief perform a set-algebra operation AND
1947  */
1948  void combine_operation_and(const bm::bvector<Alloc>& bvect);
1949 
1950  /*! \brief perform a set-algebra operation MINUS (AND NOT)
1951  */
1952  void combine_operation_sub(const bm::bvector<Alloc>& bvect);
1953 
1954  // @}
1955 
1956  // --------------------------------------------------------------------
1957  /*! @name Iterator-traversal methods */
1958  //@{
1959 
1960  /**
1961  \brief Returns enumerator pointing on the first non-zero bit.
1962  */
1963  enumerator first() const { return get_enumerator(0); }
1964 
1965  /**
1966  \fn bvector::enumerator bvector::end() const
1967  \brief Returns enumerator pointing on the next bit after the last.
1968  */
1969  enumerator end() const
1970  {
1971  typedef typename bvector<Alloc>::enumerator enumerator_type;
1972  return enumerator_type(this);
1973  }
1974 
1975  /**
1976  \brief Returns enumerator pointing on specified or the next available bit.
1977  */
1978  enumerator get_enumerator(bm::id_t pos) const
1979  {
1980  typedef typename bvector<Alloc>::enumerator enumerator_type;
1981  return enumerator_type(this, pos);
1982  }
1983 
1984  //@}
1985 
1986  // --------------------------------------------------------------------
1987  /*! @name Memory management and compression */
1988 
1989  //@{
1990 
1991  /*!
1992  @brief Calculates bitvector statistics.
1993 
1994  @param st - pointer on statistics structure to be filled in.
1995 
1996  Function fills statistics structure containing information about how
1997  this vector uses memory and estimation of max. amount of memory
1998  bvector needs to serialize itself.
1999 
2000  @sa statistics
2001  */
2002  void calc_stat(struct bm::bvector<Alloc>::statistics* st) const;
2003 
2004  /*!
2005  \brief Sets new blocks allocation strategy.
2006  \param strat - Strategy code 0 - bitblocks allocation only.
2007  1 - Blocks mutation mode (adaptive algorithm)
2008  */
2010  {
2011  new_blocks_strat_ = strat;
2012  }
2013 
2014  /*!
2015  \brief Returns blocks allocation strategy.
2016  \return - Strategy code 0 - bitblocks allocation only.
2017  1 - Blocks mutation mode (adaptive algorithm)
2018  \sa set_new_blocks_strat
2019  */
2021  {
2022  return new_blocks_strat_;
2023  }
2024 
2025  /*!
2026  \brief Optimization mode
2027  Every next level means additional checks (better compression vs time)
2028  \sa optimize
2029  */
2030  enum optmode
2031  {
2032  opt_free_0 = 1, ///< Free unused 0 blocks
2033  opt_free_01 = 2, ///< Free unused 0 and 1 blocks
2034  opt_compress = 3 ///< compress blocks when possible
2035  };
2036 
2037  /*!
2038  \brief Optimize memory bitvector's memory allocation.
2039 
2040  Function analyze all blocks in the bitvector, compresses blocks
2041  with a regular structure, frees some memory. This function is recommended
2042  after a bulk modification of the bitvector using set_bit, clear_bit or
2043  logical operations.
2044 
2045  Optionally function can calculate vector post optimization statistics
2046 
2047  @sa optmode, optimize_gap_size
2048  */
2049  void optimize(bm::word_t* temp_block = 0,
2050  optmode opt_mode = opt_compress,
2051  statistics* stat = 0);
2052 
2053  /*!
2054  \brief Optimize sizes of GAP blocks
2055 
2056  This method runs an analysis to find optimal GAP levels for the
2057  specific vector. Current GAP compression algorithm uses several fixed
2058  GAP sizes. By default bvector uses some reasonable preset.
2059  */
2060  void optimize_gap_size();
2061 
2062 
2063  /*!
2064  @brief Sets new GAP lengths table. All GAP blocks will be reallocated
2065  to match the new scheme.
2066 
2067  @param glevel_len - pointer on C-style array keeping GAP block sizes.
2068  */
2069  void set_gap_levels(const gap_word_t* glevel_len);
2070 
2071  //@}
2072 
2073  // --------------------------------------------------------------------
2074 
2075  /*! @name Comparison */
2076  //@{
2077 
2078  /*!
2079  \brief Lexicographical comparison with a bitvector.
2080 
2081  Function compares current bitvector with the provided argument
2082  bit by bit and returns -1 if our bitvector less than the argument,
2083  1 - greater, 0 - equal.
2084  */
2085  int compare(const bvector<Alloc>& bvect) const;
2086 
2087  //@}
2088 
2089  // --------------------------------------------------------------------
2090  /*! @name Open internals */
2091  //@{
2092 
2093  /*! @brief Allocates temporary block of memory.
2094 
2095  Temp block can be passed to bvector functions requiring some temp memory
2096  for their operation. (like serialize)
2097 
2098  @note method is marked const, but it's not quite true, since
2099  it can in some cases modify the state of the block allocator
2100  (if it has a state). (Can be important in MT programs).
2101 
2102  @sa free_tempblock
2103  */
2105  {
2106  blocks_manager_type* bm =
2107  const_cast<blocks_manager_type*>(&blockman_);
2108  return bm->get_allocator().alloc_bit_block();
2109  }
2110 
2111  /*! @brief Frees temporary block of memory.
2112 
2113  @note method is marked const, but it's not quite true, since
2114  it can in some cases modify the state of the block allocator
2115  (if it has a state). (Can be important in MT programs).
2116 
2117  @sa allocate_tempblock
2118  */
2119  void free_tempblock(bm::word_t* block) const
2120  {
2121  blocks_manager_type* bm =
2122  const_cast<blocks_manager_type*>(&blockman_);
2123  bm->get_allocator().free_bit_block(block);
2124  }
2125 
2126 
2127  /*!
2128  \brief get access to internal block by number
2129 
2130  This is an internal method, declared public to add low level
2131  optimized algorithms outside of the main bvector<> class.
2132  Use it AT YOUR OWN RISK!
2133 
2134  \param nb - block number
2135 
2136  \internal
2137  */
2138  const bm::word_t* get_block(unsigned nb) const
2139  {
2140  return blockman_.get_block(nb);
2141  }
2142 
2143  /*!
2144  @internal
2145  */
2147  const bm::word_t* arg_blk,
2148  bool arg_gap,
2149  bm::operation opcode)
2150  {
2151  bm::word_t* blk = const_cast<bm::word_t*>(get_block(nb));
2152  bool gap = BM_IS_GAP(blk);
2153  combine_operation_with_block(nb, gap, blk, arg_blk, arg_gap, opcode);
2154  }
2155 
2156 
2157  const blocks_manager_type& get_blocks_manager() const
2158  {
2159  return blockman_;
2160  }
2161  blocks_manager_type& get_blocks_manager()
2162  {
2163  return blockman_;
2164  }
2165 
2166  //@}
2167 
2168  static
2169  void throw_bad_alloc();
2170 
2171 private:
2172 
2173  bm::id_t check_or_next(bm::id_t prev) const;
2174 
2175  /// set bit in GAP block withlength extension control
2176  bool gap_block_set(bm::gap_word_t* gap_blk,
2177  bool val, unsigned nblock, unsigned nbit);
2178 
2179  /// check if specified bit is 1, and set it to 0
2180  /// if specified bit is 0, scan for the next 1 and returns it
2181  /// if no 1 found returns 0
2182  bm::id_t check_or_next_extract(bm::id_t prev);
2183 
2184  /**
2185  \brief Set specified bit without checking preconditions (size, etc)
2186  */
2187  bool set_bit_no_check(bm::id_t n, bool val);
2188 
2189  /**
2190  \brief AND specified bit without checking preconditions (size, etc)
2191  */
2192  bool and_bit_no_check(bm::id_t n, bool val);
2193 
2194  bool set_bit_conditional_impl(bm::id_t n, bool val, bool condition);
2195 
2196 
2197  void combine_operation_with_block(unsigned nb,
2198  bool gap,
2199  bm::word_t* blk,
2200  const bm::word_t* arg_blk,
2201  bool arg_gap,
2202  bm::operation opcode);
2203 
2204  void combine_operation_block_or(unsigned i,
2205  unsigned j,
2206  bm::word_t* blk,
2207  const bm::word_t* arg_blk);
2208 
2209  void combine_operation_block_and(unsigned i,
2210  unsigned j,
2211  bm::word_t* blk,
2212  const bm::word_t* arg_blk);
2213  void combine_operation_block_sub(unsigned i,
2214  unsigned j,
2215  bm::word_t* blk,
2216  const bm::word_t* arg_blk);
2217 
2218  void assign_gap_result(unsigned nb,
2219  const bm::gap_word_t* res,
2220  unsigned res_len,
2221  bm::word_t* blk,
2222  gap_word_t* tmp_buf);
2223 
2224  void assign_gap_result(unsigned i,
2225  unsigned j,
2226  const bm::gap_word_t* res,
2227  unsigned res_len,
2228  bm::word_t* blk,
2229  gap_word_t* tmp_buf);
2230 
2231  void copy_range_no_check(const bvector<Alloc>& bvect,
2232  bm::id_t left,
2233  bm::id_t right);
2234 
2235 private:
2236  /**
2237  \brief Extends GAP block to the next level or converts it to bit block.
2238  \param nb - Block's linear index.
2239  \param blk - Blocks's pointer
2240  */
2241  void extend_gap_block(unsigned nb, gap_word_t* blk)
2242  {
2243  blockman_.extend_gap_block(nb, blk);
2244  }
2245 
2246  /**
2247  \brief Set range without validity/bouds checking
2248  */
2249  void set_range_no_check(bm::id_t left,
2250  bm::id_t right);
2251  /**
2252  \brief Clear range without validity/bouds checking
2253  */
2254  void clear_range_no_check(bm::id_t left,
2255  bm::id_t right);
2256 
2257  /**
2258  Compute rank in block using rank-select index
2259  */
2260  static
2261  unsigned block_count_to(const bm::word_t* block,
2262  unsigned nb,
2263  unsigned nbit_right,
2264  const rs_index_type& blocks_cnt);
2265 
2266 private:
2267  blocks_manager_type blockman_; //!< bitblocks manager
2268  strategy new_blocks_strat_; //!< block allocation strategy
2269  size_type size_; //!< size in bits
2270 };
2271 
2272 
2273 
2274 
2275 
2276 //---------------------------------------------------------------------
2277 
2278 template<class Alloc>
2280  const bvector<Alloc>& v2)
2281 {
2282 #ifdef BM_USE_EXPLICIT_TEMP
2283  bvector<Alloc> ret(v1);
2284  ret.bit_and(v2);
2285  return ret;
2286 #else
2287  return bvector<Alloc>(v1).bit_and(v2);
2288 #endif
2289 }
2290 
2291 //---------------------------------------------------------------------
2292 
2293 template<class Alloc>
2295  const bvector<Alloc>& v2)
2296 {
2297 #ifdef BM_USE_EXPLICIT_TEMP
2298  bvector<Alloc> ret(v1);
2299  ret.bit_or(v2);
2300  return ret;
2301 #else
2302  return bvector<Alloc>(v1).bit_or(v2);
2303 #endif
2304 }
2305 
2306 //---------------------------------------------------------------------
2307 
2308 template<class Alloc>
2310  const bvector<Alloc>& v2)
2311 {
2312 #ifdef BM_USE_EXPLICIT_TEMP
2313  bvector<Alloc> ret(v1);
2314  ret.bit_xor(v2);
2315  return ret;
2316 #else
2317  return bvector<Alloc>(v1).bit_xor(v2);
2318 #endif
2319 }
2320 
2321 //---------------------------------------------------------------------
2322 
2323 template<class Alloc>
2325  const bvector<Alloc>& v2)
2326 {
2327 #ifdef BM_USE_EXPLICIT_TEMP
2328  bvector<Alloc> ret(v1);
2329  ret.bit_sub(v2);
2330  return ret;
2331 #else
2332  return bvector<Alloc>(v1).bit_sub(v2);
2333 #endif
2334 }
2335 
2336 
2337 // -----------------------------------------------------------------------
2338 
2339 template<typename Alloc>
2341 {
2342  if (!blockman_.is_init())
2343  blockman_.init_tree();
2344 }
2345 
2346 // -----------------------------------------------------------------------
2347 
2348 template<typename Alloc>
2350 {
2351  if (this != &bvect)
2352  {
2353  blockman_.move_from(bvect.blockman_);
2354  size_ = bvect.size_;
2355  new_blocks_strat_ = bvect.new_blocks_strat_;
2356  }
2357 }
2358 
2359 
2360 
2361 // -----------------------------------------------------------------------
2362 
2363 template<typename Alloc>
2365  bm::id_t right,
2366  bool value)
2367 {
2368  if (!blockman_.is_init())
2369  {
2370  if (!value)
2371  return *this; // nothing to do
2372  blockman_.init_tree();
2373  }
2374 
2375  if (right < left)
2376  {
2377  return set_range(right, left, value);
2378  }
2379 
2380  BM_ASSERT_THROW(right < bm::id_max, BM_ERR_RANGE);
2381  if (right >= size_) // this vect shorter than the arg.
2382  {
2383  bm::id_t new_size = (right == bm::id_max) ? bm::id_max : right + 1;
2384  resize(new_size);
2385  }
2386 
2387  BM_ASSERT(left <= right);
2388  BM_ASSERT(left < size_);
2389 
2390  if (value)
2391  set_range_no_check(left, right);
2392  else
2393  clear_range_no_check(left, right);
2394 
2395  return *this;
2396 }
2397 
2398 // -----------------------------------------------------------------------
2399 
2400 template<typename Alloc>
2402 {
2403  if (!blockman_.is_init())
2404  return 0;
2405 
2406  word_t*** blk_root = blockman_.top_blocks_root();
2407  if (!blk_root)
2408  {
2409  return 0;
2410  }
2411  typename blocks_manager_type::block_count_func func(blockman_);
2412  for_each_nzblock2(blk_root, blockman_.top_block_size(), func);
2413 
2414  return func.count();
2415 }
2416 
2417 // -----------------------------------------------------------------------
2418 
2419 template<typename Alloc>
2420 void bvector<Alloc>::resize(size_type new_size)
2421 {
2422  if (size_ == new_size) return; // nothing to do
2423  if (size_ < new_size) // size grows
2424  {
2425  if (!blockman_.is_init())
2426  blockman_.init_tree();
2427 
2428  blockman_.reserve(new_size);
2429  size_ = new_size;
2430  }
2431  else // shrink
2432  {
2433  set_range(new_size, size_ - 1, false); // clear the tail
2434  size_ = new_size;
2435  }
2436 }
2437 
2438 // -----------------------------------------------------------------------
2439 
2440 template<typename Alloc>
2441 void bvector<Alloc>::running_count_blocks(rs_index_type* blocks_cnt) const
2442 {
2443  BM_ASSERT(blocks_cnt);
2444 
2445  blocks_cnt->init();
2446 
2447  if (!blockman_.is_init())
2448  return;
2449 
2450  unsigned nb = 0;
2451  unsigned cnt = 0;
2452 
2453  for (; nb < bm::set_total_blocks; ++nb)
2454  {
2455  int no_more_blocks;
2456  const bm::word_t* block = blockman_.get_block(nb, &no_more_blocks);
2457  if (block)
2458  {
2459  cnt = blockman_.block_bitcount(block);
2460  blocks_cnt->bcount[nb] = cnt;
2461 
2462  if (BM_IS_GAP(block))
2463  {
2464  const bm::gap_word_t* const gap_block = BMGAP_PTR(block);
2465  blocks_cnt->subcount[nb].first = (bm::gap_word_t)
2467  blocks_cnt->subcount[nb].second = (bm::gap_word_t)
2468  bm::gap_bit_count_range(gap_block,
2470  bm::rs3_border1);
2471  }
2472  else
2473  {
2474  blocks_cnt->subcount[nb].first = (bm::gap_word_t)
2476  blocks_cnt->subcount[nb].second = (bm::gap_word_t)
2478  bm::rs3_border0+1,
2479  bm::rs3_border1);
2480  }
2481  }
2482  if (no_more_blocks)
2483  {
2484  blocks_cnt->total_blocks = nb;
2485  break;
2486  }
2487 
2488  } // for nb
2489 
2490  // compute running count
2491  for (unsigned i = 1; i < bm::set_total_blocks; ++i)
2492  {
2493  blocks_cnt->bcount[i] += blocks_cnt->bcount[i-1];
2494  }
2495 }
2496 // -----------------------------------------------------------------------
2497 
2498 template<typename Alloc>
2499 unsigned bvector<Alloc>::block_count_to(const bm::word_t* block,
2500  unsigned nb,
2501  unsigned nbit_right,
2502  const rs_index_type& blocks_cnt)
2503 {
2504  unsigned c;
2505 
2506  unsigned sub_range = blocks_cnt.find_sub_range(nbit_right);
2507 
2508  // evaluate 3 sub-block intervals
2509  // |--------[0]-----------[1]----------|
2510 
2511  switch(sub_range) // sub-range rank calc
2512  {
2513  case 0:
2514  // |--x-----[0]-----------[1]----------|
2515  if (nbit_right <= rs3_border0/2)
2516  {
2517  c = bm::bit_block_calc_count_to(block, nbit_right);
2518  }
2519  else
2520  {
2521  // |--------[x]-----------[1]----------|
2522  if (nbit_right == rs3_border0)
2523  {
2524  c = blocks_cnt.subcount[nb].first;
2525  }
2526  else
2527  {
2528  // |------x-[0]-----------[1]----------|
2530  nbit_right+1,
2531  rs3_border0);
2532  c = blocks_cnt.subcount[nb].first - c;
2533  }
2534  }
2535  break;
2536  case 1:
2537  // |--------[0]-x---------[1]----------|
2538  if (nbit_right <= (rs3_border0 + rs3_half_span))
2539  {
2541  rs3_border0 + 1,
2542  nbit_right);
2543  c += blocks_cnt.subcount[nb].first;
2544  }
2545  else
2546  {
2547  unsigned bc_second_range =
2548  blocks_cnt.subcount[nb].first +
2549  blocks_cnt.subcount[nb].second;
2550  // |--------[0]-----------[x]----------|
2551  if (nbit_right == rs3_border1)
2552  {
2553  c = bc_second_range;
2554  }
2555  else
2556  {
2557  // |--------[0]--------x--[1]----------|
2559  nbit_right+1,
2560  rs3_border1);
2561  c = bc_second_range - c;
2562  }
2563  }
2564  break;
2565  case 2:
2566  {
2567  unsigned bc_second_range =
2568  blocks_cnt.subcount[nb].first +
2569  blocks_cnt.subcount[nb].second;
2570 
2571  // |--------[0]-----------[1]-x--------|
2572  if (nbit_right <= (rs3_border1 + rs3_half_span))
2573  {
2575  rs3_border1 + 1,
2576  nbit_right);
2577  c += bc_second_range;
2578  }
2579  else
2580  {
2581  // |--------[0]-----------[1]----------x
2582  if (nbit_right == bm::gap_max_bits-1)
2583  {
2584  c = blocks_cnt.count(nb);
2585  }
2586  else
2587  {
2588  // |--------[0]-----------[1]-------x--|
2590  nbit_right+1,
2591  bm::gap_max_bits-1);
2592  unsigned cnt = nb ? blocks_cnt.bcount[nb-1] : 0;
2593  c = blocks_cnt.bcount[nb] - cnt - c;
2594  }
2595  }
2596  }
2597  break;
2598  default:
2599  BM_ASSERT(0);
2600  c = 0;
2601  }// switch
2602 
2603  BM_ASSERT(c == bm::bit_block_calc_count_to(block, nbit_right));
2604 
2605  return c;
2606 }
2607 
2608 // -----------------------------------------------------------------------
2609 
2610 template<typename Alloc>
2612  const rs_index_type& blocks_cnt) const
2613 {
2614  if (!blockman_.is_init())
2615  return 0;
2616 
2617  unsigned nblock_right = unsigned(right >> bm::set_block_shift);
2618  unsigned nbit_right = unsigned(right & bm::set_block_mask);
2619 
2620  // running count of all blocks before target
2621  //
2622  bm::id_t cnt = nblock_right ? blocks_cnt.bcount[nblock_right-1] : 0;
2623 
2624  const bm::word_t* block = blockman_.get_block_ptr(nblock_right);
2625  if (!block)
2626  return cnt;
2627 
2628  bool gap = BM_IS_GAP(block);
2629  if (gap)
2630  {
2631  unsigned c = bm::gap_bit_count_to(BMGAP_PTR(block), (gap_word_t)nbit_right);
2632  BM_ASSERT(c == bm::gap_bit_count_range(BMGAP_PTR(block), (gap_word_t)0, (gap_word_t)nbit_right));
2633  cnt += c;
2634  }
2635  else
2636  {
2637  if (block == FULL_BLOCK_FAKE_ADDR)
2638  {
2639  cnt += nbit_right + 1;
2640  }
2641  else // real bit-block
2642  {
2643  unsigned c =
2644  this->block_count_to(block, nblock_right, nbit_right, blocks_cnt);
2645  cnt += c;
2646  }
2647  }
2648 
2649  return cnt;
2650 }
2651 
2652 // -----------------------------------------------------------------------
2653 
2654 template<typename Alloc>
2656  const rs_index_type& blocks_cnt) const
2657 {
2658  if (!blockman_.is_init())
2659  return 0;
2660 
2661  unsigned nblock_right = unsigned(right >> bm::set_block_shift);
2662  unsigned nbit_right = unsigned(right & bm::set_block_mask);
2663 
2664  // running count of all blocks before target
2665  //
2666  bm::id_t cnt = 0;
2667 
2668  const bm::word_t* block = blockman_.get_block_ptr(nblock_right);
2669  if (!block)
2670  return 0;
2671 
2672  bool gap = BM_IS_GAP(block);
2673  if (gap)
2674  {
2675  bm::gap_word_t *gap_blk = BMGAP_PTR(block);
2676  if (bm::gap_test_unr(gap_blk, (gap_word_t)nbit_right))
2677  cnt = bm::gap_bit_count_to(gap_blk, (gap_word_t)nbit_right);
2678  else
2679  return 0;
2680  }
2681  else
2682  {
2683  if (block == FULL_BLOCK_FAKE_ADDR)
2684  {
2685  cnt = nbit_right + 1;
2686  }
2687  else
2688  {
2689  unsigned nword = nbit_right >> bm::set_word_shift;
2690  unsigned w = block[nword];
2691  w &= (1u << (nbit_right & bm::set_word_mask));
2692  if (w)
2693  {
2694  cnt = block_count_to(block, nblock_right, nbit_right, blocks_cnt);
2695  BM_ASSERT(cnt == bm::bit_block_calc_count_to(block, nbit_right));
2696  }
2697  else
2698  return 0;
2699  }
2700  }
2701  cnt += nblock_right ? blocks_cnt.bcount[nblock_right - 1] : 0;
2702  return cnt;
2703 }
2704 
2705 
2706 // -----------------------------------------------------------------------
2707 
2708 template<typename Alloc>
2710  bm::id_t right,
2711  const unsigned* block_count_arr) const
2712 {
2713  BM_ASSERT(left <= right);
2714 
2715  BM_ASSERT_THROW(right < bm::id_max, BM_ERR_RANGE);
2716  BM_ASSERT_THROW(left <= right, BM_ERR_RANGE);
2717 
2718 
2719  if (!blockman_.is_init())
2720  return 0;
2721 
2722  unsigned cnt = 0;
2723 
2724  // calculate logical number of start and destination blocks
2725  unsigned nblock_left = unsigned(left >> bm::set_block_shift);
2726  unsigned nblock_right = unsigned(right >> bm::set_block_shift);
2727 
2728  const bm::word_t* block = blockman_.get_block(nblock_left);
2729  bool left_gap = BM_IS_GAP(block);
2730 
2731  unsigned nbit_left = unsigned(left & bm::set_block_mask);
2732  unsigned nbit_right = unsigned(right & bm::set_block_mask);
2733 
2734  unsigned r =
2735  (nblock_left == nblock_right) ? nbit_right : (bm::bits_in_block-1);
2736 
2737  typename blocks_manager_type::block_count_func func(blockman_);
2738 
2739  if (block)
2740  {
2741  if ((nbit_left == 0) && (r == (bm::bits_in_block-1))) // whole block
2742  {
2743  if (block_count_arr)
2744  {
2745  cnt += block_count_arr[nblock_left];
2746  }
2747  else
2748  {
2749  func(block);//, nblock_left);
2750  }
2751  }
2752  else
2753  {
2754  if (left_gap)
2755  {
2756  cnt += gap_bit_count_range(BMGAP_PTR(block),
2757  (gap_word_t)nbit_left,
2758  (gap_word_t)r);
2759  }
2760  else
2761  {
2762  cnt += bit_block_calc_count_range(block, nbit_left, r);
2763  }
2764  }
2765  }
2766 
2767  if (nblock_left == nblock_right) // in one block
2768  {
2769  return cnt + func.count();
2770  }
2771 
2772  for (unsigned nb = nblock_left+1; nb < nblock_right; ++nb)
2773  {
2774  block = blockman_.get_block(nb);
2775  if (block_count_arr)
2776  {
2777  cnt += block_count_arr[nb];
2778  }
2779  else
2780  {
2781  if (block)
2782  func(block);//, nb);
2783  }
2784  }
2785  cnt += func.count();
2786 
2787  block = blockman_.get_block(nblock_right);
2788  bool right_gap = BM_IS_GAP(block);
2789 
2790  if (block)
2791  {
2792  if (right_gap)
2793  {
2794  cnt += gap_bit_count_range(BMGAP_PTR(block),
2795  (gap_word_t)0,
2796  (gap_word_t)nbit_right);
2797  }
2798  else
2799  {
2800  cnt += bit_block_calc_count_range(block, 0, nbit_right);
2801  }
2802  }
2803 
2804  return cnt;
2805 }
2806 
2807 // -----------------------------------------------------------------------
2808 
2809 template<typename Alloc>
2811 {
2812  blockman_.reserve_top_blocks(bm::set_array_size);
2813 
2814  bm::word_t*** blk_root = blockman_.top_blocks_root();
2815  typename blocks_manager_type::block_invert_func func(blockman_);
2816  for_each_block(blk_root, blockman_.top_block_size(), func);
2817  if (size_ == bm::id_max)
2818  {
2819  set_bit_no_check(bm::id_max, false);
2820  }
2821  else
2822  {
2823  clear_range_no_check(size_, bm::id_max);
2824  }
2825 
2826  return *this;
2827 }
2828 
2829 // -----------------------------------------------------------------------
2830 
2831 template<typename Alloc>
2833 {
2834  BM_ASSERT(n < size_);
2835  BM_ASSERT_THROW((n < size_), BM_ERR_RANGE);
2836 
2837  // calculate logical block number
2838  unsigned nblock = unsigned(n >> bm::set_block_shift);
2839  const bm::word_t* block = blockman_.get_block_ptr(nblock); // get unsanitized block ptr
2840 
2841  if (block)
2842  {
2843  // calculate word number in block and bit
2844  unsigned nbit = unsigned(n & bm::set_block_mask);
2845  if (BM_IS_GAP(block))
2846  {
2847  return gap_test_unr(BMGAP_PTR(block), nbit);
2848  }
2849  else
2850  {
2851  block = BLOCK_ADDR_SAN(block); // FULL BLOCK ADDR check
2852  unsigned nword = unsigned(nbit >> bm::set_word_shift);
2853  unsigned w = block[nword];
2854  return w & (1u << (nbit & bm::set_word_mask));
2855  }
2856  }
2857  return false;
2858 }
2859 
2860 // -----------------------------------------------------------------------
2861 
2862 template<typename Alloc>
2864  optmode opt_mode,
2865  statistics* stat)
2866 {
2867  if (!blockman_.is_init())
2868  {
2869  if (stat)
2870  calc_stat(stat);
2871  return;
2872  }
2873  word_t*** blk_root = blockman_.top_blocks_root();
2874 
2875  if (!temp_block)
2876  temp_block = blockman_.check_allocate_tempblock();
2877 
2878  typename
2879  blocks_manager_type::block_opt_func opt_func(blockman_,
2880  temp_block,
2881  (int)opt_mode,
2882  stat);
2883  if (stat)
2884  {
2885  stat->reset();
2886  ::memcpy(stat->gap_levels,
2887  blockman_.glen(), sizeof(gap_word_t) * bm::gap_levels);
2888  stat->max_serialize_mem = (unsigned)sizeof(id_t) * 4;
2889  }
2890 
2891  for_each_nzblock(blk_root, blockman_.top_block_size(), opt_func);
2892 
2893  if (stat)
2894  {
2895  size_t safe_inc = stat->max_serialize_mem / 10; // 10% increment
2896  if (!safe_inc) safe_inc = 256;
2897  stat->max_serialize_mem += safe_inc;
2898  stat->memory_used += (unsigned)(sizeof(*this) - sizeof(blockman_));
2899  stat->memory_used += blockman_.mem_used();
2900  }
2901 
2902  // the expectation is that we don't need to keep temp block if we
2903  // optimizing memory usage
2904  blockman_.free_temp_block();
2905 }
2906 
2907 // -----------------------------------------------------------------------
2908 
2909 template<typename Alloc>
2911 {
2912  if (!blockman_.is_init())
2913  return;
2914 
2915  struct bvector<Alloc>::statistics st;
2916  calc_stat(&st);
2917 
2918  if (!st.gap_blocks)
2919  return;
2920 
2921  gap_word_t opt_glen[bm::gap_levels];
2922  ::memcpy(opt_glen, st.gap_levels, bm::gap_levels * sizeof(*opt_glen));
2923 
2924  improve_gap_levels(st.gap_length,
2925  st.gap_length + st.gap_blocks,
2926  opt_glen);
2927 
2928  set_gap_levels(opt_glen);
2929 }
2930 
2931 // -----------------------------------------------------------------------
2932 
2933 template<typename Alloc>
2934 void bvector<Alloc>::set_gap_levels(const gap_word_t* glevel_len)
2935 {
2936  if (blockman_.is_init())
2937  {
2938  word_t*** blk_root = blockman_.top_blocks_root();
2939  typename
2940  blocks_manager_type::gap_level_func gl_func(blockman_, glevel_len);
2941  for_each_nzblock(blk_root, blockman_.top_block_size(),gl_func);
2942  }
2943 
2944  blockman_.set_glen(glevel_len);
2945 }
2946 
2947 // -----------------------------------------------------------------------
2948 
2949 template<typename Alloc>
2951 {
2952  int res;
2953  unsigned bn = 0;
2954 
2955  unsigned top_blocks = blockman_.top_block_size();
2956  unsigned bvect_top_blocks = bv.blockman_.top_block_size();
2957 
2958  if (bvect_top_blocks > top_blocks) top_blocks = bvect_top_blocks;
2959 
2960  for (unsigned i = 0; i < top_blocks; ++i)
2961  {
2962  const bm::word_t* const* blk_blk = blockman_.get_topblock(i);
2963  const bm::word_t* const* arg_blk_blk = bv.blockman_.get_topblock(i);
2964 
2965  if (blk_blk == arg_blk_blk)
2966  {
2967  bn += bm::set_array_size;
2968  continue;
2969  }
2970 
2971  for (unsigned j = 0; j < bm::set_array_size; ++j, ++bn)
2972  {
2973  const bm::word_t* arg_blk = arg_blk_blk ? arg_blk_blk[j] : 0;
2974  const bm::word_t* blk = blk_blk ? blk_blk[j] : 0;
2975  if (arg_blk == FULL_BLOCK_FAKE_ADDR)
2976  arg_blk = FULL_BLOCK_REAL_ADDR;
2977  if (blk == FULL_BLOCK_FAKE_ADDR)
2978  blk = FULL_BLOCK_REAL_ADDR;
2979  if (blk == arg_blk) continue;
2980 
2981  // If one block is zero we check if the other one has at least
2982  // one bit ON
2983 
2984  if (!blk || !arg_blk)
2985  {
2986  const bm::word_t* pblk;
2987  bool is_gap;
2988 
2989  if (blk)
2990  {
2991  pblk = blk;
2992  res = 1;
2993  is_gap = BM_IS_GAP(blk);
2994  }
2995  else
2996  {
2997  pblk = arg_blk;
2998  res = -1;
2999  is_gap = BM_IS_GAP(arg_blk);
3000  }
3001 
3002  if (is_gap)
3003  {
3004  if (!bm::gap_is_all_zero(BMGAP_PTR(pblk)))
3005  {
3006  return res;
3007  }
3008  }
3009  else
3010  {
3011  if (!bit_is_all_zero(pblk))
3012  {
3013  return res;
3014  }
3015  }
3016 
3017  continue;
3018  }
3019 
3020  bool arg_gap = BM_IS_GAP(arg_blk);
3021  bool gap = BM_IS_GAP(blk);
3022 
3023  if (arg_gap != gap)
3024  {
3025  BM_DECLARE_TEMP_BLOCK(temp_blk);
3026 
3027  bm::wordop_t* blk1;
3028  bm::wordop_t* blk2;
3029 
3030  if (gap)
3031  {
3032  gap_convert_to_bitset((bm::word_t*)temp_blk,
3033  BMGAP_PTR(blk));
3034 
3035  blk1 = (bm::wordop_t*)temp_blk;
3036  blk2 = (bm::wordop_t*)arg_blk;
3037  }
3038  else
3039  {
3040  gap_convert_to_bitset((bm::word_t*)temp_blk,
3041  BMGAP_PTR(arg_blk));
3042 
3043  blk1 = (bm::wordop_t*)blk;
3044  blk2 = (bm::wordop_t*)temp_blk;
3045 
3046  }
3047  res = bitcmp(blk1, blk2, bm::set_block_size_op);
3048 
3049  }
3050  else
3051  {
3052  if (gap)
3053  {
3054  res = gapcmp(BMGAP_PTR(blk), BMGAP_PTR(arg_blk));
3055  }
3056  else
3057  {
3058  res = bitcmp((bm::wordop_t*)blk,
3059  (bm::wordop_t*)arg_blk,
3061  }
3062  }
3063 
3064  if (res != 0)
3065  {
3066  return res;
3067  }
3068 
3069 
3070  } // for j
3071 
3072  } // for i
3073 
3074  return 0;
3075 }
3076 
3077 // -----------------------------------------------------------------------
3078 
3079 template<typename Alloc>
3081 {
3082  if (this != &bvect)
3083  {
3084  blockman_.swap(bvect.blockman_);
3085  bm::xor_swap(size_,bvect.size_);
3086  }
3087 }
3088 
3089 // -----------------------------------------------------------------------
3090 
3091 template<typename Alloc>
3093 {
3094  BM_ASSERT(st);
3095 
3096  st->reset();
3097  ::memcpy(st->gap_levels,
3098  blockman_.glen(), sizeof(gap_word_t) * bm::gap_levels);
3099 
3100  unsigned empty_blocks = 0;
3101 
3102  st->max_serialize_mem = unsigned(sizeof(id_t) * 4);
3103 
3104  unsigned top_size = blockman_.top_block_size();
3105  for (unsigned i = 0; i < top_size; ++i)
3106  {
3107  const bm::word_t* const* blk_blk = blockman_.get_topblock(i);
3108 
3109  if (!blk_blk)
3110  {
3111  st->max_serialize_mem += unsigned(sizeof(unsigned) + 1);
3112  continue;
3113  }
3114 
3115  for (unsigned j = 0; j < bm::set_array_size; ++j)
3116  {
3117  const bm::word_t* blk = blk_blk[j];
3118  if (IS_VALID_ADDR(blk))
3119  {
3120  st->max_serialize_mem += unsigned(empty_blocks << 2);
3121  empty_blocks = 0;
3122 
3123  if (BM_IS_GAP(blk))
3124  {
3125  bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
3126  unsigned cap = bm::gap_capacity(gap_blk, blockman_.glen());
3127  unsigned len = gap_length(gap_blk);
3128  st->add_gap_block(cap, len);
3129  }
3130  else // bit block
3131  {
3132  st->add_bit_block();
3133  }
3134  }
3135  else
3136  {
3137  ++empty_blocks;
3138  }
3139  }
3140  }
3141 
3142  size_t safe_inc = st->max_serialize_mem / 10; // 10% increment
3143  if (!safe_inc) safe_inc = 256;
3144  st->max_serialize_mem += safe_inc;
3145 
3146  // Calc size of different odd and temporary things.
3147 
3148  st->memory_used += unsigned(sizeof(*this) - sizeof(blockman_));
3149  st->memory_used += blockman_.mem_used();
3150 }
3151 
3152 // -----------------------------------------------------------------------
3153 
3154 template<class Alloc>
3156 {
3157  BM_ASSERT(blockman_.is_init());
3158  BM_ASSERT_THROW(n < bm::id_max, BM_ERR_RANGE);
3159 
3160  bool val = true; // set bit
3161 
3162  // calculate logical block number
3163  unsigned nblock = unsigned(n >> bm::set_block_shift);
3164  // calculate word number in block and bit
3165  unsigned nbit = unsigned(n & bm::set_block_mask);
3166 
3167  int block_type;
3168  bm::word_t* blk =
3169  blockman_.check_allocate_block(nblock,
3170  val,
3171  get_new_blocks_strat(),
3172  &block_type);
3173  if (!blk) return; // nothing to do
3174 
3175  if (block_type) // gap block
3176  {
3177  bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
3178  gap_block_set(gap_blk, val, nblock, nbit);
3179  }
3180  else // bit block
3181  {
3182  unsigned nword = nbit >> bm::set_word_shift;
3183  nbit &= bm::set_word_mask;
3184  blk[nword] |= (1u << nbit); // set bit
3185  }
3186 }
3187 
3188 // -----------------------------------------------------------------------
3189 
3190 
3191 template<class Alloc>
3193 {
3194  // calculate logical block number
3195  unsigned nblock = unsigned(n >> bm::set_block_shift);
3196 
3197  int block_type;
3198  bm::word_t* blk =
3199  blockman_.check_allocate_block(nblock,
3200  val,
3201  get_new_blocks_strat(),
3202  &block_type);
3203 
3204  if (!blk) return false;
3205 
3206  // calculate word number in block and bit
3207  unsigned nbit = unsigned(n & bm::set_block_mask);
3208 
3209  if (block_type) // gap
3210  {
3211  bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
3212  unsigned is_set = gap_block_set(gap_blk, val, nblock, nbit);
3213  return is_set;
3214  }
3215  else // bit block
3216  {
3217  unsigned nword = unsigned(nbit >> bm::set_word_shift);
3218  nbit &= bm::set_word_mask;
3219 
3220  bm::word_t* word = blk + nword;
3221  bm::word_t mask = (((bm::word_t)1) << nbit);
3222 
3223  if (val)
3224  {
3225  if ( ((*word) & mask) == 0 )
3226  {
3227  *word |= mask; // set bit
3228  return true;
3229  }
3230  }
3231  else
3232  {
3233  if ((*word) & mask)
3234  {
3235  *word &= ~mask; // clear bit
3236  return true;
3237  }
3238  }
3239  }
3240  return false;
3241 }
3242 
3243 // -----------------------------------------------------------------------
3244 
3245 template<class Alloc>
3247  bool val, unsigned nblock, unsigned nbit)
3248 {
3249  unsigned is_set, new_block_len;
3250  new_block_len =
3251  bm::gap_set_value(val, gap_blk, nbit, &is_set);
3252  if (is_set)
3253  {
3254  unsigned threshold = bm::gap_limit(gap_blk, blockman_.glen());
3255  if (new_block_len > threshold)
3256  {
3257  extend_gap_block(nblock, gap_blk);
3258  }
3259  }
3260  return is_set;
3261 }
3262 
3263 // -----------------------------------------------------------------------
3264 
3265 template<class Alloc>
3267 {
3268  // calculate logical block number
3269  unsigned nblock = unsigned(n >> bm::set_block_shift);
3270  bm::word_t* blk =
3271  blockman_.check_allocate_block(nblock,
3272  get_new_blocks_strat());
3273  BM_ASSERT(blk);
3274 
3275  unsigned nbit = unsigned(n & bm::set_block_mask);
3276 
3277  unsigned is_set;
3278  if (BM_IS_GAP(blk))
3279  {
3280  bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
3281  is_set = (bm::gap_test_unr(gap_blk, nbit) != 0);
3282  this->gap_block_set(gap_blk, !is_set, nblock, nbit); // flip
3283  }
3284  else // bit block
3285  {
3286  unsigned nword = unsigned(nbit >> bm::set_word_shift);
3287  nbit &= bm::set_word_mask;
3288 
3289  bm::word_t* word = blk + nword;
3290  bm::word_t mask = (((bm::word_t)1) << nbit);
3291  is_set = ((*word) & mask);
3292 
3293  *word = (is_set) ? (*word & ~mask) : (*word | mask);
3294  }
3295  return is_set;
3296 }
3297 
3298 // -----------------------------------------------------------------------
3299 
3300 template<class Alloc>
3302  bool val,
3303  bool condition)
3304 {
3305  // calculate logical block number
3306  unsigned nblock = unsigned(n >> bm::set_block_shift);
3307 
3308  int block_type;
3309  bm::word_t* blk =
3310  blockman_.check_allocate_block(nblock,
3311  val,
3312  get_new_blocks_strat(),
3313  &block_type);
3314  if (!blk)
3315  return false;
3316 
3317  // calculate word number in block and bit
3318  unsigned nbit = unsigned(n & bm::set_block_mask);
3319 
3320  if (block_type == 1) // gap
3321  {
3322  bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
3323  bool old_val = (bm::gap_test_unr(gap_blk, nbit) != 0);
3324 
3325  if (old_val != condition)
3326  {
3327  return false;
3328  }
3329 
3330  if (val != old_val)
3331  {
3332  unsigned is_set = gap_block_set(gap_blk, val, nblock, nbit);
3333  BM_ASSERT(is_set);
3334  return is_set;
3335  }
3336  }
3337  else // bit block
3338  {
3339  unsigned nword = unsigned(nbit >> bm::set_word_shift);
3340  nbit &= bm::set_word_mask;
3341 
3342  bm::word_t* word = blk + nword;
3343  bm::word_t mask = (((bm::word_t)1) << nbit);
3344  bool is_set = ((*word) & mask) != 0;
3345 
3346  if (is_set != condition)
3347  {
3348  return false;
3349  }
3350  if (is_set != val) // need to change bit
3351  {
3352  if (val) // set bit
3353  {
3354  *word |= mask;
3355  }
3356  else // clear bit
3357  {
3358  *word &= ~mask;
3359  }
3360  return true;
3361  }
3362  }
3363  return false;
3364 
3365 }
3366 
3367 // -----------------------------------------------------------------------
3368 
3369 
3370 template<class Alloc>
3372 {
3373  // calculate logical block number
3374  unsigned nblock = unsigned(n >> bm::set_block_shift);
3375 
3376  int block_type;
3377  bm::word_t* blk =
3378  blockman_.check_allocate_block(nblock,
3379  val,
3380  get_new_blocks_strat(),
3381  &block_type);
3382  if (!blk) return false;
3383 
3384  // calculate word number in block and bit
3385  unsigned nbit = unsigned(n & bm::set_block_mask);
3386 
3387  if (block_type == 1) // gap
3388  {
3389  bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
3390  bool old_val = (bm::gap_test_unr(gap_blk, nbit) != 0);
3391 
3392  bool new_val = val & old_val;
3393  if (new_val != old_val)
3394  {
3395  unsigned is_set = gap_block_set(gap_blk, val, nblock, nbit);
3396  BM_ASSERT(is_set);
3397  return is_set;
3398  }
3399  }
3400  else // bit block
3401  {
3402  unsigned nword = unsigned(nbit >> bm::set_word_shift);
3403  nbit &= bm::set_word_mask;
3404 
3405  bm::word_t* word = blk + nword;
3406  bm::word_t mask = (((bm::word_t)1) << nbit);
3407  bool is_set = ((*word) & mask) != 0;
3408 
3409  bool new_val = is_set & val;
3410  if (new_val != val) // need to change bit
3411  {
3412  if (new_val) // set bit
3413  {
3414  *word |= mask;
3415  }
3416  else // clear bit
3417  {
3418  *word &= ~mask;
3419  }
3420  return true;
3421  }
3422  }
3423  return false;
3424 }
3425 
3426 //---------------------------------------------------------------------
3427 
3428 template<class Alloc>
3430 {
3431  BM_ASSERT_THROW(from < bm::id_max, BM_ERR_RANGE);
3432 
3433  if (from == 0)
3434  {
3435  return find(pos);
3436  }
3437  pos = check_or_next(from);
3438  return (pos != 0);
3439 }
3440 
3441 //---------------------------------------------------------------------
3442 
3443 template<class Alloc>
3445 {
3446  bool found;
3447 
3448  unsigned top_blocks = blockman_.top_block_size();
3449  for (unsigned i = top_blocks-1; true; --i)
3450  {
3451  const bm::word_t* const* blk_blk = blockman_.get_topblock(i);
3452  if (blk_blk)
3453  {
3454  for (unsigned short j = bm::set_array_size-1; true; --j)
3455  {
3456  const bm::word_t* blk = blk_blk[j];
3457  if (blk)
3458  {
3459  if (blk == FULL_BLOCK_FAKE_ADDR)
3460  blk = FULL_BLOCK_REAL_ADDR;
3461 
3462  bool is_gap = BM_IS_GAP(blk);
3463  found = is_gap ? bm::gap_find_last(BMGAP_PTR(blk), &pos)
3464  : bm::bit_find_last(blk, &pos);
3465  if (found)
3466  {
3467  unsigned base_idx = i * bm::set_array_size * bm::gap_max_bits;
3468  base_idx += j * bm::gap_max_bits;
3469  pos += base_idx;
3470  return found;
3471  }
3472  }
3473 
3474  if (j == 0)
3475  break;
3476  } // for j
3477  } // if blk_blk
3478 
3479  if (i == 0)
3480  break;
3481  } // for i
3482  return false;
3483 }
3484 
3485 //---------------------------------------------------------------------
3486 
3487 template<class Alloc>
3489 {
3490  bool found;
3491 
3492  unsigned top_blocks = blockman_.top_block_size();
3493  for (unsigned short i = 0; i < top_blocks; ++i)
3494  {
3495  const bm::word_t* const* blk_blk = blockman_.get_topblock(i);
3496  if (blk_blk)
3497  {
3498  for (unsigned short j = 0; j < bm::set_array_size; ++j)
3499  {
3500  const bm::word_t* blk = blk_blk[j];
3501  if (blk)
3502  {
3503  if (blk == FULL_BLOCK_FAKE_ADDR)
3504  {
3505  found = true; pos = 0;
3506  }
3507  else
3508  {
3509  bool is_gap = BM_IS_GAP(blk);
3510  found = (is_gap) ? bm::gap_find_first(BMGAP_PTR(blk), &pos)
3511  : bm::bit_find_first(blk, &pos);
3512  }
3513  if (found)
3514  {
3515  unsigned base_idx = i * bm::set_array_size * bm::gap_max_bits;
3516  base_idx += j * bm::gap_max_bits;
3517  pos += base_idx;
3518  return found;
3519  }
3520  }
3521  } // for j
3522  } // if blk_blk
3523  } // for i
3524  return false;
3525 }
3526 
3527 //---------------------------------------------------------------------
3528 
3529 template<class Alloc>
3530 bool bvector<Alloc>::find_range(bm::id_t& in_first, bm::id_t& in_last) const
3531 {
3532  bool found = find(in_first);
3533  if (found)
3534  {
3535  found = find_reverse(in_last);
3536  BM_ASSERT(found);
3537  }
3538  return found;
3539 }
3540 
3541 //---------------------------------------------------------------------
3542 
3543 template<class Alloc>
3545 {
3546  BM_ASSERT_THROW(from < bm::id_max, BM_ERR_RANGE);
3547 
3548  bool ret = false;
3549 
3550  if (!rank || !blockman_.is_init())
3551  return ret;
3552 
3553  unsigned nb = unsigned(from >> bm::set_block_shift);
3555  unsigned bit_pos = 0;
3556 
3557  for (; nb < bm::set_total_blocks; ++nb)
3558  {
3559  int no_more_blocks;
3560  const bm::word_t* block = blockman_.get_block(nb, &no_more_blocks);
3561  if (block)
3562  {
3563  rank = bm::block_find_rank(block, rank, nbit, bit_pos);
3564  if (!rank) // target found
3565  {
3566  pos = bit_pos + (nb * bm::set_block_size * 32);
3567  return true;
3568  }
3569  }
3570  else
3571  {
3572  if (no_more_blocks)
3573  break;
3574  }
3575  nbit ^= nbit; // zero start bit after first scanned block
3576  } // for nb
3577 
3578  return ret;
3579 }
3580 
3581 //---------------------------------------------------------------------
3582 
3583 template<class Alloc>
3585  const rs_index_type& blocks_cnt) const
3586 {
3587  BM_ASSERT_THROW(from < bm::id_max, BM_ERR_RANGE);
3588 
3589  bool ret = false;
3590 
3591  if (!rank ||
3592  !blockman_.is_init() ||
3593  (blocks_cnt.bcount[blocks_cnt.total_blocks-1] < rank))
3594  return ret;
3595 
3596  unsigned nb;
3597  if (from)
3598  nb = unsigned(from >> bm::set_block_shift);
3599  else
3600  {
3601  nb = bm::lower_bound(blocks_cnt.bcount, rank, 0, blocks_cnt.total_blocks-1);
3602  BM_ASSERT(blocks_cnt.bcount[nb] >= rank);
3603  if (nb)
3604  rank -= blocks_cnt.bcount[nb-1];
3605  }
3606 
3608  unsigned bit_pos = 0;
3609 
3610  for (; nb < blocks_cnt.total_blocks; ++nb)
3611  {
3612  int no_more_blocks;
3613  const bm::word_t* block = blockman_.get_block(nb, &no_more_blocks);
3614  if (block)
3615  {
3616  if (!nbit) // check if the whole block can be skipped
3617  {
3618  unsigned block_bc = blocks_cnt.count(nb);
3619  if (rank <= block_bc) // target block
3620  {
3621  nbit = blocks_cnt.select_sub_range(nb, rank);
3622  rank = bm::block_find_rank(block, rank, nbit, bit_pos);
3623  BM_ASSERT(rank == 0);
3624  pos = bit_pos + (nb * bm::set_block_size * 32);
3625  return true;
3626  }
3627  rank -= block_bc;
3628  continue;
3629  }
3630 
3631  rank = bm::block_find_rank(block, rank, nbit, bit_pos);
3632  if (!rank) // target found
3633  {
3634  pos = bit_pos + (nb * bm::set_block_size * 32);
3635  return true;
3636  }
3637  }
3638  else
3639  {
3640  if (no_more_blocks)
3641  break;
3642  }
3643  nbit ^= nbit; // zero start bit after first scanned block
3644  } // for nb
3645 
3646  return ret;
3647 }
3648 
3649 //---------------------------------------------------------------------
3650 
3651 template<class Alloc>
3653  const rs_index_type& blocks_cnt) const
3654 {
3655  bool ret = false;
3656 
3657  if (!rank ||
3658  !blockman_.is_init() ||
3659  (blocks_cnt.bcount[bm::set_total_blocks-1] < rank))
3660  return ret;
3661 
3662  unsigned nb;
3663 
3664  nb = bm::lower_bound(blocks_cnt.bcount, rank, 0, blocks_cnt.total_blocks-1);
3665  BM_ASSERT(blocks_cnt.bcount[nb] >= rank);
3666  if (nb)
3667  rank -= blocks_cnt.bcount[nb-1];
3668 
3669  const bm::word_t* block = blockman_.get_block_ptr(nb);
3670  block = BLOCK_ADDR_SAN(block);
3671 
3672  BM_ASSERT(block);
3673  BM_ASSERT(rank <= blocks_cnt.count(nb));
3674 
3675  bm::gap_word_t nbit = blocks_cnt.select_sub_range(nb, rank);
3676  unsigned bit_pos = 0;
3677  rank = bm::block_find_rank(block, rank, nbit, bit_pos);
3678  BM_ASSERT(rank == 0);
3679  pos = bit_pos + (nb * bm::set_block_size * 32);
3680  return true;
3681 }
3682 
3683 //---------------------------------------------------------------------
3684 
3685 template<class Alloc>
3687 {
3688  if (!blockman_.is_init())
3689  return 0;
3690  for (;;)
3691  {
3692  unsigned nblock = unsigned(prev >> bm::set_block_shift);
3693  if (nblock >= bm::set_total_blocks)
3694  break;
3695 
3696  if (blockman_.is_subblock_null(nblock >> bm::set_array_shift))
3697  {
3698  prev += (bm::set_blkblk_mask + 1) - (prev & bm::set_blkblk_mask);
3699  }
3700  else
3701  {
3702  unsigned nbit = unsigned(prev & bm::set_block_mask);
3703  int no_more_blocks;
3704  const bm::word_t* block =
3705  blockman_.get_block(nblock, &no_more_blocks);
3706 
3707  if (no_more_blocks)
3708  {
3709  BM_ASSERT(block == 0);
3710  break;
3711  }
3712 
3713  if (block)
3714  {
3715  if (BM_IS_GAP(block))
3716  {
3717  if (bm::gap_find_in_block(BMGAP_PTR(block),
3718  nbit,
3719  &prev))
3720  {
3721  return prev;
3722  }
3723  }
3724  else
3725  {
3726  if (IS_FULL_BLOCK(block)) return prev;
3727  if (bm::bit_find_in_block(block, nbit, &prev))
3728  {
3729  return prev;
3730  }
3731  }
3732  }
3733  else
3734  {
3735  prev += (bm::set_block_mask + 1) - (prev & bm::set_block_mask);
3736  }
3737 
3738  }
3739  if (!prev) break;
3740  }
3741 
3742  return 0;
3743 }
3744 
3745 
3746 //---------------------------------------------------------------------
3747 
3748 template<class Alloc>
3750 {
3751  if (!blockman_.is_init())
3752  return 0;
3753 
3754  for (;;)
3755  {
3756  unsigned nblock = unsigned(prev >> bm::set_block_shift);
3757  if (nblock >= bm::set_total_blocks) break;
3758 
3759  if (blockman_.is_subblock_null(nblock >> bm::set_array_shift))
3760  {
3761  prev += (bm::set_blkblk_mask + 1) -
3762  (prev & bm::set_blkblk_mask);
3763  }
3764  else
3765  {
3766  unsigned nbit = unsigned(prev & bm::set_block_mask);
3767 
3768  int no_more_blocks;
3769  bm::word_t* block =
3770  blockman_.get_block(nblock, &no_more_blocks);
3771 
3772  if (no_more_blocks)
3773  {
3774  BM_ASSERT(block == 0);
3775  break;
3776  }
3777 
3778 
3779  if (block)
3780  {
3781  if (IS_FULL_BLOCK(block))
3782  {
3783  set(prev, false);
3784  return prev;
3785  }
3786  if (BM_IS_GAP(block))
3787  {
3788  unsigned is_set;
3789  unsigned new_block_len =
3790  gap_set_value(0, BMGAP_PTR(block), nbit, &is_set);
3791  if (is_set)
3792  {
3793  unsigned threshold =
3794  bm::gap_limit(BMGAP_PTR(block), blockman_.glen());
3795  if (new_block_len > threshold)
3796  {
3797  extend_gap_block(nblock, BMGAP_PTR(block));
3798  }
3799  return prev;
3800  }
3801  else
3802  {
3803  if (bm::gap_find_in_block(BMGAP_PTR(block),
3804  nbit,
3805  &prev))
3806  {
3807  set(prev, false);
3808  return prev;
3809  }
3810  }
3811  }
3812  else // bit block
3813  {
3814  if (bm::bit_find_in_block(block, nbit, &prev))
3815  {
3816  unsigned nbit1 =
3817  unsigned(prev & bm::set_block_mask);
3818  unsigned nword =
3819  unsigned(nbit1 >> bm::set_word_shift);
3820  nbit1 &= bm::set_word_mask;
3821  bm::word_t* word = block + nword;
3822  bm::word_t mask = ((bm::word_t)1) << nbit1;
3823  *word &= ~mask;
3824 
3825  return prev;
3826  }
3827  }
3828  }
3829  else
3830  {
3831  prev += (bm::set_block_mask + 1) -
3832  (prev & bm::set_block_mask);
3833  }
3834 
3835  }
3836  if (!prev) break;
3837  }
3838 
3839  return 0;
3840 }
3841 
3842 //---------------------------------------------------------------------
3843 
3844 #define BM_OR_OP(x) \
3845  { \
3846  blk = blk_blk[j+x]; arg_blk = blk_blk_arg[j+x]; \
3847  if (blk != arg_blk) \
3848  combine_operation_block_or(i, j+x, blk, arg_blk); \
3849  }
3850 
3851 template<class Alloc>
3853 {
3854  if (!bv.blockman_.is_init())
3855  return;
3856 
3857  unsigned top_blocks = blockman_.top_block_size();
3858  if (size_ < bv.size_) // this vect shorter than the arg.
3859  {
3860  size_ = bv.size_;
3861  }
3862  unsigned arg_top_blocks = bv.blockman_.top_block_size();
3863  top_blocks = blockman_.reserve_top_blocks(arg_top_blocks);
3864 
3865 
3866  bm::word_t*** blk_root = blockman_.top_blocks_root();
3867  bm::word_t*** blk_root_arg = bv.blockman_.top_blocks_root();
3868 
3869  for (unsigned i = 0; i < top_blocks; ++i)
3870  {
3871  bm::word_t** blk_blk = blk_root[i];
3872  bm::word_t** blk_blk_arg = (i < arg_top_blocks) ? blk_root_arg[i] : 0;
3873  if (blk_blk == blk_blk_arg || !blk_blk_arg) // nothing to do (0 OR 0 == 0)
3874  continue;
3875  if (!blk_blk)
3876  blk_blk = blockman_.alloc_top_subblock(i);
3877 
3878  unsigned j = 0;
3879  bm::word_t* blk;
3880  const bm::word_t* arg_blk;
3881  do
3882  {
3883  #if defined(BM64_AVX2) || defined(BM64_AVX512)
3884  BM_OR_OP(0)
3885  BM_OR_OP(1)
3886  BM_OR_OP(2)
3887  BM_OR_OP(3)
3888  j += 4;
3889  #elif defined(BM64_SSE4)
3890  BM_OR_OP(0)
3891  BM_OR_OP(1)
3892  j += 2;
3893  #else
3894  BM_OR_OP(0)
3895  ++j;
3896  #endif
3897  } while (j < bm::set_array_size);
3898  } // for i
3899 }
3900 
3901 #undef BM_OR_OP
3902 
3903 
3904 //---------------------------------------------------------------------
3905 
3906 #define BM_AND_OP(x) if (0 != (blk = blk_blk[j+x])) \
3907  { \
3908  if (0 != (arg_blk = blk_blk_arg[j+x])) \
3909  combine_operation_block_and(i, j+x, blk, arg_blk); \
3910  else \
3911  blockman_.zero_block(i, j+x); \
3912  }
3913 
3914 template<class Alloc>
3916 {
3917  if (!blockman_.is_init())
3918  return; // nothing to do, already empty
3919  if (!bv.blockman_.is_init())
3920  {
3921  clear(true);
3922  return;
3923  }
3924 
3925  unsigned top_blocks = blockman_.top_block_size();
3926  if (size_ < bv.size_) // this vect shorter than the arg.
3927  {
3928  size_ = bv.size_;
3929  }
3930  unsigned arg_top_blocks = bv.blockman_.top_block_size();
3931  top_blocks = blockman_.reserve_top_blocks(arg_top_blocks);
3932 
3933 
3934  bm::word_t*** blk_root = blockman_.top_blocks_root();
3935  bm::word_t*** blk_root_arg = bv.blockman_.top_blocks_root();
3936 
3937  for (unsigned i = 0; i < top_blocks; ++i)
3938  {
3939  bm::word_t** blk_blk = blk_root[i];
3940  if (!blk_blk) // nothing to do (0 AND 1 == 0)
3941  continue;
3942  bm::word_t** blk_blk_arg = (i < arg_top_blocks) ? blk_root_arg[i] : 0;
3943  if (!blk_blk_arg) // free a whole group of blocks
3944  {
3945  for (unsigned j = 0; j < bm::set_array_size; ++j)
3946  blockman_.zero_block(i, j);
3947  continue;
3948  }
3949  unsigned j = 0;
3950  bm::word_t* blk;
3951  const bm::word_t* arg_blk;
3952  do
3953  {
3954  #if defined(BM64_AVX2) || defined(BM64_AVX512)
3955  if (!avx2_test_all_zero_wave(blk_blk + j))
3956  {
3957  BM_AND_OP(0)
3958  BM_AND_OP(1)
3959  BM_AND_OP(2)
3960  BM_AND_OP(3)
3961  }
3962  j += 4;
3963  #elif defined(BM64_SSE4)
3964  if (!sse42_test_all_zero_wave(blk_blk + j))
3965  {
3966  BM_AND_OP(0)
3967  BM_AND_OP(1)
3968  }
3969  j += 2;
3970  #else
3971  BM_AND_OP(0)
3972  ++j;
3973  #endif
3974  } while (j < bm::set_array_size);
3975  } // for i
3976 }
3977 
3978 #undef BM_AND_OP
3979 
3980 
3981 //---------------------------------------------------------------------
3982 
3983 #define BM_SUB_OP(x) \
3984  if ((0 != (blk = blk_blk[j+x])) && (0 != (arg_blk = blk_blk_arg[j+x]))) \
3985  combine_operation_block_sub(i, j+x, blk, arg_blk);
3986 
3987 
3988 template<class Alloc>
3990 {
3991  if (!blockman_.is_init())
3992  return;
3993  if (!bv.blockman_.is_init())
3994  return;
3995 
3996  unsigned top_blocks = blockman_.top_block_size();
3997  if (size_ < bv.size_) // this vect shorter than the arg.
3998  {
3999  size_ = bv.size_;
4000  }
4001  unsigned arg_top_blocks = bv.blockman_.top_block_size();
4002  top_blocks = blockman_.reserve_top_blocks(arg_top_blocks);
4003 
4004  bm::word_t*** blk_root = blockman_.top_blocks_root();
4005  bm::word_t*** blk_root_arg = bv.blockman_.top_blocks_root();
4006 
4007  for (unsigned i = 0; i < top_blocks; ++i)
4008  {
4009  bm::word_t** blk_blk = blk_root[i];
4010  bm::word_t** blk_blk_arg = (i < arg_top_blocks) ? blk_root_arg[i] : 0;
4011  if (!blk_blk || !blk_blk_arg) // nothing to do (0 AND NOT 1 == 0)
4012  continue;
4013  bm::word_t* blk;
4014  const bm::word_t* arg_blk;
4015  unsigned j = 0;
4016  do
4017  {
4018  #if defined(BM64_AVX2) || defined(BM64_AVX512)
4019  if (!avx2_test_all_zero_wave(blk_blk + j))
4020  {
4021  BM_SUB_OP(0)
4022  BM_SUB_OP(1)
4023  BM_SUB_OP(2)
4024  BM_SUB_OP(3)
4025  }
4026  j += 4;
4027  #elif defined(BM64_SSE4)
4028  if (!sse42_test_all_zero_wave(blk_blk + j))
4029  {
4030  BM_SUB_OP(0)
4031  BM_SUB_OP(1)
4032  }
4033  j += 2;
4034  #else
4035  BM_SUB_OP(0)
4036  ++j;
4037  #endif
4038  } while (j < bm::set_array_size);
4039  } // for i
4040 }
4041 
4042 #undef BM_SUB_OP
4043 
4044 //---------------------------------------------------------------------
4045 
4046 template<class Alloc>
4048  const bm::bvector<Alloc>& bv,
4049  bm::operation opcode)
4050 {
4051  if (!blockman_.is_init())
4052  {
4053  if (opcode == BM_AND || opcode == BM_SUB)
4054  {
4055  return;
4056  }
4057  blockman_.init_tree();
4058  }
4059 
4060  unsigned top_blocks = blockman_.top_block_size();
4061  unsigned arg_top_blocks = bv.blockman_.top_block_size();
4062 
4063  if (arg_top_blocks > top_blocks)
4064  top_blocks = blockman_.reserve_top_blocks(arg_top_blocks);
4065 
4066  if (size_ < bv.size_) // this vect shorter than the arg.
4067  {
4068  size_ = bv.size_;
4069  // stretch our capacity
4070  blockman_.reserve_top_blocks(arg_top_blocks);
4071  top_blocks = blockman_.top_block_size();
4072  }
4073  else
4074  if (size_ > bv.size_) // this vector larger
4075  {
4076  if (opcode == BM_AND) // clear the tail with zeros
4077  {
4078  set_range(bv.size_, size_ - 1, false);
4079  if (arg_top_blocks < top_blocks)
4080  {
4081  // not to scan blocks we already swiped
4082  top_blocks = arg_top_blocks;
4083  }
4084  }
4085  }
4086 
4087  bm::word_t*** blk_root = blockman_.top_blocks_root();
4088  unsigned block_idx = 0;
4089  unsigned i, j;
4090 
4091  // calculate effective top size to avoid overscan
4092  top_blocks = blockman_.top_block_size();
4093  if (top_blocks < bv.blockman_.top_block_size())
4094  {
4095  if (opcode != BM_AND)
4096  {
4097  top_blocks = bv.blockman_.top_block_size();
4098  }
4099  }
4100 
4101  for (i = 0; i < top_blocks; ++i)
4102  {
4103  bm::word_t** blk_blk = blk_root[i];
4104  if (blk_blk == 0) // not allocated
4105  {
4106  if (opcode == BM_AND) // 0 AND anything == 0
4107  {
4108  block_idx += bm::set_array_size;
4109  continue;
4110  }
4111  const bm::word_t* const* bvbb = bv.blockman_.get_topblock(i);
4112  if (bvbb == 0) // skip it because 0 OP 0 == 0
4113  {
4114  block_idx += bm::set_array_size;
4115  continue;
4116  }
4117  // 0 - self, non-zero argument
4118  unsigned r = i * bm::set_array_size;
4119  for (j = 0; j < bm::set_array_size; ++j)
4120  {
4121  const bm::word_t* arg_blk = bv.blockman_.get_block(i, j);
4122  if (arg_blk )
4123  combine_operation_with_block(r + j,
4124  0, 0,
4125  arg_blk, BM_IS_GAP(arg_blk),
4126  opcode);
4127  } // for j
4128  continue;
4129  }
4130 
4131  if (opcode == BM_AND)
4132  {
4133  unsigned r = i * bm::set_array_size;
4134  for (j = 0; j < bm::set_array_size; ++j)
4135  {
4136  bm::word_t* blk = blk_blk[j];
4137  if (blk)
4138  {
4139  const bm::word_t* arg_blk = bv.blockman_.get_block(i, j);
4140  if (arg_blk)
4141  combine_operation_with_block(r + j,
4142  BM_IS_GAP(blk), blk,
4143  arg_blk, BM_IS_GAP(arg_blk),
4144  opcode);
4145  else
4146  blockman_.zero_block(i, j);
4147  }
4148 
4149  } // for j
4150  }
4151  else // OR, SUB, XOR
4152  {
4153  unsigned r = i * bm::set_array_size;
4154  for (j = 0; j < bm::set_array_size; ++j)
4155  {
4156  bm::word_t* blk = blk_blk[j];
4157  const bm::word_t* arg_blk = bv.blockman_.get_block(i, j);
4158  if (arg_blk || blk)
4159  combine_operation_with_block(r + j, BM_IS_GAP(blk), blk,
4160  arg_blk, BM_IS_GAP(arg_blk),
4161  opcode);
4162  } // for j
4163  }
4164  } // for i
4165 
4166 }
4167 
4168 //---------------------------------------------------------------------
4169 
4170 template<class Alloc>
4172  unsigned i, unsigned j,
4173  bm::word_t* blk, const bm::word_t* arg_blk)
4174 {
4175  bm::gap_word_t tmp_buf[bm::gap_equiv_len * 3]; // temporary result
4176  if (IS_FULL_BLOCK(blk) || !arg_blk) // all bits are set
4177  return; // nothing to do
4178 
4179  if (IS_FULL_BLOCK(arg_blk))
4180  {
4181  if (blk)
4182  blockman_.zero_block(i, j); // free target block and assign FULL
4183  blockman_.set_block_ptr(i, j, FULL_BLOCK_FAKE_ADDR);
4184  return;
4185  }
4186 
4187  if (BM_IS_GAP(blk)) // our block GAP-type
4188  {
4189  bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
4190  if (BM_IS_GAP(arg_blk)) // both blocks GAP-type
4191  {
4192  const bm::gap_word_t* res;
4193  unsigned res_len;
4194  res = bm::gap_operation_or(gap_blk,
4195  BMGAP_PTR(arg_blk),
4196  tmp_buf,
4197  res_len);
4198  BM_ASSERT(res == tmp_buf);
4200  {
4201  blockman_.zero_gap_block_ptr(i, j);
4202  blockman_.set_block_ptr(i, j, FULL_BLOCK_FAKE_ADDR);
4203  }
4204  else
4205  {
4206  assign_gap_result(i, j, res, ++res_len, blk, tmp_buf);
4207  }
4208  return;
4209  }
4210  // GAP or BIT
4211  //
4212  bm::word_t* new_blk = blockman_.get_allocator().alloc_bit_block();
4213  bm::bit_block_copy(new_blk, arg_blk); // TODO: 3 way operation
4214  bm::gap_add_to_bitset(new_blk, gap_blk);
4215 
4216  blockman_.get_allocator().free_gap_block(gap_blk, blockman_.glen());
4217  blockman_.set_block_ptr(i, j, new_blk);
4218 
4219  return;
4220  }
4221  else // our block is BITSET-type (but NOT FULL_BLOCK we checked it)
4222  {
4223  if (BM_IS_GAP(arg_blk)) // argument block is GAP-type
4224  {
4225  const bm::gap_word_t* arg_gap = BMGAP_PTR(arg_blk);
4226  if (!blk)
4227  {
4228  bool gap = true;
4229  blk = blockman_.clone_gap_block(arg_gap, gap);
4230  blockman_.set_block(i, j, blk, gap);
4231  return;
4232  }
4233 
4234  // BIT & GAP
4235  bm::gap_add_to_bitset(blk, arg_gap);
4236  return;
4237  } // if arg_gap
4238  }
4239 
4240  if (!blk)
4241  {
4242  blk = blockman_.alloc_.alloc_bit_block();
4243  bm::bit_block_copy(blk, arg_blk);
4244  blockman_.set_block_ptr(i, j, blk);
4245  return;
4246  }
4247 
4248  bool all_one = bm::bit_block_or(blk, arg_blk);
4249  if (all_one)
4250  {
4252  blockman_.get_allocator().free_bit_block(blk);
4253  blockman_.set_block_ptr(i, j, FULL_BLOCK_FAKE_ADDR);
4254  }
4255 
4256 }
4257 
4258 
4259 //---------------------------------------------------------------------
4260 
4261 
4262 template<class Alloc>
4264  unsigned i, unsigned j, bm::word_t* blk, const bm::word_t* arg_blk)
4265 {
4266  BM_ASSERT(arg_blk && blk);
4267 
4268  if (IS_FULL_BLOCK(arg_blk))
4269  return; // nothing to do
4270 
4271  gap_word_t tmp_buf[bm::gap_equiv_len * 3]; // temporary result
4272 
4273  if (BM_IS_GAP(blk)) // our block GAP-type
4274  {
4275  bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
4276  if (BM_IS_GAP(arg_blk)) // both blocks GAP-type
4277  {
4278  const bm::gap_word_t* res;
4279  unsigned res_len;
4280  res = bm::gap_operation_and(gap_blk,
4281  BMGAP_PTR(arg_blk),
4282  tmp_buf,
4283  res_len);
4284  BM_ASSERT(res == tmp_buf);
4285 
4286  if (bm::gap_is_all_zero(res))
4287  blockman_.zero_gap_block_ptr(i, j);
4288  else
4289  assign_gap_result(i, j, res, ++res_len, blk, tmp_buf);
4290  return;
4291  }
4292  // GAP & BIT
4293  //
4294  bm::word_t* new_blk = blockman_.get_allocator().alloc_bit_block();
4295  bm::bit_block_copy(new_blk, arg_blk); // TODO: 3 way operation
4296  bm::id64_t digest = bm::calc_block_digest0(new_blk);
4297 
4298  bm::gap_and_to_bitset(new_blk, gap_blk, digest);
4299 
4300  digest = bm::update_block_digest0(new_blk, digest);
4301  if (!digest)
4302  {
4303  BM_ASSERT(bm::bit_is_all_zero(new_blk));
4304  blockman_.get_allocator().free_bit_block(new_blk);
4305  new_blk = 0;
4306  }
4307  else
4308  {
4309  BM_ASSERT(!bm::bit_is_all_zero(new_blk));
4310  }
4311  blockman_.get_allocator().free_gap_block(gap_blk, blockman_.glen());
4312  blockman_.set_block_ptr(i, j, new_blk);
4313 
4314  return;
4315  }
4316  else // our block is BITSET-type or FULL_BLOCK
4317  {
4318  if (BM_IS_GAP(arg_blk)) // argument block is GAP-type
4319  {
4320  const bm::gap_word_t* arg_gap = BMGAP_PTR(arg_blk);
4321  if (bm::gap_is_all_zero(arg_gap))
4322  {
4323  blockman_.zero_block(i, j);
4324  return;
4325  }
4326  // FULL & GAP is common when AND with set_range() mask
4327  //
4328  if (IS_FULL_BLOCK(blk)) // FULL & gap = gap
4329  {
4330  bool is_new_gap;
4331  bm::word_t* new_blk = blockman_.clone_gap_block(arg_gap, is_new_gap);
4332  if (is_new_gap)
4333  BMSET_PTRGAP(new_blk);
4334 
4335  blockman_.set_block_ptr(i, j, new_blk);
4336 
4337  return;
4338  }
4339  // BIT & GAP
4340  bm::gap_and_to_bitset(blk, arg_gap);
4341  bool empty = bm::bit_is_all_zero(blk);
4342  if (empty) // operation converged bit-block to empty
4343  blockman_.zero_block(i, j);
4344 
4345  return;
4346  } // if arg_gap
4347  }
4348 
4349  // FULL & bit is common when AND with set_range() mask
4350  //
4351  if (IS_FULL_BLOCK(blk)) // FULL & bit = bit
4352  {
4353  bm::word_t* new_blk = blockman_.get_allocator().alloc_bit_block();
4354  bm::bit_block_copy(new_blk, arg_blk);
4355  blockman_.set_block_ptr(i, j, new_blk);
4356 
4357  return;
4358  }
4359  auto any_bits = bm::bit_block_and(blk, arg_blk);
4360  if (!any_bits)
4361  {
4362  blockman_.get_allocator().free_bit_block(blk);
4363  blockman_.set_block_ptr(i, j, 0);
4364  }
4365 }
4366 
4367 //---------------------------------------------------------------------
4368 
4369 template<class Alloc>
4371  unsigned i, unsigned j, bm::word_t* blk, const bm::word_t* arg_blk)
4372 {
4373  BM_ASSERT(arg_blk && blk);
4374 
4375  if (IS_FULL_BLOCK(arg_blk))
4376  {
4377  blockman_.zero_block(i, j);
4378  return;
4379  }
4380 
4381  gap_word_t tmp_buf[bm::gap_equiv_len * 3]; // temporary result
4382 
4383  if (BM_IS_GAP(blk)) // our block GAP-type
4384  {
4385  bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
4386  if (BM_IS_GAP(arg_blk)) // both blocks GAP-type
4387  {
4388  const bm::gap_word_t* res;
4389  unsigned res_len;
4390  res = bm::gap_operation_sub(gap_blk,
4391  BMGAP_PTR(arg_blk),
4392  tmp_buf,
4393  res_len);
4394 
4395  BM_ASSERT(res == tmp_buf);
4396  BM_ASSERT(!(res == tmp_buf && res_len == 0));
4397 
4398  if (bm::gap_is_all_zero(res))
4399  blockman_.zero_gap_block_ptr(i, j);
4400  else
4401  assign_gap_result(i, j, res, ++res_len, blk, tmp_buf);
4402  return;
4403  }
4404  // else: argument is BITSET-type (own block is GAP)
4405  blk = blockman_.convert_gap2bitset(i, j, gap_blk);
4406  // fall through to bit-block to bit-block operation
4407  }
4408  else // our block is BITSET-type or FULL_BLOCK
4409  {
4410  if (BM_IS_GAP(arg_blk)) // argument block is GAP-type
4411  {
4412  if (!IS_FULL_BLOCK(blk)) // gap combined to bitset
4413  {
4414  bm::gap_sub_to_bitset(blk, BMGAP_PTR(arg_blk));
4415  bool empty = bm::bit_is_all_zero(blk);
4416  if (empty) // operation converged bit-block to empty
4417  blockman_.zero_block(i, j);
4418  return;
4419  }
4420  // the worst case: convert arg block to bitset
4421  arg_blk =
4422  gap_convert_to_bitset_smart(blockman_.check_allocate_tempblock(),
4423  BMGAP_PTR(arg_blk),
4425  }
4426  }
4427 
4428  // Now here we combine two plain bitblocks using supplied bit function.
4429  bm::word_t* dst = blk;
4430 
4431  bm::word_t* ret;
4432  if (!dst || !arg_blk)
4433  return;
4434 
4435  ret = bm::bit_operation_sub(dst, arg_blk);
4436  if (ret && ret == arg_blk)
4437  {
4438  ret = blockman_.get_allocator().alloc_bit_block();
4439  bm::bit_andnot_arr_ffmask(ret, arg_blk);
4440  }
4441 
4442  if (ret != dst) // block mutation
4443  {
4444  blockman_.set_block_ptr(i, j, ret);
4445  if (IS_VALID_ADDR(dst))
4446  blockman_.get_allocator().free_bit_block(dst);
4447  }
4448 }
4449 
4450 //---------------------------------------------------------------------
4451 
4452 template<class Alloc>
4453 void
4455  bool gap,
4456  bm::word_t* blk,
4457  const bm::word_t* arg_blk,
4458  bool arg_gap,
4459  bm::operation opcode)
4460 {
4461  gap_word_t tmp_buf[bm::gap_equiv_len * 3]; // temporary result
4462  const bm::gap_word_t* res;
4463  unsigned res_len;
4464 
4465  if (opcode == BM_OR || opcode == BM_XOR)
4466  {
4467  if (!blk && arg_gap)
4468  {
4469  blk = blockman_.clone_gap_block(BMGAP_PTR(arg_blk), gap);
4470  blockman_.set_block(nb, blk, gap);
4471  return;
4472  }
4473  }
4474 
4475  if (gap) // our block GAP-type
4476  {
4477  if (arg_gap) // both blocks GAP-type
4478  {
4479  {
4480  gap_operation_func_type gfunc =
4482  BM_ASSERT(gfunc);
4483  res = (*gfunc)(BMGAP_PTR(blk),
4484  BMGAP_PTR(arg_blk),
4485  tmp_buf,
4486  res_len);
4487  }
4488  BM_ASSERT(res == tmp_buf);
4489  BM_ASSERT(!(res == tmp_buf && res_len == 0));
4490 
4491  // if as a result of the operation gap block turned to zero
4492  // we can now replace it with NULL
4493  if (gap_is_all_zero(res))
4494  blockman_.zero_block(nb);
4495  else
4496  assign_gap_result(nb, res, ++res_len, blk, tmp_buf);
4497  return;
4498  }
4499  else // argument is BITSET-type (own block is GAP)
4500  {
4501  // since we can not combine blocks of mixed type
4502  // we need to convert our block to bitset
4503 
4504  if (arg_blk == 0) // Combining against an empty block
4505  {
4506  switch (opcode)
4507  {
4508  case BM_AND: // ("Value" AND 0) == 0
4509  blockman_.zero_block(nb);
4510  return;
4511  case BM_OR: case BM_SUB: case BM_XOR:
4512  return; // nothing to do
4513  default:
4514  return; // nothing to do
4515  }
4516  }
4517  gap_word_t* gap_blk = BMGAP_PTR(blk);
4518 
4519  blk = blockman_.convert_gap2bitset(nb, gap_blk);
4520  }
4521  }
4522  else // our block is BITSET-type
4523  {
4524  if (arg_gap) // argument block is GAP-type
4525  {
4526  if (IS_VALID_ADDR(blk))
4527  {
4528  // special case, maybe we can do the job without
4529  // converting the GAP argument to bitblock
4532  BM_ASSERT(gfunc);
4533  (*gfunc)(blk, BMGAP_PTR(arg_blk));
4534 
4535  if (opcode != BM_OR)
4536  {
4537  bool b = bm::bit_is_all_zero(blk);
4538  if (b) // operation converged bit-block to empty
4539  blockman_.zero_block(nb);
4540  }
4541 
4542  return;
4543  }
4544 
4545  // the worst case we need to convert argument block to
4546  // bitset type.
4547  gap_word_t* temp_blk = (gap_word_t*) blockman_.check_allocate_tempblock();
4548  arg_blk =
4550  BMGAP_PTR(arg_blk),
4552 
4553  }
4554  }
4555 
4556  // Now here we combine two plain bitblocks using supplied bit function.
4557  bm::word_t* dst = blk;
4558 
4559  bm::word_t* ret;
4560  if (dst == 0 && arg_blk == 0)
4561  {
4562  return;
4563  }
4564 
4565  switch (opcode)
4566  {
4567  case BM_AND:
4568  ret = bit_operation_and(dst, arg_blk);
4569  goto copy_block;
4570  case BM_XOR:
4571  ret = bit_operation_xor(dst, arg_blk);
4572  if (ret && (ret == arg_blk) && IS_FULL_BLOCK(dst))
4573  {
4574  ret = blockman_.get_allocator().alloc_bit_block();
4575 #ifdef BMVECTOPT
4576  VECT_XOR_ARR_2_MASK(ret,
4577  arg_blk,
4578  arg_blk + bm::set_block_size,
4579  ~0u);
4580 #else
4581  bm::wordop_t* dst_ptr = (wordop_t*)ret;
4582  const bm::wordop_t* wrd_ptr = (wordop_t*) arg_blk;
4583  const bm::wordop_t* wrd_end =
4584  (wordop_t*) (arg_blk + bm::set_block_size);
4585 
4586  do
4587  {
4588  dst_ptr[0] = bm::all_bits_mask ^ wrd_ptr[0];
4589  dst_ptr[1] = bm::all_bits_mask ^ wrd_ptr[1];
4590  dst_ptr[2] = bm::all_bits_mask ^ wrd_ptr[2];
4591  dst_ptr[3] = bm::all_bits_mask ^ wrd_ptr[3];
4592 
4593  dst_ptr+=4;
4594  wrd_ptr+=4;
4595 
4596  } while (wrd_ptr < wrd_end);
4597 #endif
4598  break;
4599  }
4600  goto copy_block;
4601  case BM_OR:
4602  ret = bit_operation_or(dst, arg_blk);
4603  copy_block:
4604  if (ret && (ret == arg_blk) && !IS_FULL_BLOCK(ret))
4605  {
4606  ret = blockman_.get_allocator().alloc_bit_block();
4607  bit_block_copy(ret, arg_blk);
4608  }
4609  break;
4610 
4611  case BM_SUB:
4612  ret = bit_operation_sub(dst, arg_blk);
4613  if (ret && ret == arg_blk)
4614  {
4615  ret = blockman_.get_allocator().alloc_bit_block();
4616  bm::bit_andnot_arr_ffmask(ret, arg_blk);
4617  }
4618  break;
4619  default:
4620  BM_ASSERT(0);
4621  ret = 0;
4622  }
4623 
4624  if (ret != dst) // block mutation
4625  {
4626  blockman_.set_block(nb, ret);
4627  if (IS_VALID_ADDR(dst))
4628  {
4629  blockman_.get_allocator().free_bit_block(dst);
4630  }
4631  }
4632 }
4633 
4634 //---------------------------------------------------------------------
4635 
4636 template<class Alloc>
4638  unsigned nb,
4639  const bm::gap_word_t* res,
4640  unsigned res_len,
4641  bm::word_t* blk,
4642  gap_word_t* tmp_buf)
4643 {
4644  int level = bm::gap_level(BMGAP_PTR(blk));
4645  BM_ASSERT(level >= 0);
4646  unsigned threshold = unsigned(blockman_.glen(unsigned(level)) - 4u);
4647 
4648 
4649  int new_level = bm::gap_calc_level(res_len, blockman_.glen());
4650  if (new_level < 0)
4651  {
4652  blockman_.convert_gap2bitset(nb, res);
4653  return;
4654  }
4655 
4656  if (res_len > threshold)
4657  {
4658  BM_ASSERT(new_level >= 0);
4659  gap_word_t* new_blk =
4660  blockman_.allocate_gap_block(unsigned(new_level), res);
4661  bm::set_gap_level(new_blk, new_level);
4662 
4663  bm::word_t* p = (bm::word_t*)new_blk;
4664  BMSET_PTRGAP(p);
4665 
4666  if (blk)
4667  {
4668  blockman_.set_block_ptr(nb, p);
4669  blockman_.get_allocator().free_gap_block(BMGAP_PTR(blk),
4670  blockman_.glen());
4671  }
4672  else
4673  {
4674  blockman_.set_block(nb, p, true); // set GAP block
4675  }
4676  return;
4677  }
4678 
4679  // gap operation result is in the temporary buffer
4680  // we copy it back to the gap_block
4681 
4682  BM_ASSERT(blk);
4683 
4684  bm::set_gap_level(tmp_buf, level);
4685  ::memcpy(BMGAP_PTR(blk), tmp_buf, res_len * sizeof(gap_word_t));
4686 }
4687 
4688 
4689 //---------------------------------------------------------------------
4690 
4691 template<class Alloc>
4693  unsigned i,
4694  unsigned j,
4695  const bm::gap_word_t* res,
4696  unsigned res_len,
4697  bm::word_t* blk,
4698  gap_word_t* tmp_buf)
4699 {
4700  int level = bm::gap_level(BMGAP_PTR(blk));
4701  BM_ASSERT(level >= 0);
4702  unsigned threshold = unsigned(blockman_.glen(unsigned(level)) - 4u);
4703 
4704  int new_level = bm::gap_calc_level(res_len, blockman_.glen());
4705  if (new_level < 0)
4706  {
4707  blockman_.convert_gap2bitset(i, j, res);
4708  return;
4709  }
4710 
4711  if (res_len > threshold)
4712  {
4713  BM_ASSERT(new_level >= 0);
4714  gap_word_t* new_blk =
4715  blockman_.allocate_gap_block(unsigned(new_level), res);
4716  bm::set_gap_level(new_blk, new_level);
4717 
4718  bm::word_t* p = (bm::word_t*)new_blk;
4719  BMSET_PTRGAP(p);
4720 
4721  if (blk)
4722  {
4723  blockman_.set_block_ptr(i, j, p);
4724  blockman_.get_allocator().free_gap_block(BMGAP_PTR(blk),
4725  blockman_.glen());
4726  }
4727  else
4728  {
4729  blockman_.set_block(i, j, p, true); // set GAP block
4730  }
4731  return;
4732  }
4733 
4734  // gap operation result is in the temporary buffer
4735  // we copy it back to the gap_block
4736 
4737  BM_ASSERT(blk);
4738 
4739  bm::set_gap_level(tmp_buf, level);
4740  ::memcpy(BMGAP_PTR(blk), tmp_buf, res_len * sizeof(gap_word_t));
4741 }
4742 
4743 
4744 //---------------------------------------------------------------------
4745 
4746 template<class Alloc>
4748  bm::id_t right)
4749 {
4750  unsigned nblock_left = unsigned(left >> bm::set_block_shift);
4751  unsigned nblock_right = unsigned(right >> bm::set_block_shift);
4752 
4753  unsigned nbit_right = unsigned(right & bm::set_block_mask);
4754 
4755  unsigned r =
4756  (nblock_left == nblock_right) ? nbit_right :(bm::bits_in_block-1);
4757 
4758  bm::gap_word_t tmp_gap_blk[5];
4759  tmp_gap_blk[0] = 0; // just to silence GCC warning on uninit var
4760 
4761  // Set bits in the starting block
4762 
4763  unsigned nb;
4764  bm::word_t* block; //= blockman_.get_block(nblock_left);
4765  unsigned nbit_left = unsigned(left & bm::set_block_mask);
4766  if ((nbit_left == 0) && (r == bm::bits_in_block - 1)) // full block
4767  {
4768  nb = nblock_left;
4769  }
4770  else
4771  {
4772  gap_init_range_block<gap_word_t>(tmp_gap_blk,
4773  (gap_word_t)nbit_left,
4774  (gap_word_t)r,
4775  (gap_word_t)1);
4776  block = blockman_.get_block(nblock_left);
4777  combine_operation_with_block(nblock_left,
4778  BM_IS_GAP(block),
4779  block,
4780  (bm::word_t*) tmp_gap_blk,
4781  1, BM_OR);
4782 
4783  if (nblock_left == nblock_right) // in one block
4784  return;
4785  nb = nblock_left+1;
4786  }
4787 
4788  // Set all full blocks between left and right
4789  //
4790  unsigned nb_to = nblock_right + (nbit_right ==(bm::bits_in_block-1));
4791  for (; nb < nb_to; ++nb)
4792  {
4793  block = blockman_.get_block(nb);
4794  if (IS_FULL_BLOCK(block))
4795  continue;
4796  blockman_.set_block_all_set(nb);
4797  } // for
4798 
4799  if (nb_to > nblock_right)
4800  return;
4801 
4802  block = blockman_.get_block(nblock_right);
4803 
4804  gap_init_range_block<gap_word_t>(tmp_gap_blk,
4805  (gap_word_t)0,
4806  (gap_word_t)nbit_right,
4807  (gap_word_t)1);
4808 
4809  combine_operation_with_block(nblock_right,
4810  BM_IS_GAP(block),
4811  block,
4812  (bm::word_t*) tmp_gap_blk,
4813  1, BM_OR);
4814 }
4815 
4816 //---------------------------------------------------------------------
4817 
4818 template<class Alloc>
4820  bm::id_t right)
4821 {
4822  unsigned nb;
4823 
4824  // calculate logical number of start and destination blocks
4825  unsigned nblock_left = unsigned(left >> bm::set_block_shift);
4826  unsigned nblock_right = unsigned(right >> bm::set_block_shift);
4827 
4828  unsigned nbit_right = unsigned(right & bm::set_block_mask);
4829  unsigned r =
4830  (nblock_left == nblock_right) ? nbit_right : (bm::bits_in_block - 1);
4831 
4832  bm::gap_word_t tmp_gap_blk[5];
4833  tmp_gap_blk[0] = 0; // just to silence GCC warning on uninit var
4834 
4835  // Set bits in the starting block
4836  bm::word_t* block;// = blockman_.get_block(nblock_left);
4837 
4838  unsigned nbit_left = unsigned(left & bm::set_block_mask);
4839  if ((nbit_left == 0) && (r == bm::bits_in_block - 1)) // full block
4840  {
4841  nb = nblock_left;
4842  }
4843  else
4844  {
4845  bm::gap_init_range_block<gap_word_t>(tmp_gap_blk,
4846  (gap_word_t)nbit_left,
4847  (gap_word_t)r,
4848  (gap_word_t)0);
4849  block = blockman_.get_block(nblock_left);
4850  combine_operation_with_block(nblock_left,
4851  BM_IS_GAP(block),
4852  block,
4853  (bm::word_t*) tmp_gap_blk,
4854  1,
4855  BM_AND);
4856 
4857  if (nblock_left == nblock_right) // in one block
4858  return;
4859  nb = nblock_left + 1;
4860  }
4861 
4862  // Clear all full blocks between left and right
4863 
4864  unsigned nb_to = nblock_right + (nbit_right == (bm::bits_in_block - 1));
4865  for (; nb < nb_to; ++nb)
4866  {
4867  int no_more_blocks;
4868  block = blockman_.get_block(nb, &no_more_blocks);
4869  if (no_more_blocks)
4870  {
4871  BM_ASSERT(block == 0);
4872  return;
4873  }
4874  if (!block) // nothing to do
4875  continue;
4876  blockman_.zero_block(nb);
4877  } // for
4878 
4879  if (nb_to > nblock_right)
4880  return;
4881 
4882  block = blockman_.get_block(nblock_right);
4883  gap_init_range_block<gap_word_t>(tmp_gap_blk,
4884  (gap_word_t)0,
4885  (gap_word_t)nbit_right,
4886  (gap_word_t)0);
4887 
4888  combine_operation_with_block(nblock_right,
4889  BM_IS_GAP(block),
4890  block,
4891  (bm::word_t*) tmp_gap_blk,
4892  1,
4893  BM_AND);
4894 }
4895 
4896 
4897 //---------------------------------------------------------------------
4898 
4899 template<class Alloc>
4901  bm::id_t left,
4902  bm::id_t right)
4903 {
4904  if (!bvect.blockman_.is_init())
4905  {
4906  clear();
4907  return;
4908  }
4909 
4910  if (blockman_.is_init())
4911  {
4912  blockman_.deinit_tree();
4913  }
4914  if (left > right)
4915  bm::xor_swap(left, right);
4916 
4917  copy_range_no_check(bvect, left, right);
4918 }
4919 
4920 
4921 //---------------------------------------------------------------------
4922 
4923 template<class Alloc>
4925  bm::id_t left,
4926  bm::id_t right)
4927 {
4928  BM_ASSERT(left <= right);
4929  BM_ASSERT_THROW(right < bm::id_max, BM_ERR_RANGE);
4930 
4931  // copy all block(s) belonging to our range
4932  unsigned nblock_left = unsigned(left >> bm::set_block_shift);
4933  unsigned nblock_right = unsigned(right >> bm::set_block_shift);
4934 
4935  blockman_.copy(bvect.blockman_, nblock_left, nblock_right);
4936 
4937  // clear the flanks
4938  //
4939  if (left)
4940  {
4941  bm::id_t from =
4942  (left + bm::gap_max_bits >= left) ? 0u : left - bm::gap_max_bits;
4943  clear_range_no_check(from, left-1);
4944  }
4945  if (right+1 < bm::id_max)
4946  {
4947  clear_range_no_check(right+1, bm::id_max-1);
4948  }
4949 }
4950 
4951 //---------------------------------------------------------------------
4952 
4953 template<class Alloc>
4955 {
4956 #ifndef BM_NO_STL
4957  throw std::bad_alloc();
4958 #else
4959  BM_THROW(BM_ERR_BADALLOC);
4960 #endif
4961 }
4962 
4963 //---------------------------------------------------------------------
4964 //
4965 //---------------------------------------------------------------------
4966 
4967 inline
4969 {
4970  copy_from(rsi);
4971 }
4972 
4973 //---------------------------------------------------------------------
4974 
4975 inline
4977 {
4978  ::memset(this->bcount, 0, sizeof(this->bcount));
4979  ::memset(this->subcount, 0, sizeof(this->subcount));
4980 
4981  this->total_blocks = 0;
4982 }
4983 
4984 //---------------------------------------------------------------------
4985 
4986 inline
4988 {
4989  ::memcpy(this->bcount, rsi.bcount, sizeof(this->bcount));
4990  ::memcpy(this->subcount, rsi.subcount, sizeof(this->subcount));
4991  this->total_blocks = rsi.total_blocks;
4992 }
4993 
4994 //---------------------------------------------------------------------
4995 
4996 inline
4997 unsigned rs_index::count(unsigned nb) const
4998 {
4999  return (nb == 0) ? bcount[nb]
5000  : bcount[nb] - bcount[nb-1];
5001 }
5002 
5003 //---------------------------------------------------------------------
5004 
5005 inline
5006 unsigned rs_index::find_sub_range(unsigned block_bit_pos) const
5007 {
5008  return (block_bit_pos <= rs3_border0) ? 0 :
5009  (block_bit_pos > rs3_border1) ? 2 : 1;
5010 }
5011 
5012 
5013 //---------------------------------------------------------------------
5014 
5015 inline
5016 bm::gap_word_t rs_index::select_sub_range(unsigned nb, unsigned& rank) const
5017 {
5018  if (rank > this->subcount[nb].first)
5019  {
5020  rank -= this->subcount[nb].first;
5021  if (rank > this->subcount[nb].second)
5022  {
5023  rank -= this->subcount[nb].second;
5024  return rs3_border1 + 1;
5025  }
5026  else
5027  return rs3_border0 + 1;
5028  }
5029  return 0;
5030 }
5031 
5032 //---------------------------------------------------------------------
5033 
5034 
5035 } // namespace
5036 
5037 #include "bmundef.h"
5038 
5039 #ifdef _MSC_VER
5040 #pragma warning( pop )
5041 #endif
5042 
5043 
5044 #endif
Bitvector Bit-vector container with runtime compression of bits.
Definition: bm.h:136
unsigned gap_capacity(const T *buf, const T *glevel_len)
Returs GAP block capacity.
Definition: bmfunc.h:1054
memory allocation policy
Definition: bm.h:1101
bool find_rank(bm::id_t rank, bm::id_t from, bm::id_t &pos) const
Find bit-vector position for the specified rank(bitcount)
Definition: bm.h:3544
const blocks_manager_type & get_blocks_manager() const
Definition: bm.h:2157
void bit_block_copy(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
Bitblock copy operation.
Definition: bmfunc.h:4498
bvector< Alloc > & reset()
Clears every bit in the bitvector.
Definition: bm.h:1520
bm::id_t count_to_test(bm::id_t n, const rs_index_type &blocks_cnt) const
Returns count of 1 bits (population) in [0..right] range if test(right) == true.
Definition: bm.h:2655
void add_bit_block()
cound bit block
Definition: bmfunc.h:71
void combine_operation_and(const bm::bvector< Alloc > &bvect)
perform a set-algebra operation AND
Definition: bm.h:3915
unsigned gap_find_last(const T *buf, unsigned *last)
GAP block find the last set bit.
Definition: bmfunc.h:1100
bm::word_t * bit_operation_or(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
Block OR operation. Makes analysis if block is 0 or FULL.
Definition: bmfunc.h:5365
void bit_andnot_arr_ffmask(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
bitblock AND NOT with constant ~0 mask operation.
Definition: bmfunc.h:5618
unsigned block_idx_
Block index.
Definition: bm.h:358
enumerator & go_up()
Advance enumerator to the next available bit.
Definition: bm.h:588
#define BM_VECT_ALIGN
Definition: bmdef.h:293
bm::gap_word_t select_sub_range(unsigned nb, unsigned &rank) const
determine block sub-range for rank search
Definition: bm.h:5016
allocator_pool_type * get_allocator_pool()
Get curent allocator pool (if set)
Definition: bm.h:1347
counted_enumerator & operator++()
Definition: bm.h:1020
#define VECT_XOR_ARR_2_MASK(dst, src, src_end, mask)
Definition: bmsse4.h:844
bm::id_t count_range(bm::id_t left, bm::id_t right, const unsigned *block_count_arr=0) const
Returns count of 1 bits in the given range.
Definition: bm.h:2709
std::output_iterator_tag iterator_category
Definition: bm.h:387
unsigned 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:2517
const unsigned set_block_size
Definition: bmconst.h:47
void swap(bvector< Alloc > &bvect) BMNOEXEPT
Exchanges content of bv and this bvector.
Definition: bm.h:3080
operation
Bit operations enumeration.
Definition: bmfunc.h:767
bm::bvector< Alloc > & bit_or(const bm::bvector< Alloc > &vect)
Logical OR operation.
Definition: bm.h:1896
unsigned char bits[set_bitscan_wave_size *32]
bit list
Definition: bm.h:340
bvector< Alloc > operator-(const bvector< Alloc > &v1, const bvector< Alloc > &v2)
Definition: bm.h:2324
const unsigned set_word_shift
Definition: bmconst.h:59
void combine_operation_or(const bm::bvector< Alloc > &bvect)
perform a set-algebra operation OR
Definition: bm.h:3852
~bvector() BMNOEXEPT
Definition: bm.h:1189
bool test(bm::id_t n) const
returns true if bit n is set and false is bit n is 0.
Definition: bm.h:1722
bm::id_t value() const
Get current position (value)
Definition: bm.h:497
insert_iterator(bvector< Alloc > &bvect)
Definition: bm.h:396
unsigned short cnt
Number of ON bits.
Definition: bm.h:342
void optimize_gap_size()
Optimize sizes of GAP blocks.
Definition: bm.h:2910
Various constants and tables.
bool set_bit_conditional(bm::id_t n, bool val, bool condition)
Sets bit n only if current value equals the condition.
Definition: bm.h:1415
const unsigned set_array_shift
Definition: bmconst.h:78
bool compare_state(const iterator_base &ib) const
Compare FSMs for testing purposes.
Definition: bm.h:304
bvector< Alloc > operator|(const bvector< Alloc > &v1, const bvector< Alloc > &v2)
Definition: bm.h:2294
#define IS_VALID_ADDR(addr)
Definition: bmdef.h:138
Information about current bitblock.
Definition: bm.h:337
size_type capacity() const
Returns bvector&#39;s capacity (number of bits it can store)
Definition: bm.h:1565
enumerator(const bvector< Alloc > *bv)
Construct enumerator associated with a vector. This construction creates unpositioned iterator with s...
Definition: bm.h:471
size_type size() const
return current size of the vector (bits)
Definition: bm.h:1571
unsigned gap_set_value(unsigned val, T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set)
Sets or clears bit in the GAP buffer.
Definition: bmfunc.h:2246
unsigned count(unsigned nb) const
return bit-count for specified block
Definition: bm.h:4997
unsigned long long int id64_t
Definition: bmconst.h:31
gap_word_t gap_len
Current dgap length.
Definition: bm.h:350
void assign_if_not_set(allocator_pool_type &pool, bvector< Alloc > &bv)
Definition: bm.h:1073
enumerator operator++(int)
Advance enumerator forward to the next available bit. Possibly do NOT use this operator it is slower ...
Definition: bm.h:510
gap_word_t * gap_operation_sub(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize)
GAP SUB (AND NOT) operation.
Definition: bmfunc.h:4435
bm::id_t size_type
Definition: bm.h:142
void go_first()
Position enumerator to the first available bit.
Definition: bm.h:519
void optimize(bm::word_t *temp_block=0, optmode opt_mode=opt_compress, statistics *stat=0)
Optimize memory bitvector&#39;s memory allocation.
Definition: bm.h:2863
rs_index()
Definition: bm.h:108
unsigned total_blocks
Definition: bm.h:106
void invalidate()
Turns iterator into an invalid state.
Definition: bm.h:296
const unsigned short set_bitscan_wave_size
Definition: bmfunc.h:6555
Rank-Select acceleration index.
Definition: bm.h:102
Definition: bm.h:70
T gap_length(const T *buf)
Returs GAP block length.
Definition: bmfunc.h:1039
insert_iterator inserter()
Definition: bm.h:1552
const unsigned gap_equiv_len
Definition: bmconst.h:69
counted_enumerator(const enumerator &en)
Definition: bm.h:1004
insert_iterator(const insert_iterator &iit)
Definition: bm.h:403
bvector(bvector< Alloc > &&bvect) BMNOEXEPT
Move constructor.
Definition: bm.h:1214
size_t max_serialize_mem
Estimated maximum of memory required for serialization.
Definition: bmfunc.h:61
void gap_convert_to_bitset(unsigned *dest, const T *buf)
GAP block to bitblock conversion.
Definition: bmfunc.h:3196
bool const_reference
Definition: bm.h:240
pre-processor un-defines to avoid global space pollution (internal)
bm::bvector< Alloc > & bit_xor(const bm::bvector< Alloc > &vect)
Logical XOR operation.
Definition: bm.h:1916
bm::id_t count() const
Number of bits ON starting from the .
Definition: bm.h:1042
const bm::word_t * ptr
Word pointer.
Definition: bm.h:339
enumerator & skip(bm::id_t rank)
Skip specified number of bits from enumeration.
Definition: bm.h:673
#define BMNOEXEPT
Definition: bmdef.h:78
bvector< Alloc > operator^(const bvector< Alloc > &v1, const bvector< Alloc > &v2)
Definition: bm.h:2309
bool operator==(const iterator_base &it) const
Definition: bm.h:252
const bm::word_t * block_
Block pointer.(NULL-invalid)
Definition: bm.h:356
bm::word_t * bit_operation_sub(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
bitblock SUB operation.
Definition: bmfunc.h:5526
insert_iterator & operator++(int)
Definition: bm.h:441
int(* bit_visitor_callback_type)(void *handle_ptr, bm::id_t bit_idx)
Callback type to visit (callback style) bits in bit-vector(s)
Definition: bm.h:66
const reference & operator|=(bool value) const
Definition: bm.h:200
enumerator(const bvector< Alloc > *bv, bm::id_t pos)
Construct enumerator for bit vector.
Definition: bm.h:483
SIMD target version definitions.
void set_new_blocks_strat(strategy strat)
Sets new blocks allocation strategy.
Definition: bm.h:2009
bitblock_descr bit_
BitBlock related info.
Definition: bm.h:363
bool bit_block_or(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
Plain bitblock OR operation. Function does not analyse availability of source and destination blocks...
Definition: bmfunc.h:5235
reference(const reference &ref)
Definition: bm.h:163
void xor_swap(W &x, W &y)
XOR swap two scalar variables.
Definition: bmfunc.h:857
bool set_bit_and(bm::id_t n, bool val=true)
Sets bit n using bit AND with the provided value.
Definition: bm.h:1383
bool for_each_nzblock_if(T ***root, unsigned size1, F &f)
Definition: bmfunc.h:1518
void running_count_blocks(rs_index_type *blocks_cnt) const
compute running total of all blocks in bit vector
Definition: bm.h:2441
bvector< Alloc > operator &(const bvector< Alloc > &v1, const bvector< Alloc > &v2)
Definition: bm.h:2279
unsigned short idx
Current position in the bit list.
Definition: bm.h:341
int compare(const bvector< Alloc > &bvect) const
Lexicographical comparison with a bitvector.
Definition: bm.h:2950
Constant 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:996
const unsigned id_max
Definition: bmconst.h:43
#define BM_DECLARE_TEMP_BLOCK(x)
Definition: bm.h:48
rs_index blocks_count
Definition: bm.h:1114
Statistical information about bitset&#39;s memory allocation details.
Definition: bm.h:145
bm::id_t operator*() const
Get current position (value)
Definition: bm.h:491
bool find(bm::id_t &pos) const
Finds index of first 1 bit.
Definition: bm.h:3488
bm::id_t get_next(bm::id_t prev) const
Finds the number of the next bit ON.
Definition: bm.h:1796
#define BM_SUB_OP(x)
Definition: bm.h:3983
counted_enumerator & operator=(const enumerator &en)
Definition: bm.h:1011
const unsigned rs3_border1
Definition: bmconst.h:87
void forget_count()
Definition: bm.h:1701
#define BMSET_PTRGAP(ptr)
Definition: bmdef.h:166
const unsigned rs3_border0
Definition: bmconst.h:86
void combine_operation_sub(const bm::bvector< Alloc > &bvect)
perform a set-algebra operation MINUS (AND NOT)
Definition: bm.h:3989
void gap_and_to_bitset(unsigned *dest, const T *pcurr)
ANDs GAP block to bitblock.
Definition: bmfunc.h:2852
unsigned gap_bit_count_to(const T *const buf, T right)
Counts 1 bits in GAP buffer in the closed [0, right] range.
Definition: bmfunc.h:1799
bvector< Alloc > & flip()
Flips all bits.
Definition: bm.h:1542
const reference & operator=(bool value) const
Definition: bm.h:181
bvector< Alloc > operator~() const
Definition: bm.h:1327
unsigned lower_bound(const unsigned *arr, unsigned target, unsigned from, unsigned to)
Hybrid, binary-linear lower bound search in unsigned array.
Definition: bmfunc.h:6714
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:5804
BMFORCEINLINE bool gap_is_all_zero(const bm::gap_word_t *buf)
Checks if GAP block is all-zero.
Definition: bmfunc.h:1009
size_t memory_used
Memory used by bitvector including temp and service blocks.
Definition: bmfunc.h:63
Alloc allocator_type
Definition: bm.h:139
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
Definition: bm.h:1963
void clear_bit_no_check(bm::id_t n)
Clears bit n without precondiion checks.
Definition: bm.h:1501
int bitcmp(const T *buf1, const T *buf2, unsigned len)
Lexicographical comparison of BIT buffers.
Definition: bmfunc.h:3435
bm::id_t pos
Last bit position decode before.
Definition: bm.h:343
unsigned & reference
Definition: bm.h:461
bm::id_t block_find_rank(const bm::word_t *const block, bm::id_t rank, unsigned nbit_from, unsigned &nbit_pos)
Find rank in block (GAP or BIT)
Definition: bmfunc.h:5992
unsigned bit_find_last(const bm::word_t *block, unsigned *last)
BIT block find the last set bit (backward search)
Definition: bmfunc.h:5850
reference & flip()
Definition: bm.h:229
unsigned int word_t
Definition: bmconst.h:35
void free_tempblock(bm::word_t *block) const
Frees temporary block of memory.
Definition: bm.h:2119
bvector(const bvector< Alloc > &bvect)
Copy constructor.
Definition: bm.h:1165
BMFORCEINLINE void set_bit(unsigned *dest, unsigned bitpos)
Set 1 bit in a block.
Definition: bmfunc.h:2543
#define IS_FULL_BLOCK(addr)
Definition: bmdef.h:139
bm::id_t get_first() const
find first 1 bit in vector. Function may return 0 and this requires an extra check if bit 0 is actual...
Definition: bm.h:1787
#define BMREGISTER
Definition: bmdef.h:86
insert_iterator & operator=(bm::id_t n)
Definition: bm.h:417
void for_each_nzblock2(T ***root, unsigned size1, F &f)
Definition: bmfunc.h:1420
bool select(bm::id_t rank, bm::id_t &pos, const rs_index_type &blocks_cnt) const
select bit-vector position for the specified rank(bitcount)
Definition: bm.h:3652
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:1141
bool bit_is_all_zero(const bm::word_t *BMRESTRICT start)
Returns "true" if all bits in the block are 0.
Definition: bmfunc.h:982
Default SIMD friendly allocator.
allocation_policy(bm::strategy s=BM_BIT, const gap_word_t *glevels=bm::gap_len_table< true >::_len)
Definition: bm.h:1106
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&#39;s siz...
Definition: bm.h:2364
const gap_word_t * glevel_len
Definition: bm.h:1104
const reference & operator=(const reference &ref) const
Definition: bm.h:175
enumerator get_enumerator(bm::id_t pos) const
Returns enumerator pointing on specified or the next available bit.
Definition: bm.h:1978
reference(bvector< Alloc > &bv, bm::id_t position)
Definition: bm.h:158
unsigned gap_bfind(const T *buf, unsigned pos, unsigned *is_set)
Definition: bmfunc.h:1157
void move_from(bvector< Alloc > &bvect) BMNOEXEPT
Move bvector content from another bvector.
Definition: bm.h:2349
No GAP compression strategy. All new blocks are bit blocks.
Definition: bmconst.h:112
Bit manipulation primitives (internal)
#define BM_OR_OP(x)
Definition: bm.h:3844
Encoding utilities for serialization (internal)
bool operator!=(const iterator_base &it) const
Definition: bm.h:257
unsigned gap_find_first(const T *buf, unsigned *first)
GAP block find the first set bit.
Definition: bmfunc.h:1130
unsigned gap_bit_count_range(const T *const buf, unsigned left, unsigned right)
Counts 1 bits in GAP buffer in the closed [left, right] range.
Definition: bmfunc.h:1703
unsigned find_sub_range(unsigned block_bit_pos) const
determine the sub-range within a bit-block
Definition: bm.h:5006
counted_enumerator operator++(int)
Definition: bm.h:1028
unsigned gap_test_unr(const T *buf, const unsigned pos)
Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling.
Definition: bmfunc.h:1229
bool find_reverse(bm::id_t &pos) const
Finds last index of 1 bit.
Definition: bm.h:3444
bm::id64_t update_block_digest0(const bm::word_t *const block, bm::id64_t digest)
Compute digest for 64 non-zero areas based on existing digest (function revalidates zero areas) ...
Definition: bmfunc.h:716
BMFORCEINLINE bool sse42_test_all_zero_wave(const void *ptr)
check if wave of pointers is all NULL
Definition: bmsse4.h:418
bm::id_t bit_block_calc_count_range(const bm::word_t *block, bm::word_t left, bm::word_t right)
Definition: bmfunc.h:3929
bool operator!() const
Definition: bm.h:217
const gap_word_t * ptr
Word pointer.
Definition: bm.h:349
bm::bvector< Alloc > & bit_sub(const bm::bvector< Alloc > &bv)
Logical SUB operation.
Definition: bm.h:1926
const unsigned gap_levels
Definition: bmconst.h:71
const bm::word_t * get_block(unsigned nb) const
get access to internal block by number
Definition: bm.h:2138
BMFORCEINLINE unsigned word_bitcount64(bm::id64_t x)
Definition: bmfunc.h:209
bm::id_t count() const
population cout (count of ON bits)
Definition: bm.h:2401
Default GAP lengths table.
Definition: bmconst.h:296
bool operator==(const reference &ref) const
Definition: bm.h:187
const unsigned set_array_mask
Definition: bmconst.h:79
insert_iterator & operator*()
Definition: bm.h:437
bm::bvector< Alloc > * bv_
Pointer on parent bitvector.
Definition: bm.h:354
void build_rs_index(rs_index_type *rs_idx) const
compute running total of all blocks in bit vector (rank-select index)
Definition: bm.h:1637
void gap_add_to_bitset(unsigned *dest, const T *pcurr)
Adds(OR) GAP block to bitblock.
Definition: bmfunc.h:2820
unsigned short gap_word_t
Definition: bmconst.h:65
void init()
Explicit post-construction initialization.
Definition: bm.h:2340
bm::bvector< Alloc > & bit_and(const bm::bvector< Alloc > &bv)
Logical AND operation.
Definition: bm.h:1906
unsigned value_type
Definition: bm.h:458
#define BM_AND_OP(x)
Definition: bm.h:3906
blocks_manager< Alloc > blocks_manager_type
Definition: bm.h:141
mem_pool_guard(allocator_pool_type &pool, bvector< Alloc > &bv)
Definition: bm.h:1062
void gap_sub_to_bitset(unsigned *dest, const T *pcurr)
SUB (AND NOT) GAP block to bitblock.
Definition: bmfunc.h:2725
int gap_calc_level(unsigned len, const T *glevel_len)
Calculates GAP block capacity level.
Definition: bmfunc.h:3396
bool valid() const
Checks if iterator is still valid.
Definition: bm.h:287
const unsigned bits_in_array
Definition: bmconst.h:83
const reference & operator^=(bool value) const
Definition: bm.h:210
const unsigned set_blkblk_mask
Definition: bmconst.h:50
gap_word_t * gap_operation_or(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize)
GAP OR operation.
Definition: bmfunc.h:4390
const unsigned rs3_half_span
Definition: bmconst.h:88
bool inc(bm::id_t n)
Increment the specified element.
Definition: bm.h:3266
dgap_descr gap_
DGAP block related info.
Definition: bm.h:364
unsigned * pointer
Definition: bm.h:460
void(* gap_operation_to_bitset_func_type)(unsigned *, const gap_word_t *)
Definition: bmfunc.h:6472
insert_iterator & operator=(const insert_iterator &ii)
Definition: bm.h:410
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:1153
bm::id_t position_
Bit position (bit idx)
Definition: bm.h:355
std::input_iterator_tag iterator_category
Definition: bm.h:1000
bool clear_bit(bm::id_t n)
Clears bit n.
Definition: bm.h:1495
void set_gap_level(T *buf, int level)
Sets GAP block capacity level.
Definition: bmfunc.h:3374
static gap_operation_to_bitset_func_type gap_op_to_bit(unsigned i)
Definition: bmfunc.h:6497
enumerator end() const
Returns enumerator pointing on the next bit after the last.
Definition: bm.h:1969
void reset()
Reset statisctics.
Definition: bmfunc.h:90
Information about current DGAP block.
Definition: bm.h:347
bm::id_t count_to(bm::id_t n, const rs_index_type &blocks_cnt) const
Returns count of 1 bits (population) in [0..right] range.
Definition: bm.h:2611
BMFORCEINLINE gap_word_t * gap_operation_and(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize)
GAP AND operation.
Definition: bmfunc.h:4258
allocator_type::allocator_pool_type allocator_pool_type
Definition: bm.h:140
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:2832
bm::pair< bm::gap_word_t, bm::gap_word_t > BM_VECT_ALIGN subcount [bm::set_total_blocks] BM_VECT_ALIGN_ATTR
Definition: bm.h:105
#define FULL_BLOCK_REAL_ADDR
Definition: bmdef.h:135
Definitions(internal)
enumerator & operator++()
Advance enumerator forward to the next available bit.
Definition: bm.h:502
#define BM_ASSERT_THROW(x, xerrcode)
Definition: bmdef.h:335
enumerator & go_to(bm::id_t pos)
go to a specific position in the bit-vector (or next)
Definition: bm.h:746
bool any() const
Returns true if any bits in this bitset are set, and otherwise returns false.
Definition: bm.h:1736
Algorithms for fast aggregation of a group of bit-vectors.
Definition: bmaggregator.h:51
bvector & operator=(bvector< Alloc > &&bvect) BMNOEXEPT
Move assignment operator.
Definition: bm.h:1242
void combine_operation_with_block(unsigned nb, const bm::word_t *arg_blk, bool arg_gap, bm::operation opcode)
Definition: bm.h:2146
void copy_from(const rs_index &rsi) BMNOEXEPT
copy rs index
Definition: bm.h:4987
void calc_stat(struct bm::bvector< Alloc >::statistics *st) const
Calculates bitvector statistics.
Definition: bm.h:3092
bool operator[](bm::id_t n) const
Definition: bm.h:1271
unsigned difference_type
Definition: bm.h:459
bm::word_t * bit_operation_xor(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
bitblock XOR operation.
Definition: bmfunc.h:5653
const unsigned bits_in_block
Definition: bmconst.h:82
const unsigned set_block_size_op
Definition: bmconst.h:95
void copy_range(const bvector< Alloc > &bvect, bm::id_t left, bm::id_t right)
Copy all bits in the specified closed interval [left,right].
Definition: bm.h:4900
bvector< Alloc > & flip(bm::id_t n)
Flips bit n.
Definition: bm.h:1530
union bm::bvector::iterator_base::block_descr bdescr_
enumerator & skip_to_rank(bm::id_t rank)
Skip to specified relative rank.
Definition: bm.h:661
bvector(std::initializer_list< bm::id_t > il)
Brace constructor.
Definition: bm.h:1225
const unsigned gap_max_bits
Definition: bmconst.h:68
#define BM_IS_GAP(ptr)
Definition: bmdef.h:167
Class reference implements an object for bit assignment.
Definition: bm.h:155
bvector(const bvector< Alloc > &bvect, bm::id_t left, bm::id_t right)
Copy constructor for range copy [left..right].
Definition: bm.h:1176
bool find_range(bm::id_t &first, bm::id_t &last) const
Finds dynamic range of bit-vector [first, last].
Definition: bm.h:3530
bool improve_gap_levels(const T *length, const T *length_end, T *glevel_len)
Finds optimal gap blocks lengths.
Definition: bmfunc.h:6162
const unsigned set_block_mask
Definition: bmconst.h:49
static void throw_bad_alloc()
Definition: bm.h:4954
unsigned bit_find_first(const bm::word_t *block, unsigned *first)
BIT block find the first set bit.
Definition: bmfunc.h:5880
bm::word_t * allocate_tempblock() const
Allocates temporary block of memory.
Definition: bm.h:2104
insert_iterator & operator++()
Definition: bm.h:439
Constant iterator designed to enumerate "ON" bits.
Definition: bm.h:452
optmode
Optimization mode Every next level means additional checks (better compression vs time) ...
Definition: bm.h:2030
void init() BMNOEXEPT
init arrays to zeros
Definition: bm.h:4976
#define BMGAP_PTR(ptr)
Definition: bmdef.h:165
void resize(size_type new_size)
Change size of the bvector.
Definition: bm.h:2420
reference operator[](bm::id_t n)
Definition: bm.h:1260
const unsigned set_array_size
Definition: bmconst.h:77
void for_each_block(T ***root, unsigned size1, F &f)
Definition: bmfunc.h:1542
strategy get_new_blocks_strat() const
Returns blocks allocation strategy.
Definition: bm.h:2020
const unsigned set_word_mask
Definition: bmconst.h:60
bm::word_t * bit_operation_and(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
bitblock AND operation.
Definition: bmfunc.h:5002
bvector< Alloc > & invert()
Inverts all bits.
Definition: bm.h:2810
unsigned short bitscan_wave(const bm::word_t *w_ptr, unsigned char *bits)
Unpacks word wave (Nx 32-bit words)
Definition: bmfunc.h:6566
unsigned int id_t
Definition: bmconst.h:34
gap_word_t gap_levels[bm::gap_levels]
GAP lengths used by bvector.
Definition: bmfunc.h:67
bm::bvector< Alloc > * bvect_
Definition: bm.h:444
bm::id64_t bit_block_and(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
Plain bitblock AND operation. Function does not analyse availability of source and destination blocks...
Definition: bmfunc.h:4520
BMFORCEINLINE bool gap_is_all_one(const T *buf, unsigned set_max)
Checks if GAP block is all-one.
Definition: bmfunc.h:1027
unsigned gap_limit(const T *buf, const T *glevel_len)
Returs GAP block capacity limit.
Definition: bmfunc.h:1069
bvector & operator=(const bvector< Alloc > &bvect)
Copy assignment operator.
Definition: bm.h:1199
bool set_bit(bm::id_t n, bool val=true)
Sets bit n.
Definition: bm.h:1362
unsigned * gap_convert_to_bitset_smart(unsigned *dest, const T *buf, id_t set_max)
Smart GAP block to bitblock conversion.
Definition: bmfunc.h:3232
void clear(bool free_mem=false)
Clears every bit in the bitvector.
Definition: bm.h:1511
Base class for all iterators.
Definition: bm.h:246
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:1808
#define BM_ASSERT
Definition: bmdef.h:116
static gap_operation_func_type gap_operation(unsigned i)
Definition: bmfunc.h:6503
const unsigned set_total_blocks
Definition: bmconst.h:80
unsigned count_blocks(unsigned *arr) const
Computes bitcount values for all bvector blocks.
Definition: bm.h:1601
void set_bit_no_check(bm::id_t n)
Set bit without checking preconditions (size, etc)
Definition: bm.h:3155
id64_t wordop_t
Definition: bmconst.h:93
bool none() const
Returns true if no bits are set, otherwise returns false.
Definition: bm.h:1748
void advance()
advance iterator forward by one
Definition: bm.h:584
bm::id64_t calc_block_digest0(const bm::word_t *const block)
Compute digest for 64 non-zero areas.
Definition: bmfunc.h:675
void set_allocator_pool(allocator_pool_type *pool_ptr)
Set allocator pool for local (non-threaded) memory cyclic(lots of alloc-free ops) opertations...
Definition: bm.h:1340
Output iterator iterator designed to set "ON" bits based on input sequence of integers (bit indeces)...
Definition: bm.h:383
void combine_operation(const bm::bvector< Alloc > &bvect, bm::operation opcode)
perform a set-algebra operation by operation code
Definition: bm.h:4047
bool is_bits_one(const bm::wordop_t *start)
Returns "true" if all bits in the block are 1.
Definition: bmfunc.h:4191
blocks_manager_type & get_blocks_manager()
Definition: bm.h:2161
Structure with statistical information about bitset&#39;s memory allocation details.
Definition: bmfunc.h:54
const unsigned set_block_shift
Definition: bmconst.h:48
strategy
Block allocation strategies.
Definition: bmconst.h:110
T gap_level(const T *buf)
Returs GAP blocks capacity level.
Definition: bmfunc.h:1083
bm::id_t bit_block_calc_count_to(const bm::word_t *block, bm::word_t right)
Definition: bmfunc.h:3998
std::input_iterator_tag iterator_category
Definition: bm.h:456
rs_index rs_index_type
Definition: bm.h:1115
void for_each_nzblock(T ***root, unsigned size1, F &f)
Definition: bmfunc.h:1323
unsigned BM_VECT_ALIGN bcount [bm::set_total_blocks] BM_VECT_ALIGN_ATTR
Definition: bm.h:104
bool operator~() const
Definition: bm.h:223
int gapcmp(const T *buf1, const T *buf2)
Lexicographical comparison of GAP buffers.
Definition: bmfunc.h:1945
void add_gap_block(unsigned capacity, unsigned length)
count gap block
Definition: bmfunc.h:80
const id64_t all_bits_mask
Definition: bmconst.h:94
#define FULL_BLOCK_FAKE_ADDR
Definition: bmdef.h:136
unsigned block_type_
Type of block. 0-Bit, 1-GAP.
Definition: bm.h:357
bm::id_t rank(bm::id_t n, const rs_index_type &rs_idx) const
Returns rank of specified bit position.
Definition: bm.h:1666
gap_word_t *(* gap_operation_func_type)(const gap_word_t *BMRESTRICT, const gap_word_t *BMRESTRICT, gap_word_t *BMRESTRICT, unsigned &)
Definition: bmfunc.h:6476
Alloc get_allocator() const
Definition: bm.h:1332
#define BLOCK_ADDR_SAN(addr)
Definition: bmdef.h:137
bm::id_t recalc_count()
Definition: bm.h:1693