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