| 77 | } |
| 78 | |
| 79 | inline uint64_t select(bit_vector const& bv, uint64_t idx) const |
| 80 | { |
| 81 | assert(idx < num_positions()); |
| 82 | uint64_t block = idx / block_size; |
| 83 | int64_t block_pos = m_block_inventory[block]; |
| 84 | if (block_pos < 0) { |
| 85 | uint64_t overflow_pos = uint64_t(-block_pos - 1); |
| 86 | return m_overflow_positions[overflow_pos + (idx % block_size)]; |
| 87 | } |
| 88 | |
| 89 | uint64_t subblock = idx / subblock_size; |
| 90 | uint64_t start_pos = uint64_t(block_pos) + m_subblock_inventory[subblock]; |
| 91 | uint64_t reminder = idx % subblock_size; |
| 92 | mapper::mappable_vector<uint64_t> const& data = bv.data(); |
| 93 | |
| 94 | if (!reminder) { |
| 95 | return start_pos; |
| 96 | } else { |
| 97 | uint64_t word_idx = start_pos / 64; |
| 98 | uint64_t word_shift = start_pos % 64; |
| 99 | uint64_t word = WordGetter()(data, word_idx) & (uint64_t(-1) << word_shift); |
| 100 | |
| 101 | while (true) { |
| 102 | uint64_t popcnt = broadword::popcount(word); |
| 103 | if (reminder < popcnt) break; |
| 104 | reminder -= popcnt; |
| 105 | word = WordGetter()(data, ++word_idx); |
| 106 | } |
| 107 | |
| 108 | return 64 * word_idx + broadword::select_in_word(word, reminder); |
| 109 | } |
| 110 | } |
| 111 | |
| 112 | inline uint64_t num_positions() const { |
| 113 | return m_positions; |