bmbmatrix.h
Go to the documentation of this file.
#ifndef BMBMATRIX__H__INCLUDED__
#define BMBMATRIX__H__INCLUDED__
/*
Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
For more information please visit: http://bitmagic.io
*/
/*! \file bmbmatrix.h
\brief basic bit-matrix class and utilities
*/
#include <stddef.h>
#include <type_traits>
#include "bmconst.h"
#ifndef BM_NO_STL
#include <stdexcept>
#endif
#include "bm.h"
#include "bmtrans.h"
#include "bmdef.h"
namespace bm
{
/**
Basic dense bit-matrix class.
Container of row-major bit-vectors, forming a bit-matrix.
This class uses dense form of row storage.
It is applicable as a build block for other sparse containers and
succinct data structures, implementing high level abstractions.
@ingroup bmagic
@internal
*/
template<typename BV>
class basic_bmatrix
{
public:
typedef BV bvector_type;
typedef bvector_type* bvector_type_ptr;
typedef const bvector_type* bvector_type_const_ptr;
typedef typename BV::allocator_type allocator_type;
typedef typename bvector_type::allocation_policy allocation_policy_type;
typedef typename allocator_type::allocator_pool_type allocator_pool_type;
typedef typename bvector_type::size_type size_type;
typedef typename bvector_type::block_idx_type block_idx_type;
typedef unsigned char octet_type;
public:
// ------------------------------------------------------------
/*! @name Construction, assignment */
///@{
basic_bmatrix(size_type rsize,
bool is_dynamic = true,
allocation_policy_type ap = allocation_policy_type(),
size_type bv_max_size = bm::id_max,
const allocator_type& alloc = allocator_type());
~basic_bmatrix() BMNOEXCEPT;
/*! copy-ctor */
basic_bmatrix(const basic_bmatrix<BV>& bbm);
basic_bmatrix<BV>& operator=(const basic_bmatrix<BV>& bbm)
{
copy_from(bbm);
return *this;
}
#ifndef BM_NO_CXX11
/*! move-ctor */
basic_bmatrix(basic_bmatrix<BV>&& bbm) BMNOEXCEPT;
/*! move assignmment operator */
basic_bmatrix<BV>& operator = (basic_bmatrix<BV>&& bbm) BMNOEXCEPT
{
if (this != &bbm)
{
free_rows();
swap(bbm);
}
return *this;
}
#endif
void set_allocator_pool(allocator_pool_type* pool_ptr) BMNOEXCEPT;
allocator_pool_type* get_allocator_pool() const BMNOEXCEPT
{ return pool_; }
///@}
// ------------------------------------------------------------
/*! @name content manipulation */
///@{
/*! Swap content */
void swap(basic_bmatrix<BV>& bbm) BMNOEXCEPT;
/*! Copy content */
void copy_from(const basic_bmatrix<BV>& bbm);
/*! Freeze content into read-only mode drop editing overhead */
void freeze();
///@}
// ------------------------------------------------------------
/*! @name row access */
///@{
/*! Get row bit-vector. Can return NULL */
const bvector_type* row(size_type i) const BMNOEXCEPT;
/*! Get row bit-vector. Can return NULL */
bvector_type_const_ptr get_row(size_type i) const BMNOEXCEPT;
/*! Get row bit-vector. Can return NULL */
bvector_type* get_row(size_type i) BMNOEXCEPT;
/*! get number of value rows */
size_type rows() const BMNOEXCEPT { return rsize_; }
/*! get number of value rows without (not) NULLs bvector */
size_type rows_not_null() const BMNOEXCEPT { return rsize_ - bool(null_idx_);}
/*! get number of assigned avlue rows without \ NULLs bvector */
size_type calc_effective_rows_not_null() const BMNOEXCEPT;
/*! Make sure row is constructed, return bit-vector */
bvector_type_ptr construct_row(size_type row);
/*! Make sure row is copy-constructed, return bit-vector */
bvector_type_ptr construct_row(size_type row, const bvector_type& bv);
/*! destruct/deallocate row */
void destruct_row(size_type row);
/*! clear row bit-vector */
void clear_row(size_type row, bool free_mem);
/** return index of the NULL vector */
size_type get_null_idx() const BMNOEXCEPT { return null_idx_; }
/** set index of the NULL vector */
void set_null_idx(size_type null_idx) BMNOEXCEPT;
/** allocate matrix rows of bit-vectors (new rows are NULLs) */
void allocate_rows(size_type rsize);
/** Free all rows */
void free_rows() BMNOEXCEPT;
///@}
// ------------------------------------------------------------
/*! @name octet access and transposition */
///@{
/*!
Bit-transpose an octet and assign it to a bit-matrix
@param pos - column position in the matrix
@param octet_idx - octet based row position (1 octet - 8 rows)
@param octet - value to assign
*/
void set_octet(size_type pos, size_type octet_idx, unsigned char octet);
/*!
Bit-transpose and insert an octet and assign it to a bit-matrix
@param pos - column position in the matrix
@param octet_idx - octet based row position (1 octet - 8 rows)
@param octet - value to assign
*/
void insert_octet(size_type pos, size_type octet_idx, unsigned char octet);
/*!
return octet from the matrix
@param pos - column position in the matrix
@param octet_idx - octet based row position (1 octet - 8 rows)
*/
unsigned char get_octet(size_type pos, size_type octet_idx) const BMNOEXCEPT;
/*!
Compare vector[pos] with octet
It uses regulat comparison of chars to comply with the (signed)
char sort order.
@param pos - column position in the matrix
@param octet_idx - octet based row position (1 octet - 8 rows)
@param octet - octet value to compare
@return 0 - equal, -1 - less(vect[pos] < octet), 1 - greater
*/
int compare_octet(size_type pos,
size_type octet_idx, char octet) const BMNOEXCEPT;
/*!
Return number of octet currently allocated rows in the matrix
*/
size_type octet_size() const BMNOEXCEPT;
///@}
// ------------------------------------------------------------
/*! @name Utility functions */
///@{
/// Get low level internal access to
const bm::word_t* get_block(size_type p,
unsigned i, unsigned j) const BMNOEXCEPT;
/**
Clear bit-planes bit
@param slice_from - clear from [from, until)
@param slice_until - clear until (open interval!)
@param idx - bit index
*/
void clear_slices_range(unsigned slice_from, unsigned slize_until,
size_type idx);
unsigned get_half_octet(size_type pos, size_type row_idx) const BMNOEXCEPT;
/*!
\brief run memory optimization for all bit-vector rows
\param temp_block - pre-allocated memory block to avoid re-allocs
\param opt_mode - requested compression depth
\param stat - memory allocation statistics after optimization
*/
void optimize(
bm::word_t* temp_block = 0,
typename bvector_type::optmode opt_mode = bvector_type::opt_compress,
typename bvector_type::statistics* stat = 0);
/*! Optimize block in all planes
@internal
*/
void optimize_block(block_idx_type nb, typename BV::optmode opt_mode);
/*! Compute memory statistics
@param st [out] - statistics object
@param rsize - row size (for cases when operation is limited not to touch the NULL bit-vector)
*/
void calc_stat(typename bvector_type::statistics& st,
size_type rsize) const BMNOEXCEPT;
/*! Erase column/element
@param idx - index (of column) / element of bit-vectors to erase
@param erase_null - erase all including NULL vector (true)
*/
void erase_column(size_type idx, bool erase_null);
/*! Insert value 0 into a range of rows
@param idx - index (of column) / element of bit-vectors to erase
@param row_from - row to start from
*/
void insert_column(size_type idx, size_type row_from);
/*! Clear value (set 0) into a range of rows
@param idx - index (of column) / element of bit-vectors
@param row_from - row to start from
*/
void clear_column(size_type idx, size_type row_from);
/*! Swap columns (bits in all rows)
@param idx1 - column index 1
@param idx2 - column index 2
*/
void swap_columns(size_type idx1, size_type idx2);
/**
Set SUB (MINUS) operation on all existing rows
@param bv - argument vector row[i] -= bv
@param use_null - if true clear the NULL vector as well
*/
void bit_sub_rows(const bvector_type& bv, bool use_null);
/**
Set AND (intersect) operation on all existing rows
@param bv - argument vector row[i] &= bv
*/
void bit_and_rows(const bvector_type& bv);
/// Return if matrix is dynamic resizable
bool is_dynamic() const BMNOEXCEPT { return is_dynamic_; }
/// Debugging function to check if two matrixes have the same rows created
/// @return true - if the same
///
bool is_same_structure(const basic_bmatrix<BV>& bbm) const BMNOEXCEPT;
///@}
protected:
bvector_type* construct_bvector(const bvector_type* bv) const;
void destruct_bvector(bvector_type* bv) const;
static
void throw_bad_alloc() { BV::throw_bad_alloc(); }
template<typename Val, typename BVect, unsigned MAX_SIZE>
friend class base_sparse_vector;
protected:
size_type bv_size_;
allocator_type alloc_;
allocation_policy_type ap_;
allocator_pool_type* pool_ = 0;
bvector_type_ptr* bv_rows_ = 0;
size_type rsize_ = 0;
bool is_dynamic_ = true; ///< if rsize is dynamic (variable length)
size_type null_idx_ = 0; ///< Index of the NULL row
};
/**
Base class for bit-transposed(bit-sliced) sparse vector construction.
Keeps the basic housekeeping lements like matrix of sparse elements
@ingroup bmagic
@internal
*/
template<typename Val, typename BV, unsigned MAX_SIZE>
class base_sparse_vector
{
public:
enum bit_planes
{
sv_slices = (sizeof(Val) * 8 * MAX_SIZE + 1),
sv_value_slices = (sizeof(Val) * 8 * MAX_SIZE)
};
enum vector_capacity
{
max_vector_size = MAX_SIZE
};
typedef Val value_type;
typedef BV bvector_type;
typedef typename BV::size_type size_type;
typedef bvector_type* bvector_type_ptr;
typedef const bvector_type* bvector_type_const_ptr;
typedef const value_type& const_reference;
typedef typename BV::allocator_type allocator_type;
typedef typename bvector_type::allocation_policy allocation_policy_type;
typedef typename bvector_type::enumerator bvector_enumerator_type;
typedef typename allocator_type::allocator_pool_type allocator_pool_type;
typedef bm::basic_bmatrix<BV> bmatrix_type;
typedef typename std::make_unsigned<value_type>::type unsigned_value_type;
public:
base_sparse_vector();
base_sparse_vector(bm::null_support null_able,
bool is_dynamic,
allocation_policy_type ap = allocation_policy_type(),
size_type bv_max_size = bm::id_max,
const allocator_type& alloc = allocator_type());
base_sparse_vector(const base_sparse_vector<Val, BV, MAX_SIZE>& bsv);
#ifndef BM_NO_CXX11
/*! move-ctor */
base_sparse_vector(base_sparse_vector<Val, BV, MAX_SIZE>&& bsv) BMNOEXCEPT
{
bmatr_.swap(bsv.bmatr_);
size_ = bsv.size_;
effective_slices_ = bsv.effective_slices_;
bsv.size_ = 0;
}
#endif
void swap(base_sparse_vector<Val, BV, MAX_SIZE>& bsv) BMNOEXCEPT;
size_type size() const BMNOEXCEPT { return size_; }
void resize(size_type new_size, bool set_null);
void clear_range(size_type left, size_type right, bool set_null);
void keep_range_no_check(size_type left, size_type right,
bm::null_support slice_null);
/*! \brief resize to zero, free memory
@param free_mem - fully destroys the plane vectors if true
*/
void clear_all(bool free_mem = true) BMNOEXCEPT;
/*! return true if empty */
bool empty() const BMNOEXCEPT { return size() == 0; }
/** swap two vector elements */
void swap_elements(size_type idx1, size_type idx2)
{ bmatr_.swap_columns(idx1, idx2); }
public:
// ------------------------------------------------------------
/*! @name Various traits */
///@{
///
/**
\brief returns true if value type is signed integral type
*/
static constexpr bool is_signed() BMNOEXCEPT
{ return std::is_signed<value_type>::value; }
/**
\brief check if container supports NULL(unassigned) values
*/
bool is_nullable() const BMNOEXCEPT { return bmatr_.get_null_idx(); }
/**
\brief check if container supports NULL (unassigned) values
*/
bm::null_support get_null_support() const BMNOEXCEPT
{ return is_nullable() ? bm::use_null : bm::no_null; }
/**
\brief Get bit-vector of assigned values or NULL
(if not constructed that way)
*/
const bvector_type* get_null_bvector() const BMNOEXCEPT
{
if (size_type null_idx = bmatr_.get_null_idx())
return bmatr_.get_row(null_idx);
return 0;
}
/** \brief test if specified element is NULL
\param idx - element index
\return true if it is NULL false if it was assigned or container
is not configured to support assignment flags
*/
bool is_null(size_type idx) const BMNOEXCEPT;
/**
Set allocation pool
*/
void set_allocator_pool(allocator_pool_type* pool_ptr) BMNOEXCEPT
{ bmatr_.set_allocator_pool(pool_ptr); }
/**
Get allocation pool
*/
allocator_pool_type* get_allocator_pool() const BMNOEXCEPT
{ return bmatr_.get_allocator_pool(); }
///@}
// ------------------------------------------------------------
/*! @name Access to internals */
///@{
/*!
\brief get access to bit-plain, function checks and creates a plane
\return bit-vector for the bit plain
@internal
*/
bvector_type_ptr get_create_slice(unsigned i);
/*!
\brief get read-only access to bit-plane
\return bit-vector for the bit plane or NULL
@internal
*/
bvector_type_const_ptr
get_slice(unsigned i) const BMNOEXCEPT { return bmatr_.row(i); }
/*!
\brief get total number of bit-planes in the vector
@internal
*/
static unsigned slices() BMNOEXCEPT { return value_bits(); }
/** Number of stored bit-planes (value planes + extra
@internal
*/
static unsigned stored_slices() BMNOEXCEPT { return value_bits()+1; }
/** Number of effective bit-planes in the value type
@internal
*/
unsigned effective_slices() const BMNOEXCEPT
{ return effective_slices_ + 1; }
/*!
\brief get access to bit-plane as is (can return NULL)
@internal
*/
bvector_type_ptr slice(unsigned i) BMNOEXCEPT { return bmatr_.get_row(i); }
bvector_type_const_ptr slice(unsigned i) const BMNOEXCEPT
{ return bmatr_.get_row(i); }
bvector_type* get_null_bvect() BMNOEXCEPT
{
if (size_type null_idx = bmatr_.get_null_idx())
return bmatr_.get_row(null_idx);
return 0;
}
/*!
\brief free memory in bit-plane
@internal
*/
void free_slice(unsigned i) { bmatr_.destruct_row(i); }
/*!
return mask of allocated bit-planes
1 in the mask - means bit-plane N is present
returns 64-bit unsigned mask for sub 64-bit types (like int)
unallocated mask bits will be zero extended
@return 64-bit mask
@internal
*/
bm::id64_t get_slice_mask(unsigned element_idx) const BMNOEXCEPT;
/*!
get read-only access to inetrnal bit-matrix
@internal
*/
const bmatrix_type& get_bmatrix() const BMNOEXCEPT { return bmatr_; }
/**
access to internal bit-matrix
@internal
*/
bmatrix_type& get_bmatrix() BMNOEXCEPT { return bmatr_; }
/**
Set NULL plain index
@internal
*/
void mark_null_idx(unsigned null_idx) BMNOEXCEPT
{ bmatr_.null_idx_ = null_idx; }
/**
Convert signed value type to unsigned representation
@internal
*/
static
unsigned_value_type s2u(value_type v) BMNOEXCEPT;
/**
Convert unsigned value type to signed representation
@internal
*/
static
value_type u2s(unsigned_value_type v) BMNOEXCEPT;
///@}
///
// -------------------------------------------------------------------
/*!
\brief run memory optimization for all bit-vector rows
\param temp_block - pre-allocated memory block to avoid unnecessary re-allocs
\param opt_mode - requested compression depth
\param stat - memory allocation statistics after optimization
*/
void optimize(bm::word_t* temp_block = 0,
typename bvector_type::optmode opt_mode = bvector_type::opt_compress,
typename bvector_type::statistics* stat = 0);
/*!
@brief Calculates memory statistics.
Function fills statistics structure containing information about how
this vector uses memory and estimation of max. amount of memory
bvector needs to serialize itself.
@param st - pointer on statistics structure to be filled in.
@sa statistics
*/
void calc_stat(typename bvector_type::statistics* st) const BMNOEXCEPT;
/*!
\brief check if another sparse vector has the same content and size
\param sv - sparse vector for comparison
\param null_able - flag to consider NULL vector in comparison (default)
or compare only value content planes
\return true, if it is the same
*/
bool equal(const base_sparse_vector<Val, BV, MAX_SIZE>& sv,
bm::null_support null_able = bm::use_null) const BMNOEXCEPT;
protected:
void copy_from(const base_sparse_vector<Val, BV, MAX_SIZE>& bsv);
/**
Merge plane bvectors from an outside base matrix
Note: outside base matrix gets destroyed
*/
void merge_matr(bmatrix_type& bmatr);
/**
Turn on RO mode
*/
void freeze_matr() { bmatr_.freeze(); is_ro_ = true; }
/*!
clear column in all value planes
\param plane_idx - row (plane index to start from)
\param idx - bit (column) to clear
*/
void clear_value_planes_from(unsigned plane_idx, size_type idx);
/*!
insert false (clear) column in all value planes
\param plane_idx - row (plane index to start from)
\param idx - bit (column) to clear insert
*/
void insert_clear_value_planes_from(unsigned plane_idx, size_type idx);
/*!
erase bit (column) from all planes
\param idx - bit (column) to erase
\param erase_null - erase the NULL vector
*/
void erase_column(size_type idx, bool erase_null);
/*!
insert (NOT) NULL value
*/
void insert_null(size_type idx, bool not_null);
/**
Set SUB (MINUS) operation on all existing bit-slices
@param bv - argument vector row[i] -= bv
*/
void bit_sub_rows(const bvector_type& bv, bool use_null)
{ bmatr_.bit_sub_rows(bv, use_null); }
/**
Set AND (intersect) operation on all existing bit-slices
@param bv - argument vector row[i] -= bv
*/
void bit_and_rows(const bvector_type& bv) { bmatr_.bit_and_rows(bv); }
protected:
typedef typename bvector_type::block_idx_type block_idx_type;
/** Number of total bit-planes in the value type*/
static constexpr unsigned value_bits() BMNOEXCEPT
{ return base_sparse_vector<Val, BV, MAX_SIZE>::sv_value_slices; }
/** plane index for the "NOT NULL" flags plane */
//static constexpr unsigned null_plane() BMNOEXCEPT { return value_bits(); }
/** optimize block in all matrix planes */
void optimize_block(block_idx_type nb, typename BV::optmode opt_mode)
{ bmatr_.optimize_block(nb, opt_mode); }
/// Sybc read-only state
void sync_ro() BMNOEXCEPT;
/**
Perform copy_range() on a set of planes
*/
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);
protected:
bmatrix_type bmatr_; ///< bit-transposed matrix
unsigned_value_type slice_mask_ = 0; ///< slice presence bit-mask
size_type size_ = 0; ///< array size
unsigned effective_slices_=0; ///< number of bit slices actually allocated
bool is_ro_=false; ///< read-only
};
//---------------------------------------------------------------------
//
//---------------------------------------------------------------------
#ifdef _MSC_VER
#pragma warning( push )
#pragma warning( disable : 4146 )
#endif
template<typename BV>
basic_bmatrix<BV>::basic_bmatrix(size_type rsize,
bool is_dynamic,
allocation_policy_type ap,
size_type bv_max_size,
const allocator_type& alloc)
: bv_size_(bv_max_size),
alloc_(alloc),
ap_(ap)
{
allocate_rows(rsize);
is_dynamic_ = is_dynamic;
}
//---------------------------------------------------------------------
template<typename BV>
basic_bmatrix<BV>::~basic_bmatrix() BMNOEXCEPT
{
free_rows();
}
//---------------------------------------------------------------------
template<typename BV>
basic_bmatrix<BV>::basic_bmatrix(const basic_bmatrix<BV>& bbm)
: bv_size_(bbm.bv_size_),
alloc_(bbm.alloc_),
ap_(bbm.ap_)
{
copy_from(bbm);
is_dynamic_ = bbm.is_dynamic_;
}
//---------------------------------------------------------------------
template<typename BV>
basic_bmatrix<BV>::basic_bmatrix(basic_bmatrix<BV>&& bbm) BMNOEXCEPT
: bv_size_(bbm.bv_size_),
alloc_(bbm.alloc_),
ap_(bbm.ap_)
{
swap(bbm);
is_dynamic_ = bbm.is_dynamic_;
}
//---------------------------------------------------------------------
template<typename BV>
const typename basic_bmatrix<BV>::bvector_type*
basic_bmatrix<BV>::row(size_type i) const BMNOEXCEPT
{
BM_ASSERT(i < rsize_);
return bv_rows_[i];
}
//---------------------------------------------------------------------
template<typename BV>
const typename basic_bmatrix<BV>::bvector_type*
basic_bmatrix<BV>::get_row(size_type i) const BMNOEXCEPT
{
BM_ASSERT(i < rsize_);
return bv_rows_[i];
}
//---------------------------------------------------------------------
template<typename BV>
typename basic_bmatrix<BV>::bvector_type*
basic_bmatrix<BV>::get_row(size_type i) BMNOEXCEPT
{
BM_ASSERT(i < rsize_);
return bv_rows_[i];
}
//---------------------------------------------------------------------
template<typename BV>
void basic_bmatrix<BV>::set_null_idx(size_type null_idx) BMNOEXCEPT
{
BM_ASSERT(null_idx);
BM_ASSERT(get_row(null_idx));
null_idx_ = null_idx;
}
//---------------------------------------------------------------------
template<typename BV>
void basic_bmatrix<BV>::copy_from(const basic_bmatrix<BV>& bbm)
{
if (this == &bbm) // nothing to do
return;
free_rows();
bv_size_ = bbm.bv_size_;
alloc_ = bbm.alloc_;
ap_ = bbm.ap_;
null_idx_ = bbm.null_idx_;
size_type rsize = bbm.rsize_;
if (rsize)
{
bv_rows_ = (bvector_type_ptr*)alloc_.alloc_ptr(rsize);
if (!bv_rows_)
throw_bad_alloc();
rsize_ = rsize;
for (size_type i = 0; i < rsize_; ++i)
{
const bvector_type_ptr bv = bbm.bv_rows_[i];
bv_rows_[i] = bv ? construct_bvector(bv) : 0;
}
}
}
//---------------------------------------------------------------------
template<typename BV>
void basic_bmatrix<BV>::erase_column(size_type idx, bool erase_null)
{
// relies that NULL bvector is the last
size_type r_to = (!erase_null && null_idx_) ? null_idx_ : rsize_;
for (size_type i = 0; i < r_to; ++i)
if (bvector_type* bv = get_row(i))
bv->erase(idx);
}
//---------------------------------------------------------------------
template<typename BV>
void basic_bmatrix<BV>::insert_column(size_type idx,
size_type row_from)
{
for (size_type i = row_from; i < rsize_; ++i)
if (bvector_type* bv = get_row(i))
bv->insert(idx, false);
}
//---------------------------------------------------------------------
template<typename BV>
void basic_bmatrix<BV>::clear_column(size_type idx,
size_type row_from)
{
for (size_type i = row_from; i < rsize_; ++i)
if (bvector_type* bv = get_row(i))
bv->clear_bit_no_check(idx);
}
//---------------------------------------------------------------------
template<typename BV>
void basic_bmatrix<BV>::swap_columns(size_type idx1, size_type idx2)
{
for (size_type i = 0; i < rsize_; ++i)
if (bvector_type* bv = get_row(i))
bv->swap(idx1, idx2);
}
//---------------------------------------------------------------------
template<typename BV>
void basic_bmatrix<BV>::allocate_rows(size_type rsize)
{
size_type rsize_prev(rsize_);
if (rsize <= rsize_prev)
return; // nothing to do
bvector_type_ptr* bv_rows_prev(bv_rows_);
BM_ASSERT(rsize);
bv_rows_ = (bvector_type_ptr*)alloc_.alloc_ptr(unsigned(rsize));
if (!bv_rows_)
throw_bad_alloc();
rsize_ = rsize;
BM_ASSERT((!null_idx_) || (rsize & 1u));
::memset(&bv_rows_[0], 0, rsize * sizeof(bv_rows_[0]));
if (bv_rows_prev) // deallocate prev, reset NULL
{
for (size_type i = 0; i < rsize_prev; ++i)
bv_rows_[i] = bv_rows_prev[i];
alloc_.free_ptr(bv_rows_prev, unsigned(rsize_prev));
if (null_idx_) // shift-up the NULL row
{
bv_rows_[rsize-1] = bv_rows_[null_idx_];
bv_rows_[null_idx_] = 0;
null_idx_ = rsize-1;
BM_ASSERT(rsize & 1u);
}
}
}
//---------------------------------------------------------------------
template<typename BV>
typename basic_bmatrix<BV>::size_type
basic_bmatrix<BV>::octet_size() const BMNOEXCEPT
{
size_type osize = (7 + rows_not_null()) / 8;
return osize;
}
//---------------------------------------------------------------------
template<typename BV>
void basic_bmatrix<BV>::free_rows() BMNOEXCEPT
{
for (size_type i = 0; i < rsize_; ++i)
{
if (bvector_type_ptr bv = bv_rows_[i])
{
destruct_bvector(bv);
bv_rows_[i] = 0;
}
} // for i
if (bv_rows_)
alloc_.free_ptr(bv_rows_, unsigned(rsize_));
bv_rows_ = 0;
}
//---------------------------------------------------------------------
template<typename BV>
bool basic_bmatrix<BV>::is_same_structure(
const basic_bmatrix<BV>& bbm) const BMNOEXCEPT
{
BM_ASSERT(this != &bbm);
if (rsize_ != bbm.rsize_)
return false;
if (null_idx_ != bbm.null_idx_)
return false;
for (size_type i = 0; i < rsize_; ++i)
{
const bvector_type* bv = bv_rows_[i];
const bvector_type* bv_arg = bbm.bv_rows_[i];
if (bool(bv) != bool(bv_arg))
return false;
} // for i
return true;
}
//---------------------------------------------------------------------
template<typename BV>
void basic_bmatrix<BV>::set_allocator_pool(allocator_pool_type* pool_ptr) BMNOEXCEPT
{
if (pool_ != pool_ptr)
{
for (size_type i = 0; i < rsize_; ++i)
if (bvector_type_ptr bv = bv_rows_[i])
bv->set_allocator_pool(pool_ptr);
}
pool_ = pool_ptr;
}
//---------------------------------------------------------------------
template<typename BV>
typename basic_bmatrix<BV>::size_type
basic_bmatrix<BV>::calc_effective_rows_not_null() const BMNOEXCEPT
{
// TODO: SIMD
auto i = rows_not_null();
for (--i; i > 0; --i)
{
if (bv_rows_[i])
{
++i;
break;
}
}
return i;
}
//---------------------------------------------------------------------
template<typename BV>
void basic_bmatrix<BV>::bit_sub_rows(const bvector_type& bv, bool use_null)
{
size_type sz = use_null ? rsize_: calc_effective_rows_not_null();
for (size_type i = 0; i < sz; ++i)
{
if (bvector_type_ptr bv_r = bv_rows_[i])
bv_r->bit_sub(bv);
} // for i
}
//---------------------------------------------------------------------
template<typename BV>
void basic_bmatrix<BV>::bit_and_rows(const bvector_type& bv)
{
for (size_type i = 0; i < rsize_; ++i)
{
if (bvector_type_ptr bv_r = bv_rows_[i])
bv_r->bit_and(bv);
} // for i
}
//---------------------------------------------------------------------
template<typename BV>
void basic_bmatrix<BV>::swap(basic_bmatrix<BV>& bbm) BMNOEXCEPT
{
if (this == &bbm)
return;
bm::xor_swap(bv_size_, bbm.bv_size_);
allocator_type alloc_tmp = alloc_;
alloc_ = bbm.alloc_;
bbm.alloc_ = alloc_tmp;
allocation_policy_type ap_tmp = ap_;
ap_ = bbm.ap_;
bbm.ap_ = ap_tmp;
allocator_pool_type* pool_tmp = pool_;
pool_ = bbm.pool_;
bbm.pool_ = pool_tmp;
bm::xor_swap(rsize_, bbm.rsize_);
bm::xor_swap(null_idx_, bbm.null_idx_);
bvector_type_ptr* rtmp = bv_rows_;
bv_rows_ = bbm.bv_rows_;
bbm.bv_rows_ = rtmp;
}
//---------------------------------------------------------------------
template<typename BV>
typename basic_bmatrix<BV>::bvector_type_ptr
basic_bmatrix<BV>::construct_row(size_type row)
{
if (is_dynamic())
{
if (row >= rsize_)
allocate_rows(rsize_ + 8);
}
BM_ASSERT(row < rsize_);
bvector_type_ptr bv = bv_rows_[row];
if (!bv)
bv = bv_rows_[row] = construct_bvector(0);
return bv;
}
//---------------------------------------------------------------------
template<typename BV>
typename basic_bmatrix<BV>::bvector_type_ptr
basic_bmatrix<BV>::construct_row(size_type row, const bvector_type& bv_src)
{
if (row >= rsize_)
allocate_rows(row + 8);
BM_ASSERT(row < rsize_);
bvector_type_ptr bv = bv_rows_[row];
if (bv)
*bv = bv_src;
else
bv = bv_rows_[row] = construct_bvector(&bv_src);
return bv;
}
//---------------------------------------------------------------------
template<typename BV>
void basic_bmatrix<BV>::destruct_row(size_type row)
{
BM_ASSERT(row < rsize_);
if (bvector_type_ptr bv = bv_rows_[row])
{
destruct_bvector(bv);
bv_rows_[row] = 0;
}
}
//---------------------------------------------------------------------
template<typename BV>
void basic_bmatrix<BV>::clear_row(size_type row, bool free_mem)
{
BM_ASSERT(row < rsize_);
if (bvector_type_ptr bv = bv_rows_[row])
{
if (free_mem)
{
destruct_bvector(bv);
bv_rows_[row] = 0;
}
else
bv->clear(true);
}
}
//---------------------------------------------------------------------
template<typename BV>
typename basic_bmatrix<BV>::bvector_type*
basic_bmatrix<BV>::construct_bvector(const bvector_type* bv) const
{
bvector_type* rbv = 0;
#ifdef BM_NO_STL // C compatibility mode
void* mem = ::malloc(sizeof(bvector_type));
if (mem == 0)
{
BM_THROW(false, BM_ERR_BADALLOC);
}
if (bv)
rbv = new(mem) bvector_type(*bv);
else
{
rbv = new(mem) bvector_type(ap_.strat, ap_.glevel_len, bv_size_, alloc_);
rbv->init();
}
#else
if (bv)
rbv = new bvector_type(*bv);
else
{
rbv = new bvector_type(ap_.strat, ap_.glevel_len, bv_size_, alloc_);
rbv->init();
}
#endif
if (pool_)
rbv->set_allocator_pool(pool_);
return rbv;
}
//---------------------------------------------------------------------
template<typename BV>
void basic_bmatrix<BV>::destruct_bvector(bvector_type* bv) const
{
#ifdef BM_NO_STL // C compatibility mode
bv->~TBM_bvector();
::free((void*)bv);
#else
delete bv;
#endif
}
//---------------------------------------------------------------------
template<typename BV>
const bm::word_t*
basic_bmatrix<BV>::get_block(size_type p,
unsigned i, unsigned j) const BMNOEXCEPT
{
if (bvector_type_const_ptr bv = this->row(p))
return bv->get_blocks_manager().get_block_ptr(i, j);
return 0;
}
//---------------------------------------------------------------------
template<typename BV>
void basic_bmatrix<BV>::clear_slices_range(
unsigned slice_from, unsigned slice_until,
size_type idx)
{
for (unsigned p = slice_from; p < slice_until; ++p)
if (bvector_type* bv = this->get_row(p)) // TODO: optimize cleaning
bv->clear_bit_no_check(idx);
}
//---------------------------------------------------------------------
template<typename BV>
void basic_bmatrix<BV>::set_octet(size_type pos,
size_type octet_idx,
unsigned char octet)
{
if (7u + octet_idx * 8u > rsize_)
allocate_rows(rsize_ + 16);
size_type row = octet_idx * 8;
size_type row_end = row + 8;
for (; row < row_end; ++row)
{
bvector_type* bv = (row < rsize_) ? this->get_row(row) : 0;
if (octet & 1u)
{
if (!bv)
bv = this->construct_row(row);
bv->set_bit_no_check(pos);
}
else
{
if (bv)
bv->clear_bit_no_check(pos);
}
octet >>= 1;
if (!octet)
break;
} // for
// clear the tail
if (row_end > rsize_)
row_end = rsize_;
for (++row; row < row_end; ++row)
if (bvector_type* bv = this->get_row(row))
bv->clear_bit_no_check(pos);
}
//---------------------------------------------------------------------
template<typename BV>
void basic_bmatrix<BV>::insert_octet(size_type pos,
size_type octet_idx,
unsigned char octet)
{
BM_ASSERT(octet_idx * 8u < rsize_);
size_type oct = octet;
size_type row = octet_idx * 8;
size_type row_end = row + 8;
for (; row < row_end; ++row)
{
bvector_type* bv = (row < rsize_) ? this->get_row(row) : 0;
if (oct & 1u)
{
if (!bv)
{
bv = this->construct_row(row);
bv->set_bit_no_check(pos);
}
else
{
bv->insert(pos, true);
}
}
else
{
if (bv)
bv->insert(pos, false);
}
oct >>= 1;
if (!oct)
break;
} // for
// clear the tail
if (row_end > rsize_)
row_end = rsize_;
for (++row; row < row_end; ++row)
if (bvector_type* bv = this->get_row(row))
bv->insert(pos, false);
}
//---------------------------------------------------------------------
/// @internal
inline
bool check_any_fullb(const bm::word_t* blka[8], const bm::word_t* FBADDR)
{
bool b1, b2;
b1 = (blka[0] == FBADDR);
b2 = (blka[1] == FBADDR);
b1 |= (blka[2] == FBADDR);
b2 |= (blka[3] == FBADDR);
b1 |= (blka[4] == FBADDR);
b2 |= (blka[5] == FBADDR);
b1 |= (blka[6] == FBADDR);
b2 |= (blka[7] == FBADDR);
return b1 | b2;
}
template<typename BV>
unsigned char
basic_bmatrix<BV>::get_octet(size_type pos, size_type octet_idx) const BMNOEXCEPT
{
const bm::word_t* blka[8];
unsigned v = 0;
block_idx_type nb = (pos >> bm::set_block_shift);
unsigned i0, j0;
bm::get_block_coord(nb, i0, j0);
unsigned row_idx = unsigned(octet_idx * 8);
if (row_idx + 7 >= rsize_ ||
(null_idx_ && (row_idx + 7 > null_idx_))) // out of bounds request?
return (unsigned char)v;
blka[0] = get_block(row_idx+0, i0, j0);
blka[1] = get_block(row_idx+1, i0, j0);
blka[2] = get_block(row_idx+2, i0, j0);
blka[3] = get_block(row_idx+3, i0, j0);
blka[4] = get_block(row_idx+4, i0, j0);
blka[5] = get_block(row_idx+5, i0, j0);
blka[6] = get_block(row_idx+6, i0, j0);
blka[7] = get_block(row_idx+7, i0, j0);
const bm::word_t* const FBADDR = FULL_BLOCK_FAKE_ADDR;
unsigned is_set;
unsigned nbit = unsigned(pos & bm::set_block_mask);
const unsigned nword = unsigned(nbit >> bm::set_word_shift);
const unsigned mask0 = 1u << (nbit & bm::set_word_mask);
#if 0
bool any_full = bm::check_any_fullb(blka, FBADDR);
if (!any_full)
{
if (const bm::word_t* blk; (blk = blka[0])!=0)
{
is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
v |= (unsigned)bool(is_set);
}
if (const bm::word_t* blk;(blk = blka[1])!=0)
{
is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
v |= unsigned(bool(is_set)) << 1u;
}
if (const bm::word_t* blk;(blk = blka[2])!=0)
{
is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
v |= unsigned(bool(is_set)) << 2u;
}
if (const bm::word_t* blk;(blk = blka[3])!=0)
{
is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
v |= unsigned(bool(is_set)) << 3u;
}
if (const bm::word_t* blk;(blk = blka[4])!=0)
{
is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
v |= unsigned(bool(is_set)) << 4u;
}
if (const bm::word_t* blk;(blk = blka[5])!=0)
{
is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
v |= unsigned(bool(is_set)) << 5u;
}
if (const bm::word_t* blk;(blk = blka[6])!=0)
{
is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
v |= unsigned(bool(is_set)) << 6u;
}
if (const bm::word_t* blk;(blk = blka[7])!=0)
{
is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
v |= unsigned(bool(is_set)) << 7u;
}
return (unsigned char)v;
}
#endif
const bm::word_t* blk;
if ((blk = blka[0])!=0)
{
if (blk == FBADDR)
is_set = 1;
else
is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
v |= (unsigned)bool(is_set);
}
if ((blk = blka[1])!=0)
{
if (blk == FBADDR)
is_set = 1;
else
is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
v |= unsigned(bool(is_set)) << 1u;
}
if ((blk = blka[2])!=0)
{
if (blk == FBADDR)
is_set = 1;
else
is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
v |= unsigned(bool(is_set)) << 2u;
}
if ((blk = blka[3])!=0)
{
if (blk == FBADDR)
is_set = 1;
else
is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
v |= unsigned(bool(is_set)) << 3u;
}
if ((blk = blka[4])!=0)
{
if (blk == FBADDR)
is_set = 1;
else
is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
v |= unsigned(bool(is_set)) << 4u;
}
if ((blk = blka[5])!=0)
{
if (blk == FBADDR)
is_set = 1;
else
is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
v |= unsigned(bool(is_set)) << 5u;
}
if ((blk = blka[6])!=0)
{
if (blk == FBADDR)
is_set = 1;
else
is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
v |= unsigned(bool(is_set)) << 6u;
}
if ((blk = blka[7])!=0)
{
if (blk == FBADDR)
is_set = 1;
else
is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
v |= unsigned(bool(is_set)) << 7u;
}
return (unsigned char)v;
}
//---------------------------------------------------------------------
template<typename BV>
int basic_bmatrix<BV>::compare_octet(size_type pos,
size_type octet_idx,
char octet) const BMNOEXCEPT
{
char value = char(get_octet(pos, octet_idx));
return (value > octet) - (value < octet);
}
//---------------------------------------------------------------------
/**
Test 4 pointers are all marked as GAPs
@internal
*/
inline
bool test_4gaps(const bm::word_t* p0, const bm::word_t* p1,
const bm::word_t* p2, const bm::word_t* p3) BMNOEXCEPT
{
uintptr_t p
= uintptr_t(p0) | uintptr_t(p1) | uintptr_t(p2) | uintptr_t(p3);
return (p & 1);
}
/**
Test 4 pointers are not NULL and not marked as FULLBLOCK
@internal
*/
inline
bool test_4bits(const bm::word_t* p0, const bm::word_t* p1,
const bm::word_t* p2, const bm::word_t* p3) BMNOEXCEPT
{
return p0 && p0!=FULL_BLOCK_FAKE_ADDR &&
p1 && p1!=FULL_BLOCK_FAKE_ADDR &&
p2 && p2!=FULL_BLOCK_FAKE_ADDR &&
p3 && p3!=FULL_BLOCK_FAKE_ADDR;
}
template<typename BV>
unsigned
basic_bmatrix<BV>::get_half_octet(size_type pos, size_type row_idx) const BMNOEXCEPT
{
unsigned v = 0;
block_idx_type nb = (pos >> bm::set_block_shift);
unsigned i0, j0;
bm::get_block_coord(nb, i0, j0);
const bm::word_t* blk;
const bm::word_t* blka[4];
unsigned nbit = unsigned(pos & bm::set_block_mask);
blka[0] = get_block(row_idx+0, i0, j0);
blka[1] = get_block(row_idx+1, i0, j0);
blka[2] = get_block(row_idx+2, i0, j0);
blka[3] = get_block(row_idx+3, i0, j0);
unsigned is_set;
unsigned nword = unsigned(nbit >> bm::set_word_shift);
unsigned mask0 = 1u << (nbit & bm::set_word_mask);
// speculative assumption that nibble is often 4 bit-blocks
// and we will be able to extract it faster with less mispredicts
//
if (!test_4gaps(blka[0], blka[1], blka[2], blka[3]))
{
if (test_4bits(blka[0], blka[1], blka[2], blka[3]))
{
v = unsigned(bool((blka[0][nword] & mask0))) |
unsigned(bool((blka[1][nword] & mask0)) << 1u) |
unsigned(bool((blka[2][nword] & mask0)) << 2u) |
unsigned(bool((blka[3][nword] & mask0)) << 3u);
return v;
}
}
// hypothesis above didn't work out extract the regular way
unsigned i = 0;
do
{
if ((blk = blka[i])!=0)
{
if (blk == FULL_BLOCK_FAKE_ADDR)
is_set = 1;
else
is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
v |= unsigned(bool(is_set)) << i;
}
if ((blk = blka[++i])!=0)
{
if (blk == FULL_BLOCK_FAKE_ADDR)
is_set = 1;
else
is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
v |= unsigned(bool(is_set)) << i;
}
} while(++i < 4);
return v;
}
//---------------------------------------------------------------------
template<typename BV>
void basic_bmatrix<BV>::optimize(bm::word_t* temp_block,
typename bvector_type::optmode opt_mode,
typename bvector_type::statistics* st)
{
if (st)
st->reset();
BM_DECLARE_TEMP_BLOCK(tb)
if (!temp_block)
temp_block = tb;
for (unsigned k = 0; k < rsize_; ++k)
{
if (bvector_type* bv = get_row(k))
{
typename bvector_type::statistics stbv;
stbv.reset();
bv->optimize(temp_block, opt_mode, st ? &stbv : 0);
if (st)
st->add(stbv);
}
} // for k
}
//---------------------------------------------------------------------
template<typename BV>
void basic_bmatrix<BV>::freeze()
{
for (unsigned k = 0; k < rsize_; ++k)
if (bvector_type* bv = get_row(k))
bv->freeze();
}
//---------------------------------------------------------------------
template<typename BV>
void basic_bmatrix<BV>::calc_stat(typename bvector_type::statistics& st,
size_type rsize) const BMNOEXCEPT
{
for (size_type i = 0; i < rsize; ++i)
if (const bvector_type* bv = row(i))
{
typename bvector_type::statistics stbv;
bv->calc_stat(&stbv);
st.add(stbv);
}
else
st.max_serialize_mem += 8;
}
//---------------------------------------------------------------------
template<typename BV>
void basic_bmatrix<BV>::optimize_block(block_idx_type nb,
typename BV::optmode opt_mode)
{
for (unsigned k = 0; k < rsize_; ++k)
{
if (bvector_type* bv = get_row(k))
{
unsigned i, j;
bm::get_block_coord(nb, i, j);
typename bvector_type::blocks_manager_type& bman =
bv->get_blocks_manager();
bman.optimize_bit_block(i, j, opt_mode);
}
} // for k
}
//---------------------------------------------------------------------
//
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
base_sparse_vector<Val, BV, MAX_SIZE>::base_sparse_vector()
: bmatr_(sv_slices, true, allocation_policy_type(), bm::id_max, allocator_type())
{}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
base_sparse_vector<Val, BV, MAX_SIZE>::base_sparse_vector(
bm::null_support null_able,
bool is_dynamic,
allocation_policy_type ap,
size_type bv_max_size,
const allocator_type& alloc)
: bmatr_(sv_slices, is_dynamic, ap, bv_max_size, alloc)
{
if (null_able == bm::use_null)
{
size_type null_idx = (MAX_SIZE * sizeof(Val) * 8);
bmatr_.construct_row(null_idx)->init();
bmatr_.set_null_idx(null_idx);
slice_mask_ |= unsigned_value_type(1) << null_idx;
}
}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
base_sparse_vector<Val, BV, MAX_SIZE>::base_sparse_vector(
const base_sparse_vector<Val, BV, MAX_SIZE>& bsv)
: bmatr_(bsv.bmatr_),
slice_mask_(bsv.slice_mask_),
size_(bsv.size_),
effective_slices_(bsv.effective_slices_)
{}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
void base_sparse_vector<Val, BV, MAX_SIZE>::copy_from(
const base_sparse_vector<Val, BV, MAX_SIZE>& bsv)
{
resize(bsv.size(), true);
effective_slices_ = bsv.effective_slices_;
size_type arg_null_idx = bsv.bmatr_.get_null_idx();
if (arg_null_idx)
bmatr_.null_idx_ = arg_null_idx;
size_type slices = bsv.get_bmatrix().rows(); //stored_slices();
bmatr_.allocate_rows(slices);
for (size_type i = 0; i < slices; ++i)
{
bvector_type* bv = bmatr_.get_row(i);
const bvector_type* bv_src = bsv.bmatr_.row(i);
if (i && (i == arg_null_idx)) // NULL plane copy
{
if (bv && !bv_src) // special case (copy from not NULL)
{
if (size_)
bv->set_range(0, size_-1);
continue;
}
}
if (bv)
{
bmatr_.destruct_row(i);
slice_mask_ &= ~(unsigned_value_type(1) << i);
}
if (bv_src)
{
bmatr_.construct_row(i, *bv_src);
slice_mask_ |= (unsigned_value_type(1) << i);
}
} // for i
}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
void base_sparse_vector<Val, BV, MAX_SIZE>::merge_matr(
bmatrix_type& bmatr)
{
size_type rows = this->bmatr_.rows();
const size_type arg_rows = bmatr.rows();
if (rows < arg_rows)
{
rows = arg_rows;
bmatr_.allocate_rows(rows);
BM_ASSERT(this->bmatr_.rows() == arg_rows);
}
bvector_type* bv_null_arg = 0;
size_type null_idx = bmatr.get_null_idx();
if (null_idx)
bv_null_arg = bmatr.get_row(null_idx);
if (bvector_type* bv_null = get_null_bvect())
{
BM_ASSERT(bv_null_arg);
bv_null->merge(*bv_null_arg);
}
if (rows > arg_rows)
rows = arg_rows; // min
for (unsigned j = 0; j < rows; ++j)
{
bvector_type* arg_bv = bmatr.get_row(j);
if (arg_bv && arg_bv != bv_null_arg)
{
bvector_type* bv = this->get_create_slice(j);
slice_mask_ |= (unsigned_value_type(1) << j);
bv->merge(*arg_bv);
}
} // for j
}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
void base_sparse_vector<Val, BV, MAX_SIZE>::swap(
base_sparse_vector<Val, BV, MAX_SIZE>& bsv) BMNOEXCEPT
{
if (this != &bsv)
{
bmatr_.swap(bsv.bmatr_);
bm::xor_swap(slice_mask_, bsv.slice_mask_);
bm::xor_swap(size_, bsv.size_);
bm::xor_swap(effective_slices_, bsv.effective_slices_);
}
}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
void base_sparse_vector<Val, BV, MAX_SIZE>::clear_all(bool free_mem) BMNOEXCEPT
{
auto slices = bmatr_.rows();
bvector_type* bv_null = this->get_null_bvect();
for (size_type i = 0; i < slices; ++i)
if (bvector_type* bv = this->bmatr_.get_row(i))
if (bv != bv_null)
bmatr_.clear_row(i, free_mem);
slice_mask_ = 0; size_ = 0;
if (bv_null)
bv_null->clear(true);
is_ro_ = false;
}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
void base_sparse_vector<Val, BV, MAX_SIZE>::clear_range(
typename base_sparse_vector<Val, BV, MAX_SIZE>::size_type left,
typename base_sparse_vector<Val, BV, MAX_SIZE>::size_type right,
bool set_null)
{
if (right < left)
return clear_range(right, left, set_null);
auto planes = bmatr_.rows();
bvector_type* bv_null = this->get_null_bvect();
for (unsigned i = 0; i < planes; ++i)
{
if (bvector_type* bv = this->bmatr_.get_row(i))
if (bv != bv_null)
bv->clear_range_no_check(left, right);
}
if (set_null && bv_null)
bv_null->clear_range_no_check(left, right);
}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
void base_sparse_vector<Val, BV, MAX_SIZE>::keep_range_no_check(
size_type left, size_type right,
bm::null_support slice_null)
{
if (left)
this->clear_range(0, left-1, (slice_null == bm::use_null));
size_type sz = size();
if (right < sz)
this->clear_range(right + 1, sz, (slice_null == bm::use_null));
}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
void base_sparse_vector<Val, BV, MAX_SIZE>::resize(size_type sz, bool set_null)
{
if (sz == size()) // nothing to do
return;
if (!sz) // resize to zero is an equivalent of non-destructive deallocation
{
clear_all();
return;
}
if (sz < size()) // vector shrink
clear_range(sz, this->size_, set_null); // clear the tails and NULL
size_ = sz;
}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
bool base_sparse_vector<Val, BV, MAX_SIZE>::is_null(
size_type idx) const BMNOEXCEPT
{
const bvector_type* bv_null = get_null_bvector();
return (bv_null) ? (!bv_null->test(idx)) : false;
}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
void base_sparse_vector<Val, BV, MAX_SIZE>::insert_null(size_type idx,
bool not_null)
{
if (bvector_type* bv_null = this->get_null_bvect())
bv_null->insert(idx, not_null);
}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
typename base_sparse_vector<Val, BV, MAX_SIZE>::bvector_type_ptr
base_sparse_vector<Val, BV, MAX_SIZE>::get_create_slice(unsigned i)
{
bvector_type_ptr bv = bmatr_.construct_row(i);
// slice mask or efective_slices does not extend beyond the natural size
// (in bits)
if (i < (sizeof(value_type) * 8))
{
// note: unsigned int shift by << 32 is UNDEFINED behav.
slice_mask_ |= (unsigned_value_type(1) << i);
if (i > effective_slices_)
effective_slices_ = i;
}
return bv;
}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
bm::id64_t base_sparse_vector<Val, BV, MAX_SIZE>::get_slice_mask(
unsigned element_idx) const BMNOEXCEPT
{
bm::id64_t mask = 0;
bm::id64_t mask1 = 1;
const unsigned planes = sizeof(value_type) * 8;
unsigned bidx = 0;
unsigned slice_size = (element_idx+1) * planes;
if (slice_size > this->bmatr_.rows())
slice_size = (unsigned) this->bmatr_.rows();
for (unsigned i = element_idx * planes; i < slice_size; ++i, ++bidx)
mask |= get_slice(i) ? (mask1 << bidx) : 0ull;
return mask;
}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
void base_sparse_vector<Val, BV, MAX_SIZE>::optimize(bm::word_t* temp_block,
typename bvector_type::optmode opt_mode,
typename bvector_type::statistics* st)
{
typename bvector_type::statistics stbv;
bmatr_.optimize(temp_block, opt_mode, &stbv);
if (st)
st->add(stbv);
bvector_type* bv_null = this->get_null_bvect();
unsigned slices = (unsigned)this->bmatr_.rows();
for (unsigned j = 0; j < slices; ++j)
{
bvector_type* bv = this->bmatr_.get_row(j);
if (bv && (bv != bv_null)) // protect the NULL vector from de-allocation
{
// TODO: check if this can be done within optimize loop
if (!bv->any()) // empty vector?
{
this->bmatr_.destruct_row(j);
slice_mask_ &= ~(unsigned_value_type(1) << j);
continue;
}
}
} // for j
}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
void base_sparse_vector<Val, BV, MAX_SIZE>::calc_stat(
typename bvector_type::statistics* st) const BMNOEXCEPT
{
BM_ASSERT(st);
st->reset();
size_type slices = this->get_bmatrix().rows();//stored_slices();
bmatr_.calc_stat(*st, slices);
// header accounting
st->max_serialize_mem += 1 + 1 + 1 + 1 + 8 + (8 * slices);
st->max_serialize_mem += 1 + 8; // extra header fields for large bit-matrixes
}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
void base_sparse_vector<Val, BV, MAX_SIZE>::clear_value_planes_from(
unsigned plane_idx, size_type idx)
{
bmatr_.clear_column(idx, plane_idx);
}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
void base_sparse_vector<Val, BV, MAX_SIZE>::insert_clear_value_planes_from(
unsigned plane_idx, size_type idx)
{
bmatr_.insert_column(idx, plane_idx);
}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
void base_sparse_vector<Val, BV, MAX_SIZE>::erase_column(
size_type idx, bool erase_null)
{
bmatr_.erase_column(idx, erase_null);
}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
bool base_sparse_vector<Val, BV, MAX_SIZE>::equal(
const base_sparse_vector<Val, BV, MAX_SIZE>& sv,
bm::null_support null_able) const BMNOEXCEPT
{
if (size_type arg_size = sv.size(); this->size_ != arg_size)
return false;
unsigned slices = (unsigned) this->bmatr_.rows();
unsigned arg_slices = (unsigned) sv.bmatr_.rows();
unsigned max_slices(slices);
if (max_slices < arg_slices)
max_slices = arg_slices;
const bvector_type* bv_null = this->get_null_bvector();
const bvector_type* bv_null_arg = sv.get_null_bvector();
for (unsigned j = 0; j < max_slices; ++j)
{
const bvector_type* bv;
const bvector_type* arg_bv;
bv = (j < slices) ? this->bmatr_.get_row(j) : 0;
arg_bv = (j < arg_slices) ? sv.bmatr_.get_row(j) : 0;
if (bv == bv_null)
bv = 0; // NULL vector compare postponed for later
if (arg_bv == bv_null_arg)
arg_bv = 0;
if (bv == arg_bv) // same NULL
continue;
// check if any not NULL and not empty
if (!bv && arg_bv)
{
if (arg_bv->any())
return false;
continue;
}
if (bv && !arg_bv)
{
if (bv->any())
return false;
continue;
}
// both not NULL
bool eq = bv->equal(*arg_bv);
if (!eq)
return false;
} // for j
if (null_able == bm::use_null)
{
// check the NULL vectors
if (bv_null == bv_null_arg)
return true;
if (!bv_null || !bv_null_arg)
return false; // TODO: this may need an improvement when one is null, others not null
BM_ASSERT(bv_null);
BM_ASSERT(bv_null_arg);
bool eq = bv_null->equal(*bv_null_arg);
if (!eq)
return false;
}
return true;
}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
void base_sparse_vector<Val, BV, MAX_SIZE>::sync_ro() BMNOEXCEPT
{
unsigned slices = (unsigned) this->bmatr_.rows();
for (unsigned j = 0; j < slices; ++j)
{
if (const bvector_type* bv = this->bmatr_.get_row(j))
{
if (bv->is_ro())
{
is_ro_ = true;
break;
}
}
} // for j
}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
void base_sparse_vector<Val, BV, MAX_SIZE>::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)
{
if (bmatr_.rows() < bsv.bmatr_.rows())
bmatr_.allocate_rows(bsv.bmatr_.rows());
size_type spli;
const bvector_type* bv_null_arg = bsv.get_null_bvector();
if (bvector_type* bv_null = get_null_bvect())
{
spli = this->bmatr_.rows(); //stored_slices();
if (bv_null_arg && (slice_null == bm::use_null))
bv_null->copy_range(*bv_null_arg, left, right);
--spli;
}
else
spli = this->bmatr_.rows();
for (size_type j = 0; j < spli; ++j)
{
if (const bvector_type* arg_bv = bsv.bmatr_.row(j))
{
if (arg_bv == bv_null_arg)
continue;
bvector_type* bv = this->get_create_slice(unsigned(j));
bv->copy_range(*arg_bv, left, right);
}
} // for j
}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
typename base_sparse_vector<Val, BV, MAX_SIZE>::unsigned_value_type
base_sparse_vector<Val, BV, MAX_SIZE>::s2u(value_type v) BMNOEXCEPT
{
if constexpr (is_signed())
{
if (v < 0)
{
// the +1 trick is to get abs of INT_MIN without overflowing
// https://stackoverflow.com/questions/22268815/absolute-value-of-int-min
value_type uv = -(v+1);
return 1u | unsigned_value_type((unsigned_value_type(uv) << 1u));
}
return unsigned_value_type(unsigned_value_type(v) << 1u);
}
else
return v;
}
//---------------------------------------------------------------------
template<class Val, class BV, unsigned MAX_SIZE>
typename base_sparse_vector<Val, BV, MAX_SIZE>::value_type
base_sparse_vector<Val, BV, MAX_SIZE>::u2s(unsigned_value_type uv) BMNOEXCEPT
{
if constexpr (is_signed())
{
if (uv & 1u) // signed
{
value_type s = (-(uv >> 1u)) - 1;
return s;
}
return value_type(uv >> 1u);
}
else
return uv;
}
#ifdef _MSC_VER
#pragma warning( pop )
#endif
} // namespace
#endif
bm.h
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
BM_DECLARE_TEMP_BLOCK
#define BM_DECLARE_TEMP_BLOCK(x)
Definition bm.h:47
bmconst.h
Constants, lookup tables and typedefs.
bmdef.h
Definitions(internal).
BMNOEXCEPT
#define BMNOEXCEPT
Definition bmdef.h:82
BMGAP_PTR
#define BMGAP_PTR(ptr)
Definition bmdef.h:189
BM_IS_GAP
#define BM_IS_GAP(ptr)
Definition bmdef.h:191
BM_ASSERT
#define BM_ASSERT
Definition bmdef.h:139
FULL_BLOCK_FAKE_ADDR
#define FULL_BLOCK_FAKE_ADDR
Definition bmdef.h:158
bmtrans.h
Utilities for bit transposition (internal) (experimental!).
bm::base_sparse_vector::freeze_matr
void freeze_matr()
Turn on RO mode.
Definition bmbmatrix.h:633
bm::base_sparse_vector::get_slice
bvector_type_const_ptr get_slice(unsigned i) const BMNOEXCEPT
get read-only access to bit-plane
Definition bmbmatrix.h:497
bm::base_sparse_vector::swap
void swap(base_sparse_vector< Val, BV, MAX_SIZE > &bsv) BMNOEXCEPT
Definition bmbmatrix.h:1744
bm::base_sparse_vector::resize
void resize(size_type new_size, bool set_null)
Definition bmbmatrix.h:1812
bm::base_sparse_vector::get_null_support
bm::null_support get_null_support() const BMNOEXCEPT
check if container supports NULL (unassigned) values
Definition bmbmatrix.h:444
bm::base_sparse_vector::effective_slices
unsigned effective_slices() const BMNOEXCEPT
Number of effective bit-planes in the value type.
Definition bmbmatrix.h:514
bm::base_sparse_vector< Val, BV, 1 >::slice_mask_
unsigned_value_type slice_mask_
Definition bmbmatrix.h:702
bm::base_sparse_vector::bvector_type_const_ptr
const bvector_type * bvector_type_const_ptr
Definition bmbmatrix.h:369
bm::base_sparse_vector::merge_matr
void merge_matr(bmatrix_type &bmatr)
Merge plane bvectors from an outside base matrix Note: outside base matrix gets destroyed.
Definition bmbmatrix.h:1705
bm::base_sparse_vector::vector_capacity
vector_capacity
Definition bmbmatrix.h:361
bm::base_sparse_vector< Val, BV, 1 >::max_vector_size
@ max_vector_size
Definition bmbmatrix.h:362
bm::base_sparse_vector::slices
static unsigned slices() BMNOEXCEPT
get total number of bit-planes in the vector
Definition bmbmatrix.h:503
bm::base_sparse_vector::u2s
static value_type u2s(unsigned_value_type v) BMNOEXCEPT
Convert unsigned value type to signed representation.
Definition bmbmatrix.h:2108
bm::base_sparse_vector::bvector_type_ptr
bvector_type * bvector_type_ptr
Definition bmbmatrix.h:368
bm::base_sparse_vector::const_reference
const value_type & const_reference
Definition bmbmatrix.h:370
bm::base_sparse_vector::get_null_bvector
const bvector_type * get_null_bvector() const BMNOEXCEPT
Get bit-vector of assigned values or NULL (if not constructed that way).
Definition bmbmatrix.h:451
bm::base_sparse_vector::slice
bvector_type_ptr slice(unsigned i) BMNOEXCEPT
get access to bit-plane as is (can return NULL)
Definition bmbmatrix.h:521
bm::base_sparse_vector::copy_from
void copy_from(const base_sparse_vector< Val, BV, MAX_SIZE > &bsv)
Definition bmbmatrix.h:1663
bm::base_sparse_vector::s2u
static unsigned_value_type s2u(value_type v) BMNOEXCEPT
Convert signed value type to unsigned representation.
Definition bmbmatrix.h:2087
bm::base_sparse_vector::allocation_policy_type
bvector_type::allocation_policy allocation_policy_type
Definition bmbmatrix.h:372
bm::base_sparse_vector::set_allocator_pool
void set_allocator_pool(allocator_pool_type *pool_ptr) BMNOEXCEPT
Set allocation pool.
Definition bmbmatrix.h:468
bm::base_sparse_vector::clear_range
void clear_range(size_type left, size_type right, bool set_null)
Definition bmbmatrix.h:1776
bm::base_sparse_vector::get_create_slice
bvector_type_ptr get_create_slice(unsigned i)
get access to bit-plain, function checks and creates a plane
Definition bmbmatrix.h:1851
bm::base_sparse_vector::size
size_type size() const BMNOEXCEPT
Definition bmbmatrix.h:402
bm::base_sparse_vector::base_sparse_vector
base_sparse_vector(const base_sparse_vector< Val, BV, MAX_SIZE > &bsv)
Definition bmbmatrix.h:1652
bm::base_sparse_vector< Val, BV, 1 >::empty
bool empty() const BMNOEXCEPT
Definition bmbmatrix.h:417
bm::base_sparse_vector::free_slice
void free_slice(unsigned i)
free memory in bit-plane
Definition bmbmatrix.h:536
bm::base_sparse_vector::optimize_block
void optimize_block(block_idx_type nb, typename BV::optmode opt_mode)
plane index for the "NOT NULL" flags plane
Definition bmbmatrix.h:685
bm::base_sparse_vector< Val, BV, 1 >::effective_slices_
unsigned effective_slices_
Definition bmbmatrix.h:704
bm::base_sparse_vector< Val, BV, 1 >::bmatr_
bmatrix_type bmatr_
Definition bmbmatrix.h:701
bm::base_sparse_vector::erase_column
void erase_column(size_type idx, bool erase_null)
Definition bmbmatrix.h:1952
bm::base_sparse_vector::allocator_pool_type
allocator_type::allocator_pool_type allocator_pool_type
Definition bmbmatrix.h:374
bm::base_sparse_vector::base_sparse_vector
base_sparse_vector(bm::null_support null_able, bool is_dynamic, allocation_policy_type ap=allocation_policy_type(), size_type bv_max_size=bm::id_max, const allocator_type &alloc=allocator_type())
Definition bmbmatrix.h:1632
bm::base_sparse_vector::swap_elements
void swap_elements(size_type idx1, size_type idx2)
swap two vector elements
Definition bmbmatrix.h:420
bm::base_sparse_vector< Val, BV, 1 >::is_ro_
bool is_ro_
Definition bmbmatrix.h:705
bm::base_sparse_vector::get_allocator_pool
allocator_pool_type * get_allocator_pool() const BMNOEXCEPT
Get allocation pool.
Definition bmbmatrix.h:474
bm::base_sparse_vector< Val, BV, 1 >::copy_range_slices
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)
bm::base_sparse_vector::base_sparse_vector
base_sparse_vector(base_sparse_vector< Val, BV, MAX_SIZE > &&bsv) BMNOEXCEPT
Definition bmbmatrix.h:391
bm::base_sparse_vector::get_slice_mask
bm::id64_t get_slice_mask(unsigned element_idx) const BMNOEXCEPT
Definition bmbmatrix.h:1870
bm::base_sparse_vector::stored_slices
static unsigned stored_slices() BMNOEXCEPT
Number of stored bit-planes (value planes + extra.
Definition bmbmatrix.h:508
bm::base_sparse_vector::value_bits
static constexpr unsigned value_bits() BMNOEXCEPT
Number of total bit-planes in the value type.
Definition bmbmatrix.h:678
bm::base_sparse_vector::is_null
bool is_null(size_type idx) const BMNOEXCEPT
test if specified element is NULL
Definition bmbmatrix.h:1830
bm::base_sparse_vector< Val, BV, 1 >::size_
size_type size_
Definition bmbmatrix.h:703
bm::base_sparse_vector::bit_and_rows
void bit_and_rows(const bvector_type &bv)
Set AND (intersect) operation on all existing bit-slices.
Definition bmbmatrix.h:672
bm::base_sparse_vector::base_sparse_vector
base_sparse_vector()
Definition bmbmatrix.h:1625
bm::base_sparse_vector::keep_range_no_check
void keep_range_no_check(size_type left, size_type right, bm::null_support slice_null)
Definition bmbmatrix.h:1798
bm::base_sparse_vector::unsigned_value_type
std::make_unsigned< value_type >::type unsigned_value_type
Definition bmbmatrix.h:376
bm::base_sparse_vector::get_bmatrix
const bmatrix_type & get_bmatrix() const BMNOEXCEPT
Definition bmbmatrix.h:553
bm::base_sparse_vector::get_null_bvect
bvector_type * get_null_bvect() BMNOEXCEPT
Definition bmbmatrix.h:525
bm::base_sparse_vector::mark_null_idx
void mark_null_idx(unsigned null_idx) BMNOEXCEPT
Set NULL plain index.
Definition bmbmatrix.h:565
bm::base_sparse_vector::slice
bvector_type_const_ptr slice(unsigned i) const BMNOEXCEPT
Definition bmbmatrix.h:522
bm::base_sparse_vector::size_type
BV::size_type size_type
Definition bmbmatrix.h:367
bm::base_sparse_vector::bvector_enumerator_type
bvector_type::enumerator bvector_enumerator_type
Definition bmbmatrix.h:373
bm::base_sparse_vector::sync_ro
void sync_ro() BMNOEXCEPT
Sybc read-only state.
Definition bmbmatrix.h:2030
bm::base_sparse_vector::bit_sub_rows
void bit_sub_rows(const bvector_type &bv, bool use_null)
Set SUB (MINUS) operation on all existing bit-slices.
Definition bmbmatrix.h:665
bm::base_sparse_vector::clear_all
void clear_all(bool free_mem=true) BMNOEXCEPT
resize to zero, free memory
Definition bmbmatrix.h:1759
bm::base_sparse_vector::bvector_type
BV bvector_type
Definition bmbmatrix.h:366
bm::base_sparse_vector::value_type
Val value_type
Definition bmbmatrix.h:365
bm::base_sparse_vector::get_bmatrix
bmatrix_type & get_bmatrix() BMNOEXCEPT
access to internal bit-matrix
Definition bmbmatrix.h:559
bm::base_sparse_vector::bmatrix_type
bm::basic_bmatrix< BV > bmatrix_type
Definition bmbmatrix.h:375
bm::base_sparse_vector::allocator_type
BV::allocator_type allocator_type
Definition bmbmatrix.h:371
bm::base_sparse_vector::is_signed
static constexpr bool is_signed() BMNOEXCEPT
returns true if value type is signed integral type
Definition bmbmatrix.h:433
bm::base_sparse_vector::optimize
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:1888
bm::base_sparse_vector::insert_null
void insert_null(size_type idx, bool not_null)
Definition bmbmatrix.h:1840
bm::base_sparse_vector::clear_value_planes_from
void clear_value_planes_from(unsigned plane_idx, size_type idx)
Definition bmbmatrix.h:1934
bm::base_sparse_vector::bit_planes
bit_planes
Definition bmbmatrix.h:355
bm::base_sparse_vector< Val, BV, 1 >::sv_slices
@ sv_slices
Definition bmbmatrix.h:356
bm::base_sparse_vector< Val, BV, 1 >::sv_value_slices
@ sv_value_slices
Definition bmbmatrix.h:357
bm::base_sparse_vector::calc_stat
void calc_stat(typename bvector_type::statistics *st) const BMNOEXCEPT
Calculates memory statistics.
Definition bmbmatrix.h:1918
bm::base_sparse_vector::is_nullable
bool is_nullable() const BMNOEXCEPT
check if container supports NULL(unassigned) values
Definition bmbmatrix.h:439
bm::base_sparse_vector::equal
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:1961
bm::base_sparse_vector::insert_clear_value_planes_from
void insert_clear_value_planes_from(unsigned plane_idx, size_type idx)
Definition bmbmatrix.h:1943
bm::base_sparse_vector::block_idx_type
bvector_type::block_idx_type block_idx_type
Definition bmbmatrix.h:675
bm::basic_bmatrix
Basic dense bit-matrix class.
Definition bmbmatrix.h:56
bm::basic_bmatrix::insert_octet
void insert_octet(size_type pos, size_type octet_idx, unsigned char octet)
Definition bmbmatrix.h:1232
bm::basic_bmatrix::insert_column
void insert_column(size_type idx, size_type row_from)
Definition bmbmatrix.h:848
bm::basic_bmatrix::block_idx_type
bvector_type::block_idx_type block_idx_type
Definition bmbmatrix.h:65
bm::basic_bmatrix::swap
void swap(basic_bmatrix< BV > &bbm) BMNOEXCEPT
Definition bmbmatrix.h:1024
bm::basic_bmatrix::~basic_bmatrix
~basic_bmatrix() BMNOEXCEPT
Definition bmbmatrix.h:734
bm::basic_bmatrix::bvector_type_ptr
bvector_type * bvector_type_ptr
Definition bmbmatrix.h:59
bm::basic_bmatrix::bv_rows_
bvector_type_ptr * bv_rows_
Definition bmbmatrix.h:337
bm::basic_bmatrix::alloc_
allocator_type alloc_
Definition bmbmatrix.h:333
bm::basic_bmatrix::swap_columns
void swap_columns(size_type idx1, size_type idx2)
Definition bmbmatrix.h:870
bm::basic_bmatrix::is_dynamic_
bool is_dynamic_
if rsize is dynamic (variable length)
Definition bmbmatrix.h:339
bm::basic_bmatrix::set_allocator_pool
void set_allocator_pool(allocator_pool_type *pool_ptr) BMNOEXCEPT
Definition bmbmatrix.h:965
bm::basic_bmatrix::set_null_idx
void set_null_idx(size_type null_idx) BMNOEXCEPT
set index of the NULL vector
Definition bmbmatrix.h:796
bm::basic_bmatrix::construct_row
bvector_type_ptr construct_row(size_type row)
Definition bmbmatrix.h:1055
bm::basic_bmatrix::bvector_type
BV bvector_type
Definition bmbmatrix.h:58
bm::basic_bmatrix::get_half_octet
unsigned get_half_octet(size_type pos, size_type row_idx) const BMNOEXCEPT
Definition bmbmatrix.h:1484
bm::basic_bmatrix::allocator_type
BV::allocator_type allocator_type
Definition bmbmatrix.h:61
bm::basic_bmatrix::allocation_policy_type
bvector_type::allocation_policy allocation_policy_type
Definition bmbmatrix.h:62
bm::basic_bmatrix::null_idx_
size_type null_idx_
Index of the NULL row.
Definition bmbmatrix.h:340
bm::basic_bmatrix::allocator_pool_type
allocator_type::allocator_pool_type allocator_pool_type
Definition bmbmatrix.h:63
bm::basic_bmatrix::get_null_idx
size_type get_null_idx() const BMNOEXCEPT
return index of the NULL vector
Definition bmbmatrix.h:162
bm::basic_bmatrix::destruct_row
void destruct_row(size_type row)
Definition bmbmatrix.h:1090
bm::basic_bmatrix::bvector_type_const_ptr
const bvector_type * bvector_type_const_ptr
Definition bmbmatrix.h:60
bm::basic_bmatrix::construct_bvector
bvector_type * construct_bvector(const bvector_type *bv) const
Definition bmbmatrix.h:1122
bm::basic_bmatrix::freeze
void freeze()
Definition bmbmatrix.h:1574
bm::basic_bmatrix::get_block
const bm::word_t * get_block(size_type p, unsigned i, unsigned j) const BMNOEXCEPT
Get low level internal access to.
Definition bmbmatrix.h:1169
bm::basic_bmatrix::bit_and_rows
void bit_and_rows(const bvector_type &bv)
Set AND (intersect) operation on all existing rows.
Definition bmbmatrix.h:1012
bm::basic_bmatrix::operator=
basic_bmatrix< BV > & operator=(const basic_bmatrix< BV > &bbm)
Definition bmbmatrix.h:82
bm::basic_bmatrix::calc_stat
void calc_stat(typename bvector_type::statistics &st, size_type rsize) const BMNOEXCEPT
Definition bmbmatrix.h:1584
bm::basic_bmatrix::compare_octet
int compare_octet(size_type pos, size_type octet_idx, char octet) const BMNOEXCEPT
Definition bmbmatrix.h:1445
bm::basic_bmatrix::rows_not_null
size_type rows_not_null() const BMNOEXCEPT
Definition bmbmatrix.h:143
bm::basic_bmatrix::rsize_
size_type rsize_
Definition bmbmatrix.h:338
bm::basic_bmatrix::pool_
allocator_pool_type * pool_
Definition bmbmatrix.h:335
bm::basic_bmatrix::get_allocator_pool
allocator_pool_type * get_allocator_pool() const BMNOEXCEPT
Definition bmbmatrix.h:106
bm::basic_bmatrix::copy_from
void copy_from(const basic_bmatrix< BV > &bbm)
Definition bmbmatrix.h:806
bm::basic_bmatrix::is_same_structure
bool is_same_structure(const basic_bmatrix< BV > &bbm) const BMNOEXCEPT
Debugging function to check if two matrixes have the same rows created.
Definition bmbmatrix.h:941
bm::basic_bmatrix::throw_bad_alloc
static void throw_bad_alloc()
Definition bmbmatrix.h:326
bm::basic_bmatrix::optimize
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:1547
bm::basic_bmatrix::clear_slices_range
void clear_slices_range(unsigned slice_from, unsigned slize_until, size_type idx)
Clear bit-planes bit.
Definition bmbmatrix.h:1180
bm::basic_bmatrix::octet_type
unsigned char octet_type
Definition bmbmatrix.h:66
bm::basic_bmatrix::clear_column
void clear_column(size_type idx, size_type row_from)
Definition bmbmatrix.h:859
bm::basic_bmatrix::bv_size_
size_type bv_size_
Definition bmbmatrix.h:332
bm::basic_bmatrix::clear_row
void clear_row(size_type row, bool free_mem)
Definition bmbmatrix.h:1103
bm::basic_bmatrix::is_dynamic
bool is_dynamic() const BMNOEXCEPT
Return if matrix is dynamic resizable.
Definition bmbmatrix.h:310
bm::basic_bmatrix::row
const bvector_type * row(size_type i) const BMNOEXCEPT
Definition bmbmatrix.h:767
bm::basic_bmatrix::allocate_rows
void allocate_rows(size_type rsize)
allocate matrix rows of bit-vectors (new rows are NULLs)
Definition bmbmatrix.h:880
bm::basic_bmatrix::optimize_block
void optimize_block(block_idx_type nb, typename BV::optmode opt_mode)
Definition bmbmatrix.h:1601
bm::basic_bmatrix::ap_
allocation_policy_type ap_
Definition bmbmatrix.h:334
bm::basic_bmatrix::rows
size_type rows() const BMNOEXCEPT
Definition bmbmatrix.h:140
bm::basic_bmatrix::destruct_bvector
void destruct_bvector(bvector_type *bv) const
Definition bmbmatrix.h:1155
bm::basic_bmatrix::calc_effective_rows_not_null
size_type calc_effective_rows_not_null() const BMNOEXCEPT
Definition bmbmatrix.h:981
bm::basic_bmatrix::set_octet
void set_octet(size_type pos, size_type octet_idx, unsigned char octet)
Definition bmbmatrix.h:1193
bm::basic_bmatrix::erase_column
void erase_column(size_type idx, bool erase_null)
Definition bmbmatrix.h:836
bm::basic_bmatrix::basic_bmatrix
basic_bmatrix(size_type rsize, bool is_dynamic=true, allocation_policy_type ap=allocation_policy_type(), size_type bv_max_size=bm::id_max, const allocator_type &alloc=allocator_type())
Definition bmbmatrix.h:718
bm::basic_bmatrix::bit_sub_rows
void bit_sub_rows(const bvector_type &bv, bool use_null)
Set SUB (MINUS) operation on all existing rows.
Definition bmbmatrix.h:999
bm::basic_bmatrix::octet_size
size_type octet_size() const BMNOEXCEPT
Definition bmbmatrix.h:913
bm::basic_bmatrix::free_rows
void free_rows() BMNOEXCEPT
Free all rows.
Definition bmbmatrix.h:923
bm::basic_bmatrix::base_sparse_vector
friend class base_sparse_vector
Definition bmbmatrix.h:329
bm::basic_bmatrix::get_octet
unsigned char get_octet(size_type pos, size_type octet_idx) const BMNOEXCEPT
Definition bmbmatrix.h:1295
bm::basic_bmatrix::size_type
bvector_type::size_type size_type
Definition bmbmatrix.h:64
bm::basic_bmatrix::get_row
bvector_type_const_ptr get_row(size_type i) const BMNOEXCEPT
Definition bmbmatrix.h:777
bm::bvector::enumerator
Constant iterator designed to enumerate "ON" bits.
Definition bm.h:603
bm::size_type
bm::bvector::optmode
optmode
Optimization mode Every next level means additional checks (better compression vs time).
Definition bm.h:133
bm::bvector::opt_compress
@ opt_compress
compress blocks when possible (GAP/prefix sum)
Definition bm.h:137
bm::bvector::blocks_manager_type
blocks_manager< Alloc > blocks_manager_type
Definition bm.h:119
bm::bvector::size_type
bvector_size_type size_type
Definition bm.h:121
bm::bvector::init
void init()
Explicit post-construction initialization. Must be caled to make sure safe use of *_no_check() method...
Definition bm.h:2280
bm::bvector::copy_range
void copy_range(const bvector< Alloc > &bvect, size_type left, size_type right)
Copy all bits in the specified closed interval [left,right].
Definition bm.h:7981
bm::bvector::block_idx_type
blocks_manager_type::block_idx_type block_idx_type
Definition bm.h:120
bm::null_support
null_support
NULL-able value support.
Definition bmconst.h:229
bm::use_null
@ use_null
support "non-assigned" or "NULL" logic
Definition bmconst.h:230
bm::no_null
@ no_null
do not support NULL values
Definition bmconst.h:231
bm::gap_test_unr
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:1833
bm
Definition bm.h:78
bm::id_max
const unsigned id_max
Definition bmconst.h:109
bm::word_t
unsigned int word_t
Definition bmconst.h:39
bm::test_4bits
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.
Definition bmbmatrix.h:1472
bm::set_block_mask
const unsigned set_block_mask
Definition bmconst.h:57
bm::get_block_coord
BMFORCEINLINE void get_block_coord(BI_TYPE nb, unsigned &i, unsigned &j) BMNOEXCEPT
Recalc linear bvector block index into 2D matrix coordinates.
Definition bmfunc.h:180
bm::check_any_fullb
bool check_any_fullb(const bm::word_t *blka[8], const bm::word_t *FBADDR)
Definition bmbmatrix.h:1279
bm::set_word_shift
const unsigned set_word_shift
Definition bmconst.h:72
bm::xor_swap
BMFORCEINLINE void xor_swap(W &x, W &y) BMNOEXCEPT
XOR swap two variables.
Definition bmutil.h:534
bm::id64_t
unsigned long long int id64_t
Definition bmconst.h:35
bm::set_block_shift
const unsigned set_block_shift
Definition bmconst.h:56
bm::set_word_mask
const unsigned set_word_mask
Definition bmconst.h:73
bm::test_4gaps
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.
Definition bmbmatrix.h:1460
bm::bv_statistics::reset
void reset() BMNOEXCEPT
Reset statisctics.
Definition bmfunc.h:94
bm::bv_statistics::add
void add(const bv_statistics &st) BMNOEXCEPT
Sum data from another sttructure.
Definition bmfunc.h:103
bm::bvector::allocation_policy
memory allocation policy
Definition bm.h:805
bm::bvector::statistics
Statistical information about bitset's memory allocation details.
Definition bm.h:125
construct_bvector
static TBVector * construct_bvector()
Definition xsample01.cpp:101
bvector_type
bm::bvector bvector_type
Definition xsample07a.cpp:94