1#ifndef BMBMATRIX__H__INCLUDED__
2#define BMBMATRIX__H__INCLUDED__
102 {
pool_ = pool_ptr; }
215 typename bvector_type::statistics* stat = 0);
252template<
typename Val,
typename BV,
unsigned MAX_SIZE>
510: bv_size_(bv_max_size),
532: bv_size_(bbm.bv_size_),
546: bv_size_(bbm.bv_size_),
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);
601 bool b = bv_rows_[j + 0] || bv_rows_[j + 1] ||
602 bv_rows_[j + 2] || bv_rows_[j + 3];
671 destruct_bvector(bv);
677 alloc_.free_ptr(bv_rows_,
unsigned(rsize_));
694 bbm.alloc_ = alloc_tmp;
702 bbm.pool_ = pool_tmp;
707 bv_rows_ = bbm.bv_rows_;
755 destruct_bvector(bv);
772 BM_THROW(
false, BM_ERR_BADALLOC);
811 bv->get_blocks_manager();
812 return bman.get_block_ptr(i, j);
830 for (; row < row_end; ++row)
837 bv = this->construct_row(row);
840 bv->set_bit_no_check(pos);
845 bv->clear_bit_no_check(pos);
853 for (++row; row < row_end; ++row)
857 bv->clear_bit_no_check(pos);
873 for (; row < row_end; ++row)
880 bv = this->construct_row(row);
882 bv->set_bit_no_check(pos);
886 bv->insert(pos,
true);
892 bv->insert(pos,
false);
900 for (++row; row < row_end; ++row)
904 bv->insert(pos,
false);
927 unsigned row_idx = unsigned(octet_idx * 8);
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);
939 if ((blk = blka[0])!=0)
945 v |= (unsigned)
bool(is_set);
947 if ((blk = blka[1])!=0)
953 v |= unsigned(
bool(is_set)) << 1u;
955 if ((blk = blka[2])!=0)
961 v |= unsigned(
bool(is_set)) << 2u;
963 if ((blk = blka[3])!=0)
969 v |= unsigned(
bool(is_set)) << 3u;
973 if ((blk = blka[4])!=0)
979 v |= unsigned(
bool(is_set)) << 4u;
981 if ((blk = blka[5])!=0)
987 v |= unsigned(
bool(is_set)) << 5u;
989 if ((blk = blka[6])!=0)
995 v |= unsigned(
bool(is_set)) << 6u;
997 if ((blk = blka[7])!=0)
1003 v |= unsigned(
bool(is_set)) << 7u;
1006 return (
unsigned char)v;
1011template<
typename BV>
1016 char value = char(get_octet(pos, octet_idx));
1017 return (value > octet) - (value < octet);
1022template<
typename BV>
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);
1044 if ((blk = blka[0])!=0)
1050 v |= unsigned(
bool(is_set));
1052 if ((blk = blka[1])!=0)
1058 v |= unsigned(
bool(is_set)) << 1u;
1060 if ((blk = blka[2])!=0)
1066 v |= unsigned(
bool(is_set)) << 2u;
1068 if ((blk = blka[3])!=0)
1074 v |= unsigned(
bool(is_set)) << 3u;
1081template<
typename BV>
1093 for (
unsigned k = 0; k < rsize_; ++k)
1100 bv->optimize(temp_block, opt_mode, st ? &stbv : 0);
1111template<
typename BV>
1114 for (
unsigned k = 0; k < rsize_; ++k)
1122 bv->get_blocks_manager();
1123 bman.optimize_bit_block(i, j);
1134template<
class Val,
class BV,
unsigned MAX_SIZE>
1138 effective_plains_(0)
1144template<
class Val,
class BV,
unsigned MAX_SIZE>
1150: bmatr_(sv_plains, ap, bv_max_size, alloc),
1152 effective_plains_(0)
1163template<
class Val,
class BV,
unsigned MAX_SIZE>
1166: bmatr_(bsv.bmatr_),
1168 effective_plains_(bsv.effective_plains_)
1174template<
class Val,
class BV,
unsigned MAX_SIZE>
1181 unsigned ni = this->null_plain();
1193 bv->set_range(0, size_-1);
1199 bmatr_.destruct_row(i);
1201 bmatr_.construct_row(i, *bv_src);
1207template<
class Val,
class BV,
unsigned MAX_SIZE>
1213 bmatr_.swap(bsv.bmatr_);
1216 bm::xor_swap(effective_plains_, bsv.effective_plains_);
1222template<
class Val,
class BV,
unsigned MAX_SIZE>
1225 unsigned plains = value_bits();
1228 bmatr_.destruct_row(i);
1238template<
class Val,
class BV,
unsigned MAX_SIZE>
1246 return clear_range(right, left, set_null);
1248 unsigned plains = value_bits();
1249 for (
unsigned i = 0; i < plains; ++i)
1253 bv->set_range(left, right,
false);
1260 bv_null->set_range(left, right,
false);
1266template<
class Val,
class BV,
unsigned MAX_SIZE>
1277 clear_range(sz, this->size_-1,
true);
1284template<
class Val,
class BV,
unsigned MAX_SIZE>
1289 return (bv_null) ? (!bv_null->test(idx)) :
false;
1294template<
class Val,
class BV,
unsigned MAX_SIZE>
1300 bv_null->insert(idx, not_null);
1305template<
class Val,
class BV,
unsigned MAX_SIZE>
1312 bv = bmatr_.construct_row(i);
1314 if (i > effective_plains_ && i < value_bits())
1315 effective_plains_ = i;
1322template<
class Val,
class BV,
unsigned MAX_SIZE>
1329 const unsigned plains =
sizeof(
value_type) * 8;
1331 for (
unsigned i = element_idx * plains; i < (element_idx+1) * plains; i+=4)
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;
1344template<
class Val,
class BV,
unsigned MAX_SIZE>
1350 bmatr_.optimize(temp_block, opt_mode, &stbv);
1356 unsigned stored_plains = this->stored_plains();
1357 for (
unsigned j = 0; j < stored_plains; ++j)
1360 if (bv && (bv != bv_null))
1365 this->bmatr_.destruct_row(j);
1374template<
class Val,
class BV,
unsigned MAX_SIZE>
1382 unsigned stored_plains = this->stored_plains();
1383 for (
unsigned j = 0; j < stored_plains; ++j)
1389 bv->calc_stat(&stbv);
1394 st->max_serialize_mem += 8;
1399 st->max_serialize_mem += 1 + 1 + 1 + 1 + 8 + (8 * this->stored_plains());
1400 st->max_serialize_mem += 1 + 8;
1405template<
class Val,
class BV,
unsigned MAX_SIZE>
1409 for (
unsigned i = plain_idx; i < sv_value_plains; ++i)
1413 bv->clear_bit_no_check(idx);
1419template<
class Val,
class BV,
unsigned MAX_SIZE>
1423 for (
unsigned i = plain_idx; i < sv_value_plains; ++i)
1427 bv->insert(idx,
false);
1433template<
class Val,
class BV,
unsigned MAX_SIZE>
1436 for (
unsigned i = 0; i < sv_value_plains; ++i)
1446template<
class Val,
class BV,
unsigned MAX_SIZE>
1452 if (this->size_ != arg_size)
1456 unsigned plains = this->plains();
1457 for (
unsigned j = 0; j < plains; ++j)
1477 bool eq = bv->equal(*arg_bv);
1484 const bvector_type* bv_null = this->get_null_bvector();
1485 const bvector_type* bv_null_arg = sv.get_null_bvector();
1488 if (bv_null == bv_null_arg)
1490 if (!bv_null || !bv_null_arg)
1494 bool eq = bv_null->equal(*bv_null_arg);
1503template<
class Val,
class BV,
unsigned MAX_SIZE>
1515 plains = this->stored_plains();
1517 bv_null->copy_range(*bv_null_arg, left, right);
1521 plains = this->plains();
1523 for (
unsigned j = 0; j < plains; ++j)
1530 bv = this->get_plain(j);
1531 bv->copy_range(*arg_bv, left, right);
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
#define BM_DECLARE_TEMP_BLOCK(x)
Constants, tables and typedefs.
#define FULL_BLOCK_FAKE_ADDR
Utilities for bit transposition (internal) (experimental!)
Base class for bit-transposed sparse vector construction.
allocator_type::allocator_pool_type allocator_pool_type
void insert_clear_value_plains_from(unsigned plain_idx, size_type idx)
void swap(base_sparse_vector< Val, BV, MAX_SIZE > &bsv) BMNOEXCEPT
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.
base_sparse_vector(bm::null_support null_able, allocation_policy_type ap, size_type bv_max_size, const allocator_type &alloc)
bvector_type_ptr get_plain(unsigned i)
get access to bit-plain, function checks and creates a plain
unsigned effective_plains_
const bvector_type * get_null_bvector() const BMNOEXCEPT
Get bit-vector of assigned values or NULL (if not constructed that way)
void optimize_block(block_idx_type nb)
optimize block in all matrix plains
void copy_from(const base_sparse_vector< Val, BV, MAX_SIZE > &bsv)
BV::allocator_type allocator_type
unsigned effective_plains() const BMNOEXCEPT
Number of effective bit-plains in the value type.
static unsigned value_bits() BMNOEXCEPT
Number of total bit-plains in the value type.
bm::basic_bmatrix< BV > bmatrix_type
void clear_range(size_type left, size_type right, bool set_null)
size_type size() const BMNOEXCEPT
bvector_type_const_ptr plain(unsigned i) const BMNOEXCEPT
base_sparse_vector(const base_sparse_vector< Val, BV, MAX_SIZE > &bsv)
void free_plain(unsigned i)
free memory in bit-plain
bool empty() const BMNOEXCEPT
const bvector_type * bvector_type_const_ptr
bm::id64_t get_plains_mask(unsigned element_idx) const BMNOEXCEPT
bmatrix_type bmatr_
bit-transposed matrix
void resize(size_type new_size)
bvector_type * get_null_bvect()
void clear() BMNOEXCEPT
resize to zero, free memory
static unsigned plains() BMNOEXCEPT
get total number of bit-plains in the vector
bvector_type * bvector_type_ptr
bvector_type_const_ptr get_plain(unsigned i) const BMNOEXCEPT
get read-only access to bit-plain
bvector_type::enumerator bvector_enumerator_type
base_sparse_vector(base_sparse_vector< Val, BV, MAX_SIZE > &&bsv) BMNOEXCEPT
static unsigned null_plain() BMNOEXCEPT
plain index for the "NOT NULL" flags plain
const value_type & const_reference
bool is_null(size_type idx) const BMNOEXCEPT
test if specified element is NULL
size_type size_
array size
const bmatrix_type & get_bmatrix() const BMNOEXCEPT
bvector_type::block_idx_type block_idx_type
bvector_type::allocation_policy allocation_policy_type
static unsigned stored_plains() BMNOEXCEPT
Number of stored bit-plains (value plains + extra.
bvector_type_ptr plain(unsigned i) BMNOEXCEPT
get access to bit-plain as is (can return NULL)
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
void insert_null(size_type idx, bool not_null)
void calc_stat(typename bvector_type::statistics *st) const BMNOEXCEPT
Calculates memory statistics.
void clear_value_plains_from(unsigned plain_idx, size_type idx)
bool is_nullable() const BMNOEXCEPT
check if container supports NULL(unassigned) values
void erase_column(size_type idx)
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
Basic dense bit-matrix class.
bvector_type::size_type size_type
void insert_octet(size_type pos, size_type octet_idx, unsigned char octet)
const bvector_type * bvector_type_const_ptr
void swap(basic_bmatrix< BV > &bbm) BMNOEXCEPT
~basic_bmatrix() BMNOEXCEPT
bvector_type_ptr * bv_rows_
BV::allocator_type allocator_type
void set_allocator_pool(allocator_pool_type *pool_ptr) BMNOEXCEPT
bvector_type_ptr construct_row(size_type row)
unsigned get_half_octet(size_type pos, size_type row_idx) const BMNOEXCEPT
bvector_type_ptr construct_row(size_type row, const bvector_type &bv)
void destruct_row(size_type row)
bvector_type * construct_bvector(const bvector_type *bv) const
const bm::word_t * get_block(size_type p, unsigned i, unsigned j) const BMNOEXCEPT
Get low level internal access to.
bool test_4rows(unsigned i) const BMNOEXCEPT
Test if 4 rows from i are not NULL.
basic_bmatrix< BV > & operator=(const basic_bmatrix< BV > &bbm)
int compare_octet(size_type pos, size_type octet_idx, char octet) const BMNOEXCEPT
allocator_pool_type * pool_
void copy_from(const basic_bmatrix< BV > &bbm)
static void throw_bad_alloc()
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(basic_bmatrix< BV > &&bbm) BMNOEXCEPT
const bvector_type * row(size_type i) const BMNOEXCEPT
void allocate_rows(size_type rsize)
bvector_type * bvector_type_ptr
allocation_policy_type ap_
void optimize_block(block_idx_type nb)
size_type rows() const BMNOEXCEPT
void destruct_bvector(bvector_type *bv) const
bvector_type * get_row(size_type i) BMNOEXCEPT
allocator_type::allocator_pool_type allocator_pool_type
void set_octet(size_type pos, size_type octet_idx, unsigned char octet)
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())
void free_rows() BMNOEXCEPT
unsigned char get_octet(size_type pos, size_type octet_idx) const BMNOEXCEPT
bvector_type::allocation_policy allocation_policy_type
bvector_type_const_ptr get_row(size_type i) const BMNOEXCEPT
bvector_type::block_idx_type block_idx_type
Constant iterator designed to enumerate "ON" bits.
@ opt_compress
compress blocks when possible (GAP/prefix sum)
blocks_manager_type::block_idx_type block_idx_type
blocks_manager< Alloc > blocks_manager_type
null_support
NULL-able value support.
@ use_null
support "non-assigned" or "NULL" logic
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.
const unsigned set_array_mask
void xor_swap(W &x, W &y) BMNOEXCEPT
XOR swap two scalar variables.
const unsigned set_block_mask
const unsigned set_word_shift
unsigned long long int id64_t
const unsigned set_array_shift
void get_block_coord(BI_TYPE nb, unsigned &i, unsigned &j) BMNOEXCEPT
Recalc linear bvector block index into 2D matrix coordinates.
const unsigned set_block_shift
const unsigned set_word_mask
void reset() BMNOEXCEPT
Reset statisctics.
void add(const bv_statistics &st) BMNOEXCEPT
Sum data from another sttructure.
Statistical information about bitset's memory allocation details.
static TBVector * construct_bvector()