32 static_assert(
sizeof(
long long) >=
sizeof(uint64_t),
33 "__builtin_...ll is used on uint64_t values.");
36 std::array<uint64_t, 64> m{};
37 for (
int i = 0; i < 64; ++i) m[i] = (uint64_t{1} << i) - 1;
45 if (end == 0)
return 0;
50 const uint32_t sum = GetIndexOnesCount(end_word);
54 if (bit_index == 0)
return sum;
55 return sum + __builtin_popcountll(bits_[end_word] & kLowBitsMasks[bit_index]);
60 const RankIndexEntry& entry = FindRankIndexEntry(bit_index);
61 const uint32_t block_index = &entry - rank_index_.data();
63 static_assert(kUnitsPerRankIndexEntry == 8);
64 uint32_t word_index = block_index * kUnitsPerRankIndexEntry;
67 uint32_t rembits = bit_index - entry.absolute_ones_count();
68 if (rembits < entry.relative_ones_count_4()) {
69 if (rembits < entry.relative_ones_count_2()) {
70 if (rembits < entry.relative_ones_count_1()) {
74 rembits -= entry.relative_ones_count_1();
76 }
else if (rembits < entry.relative_ones_count_3()) {
78 rembits -= entry.relative_ones_count_2();
81 rembits -= entry.relative_ones_count_3();
83 }
else if (rembits < entry.relative_ones_count_6()) {
84 if (rembits < entry.relative_ones_count_5()) {
86 rembits -= entry.relative_ones_count_4();
89 rembits -= entry.relative_ones_count_5();
91 }
else if (rembits < entry.relative_ones_count_7()) {
93 rembits -= entry.relative_ones_count_6();
96 rembits -= entry.relative_ones_count_7();
99 const int nth =
nth_bit(bits_[word_index], rembits);
105 if (bit_index >= zeros_count)
return Bits();
106 const RankIndexEntry& entry = FindInvertedRankIndexEntry(bit_index);
107 const uint32_t block_index = &entry - rank_index_.data();
108 static_assert(kUnitsPerRankIndexEntry == 8);
109 uint32_t word_index = block_index * kUnitsPerRankIndexEntry;
112 uint32_t entry_zeros_count =
114 uint32_t remzeros = bit_index - entry_zeros_count;
123 }
else if (remzeros < 3 *
kStorageBitSize - entry.relative_ones_count_3()) {
130 }
else if (remzeros < 6 *
kStorageBitSize - entry.relative_ones_count_6()) {
138 }
else if (remzeros < 7 *
kStorageBitSize - entry.relative_ones_count_7()) {
146 const int nth =
nth_bit(~bits_[word_index], remzeros);
152 if (bit_index >= zeros_count)
return {
Bits(),
Bits()};
153 if (bit_index + 1 >= zeros_count)
return {
Select0(bit_index),
Bits()};
155 const RankIndexEntry& entry = FindInvertedRankIndexEntry(bit_index);
156 const uint32_t block_index = &entry - rank_index_.data();
157 uint32_t word_index = block_index * kUnitsPerRankIndexEntry;
160 uint32_t entry_zeros_count =
162 uint32_t remzeros = bit_index - entry_zeros_count;
171 }
else if (remzeros < 3 *
kStorageBitSize - entry.relative_ones_count_3()) {
178 }
else if (remzeros < 6 *
kStorageBitSize - entry.relative_ones_count_6()) {
186 }
else if (remzeros < 7 *
kStorageBitSize - entry.relative_ones_count_7()) {
195 const uint64_t inv_word = ~bits_[word_index];
196 const int nth =
nth_bit(inv_word, remzeros);
207 const uint64_t mask = -(uint64_t{0x2} << nth);
208 const uint64_t masked_inv_word = inv_word & mask;
211 if (masked_inv_word != 0) {
213 const int next_nth = __builtin_ctzll(masked_inv_word);
224 uint32_t BitmapIndex::GetIndexOnesCount(
size_t array_index)
const {
225 const auto& rank_index_entry =
226 rank_index_[array_index / kUnitsPerRankIndexEntry];
227 uint32_t ones_count = rank_index_entry.absolute_ones_count();
228 static_assert(kUnitsPerRankIndexEntry == 8);
229 return ones_count + rank_index_entry.relative_ones_count(
230 array_index % kUnitsPerRankIndexEntry);
234 bool enable_select_0_index,
235 bool enable_select_1_index) {
241 num_bits_ = num_bits;
243 rank_index_.resize(rank_index_size());
245 select_0_index_.clear();
246 if (enable_select_0_index) {
248 select_0_index_.reserve(num_bits / (2 * kBitsPerSelect0Block) + 1);
251 select_1_index_.clear();
252 if (enable_select_1_index) {
253 select_1_index_.reserve(num_bits / (2 * kBitsPerSelect1Block) + 1);
257 uint32_t ones_count = 0;
258 uint32_t zeros_count = 0;
259 for (uint32_t word_index = 0; word_index < kArraySize; word_index += 8) {
260 const uint64_t word[8] = {
262 (word_index + 1 < kArraySize) ? bits[word_index + 1] : 0,
263 (word_index + 2 < kArraySize) ? bits[word_index + 2] : 0,
264 (word_index + 3 < kArraySize) ? bits[word_index + 3] : 0,
265 (word_index + 4 < kArraySize) ? bits[word_index + 4] : 0,
266 (word_index + 5 < kArraySize) ? bits[word_index + 5] : 0,
267 (word_index + 6 < kArraySize) ? bits[word_index + 6] : 0,
268 (word_index + 7 < kArraySize) ? bits[word_index + 7] : 0,
271 const int word_ones_count[8] = {
272 __builtin_popcountll(word[0]), __builtin_popcountll(word[1]),
273 __builtin_popcountll(word[2]), __builtin_popcountll(word[3]),
274 __builtin_popcountll(word[4]), __builtin_popcountll(word[5]),
275 __builtin_popcountll(word[6]), __builtin_popcountll(word[7]),
278 auto& rank_index_entry = rank_index_[word_index / kUnitsPerRankIndexEntry];
279 const uint32_t abs_ones_count = ones_count;
280 rank_index_entry.set_absolute_ones_count(abs_ones_count);
281 ones_count += word_ones_count[0];
282 rank_index_entry.set_relative_ones_count_1(ones_count - abs_ones_count);
283 ones_count += word_ones_count[1];
284 rank_index_entry.set_relative_ones_count_2(ones_count - abs_ones_count);
285 ones_count += word_ones_count[2];
286 rank_index_entry.set_relative_ones_count_3(ones_count - abs_ones_count);
287 ones_count += word_ones_count[3];
288 rank_index_entry.set_relative_ones_count_4(ones_count - abs_ones_count);
289 ones_count += word_ones_count[4];
290 rank_index_entry.set_relative_ones_count_5(ones_count - abs_ones_count);
291 ones_count += word_ones_count[5];
292 rank_index_entry.set_relative_ones_count_6(ones_count - abs_ones_count);
293 ones_count += word_ones_count[6];
294 rank_index_entry.set_relative_ones_count_7(ones_count - abs_ones_count);
295 ones_count += word_ones_count[7];
297 if (enable_select_0_index) {
298 int s0_zeros_count = zeros_count;
299 for (
int i = 0; i < 8; ++i) {
301 if (bit_offset >= num_bits_)
break;
307 const uint32_t bits_remaining = num_bits - bit_offset;
308 const int word_zeros_count =
316 const uint32_t zeros_to_skip = -s0_zeros_count % kBitsPerSelect0Block;
317 if (word_zeros_count > zeros_to_skip) {
318 const int nth =
nth_bit(~word[i], zeros_to_skip);
319 select_0_index_.push_back(bit_offset + nth);
320 static_assert(kBitsPerSelect0Block >= 512,
321 "kBitsPerSelect0Block must be at least 512.");
324 s0_zeros_count += word_zeros_count;
329 if (enable_select_1_index) {
330 int s1_ones_count = abs_ones_count;
331 for (
int i = 0; i < 8; ++i) {
333 uint32_t ones_to_skip = -s1_ones_count % kBitsPerSelect1Block;
334 if (word_ones_count[i] > ones_to_skip) {
335 const int nth =
nth_bit(word[i], ones_to_skip);
336 select_1_index_.push_back(bit_offset + nth);
337 static_assert(kBitsPerSelect1Block >= 512,
338 "kBitsPerSelect1Block must be at least 512.");
341 s1_ones_count += word_ones_count[i];
346 rank_index_.back().set_absolute_ones_count(ones_count);
348 if (enable_select_0_index) {
350 select_0_index_.push_back(num_bits_);
351 select_0_index_.shrink_to_fit();
354 if (enable_select_1_index) {
355 select_1_index_.push_back(num_bits_);
356 select_1_index_.shrink_to_fit();
360 const BitmapIndex::RankIndexEntry& BitmapIndex::FindRankIndexEntry(
361 size_t bit_index)
const {
363 DCHECK_LT(bit_index, rank_index_.back().absolute_ones_count());
365 const RankIndexEntry* begin =
nullptr;
366 const RankIndexEntry* end =
nullptr;
367 if (select_1_index_.empty()) {
368 begin = &rank_index_[0];
369 end = begin + rank_index_.size();
371 const uint32_t select_index = bit_index / kBitsPerSelect1Block;
372 DCHECK_LT(select_index + 1, select_1_index_.size());
381 const uint32_t lo_bit_index = select_1_index_[select_index];
382 const uint32_t hi_bit_index = select_1_index_[select_index + 1];
384 begin = &rank_index_[lo_bit_index / kBitsPerSelect1Block];
385 end = &rank_index_[(hi_bit_index + kBitsPerSelect1Block - 1) /
386 kBitsPerSelect1Block];
390 const RankIndexEntry* entry =
nullptr;
391 if (end - begin <= kMaxLinearSearchBlocks) {
392 for (entry = begin; entry != end; ++entry) {
393 if (entry->absolute_ones_count() > bit_index)
break;
396 RankIndexEntry search_entry;
397 search_entry.set_absolute_ones_count(bit_index);
399 entry = &*std::upper_bound(
400 begin, end, search_entry,
401 [](
const RankIndexEntry& e1,
const RankIndexEntry& e2) {
402 return e1.absolute_ones_count() < e2.absolute_ones_count();
406 const auto& e = *(entry - 1);
407 DCHECK_LE(e.absolute_ones_count(), bit_index);
408 DCHECK_GT(entry->absolute_ones_count(), bit_index);
412 const BitmapIndex::RankIndexEntry& BitmapIndex::FindInvertedRankIndexEntry(
413 size_t bit_index)
const {
415 DCHECK_LT(bit_index, num_bits_ - rank_index_.back().absolute_ones_count());
417 uint32_t lo = 0, hi = 0;
418 if (select_0_index_.empty()) {
420 hi = (num_bits_ + kBitsPerRankIndexEntry - 1) / kBitsPerRankIndexEntry;
422 const uint32_t select_index = bit_index / kBitsPerSelect0Block;
423 DCHECK_LT(select_index + 1, select_0_index_.size());
427 lo = select_0_index_[select_index] / kBitsPerSelect0Block;
428 hi = (select_0_index_[select_index + 1] + kBitsPerSelect0Block - 1) /
429 kBitsPerSelect0Block;
437 while (lo + 1 < hi) {
438 const uint32_t mid = lo + (hi - lo) / 2;
440 kBitsPerRankIndexEntry * mid - rank_index_[mid].absolute_ones_count()) {
447 DCHECK_LE(lo * kBitsPerRankIndexEntry - rank_index_[lo].absolute_ones_count(),
449 if ((lo + 1) * kBitsPerRankIndexEntry <= num_bits_) {
450 DCHECK_GT((lo + 1) * kBitsPerRankIndexEntry -
451 rank_index_[lo + 1].absolute_ones_count(),
454 DCHECK_GT(num_bits_ - rank_index_[lo + 1].absolute_ones_count(), bit_index);
456 return rank_index_[lo];
static constexpr uint32_t kStorageBitSize
constexpr std::array< uint64_t, 64 > kLowBitsMasks
void BuildIndex(const uint64_t *bits, size_t num_bits, bool enable_select_0_index=false, bool enable_select_1_index=false)
size_t Select1(size_t bit_index) const
size_t Rank1(size_t end) const
size_t Select0(size_t bit_index) const
size_t GetOnesCount() const
constexpr std::array< uint64_t, 64 > LowBitsMasks()
std::pair< size_t, size_t > Select0s(size_t bit_index) const
int nth_bit(const uint64_t v, uint32_t r)