BitMagic-C++
bmbmatrix.h
Go to the documentation of this file.
1#ifndef BMBMATRIX__H__INCLUDED__
2#define BMBMATRIX__H__INCLUDED__
3/*
4Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
5
6Licensed under the Apache License, Version 2.0 (the "License");
7you may not use this file except in compliance with the License.
8You may obtain a copy of the License at
9
10 http://www.apache.org/licenses/LICENSE-2.0
11
12Unless required by applicable law or agreed to in writing, software
13distributed under the License is distributed on an "AS IS" BASIS,
14WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15See the License for the specific language governing permissions and
16limitations under the License.
17
18For more information please visit: http://bitmagic.io
19*/
20
21/*! \file bmbmatrix.h
22 \brief basic bit-matrix class and utilities
23*/
24
25#include <stddef.h>
26#include "bmconst.h"
27
28#ifndef BM_NO_STL
29#include <stdexcept>
30#endif
31
32#include "bm.h"
33#include "bmtrans.h"
34#include "bmdef.h"
35
36
37
38namespace bm
39{
40
41/**
42 Basic dense bit-matrix class.
43
44 Container of row-major bit-vectors, forming a bit-matrix.
45 This class uses dense form of row storage.
46 It is applicable as a build block for other sparse containers and
47 succinct data structures, implementing high level abstractions.
48
49 @ingroup bmagic
50 @internal
51*/
52template<typename BV>
54{
55public:
56 typedef BV bvector_type;
59 typedef typename BV::allocator_type allocator_type;
61 typedef typename allocator_type::allocator_pool_type allocator_pool_type;
64 typedef unsigned char octet_type;
65
66public:
67 // ------------------------------------------------------------
68 /*! @name Construction, assignment */
69 ///@{
70
73 size_type bv_max_size = bm::id_max,
74 const allocator_type& alloc = allocator_type());
76
77 /*! copy-ctor */
79 basic_bmatrix<BV>& operator=(const basic_bmatrix<BV>& bbm)
80 {
81 copy_from(bbm);
82 return *this;
83 }
84
85#ifndef BM_NO_CXX11
86 /*! move-ctor */
88
89 /*! move assignmment operator */
91 {
92 if (this != &bbm)
93 {
94 free_rows();
95 swap(bbm);
96 }
97 return *this;
98 }
99#endif
100
102 { pool_ = pool_ptr; }
103
104 ///@}
105
106 // ------------------------------------------------------------
107 /*! @name content manipulation */
108 ///@{
109
110 /*! Swap content */
112
113 /*! Copy content */
114 void copy_from(const basic_bmatrix<BV>& bbm);
115
116 ///@}
117
118 // ------------------------------------------------------------
119 /*! @name row access */
120 ///@{
121
122 /*! Get row bit-vector. Can return NULL */
124
125 /*! Get row bit-vector. Can return NULL */
127
128 /*! Get row bit-vector. Can return NULL */
130
131 /*! get number of value rows */
132 size_type rows() const BMNOEXCEPT { return rsize_; }
133
134 /*! Make sure row is constructed, return bit-vector */
136
137 /*! Make sure row is copy-constructed, return bit-vector */
139
141 ///@}
142
143
144 // ------------------------------------------------------------
145 /*! @name octet access and transposition */
146 ///@{
147
148 /*!
149 Bit-transpose an octet and assign it to a bit-matrix
150
151 @param pos - column position in the matrix
152 @param octet_idx - octet based row position (1 octet - 8 rows)
153 @param octet - value to assign
154 */
155 void set_octet(size_type pos, size_type octet_idx, unsigned char octet);
156
157 /*!
158 Bit-transpose and insert an octet and assign it to a bit-matrix
159
160 @param pos - column position in the matrix
161 @param octet_idx - octet based row position (1 octet - 8 rows)
162 @param octet - value to assign
163 */
164 void insert_octet(size_type pos, size_type octet_idx, unsigned char octet);
165
166 /*!
167 return octet from the matrix
168
169 @param pos - column position in the matrix
170 @param octet_idx - octet based row position (1 octet - 8 rows)
171 */
172 unsigned char get_octet(size_type pos, size_type octet_idx) const BMNOEXCEPT;
173
174 /*!
175 Compare vector[pos] with octet
176
177 It uses regulat comparison of chars to comply with the (signed)
178 char sort order.
179
180 @param pos - column position in the matrix
181 @param octet_idx - octet based row position (1 octet - 8 rows)
182 @param octet - octet value to compare
183
184 @return 0 - equal, -1 - less(vect[pos] < octet), 1 - greater
185 */
187 size_type octet_idx, char octet) const BMNOEXCEPT;
188
189 ///@}
190
191public:
192
193 // ------------------------------------------------------------
194 /*! @name Utility function */
195 ///@{
196
197 /// Test if 4 rows from i are not NULL
198 bool test_4rows(unsigned i) const BMNOEXCEPT;
199
200 /// Get low level internal access to
202 unsigned i, unsigned j) const BMNOEXCEPT;
203
204 unsigned get_half_octet(size_type pos, size_type row_idx) const BMNOEXCEPT;
205
206 /*!
207 \brief run memory optimization for all bit-vector rows
208 \param temp_block - pre-allocated memory block to avoid re-allocs
209 \param opt_mode - requested compression depth
210 \param stat - memory allocation statistics after optimization
211 */
213 bm::word_t* temp_block = 0,
215 typename bvector_type::statistics* stat = 0);
216
217 /*! Optimize block in all planes
218 @internal
219 */
221
222 ///@}
223
224
225protected:
228
231
232 static
233 void throw_bad_alloc() { BV::throw_bad_alloc(); }
234
235
236protected:
241
244};
245
246/**
247 Base class for bit-transposed sparse vector construction
248
249 @ingroup bmagic
250 @internal
251*/
252template<typename Val, typename BV, unsigned MAX_SIZE>
254{
255public:
257 {
258 sv_plains = (sizeof(Val) * 8 * MAX_SIZE + 1),
259 sv_value_plains = (sizeof(Val) * 8 * MAX_SIZE)
260 };
261
263 {
264 max_vector_size = MAX_SIZE
265 };
266
267 typedef Val value_type;
268 typedef BV bvector_type;
269 typedef typename BV::size_type size_type;
273 typedef typename BV::allocator_type allocator_type;
276 typedef typename allocator_type::allocator_pool_type allocator_pool_type;
278
279public:
281
284 size_type bv_max_size,
285 const allocator_type& alloc);
286
288
289#ifndef BM_NO_CXX11
290 /*! move-ctor */
292 {
293 bmatr_.swap(bsv.bmatr_);
294 size_ = bsv.size_;
295 effective_plains_ = bsv.effective_plains_;
296 bsv.size_ = 0;
297 }
298#endif
299
301
302 size_type size() const BMNOEXCEPT { return size_; }
303
304 void resize(size_type new_size);
305
306 void clear_range(size_type left, size_type right, bool set_null);
307
308 /*! \brief resize to zero, free memory */
310
311 /*! return true if empty */
312 bool empty() const BMNOEXCEPT { return size() == 0; }
313
314public:
315
316 // ------------------------------------------------------------
317 /*! @name Various traits */
318 //@{
319 /**
320 \brief check if container supports NULL(unassigned) values
321 */
323 { return bmatr_.get_row(this->null_plain()) != 0; }
324
325 /**
326 \brief Get bit-vector of assigned values or NULL
327 (if not constructed that way)
328 */
329 const bvector_type* get_null_bvector() const BMNOEXCEPT
330 { return bmatr_.get_row(this->null_plain()); }
331
332 /** \brief test if specified element is NULL
333 \param idx - element index
334 \return true if it is NULL false if it was assigned or container
335 is not configured to support assignment flags
336 */
337 bool is_null(size_type idx) const BMNOEXCEPT;
338
339
340 ///@}
341
342
343 // ------------------------------------------------------------
344 /*! @name Access to internals */
345 ///@{
346
347 /*!
348 \brief get access to bit-plain, function checks and creates a plain
349 \return bit-vector for the bit plain
350 */
352
353 /*!
354 \brief get read-only access to bit-plain
355 \return bit-vector for the bit plain or NULL
356 */
358 get_plain(unsigned i) const BMNOEXCEPT { return bmatr_.row(i); }
359
360 /*!
361 \brief get total number of bit-plains in the vector
362 */
363 static unsigned plains() BMNOEXCEPT { return value_bits(); }
364
365 /** Number of stored bit-plains (value plains + extra */
366 static unsigned stored_plains() BMNOEXCEPT { return value_bits()+1; }
367
368
369 /** Number of effective bit-plains in the value type */
371 { return effective_plains_ + 1; }
372
373 /*!
374 \brief get access to bit-plain as is (can return NULL)
375 */
376 bvector_type_ptr plain(unsigned i) BMNOEXCEPT { return bmatr_.get_row(i); }
378 { return bmatr_.get_row(i); }
379
381
382 /*!
383 \brief free memory in bit-plain
384 */
385 void free_plain(unsigned i) { bmatr_.destruct_row(i); }
386
387 /*!
388 return mask of allocated bit-plains
389 1 in the mask - means bit-plain N is present
390 returns 64-bit unsigned mask for sub 64-bit types (like int)
391 unallocated mask bits will be zero extended
392
393 @return 64-bit mask
394 @internal
395 */
396 bm::id64_t get_plains_mask(unsigned element_idx) const BMNOEXCEPT;
397
398 /*!
399 get read-only access to inetrnal bit-matrix
400 */
401 const bmatrix_type& get_bmatrix() const BMNOEXCEPT { return bmatr_; }
402 ///@}
403
404 /*!
405 \brief run memory optimization for all bit-vector rows
406 \param temp_block - pre-allocated memory block to avoid unnecessary re-allocs
407 \param opt_mode - requested compression depth
408 \param stat - memory allocation statistics after optimization
409 */
410 void optimize(bm::word_t* temp_block = 0,
412 typename bvector_type::statistics* stat = 0);
413
414 /*!
415 @brief Calculates memory statistics.
416
417 Function fills statistics structure containing information about how
418 this vector uses memory and estimation of max. amount of memory
419 bvector needs to serialize itself.
420
421 @param st - pointer on statistics structure to be filled in.
422
423 @sa statistics
424 */
426
427 /*!
428 \brief check if another sparse vector has the same content and size
429
430 \param sv - sparse vector for comparison
431 \param null_able - flag to consider NULL vector in comparison (default)
432 or compare only value content plains
433
434 \return true, if it is the same
435 */
437 bm::null_support null_able = bm::use_null) const BMNOEXCEPT;
438
439protected:
441
442 /*!
443 clear column in all value plains
444 \param plain_idx - row (plain index to start from)
445 \param idx - bit (column) to clear
446 */
447 void clear_value_plains_from(unsigned plain_idx, size_type idx);
448
449 /*!
450 insert false (clear) column in all value plains
451 \param plain_idx - row (plain index to start from)
452 \param idx - bit (column) to clear insert
453 */
454 void insert_clear_value_plains_from(unsigned plain_idx, size_type idx);
455
456 /*!
457 erase bit (column) from all plains
458 \param idx - bit (column) to erase
459 */
461
462 /*!
463 insert (NOT) NULL value
464 */
465 void insert_null(size_type idx, bool not_null);
466
467protected:
469
470 /** Number of total bit-plains in the value type*/
475
476 /** plain index for the "NOT NULL" flags plain */
477 static unsigned null_plain() BMNOEXCEPT { return value_bits(); }
478
479 /** optimize block in all matrix plains */
481 {
483 }
484
485 /**
486 Perform copy_range() on a set of plains
487 */
492 bm::null_support splice_null);
493
494protected:
495 bmatrix_type bmatr_; ///< bit-transposed matrix
496 size_type size_; ///< array size
498
499};
500
501//---------------------------------------------------------------------
502//
503//---------------------------------------------------------------------
504
505template<typename BV>
508 size_type bv_max_size,
509 const allocator_type& alloc)
510: bv_size_(bv_max_size),
511 alloc_(alloc),
512 ap_(ap),
513 pool_(0),
514 bv_rows_(0),
515 rsize_(0)
516{
517 allocate_rows(rsize);
518}
519
520//---------------------------------------------------------------------
521
522template<typename BV>
527
528//---------------------------------------------------------------------
529
530template<typename BV>
532: bv_size_(bbm.bv_size_),
533 alloc_(bbm.alloc_),
534 ap_(bbm.ap_),
535 pool_(0),
536 bv_rows_(0),
537 rsize_(0)
538{
539 copy_from(bbm);
540}
541
542//---------------------------------------------------------------------
543
544template<typename BV>
546: bv_size_(bbm.bv_size_),
547 alloc_(bbm.alloc_),
548 ap_(bbm.ap_),
549 pool_(0),
550 bv_rows_(0),
551 rsize_(0)
552{
553 swap(bbm);
554}
555
556//---------------------------------------------------------------------
557
558template<typename BV>
561{
562 BM_ASSERT(i < rsize_);
563 return bv_rows_[i];
564}
565
566//---------------------------------------------------------------------
567
568template<typename BV>
571{
572 BM_ASSERT(i < rsize_);
573 return bv_rows_[i];
574}
575
576//---------------------------------------------------------------------
577
578template<typename BV>
581{
582 BM_ASSERT(i < rsize_);
583 return bv_rows_[i];
584}
585
586//---------------------------------------------------------------------
587
588template<typename BV>
590{
591 BM_ASSERT((j + 4) <= rsize_);
592#if defined(BM64_SSE4)
593 __m128i w0 = _mm_loadu_si128((__m128i*)(bv_rows_ + j));
594 __m128i w1 = _mm_loadu_si128((__m128i*)(bv_rows_ + j + 2));
595 w0 = _mm_or_si128(w0, w1);
596 return !_mm_testz_si128(w0, w0);
597#elif defined(BM64_AVX2) || defined(BM64_AVX512)
598 __m256i w0 = _mm256_loadu_si256((__m256i*)(bv_rows_ + j));
599 return !_mm256_testz_si256(w0, w0);
600#else
601 bool b = bv_rows_[j + 0] || bv_rows_[j + 1] ||
602 bv_rows_[j + 2] || bv_rows_[j + 3];
603 return b;
604#endif
605}
606
607//---------------------------------------------------------------------
608
609template<typename BV>
611{
612 if (this == &bbm) // nothing to do
613 return;
614 free_rows();
615
616 bv_size_ = bbm.bv_size_;
617 alloc_ = bbm.alloc_;
618 ap_ = bbm.ap_;
619
620 size_type rsize = bbm.rsize_;
621 if (rsize)
622 {
623 bv_rows_ = (bvector_type_ptr*)alloc_.alloc_ptr(rsize);
624 if (!bv_rows_)
625 throw_bad_alloc();
626 else
627 {
628 rsize_ = rsize;
629 for (size_type i = 0; i < rsize_; ++i)
630 {
631 const bvector_type_ptr bv = bbm.bv_rows_[i];
632 bv_rows_[i] = bv ? construct_bvector(bv) : 0;
633 }
634 }
635 }
636
637}
638
639
640//---------------------------------------------------------------------
641
642template<typename BV>
644{
645 BM_ASSERT(!bv_rows_);
646
647 if (rsize)
648 {
649 bv_rows_ = (bvector_type_ptr*)alloc_.alloc_ptr(unsigned(rsize));
650 if (!bv_rows_)
651 throw_bad_alloc();
652 else
653 {
654 rsize_ = rsize;
655 for (size_type i = 0; i < rsize; ++i)
656 bv_rows_[i] = 0;
657 }
658 }
659}
660
661//---------------------------------------------------------------------
662
663template<typename BV>
665{
666 for (size_type i = 0; i < rsize_; ++i)
667 {
668 bvector_type_ptr bv = bv_rows_[i];
669 if (bv)
670 {
671 destruct_bvector(bv);
672 bv_rows_[i] = 0;
673 }
674 } // for i
675 if (bv_rows_)
676 {
677 alloc_.free_ptr(bv_rows_, unsigned(rsize_));
678 }
679 bv_rows_ = 0;
680}
681
682//---------------------------------------------------------------------
683
684template<typename BV>
686{
687 if (this == &bbm)
688 return;
689
690 bm::xor_swap(bv_size_, bbm.bv_size_);
691
692 allocator_type alloc_tmp = alloc_;
693 alloc_ = bbm.alloc_;
694 bbm.alloc_ = alloc_tmp;
695
696 allocation_policy_type ap_tmp = ap_;
697 ap_ = bbm.ap_;
698 bbm.ap_ = ap_tmp;
699
700 allocator_pool_type* pool_tmp = pool_;
701 pool_ = bbm.pool_;
702 bbm.pool_ = pool_tmp;
703
704 bm::xor_swap(rsize_, bbm.rsize_);
705
706 bvector_type_ptr* rtmp = bv_rows_;
707 bv_rows_ = bbm.bv_rows_;
708 bbm.bv_rows_ = rtmp;
709}
710
711//---------------------------------------------------------------------
712
713template<typename BV>
716{
717 BM_ASSERT(row < rsize_);
718 bvector_type_ptr bv = bv_rows_[row];
719 if (!bv)
720 {
721 bv = bv_rows_[row] = construct_bvector(0);
722 }
723 return bv;
724}
725
726//---------------------------------------------------------------------
727
728template<typename BV>
731{
732 BM_ASSERT(row < rsize_);
733 bvector_type_ptr bv = bv_rows_[row];
734 if (bv)
735 {
736 *bv = bv_src;
737 }
738 else
739 {
740 bv = bv_rows_[row] = construct_bvector(&bv_src);
741 }
742 return bv;
743}
744
745
746//---------------------------------------------------------------------
747
748template<typename BV>
750{
751 BM_ASSERT(row < rsize_);
752 bvector_type_ptr bv = bv_rows_[row];
753 if (bv)
754 {
755 destruct_bvector(bv);
756 bv_rows_[row] = 0;
757 }
758}
759
760
761//---------------------------------------------------------------------
762
763template<typename BV>
766{
767 bvector_type* rbv = 0;
768#ifdef BM_NO_STL // C compatibility mode
769 void* mem = ::malloc(sizeof(bvector_type));
770 if (mem == 0)
771 {
772 BM_THROW(false, BM_ERR_BADALLOC);
773 }
774 rbv = bv ? new(mem) bvector_type(*bv)
775 : new(mem) bvector_type(ap_.strat, ap_.glevel_len,
776 bv_size_,
777 alloc_);
778#else
779 rbv = bv ? new bvector_type(*bv)
780 : new bvector_type(ap_.strat, ap_.glevel_len,
781 bv_size_,
782 alloc_);
783#endif
784 return rbv;
785}
786
787//---------------------------------------------------------------------
788
789template<typename BV>
791{
792#ifdef BM_NO_STL // C compatibility mode
793 bv->~TBM_bvector();
794 ::free((void*)bv);
795#else
796 delete bv;
797#endif
798}
799
800//---------------------------------------------------------------------
801
802template<typename BV>
803const bm::word_t*
805 unsigned i, unsigned j) const BMNOEXCEPT
806{
807 bvector_type_const_ptr bv = this->row(p);
808 if (bv)
809 {
810 const typename bvector_type::blocks_manager_type& bman =
811 bv->get_blocks_manager();
812 return bman.get_block_ptr(i, j);
813 }
814 return 0;
815}
816
817
818//---------------------------------------------------------------------
819
820template<typename BV>
822 size_type octet_idx,
823 unsigned char octet)
824{
825 BM_ASSERT(octet_idx * 8u < rsize_);
826
827 size_type oct = octet;
828 size_type row = octet_idx * 8;
829 size_type row_end = row + 8;
830 for (; row < row_end; ++row)
831 {
832 bvector_type* bv = this->get_row(row);
833 if (oct & 1u)
834 {
835 if (!bv)
836 {
837 bv = this->construct_row(row);
838 bv->init();
839 }
840 bv->set_bit_no_check(pos);
841 }
842 else
843 {
844 if (bv)
845 bv->clear_bit_no_check(pos);
846 }
847 oct >>= 1;
848 if (!oct)
849 break;
850 } // for
851
852 // clear the tail
853 for (++row; row < row_end; ++row)
854 {
855 bvector_type* bv = this->get_row(row);
856 if (bv)
857 bv->clear_bit_no_check(pos);
858 } // for
859}
860
861//---------------------------------------------------------------------
862
863template<typename BV>
865 size_type octet_idx,
866 unsigned char octet)
867{
868 BM_ASSERT(octet_idx * 8u < rsize_);
869
870 size_type oct = octet;
871 size_type row = octet_idx * 8;
872 size_type row_end = row + 8;
873 for (; row < row_end; ++row)
874 {
875 bvector_type* bv = this->get_row(row);
876 if (oct & 1u)
877 {
878 if (!bv)
879 {
880 bv = this->construct_row(row);
881 bv->init();
882 bv->set_bit_no_check(pos);
883 }
884 else
885 {
886 bv->insert(pos, true);
887 }
888 }
889 else
890 {
891 if (bv)
892 bv->insert(pos, false);
893 }
894 oct >>= 1;
895 if (!oct)
896 break;
897 } // for
898
899 // clear the tail
900 for (++row; row < row_end; ++row)
901 {
902 bvector_type* bv = this->get_row(row);
903 if (bv)
904 bv->insert(pos, false);
905 } // for
906}
907
908
909//---------------------------------------------------------------------
910
911template<typename BV>
912unsigned char
914{
915 unsigned v = 0;
916
918 unsigned i0 = unsigned(nb >> bm::set_array_shift); // top block address
919 unsigned j0 = unsigned(nb & bm::set_array_mask); // address in sub-block
920
921 const bm::word_t* blk;
922 const bm::word_t* blka[8];
923 unsigned nbit = unsigned(pos & bm::set_block_mask);
924 unsigned nword = unsigned(nbit >> bm::set_word_shift);
925 unsigned mask0 = 1u << (nbit & bm::set_word_mask);
926
927 unsigned row_idx = unsigned(octet_idx * 8);
928
929 blka[0] = get_block(row_idx+0, i0, j0);
930 blka[1] = get_block(row_idx+1, i0, j0);
931 blka[2] = get_block(row_idx+2, i0, j0);
932 blka[3] = get_block(row_idx+3, i0, j0);
933 blka[4] = get_block(row_idx+4, i0, j0);
934 blka[5] = get_block(row_idx+5, i0, j0);
935 blka[6] = get_block(row_idx+6, i0, j0);
936 blka[7] = get_block(row_idx+7, i0, j0);
937 unsigned is_set;
938
939 if ((blk = blka[0])!=0)
940 {
941 if (blk == FULL_BLOCK_FAKE_ADDR)
942 is_set = 1;
943 else
944 is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
945 v |= (unsigned)bool(is_set);
946 }
947 if ((blk = blka[1])!=0)
948 {
949 if (blk == FULL_BLOCK_FAKE_ADDR)
950 is_set = 1;
951 else
952 is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
953 v |= unsigned(bool(is_set)) << 1u;
954 }
955 if ((blk = blka[2])!=0)
956 {
957 if (blk == FULL_BLOCK_FAKE_ADDR)
958 is_set = 1;
959 else
960 is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
961 v |= unsigned(bool(is_set)) << 2u;
962 }
963 if ((blk = blka[3])!=0)
964 {
965 if (blk == FULL_BLOCK_FAKE_ADDR)
966 is_set = 1;
967 else
968 is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
969 v |= unsigned(bool(is_set)) << 3u;
970 }
971
972
973 if ((blk = blka[4])!=0)
974 {
975 if (blk == FULL_BLOCK_FAKE_ADDR)
976 is_set = 1;
977 else
978 is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
979 v |= unsigned(bool(is_set)) << 4u;
980 }
981 if ((blk = blka[5])!=0)
982 {
983 if (blk == FULL_BLOCK_FAKE_ADDR)
984 is_set = 1;
985 else
986 is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
987 v |= unsigned(bool(is_set)) << 5u;
988 }
989 if ((blk = blka[6])!=0)
990 {
991 if (blk == FULL_BLOCK_FAKE_ADDR)
992 is_set = 1;
993 else
994 is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
995 v |= unsigned(bool(is_set)) << 6u;
996 }
997 if ((blk = blka[7])!=0)
998 {
999 if (blk == FULL_BLOCK_FAKE_ADDR)
1000 is_set = 1;
1001 else
1002 is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
1003 v |= unsigned(bool(is_set)) << 7u;
1004 }
1005
1006 return (unsigned char)v;
1007}
1008
1009//---------------------------------------------------------------------
1010
1011template<typename BV>
1013 size_type octet_idx,
1014 char octet) const BMNOEXCEPT
1015{
1016 char value = char(get_octet(pos, octet_idx));
1017 return (value > octet) - (value < octet);
1018}
1019
1020//---------------------------------------------------------------------
1021
1022template<typename BV>
1023unsigned
1025{
1026 unsigned v = 0;
1027
1028 block_idx_type nb = (pos >> bm::set_block_shift);
1029 unsigned i0 = unsigned(nb >> bm::set_array_shift); // top block address
1030 unsigned j0 = unsigned(nb & bm::set_array_mask); // address in sub-block
1031
1032 const bm::word_t* blk;
1033 const bm::word_t* blka[4];
1034 unsigned nbit = unsigned(pos & bm::set_block_mask);
1035 unsigned nword = unsigned(nbit >> bm::set_word_shift);
1036 unsigned mask0 = 1u << (nbit & bm::set_word_mask);
1037
1038 blka[0] = get_block(row_idx+0, i0, j0);
1039 blka[1] = get_block(row_idx+1, i0, j0);
1040 blka[2] = get_block(row_idx+2, i0, j0);
1041 blka[3] = get_block(row_idx+3, i0, j0);
1042 unsigned is_set;
1043
1044 if ((blk = blka[0])!=0)
1045 {
1046 if (blk == FULL_BLOCK_FAKE_ADDR)
1047 is_set = 1;
1048 else
1049 is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
1050 v |= unsigned(bool(is_set));
1051 }
1052 if ((blk = blka[1])!=0)
1053 {
1054 if (blk == FULL_BLOCK_FAKE_ADDR)
1055 is_set = 1;
1056 else
1057 is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
1058 v |= unsigned(bool(is_set)) << 1u;
1059 }
1060 if ((blk = blka[2])!=0)
1061 {
1062 if (blk == FULL_BLOCK_FAKE_ADDR)
1063 is_set = 1;
1064 else
1065 is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
1066 v |= unsigned(bool(is_set)) << 2u;
1067 }
1068 if ((blk = blka[3])!=0)
1069 {
1070 if (blk == FULL_BLOCK_FAKE_ADDR)
1071 is_set = 1;
1072 else
1073 is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
1074 v |= unsigned(bool(is_set)) << 3u;
1075 }
1076 return v;
1077}
1078
1079//---------------------------------------------------------------------
1080
1081template<typename BV>
1083 typename bvector_type::optmode opt_mode,
1084 typename bvector_type::statistics* st)
1085{
1086 if (st)
1087 st->reset();
1088
1090 if (!temp_block)
1091 temp_block = tb;
1092
1093 for (unsigned k = 0; k < rsize_; ++k)
1094 {
1095 bvector_type* bv = get_row(k);
1096 if (bv)
1097 {
1098 typename bvector_type::statistics stbv;
1099 stbv.reset();
1100 bv->optimize(temp_block, opt_mode, st ? &stbv : 0);
1101 if (st)
1102 {
1103 st->add(stbv);
1104 }
1105 }
1106 } // for k
1107}
1108
1109//---------------------------------------------------------------------
1110
1111template<typename BV>
1113{
1114 for (unsigned k = 0; k < rsize_; ++k)
1115 {
1116 bvector_type* bv = get_row(k);
1117 if (bv)
1118 {
1119 unsigned i, j;
1120 bm::get_block_coord(nb, i, j);
1121 typename bvector_type::blocks_manager_type& bman =
1122 bv->get_blocks_manager();
1123 bman.optimize_bit_block(i, j);
1124 }
1125 } // for k
1126
1127}
1128
1129//---------------------------------------------------------------------
1130//---------------------------------------------------------------------
1131
1132
1133
1134template<class Val, class BV, unsigned MAX_SIZE>
1136: bmatr_(sv_plains, allocation_policy_type(), bm::id_max, allocator_type()),
1137 size_(0),
1138 effective_plains_(0)
1139{
1140}
1141
1142//---------------------------------------------------------------------
1143
1144template<class Val, class BV, unsigned MAX_SIZE>
1146 bm::null_support null_able,
1148 size_type bv_max_size,
1149 const allocator_type& alloc)
1150: bmatr_(sv_plains, ap, bv_max_size, alloc),
1151 size_(0),
1152 effective_plains_(0)
1153{
1154 if (null_able == bm::use_null)
1155 {
1156 unsigned i = null_plain();
1157 bmatr_.construct_row(i)->init();
1158 }
1159}
1160
1161//---------------------------------------------------------------------
1162
1163template<class Val, class BV, unsigned MAX_SIZE>
1166: bmatr_(bsv.bmatr_),
1167 size_(bsv.size_),
1168 effective_plains_(bsv.effective_plains_)
1169{
1170}
1171
1172//---------------------------------------------------------------------
1173
1174template<class Val, class BV, unsigned MAX_SIZE>
1177{
1178 resize(bsv.size());
1179 effective_plains_ = bsv.effective_plains_;
1180
1181 unsigned ni = this->null_plain();
1182 unsigned plains = bsv.stored_plains();
1183 for (size_type i = 0; i < plains; ++i)
1184 {
1185 bvector_type* bv = bmatr_.get_row(i);
1186 const bvector_type* bv_src = bsv.bmatr_.row(i);
1187
1188 if (i == ni) // NULL plain copy
1189 {
1190 if (bv && !bv_src) // special case (copy from not NULL)
1191 {
1192 if (size_)
1193 bv->set_range(0, size_-1);
1194 continue;
1195 }
1196 }
1197
1198 if (bv)
1199 bmatr_.destruct_row(i);
1200 if (bv_src)
1201 bmatr_.construct_row(i, *bv_src);
1202 } // for i
1203}
1204
1205//---------------------------------------------------------------------
1206
1207template<class Val, class BV, unsigned MAX_SIZE>
1210{
1211 if (this != &bsv)
1212 {
1213 bmatr_.swap(bsv.bmatr_);
1214
1215 bm::xor_swap(size_, bsv.size_);
1216 bm::xor_swap(effective_plains_, bsv.effective_plains_);
1217 }
1218}
1219
1220//---------------------------------------------------------------------
1221
1222template<class Val, class BV, unsigned MAX_SIZE>
1224{
1225 unsigned plains = value_bits();
1226 for (size_type i = 0; i < plains; ++i)
1227 {
1228 bmatr_.destruct_row(i);
1229 }
1230 size_ = 0;
1231 bvector_type* bv_null = get_null_bvect();
1232 if (bv_null)
1233 bv_null->clear();
1234}
1235
1236//---------------------------------------------------------------------
1237
1238template<class Val, class BV, unsigned MAX_SIZE>
1242 bool set_null)
1243{
1244 if (right < left)
1245 {
1246 return clear_range(right, left, set_null);
1247 }
1248 unsigned plains = value_bits();
1249 for (unsigned i = 0; i < plains; ++i)
1250 {
1251 bvector_type* bv = this->bmatr_.get_row(i);
1252 if (bv)
1253 bv->set_range(left, right, false);
1254 } // for i
1255
1256 if (set_null)
1257 {
1258 bvector_type* bv_null = this->get_null_bvect();
1259 if (bv_null)
1260 bv_null->set_range(left, right, false);
1261 }
1262}
1263
1264//---------------------------------------------------------------------
1265
1266template<class Val, class BV, unsigned MAX_SIZE>
1268{
1269 if (sz == size()) // nothing to do
1270 return;
1271 if (!sz) // resize to zero is an equivalent of non-destructive deallocation
1272 {
1273 clear();
1274 return;
1275 }
1276 if (sz < size()) // vector shrink
1277 clear_range(sz, this->size_-1, true); // clear the tails and NULL vect
1278 size_ = sz;
1279}
1280
1281
1282//---------------------------------------------------------------------
1283
1284template<class Val, class BV, unsigned MAX_SIZE>
1286 size_type idx) const BMNOEXCEPT
1287{
1288 const bvector_type* bv_null = get_null_bvector();
1289 return (bv_null) ? (!bv_null->test(idx)) : false;
1290}
1291
1292//---------------------------------------------------------------------
1293
1294template<class Val, class BV, unsigned MAX_SIZE>
1296 bool not_null)
1297{
1298 bvector_type* bv_null = this->get_null_bvect();
1299 if (bv_null)
1300 bv_null->insert(idx, not_null);
1301}
1302
1303//---------------------------------------------------------------------
1304
1305template<class Val, class BV, unsigned MAX_SIZE>
1308{
1309 bvector_type_ptr bv = bmatr_.get_row(i);
1310 if (!bv)
1311 {
1312 bv = bmatr_.construct_row(i);
1313 bv->init();
1314 if (i > effective_plains_ && i < value_bits())
1315 effective_plains_ = i;
1316 }
1317 return bv;
1318}
1319
1320//---------------------------------------------------------------------
1321
1322template<class Val, class BV, unsigned MAX_SIZE>
1324 unsigned element_idx) const BMNOEXCEPT
1325{
1326 BM_ASSERT(element_idx < MAX_SIZE);
1327 bm::id64_t mask = 0;
1328 bm::id64_t mask1 = 1;
1329 const unsigned plains = sizeof(value_type) * 8;
1330 unsigned bidx = 0;
1331 for (unsigned i = element_idx * plains; i < (element_idx+1) * plains; i+=4)
1332 {
1333 mask |= get_plain(i+0) ? (mask1 << (bidx+0)) : 0ull;
1334 mask |= get_plain(i+1) ? (mask1 << (bidx+1)) : 0ull;
1335 mask |= get_plain(i+2) ? (mask1 << (bidx+2)) : 0ull;
1336 mask |= get_plain(i+3) ? (mask1 << (bidx+3)) : 0ull;
1337 bidx += 4;
1338 } // for i
1339 return mask;
1340}
1341
1342//---------------------------------------------------------------------
1343
1344template<class Val, class BV, unsigned MAX_SIZE>
1346 typename bvector_type::optmode opt_mode,
1347 typename bvector_type::statistics* st)
1348{
1349 typename bvector_type::statistics stbv;
1350 bmatr_.optimize(temp_block, opt_mode, &stbv);
1351 if (st)
1352 st->add(stbv);
1353
1354 bvector_type* bv_null = this->get_null_bvect();
1355
1356 unsigned stored_plains = this->stored_plains();
1357 for (unsigned j = 0; j < stored_plains; ++j)
1358 {
1359 bvector_type* bv = this->bmatr_.get_row(j);
1360 if (bv && (bv != bv_null)) // protect the NULL vector from de-allocation
1361 {
1362 // TODO: check if this can be done within optimize loop
1363 if (!bv->any()) // empty vector?
1364 {
1365 this->bmatr_.destruct_row(j);
1366 continue;
1367 }
1368 }
1369 } // for j
1370}
1371
1372//---------------------------------------------------------------------
1373
1374template<class Val, class BV, unsigned MAX_SIZE>
1376 typename bvector_type::statistics* st) const BMNOEXCEPT
1377{
1378 BM_ASSERT(st);
1379
1380 st->reset();
1381
1382 unsigned stored_plains = this->stored_plains();
1383 for (unsigned j = 0; j < stored_plains; ++j)
1384 {
1385 const bvector_type* bv = this->bmatr_.row(j);
1386 if (bv)
1387 {
1388 typename bvector_type::statistics stbv;
1389 bv->calc_stat(&stbv);
1390 st->add(stbv);
1391 }
1392 else
1393 {
1394 st->max_serialize_mem += 8;
1395 }
1396 } // for j
1397
1398 // header accounting
1399 st->max_serialize_mem += 1 + 1 + 1 + 1 + 8 + (8 * this->stored_plains());
1400 st->max_serialize_mem += 1 + 8; // extra header fields for large bit-matrixes
1401}
1402
1403//---------------------------------------------------------------------
1404
1405template<class Val, class BV, unsigned MAX_SIZE>
1407 unsigned plain_idx, size_type idx)
1408{
1409 for (unsigned i = plain_idx; i < sv_value_plains; ++i)
1410 {
1411 bvector_type* bv = this->bmatr_.get_row(i);
1412 if (bv)
1413 bv->clear_bit_no_check(idx);
1414 }
1415}
1416
1417//---------------------------------------------------------------------
1418
1419template<class Val, class BV, unsigned MAX_SIZE>
1421 unsigned plain_idx, size_type idx)
1422{
1423 for (unsigned i = plain_idx; i < sv_value_plains; ++i)
1424 {
1425 bvector_type* bv = this->bmatr_.get_row(i);
1426 if (bv)
1427 bv->insert(idx, false);
1428 }
1429}
1430
1431//---------------------------------------------------------------------
1432
1433template<class Val, class BV, unsigned MAX_SIZE>
1435{
1436 for (unsigned i = 0; i < sv_value_plains; ++i)
1437 {
1438 bvector_type* bv = this->bmatr_.get_row(i);
1439 if (bv)
1440 bv->erase(idx);
1441 }
1442}
1443
1444//---------------------------------------------------------------------
1445
1446template<class Val, class BV, unsigned MAX_SIZE>
1449 bm::null_support null_able) const BMNOEXCEPT
1450{
1451 size_type arg_size = sv.size();
1452 if (this->size_ != arg_size)
1453 {
1454 return false;
1455 }
1456 unsigned plains = this->plains();
1457 for (unsigned j = 0; j < plains; ++j)
1458 {
1459 const bvector_type* bv = this->bmatr_.get_row(j);
1460 const bvector_type* arg_bv = sv.bmatr_.get_row(j);
1461 if (bv == arg_bv) // same NULL
1462 continue;
1463 // check if any not NULL and not empty
1464 if (!bv && arg_bv)
1465 {
1466 if (arg_bv->any())
1467 return false;
1468 continue;
1469 }
1470 if (bv && !arg_bv)
1471 {
1472 if (bv->any())
1473 return false;
1474 continue;
1475 }
1476 // both not NULL
1477 bool eq = bv->equal(*arg_bv);
1478 if (!eq)
1479 return false;
1480 } // for j
1481
1482 if (null_able == bm::use_null)
1483 {
1484 const bvector_type* bv_null = this->get_null_bvector();
1485 const bvector_type* bv_null_arg = sv.get_null_bvector();
1486
1487 // check the NULL vectors
1488 if (bv_null == bv_null_arg)
1489 return true;
1490 if (!bv_null || !bv_null_arg)
1491 return false;
1492 BM_ASSERT(bv_null);
1493 BM_ASSERT(bv_null_arg);
1494 bool eq = bv_null->equal(*bv_null_arg);
1495 if (!eq)
1496 return false;
1497 }
1498 return true;
1499}
1500
1501//---------------------------------------------------------------------
1502
1503template<class Val, class BV, unsigned MAX_SIZE>
1508 bm::null_support splice_null)
1509{
1510 bvector_type* bv_null = get_null_bvect();
1511 const bvector_type* bv_null_arg = bsv.get_null_bvector();
1512 unsigned plains;
1513 if (bv_null)
1514 {
1515 plains = this->stored_plains();
1516 if (bv_null_arg && (splice_null == bm::use_null))
1517 bv_null->copy_range(*bv_null_arg, left, right);
1518 --plains;
1519 }
1520 else
1521 plains = this->plains();
1522
1523 for (unsigned j = 0; j < plains; ++j)
1524 {
1525 const bvector_type* arg_bv = bsv.bmatr_.row(j);
1526 if (arg_bv)
1527 {
1528 bvector_type* bv = this->bmatr_.get_row(j);
1529 if (!bv)
1530 bv = this->get_plain(j);
1531 bv->copy_range(*arg_bv, left, right);
1532 }
1533 } // for j
1534
1535}
1536
1537//---------------------------------------------------------------------
1538
1539} // namespace
1540
1541#endif
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
#define BM_DECLARE_TEMP_BLOCK(x)
Definition bm.h:47
Constants, tables and typedefs.
Definitions(internal)
#define BMNOEXCEPT
Definition bmdef.h:79
#define BMGAP_PTR(ptr)
Definition bmdef.h:179
#define BM_IS_GAP(ptr)
Definition bmdef.h:181
#define BM_ASSERT
Definition bmdef.h:130
#define FULL_BLOCK_FAKE_ADDR
Definition bmdef.h:149
Utilities for bit transposition (internal) (experimental!)
Base class for bit-transposed sparse vector construction.
Definition bmbmatrix.h:254
void insert_clear_value_plains_from(unsigned plain_idx, size_type idx)
Definition bmbmatrix.h:1420
void swap(base_sparse_vector< Val, BV, MAX_SIZE > &bsv) BMNOEXCEPT
Definition bmbmatrix.h:1208
void copy_range_plains(const base_sparse_vector< Val, BV, MAX_SIZE > &bsv, typename base_sparse_vector< Val, BV, MAX_SIZE >::size_type left, typename base_sparse_vector< Val, BV, MAX_SIZE >::size_type right, bm::null_support splice_null)
Perform copy_range() on a set of plains.
Definition bmbmatrix.h:1504
base_sparse_vector(bm::null_support null_able, allocation_policy_type ap, size_type bv_max_size, const allocator_type &alloc)
Definition bmbmatrix.h:1145
const bvector_type * bvector_type_const_ptr
Definition bmbmatrix.h:271
bvector_type_ptr get_plain(unsigned i)
get access to bit-plain, function checks and creates a plain
Definition bmbmatrix.h:1307
bvector_type * bvector_type_ptr
Definition bmbmatrix.h:270
const value_type & const_reference
Definition bmbmatrix.h:272
const bvector_type * get_null_bvector() const BMNOEXCEPT
Get bit-vector of assigned values or NULL (if not constructed that way)
Definition bmbmatrix.h:329
void optimize_block(block_idx_type nb)
optimize block in all matrix plains
Definition bmbmatrix.h:480
void copy_from(const base_sparse_vector< Val, BV, MAX_SIZE > &bsv)
Definition bmbmatrix.h:1175
bvector_type::allocation_policy allocation_policy_type
Definition bmbmatrix.h:274
unsigned effective_plains() const BMNOEXCEPT
Number of effective bit-plains in the value type.
Definition bmbmatrix.h:370
static unsigned value_bits() BMNOEXCEPT
Number of total bit-plains in the value type.
Definition bmbmatrix.h:471
void clear_range(size_type left, size_type right, bool set_null)
Definition bmbmatrix.h:1239
size_type size() const BMNOEXCEPT
Definition bmbmatrix.h:302
bvector_type_const_ptr plain(unsigned i) const BMNOEXCEPT
Definition bmbmatrix.h:377
base_sparse_vector(const base_sparse_vector< Val, BV, MAX_SIZE > &bsv)
Definition bmbmatrix.h:1164
void free_plain(unsigned i)
free memory in bit-plain
Definition bmbmatrix.h:385
bool empty() const BMNOEXCEPT
Definition bmbmatrix.h:312
bm::id64_t get_plains_mask(unsigned element_idx) const BMNOEXCEPT
Definition bmbmatrix.h:1323
bmatrix_type bmatr_
bit-transposed matrix
Definition bmbmatrix.h:495
void resize(size_type new_size)
Definition bmbmatrix.h:1267
bvector_type * get_null_bvect()
Definition bmbmatrix.h:380
allocator_type::allocator_pool_type allocator_pool_type
Definition bmbmatrix.h:276
void clear() BMNOEXCEPT
resize to zero, free memory
Definition bmbmatrix.h:1223
static unsigned plains() BMNOEXCEPT
get total number of bit-plains in the vector
Definition bmbmatrix.h:363
bvector_type_const_ptr get_plain(unsigned i) const BMNOEXCEPT
get read-only access to bit-plain
Definition bmbmatrix.h:358
base_sparse_vector(base_sparse_vector< Val, BV, MAX_SIZE > &&bsv) BMNOEXCEPT
Definition bmbmatrix.h:291
static unsigned null_plain() BMNOEXCEPT
plain index for the "NOT NULL" flags plain
Definition bmbmatrix.h:477
bool is_null(size_type idx) const BMNOEXCEPT
test if specified element is NULL
Definition bmbmatrix.h:1285
size_type size_
array size
Definition bmbmatrix.h:496
const bmatrix_type & get_bmatrix() const BMNOEXCEPT
Definition bmbmatrix.h:401
BV::size_type size_type
Definition bmbmatrix.h:269
bvector_type::enumerator bvector_enumerator_type
Definition bmbmatrix.h:275
static unsigned stored_plains() BMNOEXCEPT
Number of stored bit-plains (value plains + extra.
Definition bmbmatrix.h:366
bvector_type_ptr plain(unsigned i) BMNOEXCEPT
get access to bit-plain as is (can return NULL)
Definition bmbmatrix.h:376
bm::basic_bmatrix< BV > bmatrix_type
Definition bmbmatrix.h:277
BV::allocator_type allocator_type
Definition bmbmatrix.h:273
void optimize(bm::word_t *temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, typename bvector_type::statistics *stat=0)
run memory optimization for all bit-vector rows
Definition bmbmatrix.h:1345
void insert_null(size_type idx, bool not_null)
Definition bmbmatrix.h:1295
void calc_stat(typename bvector_type::statistics *st) const BMNOEXCEPT
Calculates memory statistics.
Definition bmbmatrix.h:1375
void clear_value_plains_from(unsigned plain_idx, size_type idx)
Definition bmbmatrix.h:1406
bool is_nullable() const BMNOEXCEPT
check if container supports NULL(unassigned) values
Definition bmbmatrix.h:322
void erase_column(size_type idx)
Definition bmbmatrix.h:1434
bool equal(const base_sparse_vector< Val, BV, MAX_SIZE > &sv, bm::null_support null_able=bm::use_null) const BMNOEXCEPT
check if another sparse vector has the same content and size
Definition bmbmatrix.h:1447
bvector_type::block_idx_type block_idx_type
Definition bmbmatrix.h:468
Basic dense bit-matrix class.
Definition bmbmatrix.h:54
void insert_octet(size_type pos, size_type octet_idx, unsigned char octet)
Definition bmbmatrix.h:864
bvector_type::block_idx_type block_idx_type
Definition bmbmatrix.h:63
void swap(basic_bmatrix< BV > &bbm) BMNOEXCEPT
Definition bmbmatrix.h:685
~basic_bmatrix() BMNOEXCEPT
Definition bmbmatrix.h:523
bvector_type * bvector_type_ptr
Definition bmbmatrix.h:57
bvector_type_ptr * bv_rows_
Definition bmbmatrix.h:242
allocator_type alloc_
Definition bmbmatrix.h:238
void set_allocator_pool(allocator_pool_type *pool_ptr) BMNOEXCEPT
Definition bmbmatrix.h:101
bvector_type_ptr construct_row(size_type row)
Definition bmbmatrix.h:715
unsigned get_half_octet(size_type pos, size_type row_idx) const BMNOEXCEPT
Definition bmbmatrix.h:1024
BV::allocator_type allocator_type
Definition bmbmatrix.h:59
bvector_type::allocation_policy allocation_policy_type
Definition bmbmatrix.h:60
bvector_type_ptr construct_row(size_type row, const bvector_type &bv)
Definition bmbmatrix.h:730
allocator_type::allocator_pool_type allocator_pool_type
Definition bmbmatrix.h:61
void destruct_row(size_type row)
Definition bmbmatrix.h:749
const bvector_type * bvector_type_const_ptr
Definition bmbmatrix.h:58
bvector_type * construct_bvector(const bvector_type *bv) const
Definition bmbmatrix.h:765
const bm::word_t * get_block(size_type p, unsigned i, unsigned j) const BMNOEXCEPT
Get low level internal access to.
Definition bmbmatrix.h:804
bool test_4rows(unsigned i) const BMNOEXCEPT
Test if 4 rows from i are not NULL.
Definition bmbmatrix.h:589
basic_bmatrix< BV > & operator=(const basic_bmatrix< BV > &bbm)
Definition bmbmatrix.h:79
int compare_octet(size_type pos, size_type octet_idx, char octet) const BMNOEXCEPT
Definition bmbmatrix.h:1012
size_type rsize_
Definition bmbmatrix.h:243
allocator_pool_type * pool_
Definition bmbmatrix.h:240
void copy_from(const basic_bmatrix< BV > &bbm)
Definition bmbmatrix.h:610
static void throw_bad_alloc()
Definition bmbmatrix.h:233
void optimize(bm::word_t *temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, typename bvector_type::statistics *stat=0)
run memory optimization for all bit-vector rows
Definition bmbmatrix.h:1082
basic_bmatrix(basic_bmatrix< BV > &&bbm) BMNOEXCEPT
Definition bmbmatrix.h:545
unsigned char octet_type
Definition bmbmatrix.h:64
size_type bv_size_
Definition bmbmatrix.h:237
const bvector_type * row(size_type i) const BMNOEXCEPT
Definition bmbmatrix.h:560
void allocate_rows(size_type rsize)
Definition bmbmatrix.h:643
allocation_policy_type ap_
Definition bmbmatrix.h:239
void optimize_block(block_idx_type nb)
Definition bmbmatrix.h:1112
size_type rows() const BMNOEXCEPT
Definition bmbmatrix.h:132
void destruct_bvector(bvector_type *bv) const
Definition bmbmatrix.h:790
bvector_type * get_row(size_type i) BMNOEXCEPT
Definition bmbmatrix.h:580
void set_octet(size_type pos, size_type octet_idx, unsigned char octet)
Definition bmbmatrix.h:821
basic_bmatrix(size_type rsize, allocation_policy_type ap=allocation_policy_type(), size_type bv_max_size=bm::id_max, const allocator_type &alloc=allocator_type())
Definition bmbmatrix.h:506
void free_rows() BMNOEXCEPT
Definition bmbmatrix.h:664
unsigned char get_octet(size_type pos, size_type octet_idx) const BMNOEXCEPT
Definition bmbmatrix.h:913
bvector_type::size_type size_type
Definition bmbmatrix.h:62
bvector_type_const_ptr get_row(size_type i) const BMNOEXCEPT
Definition bmbmatrix.h:570
Constant iterator designed to enumerate "ON" bits.
Definition bm.h:600
Bitvector Bit-vector container with runtime compression of bits.
Definition bm.h:108
optmode
Optimization mode Every next level means additional checks (better compression vs time)
Definition bm.h:130
@ opt_compress
compress blocks when possible (GAP/prefix sum)
Definition bm.h:134
bm::id_t size_type
Definition bm.h:117
blocks_manager< Alloc > blocks_manager_type
Definition bm.h:112
blocks_manager_type::block_idx_type block_idx_type
Definition bm.h:113
null_support
NULL-able value support.
Definition bmconst.h:214
@ use_null
support "non-assigned" or "NULL" logic
Definition bmconst.h:215
unsigned gap_test_unr(const T *BMRESTRICT buf, const unsigned pos) BMNOEXCEPT
Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling.
Definition bmfunc.h:1298
Definition bm.h:77
const unsigned set_array_mask
Definition bmconst.h:96
void xor_swap(W &x, W &y) BMNOEXCEPT
XOR swap two scalar variables.
Definition bmfunc.h:909
const unsigned id_max
Definition bmconst.h:108
unsigned int word_t
Definition bmconst.h:38
const unsigned set_block_mask
Definition bmconst.h:56
const unsigned set_word_shift
Definition bmconst.h:71
unsigned long long int id64_t
Definition bmconst.h:34
const unsigned set_array_shift
Definition bmconst.h:95
void get_block_coord(BI_TYPE nb, unsigned &i, unsigned &j) BMNOEXCEPT
Recalc linear bvector block index into 2D matrix coordinates.
Definition bmfunc.h:147
const unsigned set_block_shift
Definition bmconst.h:55
const unsigned set_word_mask
Definition bmconst.h:72
bm::bvector bvector_type
void reset() BMNOEXCEPT
Reset statisctics.
Definition bmfunc.h:96
void add(const bv_statistics &st) BMNOEXCEPT
Sum data from another sttructure.
Definition bmfunc.h:105
memory allocation policy
Definition bm.h:820
Statistical information about bitset's memory allocation details.
Definition bm.h:122
static TBVector * construct_bvector()
Definition xsample01.cpp:99