1#ifndef BMBMATRIX__H__INCLUDED__
2#define BMBMATRIX__H__INCLUDED__
313 template<
typename Val,
typename BVect,
unsigned MAX_SIZE>
334template<
typename Val,
typename BV,
unsigned MAX_SIZE>
413 {
return std::is_signed<value_type>::value; }
689#pragma warning( push )
690#pragma warning( disable : 4146 )
698: bv_size_(bv_max_size),
721: bv_size_(bbm.bv_size_),
736: bv_size_(bbm.bv_size_),
784 null_idx_ = null_idx;
823 size_type r_to = (!erase_null && null_idx_) ? null_idx_ : rsize_;
835 for (
size_type i = row_from; i < rsize_; ++i)
837 bv->insert(idx,
false);
846 for (
size_type i = row_from; i < rsize_; ++i)
848 bv->clear_bit_no_check(idx);
857 if (rsize <= rsize_prev)
867 ::memset(&bv_rows_[0], 0, rsize *
sizeof(bv_rows_[0]));
870 for (
size_type i = 0; i < rsize_prev; ++i)
871 bv_rows_[i] = bv_rows_prev[i];
872 alloc_.free_ptr(bv_rows_prev,
unsigned(rsize_prev));
875 bv_rows_[rsize-1] = bv_rows_[null_idx_];
876 bv_rows_[null_idx_] = 0;
888 size_type osize = (7 + rows_not_null()) / 8;
902 destruct_bvector(bv);
907 alloc_.free_ptr(bv_rows_,
unsigned(rsize_));
916 if (pool_ != pool_ptr)
920 bv->set_allocator_pool(pool_ptr);
933 auto i = rows_not_null();
934 for (--i; i > 0; --i)
982 bbm.alloc_ = alloc_tmp;
990 bbm.pool_ = pool_tmp;
996 bv_rows_ = bbm.bv_rows_;
1002template<
typename BV>
1007 allocate_rows(row + 8);
1017template<
typename BV>
1022 allocate_rows(row + 8);
1035template<
typename BV>
1041 destruct_bvector(bv);
1048template<
typename BV>
1056 destruct_bvector(bv);
1066template<
typename BV>
1075 BM_THROW(
false, BM_ERR_BADALLOC);
1081 rbv =
new(mem)
bvector_type(ap_.strat, ap_.glevel_len, bv_size_, alloc_);
1089 rbv =
new bvector_type(ap_.strat, ap_.glevel_len, bv_size_, alloc_);
1094 rbv->set_allocator_pool(pool_);
1100template<
typename BV>
1113template<
typename BV>
1119 return bv->get_blocks_manager().get_block_ptr(i, j);
1125template<
typename BV>
1127 unsigned slice_from,
unsigned slice_until,
1130 for (
unsigned p = slice_from; p < slice_until; ++p)
1132 bv->clear_bit_no_check(idx);
1138template<
typename BV>
1141 unsigned char octet)
1143 if (7u + octet_idx * 8u > rsize_)
1144 allocate_rows(rsize_ + 16);
1148 for (; row < row_end; ++row)
1150 bvector_type* bv = (row < rsize_) ? this->get_row(row) : 0;
1154 bv = this->construct_row(row);
1155 bv->set_bit_no_check(pos);
1160 bv->clear_bit_no_check(pos);
1168 if (row_end > rsize_)
1170 for (++row; row < row_end; ++row)
1172 bv->clear_bit_no_check(pos);
1177template<
typename BV>
1180 unsigned char octet)
1187 for (; row < row_end; ++row)
1189 bvector_type* bv = (row < rsize_) ? this->get_row(row) : 0;
1194 bv = this->construct_row(row);
1195 bv->set_bit_no_check(pos);
1199 bv->insert(pos,
true);
1205 bv->insert(pos,
false);
1213 if (row_end > rsize_)
1215 for (++row; row < row_end; ++row)
1217 bv->insert(pos,
false);
1223template<
typename BV>
1239 unsigned row_idx = unsigned(octet_idx * 8);
1240 if (row_idx + 7 >= rsize_ ||
1241 (null_idx_ && (row_idx + 7 > null_idx_)))
1242 return (
unsigned char)v;
1244 blka[0] = get_block(row_idx+0, i0, j0);
1245 blka[1] = get_block(row_idx+1, i0, j0);
1246 blka[2] = get_block(row_idx+2, i0, j0);
1247 blka[3] = get_block(row_idx+3, i0, j0);
1248 blka[4] = get_block(row_idx+4, i0, j0);
1249 blka[5] = get_block(row_idx+5, i0, j0);
1250 blka[6] = get_block(row_idx+6, i0, j0);
1251 blka[7] = get_block(row_idx+7, i0, j0);
1254 if ((blk = blka[0])!=0)
1260 v |= (unsigned)
bool(is_set);
1262 if ((blk = blka[1])!=0)
1268 v |= unsigned(
bool(is_set)) << 1u;
1270 if ((blk = blka[2])!=0)
1276 v |= unsigned(
bool(is_set)) << 2u;
1278 if ((blk = blka[3])!=0)
1284 v |= unsigned(
bool(is_set)) << 3u;
1288 if ((blk = blka[4])!=0)
1294 v |= unsigned(
bool(is_set)) << 4u;
1296 if ((blk = blka[5])!=0)
1302 v |= unsigned(
bool(is_set)) << 5u;
1304 if ((blk = blka[6])!=0)
1310 v |= unsigned(
bool(is_set)) << 6u;
1312 if ((blk = blka[7])!=0)
1318 v |= unsigned(
bool(is_set)) << 7u;
1321 return (
unsigned char)v;
1326template<
typename BV>
1331 char value = char(get_octet(pos, octet_idx));
1332 return (value > octet) - (value < octet);
1346 = uintptr_t(p0) | uintptr_t(p1) | uintptr_t(p2) | uintptr_t(p3);
1364template<
typename BV>
1378 blka[0] = get_block(row_idx+0, i0, j0);
1379 blka[1] = get_block(row_idx+1, i0, j0);
1380 blka[2] = get_block(row_idx+2, i0, j0);
1381 blka[3] = get_block(row_idx+3, i0, j0);
1391 if (!
test_4gaps(blka[0], blka[1], blka[2], blka[3]))
1393 if (
test_4bits(blka[0], blka[1], blka[2], blka[3]))
1395 v = unsigned(
bool((blka[0][nword] & mask0))) |
1396 unsigned(
bool((blka[1][nword] & mask0)) << 1u) |
1397 unsigned(
bool((blka[2][nword] & mask0)) << 2u) |
1398 unsigned(
bool((blka[3][nword] & mask0)) << 3u);
1406 if ((blk = blka[i])!=0)
1412 v |= unsigned(
bool(is_set)) << i;
1414 if ((blk = blka[++i])!=0)
1420 v |= unsigned(
bool(is_set)) << i;
1428template<
typename BV>
1440 for (
unsigned k = 0; k < rsize_; ++k)
1446 bv->optimize(temp_block, opt_mode, st ? &stbv : 0);
1455template<
typename BV>
1458 for (
unsigned k = 0; k < rsize_; ++k)
1465template<
typename BV>
1473 bv->calc_stat(&stbv);
1477 st.max_serialize_mem += 8;
1482template<
typename BV>
1484 typename BV::optmode opt_mode)
1486 for (
unsigned k = 0; k < rsize_; ++k)
1493 bv->get_blocks_manager();
1494 bman.optimize_bit_block(i, j, opt_mode);
1505template<
class Val,
class BV,
unsigned MAX_SIZE>
1512template<
class Val,
class BV,
unsigned MAX_SIZE>
1518: bmatr_(sv_slices, ap, bv_max_size, alloc)
1522 size_type null_idx = (MAX_SIZE *
sizeof(Val) * 8);
1531template<
class Val,
class BV,
unsigned MAX_SIZE>
1534: bmatr_(bsv.bmatr_),
1535 slice_mask_(bsv.slice_mask_),
1537 effective_slices_(bsv.effective_slices_)
1542template<
class Val,
class BV,
unsigned MAX_SIZE>
1546 resize(bsv.
size(),
true);
1551 bmatr_.null_idx_ = arg_null_idx;
1554 bmatr_.allocate_rows(slices);
1560 if (i && (i == arg_null_idx))
1565 bv->set_range(0, size_-1);
1571 bmatr_.destruct_row(i);
1576 bmatr_.construct_row(i, *bv_src);
1584template<
class Val,
class BV,
unsigned MAX_SIZE>
1590 if (rows < arg_rows)
1593 bmatr_.allocate_rows(rows);
1594 BM_ASSERT(this->bmatr_.rows() == arg_rows);
1600 bv_null_arg = bmatr.
get_row(null_idx);
1605 bv_null->merge(*bv_null_arg);
1607 if (rows > arg_rows)
1609 for (
unsigned j = 0; j < rows; ++j)
1612 if (arg_bv && arg_bv != bv_null_arg)
1623template<
class Val,
class BV,
unsigned MAX_SIZE>
1629 bmatr_.swap(bsv.bmatr_);
1632 bm::xor_swap(effective_slices_, bsv.effective_slices_);
1638template<
class Val,
class BV,
unsigned MAX_SIZE>
1641 auto slices = bmatr_.rows();
1646 bmatr_.clear_row(i, free_mem);
1647 slice_mask_ = 0; size_ = 0;
1649 bv_null->clear(
true);
1654template<
class Val,
class BV,
unsigned MAX_SIZE>
1661 return clear_range(right, left, set_null);
1662 auto planes = bmatr_.rows();
1664 for (
unsigned i = 0; i < planes; ++i)
1668 bv->clear_range_no_check(left, right);
1670 if (set_null && bv_null)
1671 bv_null->clear_range_no_check(left, right);
1676template<
class Val,
class BV,
unsigned MAX_SIZE>
1682 this->clear_range(0, left-1, (slice_null ==
bm::use_null));
1685 this->clear_range(right + 1, sz, (slice_null ==
bm::use_null));
1690template<
class Val,
class BV,
unsigned MAX_SIZE>
1701 clear_range(sz, this->size_, set_null);
1708template<
class Val,
class BV,
unsigned MAX_SIZE>
1713 return (bv_null) ? (!bv_null->test(idx)) :
false;
1718template<
class Val,
class BV,
unsigned MAX_SIZE>
1723 bv_null->insert(idx, not_null);
1728template<
class Val,
class BV,
unsigned MAX_SIZE>
1740 if (i > effective_slices_)
1741 effective_slices_ = i;
1748template<
class Val,
class BV,
unsigned MAX_SIZE>
1754 const unsigned planes =
sizeof(
value_type) * 8;
1756 unsigned slice_size = (element_idx+1) * planes;
1757 if (slice_size > this->bmatr_.rows())
1758 slice_size = (
unsigned) this->bmatr_.rows();
1759 for (
unsigned i = element_idx * planes; i < slice_size; ++i, ++bidx)
1760 mask |= get_slice(i) ? (mask1 << bidx) : 0ull;
1766template<
class Val,
class BV,
unsigned MAX_SIZE>
1772 bmatr_.optimize(temp_block, opt_mode, &stbv);
1777 unsigned slices = (unsigned)this->bmatr_.rows();
1778 for (
unsigned j = 0; j < slices; ++j)
1781 if (bv && (bv != bv_null))
1786 this->bmatr_.destruct_row(j);
1796template<
class Val,
class BV,
unsigned MAX_SIZE>
1802 size_type slices = this->get_bmatrix().rows();
1803 bmatr_.calc_stat(*st, slices);
1806 st->max_serialize_mem += 1 + 1 + 1 + 1 + 8 + (8 * slices);
1807 st->max_serialize_mem += 1 + 8;
1812template<
class Val,
class BV,
unsigned MAX_SIZE>
1816 bmatr_.clear_column(idx, plane_idx);
1821template<
class Val,
class BV,
unsigned MAX_SIZE>
1825 bmatr_.insert_column(idx, plane_idx);
1830template<
class Val,
class BV,
unsigned MAX_SIZE>
1834 bmatr_.erase_column(idx, erase_null);
1839template<
class Val,
class BV,
unsigned MAX_SIZE>
1844 if (
size_type arg_size = sv.size(); this->size_ != arg_size)
1847 unsigned slices = (unsigned) this->bmatr_.rows();
1848 unsigned arg_slices = (unsigned) sv.bmatr_.rows();
1849 unsigned max_slices(slices);
1850 if (max_slices < arg_slices)
1851 max_slices = arg_slices;
1853 const bvector_type* bv_null = this->get_null_bvector();
1854 const bvector_type* bv_null_arg = sv.get_null_bvector();
1856 for (
unsigned j = 0; j < max_slices; ++j)
1861 bv = (j < slices) ? this->bmatr_.get_row(j) : 0;
1862 arg_bv = (j < arg_slices) ? sv.bmatr_.get_row(j) : 0;
1865 if (arg_bv == bv_null_arg)
1884 bool eq = bv->equal(*arg_bv);
1892 if (bv_null == bv_null_arg)
1894 if (!bv_null || !bv_null_arg)
1899 bool eq = bv_null->equal(*bv_null_arg);
1908template<
class Val,
class BV,
unsigned MAX_SIZE>
1922 spli = this->bmatr_.rows();
1924 bv_null->copy_range(*bv_null_arg, left, right);
1928 spli = this->bmatr_.rows();
1934 if (arg_bv == bv_null_arg)
1936 bvector_type* bv = this->get_create_slice(
unsigned(j));
1937 bv->copy_range(*arg_bv, left, right);
1945template<
class Val,
class BV,
unsigned MAX_SIZE>
1949 if constexpr (is_signed())
1966template<
class Val,
class BV,
unsigned MAX_SIZE>
1970 if constexpr (is_signed())
1983#pragma warning( pop )
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
#define BM_DECLARE_TEMP_BLOCK(x)
Constants, lookup tables and typedefs.
#define FULL_BLOCK_FAKE_ADDR
Utilities for bit transposition (internal) (experimental!)
Base class for bit-transposed(bit-sliced) sparse vector construction.
void freeze_matr()
Turn on RO mode.
bvector_type_const_ptr get_slice(unsigned i) const BMNOEXCEPT
get read-only access to bit-plane
void swap(base_sparse_vector< Val, BV, MAX_SIZE > &bsv) BMNOEXCEPT
void resize(size_type new_size, bool set_null)
bm::null_support get_null_support() const BMNOEXCEPT
check if container supports NULL (unassigned) values
unsigned effective_slices() const BMNOEXCEPT
Number of effective bit-planes in the value type.
unsigned_value_type slice_mask_
slice presence bit-mask
const bvector_type * bvector_type_const_ptr
void merge_matr(bmatrix_type &bmatr)
Merge plane bvectors from an outside base matrix Note: outside base matrix gets destroyed.
static unsigned slices() BMNOEXCEPT
get total number of bit-planes in the vector
static value_type u2s(unsigned_value_type v) BMNOEXCEPT
Convert unsigned value type to signed representation.
bvector_type * bvector_type_ptr
const value_type & const_reference
bmatrix_type & get_bmatrix() BMNOEXCEPT
access to internal bit-matrix
bvector_type_ptr slice(unsigned i) BMNOEXCEPT
get access to bit-plane as is (can return NULL)
void copy_from(const base_sparse_vector< Val, BV, MAX_SIZE > &bsv)
static unsigned_value_type s2u(value_type v) BMNOEXCEPT
Convert signed value type to unsigned representation.
bvector_type::allocation_policy allocation_policy_type
void set_allocator_pool(allocator_pool_type *pool_ptr) BMNOEXCEPT
Set allocation pool.
void clear_range(size_type left, size_type right, bool set_null)
bvector_type_ptr get_create_slice(unsigned i)
get access to bit-plain, function checks and creates a plane
size_type size() const BMNOEXCEPT
base_sparse_vector(const base_sparse_vector< Val, BV, MAX_SIZE > &bsv)
bool empty() const BMNOEXCEPT
const bmatrix_type & get_bmatrix() const BMNOEXCEPT
void free_slice(unsigned i)
free memory in bit-plane
void optimize_block(block_idx_type nb, typename BV::optmode opt_mode)
plane index for the "NOT NULL" flags plane
unsigned effective_slices_
number of bit slices actually allocated
bmatrix_type bmatr_
bit-transposed matrix
void erase_column(size_type idx, bool erase_null)
allocator_type::allocator_pool_type allocator_pool_type
base_sparse_vector(bm::null_support null_able, allocation_policy_type ap=allocation_policy_type(), size_type bv_max_size=bm::id_max, const allocator_type &alloc=allocator_type())
void copy_range_slices(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 slice_null)
Perform copy_range() on a set of planes.
base_sparse_vector(base_sparse_vector< Val, BV, MAX_SIZE > &&bsv) BMNOEXCEPT
bm::id64_t get_slice_mask(unsigned element_idx) const BMNOEXCEPT
static unsigned stored_slices() BMNOEXCEPT
Number of stored bit-planes (value planes + extra.
static constexpr unsigned value_bits() BMNOEXCEPT
Number of total bit-planes in the value type.
bool is_null(size_type idx) const BMNOEXCEPT
test if specified element is NULL
const bvector_type * get_null_bvector() const BMNOEXCEPT
Get bit-vector of assigned values or NULL (if not constructed that way)
size_type size_
array size
void bit_and_rows(const bvector_type &bv)
Set AND (intersect) operation on all existing bit-slices.
void keep_range_no_check(size_type left, size_type right, bm::null_support slice_null)
std::make_unsigned< value_type >::type unsigned_value_type
void mark_null_idx(unsigned null_idx) BMNOEXCEPT
Set NULL plain index.
bvector_type_const_ptr slice(unsigned i) const BMNOEXCEPT
allocator_pool_type * get_allocator_pool() const BMNOEXCEPT
Get allocation pool.
bvector_type::enumerator bvector_enumerator_type
void bit_sub_rows(const bvector_type &bv, bool use_null)
Set SUB (MINUS) operation on all existing bit-slices.
void clear_all(bool free_mem=true) BMNOEXCEPT
resize to zero, free memory
bm::basic_bmatrix< BV > bmatrix_type
bvector_type * get_null_bvect() BMNOEXCEPT
BV::allocator_type allocator_type
static constexpr bool is_signed() BMNOEXCEPT
returns true if value type is signed integral type
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 clear_value_planes_from(unsigned plane_idx, size_type idx)
void calc_stat(typename bvector_type::statistics *st) const BMNOEXCEPT
Calculates memory statistics.
bool is_nullable() const BMNOEXCEPT
check if container supports NULL(unassigned) values
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
void insert_clear_value_planes_from(unsigned plane_idx, size_type idx)
bvector_type::block_idx_type block_idx_type
Basic dense bit-matrix class.
void insert_octet(size_type pos, size_type octet_idx, unsigned char octet)
void insert_column(size_type idx, size_type row_from)
bvector_type::block_idx_type block_idx_type
void swap(basic_bmatrix< BV > &bbm) BMNOEXCEPT
~basic_bmatrix() BMNOEXCEPT
basic_bmatrix< BV > & operator=(const basic_bmatrix< BV > &bbm)
bvector_type * bvector_type_ptr
bvector_type_ptr * bv_rows_
void set_allocator_pool(allocator_pool_type *pool_ptr) BMNOEXCEPT
void set_null_idx(size_type null_idx) BMNOEXCEPT
set index of the NULL vector
bvector_type_ptr construct_row(size_type row)
unsigned get_half_octet(size_type pos, size_type row_idx) const BMNOEXCEPT
BV::allocator_type allocator_type
bvector_type::allocation_policy allocation_policy_type
size_type null_idx_
Index of the NULL row.
allocator_type::allocator_pool_type allocator_pool_type
size_type get_null_idx() const BMNOEXCEPT
return index of the NULL vector
void destruct_row(size_type row)
const bvector_type * bvector_type_const_ptr
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.
void bit_and_rows(const bvector_type &bv)
Set AND (intersect) operation on all existing rows.
void calc_stat(typename bvector_type::statistics &st, size_type rsize) const BMNOEXCEPT
allocator_pool_type * get_allocator_pool() const BMNOEXCEPT
int compare_octet(size_type pos, size_type octet_idx, char octet) const BMNOEXCEPT
size_type rows_not_null() 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
void clear_slices_range(unsigned slice_from, unsigned slize_until, size_type idx)
Clear bit-planes bit.
void clear_column(size_type idx, size_type row_from)
void clear_row(size_type row, bool free_mem)
const bvector_type * row(size_type i) const BMNOEXCEPT
void allocate_rows(size_type rsize)
allocate matrix rows of bit-vectors (new rows are NULLs)
void optimize_block(block_idx_type nb, typename BV::optmode opt_mode)
allocation_policy_type ap_
size_type rows() const BMNOEXCEPT
void destruct_bvector(bvector_type *bv) const
size_type calc_effective_rows_not_null() const BMNOEXCEPT
void set_octet(size_type pos, size_type octet_idx, unsigned char octet)
void erase_column(size_type idx, bool erase_null)
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 bit_sub_rows(const bvector_type &bv, bool use_null)
Set SUB (MINUS) operation on all existing rows.
size_type octet_size() const BMNOEXCEPT
void free_rows() BMNOEXCEPT
Free all rows.
unsigned char get_octet(size_type pos, size_type octet_idx) const BMNOEXCEPT
bvector_type::size_type size_type
bvector_type_const_ptr get_row(size_type i) const BMNOEXCEPT
Constant iterator designed to enumerate "ON" bits.
Bitvector Bit-vector container with runtime compression of bits.
optmode
Optimization mode Every next level means additional checks (better compression vs time)
@ opt_compress
compress blocks when possible (GAP/prefix sum)
blocks_manager< Alloc > blocks_manager_type
bvector_size_type size_type
void init()
Explicit post-construction initialization. Must be caled to make sure safe use of *_no_check() method...
blocks_manager_type::block_idx_type block_idx_type
null_support
NULL-able value support.
@ use_null
support "non-assigned" or "NULL" logic
@ no_null
do not support NULL values
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
bool test_4bits(const bm::word_t *p0, const bm::word_t *p1, const bm::word_t *p2, const bm::word_t *p3) BMNOEXCEPT
Test 4 pointers are not NULL and not marked as FULLBLOCK.
const unsigned set_block_mask
BMFORCEINLINE void get_block_coord(BI_TYPE nb, unsigned &i, unsigned &j) BMNOEXCEPT
Recalc linear bvector block index into 2D matrix coordinates.
const unsigned set_word_shift
BMFORCEINLINE void xor_swap(W &x, W &y) BMNOEXCEPT
XOR swap two variables.
unsigned long long int id64_t
const unsigned set_array_shift
const unsigned set_block_shift
const unsigned set_word_mask
bool test_4gaps(const bm::word_t *p0, const bm::word_t *p1, const bm::word_t *p2, const bm::word_t *p3) BMNOEXCEPT
Test 4 pointers are all marked as GAPs.
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()