1 #ifndef BMBMATRIX__H__INCLUDED__ 2 #define BMBMATRIX__H__INCLUDED__ 122 const bvector_type*
row(size_type i)
const;
125 bvector_type_const_ptr
get_row(size_type i)
const;
128 bvector_type*
get_row(size_type i);
137 bvector_type_ptr
construct_row(size_type row,
const bvector_type& bv);
154 void set_octet(size_type pos, size_type octet_idx,
unsigned char octet);
163 void insert_octet(size_type pos, size_type octet_idx,
unsigned char octet);
171 unsigned char get_octet(size_type pos, size_type octet_idx)
const;
186 size_type octet_idx,
char octet)
const;
230 allocation_policy_type
ap_;
243 template<
typename Val,
typename BV,
unsigned MAX_SIZE>
249 sv_plains = (
sizeof(Val) * 8 * MAX_SIZE + 1),
250 sv_value_plains = (
sizeof(Val) * 8 * MAX_SIZE)
255 max_vector_size = MAX_SIZE
274 allocation_policy_type ap,
275 size_type bv_max_size,
276 const allocator_type& alloc);
284 bmatr_.swap(bsv.bmatr_);
286 effective_plains_ = bsv.effective_plains_;
293 size_type
size()
const {
return size_; }
295 void resize(size_type new_size);
297 void clear_range(size_type left, size_type right,
bool set_null);
303 bool empty()
const {
return size() == 0; }
313 bool is_nullable()
const {
return bmatr_.get_row(this->null_plain()) != 0; }
320 {
return bmatr_.get_row(this->null_plain()); }
327 bool is_null(size_type idx)
const;
341 bvector_type_ptr get_plain(
unsigned i);
347 bvector_type_const_ptr
353 static unsigned plains() {
return value_bits(); }
365 bvector_type_ptr
plain(
unsigned i) {
return bmatr_.get_row(i); }
366 const bvector_type_ptr
plain(
unsigned i)
const {
return bmatr_.get_row(i); }
384 bm::id64_t get_plains_mask(
unsigned element_idx)
const;
432 void clear_value_plains_from(
unsigned plain_idx, size_type idx);
439 void insert_clear_value_plains_from(
unsigned plain_idx, size_type idx);
445 void erase_column(size_type idx);
450 void insert_null(size_type idx,
bool not_null);
472 template<
typename BV>
474 allocation_policy_type ap,
475 size_type bv_max_size,
476 const allocator_type& alloc)
484 allocate_rows(rsize);
489 template<
typename BV>
497 template<
typename BV>
499 : bv_size_(bbm.bv_size_),
511 template<
typename BV>
513 : bv_size_(bbm.bv_size_),
525 template<
typename BV>
535 template<
typename BV>
545 template<
typename BV>
555 template<
typename BV>
559 #if defined(BM64_SSE4) 560 __m128i w0 = _mm_loadu_si128((__m128i*)(bv_rows_ + j));
561 __m128i w1 = _mm_loadu_si128((__m128i*)(bv_rows_ + j + 2));
562 w0 = _mm_or_si128(w0, w1);
563 return !_mm_testz_si128(w0, w0);
564 #elif defined(BM64_AVX2) || defined(BM64_AVX512) 565 __m256i w0 = _mm256_loadu_si256((__m256i*)(bv_rows_ + j));
566 return !_mm256_testz_si256(w0, w0);
568 bool b = bv_rows_[j + 0] || bv_rows_[j + 1] || bv_rows_[j + 2] || bv_rows_[j + 3];
575 template<
typename BV>
586 size_type rsize = bbm.
rsize_;
589 bv_rows_ = (bvector_type_ptr*)alloc_.alloc_ptr(rsize);
595 for (size_type i = 0; i < rsize_; ++i)
597 const bvector_type_ptr bv = bbm.
bv_rows_[i];
608 template<
typename BV>
615 bv_rows_ = (bvector_type_ptr*)alloc_.alloc_ptr(
unsigned(rsize));
621 for (size_type i = 0; i < rsize; ++i)
629 template<
typename BV>
632 for (size_type i = 0; i < rsize_; ++i)
634 bvector_type_ptr bv = bv_rows_[i];
637 destruct_bvector(bv);
643 alloc_.free_ptr(bv_rows_,
unsigned(rsize_));
650 template<
typename BV>
658 allocator_type alloc_tmp = alloc_;
660 bbm.alloc_ = alloc_tmp;
662 allocation_policy_type ap_tmp = ap_;
666 allocator_pool_type* pool_tmp = pool_;
668 bbm.pool_ = pool_tmp;
672 bvector_type_ptr* rtmp = bv_rows_;
673 bv_rows_ = bbm.bv_rows_;
679 template<
typename BV>
684 bvector_type_ptr bv = bv_rows_[row];
694 template<
typename BV>
699 bvector_type_ptr bv = bv_rows_[row];
714 template<
typename BV>
718 bvector_type_ptr bv = bv_rows_[row];
721 destruct_bvector(bv);
729 template<
typename BV>
733 bvector_type* rbv = 0;
734 #ifdef BM_NO_STL // C compatibility mode 735 void* mem = ::malloc(
sizeof(bvector_type));
738 BM_THROW(
false, BM_ERR_BADALLOC);
755 template<
typename BV>
758 #ifdef BM_NO_STL // C compatibility mode 768 template<
typename BV>
772 bvector_type_const_ptr bv = this->row(p);
776 return bman.get_block_ptr(i, j);
784 template<
typename BV>
791 size_type oct = octet;
792 size_type row = octet_idx * 8;
793 size_type row_end = row + 8;
794 for (; row < row_end; ++row)
796 bvector_type* bv = this->get_row(row);
801 bv = this->construct_row(row);
817 for (++row; row < row_end; ++row)
819 bvector_type* bv = this->get_row(row);
827 template<
typename BV>
834 size_type oct = octet;
835 size_type row = octet_idx * 8;
836 size_type row_end = row + 8;
837 for (; row < row_end; ++row)
839 bvector_type* bv = this->get_row(row);
844 bv = this->construct_row(row);
864 for (++row; row < row_end; ++row)
866 bvector_type* bv = this->get_row(row);
875 template<
typename BV>
891 unsigned row_idx = unsigned(octet_idx * 8);
893 blka[0] = get_block(row_idx+0, i0, j0);
894 blka[1] = get_block(row_idx+1, i0, j0);
895 blka[2] = get_block(row_idx+2, i0, j0);
896 blka[3] = get_block(row_idx+3, i0, j0);
897 blka[4] = get_block(row_idx+4, i0, j0);
898 blka[5] = get_block(row_idx+5, i0, j0);
899 blka[6] = get_block(row_idx+6, i0, j0);
900 blka[7] = get_block(row_idx+7, i0, j0);
903 if ((blk = blka[0])!=0)
909 v |= (unsigned)
bool(is_set);
911 if ((blk = blka[1])!=0)
917 v |= unsigned(
bool(is_set)) << 1u;
919 if ((blk = blka[2])!=0)
925 v |= unsigned(
bool(is_set)) << 2u;
927 if ((blk = blka[3])!=0)
933 v |= unsigned(
bool(is_set)) << 3u;
937 if ((blk = blka[4])!=0)
943 v |= unsigned(
bool(is_set)) << 4u;
945 if ((blk = blka[5])!=0)
951 v |= unsigned(
bool(is_set)) << 5u;
953 if ((blk = blka[6])!=0)
959 v |= unsigned(
bool(is_set)) << 6u;
961 if ((blk = blka[7])!=0)
967 v |= unsigned(
bool(is_set)) << 7u;
970 return (
unsigned char)v;
975 template<
typename BV>
980 char value = char(get_octet(pos, octet_idx));
981 return (value > octet) - (value < octet);
986 template<
typename BV>
1002 blka[0] = get_block(row_idx+0, i0, j0);
1003 blka[1] = get_block(row_idx+1, i0, j0);
1004 blka[2] = get_block(row_idx+2, i0, j0);
1005 blka[3] = get_block(row_idx+3, i0, j0);
1008 if ((blk = blka[0])!=0)
1014 v |= unsigned(
bool(is_set));
1016 if ((blk = blka[1])!=0)
1022 v |= unsigned(
bool(is_set)) << 1u;
1024 if ((blk = blka[2])!=0)
1030 v |= unsigned(
bool(is_set)) << 2u;
1032 if ((blk = blka[3])!=0)
1038 v |= unsigned(
bool(is_set)) << 3u;
1045 template<
typename BV>
1057 for (
unsigned k = 0; k < rsize_; ++k)
1059 bvector_type* bv = get_row(k);
1064 bv->
optimize(temp_block, opt_mode, st ? &stbv : 0);
1080 template<
class Val,
class BV,
unsigned MAX_SIZE>
1082 : bmatr_(sv_plains, allocation_policy_type(),
bm::
id_max, allocator_type()),
1084 effective_plains_(0)
1090 template<
class Val,
class BV,
unsigned MAX_SIZE>
1093 allocation_policy_type ap,
1094 size_type bv_max_size,
1095 const allocator_type& alloc)
1096 : bmatr_(sv_plains, ap, bv_max_size, alloc),
1098 effective_plains_(0)
1102 unsigned i = null_plain();
1103 bmatr_.construct_row(i)->init();
1109 template<
class Val,
class BV,
unsigned MAX_SIZE>
1112 : bmatr_(bsv.bmatr_),
1114 effective_plains_(bsv.effective_plains_)
1120 template<
class Val,
class BV,
unsigned MAX_SIZE>
1127 unsigned ni = this->null_plain();
1129 for (size_type i = 0; i < plains; ++i)
1131 bvector_type* bv = bmatr_.get_row(i);
1132 const bvector_type* bv_src = bsv.
bmatr_.
row(i);
1139 bv->set_range(0, size_-1);
1145 bmatr_.destruct_row(i);
1147 bmatr_.construct_row(i, *bv_src);
1153 template<
class Val,
class BV,
unsigned MAX_SIZE>
1159 bmatr_.swap(bsv.bmatr_);
1162 bm::xor_swap(effective_plains_, bsv.effective_plains_);
1168 template<
class Val,
class BV,
unsigned MAX_SIZE>
1171 unsigned plains = value_bits();
1172 for (size_type i = 0; i < plains; ++i)
1174 bmatr_.destruct_row(i);
1177 bvector_type* bv_null = get_null_bvect();
1184 template<
class Val,
class BV,
unsigned MAX_SIZE>
1192 return clear_range(right, left, set_null);
1194 unsigned plains = value_bits();
1195 for (
unsigned i = 0; i < plains; ++i)
1197 bvector_type* bv = this->bmatr_.get_row(i);
1199 bv->set_range(left, right,
false);
1204 bvector_type* bv_null = this->get_null_bvect();
1206 bv_null->set_range(left, right,
false);
1212 template<
class Val,
class BV,
unsigned MAX_SIZE>
1223 clear_range(sz, this->size_-1,
true);
1230 template<
class Val,
class BV,
unsigned MAX_SIZE>
1233 const bvector_type* bv_null = get_null_bvector();
1234 return (bv_null) ? (!bv_null->test(idx)) :
false;
1239 template<
class Val,
class BV,
unsigned MAX_SIZE>
1243 bvector_type* bv_null = this->get_null_bvect();
1245 bv_null->insert(idx, not_null);
1250 template<
class Val,
class BV,
unsigned MAX_SIZE>
1254 bvector_type_ptr bv = bmatr_.get_row(i);
1257 bv = bmatr_.construct_row(i);
1259 if (i > effective_plains_ && i < value_bits())
1260 effective_plains_ = i;
1267 template<
class Val,
class BV,
unsigned MAX_SIZE>
1269 unsigned element_idx)
const 1274 const unsigned plains =
sizeof(
value_type) * 8;
1276 for (
unsigned i = element_idx * plains; i < (element_idx+1) * plains; i+=4)
1278 mask |= get_plain(i+0) ? (mask1 << (bidx+0)) : 0ull;
1279 mask |= get_plain(i+1) ? (mask1 << (bidx+1)) : 0ull;
1280 mask |= get_plain(i+2) ? (mask1 << (bidx+2)) : 0ull;
1281 mask |= get_plain(i+3) ? (mask1 << (bidx+3)) : 0ull;
1289 template<
class Val,
class BV,
unsigned MAX_SIZE>
1295 bmatr_.optimize(temp_block, opt_mode, &stbv);
1299 bvector_type* bv_null = this->get_null_bvect();
1301 unsigned stored_plains = this->stored_plains();
1302 for (
unsigned j = 0; j < stored_plains; ++j)
1304 bvector_type* bv = this->bmatr_.get_row(j);
1305 if (bv && (bv != bv_null))
1310 this->bmatr_.destruct_row(j);
1319 template<
class Val,
class BV,
unsigned MAX_SIZE>
1327 unsigned stored_plains = this->stored_plains();
1328 for (
unsigned j = 0; j < stored_plains; ++j)
1330 const bvector_type* bv = this->bmatr_.row(j);
1334 bv->calc_stat(&stbv);
1350 template<
class Val,
class BV,
unsigned MAX_SIZE>
1352 unsigned plain_idx, size_type idx)
1354 for (
unsigned i = plain_idx; i < sv_value_plains; ++i)
1356 bvector_type* bv = this->bmatr_.get_row(i);
1358 bv->clear_bit_no_check(idx);
1364 template<
class Val,
class BV,
unsigned MAX_SIZE>
1366 unsigned plain_idx, size_type idx)
1368 for (
unsigned i = plain_idx; i < sv_value_plains; ++i)
1370 bvector_type* bv = this->bmatr_.get_row(i);
1372 bv->insert(idx,
false);
1378 template<
class Val,
class BV,
unsigned MAX_SIZE>
1381 for (
unsigned i = 0; i < sv_value_plains; ++i)
1383 bvector_type* bv = this->bmatr_.get_row(i);
1391 template<
class Val,
class BV,
unsigned MAX_SIZE>
1396 size_type arg_size = sv.
size();
1397 if (this->size_ != arg_size)
1401 unsigned plains = this->plains();
1402 for (
unsigned j = 0; j < plains; ++j)
1404 const bvector_type* bv = this->bmatr_.get_row(j);
1422 int cmp = bv->compare(*arg_bv);
1429 const bvector_type* bv_null = this->get_null_bvector();
1433 if (bv_null == bv_null_arg)
1435 if (!bv_null || !bv_null_arg)
1439 int cmp = bv_null->compare(*bv_null);
bvector_type * get_null_bvect()
const blocks_manager_type & get_blocks_manager() const
get access to memory manager (internal) Use only if you are BitMagic library
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
bvector_type::size_type size_type
bvector_type * bvector_type_ptr
const bm::word_t * get_block(size_type p, unsigned i, unsigned j) const
Get low level internal access to.
void clear_bit_no_check(size_type n)
Clears bit n without precondiion checks.
const bvector_type_ptr plain(unsigned i) const
bvector_type::block_idx_type block_idx_type
bool is_nullable() const
check if container supports NULL(unassigned) values
static TBVector * construct_bvector()
void swap(basic_bmatrix< BV > &bbm) BMNOEXEPT
static unsigned plains()
get total number of bit-plains in the vector
Base class for bit-transposed sparse vector construction.
const unsigned set_word_shift
bvector_type::allocation_policy allocation_policy_type
allocator_type::allocator_pool_type allocator_pool_type
bool test_4rows(unsigned i) const
Test if 4 rows from i are not NULL.
unsigned char get_octet(size_type pos, size_type octet_idx) const
Constants, tables and typedefs.
const unsigned set_array_shift
unsigned long long int id64_t
unsigned get_half_octet(size_type pos, size_type row_idx) const
static unsigned value_bits()
Number of total bit-plains in the value type.
void optimize(bm::word_t *temp_block=0, optmode opt_mode=opt_compress, statistics *stat=0)
Optimize memory bitvector's memory allocation.
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
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())
bvector_type::enumerator bvector_enumerator_type
void free_plain(unsigned i)
free memory in bit-plain
void free_rows() BMNOEXEPT
size_t max_serialize_mem
estimated maximum memory for serialization
const bvector_type * row(size_type i) const
BV::allocator_type allocator_type
unsigned effective_plains_
void xor_swap(W &x, W &y)
XOR swap two scalar variables.
compress blocks when possible (GAP/prefix sum)
bm::basic_bmatrix< BV > bmatrix_type
const bvector_type * get_null_bvector() const
Get bit-vector of assigned values or NULL (if not constructed that way)
const bvector_type * bvector_type_const_ptr
#define BM_DECLARE_TEMP_BLOCK(x)
Statistical information about bitset's memory allocation details.
~basic_bmatrix() BMNOEXEPT
basic_bmatrix< BV > & operator=(const basic_bmatrix< BV > &bbm)
bvector_type_ptr plain(unsigned i)
get access to bit-plain as is (can return NULL)
null_support
NULL-able value support.
blocks_manager_type::block_idx_type block_idx_type
unsigned effective_plains() const
Number of effective bit-plains in the value type.
allocator_pool_type * pool_
int compare_octet(size_type pos, size_type octet_idx, char octet) const
static void throw_bad_alloc()
support "non-assigned" or "NULL" logic
Basic dense bit-matrix class.
BV::allocator_type allocator_type
void allocate_rows(size_type rsize)
unsigned gap_test_unr(const T *buf, const unsigned pos)
Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling.
const unsigned set_array_mask
const value_type & const_reference
void copy_from(const basic_bmatrix< BV > &bbm)
void init()
Explicit post-construction initialization.
void insert_octet(size_type pos, size_type octet_idx, unsigned char octet)
blocks_manager< Alloc > blocks_manager_type
bvector_type * construct_bvector(const bvector_type *bv) const
const bvector_type * bvector_type_const_ptr
void reset()
Reset statisctics.
allocation_policy_type ap_
bvector_type_const_ptr get_plain(unsigned i) const
get read-only access to bit-plain
bvector_type * bvector_type_ptr
bvector_type_ptr construct_row(size_type row)
void set_allocator_pool(allocator_pool_type *pool_ptr)
Utilities for bit transposition (internal) (experimental!)
const unsigned set_block_mask
bvector_type_const_ptr get_row(size_type i) const
Constant iterator designed to enumerate "ON" bits.
optmode
Optimization mode Every next level means additional checks (better compression vs time) ...
const unsigned set_word_mask
static unsigned null_plain()
plain index for the "NOT NULL" flag1s plain
base_sparse_vector(base_sparse_vector< Val, BV, MAX_SIZE > &&bsv) BMNOEXEPT
void destruct_bvector(bvector_type *bv) const
void set_octet(size_type pos, size_type octet_idx, unsigned char octet)
bmatrix_type bmatr_
bit-transposed matrix
const unsigned set_block_shift
void add(const bv_statistics &st)
Sum data from another sttructure.
bvector_type_ptr * bv_rows_
static unsigned stored_plains()
Number of stored bit-plains (value plains + extra.
allocator_type::allocator_pool_type allocator_pool_type
void destruct_row(size_type row)
bvector_type::allocation_policy allocation_policy_type
void set_bit_no_check(size_type n)
Set bit without checking preconditions (size, etc)
size_type size_
array size
#define FULL_BLOCK_FAKE_ADDR
bool insert(size_type n, bool value)
Insert bit into specified position All the vector content after insert position is shifted right...