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