sample26.cpp

Immutable bit-vectors.

Immutable bit-vectors.This example generates sparse bit-vectors and shows how to make them use less memory via optimization (after optimization bit-vector remains mutable) and freezing it into immutable, where memory all edit reservations are getting dropped. Freezing also allocates memory blocks together, reducing the heap fragmentation.

See also
  bm::bvector::optimize
  bm::bvector::freeze
  bm::bvector::is_ro

/*
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
*/
/** \example sample26.cpp
Immutable bit-vectors.
This example generates sparse bit-vectors and shows how to make them use less memory
via optimization (after optimization bit-vector remains mutable) and freezing it into immutable,
where memory all edit reservations are getting dropped.
Freezing also allocates memory blocks together, reducing the heap fragmentation.
\sa bm::bvector::optimize
\sa bm::bvector::freeze
\sa bm::bvector::is_ro
*/
/*! \file sample26.cpp
\brief Example: bvector<> with immutability (read-only)
*/
#include <stdlib.h>
#include <iostream>
#include <cassert>
#include "bm.h"
#include "bmundef.h" /* clear the pre-proc defines from BM */
using namespace std;
const unsigned MAX_VALUE = 1000000;
/// Fill bit-vectors with values using dense and sparse distrubutions
///
static
void fill_bvector(bm::bvector<>* bv1, bm::bvector<>* bv2)
{
const unsigned fill_factor1 = 2500;
const unsigned fill_factor2 = 150;
for (unsigned i = 0; i < MAX_VALUE; ++i)
if (unsigned(rand()) % fill_factor1)
bv1->set(i);
for (unsigned i = 0; i < MAX_VALUE; i+=fill_factor2)
bv2->set(i);
}
static
void print_statistics(const bm::bvector<>& bv)
{
bm::bvector<>::statistics st;
bv.calc_stat(&st);
cout << "Bit blocks :" << st.bit_blocks << endl;
cout << "GAP blocks :" << st.gap_blocks << endl;
cout << "Memory used :" << st.memory_used << endl;
cout << "Memory overhead :" << st.gap_cap_overhead << endl;
cout << "Max.serialize mem :" << st.max_serialize_mem << endl << endl;;
}
int main(void)
{
try
{
bm::bvector<> bv1;
bm::bvector<> bv2;
fill_bvector(&bv1, &bv2); // Fill bvectors (dense and sparse)
cout << "Statistics before memory optimization" << endl;
cout << "-------------------------------------" << endl << endl;
print_statistics(bv1);
print_statistics(bv2);
{
// optimization scratch buffer on stack to avoid dynamic allocation
BM_DECLARE_TEMP_BLOCK(tb)
bv1.optimize(tb);
bv2.optimize(tb);
}
cout << "Statistics after memory optimization" << endl;
cout << "-------------------------------------" << endl;
print_statistics(bv1);
print_statistics(bv2);
// two ways to turn vector read-only:
// 1. construct a new vector as a READ_ONLY copy (drop the old one)
// 2. Use bm::bvector<>::freeze()
bm::bvector<> bv1_ro(bv1, bm::finalization::READONLY);
assert(bv1_ro.is_ro());
bv2.freeze();
cout << bv2.is_ro() << endl; // 1 - yes it is now READ_ONLY
cout << "Statistics after freezing" << endl;
cout << "-------------------------------------" << endl;
print_statistics(bv1_ro);
print_statistics(bv2);
// interface-wise, immutable bit-vectors remain just the same bvector<>
// bit you CANNOT call non-cost modification functions on it
// (it would be undefined behavior) don't shoot yourself in the leg
//
// READ-ONLY status is preserved over the copy construction and
// assignment
{
// copy construct of RO bit-vector (result is read-only vector vector)
bm::bvector<> bv11(bv1_ro);
assert(bv11.is_ro());
bool eq = bv11.equal(bv1_ro);
assert(eq); (void) eq;
}
// if you can rewet it back here is how to do it
// construct bv11 as READ-WRITE from READONLY
{
assert(bv2.is_ro()); // bv2 is immutable
bm::bvector<> bv21(bv2, bm::finalization::READWRITE);
bv2.swap(bv21);
assert(!bv2.is_ro()); // bv2 is now a mutable vector again
bv2.set(0); // we can do chnage operations at this point
}
}
catch(std::exception& ex)
{
std::cerr << ex.what() << std::endl;
}
return 0;
}
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
bmundef.h
pre-processor un-defines to avoid global space pollution (internal)
bm::bvector
Bitvector Bit-vector container with runtime compression of bits.
Definition bm.h:115
bm::bvector::set
bvector< Alloc > & set(size_type n, bool val=true)
Sets bit n if val is true, clears bit n if val is false.
Definition bm.h:4188
bm::bvector::optimize
void optimize(bm::word_t *temp_block=0, optmode opt_mode=opt_compress, statistics *stat=0)
Optimize memory bitvector's memory allocation.
Definition bm.h:3635
bm::bvector::swap
void swap(bvector< Alloc > &bvect) BMNOEXCEPT
Exchanges content of bv and this bvector.
Definition bm.h:3966
bm::bvector::freeze
void freeze()
Turn current vector to read-only (immutable vector).
Definition bm.h:8058
bm::bvector::is_ro
bool is_ro() const BMNOEXCEPT
Returns true if vector is read-only.
Definition bm.h:1060
bm::bvector::calc_stat
void calc_stat(struct bm::bvector< Alloc >::statistics *st) const BMNOEXCEPT
Calculates bitvector statistics.
Definition bm.h:3978
bm::finalization::READWRITE
@ READWRITE
mutable (read-write object)
Definition bmconst.h:159
bm::finalization::READONLY
@ READONLY
immutable (read-only object)
Definition bmconst.h:158
main
int main(void)
Definition sample1.cpp:43
print_statistics
static void print_statistics(const bm::bvector<> &bv)
Definition sample3.cpp:61
fill_bvector
static void fill_bvector(bm::bvector<> *bv1, bm::bvector<> *bv2)
Definition sample3.cpp:48
MAX_VALUE
const unsigned MAX_VALUE
Definition sample3.cpp:42
bm::bv_statistics::gap_cap_overhead
size_t gap_cap_overhead
gap memory overhead between length and capacity
Definition bmfunc.h:63
bm::bv_statistics::gap_blocks
size_t gap_blocks
Number of GAP blocks.
Definition bmfunc.h:58
bm::bv_statistics::bit_blocks
size_t bit_blocks
Number of bit blocks.
Definition bmfunc.h:57
bm::bv_statistics::max_serialize_mem
size_t max_serialize_mem
estimated maximum memory for serialization
Definition bmfunc.h:61
bm::bv_statistics::memory_used
size_t memory_used
memory usage for all blocks and service tables
Definition bmfunc.h:62
bm::bvector::statistics
Statistical information about bitset's memory allocation details.
Definition bm.h:125