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