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