| 101 | } |
| 102 | |
| 103 | size_t FeaturesOffsetsTable::GetFeatureIndexbyOffset(uint32_t offset) const |
| 104 | { |
| 105 | ASSERT_GREATER(size(), 0, ("We must not ask empty table")); |
| 106 | ASSERT_LESS_OR_EQUAL(offset, m_table.select(size() - 1), |
| 107 | ("Offset out of bounds", offset, m_table.select(size() - 1))); |
| 108 | ASSERT_GREATER_OR_EQUAL(offset, m_table.select(0), ("Offset out of bounds", offset, m_table.select(size() - 1))); |
| 109 | // Binary search in elias_fano list |
| 110 | size_t leftBound = 0, rightBound = size(); |
| 111 | while (leftBound + 1 < rightBound) |
| 112 | { |
| 113 | size_t middle = leftBound + (rightBound - leftBound) / 2; |
| 114 | if (m_table.select(middle) <= offset) |
| 115 | leftBound = middle; |
| 116 | else |
| 117 | rightBound = middle; |
| 118 | } |
| 119 | ASSERT_EQUAL(offset, m_table.select(leftBound), ("Can't find offset", offset, "in the table")); |
| 120 | return leftBound; |
| 121 | } |
| 122 | |
| 123 | bool BuildOffsetsTable(string const & filePath) |
| 124 | { |