search

simongog / sdsl-lite

Succinct Data Structure Library 2.0
Other
2.21k stars 350 forks source link

sd_array crash when 0 bits are set to 1 #288

Closed farruggia closed 8 years ago

farruggia commented 8 years ago

A crash occurs whenever a bit is accessed using operator[] on a sd_array with 0 bits set to 1.

Example code:

  sdsl::sd_vector_builder bd(10, 0);
  sdsl::sd_vector<> sd(bd);
  for (auto i = 0U; i < 10; ++i) {
    sd[i];
  }

which results in the following assertion error when building in debug mode:

sdsl/select_support_mcl.hpp:349: sdsl::select_support::size_type sdsl::select_support_mcl<t_bit_pattern, t_pattern_len>::select(sdsl::select_support::size_type) const [with unsigned char t_b = 0u; unsigned char t_pat_len = 1u; sdsl::select_support::size_type = long unsigned int]: Assertion `i > 0 and i <= m_arg_cnt' failed.

the problem does not occur when even just one bit, in any position, is set to 1.

jltsiren commented 8 years ago

I guess that removing the line

    if(m_capacity == 0) { return; }

from the constructor of sd_vector_builder should help. It looks like the general case will work with no 1-bits after all.

farruggia commented 8 years ago

I just patched sd_vector.cpp as you propose and it seems that the bug is now gone (tested access + iteration + rank queries).