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 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 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 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 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 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 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  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  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  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  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 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 size, bm::sort_order so)
3291 {
3292  if (!ids || !size)
3293  return; // nothing to do
3294  if (!blockman_.is_init())
3295  blockman_.init_tree();
3296 
3297  import(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 size, bm::sort_order so)
3306 {
3307  if (!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, 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 size, bm::sort_order so)
3333 {
3334  if (!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, 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,
3424  bm::sort_order sorted_idx)
3425 {
3426  bm::id_t n, nblock, start, stop = size;
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-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, nblock, start);
3453  BM_ASSERT(start < stop);
3454  import_block(ids, nblock, start, stop);
3455  start = stop;
3456  } while (start < size);
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>
3836 {
3837  BM_ASSERT_THROW(from < bm::id_max, BM_ERR_RANGE);
3838 
3839  bool ret = false;
3840 
3841  if (!rank || !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 = bm::block_find_rank(block, rank, nbit, bit_pos);
3855  if (!rank) // 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 ||
3883  !blockman_.is_init() ||
3884  (blocks_cnt.bcount[blocks_cnt.total_blocks-1] < rank))
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, 0, blocks_cnt.total_blocks-1);
3893  BM_ASSERT(blocks_cnt.bcount[nb] >= rank);
3894  if (nb)
3895  rank -= 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 <= block_bc) // target block
3911  {
3912  nbit = blocks_cnt.select_sub_range(nb, rank);
3913  rank = bm::block_find_rank(block, rank, nbit, bit_pos);
3914  BM_ASSERT(rank == 0);
3915  pos = bit_pos + (nb * bm::set_block_size * 32);
3916  return true;
3917  }
3918  rank -= block_bc;
3919  continue;
3920  }
3921 
3922  rank = bm::block_find_rank(block, rank, nbit, bit_pos);
3923  if (!rank) // 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 ||
3949  !blockman_.is_init() ||
3950  (blocks_cnt.bcount[bm::set_total_blocks-1] < rank))
3951  return ret;
3952 
3953  unsigned nb;
3954 
3955  nb = bm::lower_bound(blocks_cnt.bcount, rank, 0, blocks_cnt.total_blocks-1);
3956  BM_ASSERT(blocks_cnt.bcount[nb] >= rank);
3957  if (nb)
3958  rank -= 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 <= blocks_cnt.count(nb));
3965 
3966  bm::gap_word_t nbit = blocks_cnt.select_sub_range(nb, rank);
3967  unsigned bit_pos = 0;
3968  rank = bm::block_find_rank(block, rank, nbit, bit_pos);
3969  BM_ASSERT(rank == 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  // process target block insertion
4164  {
4165  bm::word_t* block = blockman_.get_block_ptr(nb);
4166  if (!block && !value) // nothing to do
4167  {}
4168  else
4169  {
4170  if (!block)
4171  block = blockman_.check_allocate_block(nb, BM_BIT);
4172  if (BM_IS_GAP(block) || IS_FULL_BLOCK(block))
4173  block = blockman_.deoptimize_block(nb);
4174  BM_ASSERT(IS_VALID_ADDR(block));
4175 
4176  if (!n && !value)
4177  {
4178  bm::word_t acc;
4179  carry_over = bm::bit_block_shift_r1_unr(block, &acc, carry_over);
4180  if (!acc)
4181  blockman_.zero_block(nb);
4182  }
4183  else
4184  {
4185  unsigned nbit = unsigned(n & bm::set_block_mask);
4186  carry_over = bm::bit_block_insert(block, nbit, value);
4187  }
4188  }
4189  }
4190 
4191  unsigned i0, j0;
4192  blockman_.get_block_coord(nb, i0, j0);
4193 
4194  unsigned top_blocks = blockman_.top_block_size();
4195  bm::word_t*** blk_root = blockman_.top_blocks_root();
4196  bm::word_t** blk_blk;
4197  bm::word_t* block;
4198 
4199  for (unsigned i = i0; i < bm::set_array_size; ++i)
4200  {
4201  if (i >= top_blocks)
4202  {
4203  if (!carry_over)
4204  break;
4205  blk_blk = 0;
4206  }
4207  else
4208  blk_blk = blk_root[i];
4209 
4210  if (!blk_blk) // top level group of blocks missing - can skip it
4211  {
4212  if (carry_over)
4213  {
4214  // carry over: needs block-list extension and a block
4215  unsigned nblock = (i * bm::set_array_size) + 0;
4216  if (nblock > nb)
4217  {
4218  block =
4219  blockman_.check_allocate_block(nblock, 0, 0, &block_type, false);
4220  block[0] |= carry_over; // block is brand new (0000)
4221 
4222  // reset all control vars (blocks tree may have re-allocated)
4223  blk_root = blockman_.top_blocks_root();
4224  blk_blk = blk_root[i];
4225  top_blocks = blockman_.top_block_size();
4226 
4227  carry_over = 0;
4228  }
4229  }
4230  continue;
4231  }
4232 
4233  unsigned j = 0;
4234  do
4235  {
4236  unsigned nblock = (i * bm::set_array_size) + j;
4237  if (nblock <= nb) // quickly skip to block next to target, shift
4238  {
4239  j = j0;
4240  continue;
4241  }
4242  block = blk_blk[j];
4243  if (!block)
4244  {
4245  if (carry_over)
4246  {
4247  block =
4248  blockman_.check_allocate_block(nblock, 0, 0, &block_type, false);
4249  blk_blk = blk_root[i];
4250  block[0] |= carry_over; // block is brand new (0000)
4251  carry_over = 0; block = 0;
4252  }
4253  // no CO: tight loop scan for the next available block (if any)
4254  for (++j; j < bm::set_array_size; ++j)
4255  {
4256  if (0 != (block = blk_blk[j]))
4257  {
4258  nblock = (i * bm::set_array_size) + j;
4259  break;
4260  }
4261  } // for j
4262  if (!block)
4263  continue;
4264  }
4265  if (IS_FULL_BLOCK(block))
4266  {
4267  // 1 in 1 out, block is still all 0xFFFF..
4268  // 0 into 1 -> carry in 0, carry out 1
4269  if (!carry_over)
4270  {
4271  block = blockman_.deoptimize_block(nblock);
4272  block[0] <<= (carry_over = 1);
4273  }
4274  continue;
4275  }
4276  if (BM_IS_GAP(block)) // TODO: implement true GAP shift
4277  block = blockman_.deoptimize_block(nblock);
4278 
4279  bm::word_t acc;
4280  carry_over = bm::bit_block_shift_r1_unr(block, &acc, carry_over);
4281  BM_ASSERT(carry_over <= 1);
4282 
4283  if (nblock == bm::set_total_blocks-1) // last possible block
4284  {
4285  carry_over = block[bm::set_block_size-1] & (1u<<31);
4286  block[bm::set_block_size-1] &= ~(1u<<31); // clear the 1-bit tail
4287  if (!acc) // block shifted out: release memory
4288  blockman_.zero_block(nblock);
4289  break;
4290  }
4291  if (!acc)
4292  blockman_.zero_block(nblock);
4293 
4294  } while (++j < bm::set_array_size);
4295  } // for i
4296  return carry_over;
4297 
4298 }
4299 
4300 //---------------------------------------------------------------------
4301 
4302 template<class Alloc>
4304 {
4305  if (!bv.blockman_.is_init())
4306  {
4307  this->move_from(bv);
4308  return;
4309  }
4310 
4311  unsigned top_blocks = blockman_.top_block_size();
4312  if (size_ < bv.size_) // this vect shorter than the arg.
4313  {
4314  size_ = bv.size_;
4315  }
4316  unsigned arg_top_blocks = bv.blockman_.top_block_size();
4317  top_blocks = blockman_.reserve_top_blocks(arg_top_blocks);
4318 
4319 
4320  bm::word_t*** blk_root = blockman_.top_blocks_root();
4321  bm::word_t*** blk_root_arg = bv.blockman_.top_blocks_root();
4322 
4323  for (unsigned i = 0; i < top_blocks; ++i)
4324  {
4325  bm::word_t** blk_blk = blk_root[i];
4326  bm::word_t** blk_blk_arg = (i < arg_top_blocks) ? blk_root_arg[i] : 0;
4327  if (blk_blk == blk_blk_arg || !blk_blk_arg) // nothing to do (0 OR 0 == 0)
4328  continue;
4329  if (!blk_blk && blk_blk_arg) // top block transfer
4330  {
4331  BM_ASSERT(i < arg_top_blocks);
4332 
4333  blk_root[i] = blk_root_arg[i];
4334  blk_root_arg[i] = 0;
4335  continue;
4336  }
4337 
4338  unsigned j = 0;
4339  bm::word_t* blk;
4340  bm::word_t* arg_blk;
4341  do
4342  {
4343  blk = blk_blk[j]; arg_blk = blk_blk_arg[j];
4344  if (blk != arg_blk)
4345  {
4346  if (!blk && arg_blk) // block transfer
4347  {
4348  blockman_.set_block_ptr(i, j, arg_blk);
4349  bv.blockman_.set_block_ptr(i, j, 0);
4350  }
4351  else // need full OR
4352  {
4353  combine_operation_block_or(i, j, blk, arg_blk);
4354  }
4355  }
4356  } while (++j < bm::set_array_size);
4357  } // for i
4358 }
4359 
4360 //---------------------------------------------------------------------
4361 
4362 template<class Alloc>
4364  const bm::word_t* arg_blk,
4365  bool arg_gap,
4366  bm::operation opcode)
4367 {
4368  bm::word_t* blk = blockman_.get_block(nb);
4369  bool gap = BM_IS_GAP(blk);
4370  combine_operation_with_block(nb, gap, blk, arg_blk, arg_gap, opcode);
4371 }
4372 
4373 //---------------------------------------------------------------------
4374 
4375 template<class Alloc>
4378  const bm::bvector<Alloc>& bv2,
4379  bm::bvector<Alloc>::optmode opt_mode)
4380 {
4381  if (blockman_.is_init())
4382  blockman_.deinit_tree();
4383 
4384  if (&bv1 == &bv2)
4385  {
4386  this->bit_or(bv2);
4387  return *this;
4388  }
4389  if (this == &bv1)
4390  {
4391  this->bit_or(bv2);
4392  return *this;
4393  }
4394  if (this == &bv2)
4395  {
4396  this->bit_or(bv1);
4397  return *this;
4398  }
4399 
4400  const blocks_manager_type& bman1 = bv1.get_blocks_manager();
4401  const blocks_manager_type& bman2 = bv2.get_blocks_manager();
4402 
4403  unsigned top_blocks1 = bman1.top_block_size();
4404  unsigned top_blocks2 = bman2.top_block_size();
4405  unsigned top_blocks = (top_blocks2 > top_blocks1) ? top_blocks2 : top_blocks1;
4406  top_blocks = blockman_.reserve_top_blocks(top_blocks);
4407 
4408  size_ = bv1.size_;
4409  if (size_ < bv2.size_)
4410  size_ = bv2.size_;
4411 
4412  bm::word_t*** blk_root_arg1 = bv1.blockman_.top_blocks_root();
4413  bm::word_t*** blk_root_arg2 = bv2.blockman_.top_blocks_root();
4414 
4415  for (unsigned i = 0; i < top_blocks; ++i)
4416  {
4417  bm::word_t** blk_blk_arg1 = (i < top_blocks1) ? blk_root_arg1[i] : 0;
4418  bm::word_t** blk_blk_arg2 = (i < top_blocks2) ? blk_root_arg2[i] : 0;
4419 
4420  if (blk_blk_arg1 == blk_blk_arg2)
4421  {
4422  BM_ASSERT(!blk_blk_arg1);
4423  continue;
4424  }
4425  bm::word_t** blk_blk = blockman_.alloc_top_subblock(i);
4426  bool any_blocks = false;
4427  unsigned j = 0;
4428  do
4429  {
4430  const bm::word_t* arg_blk1 = blk_blk_arg1 ? blk_blk_arg1[j] : 0;
4431  const bm::word_t* arg_blk2 = blk_blk_arg2 ? blk_blk_arg2[j] : 0;
4432  if (arg_blk1 == arg_blk2 && !arg_blk1)
4433  continue;
4434  bool need_opt = combine_operation_block_or(i, j, arg_blk1, arg_blk2);
4435  if (need_opt && opt_mode == opt_compress)
4436  blockman_.optimize_bit_block(i, j);
4437  any_blocks |= bool(blk_blk[j]);
4438  } while (++j < bm::set_array_size);
4439 
4440  if (!any_blocks)
4441  blockman_.free_top_subblock(i);
4442 
4443  } // for i
4444 
4445  if (opt_mode != opt_none)
4446  blockman_.free_temp_block();
4447 
4448  return *this;
4449 }
4450 
4451 //---------------------------------------------------------------------
4452 
4453 template<class Alloc>
4456  const bm::bvector<Alloc>& bv2,
4457  bm::bvector<Alloc>::optmode opt_mode)
4458 {
4459  if (blockman_.is_init())
4460  blockman_.deinit_tree();
4461 
4462  if (&bv1 == &bv2)
4463  return *this; // nothing to do empty result
4464 
4465  if (this == &bv1)
4466  {
4467  this->bit_xor(bv2);
4468  return *this;
4469  }
4470  if (this == &bv2)
4471  {
4472  this->bit_xor(bv1);
4473  return *this;
4474  }
4475 
4476  const blocks_manager_type& bman1 = bv1.get_blocks_manager();
4477  if (!bman1.is_init())
4478  {
4479  *this = bv2;
4480  return *this;
4481  }
4482  const blocks_manager_type& bman2 = bv2.get_blocks_manager();
4483  if (!bman2.is_init())
4484  {
4485  *this = bv1;
4486  return *this;
4487  }
4488 
4489  unsigned top_blocks1 = bman1.top_block_size();
4490  unsigned top_blocks2 = bman2.top_block_size();
4491  unsigned top_blocks = (top_blocks2 > top_blocks1) ? top_blocks2 : top_blocks1;
4492  top_blocks = blockman_.reserve_top_blocks(top_blocks);
4493 
4494  size_ = bv1.size_;
4495  if (size_ < bv2.size_)
4496  size_ = bv2.size_;
4497 
4498  bm::word_t*** blk_root_arg1 = bv1.blockman_.top_blocks_root();
4499  bm::word_t*** blk_root_arg2 = bv2.blockman_.top_blocks_root();
4500 
4501  for (unsigned i = 0; i < top_blocks; ++i)
4502  {
4503  bm::word_t** blk_blk_arg1 = (i < top_blocks1) ? blk_root_arg1[i] : 0;
4504  bm::word_t** blk_blk_arg2 = (i < top_blocks2) ? blk_root_arg2[i] : 0;
4505 
4506  if (blk_blk_arg1 == blk_blk_arg2)
4507  {
4508  BM_ASSERT(!blk_blk_arg1);
4509  continue;
4510  }
4511  bm::word_t** blk_blk = blockman_.alloc_top_subblock(i);
4512  bool any_blocks = false;
4513  unsigned j = 0;
4514  do
4515  {
4516  const bm::word_t* arg_blk1 = blk_blk_arg1 ? blk_blk_arg1[j] : 0;
4517  const bm::word_t* arg_blk2 = blk_blk_arg2 ? blk_blk_arg2[j] : 0;
4518  if ((arg_blk1 == arg_blk2) &&
4519  (!arg_blk1 || arg_blk1 == FULL_BLOCK_FAKE_ADDR))
4520  continue; // 0 ^ 0 == 0 , 1 ^ 1 == 0 (nothing to do)
4521 
4522  bool need_opt = combine_operation_block_xor(i, j, arg_blk1, arg_blk2);
4523  if (need_opt && opt_mode == opt_compress)
4524  blockman_.optimize_bit_block(i, j);
4525  any_blocks |= bool(blk_blk[j]);
4526  } while (++j < bm::set_array_size);
4527 
4528  if (!any_blocks)
4529  blockman_.free_top_subblock(i);
4530 
4531  } // for i
4532 
4533  if (opt_mode != opt_none)
4534  blockman_.free_temp_block();
4535 
4536  return *this;
4537 }
4538 
4539 //---------------------------------------------------------------------
4540 
4541 template<class Alloc>
4544  const bm::bvector<Alloc>& bv2,
4545  bm::bvector<Alloc>::optmode opt_mode)
4546 {
4547  if (blockman_.is_init())
4548  blockman_.deinit_tree();
4549 
4550  if (&bv1 == &bv2)
4551  {
4552  this->bit_or(bv1);
4553  return *this;
4554  }
4555 
4556  if (this == &bv1)
4557  {
4558  this->bit_and(bv2);
4559  return *this;
4560  }
4561  if (this == &bv2)
4562  {
4563  this->bit_and(bv1);
4564  return *this;
4565  }
4566 
4567  const blocks_manager_type& bman1 = bv1.get_blocks_manager();
4568  const blocks_manager_type& bman2 = bv2.get_blocks_manager();
4569  if (!bman1.is_init() || !bman2.is_init())
4570  {
4571  return *this;
4572  }
4573 
4574  unsigned top_blocks1 = bman1.top_block_size();
4575  unsigned top_blocks2 = bman2.top_block_size();
4576  unsigned top_blocks = (top_blocks2 > top_blocks1) ? top_blocks2 : top_blocks1;
4577  top_blocks = blockman_.reserve_top_blocks(top_blocks);
4578 
4579  size_ = bv1.size_;
4580  if (size_ < bv2.size_)
4581  size_ = bv2.size_;
4582 
4583  bm::word_t*** blk_root_arg1 = bv1.blockman_.top_blocks_root();
4584  bm::word_t*** blk_root_arg2 = bv2.blockman_.top_blocks_root();
4585 
4586  for (unsigned i = 0; i < top_blocks; ++i)
4587  {
4588  bm::word_t** blk_blk_arg1 = (i < top_blocks1) ? blk_root_arg1[i] : 0;
4589  bm::word_t** blk_blk_arg2 = (i < top_blocks2) ? blk_root_arg2[i] : 0;
4590 
4591  if (blk_blk_arg1 == blk_blk_arg2)
4592  {
4593  BM_ASSERT(!blk_blk_arg1);
4594  continue; // 0 & 0 == 0
4595  }
4596  bm::word_t** blk_blk = blockman_.alloc_top_subblock(i);
4597  bool any_blocks = false;
4598  unsigned j = 0;
4599  do
4600  {
4601  const bm::word_t* arg_blk1 = blk_blk_arg1 ? blk_blk_arg1[j] : 0;
4602  const bm::word_t* arg_blk2 = blk_blk_arg2 ? blk_blk_arg2[j] : 0;
4603  if ((arg_blk1 == arg_blk2) && !arg_blk1)
4604  continue; // 0 & 0 == 0
4605 
4606  bool need_opt = combine_operation_block_and(i, j, arg_blk1, arg_blk2);
4607  if (need_opt && opt_mode == opt_compress)
4608  blockman_.optimize_bit_block(i, j);
4609  any_blocks |= bool(blk_blk[j]);
4610  } while (++j < bm::set_array_size);
4611 
4612  if (!any_blocks)
4613  blockman_.free_top_subblock(i);
4614 
4615  } // for i
4616 
4617  if (opt_mode != opt_none)
4618  blockman_.free_temp_block();
4619 
4620  return *this;
4621 }
4622 
4623 
4624 //---------------------------------------------------------------------
4625 
4626 template<class Alloc>
4629  const bm::bvector<Alloc>& bv2,
4630  bm::bvector<Alloc>::optmode opt_mode)
4631 {
4632  if (blockman_.is_init())
4633  blockman_.deinit_tree();
4634 
4635  if (&bv1 == &bv2)
4636  return *this; // nothing to do empty result
4637 
4638  if (this == &bv1)
4639  {
4640  this->bit_sub(bv2);
4641  return *this;
4642  }
4643  if (this == &bv2)
4644  {
4645  this->bit_sub(bv1);
4646  return *this;
4647  }
4648 
4649  const blocks_manager_type& bman1 = bv1.get_blocks_manager();
4650  const blocks_manager_type& bman2 = bv2.get_blocks_manager();
4651  if (!bman1.is_init())
4652  {
4653  return *this;
4654  }
4655  if (!bman2.is_init())
4656  {
4657  this->bit_or(bv1);
4658  return *this;
4659  }
4660 
4661  unsigned top_blocks1 = bman1.top_block_size();
4662  unsigned top_blocks2 = bman2.top_block_size();
4663  unsigned top_blocks = (top_blocks2 > top_blocks1) ? top_blocks2 : top_blocks1;
4664  top_blocks = blockman_.reserve_top_blocks(top_blocks);
4665 
4666  size_ = bv1.size_;
4667  if (size_ < bv2.size_)
4668  size_ = bv2.size_;
4669 
4670  bm::word_t*** blk_root_arg1 = bv1.blockman_.top_blocks_root();
4671  bm::word_t*** blk_root_arg2 = bv2.blockman_.top_blocks_root();
4672 
4673  for (unsigned i = 0; i < top_blocks; ++i)
4674  {
4675  bm::word_t** blk_blk_arg1 = (i < top_blocks1) ? blk_root_arg1[i] : 0;
4676  bm::word_t** blk_blk_arg2 = (i < top_blocks2) ? blk_root_arg2[i] : 0;
4677 
4678  if (blk_blk_arg1 == blk_blk_arg2)
4679  {
4680  BM_ASSERT(!blk_blk_arg1);
4681  continue; // 0 AND NOT 0 == 0
4682  }
4683  bm::word_t** blk_blk = blockman_.alloc_top_subblock(i);
4684  bool any_blocks = false;
4685  unsigned j = 0;
4686  do
4687  {
4688  const bm::word_t* arg_blk1 = blk_blk_arg1 ? blk_blk_arg1[j] : 0;
4689  const bm::word_t* arg_blk2 = blk_blk_arg2 ? blk_blk_arg2[j] : 0;
4690  if ((arg_blk1 == arg_blk2) && !arg_blk1)
4691  continue; // 0 & ~0 == 0
4692 
4693  bool need_opt = combine_operation_block_sub(i, j, arg_blk1, arg_blk2);
4694  if (need_opt && opt_mode == opt_compress)
4695  blockman_.optimize_bit_block(i, j);
4696  any_blocks |= bool(blk_blk[j]);
4697  } while (++j < bm::set_array_size);
4698 
4699  if (!any_blocks)
4700  blockman_.free_top_subblock(i);
4701 
4702  } // for i
4703 
4704  if (opt_mode != opt_none)
4705  blockman_.free_temp_block();
4706 
4707  return *this;
4708 }
4709 
4710 
4711 //---------------------------------------------------------------------
4712 
4713 #define BM_OR_OP(x) \
4714  { \
4715  blk = blk_blk[j+x]; arg_blk = blk_blk_arg[j+x]; \
4716  if (blk != arg_blk) \
4717  combine_operation_block_or(i, j+x, blk, arg_blk); \
4718  }
4719 
4720 template<class Alloc>
4722 {
4723  if (!bv.blockman_.is_init())
4724  return;
4725 
4726  unsigned top_blocks = blockman_.top_block_size();
4727  if (size_ < bv.size_)
4728  size_ = bv.size_;
4729 
4730  unsigned arg_top_blocks = bv.blockman_.top_block_size();
4731  top_blocks = blockman_.reserve_top_blocks(arg_top_blocks);
4732 
4733  bm::word_t*** blk_root = blockman_.top_blocks_root();
4734  bm::word_t*** blk_root_arg = bv.blockman_.top_blocks_root();
4735 
4736  for (unsigned i = 0; i < top_blocks; ++i)
4737  {
4738  bm::word_t** blk_blk = blk_root[i];
4739  bm::word_t** blk_blk_arg = (i < arg_top_blocks) ? blk_root_arg[i] : 0;
4740  if (blk_blk == blk_blk_arg || !blk_blk_arg) // nothing to do (0 OR 0 == 0)
4741  continue;
4742  if (!blk_blk)
4743  blk_blk = blockman_.alloc_top_subblock(i);
4744 
4745  unsigned j = 0;
4746  bm::word_t* blk;
4747  const bm::word_t* arg_blk;
4748  do
4749  {
4750  #if defined(BM64_AVX2) || defined(BM64_AVX512)
4751  if (!avx2_test_all_eq_wave2(blk_blk + j, blk_blk_arg + j))
4752  {
4753  BM_OR_OP(0)
4754  BM_OR_OP(1)
4755  BM_OR_OP(2)
4756  BM_OR_OP(3)
4757  }
4758  j += 4;
4759  #elif defined(BM64_SSE4)
4760  if (!sse42_test_all_eq_wave2(blk_blk + j, blk_blk_arg + j))
4761  {
4762  BM_OR_OP(0)
4763  BM_OR_OP(1)
4764  }
4765  j += 2;
4766  #else
4767  BM_OR_OP(0)
4768  ++j;
4769  #endif
4770  } while (j < bm::set_array_size);
4771  } // for i
4772 }
4773 
4774 #undef BM_OR_OP
4775 
4776 //---------------------------------------------------------------------
4777 
4778 #define BM_XOR_OP(x) \
4779  { \
4780  blk = blk_blk[j+x]; arg_blk = blk_blk_arg[j+x]; \
4781  combine_operation_block_xor(i, j+x, blk, arg_blk); \
4782  }
4783 
4784 template<class Alloc>
4786 {
4787  if (!bv.blockman_.is_init())
4788  return;
4789 
4790  unsigned top_blocks = blockman_.top_block_size();
4791  if (size_ < bv.size_) // this vect shorter than the arg.
4792  {
4793  size_ = bv.size_;
4794  }
4795  unsigned arg_top_blocks = bv.blockman_.top_block_size();
4796  top_blocks = blockman_.reserve_top_blocks(arg_top_blocks);
4797 
4798  bm::word_t*** blk_root = blockman_.top_blocks_root();
4799  bm::word_t*** blk_root_arg = bv.blockman_.top_blocks_root();
4800 
4801  for (unsigned i = 0; i < top_blocks; ++i)
4802  {
4803  bm::word_t** blk_blk = blk_root[i];
4804  bm::word_t** blk_blk_arg = (i < arg_top_blocks) ? blk_root_arg[i] : 0;
4805  if (blk_blk == blk_blk_arg || !blk_blk_arg) // nothing to do (any XOR 0 == 0)
4806  continue;
4807 
4808  if (!blk_blk)
4809  blk_blk = blockman_.alloc_top_subblock(i);
4810 
4811  unsigned j = 0;
4812  bm::word_t* blk;
4813  const bm::word_t* arg_blk;
4814  do
4815  {
4816  #if defined(BM64_AVX2) || defined(BM64_AVX512)
4817  if (!avx2_test_all_zero_wave2(blk_blk + j, blk_blk_arg + j))
4818  {
4819  BM_XOR_OP(0)
4820  BM_XOR_OP(1)
4821  BM_XOR_OP(2)
4822  BM_XOR_OP(3)
4823  }
4824  j += 4;
4825  #elif defined(BM64_SSE4)
4826  if (!sse42_test_all_zero_wave2(blk_blk + j, blk_blk_arg + j))
4827  {
4828  BM_XOR_OP(0)
4829  BM_XOR_OP(1)
4830  }
4831  j += 2;
4832  #else
4833  BM_XOR_OP(0)
4834  ++j;
4835  #endif
4836  } while (j < bm::set_array_size);
4837  } // for i
4838 }
4839 
4840 #undef BM_XOR_OP
4841 
4842 
4843 //---------------------------------------------------------------------
4844 
4845 #define BM_AND_OP(x) if (0 != (blk = blk_blk[j+x])) \
4846  { \
4847  if (0 != (arg_blk = blk_blk_arg[j+x])) \
4848  combine_operation_block_and(i, j+x, blk, arg_blk); \
4849  else \
4850  blockman_.zero_block(i, j+x); \
4851  }
4852 
4853 template<class Alloc>
4855 {
4856  if (!blockman_.is_init())
4857  return; // nothing to do, already empty
4858  if (!bv.blockman_.is_init())
4859  {
4860  clear(true);
4861  return;
4862  }
4863 
4864  unsigned top_blocks = blockman_.top_block_size();
4865  if (size_ < bv.size_) // this vect shorter than the arg.
4866  {
4867  size_ = bv.size_;
4868  }
4869  unsigned arg_top_blocks = bv.blockman_.top_block_size();
4870  top_blocks = blockman_.reserve_top_blocks(arg_top_blocks);
4871 
4872 
4873  bm::word_t*** blk_root = blockman_.top_blocks_root();
4874  bm::word_t*** blk_root_arg = bv.blockman_.top_blocks_root();
4875 
4876  for (unsigned i = 0; i < top_blocks; ++i)
4877  {
4878  bm::word_t** blk_blk = blk_root[i];
4879  if (!blk_blk) // nothing to do (0 AND 1 == 0)
4880  continue;
4881  bm::word_t** blk_blk_arg = (i < arg_top_blocks) ? blk_root_arg[i] : 0;
4882  if (!blk_blk_arg) // free a whole group of blocks
4883  {
4884  for (unsigned j = 0; j < bm::set_array_size; ++j)
4885  blockman_.zero_block(i, j);
4886  continue;
4887  }
4888  unsigned j = 0;
4889  bm::word_t* blk;
4890  const bm::word_t* arg_blk;
4891  do
4892  {
4893  #if defined(BM64_AVX2) || defined(BM64_AVX512)
4894  if (!avx2_test_all_zero_wave(blk_blk + j))
4895  {
4896  BM_AND_OP(0)
4897  BM_AND_OP(1)
4898  BM_AND_OP(2)
4899  BM_AND_OP(3)
4900  }
4901  j += 4;
4902  #elif defined(BM64_SSE4)
4903  if (!sse42_test_all_zero_wave(blk_blk + j))
4904  {
4905  BM_AND_OP(0)
4906  BM_AND_OP(1)
4907  }
4908  j += 2;
4909  #else
4910  BM_AND_OP(0)
4911  ++j;
4912  #endif
4913  } while (j < bm::set_array_size);
4914  } // for i
4915 }
4916 
4917 #undef BM_AND_OP
4918 
4919 
4920 //---------------------------------------------------------------------
4921 
4922 #define BM_SUB_OP(x) \
4923  if ((0 != (blk = blk_blk[j+x])) && (0 != (arg_blk = blk_blk_arg[j+x]))) \
4924  combine_operation_block_sub(i, j+x, blk, arg_blk);
4925 
4926 
4927 template<class Alloc>
4929 {
4930  if (!blockman_.is_init())
4931  return;
4932  if (!bv.blockman_.is_init())
4933  return;
4934 
4935  unsigned top_blocks = blockman_.top_block_size();
4936  if (size_ < bv.size_) // this vect shorter than the arg.
4937  {
4938  size_ = bv.size_;
4939  }
4940  unsigned arg_top_blocks = bv.blockman_.top_block_size();
4941  top_blocks = blockman_.reserve_top_blocks(arg_top_blocks);
4942 
4943  bm::word_t*** blk_root = blockman_.top_blocks_root();
4944  bm::word_t*** blk_root_arg = bv.blockman_.top_blocks_root();
4945 
4946  for (unsigned i = 0; i < top_blocks; ++i)
4947  {
4948  bm::word_t** blk_blk = blk_root[i];
4949  bm::word_t** blk_blk_arg = (i < arg_top_blocks) ? blk_root_arg[i] : 0;
4950  if (!blk_blk || !blk_blk_arg) // nothing to do (0 AND NOT 1 == 0)
4951  continue;
4952  bm::word_t* blk;
4953  const bm::word_t* arg_blk;
4954  unsigned j = 0;
4955  do
4956  {
4957  #if defined(BM64_AVX2) || defined(BM64_AVX512)
4958  if (!avx2_test_all_zero_wave(blk_blk + j))
4959  {
4960  BM_SUB_OP(0)
4961  BM_SUB_OP(1)
4962  BM_SUB_OP(2)
4963  BM_SUB_OP(3)
4964  }
4965  j += 4;
4966  #elif defined(BM64_SSE4)
4967  if (!sse42_test_all_zero_wave(blk_blk + j))
4968  {
4969  BM_SUB_OP(0)
4970  BM_SUB_OP(1)
4971  }
4972  j += 2;
4973  #else
4974  BM_SUB_OP(0)
4975  ++j;
4976  #endif
4977  } while (j < bm::set_array_size);
4978  } // for i
4979 }
4980 
4981 #undef BM_SUB_OP
4982 
4983 //---------------------------------------------------------------------
4984 
4985 template<class Alloc>
4987  const bm::bvector<Alloc>& bv,
4988  bm::operation opcode)
4989 {
4990  if (!blockman_.is_init())
4991  {
4992  if (opcode == BM_AND || opcode == BM_SUB)
4993  {
4994  return;
4995  }
4996  blockman_.init_tree();
4997  }
4998 
4999  unsigned top_blocks = blockman_.top_block_size();
5000  unsigned arg_top_blocks = bv.blockman_.top_block_size();
5001 
5002  if (arg_top_blocks > top_blocks)
5003  top_blocks = blockman_.reserve_top_blocks(arg_top_blocks);
5004 
5005  if (size_ < bv.size_) // this vect shorter than the arg.
5006  {
5007  size_ = bv.size_;
5008  // stretch our capacity
5009  blockman_.reserve_top_blocks(arg_top_blocks);
5010  top_blocks = blockman_.top_block_size();
5011  }
5012  else
5013  if (size_ > bv.size_) // this vector larger
5014  {
5015  if (opcode == BM_AND) // clear the tail with zeros
5016  {
5017  set_range(bv.size_, size_ - 1, false);
5018  if (arg_top_blocks < top_blocks)
5019  {
5020  // not to scan blocks we already swiped
5021  top_blocks = arg_top_blocks;
5022  }
5023  }
5024  }
5025 
5026  bm::word_t*** blk_root = blockman_.top_blocks_root();
5027  unsigned block_idx = 0;
5028  unsigned i, j;
5029 
5030  // calculate effective top size to avoid overscan
5031  top_blocks = blockman_.top_block_size();
5032  if (top_blocks < bv.blockman_.top_block_size())
5033  {
5034  if (opcode != BM_AND)
5035  {
5036  top_blocks = bv.blockman_.top_block_size();
5037  }
5038  }
5039 
5040  for (i = 0; i < top_blocks; ++i)
5041  {
5042  bm::word_t** blk_blk = blk_root[i];
5043  if (blk_blk == 0) // not allocated
5044  {
5045  if (opcode == BM_AND) // 0 AND anything == 0
5046  {
5047  block_idx += bm::set_array_size;
5048  continue;
5049  }
5050  const bm::word_t* const* bvbb = bv.blockman_.get_topblock(i);
5051  if (bvbb == 0) // skip it because 0 OP 0 == 0
5052  {
5053  block_idx += bm::set_array_size;
5054  continue;
5055  }
5056  // 0 - self, non-zero argument
5057  unsigned r = i * bm::set_array_size;
5058  for (j = 0; j < bm::set_array_size; ++j)
5059  {
5060  const bm::word_t* arg_blk = bv.blockman_.get_block(i, j);
5061  if (arg_blk )
5062  combine_operation_with_block(r + j,
5063  0, 0,
5064  arg_blk, BM_IS_GAP(arg_blk),
5065  opcode);
5066  } // for j
5067  continue;
5068  }
5069 
5070  if (opcode == BM_AND)
5071  {
5072  unsigned r = i * bm::set_array_size;
5073  for (j = 0; j < bm::set_array_size; ++j)
5074  {
5075  bm::word_t* blk = blk_blk[j];
5076  if (blk)
5077  {
5078  const bm::word_t* arg_blk = bv.blockman_.get_block(i, j);
5079  if (arg_blk)
5080  combine_operation_with_block(r + j,
5081  BM_IS_GAP(blk), blk,
5082  arg_blk, BM_IS_GAP(arg_blk),
5083  opcode);
5084  else
5085  blockman_.zero_block(i, j);
5086  }
5087 
5088  } // for j
5089  }
5090  else // OR, SUB, XOR
5091  {
5092  unsigned r = i * bm::set_array_size;
5093  for (j = 0; j < bm::set_array_size; ++j)
5094  {
5095  bm::word_t* blk = blk_blk[j];
5096  const bm::word_t* arg_blk = bv.blockman_.get_block(i, j);
5097  if (arg_blk || blk)
5098  combine_operation_with_block(r + j, BM_IS_GAP(blk), blk,
5099  arg_blk, BM_IS_GAP(arg_blk),
5100  opcode);
5101  } // for j
5102  }
5103  } // for i
5104 
5105 }
5106 
5107 //---------------------------------------------------------------------
5108 
5109 template<class Alloc>
5111  unsigned j,
5112  const bm::word_t* arg_blk1,
5113  const bm::word_t* arg_blk2)
5114 {
5115  bm::gap_word_t tmp_buf[bm::gap_equiv_len * 3]; // temporary result
5116  if (!arg_blk1)
5117  {
5118  blockman_.clone_assign_block(i, j, arg_blk2);
5119  return 0;
5120  }
5121  if (!arg_blk2)
5122  {
5123  blockman_.clone_assign_block(i, j, arg_blk1);
5124  return 0;
5125  }
5126  if ((arg_blk1==FULL_BLOCK_FAKE_ADDR) || (arg_blk2==FULL_BLOCK_FAKE_ADDR))
5127  {
5128  blockman_.set_block_ptr(i, j, FULL_BLOCK_FAKE_ADDR);
5129  return 0;
5130  }
5131 
5132  bool is_gap1 = BM_IS_GAP(arg_blk1);
5133  bool is_gap2 = BM_IS_GAP(arg_blk2);
5134 
5135  if (is_gap1 | is_gap2) // at least one GAP
5136  {
5137  if (is_gap1 & is_gap2) // both GAPS
5138  {
5139  unsigned res_len;
5140  bm::gap_operation_or(BMGAP_PTR(arg_blk1),
5141  BMGAP_PTR(arg_blk2),
5142  tmp_buf, res_len);
5143  blockman_.clone_gap_block(i, j, tmp_buf, res_len);
5144  return 0;
5145  }
5146  // one GAP one bit block
5147  const bm::word_t* arg_block;
5148  const bm::gap_word_t* arg_gap;
5149  if (is_gap1) // arg1 is GAP -> clone arg2(bit)
5150  {
5151  arg_block = arg_blk2;
5152  arg_gap = BMGAP_PTR(arg_blk1);
5153  }
5154  else // arg2 is GAP
5155  {
5156  arg_block = arg_blk1;
5157  arg_gap = BMGAP_PTR(arg_blk2);
5158  }
5159  bm::word_t* block = blockman_.clone_assign_block(i, j, arg_block);
5160  bm::gap_add_to_bitset(block, arg_gap);
5161 
5162  return true; // optimization may be needed
5163  }
5164 
5165  // 2 bit-blocks
5166  //
5167  bm::word_t* block = blockman_.borrow_tempblock();
5168  blockman_.set_block_ptr(i, j, block);
5169 
5170  bool all_one = bm::bit_block_or_2way(block, arg_blk1, arg_blk2);
5171  if (all_one)
5172  {
5173  blockman_.set_block_ptr(i, j, FULL_BLOCK_FAKE_ADDR);
5174  blockman_.return_tempblock(block);
5175  return 0;
5176  }
5177  return true;
5178 }
5179 
5180 //---------------------------------------------------------------------
5181 
5182 template<class Alloc>
5184  unsigned j,
5185  const bm::word_t* arg_blk1,
5186  const bm::word_t* arg_blk2)
5187 {
5188  bm::gap_word_t tmp_buf[bm::gap_equiv_len * 3]; // temporary result
5189 
5190  if (!arg_blk1)
5191  {
5192  blockman_.clone_assign_block(i, j, arg_blk2);
5193  return 0;
5194  }
5195  if (!arg_blk2)
5196  {
5197  blockman_.clone_assign_block(i, j, arg_blk1);
5198  return 0;
5199  }
5200  if (arg_blk1==FULL_BLOCK_FAKE_ADDR)
5201  {
5202  BM_ASSERT(!IS_FULL_BLOCK(arg_blk2));
5203  blockman_.clone_assign_block(i, j, arg_blk2, true); // invert
5204  return 0;
5205  }
5206  if (arg_blk2==FULL_BLOCK_FAKE_ADDR)
5207  {
5208  BM_ASSERT(!IS_FULL_BLOCK(arg_blk1));
5209  blockman_.clone_assign_block(i, j, arg_blk1, true); // invert
5210  return 0;
5211  }
5212 
5213  bool is_gap1 = BM_IS_GAP(arg_blk1);
5214  bool is_gap2 = BM_IS_GAP(arg_blk2);
5215 
5216  if (is_gap1 | is_gap2) // at least one GAP
5217  {
5218  if (is_gap1 & is_gap2) // both GAPS
5219  {
5220  unsigned res_len;
5221  bm::gap_operation_xor(BMGAP_PTR(arg_blk1),
5222  BMGAP_PTR(arg_blk2),
5223  tmp_buf, res_len);
5224  blockman_.clone_gap_block(i, j, tmp_buf, res_len);
5225  return 0;
5226  }
5227  // one GAP one bit block
5228  const bm::word_t* arg_block;
5229  const bm::gap_word_t* arg_gap;
5230  if (is_gap1) // arg1 is GAP -> clone arg2(bit)
5231  {
5232  arg_block = arg_blk2;
5233  arg_gap = BMGAP_PTR(arg_blk1);
5234  }
5235  else // arg2 is GAP
5236  {
5237  arg_block = arg_blk1;
5238  arg_gap = BMGAP_PTR(arg_blk2);
5239  }
5240  bm::word_t* block = blockman_.clone_assign_block(i, j, arg_block);
5241  bm::gap_xor_to_bitset(block, arg_gap);
5242 
5243  return true; // optimization may be needed
5244  }
5245 
5246  // 2 bit-blocks
5247  //
5248  bm::word_t* block = blockman_.borrow_tempblock();
5249  blockman_.set_block_ptr(i, j, block);
5250 
5251  bm::id64_t or_mask = bm::bit_block_xor_2way(block, arg_blk1, arg_blk2);
5252  if (!or_mask)
5253  {
5254  blockman_.set_block_ptr(i, j, 0);
5255  blockman_.return_tempblock(block);
5256  return 0;
5257  }
5258 
5259  return true;
5260 }
5261 
5262 //---------------------------------------------------------------------
5263 
5264 template<class Alloc>
5266  unsigned j,
5267  const bm::word_t* arg_blk1,
5268  const bm::word_t* arg_blk2)
5269 {
5270  bm::gap_word_t tmp_buf[bm::gap_equiv_len * 3]; // temporary result
5271 
5272  if (!arg_blk1 || !arg_blk2)
5273  {
5274  return 0;
5275  }
5276  if ((arg_blk1==FULL_BLOCK_FAKE_ADDR) && (arg_blk2==FULL_BLOCK_FAKE_ADDR))
5277  {
5278  blockman_.set_block_ptr(i, j, FULL_BLOCK_FAKE_ADDR);
5279  return 0;
5280  }
5281  if (arg_blk1==FULL_BLOCK_FAKE_ADDR)
5282  {
5283  blockman_.clone_assign_block(i, j, arg_blk2);
5284  return 0;
5285  }
5286  if (arg_blk2==FULL_BLOCK_FAKE_ADDR)
5287  {
5288  blockman_.clone_assign_block(i, j, arg_blk1);
5289  return 0;
5290  }
5291 
5292  bool is_gap1 = BM_IS_GAP(arg_blk1);
5293  bool is_gap2 = BM_IS_GAP(arg_blk2);
5294 
5295  if (is_gap1 | is_gap2) // at least one GAP
5296  {
5297  if (is_gap1 & is_gap2) // both GAPS
5298  {
5299  unsigned res_len;
5300  bm::gap_operation_and(BMGAP_PTR(arg_blk1),
5301  BMGAP_PTR(arg_blk2),
5302  tmp_buf, res_len);
5303  blockman_.clone_gap_block(i, j, tmp_buf, res_len);
5304  return 0;
5305  }
5306  // one GAP one bit block
5307  const bm::word_t* arg_block;
5308  const bm::gap_word_t* arg_gap;
5309  if (is_gap1) // arg1 is GAP -> clone arg2(bit)
5310  {
5311  arg_block = arg_blk2;
5312  arg_gap = BMGAP_PTR(arg_blk1);
5313  }
5314  else // arg2 is GAP
5315  {
5316  arg_block = arg_blk1;
5317  arg_gap = BMGAP_PTR(arg_blk2);
5318  }
5319  bm::word_t* block = blockman_.clone_assign_block(i, j, arg_block);
5320  bm::gap_and_to_bitset(block, arg_gap);
5321 
5322  return true; // optimization may be needed
5323  }
5324 
5325  // 2 bit-blocks
5326  //
5327  bm::word_t* block = blockman_.borrow_tempblock();
5328  blockman_.set_block_ptr(i, j, block);
5329 
5330  bm::id64_t digest = bm::bit_block_and_2way(block, arg_blk1, arg_blk2, ~0ull);
5331  if (!digest)
5332  {
5333  blockman_.set_block_ptr(i, j, 0);
5334  blockman_.return_tempblock(block);
5335  return 0;
5336  }
5337 
5338  return true;
5339 }
5340 
5341 //---------------------------------------------------------------------
5342 
5343 template<class Alloc>
5345  unsigned j,
5346  const bm::word_t* arg_blk1,
5347  const bm::word_t* arg_blk2)
5348 {
5349  bm::gap_word_t tmp_buf[bm::gap_equiv_len * 3]; // temporary result
5350 
5351  if (!arg_blk1)
5352  return 0;
5353  if (!arg_blk2)
5354  {
5355  blockman_.clone_assign_block(i, j, arg_blk1);
5356  return 0;
5357  }
5358  if (arg_blk2==FULL_BLOCK_FAKE_ADDR)
5359  return 0;
5360  if (arg_blk1==FULL_BLOCK_FAKE_ADDR)
5361  arg_blk1 = FULL_BLOCK_REAL_ADDR;
5362 
5363  bool is_gap1 = BM_IS_GAP(arg_blk1);
5364  bool is_gap2 = BM_IS_GAP(arg_blk2);
5365 
5366  if (is_gap1 | is_gap2) // at least one GAP
5367  {
5368  if (is_gap1 & is_gap2) // both GAPS
5369  {
5370  unsigned res_len;
5371  bm::gap_operation_sub(BMGAP_PTR(arg_blk1),
5372  BMGAP_PTR(arg_blk2),
5373  tmp_buf, res_len);
5374  blockman_.clone_gap_block(i, j, tmp_buf, res_len);
5375  return 0;
5376  }
5377 
5378  if (is_gap1)
5379  {
5380  bm::word_t* block = blockman_.borrow_tempblock();
5381  blockman_.set_block_ptr(i, j, block);
5382  bm::gap_convert_to_bitset(block, BMGAP_PTR(arg_blk1));
5383  bm::id64_t acc = bm::bit_block_sub(block, arg_blk2);
5384  if (!acc)
5385  {
5386  blockman_.set_block_ptr(i, j, 0);
5387  blockman_.return_tempblock(block);
5388  return 0;
5389  }
5390  return true;
5391  }
5392  BM_ASSERT(is_gap2);
5393  bm::word_t* block = blockman_.clone_assign_block(i, j, arg_blk1);
5394  bm::gap_sub_to_bitset(block, BMGAP_PTR(arg_blk2));
5395 
5396  return true; // optimization may be needed
5397  }
5398 
5399  // 2 bit-blocks:
5400  //
5401  bm::word_t* block = blockman_.borrow_tempblock();
5402  blockman_.set_block_ptr(i, j, block);
5403 
5404  bm::id64_t digest = bm::bit_block_sub_2way(block, arg_blk1, arg_blk2, ~0ull);
5405  if (!digest)
5406  {
5407  blockman_.set_block_ptr(i, j, 0);
5408  blockman_.return_tempblock(block);
5409  return 0;
5410  }
5411  return true;
5412 }
5413 
5414 
5415 //---------------------------------------------------------------------
5416 
5417 template<class Alloc>
5419  unsigned i, unsigned j,
5420  bm::word_t* blk, const bm::word_t* arg_blk)
5421 {
5422  bm::gap_word_t tmp_buf[bm::gap_equiv_len * 3]; // temporary result
5423  if (IS_FULL_BLOCK(blk) || !arg_blk) // all bits are set
5424  return; // nothing to do
5425 
5426  if (IS_FULL_BLOCK(arg_blk))
5427  {
5428  if (blk)
5429  blockman_.zero_block(i, j); // free target block and assign FULL
5430  blockman_.set_block_ptr(i, j, FULL_BLOCK_FAKE_ADDR);
5431  return;
5432  }
5433 
5434  if (BM_IS_GAP(blk)) // our block GAP-type
5435  {
5436  bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
5437  if (BM_IS_GAP(arg_blk)) // both blocks GAP-type
5438  {
5439  const bm::gap_word_t* res; unsigned res_len;
5440  res = bm::gap_operation_or(gap_blk, BMGAP_PTR(arg_blk),
5441  tmp_buf, res_len);
5442  BM_ASSERT(res == tmp_buf);
5443  blockman_.assign_gap_check(i, j, res, ++res_len, blk, tmp_buf);
5444  return;
5445  }
5446  // GAP or BIT
5447  //
5448  bm::word_t* new_blk = blockman_.get_allocator().alloc_bit_block();
5449  bm::bit_block_copy(new_blk, arg_blk);
5450  bm::gap_add_to_bitset(new_blk, gap_blk);
5451 
5452  blockman_.get_allocator().free_gap_block(gap_blk, blockman_.glen());
5453  blockman_.set_block_ptr(i, j, new_blk);
5454 
5455  return;
5456  }
5457  else // our block is BITSET-type (but NOT FULL_BLOCK we checked it)
5458  {
5459  if (BM_IS_GAP(arg_blk)) // argument block is GAP-type
5460  {
5461  const bm::gap_word_t* arg_gap = BMGAP_PTR(arg_blk);
5462  if (!blk)
5463  {
5464  bool gap = true;
5465  blk = blockman_.clone_gap_block(arg_gap, gap);
5466  blockman_.set_block(i, j, blk, gap);
5467  return;
5468  }
5469 
5470  // BIT & GAP
5471  bm::gap_add_to_bitset(blk, arg_gap);
5472  return;
5473  } // if arg_gap
5474  }
5475 
5476  if (!blk)
5477  {
5478  blk = blockman_.alloc_.alloc_bit_block();
5479  bm::bit_block_copy(blk, arg_blk);
5480  blockman_.set_block_ptr(i, j, blk);
5481  return;
5482  }
5483 
5484  bool all_one = bm::bit_block_or(blk, arg_blk);
5485  if (all_one)
5486  {
5488  blockman_.get_allocator().free_bit_block(blk);
5489  blockman_.set_block_ptr(i, j, FULL_BLOCK_FAKE_ADDR);
5490  }
5491 
5492 }
5493 
5494 //---------------------------------------------------------------------
5495 
5496 template<class Alloc>
5498  unsigned i, unsigned j,
5499  bm::word_t* blk, const bm::word_t* arg_blk)
5500 {
5501  bm::gap_word_t tmp_buf[bm::gap_equiv_len * 3]; // temporary result
5502  if (!arg_blk) // all bits are set
5503  return; // nothing to do
5504 
5505  if (IS_FULL_BLOCK(arg_blk))
5506  {
5507  if (blk)
5508  {
5509  if (BM_IS_GAP(blk))
5510  bm::gap_invert(BMGAP_PTR(blk));
5511  else
5512  {
5513  if (IS_FULL_BLOCK(blk)) // 1 xor 1 = 0
5514  blockman_.set_block_ptr(i, j, 0);
5515  else
5516  bm::bit_invert((wordop_t*) blk);
5517  }
5518  }
5519  else // blk == 0
5520  {
5521  blockman_.set_block_ptr(i, j, FULL_BLOCK_FAKE_ADDR);
5522  }
5523  return;
5524  }
5525  if (IS_FULL_BLOCK(blk))
5526  {
5527  if (!arg_blk)
5528  return;
5529  // deoptimize block
5530  blk = blockman_.get_allocator().alloc_bit_block();
5531  bm::bit_block_set(blk, ~0u);
5532  blockman_.set_block_ptr(i, j, blk);
5533  }
5534 
5535 
5536  if (BM_IS_GAP(blk)) // our block GAP-type
5537  {
5538  bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
5539  if (BM_IS_GAP(arg_blk)) // both blocks GAP-type
5540  {
5541  const bm::gap_word_t* res;
5542  unsigned res_len;
5543  res = bm::gap_operation_xor(gap_blk,
5544  BMGAP_PTR(arg_blk),
5545  tmp_buf,
5546  res_len);
5547  BM_ASSERT(res == tmp_buf);
5548  blockman_.assign_gap_check(i, j, res, ++res_len, blk, tmp_buf);
5549  return;
5550  }
5551  // GAP or BIT
5552  //
5553  bm::word_t* new_blk = blockman_.get_allocator().alloc_bit_block();
5554  bm::bit_block_copy(new_blk, arg_blk);
5555  bm::gap_xor_to_bitset(new_blk, gap_blk);
5556 
5557  blockman_.get_allocator().free_gap_block(gap_blk, blockman_.glen());
5558  blockman_.set_block_ptr(i, j, new_blk);
5559 
5560  return;
5561  }
5562  else // our block is BITSET-type (but NOT FULL_BLOCK we checked it)
5563  {
5564  if (BM_IS_GAP(arg_blk)) // argument block is GAP-type
5565  {
5566  const bm::gap_word_t* arg_gap = BMGAP_PTR(arg_blk);
5567  if (!blk)
5568  {
5569  bool gap = true;
5570  blk = blockman_.clone_gap_block(arg_gap, gap);
5571  blockman_.set_block(i, j, blk, gap);
5572  return;
5573  }
5574  // BIT & GAP
5575  bm::gap_xor_to_bitset(blk, arg_gap);
5576  return;
5577  } // if arg_gap
5578  }
5579 
5580  if (!blk)
5581  {
5582  blk = blockman_.alloc_.alloc_bit_block();
5583  bm::bit_block_copy(blk, arg_blk);
5584  blockman_.set_block_ptr(i, j, blk);
5585  return;
5586  }
5587 
5588  auto any_bits = bm::bit_block_xor(blk, arg_blk);
5589  if (!any_bits)
5590  {
5591  blockman_.get_allocator().free_bit_block(blk);
5592  blockman_.set_block_ptr(i, j, 0);
5593  }
5594 }
5595 
5596 
5597 //---------------------------------------------------------------------
5598 
5599 
5600 template<class Alloc>
5602  unsigned i, unsigned j, bm::word_t* blk, const bm::word_t* arg_blk)
5603 {
5604  BM_ASSERT(arg_blk && blk);
5605 
5606  if (IS_FULL_BLOCK(arg_blk))
5607  return; // nothing to do
5608 
5609  gap_word_t tmp_buf[bm::gap_equiv_len * 3]; // temporary result
5610 
5611  if (BM_IS_GAP(blk)) // our block GAP-type
5612  {
5613  bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
5614  if (BM_IS_GAP(arg_blk)) // both blocks GAP-type
5615  {
5616  const bm::gap_word_t* res;
5617  unsigned res_len;
5618  res = bm::gap_operation_and(gap_blk,
5619  BMGAP_PTR(arg_blk),
5620  tmp_buf,
5621  res_len);
5622  BM_ASSERT(res == tmp_buf);
5623  blockman_.assign_gap_check(i, j, res, ++res_len, blk, tmp_buf);
5624  return;
5625  }
5626  // GAP & BIT
5627  //
5628  bm::word_t* new_blk = blockman_.get_allocator().alloc_bit_block();
5629  bm::bit_block_copy(new_blk, arg_blk);
5630  bm::id64_t digest = bm::calc_block_digest0(new_blk);
5631 
5632  bm::gap_and_to_bitset(new_blk, gap_blk, digest);
5633 
5634  digest = bm::update_block_digest0(new_blk, digest);
5635  if (!digest)
5636  {
5637  BM_ASSERT(bm::bit_is_all_zero(new_blk));
5638  blockman_.get_allocator().free_bit_block(new_blk);
5639  new_blk = 0;
5640  }
5641  else
5642  {
5643  BM_ASSERT(!bm::bit_is_all_zero(new_blk));
5644  }
5645  blockman_.get_allocator().free_gap_block(gap_blk, blockman_.glen());
5646  blockman_.set_block_ptr(i, j, new_blk);
5647 
5648  return;
5649  }
5650  else // our block is BITSET-type or FULL_BLOCK
5651  {
5652  if (BM_IS_GAP(arg_blk)) // argument block is GAP-type
5653  {
5654  const bm::gap_word_t* arg_gap = BMGAP_PTR(arg_blk);
5655  if (bm::gap_is_all_zero(arg_gap))
5656  {
5657  blockman_.zero_block(i, j);
5658  return;
5659  }
5660  // FULL & GAP is common when AND with set_range() mask
5661  //
5662  if (IS_FULL_BLOCK(blk)) // FULL & gap = gap
5663  {
5664  bool is_new_gap;
5665  bm::word_t* new_blk = blockman_.clone_gap_block(arg_gap, is_new_gap);
5666  if (is_new_gap)
5667  BMSET_PTRGAP(new_blk);
5668 
5669  blockman_.set_block_ptr(i, j, new_blk);
5670 
5671  return;
5672  }
5673  // BIT & GAP
5674  bm::gap_and_to_bitset(blk, arg_gap);
5675  bool empty = bm::bit_is_all_zero(blk);
5676  if (empty) // operation converged bit-block to empty
5677  blockman_.zero_block(i, j);
5678 
5679  return;
5680  } // if arg_gap
5681  }
5682 
5683  // FULL & bit is common when AND with set_range() mask
5684  //
5685  if (IS_FULL_BLOCK(blk)) // FULL & bit = bit
5686  {
5687  bm::word_t* new_blk = blockman_.get_allocator().alloc_bit_block();
5688  bm::bit_block_copy(new_blk, arg_blk);
5689  blockman_.set_block_ptr(i, j, new_blk);
5690 
5691  return;
5692  }
5693  auto any_bits = bm::bit_block_and(blk, arg_blk);
5694  if (!any_bits)
5695  {
5696  blockman_.get_allocator().free_bit_block(blk);
5697  blockman_.set_block_ptr(i, j, 0);
5698  }
5699 }
5700 
5701 //---------------------------------------------------------------------
5702 
5703 template<class Alloc>
5705  unsigned i, unsigned j, bm::word_t* blk, const bm::word_t* arg_blk)
5706 {
5707  BM_ASSERT(arg_blk && blk);
5708 
5709  if (IS_FULL_BLOCK(arg_blk))
5710  {
5711  blockman_.zero_block(i, j);
5712  return;
5713  }
5714 
5715  gap_word_t tmp_buf[bm::gap_equiv_len * 3]; // temporary result
5716 
5717  if (BM_IS_GAP(blk)) // our block GAP-type
5718  {
5719  bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
5720  if (BM_IS_GAP(arg_blk)) // both blocks GAP-type
5721  {
5722  const bm::gap_word_t* res;
5723  unsigned res_len;
5724  res = bm::gap_operation_sub(gap_blk,
5725  BMGAP_PTR(arg_blk),
5726  tmp_buf,
5727  res_len);
5728 
5729  BM_ASSERT(res == tmp_buf);
5730  BM_ASSERT(!(res == tmp_buf && res_len == 0));
5731 
5732  blockman_.assign_gap_check(i, j, res, ++res_len, blk, tmp_buf);
5733  return;
5734  }
5735  // else: argument is BITSET-type (own block is GAP)
5736  blk = blockman_.convert_gap2bitset(i, j, gap_blk);
5737  // fall through to bit-block to bit-block operation
5738  }
5739  else // our block is BITSET-type or FULL_BLOCK
5740  {
5741  if (BM_IS_GAP(arg_blk)) // argument block is GAP-type
5742  {
5743  if (!IS_FULL_BLOCK(blk)) // gap combined to bitset
5744  {
5745  bm::gap_sub_to_bitset(blk, BMGAP_PTR(arg_blk));
5746  bool empty = bm::bit_is_all_zero(blk);
5747  if (empty) // operation converged bit-block to empty
5748  blockman_.zero_block(i, j);
5749  return;
5750  }
5751  // the worst case: convert arg block to bitset
5752  arg_blk =
5753  gap_convert_to_bitset_smart(blockman_.check_allocate_tempblock(),
5754  BMGAP_PTR(arg_blk),
5756  }
5757  }
5758 
5759  // Now here we combine two plain bitblocks using supplied bit function.
5760  bm::word_t* dst = blk;
5761 
5762  bm::word_t* ret;
5763  if (!dst || !arg_blk)
5764  return;
5765 
5766  ret = bm::bit_operation_sub(dst, arg_blk);
5767  if (ret && ret == arg_blk)
5768  {
5769  ret = blockman_.get_allocator().alloc_bit_block();
5770  bm::bit_andnot_arr_ffmask(ret, arg_blk);
5771  }
5772 
5773  if (ret != dst) // block mutation
5774  {
5775  blockman_.set_block_ptr(i, j, ret);
5776  if (IS_VALID_ADDR(dst))
5777  blockman_.get_allocator().free_bit_block(dst);
5778  }
5779 }
5780 
5781 //---------------------------------------------------------------------
5782 
5783 template<class Alloc>
5784 void
5786  bool gap,
5787  bm::word_t* blk,
5788  const bm::word_t* arg_blk,
5789  bool arg_gap,
5790  bm::operation opcode)
5791 {
5792  gap_word_t tmp_buf[bm::gap_equiv_len * 3]; // temporary result
5793  const bm::gap_word_t* res;
5794  unsigned res_len;
5795 
5796  if (opcode == BM_OR || opcode == BM_XOR)
5797  {
5798  if (!blk && arg_gap)
5799  {
5800  blk = blockman_.clone_gap_block(BMGAP_PTR(arg_blk), gap);
5801  blockman_.set_block(nb, blk, gap);
5802  return;
5803  }
5804  }
5805 
5806  if (gap) // our block GAP-type
5807  {
5808  if (arg_gap) // both blocks GAP-type
5809  {
5810  {
5811  gap_operation_func_type gfunc =
5813  BM_ASSERT(gfunc);
5814  res = (*gfunc)(BMGAP_PTR(blk),
5815  BMGAP_PTR(arg_blk),
5816  tmp_buf,
5817  res_len);
5818  }
5819  BM_ASSERT(res == tmp_buf);
5820  BM_ASSERT(!(res == tmp_buf && res_len == 0));
5821 
5822  // if as a result of the operation gap block turned to zero
5823  // we can now replace it with NULL
5824  if (bm::gap_is_all_zero(res))
5825  blockman_.zero_block(nb);
5826  else
5827  blockman_.assign_gap(nb, res, ++res_len, blk, tmp_buf);
5828  return;
5829  }
5830  else // argument is BITSET-type (own block is GAP)
5831  {
5832  // since we can not combine blocks of mixed type
5833  // we need to convert our block to bitset
5834 
5835  if (arg_blk == 0) // Combining against an empty block
5836  {
5837  switch (opcode)
5838  {
5839  case BM_AND: // ("Value" AND 0) == 0
5840  blockman_.zero_block(nb);
5841  return;
5842  case BM_OR: case BM_SUB: case BM_XOR:
5843  return; // nothing to do
5844  default:
5845  return; // nothing to do
5846  }
5847  }
5848  gap_word_t* gap_blk = BMGAP_PTR(blk);
5849  blk = blockman_.convert_gap2bitset(nb, gap_blk);
5850  }
5851  }
5852  else // our block is BITSET-type
5853  {
5854  if (arg_gap) // argument block is GAP-type
5855  {
5856  if (IS_VALID_ADDR(blk))
5857  {
5858  // special case, maybe we can do the job without
5859  // converting the GAP argument to bitblock
5862  BM_ASSERT(gfunc);
5863  (*gfunc)(blk, BMGAP_PTR(arg_blk));
5864 
5865  if (opcode != BM_OR)
5866  {
5867  bool b = bm::bit_is_all_zero(blk);
5868  if (b) // operation converged bit-block to empty
5869  blockman_.zero_block(nb);
5870  }
5871  return;
5872  }
5873 
5874  // the worst case we need to convert argument block to
5875  // bitset type.
5876  gap_word_t* temp_blk = (gap_word_t*) blockman_.check_allocate_tempblock();
5877  arg_blk =
5879  BMGAP_PTR(arg_blk),
5881  }
5882  }
5883 
5884  // Now here we combine two plain bitblocks using supplied bit function.
5885  bm::word_t* dst = blk;
5886 
5887  bm::word_t* ret;
5888  if (dst == 0 && arg_blk == 0)
5889  {
5890  return;
5891  }
5892 
5893  switch (opcode)
5894  {
5895  case BM_AND:
5896  ret = bm::bit_operation_and(dst, arg_blk);
5897  goto copy_block;
5898  case BM_XOR:
5899  ret = bm::bit_operation_xor(dst, arg_blk);
5900  if (ret && (ret == arg_blk) && IS_FULL_BLOCK(dst))
5901  {
5902  ret = blockman_.get_allocator().alloc_bit_block();
5903 #ifdef BMVECTOPT
5904  VECT_XOR_ARR_2_MASK(ret,
5905  arg_blk,
5906  arg_blk + bm::set_block_size,
5907  ~0u);
5908 #else
5909  bm::wordop_t* dst_ptr = (wordop_t*)ret;
5910  const bm::wordop_t* wrd_ptr = (wordop_t*) arg_blk;
5911  const bm::wordop_t* wrd_end =
5912  (wordop_t*) (arg_blk + bm::set_block_size);
5913 
5914  do
5915  {
5916  dst_ptr[0] = bm::all_bits_mask ^ wrd_ptr[0];
5917  dst_ptr[1] = bm::all_bits_mask ^ wrd_ptr[1];
5918  dst_ptr[2] = bm::all_bits_mask ^ wrd_ptr[2];
5919  dst_ptr[3] = bm::all_bits_mask ^ wrd_ptr[3];
5920 
5921  dst_ptr+=4;
5922  wrd_ptr+=4;
5923 
5924  } while (wrd_ptr < wrd_end);
5925 #endif
5926  break;
5927  }
5928  goto copy_block;
5929  case BM_OR:
5930  ret = bm::bit_operation_or(dst, arg_blk);
5931  copy_block:
5932  if (ret && (ret == arg_blk) && !IS_FULL_BLOCK(ret))
5933  {
5934  ret = blockman_.get_allocator().alloc_bit_block();
5935  bm::bit_block_copy(ret, arg_blk);
5936  }
5937  break;
5938 
5939  case BM_SUB:
5940  ret = bit_operation_sub(dst, arg_blk);
5941  if (ret && ret == arg_blk)
5942  {
5943  ret = blockman_.get_allocator().alloc_bit_block();
5944  bm::bit_andnot_arr_ffmask(ret, arg_blk);
5945  }
5946  break;
5947  default:
5948  BM_ASSERT(0);
5949  ret = 0;
5950  }
5951 
5952  if (ret != dst) // block mutation
5953  {
5954  blockman_.set_block(nb, ret);
5955  if (IS_VALID_ADDR(dst))
5956  {
5957  blockman_.get_allocator().free_bit_block(dst);
5958  }
5959  }
5960 }
5961 
5962 //---------------------------------------------------------------------
5963 
5964 template<class Alloc>
5966  bm::id_t right)
5967 {
5968  unsigned nblock_left = unsigned(left >> bm::set_block_shift);
5969  unsigned nblock_right = unsigned(right >> bm::set_block_shift);
5970 
5971  unsigned nbit_right = unsigned(right & bm::set_block_mask);
5972 
5973  unsigned r =
5974  (nblock_left == nblock_right) ? nbit_right :(bm::bits_in_block-1);
5975 
5976  bm::gap_word_t tmp_gap_blk[5];
5977  tmp_gap_blk[0] = 0; // just to silence GCC warning on uninit var
5978 
5979  // Set bits in the starting block
5980 
5981  unsigned nb;
5982  bm::word_t* block; //= blockman_.get_block(nblock_left);
5983  unsigned nbit_left = unsigned(left & bm::set_block_mask);
5984  if ((nbit_left == 0) && (r == bm::bits_in_block - 1)) // full block
5985  {
5986  nb = nblock_left;
5987  }
5988  else
5989  {
5990  gap_init_range_block<gap_word_t>(tmp_gap_blk,
5991  (gap_word_t)nbit_left,
5992  (gap_word_t)r,
5993  (gap_word_t)1);
5994  block = blockman_.get_block(nblock_left);
5995  combine_operation_with_block(nblock_left,
5996  BM_IS_GAP(block),
5997  block,
5998  (bm::word_t*) tmp_gap_blk,
5999  1, BM_OR);
6000 
6001  if (nblock_left == nblock_right) // in one block
6002  return;
6003  nb = nblock_left+1;
6004  }
6005 
6006  // Set all full blocks between left and right
6007  //
6008  unsigned nb_to = nblock_right + (nbit_right ==(bm::bits_in_block-1));
6009  for (; nb < nb_to; ++nb)
6010  {
6011  block = blockman_.get_block(nb);
6012  if (IS_FULL_BLOCK(block))
6013  continue;
6014  blockman_.set_block_all_set(nb);
6015  } // for
6016 
6017  if (nb_to > nblock_right)
6018  return;
6019 
6020  block = blockman_.get_block(nblock_right);
6021 
6022  gap_init_range_block<gap_word_t>(tmp_gap_blk,
6023  (gap_word_t)0,
6024  (gap_word_t)nbit_right,
6025  (gap_word_t)1);
6026 
6027  combine_operation_with_block(nblock_right,
6028  BM_IS_GAP(block),
6029  block,
6030  (bm::word_t*) tmp_gap_blk,
6031  1, BM_OR);
6032 }
6033 
6034 //---------------------------------------------------------------------
6035 
6036 template<class Alloc>
6038  bm::id_t right)
6039 {
6040  unsigned nb;
6041 
6042  // calculate logical number of start and destination blocks
6043  unsigned nblock_left = unsigned(left >> bm::set_block_shift);
6044  unsigned nblock_right = unsigned(right >> bm::set_block_shift);
6045 
6046  unsigned nbit_right = unsigned(right & bm::set_block_mask);
6047  unsigned r =
6048  (nblock_left == nblock_right) ? nbit_right : (bm::bits_in_block - 1);
6049 
6050  bm::gap_word_t tmp_gap_blk[5];
6051  tmp_gap_blk[0] = 0; // just to silence GCC warning on uninit var
6052 
6053  // Set bits in the starting block
6054  bm::word_t* block;// = blockman_.get_block(nblock_left);
6055 
6056  unsigned nbit_left = unsigned(left & bm::set_block_mask);
6057  if ((nbit_left == 0) && (r == bm::bits_in_block - 1)) // full block
6058  {
6059  nb = nblock_left;
6060  }
6061  else
6062  {
6063  bm::gap_init_range_block<gap_word_t>(tmp_gap_blk,
6064  (gap_word_t)nbit_left,
6065  (gap_word_t)r,
6066  (gap_word_t)0);
6067  block = blockman_.get_block(nblock_left);
6068  combine_operation_with_block(nblock_left,
6069  BM_IS_GAP(block),
6070  block,
6071  (bm::word_t*) tmp_gap_blk,
6072  1,
6073  BM_AND);
6074 
6075  if (nblock_left == nblock_right) // in one block
6076  return;
6077  nb = nblock_left + 1;
6078  }
6079 
6080  // Clear all full blocks between left and right
6081 
6082  unsigned nb_to = nblock_right + (nbit_right == (bm::bits_in_block - 1));
6083  for (; nb < nb_to; ++nb)
6084  {
6085  int no_more_blocks;
6086  block = blockman_.get_block(nb, &no_more_blocks);
6087  if (no_more_blocks)
6088  {
6089  BM_ASSERT(block == 0);
6090  return;
6091  }
6092  if (!block) // nothing to do
6093  continue;
6094  blockman_.zero_block(nb);
6095  } // for
6096 
6097  if (nb_to > nblock_right)
6098  return;
6099 
6100  block = blockman_.get_block(nblock_right);
6101  gap_init_range_block<gap_word_t>(tmp_gap_blk,
6102  (gap_word_t)0,
6103  (gap_word_t)nbit_right,
6104  (gap_word_t)0);
6105 
6106  combine_operation_with_block(nblock_right,
6107  BM_IS_GAP(block),
6108  block,
6109  (bm::word_t*) tmp_gap_blk,
6110  1,
6111  BM_AND);
6112 }
6113 
6114 
6115 //---------------------------------------------------------------------
6116 
6117 template<class Alloc>
6119  bm::id_t left,
6120  bm::id_t right)
6121 {
6122  if (!bvect.blockman_.is_init())
6123  {
6124  clear();
6125  return;
6126  }
6127 
6128  if (blockman_.is_init())
6129  {
6130  blockman_.deinit_tree();
6131  }
6132  if (left > right)
6133  bm::xor_swap(left, right);
6134 
6135  copy_range_no_check(bvect, left, right);
6136 }
6137 
6138 
6139 //---------------------------------------------------------------------
6140 
6141 template<class Alloc>
6143  bm::id_t left,
6144  bm::id_t right)
6145 {
6146  BM_ASSERT(left <= right);
6147  BM_ASSERT_THROW(right < bm::id_max, BM_ERR_RANGE);
6148 
6149  // copy all block(s) belonging to our range
6150  unsigned nblock_left = unsigned(left >> bm::set_block_shift);
6151  unsigned nblock_right = unsigned(right >> bm::set_block_shift);
6152 
6153  blockman_.copy(bvect.blockman_, nblock_left, nblock_right);
6154 
6155  // clear the flanks
6156  //
6157  if (left)
6158  {
6159  bm::id_t from =
6160  (left + bm::gap_max_bits >= left) ? 0u : left - bm::gap_max_bits;
6161  clear_range_no_check(from, left-1);
6162  }
6163  if (right+1 < bm::id_max)
6164  {
6165  clear_range_no_check(right+1, bm::id_max-1);
6166  }
6167 }
6168 
6169 //---------------------------------------------------------------------
6170 
6171 template<class Alloc>
6173 {
6174 #ifndef BM_NO_STL
6175  throw std::bad_alloc();
6176 #else
6177  BM_THROW(BM_ERR_BADALLOC);
6178 #endif
6179 }
6180 
6181 //---------------------------------------------------------------------
6182 //
6183 //---------------------------------------------------------------------
6184 
6185 inline
6187 {
6188  copy_from(rsi);
6189 }
6190 
6191 //---------------------------------------------------------------------
6192 
6193 inline
6195 {
6196  ::memset(this->bcount, 0, sizeof(this->bcount));
6197  ::memset(this->subcount, 0, sizeof(this->subcount));
6198 
6199  this->total_blocks = 0;
6200 }
6201 
6202 //---------------------------------------------------------------------
6203 
6204 inline
6206 {
6207  ::memcpy(this->bcount, rsi.bcount, sizeof(this->bcount));
6208  ::memcpy(this->subcount, rsi.subcount, sizeof(this->subcount));
6209  this->total_blocks = rsi.total_blocks;
6210 }
6211 
6212 //---------------------------------------------------------------------
6213 
6214 inline
6215 unsigned rs_index::count(unsigned nb) const
6216 {
6217  return (nb == 0) ? bcount[nb]
6218  : bcount[nb] - bcount[nb-1];
6219 }
6220 
6221 //---------------------------------------------------------------------
6222 
6223 inline
6224 unsigned rs_index::find_sub_range(unsigned block_bit_pos) const
6225 {
6226  return (block_bit_pos <= rs3_border0) ? 0 :
6227  (block_bit_pos > rs3_border1) ? 2 : 1;
6228 }
6229 
6230 
6231 //---------------------------------------------------------------------
6232 
6233 inline
6234 bm::gap_word_t rs_index::select_sub_range(unsigned nb, unsigned& rank) const
6235 {
6236  if (rank > this->subcount[nb].first)
6237  {
6238  rank -= this->subcount[nb].first;
6239  if (rank > this->subcount[nb].second)
6240  {
6241  rank -= this->subcount[nb].second;
6242  return rs3_border1 + 1;
6243  }
6244  else
6245  return rs3_border0 + 1;
6246  }
6247  return 0;
6248 }
6249 
6250 //---------------------------------------------------------------------
6251 
6252 
6253 
6254 } // namespace
6255 
6256 #include "bmundef.h"
6257 
6258 #ifdef _MSC_VER
6259 #pragma warning( pop )
6260 #endif
6261 
6262 
6263 #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:991
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:4643
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:4854
unsigned gap_find_last(const T *buf, unsigned *last)
GAP block find the last set bit.
Definition: bmfunc.h:1037
void bit_invert(T *start)
Definition: bmfunc.h:4312
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:5656
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:4469
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:5973
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
#define BM_VECT_ALIGN
Definition: bmdef.h:293
bm::gap_word_t select_sub_range(unsigned nb, unsigned &rank) const
determine block sub-range for rank search
Definition: bm.h:6234
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:1213
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:5937
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:2461
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
std::output_iterator_tag iterator_category
Definition: bm.h:480
unsigned char bits[set_bitscan_wave_size *32]
bit list
Definition: bm.h:347
bm::bvector< Alloc > & bit_sub(const bm::bvector< Alloc > &bv1, const bm::bvector< Alloc > &bv2, bm::bvector< Alloc >::optmode opt_mode)
3-operand SUB : this := bv1 MINUS bv2 SUBtraction is also known as AND NOT
Definition: bm.h:4628
const unsigned set_word_shift
Definition: bmconst.h:64
void combine_operation_or(const bm::bvector< Alloc > &bvect)
perform a set-algebra operation OR
Definition: bm.h:4721
~bvector() BMNOEXEPT
Definition: bm.h:1329
void gap_xor_to_bitset(unsigned *dest, const T *pcurr)
XOR GAP block to bitblock.
Definition: bmfunc.h:2755
bool test(bm::id_t n) const
returns true if bit n is set and false is bit n is 0.
Definition: bm.h:1788
void combine_operation_xor(const bm::bvector< Alloc > &bvect)
perform a set-algebra operation XOR
Definition: bm.h:4785
bvector< Alloc > & set()
Sets every bit in this bitset to 1.
Definition: bm.h:3358
bm::id_t value() const
Get current position (value)
Definition: bm.h:643
bm::bvector< Alloc > & bit_or(const bm::bvector< Alloc > &bv1, const bm::bvector< Alloc > &bv2, bm::bvector< Alloc >::optmode opt_mode)
3-operand OR : this := bv1 OR bv2
Definition: bm.h:4377
insert_iterator(bvector< Alloc > &bvect)
Definition: bm.h:407