1 #ifndef BMSPARSEVEC_UTIL_H__INCLUDED__ 2 #define BMSPARSEVEC_UTIL_H__INCLUDED__ 24 #ifndef BM__H__INCLUDED__ 27 # error missing include (bm.h or bm64.h) 58 if (
this != &addr_res)
60 addr_bv_ = addr_res.addr_bv_;
61 in_sync_ = addr_res.in_sync_;
64 rs_index_->copy_from(*addr_res.rs_index_);
85 bool resolve(size_type id_from, size_type* id_to)
const;
97 bool get(size_type id_from, size_type* id_to)
const;
102 void set(size_type id_from);
156 bvector_type addr_bv_;
157 rs_index_type* rs_index_;
187 bool resolve(size_type id_from, size_type* id_to)
const;
197 bool get(size_type id_from, size_type* id_to)
const;
202 void set(size_type id_from);
215 bvector_type set_flags_bv_;
216 sparse_vector_type addr_sv_;
225 template<
class Value,
class BV>
249 bool push_back(key_type key,
const value_type& val);
254 const value_type& at(key_type key)
const;
259 value_type& at(key_type key);
271 bool resolve(key_type key, address_type* addr)
const;
275 const value_type&
get(address_type addr)
const;
279 const address_resolver_type&
resolver()
const {
return addr_res_; }
283 address_resolver_type&
resolver() {
return addr_res_; }
287 size_t size()
const {
return dense_vect_.size(); }
299 void throw_range_error(
const char* err_msg)
const;
332 bool added = this->push_back(key, buffer_type());
335 buffer_type& buf = this->at(key);
348 typename BV::statistics bv_st;
349 const BV& addr_bv = this->addr_res_.get_bvector();
350 addr_bv.calc_stat(&bv_st);
355 for (
size_t i = 0; i < this->dense_vect_.size(); ++i)
357 const buffer_type& buf = this->dense_vect_.at(i);
363 size_t h_size = 2 + 1 + ((this->dense_vect_.size()+1) * 8);
380 : rs_index_(0), in_sync_(false)
383 construct_rs_index();
403 rs_index_ =
new(rs_index_) rs_index_type();
413 rs_index_->~rs_index();
423 : addr_bv_(addr_res.addr_bv_),
424 in_sync_(addr_res.in_sync_)
427 construct_rs_index();
431 rs_index_->copy_from(*addr_res.rs_index_);
442 if (
this != &addr_res)
444 addr_bv_.move_from(addr_res.addr_bv_);
445 in_sync_ = addr_res.in_sync_;
449 rs_index_ = addr_res.rs_index_;
450 addr_res.rs_index_ = 0;
455 rs_index_ = 0; in_sync_ =
false;
467 *id_to = addr_bv_.count_to_test(id_from, *rs_index_);
471 bool found = addr_bv_.test(id_from);
478 *id_to = addr_bv_.count_range(0, id_from);
481 return (
bool) *id_to;
492 *id_to = addr_bv_.count_to_test(id_from, *rs_index_);
504 addr_bv_.set(id_from);
514 if (in_sync_ && force ==
false)
517 addr_bv_.build_rs_index(rs_index_);
534 int cmp = addr_bv_.compare(addr_res.addr_bv_);
548 set_flags_bv_.init();
555 : set_flags_bv_(addr_res.set_flags_bv_),
556 addr_sv_(addr_res.addr_sv_),
557 max_addr_(addr_res.max_addr_)
568 bool found = set_flags_bv_.test(id_from);
569 *id_to = found ? addr_sv_.at(id_from) : 0;
578 bool found = set_flags_bv_.test(id_from);
581 set_flags_bv_.set(id_from);
583 addr_sv_.set(id_from, max_addr_);
592 set_flags_bv_.optimize(temp_block);
593 addr_sv_.optimize(temp_block);
599 template<
class Value,
class BV>
607 template<
class Value,
class BV>
610 if (dense_vect_.empty())
614 if (key <= last_add_)
621 dense_vect_.push_back(val);
628 template<
class Value,
class BV>
636 template<
class Value,
class BV>
644 template<
class Value,
class BV>
648 bool found = addr_res_.
resolve(key, addr);
656 template<
class Value,
class BV>
660 return dense_vect_.
at(addr);
665 template<
class Value,
class BV>
670 bool found = addr_res_.
resolve(key, &idx);
673 throw_range_error(
"compressed collection item not found");
680 template<
class Value,
class BV>
685 bool found = addr_res_.
resolve(key, &idx);
688 throw_range_error(
"compressed collection item not found");
690 return dense_vect_.at(idx-1);
696 template<
class Value,
class BV>
700 throw std::range_error(err_msg);
708 template<
class Value,
class BV>
715 int cmp = bv.compare(bva);
719 for (
size_t i = 0; i < dense_vect_.size(); ++i)
bool in_sync() const
returns true if prefix sum table is in sync with the vector
bvector_type::rs_index_type rs_index_type
void optimize(bm::word_t *temp_block=0)
optimize underlying bit-vector
void set(size_type id_from)
Set id (bit) to address resolver.
address_resolver_type & resolver()
Get address resolver.
rs_index< allocator_type > rs_index_type
void * aligned_new_malloc(size_t size)
Aligned malloc (unlike classic malloc it throws bad_alloc exception)
const bvector_type & get_bvector() const
Get const reference to the underlying bit-vector of set values.
bool resolve(size_type id_from, size_type *id_to) const
Resolve id to integer id (address)
bvector_type & get_bvector()
Get writable reference to the underlying bit-vector.
void optimize(bm::word_t *temp_block=0)
optimize underlying sparse vectors
Bit-bector prefix sum address resolver using bit-vector prefix sum as a space compactor.
compressed_collection< typename serializer< BV >::buffer, BV > parent_type
pre-processor un-defines to avoid global space pollution (internal)
container_type & container()
return dense container for direct access (this should be treated as an internal function designed for...
void unsync()
Unsync the prefix sum table.
serializer< BV >::buffer buffer_type
const value_type & at(key_type key) const
find and return const associated value (with bounds/presense checking)
void aligned_free(void *ptr)
Aligned free.
bool resolve(size_type id_from, size_type *id_to) const
Resolve id to integer id (address)
size_t size() const
size of collection
void sync(bool force=false)
Re-calculate prefix sum table (same as calc_prefix_sum)
void calc_stat(statistics *st) const
compute statistics on memory consumption
std::vector< value_type > container_type
const address_resolver_type & resolver() const
Get address resolver.
container_type dense_vect_
compressed space container
SV::bvector_type bvector_type
const bvector_type & get_bvector() const
Get const reference to the underlying bit-vector.
#define BM_ASSERT_THROW(x, xerrcode)
bool resolve(key_type key, address_type *addr) const
Resolve key address (index) in the dense vector.
bool move_buffer(typename parent_type::key_type key, buffer_type &buffer)
move external buffer into collection
bvector_type::size_type size_type
size_t memory_used
total capacity
Serialization / compression of bvector<>. Set theoretical operations on compressed BLOBs...
address_resolver_type addr_res_
address resolver
Compressed (sparse collection of objects)
void move_from(bvps_addr_resolver &addr_res) BMNOEXEPT
Move content from the argument address resolver.
size_t max_serialize_mem
memory needed for serialization
bool equal(const bvps_addr_resolver &addr_res) const
equality comparison
key_type last_add_
last added element
bvps_addr_resolver & operator=(const bvps_addr_resolver &addr_res)
Compressed (sparse collection of objects)
byte_buffer< allocator_type > buffer
void construct_rs_index()
void sync()
Checkpoint method to prepare collection for reading.
void optimize(bm::word_t *temp_block=0)
perform memory optimizations/compression
void calc_prefix_sum(bool force=false)
Re-calculate prefix sum table.
bm::bvps_addr_resolver< bvector_type > address_resolver_type
sparse vector based address resolver (no space compactor, just bit-plane compressors provided by spar...