| 46 | // https://github.com/jermp/pthash/blob/master/include/encoders/darray.hpp |
| 47 | struct darray1_view { |
| 48 | inline uint64_t select(const bit_vector_view& bv, uint64_t idx) const { |
| 49 | assert(idx < m_positions); |
| 50 | uint64_t block = idx / block_size; |
| 51 | int64_t block_pos = m_block_inventory[block]; |
| 52 | if (block_pos < 0) { // sparse super-block |
| 53 | uint64_t overflow_pos = uint64_t(-block_pos - 1); |
| 54 | return m_overflow_positions[overflow_pos + (idx & (block_size - 1))]; |
| 55 | } |
| 56 | |
| 57 | size_t subblock = idx / subblock_size; |
| 58 | size_t start_pos = uint64_t(block_pos) + m_subblock_inventory[subblock]; |
| 59 | size_t reminder = idx & (subblock_size - 1); |
| 60 | if (!reminder) { |
| 61 | return start_pos; |
| 62 | } |
| 63 | |
| 64 | const uint64_t* data = bv.data(); |
| 65 | size_t word_idx = start_pos >> 6; |
| 66 | size_t word_shift = start_pos & 63; |
| 67 | uint64_t word = data[word_idx] & (uint64_t(-1) << word_shift); |
| 68 | |
| 69 | while (true) { |
| 70 | size_t popcnt = pthash::util::popcount(word); |
| 71 | if (reminder < popcnt) { |
| 72 | break; |
| 73 | } |
| 74 | reminder -= popcnt; |
| 75 | word = data[++word_idx]; |
| 76 | } |
| 77 | |
| 78 | return (word_idx << 6) + pthash::util::select_in_word(word, reminder); |
| 79 | } |
| 80 | |
| 81 | template <typename Loader> |
| 82 | void load(Loader& loader) { |