nicola-gigante / bitvector Goto Github PK

The following code violates an assertion in the access() function:

ulint M=4096;
bitvector_t<2048, alloc_on_demand> bv_Btree(M,256);

cout << "Insert ... "<< flush;

for(ulint i=0;i<M;i++)
    bv_Btree.insert(i,0);

cout << "done."<< endl;

cout << "access ... "<< flush;

for(ulint i=0;i<M;i++)
    bv_Btree.access(i);

cout << "done."<< endl;

Failed assertion:

test: ../../data_structures/../common/../extern/bitvector/include/internal/bitvector.hpp:303: bv::internal::bt_impl<, >::subtree_ref_base bv::internal::bt_impl<, >::subtree_ref_base::child(size_t) const [with bool Const = true; long unsigned int W = 2048ul; bv::allocation_policy_t AP = (bv::allocation_policy_t)0u; size_t = long unsigned int]: Assertion `pointers(k) != 0' failed.

When calling size() of a packed_view object, the returned value is not the same as specified in the constructor. Example:

 ulint n=1000;
 auto pv =  packed_view<vector>(3,n);
 cout << pv.size() << endl;

 n=999999;
 pv =  packed_view<vector>(3,n);
 cout << pv.size() << endl;

output:

1002
1000000

bitvector produces a failed assertion in the DNA aligner ERNE (while constructing the data structure) if the code is compiled using gcc 4.7.1:

erne-create: BWTIL/data_structures/../
common/../extern/bitvector/include/internal/bitvector.hpp:342: std::pair<long unsigned int, long unsigned int> bv::internal::bt_impl<, >::subtree_ref_base::find_insert_point(size_t) const [with bool Const = true; long unsigned int W = 2048ul; bv::allocation_policy_t AP = (bv::allocation_policy_t)0u; size_t = long unsigned int]: Assertion `is_node()' failed.

To reproduce, download ERNE code from https://svn.code.sf.net/p/erne/code/trunk/ (boost required), then configure and compile with gcc 4.7.1. The command that produces the error is

erne-create --fasta vitis.fasta --out structure_name

where "vitis.fasta" is the vitis vinifera genome. The assertion fails at 0% of the construction so it is likely that the problem will occur also with any other input.

Other notes: the program terminates successfully if ERNE is compiled with gcc 4.8+

for some sizes, bitview doesn't allocate enough memory (as required in the constructor). example:

 ulint n = 3137161265;
 auto bv = bitview<vector>(n);

 cout << "n = " << n <<endl;
 cout << "bitview size = " << bv.size() << endl;

returns

n = 3137161265
bitview size = 3137161216

I couldn't reproduce this error outside my program cw-bwt. While inserting bits in a bitvector, an assertion fails. To reproduce the error:

git clone --recursive https://github.com/nicolaprezza/BWTIL
cd BWTIL
ASSERTS=yes CXX=g++ make cw-bwt
./cw-bwt data/plain/english.1MB data/bwt/english.1MB.bwt

Depending on wether cw-bwt is compiled with g++ or clang++, the failed assert is different:

cw-bwt: tools/cw-bwt/../../algorithms/../common/../extern/bitvector/include/internal/bits.h:177: bool bv::internal::ensure_bitsize(T, size_t) [with T = long unsigned int; = void; size_t = long unsigned int]: Assertion `lowbits(value, width) == value' failed.
Aborted (core dumped)

for g++, and

cw-bwt: extern/bitvector/include/internal/bitvector.hpp:303: subtree_ref_base bv::internal::bt_impl<2048, 0>::subtree_ref_base::child(size_t) const [Const = true]: Assertion `pointers(k) != 0' failed.

for clang++

I can use rank but how can I use select?

apparently, everyone in his life implemented at least once a header starting with "#ifndef BITVECTOR_H #define BITVECTOR_H", with obvious consequences for poor people wishing to use multiple submodules.

could you please kindly rename your definition to something else? in exchange, I'll offer you a beer.