118 for (
typename TM::iterator it = id_map.begin();
122 typename TM::mapped_type mp = it->second;
180 void get_vector(
unsigned id, std::vector<unsigned>& vect)
const;
190 map_type::const_iterator it =
idx_.find(
id);
191 if (it !=
idx_.end())
194 vect.resize(vaddr.
size+1);
196 for (
unsigned j = 1; j < vect.size(); ++j)
199 a += (vect[j-1] + 1);
221 unsigned method = rand() % 5;
224 unsigned seed_id = unsigned(rand()) %
max_size;
235 unsigned seed_id = unsigned(rand()) %
max_size;
236 unsigned id = seed_id;
251 unsigned id = unsigned(rand()) %
max_size;
273 std::cerr <<
"Warning. Empty vector generated!" << std::endl;
276 bvi.
idx_[i] = ap.release();
285 size_t mem_total = 0;
286 for (bv_index::map_type::const_iterator it = bvi.
idx_.begin();
287 it != bvi.
idx_.end();
296 mem_total +=
sizeof(
void*);
307 size_t mem_total = 0;
308 std::vector<unsigned char> buf;
319 for (bv_index::map_type::const_iterator it = bvi.
idx_.begin();
320 it != bvi.
idx_.end();
323 unsigned id = it->first;
338 vbuf.resize(bvs_size);
339 ::memcpy(vbuf.data(), buf.data(), bvs_size);
341 mem_total += bvs_size;
343 mem_total +=
sizeof(std::vector<unsigned char>::size_type);
354 throw std::runtime_error(
"deserialization check failed");
369 size_t mem_total = 0;
371 for (bv_index::map_type::const_iterator it = bvi.
idx_.begin();
372 it != bvi.
idx_.end();
375 unsigned id = it->first;
378 unsigned count = bvp->
count();
389 sizeof(vect_index::buffer_type::value_type) * vect.size() +
390 sizeof(vect_index::buffer_type::size_type);
410 for (
size_t k = vect.size()-1; k >= 1; --k)
412 vect[k] -= vect[k-1];
423 size_t mem_total = 0;
425 std::vector<unsigned> vect;
429 for (bv_index::map_type::const_iterator it = bvi.
idx_.begin();
430 it != bvi.
idx_.end();
433 unsigned id = it->first;
441 for (
unsigned k = 1; k < vect.size(); ++k)
445 delta_map.push_back(std::make_pair(sum,
id));
452 std::sort(delta_map.begin(), delta_map.end());
453 if (delta_map.size() != bvi.
idx_.size())
455 throw std::runtime_error(
"delta map size is incorrect");
459 for (
unsigned j = 0; j < delta_map.size(); ++j)
461 unsigned id = delta_map[j].second;
463 bv_index::map_type::const_iterator it = bvi.
idx_.find(
id);
464 if (it == bvi.
idx_.end())
473 vaddr.
size = (unsigned)(vect.size() - 1);
480 sv_pos += vaddr.
size;
483 sv_idx.
idx_[id] = vaddr;
489 sparse_vect_index::sparse_vector_type::statistics st;
493 mem_total += st.memory_used;
495 mem_total += st.memory_used;
499 for (bv_index::map_type::const_iterator it = bvi.
idx_.begin();
500 it != bvi.
idx_.end();
503 unsigned id = it->first;
515 std::vector<unsigned> svect;
517 if (svect.size() != vect.size())
519 std::cerr <<
"Size check failed! id = " <<
id
520 <<
"size() = " << svect.size()
522 throw std::runtime_error(
"sparse vector content check failed");
525 for (
unsigned k = 0; k < vect.size(); ++k)
527 if (vect[k] != svect[k])
529 std::cerr <<
"SV content check failed! id = " <<
id
530 <<
" i=" << k << std::endl;
531 for (
unsigned h = 0; h < vect.size(); ++h)
533 std::cout <<
"[" << vect[h] <<
"=" << svect[h] <<
"], ";
535 std::cout << std::endl;
536 throw std::runtime_error(
"sparse vector content check failed");
562 for (bv_index::map_type::const_iterator it = bvi.
idx_.begin();
563 it != bvi.
idx_.end();
575 std::vector<unsigned> result_set;
581 result_set.resize(0);
586 bv_index::map_type::const_iterator it = bvi.
idx_.find(
id);
587 if (it == bvi.
idx_.end())
600 result_set.push_back(*en);
625 for (bvs_index::map_type::const_iterator it = bvs.
idx_.begin();
626 it != bvs.
idx_.end();
630 if (svect.size() == 0)
632 throw std::runtime_error(
"empty buffer error");
634 const unsigned char* buf = it->second.data();
644 std::vector<unsigned> result_set;
650 result_set.resize(0);
655 bvs_index::map_type::const_iterator it = bvs.
idx_.find(
id);
656 if (it == bvs.
idx_.end())
659 const unsigned char* buf = it->second.data();
670 result_set.push_back(*en);
685 for (vect_index::map_type::const_iterator it = vecti.
idx_.begin();
686 it != vecti.
idx_.end();
690 if (vect.size() == 0)
692 throw std::runtime_error(
"empty buffer error");
704 std::vector<unsigned> result_set;
710 result_set.resize(0);
715 vect_index::map_type::const_iterator it = vecti.
idx_.find(
id);
716 if (it == vecti.
idx_.end())
731 result_set.push_back(*en);
746 std::vector<unsigned> vect;
749 for (sparse_vect_index::map_type::const_iterator it = svi.
idx_.begin();
750 it != svi.
idx_.end();
753 unsigned id = it->first;
765 std::vector<unsigned> result_set;
771 result_set.resize(0);
777 if (vect.size() == 0)
790 result_set.push_back(*en);
814 size_t bv_mem_total_MB = bv_mem_total / (1024*1024);
816 std::cout <<
"bm::bvector<> memory footprint = "
817 << bv_mem_total <<
" (" << bv_mem_total_MB <<
"MB)"
821 size_t bvs_mem_total_MB = bvs_mem_total / (1024*1024);
823 std::cout <<
"bm::bvector<> BLOB memory footprint = "
824 << bvs_mem_total <<
" (" << bvs_mem_total_MB <<
"MB)"
828 size_t vecti_mem_total_MB = vecti_mem_total / (1024*1024);
830 std::cout <<
"std::vector<unsigned> memory footprint = "
831 << vecti_mem_total <<
" (" << vecti_mem_total_MB <<
"MB)"
835 size_t svi_mem_total_MB = svi_mem_total / (1024*1024);
837 std::cout <<
"bm::sparse_vector<> memory footprint = "
838 << svi_mem_total <<
" (" << svi_mem_total_MB <<
"MB)"
850 std::cout << std::endl <<
"Performance (ops/sec):" << std::endl;
856 catch(std::exception& ex)
858 std::cerr << ex.what() << std::endl;
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
#define BM_DECLARE_TEMP_BLOCK(x)
Algorithms for bvector<> (main include)
Serialization / compression of bvector<>. Set theoretical operations on compressed BLOBs.
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
Algorithms for bm::sparse_vector.
Serialization for sparse_vector<>
Timing utilities for benchmarking (internal)
pre-processor un-defines to avoid global space pollution (internal)
Constant iterator designed to enumerate "ON" bits.
bool valid() const BMNOEXCEPT
Checks if iterator is still valid.
Bitvector Bit-vector container with runtime compression of bits.
@ opt_compress
compress blocks when possible (GAP/prefix sum)
size_type count() const BMNOEXCEPT
population count (count of ON bits)
void resize(size_type new_size)
Change size of the bvector.
void optimize(bm::word_t *temp_block=0, optmode opt_mode=opt_compress, statistics *stat=0)
Optimize memory bitvector's memory allocation.
bool set_bit(size_type n, bool val=true)
Sets bit n.
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
enumerator end() const
Returns enumerator pointing on the next bit after the last.
void clear(const size_type *ids, size_type ids_size, bm::sort_order so=bm::BM_UNKNOWN)
clear list of bits in this bitset
int compare(const bvector< Alloc > &bvect) const BMNOEXCEPT
Lexicographical comparison with a bitvector.
void calc_stat(struct bm::bvector< Alloc >::statistics *st) const BMNOEXCEPT
Calculates bitvector statistics.
Utility class to collect performance measurements and statistics.
std::map< std::string, statistics > duration_map_type
test name to duration map
void add_repeats(unsigned inc)
static void print_duration_map(TOut &tout, const duration_map_type &dmap, format fmt=ct_time)
Deserializer, performs logical operations between bit-vector and serialized bit-vector.
size_type deserialize(bvector_type &bv, const unsigned char *buf, set_operation op, bool exit_on_one=false)
Deserialize bvector using buffer as set operation argument.
Bit-vector serialization class.
void gap_length_serialization(bool value) BMNOEXCEPT
Set GAP length serialization (serializes GAP levels of the original vector)
void set_compression_level(unsigned clevel) BMNOEXCEPT
Set compression level.
void byte_order_serialization(bool value) BMNOEXCEPT
Set byte-order serialization (for cross platform compatibility)
size_type serialize(const BV &bv, unsigned char *buf, size_t buf_size)
Bitvector serialization into memory block.
succinct sparse vector with runtime compression using bit-slicing / transposition method
value_type get(size_type idx) const BMNOEXCEPT
get specified element without bounds checking
void set(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
void import(const value_type *arr, size_type arr_size, size_type offset=0, bool set_not_null=true)
Import list of elements from a C-style array.
void optimize(bm::word_t *temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, typename sparse_vector< Val, BV >::statistics *stat=0)
run memory optimization for all vector planes
@ BM_GAP
GAP compression is ON.
size_t deserialize(BV &bv, const unsigned char *buf, bm::word_t *temp_block=0, const bm::bv_ref_vector< BV > *ref_vect=0)
Bitvector deserialization from a memory BLOB.
void combine_or(BV &bv, It first, It last)
OR Combine bitvector and the iterable sequence.
const unsigned gap_levels
unsigned short gap_word_t
size_t max_serialize_mem
estimated maximum memory for serialization
size_t memory_used
memory usage for all blocks and service tables
Statistical information about bitset's memory allocation details.
std::map< unsigned, TBVector * > map_type
std::map< unsigned, buffer_type > map_type
std::vector< unsigned char > buffer_type
static const bm::gap_word_t _len[bm::gap_levels]
sparse_vector_type sv_storage1_
bm::sparse_vector< unsigned, bm::bvector<> > sparse_vector_type
std::map< unsigned, vect_addr > map_type
std::vector< std::pair< uint64_t, unsigned > > delta_sum_map_type
void get_vector(unsigned id, std::vector< unsigned > &vect) const
sparse_vector_type sv_storage_
std::map< unsigned, buffer_type > map_type
std::vector< unsigned int > buffer_type
static void generate_random_vector(TBVector *bv)
static void generate_bv_index(bv_index &bvi)
const unsigned index_size
static void speed_test_vect_index(const vect_index &vecti)
const unsigned benchmark_ops
static TBVector * construct_bvector()
const unsigned bits_per_vect
static void speed_test_bv_index(const bv_index &bvi)
static size_t calc_memory_footprint(const bv_index &bvi)
static void bv2delta(const TBVector &bv, std::vector< unsigned > &vect)
static size_t convert_bv2bvs(const bv_index &bvi, bvs_index &bvs)
void destroy_map(TM &id_map)
const unsigned result_set_cnt
bm::chrono_taker ::duration_map_type timing_map
static void speed_test_sv_index(const sparse_vect_index &svi)
static size_t convert_bv2vect(const bv_index &bvi, vect_index &vidx)
const unsigned sample_cnt
static size_t convert_bv2sv(const bv_index &bvi, sparse_vect_index &sv_idx)
static void speed_test_bvs_index(const bvs_index &bvs)