CRoaring 4.3.5
Roaring bitmaps in C (and C++)
Loading...
Searching...
No Matches
roaring64map.hh
Go to the documentation of this file.
1
9#ifndef INCLUDE_ROARING_64_MAP_HH_
10#define INCLUDE_ROARING_64_MAP_HH_
11
12#include <algorithm>
13#include <cinttypes> // PRIu64 macro
14#include <climits> // for UINT64_MAX
15#include <cstdarg> // for va_list handling in bitmapOf()
16#include <cstdio> // for std::printf() in the printf() method
17#include <cstring> // for std::memcpy()
18#include <functional>
19#include <initializer_list>
20#include <limits>
21#include <map>
22#include <new>
23#include <numeric>
24#include <queue>
25#include <stdexcept>
26#include <string>
27#include <utility>
28
29#include "roaring.hh"
30
31namespace roaring {
32
34
35class Roaring64MapSetBitBiDirectionalIterator;
36
37// For backwards compatibility; there used to be two kinds of iterators
38// (forward and bidirectional) and now there's only one.
39typedef Roaring64MapSetBitBiDirectionalIterator
41
43 typedef api::roaring_bitmap_t roaring_bitmap_t;
44
45 public:
49 Roaring64Map() = default;
50
54 Roaring64Map(size_t n, const uint32_t *data) { addMany(n, data); }
55
59 Roaring64Map(size_t n, const uint64_t *data) { addMany(n, data); }
60
64 Roaring64Map(std::initializer_list<uint64_t> l) {
65 addMany(l.size(), l.begin());
66 }
67
71 explicit Roaring64Map(const Roaring &r) { emplaceOrInsert(0, r); }
72
76 explicit Roaring64Map(Roaring &&r) { emplaceOrInsert(0, std::move(r)); }
77
83 explicit Roaring64Map(roaring_bitmap_t *s) {
84 emplaceOrInsert(0, Roaring(s));
85 }
86
87 Roaring64Map(const Roaring64Map &r) = default;
88
89 Roaring64Map(Roaring64Map &&r) noexcept = default;
90
94 Roaring64Map &operator=(const Roaring64Map &r) = default;
95
99 Roaring64Map &operator=(Roaring64Map &&r) noexcept = default;
100
104 Roaring64Map &operator=(std::initializer_list<uint64_t> l) {
105 // Delegate to move assignment operator
106 *this = Roaring64Map(l);
107 return *this;
108 }
109
113 static Roaring64Map bitmapOf(size_t n...) {
114 Roaring64Map ans;
115 va_list vl;
116 va_start(vl, n);
117 for (size_t i = 0; i < n; i++) {
118 ans.add(va_arg(vl, uint64_t));
119 }
120 va_end(vl);
121 return ans;
122 }
123
128 static Roaring64Map bitmapOfList(std::initializer_list<uint64_t> l) {
129 Roaring64Map ans;
130 ans.addMany(l.size(), l.begin());
131 return ans;
132 }
133
137 void add(uint32_t x) { lookupOrCreateInner(0).add(x); }
138
142 void add(uint64_t x) { lookupOrCreateInner(highBytes(x)).add(lowBytes(x)); }
143
149 bool addChecked(uint32_t x) { return lookupOrCreateInner(0).addChecked(x); }
150
156 bool addChecked(uint64_t x) {
157 return lookupOrCreateInner(highBytes(x)).addChecked(lowBytes(x));
158 }
159
163 void addRange(uint64_t min, uint64_t max) {
164 if (min >= max) {
165 return;
166 }
167 addRangeClosed(min, max - 1);
168 }
169
173 void addRangeClosed(uint32_t min, uint32_t max) {
174 lookupOrCreateInner(0).addRangeClosed(min, max);
175 }
176
180 void addRangeClosed(uint64_t min, uint64_t max) {
181 if (min > max) {
182 return;
183 }
184 uint32_t start_high = highBytes(min);
185 uint32_t start_low = lowBytes(min);
186 uint32_t end_high = highBytes(max);
187 uint32_t end_low = lowBytes(max);
188
189 // We put std::numeric_limits<>::max in parentheses to avoid a
190 // clash with the Windows.h header under Windows.
191 const uint32_t uint32_max = (std::numeric_limits<uint32_t>::max)();
192
193 // Fill in any nonexistent slots with empty Roarings. This simplifies
194 // the logic below, allowing it to simply iterate over the map between
195 // 'start_high' and 'end_high' in a linear fashion.
196 auto current_iter = ensureRangePopulated(start_high, end_high);
197
198 // If start and end land on the same inner bitmap, then we can do the
199 // whole operation in one call.
200 if (start_high == end_high) {
201 auto &bitmap = current_iter->second;
202 bitmap.addRangeClosed(start_low, end_low);
203 return;
204 }
205
206 // Because start and end don't land on the same inner bitmap,
207 // we need to do this in multiple steps:
208 // 1. Partially fill the first bitmap with values from the closed
209 // interval [start_low, uint32_max]
210 // 2. Fill intermediate bitmaps completely: [0, uint32_max]
211 // 3. Partially fill the last bitmap with values from the closed
212 // interval [0, end_low]
213 auto num_intermediate_bitmaps = end_high - start_high - 1;
214
215 // Step 1: Partially fill the first bitmap.
216 {
217 auto &bitmap = current_iter->second;
218 bitmap.addRangeClosed(start_low, uint32_max);
219 ++current_iter;
220 }
221
222 // Step 2. Fill intermediate bitmaps completely.
223 if (num_intermediate_bitmaps != 0) {
224 auto &first_intermediate = current_iter->second;
225 first_intermediate.addRangeClosed(0, uint32_max);
226 ++current_iter;
227
228 // Now make (num_intermediate_bitmaps - 1) copies of this.
229 for (uint32_t i = 1; i != num_intermediate_bitmaps; ++i) {
230 auto &next_intermediate = current_iter->second;
231 next_intermediate = first_intermediate;
232 ++current_iter;
233 }
234 }
235
236 // Step 3: Partially fill the last bitmap.
237 auto &bitmap = current_iter->second;
238 bitmap.addRangeClosed(0, end_low);
239 }
240
244 void addMany(size_t n_args, const uint32_t *vals) {
245 lookupOrCreateInner(0).addMany(n_args, vals);
246 }
247
251 void addMany(size_t n_args, const uint64_t *vals) {
252 // Potentially reduce outer map lookups by optimistically
253 // assuming that adjacent values will belong to the same inner bitmap.
254 Roaring *last_inner_bitmap = nullptr;
255 uint32_t last_value_high = 0;
256 BulkContext last_bulk_context;
257 for (size_t lcv = 0; lcv < n_args; lcv++) {
258 auto value = vals[lcv];
259 auto value_high = highBytes(value);
260 auto value_low = lowBytes(value);
261 if (last_inner_bitmap == nullptr || value_high != last_value_high) {
262 last_inner_bitmap = &lookupOrCreateInner(value_high);
263 last_value_high = value_high;
264 last_bulk_context = BulkContext{};
265 }
266 last_inner_bitmap->addBulk(last_bulk_context, value_low);
267 }
268 }
269
273 void remove(uint32_t x) {
274 auto iter = roarings.begin();
275 // Since x is a uint32_t, highbytes(x) == 0. The inner bitmap we are
276 // looking for, if it exists, will be at the first slot of 'roarings'.
277 if (iter == roarings.end() || iter->first != 0) {
278 return;
279 }
280 auto &bitmap = iter->second;
281 bitmap.remove(x);
282 eraseIfEmpty(iter);
283 }
284
288 void remove(uint64_t x) {
289 auto iter = roarings.find(highBytes(x));
290 if (iter == roarings.end()) {
291 return;
292 }
293 auto &bitmap = iter->second;
294 bitmap.remove(lowBytes(x));
295 eraseIfEmpty(iter);
296 }
297
303 bool removeChecked(uint32_t x) {
304 auto iter = roarings.begin();
305 // Since x is a uint32_t, highbytes(x) == 0. The inner bitmap we are
306 // looking for, if it exists, will be at the first slot of 'roarings'.
307 if (iter == roarings.end() || iter->first != 0) {
308 return false;
309 }
310 auto &bitmap = iter->second;
311 if (!bitmap.removeChecked(x)) {
312 return false;
313 }
314 eraseIfEmpty(iter);
315 return true;
316 }
317
323 bool removeChecked(uint64_t x) {
324 auto iter = roarings.find(highBytes(x));
325 if (iter == roarings.end()) {
326 return false;
327 }
328 auto &bitmap = iter->second;
329 if (!bitmap.removeChecked(lowBytes(x))) {
330 return false;
331 }
332 eraseIfEmpty(iter);
333 return true;
334 }
335
339 void removeRange(uint64_t min, uint64_t max) {
340 if (min >= max) {
341 return;
342 }
343 return removeRangeClosed(min, max - 1);
344 }
345
349 void removeRangeClosed(uint32_t min, uint32_t max) {
350 auto iter = roarings.begin();
351 // Since min and max are uint32_t, highbytes(min or max) == 0. The inner
352 // bitmap we are looking for, if it exists, will be at the first slot of
353 // 'roarings'.
354 if (iter == roarings.end() || iter->first != 0) {
355 return;
356 }
357 auto &bitmap = iter->second;
358 bitmap.removeRangeClosed(min, max);
359 eraseIfEmpty(iter);
360 }
361
365 void removeRangeClosed(uint64_t min, uint64_t max) {
366 if (min > max) {
367 return;
368 }
369 uint32_t start_high = highBytes(min);
370 uint32_t start_low = lowBytes(min);
371 uint32_t end_high = highBytes(max);
372 uint32_t end_low = lowBytes(max);
373
374 // We put std::numeric_limits<>::max in parentheses to avoid a
375 // clash with the Windows.h header under Windows.
376 const uint32_t uint32_max = (std::numeric_limits<uint32_t>::max)();
377
378 // If the outer map is empty, end_high is less than the first key,
379 // or start_high is greater than the last key, then exit now because
380 // there is no work to do.
381 if (roarings.empty() || end_high < roarings.cbegin()->first ||
382 start_high > (roarings.crbegin())->first) {
383 return;
384 }
385
386 // If we get here, start_iter points to the first entry in the outer map
387 // with key >= start_high. Such an entry is known to exist (i.e. the
388 // iterator will not be equal to end()) because start_high <= the last
389 // key in the map (thanks to the above if statement).
390 auto start_iter = roarings.lower_bound(start_high);
391 // end_iter points to the first entry in the outer map with
392 // key >= end_high, if such a key exists. Otherwise, it equals end().
393 auto end_iter = roarings.lower_bound(end_high);
394
395 // Note that the 'lower_bound' method will find the start and end slots,
396 // if they exist; otherwise it will find the next-higher slots.
397 // In the case where 'start' landed on an existing slot, we need to do a
398 // partial erase of that slot, and likewise for 'end'. But all the slots
399 // in between can be fully erased. More precisely:
400 //
401 // 1. If the start point falls on an existing entry, there are two
402 // subcases:
403 // a. if the end point falls on that same entry, remove the closed
404 // interval [start_low, end_low] from that entry and we are done.
405 // b. Otherwise, remove the closed interval [start_low, uint32_max]
406 // from that entry, advance start_iter, and fall through to
407 // step 2.
408 // 2. Completely erase all slots in the half-open interval
409 // [start_iter, end_iter)
410 // 3. If the end point falls on an existing entry, remove the closed
411 // interval [0, end_high] from it.
412
413 // Step 1. If the start point falls on an existing entry...
414 if (start_iter->first == start_high) {
415 auto &start_inner = start_iter->second;
416 // 1a. if the end point falls on that same entry...
417 if (start_iter == end_iter) {
418 start_inner.removeRangeClosed(start_low, end_low);
419 eraseIfEmpty(start_iter);
420 return;
421 }
422
423 // 1b. Otherwise, remove the closed range [start_low, uint32_max]...
424 start_inner.removeRangeClosed(start_low, uint32_max);
425 // Advance start_iter, but keep the old value so we can check the
426 // bitmap we just modified for emptiness and erase if it necessary.
427 auto temp = start_iter++;
428 eraseIfEmpty(temp);
429 }
430
431 // 2. Completely erase all slots in the half-open interval...
432 roarings.erase(start_iter, end_iter);
433
434 // 3. If the end point falls on an existing entry...
435 if (end_iter != roarings.end() && end_iter->first == end_high) {
436 auto &end_inner = end_iter->second;
437 end_inner.removeRangeClosed(0, end_low);
438 eraseIfEmpty(end_iter);
439 }
440 }
441
445 void clear() { roarings.clear(); }
446
450 uint64_t maximum() const {
451 for (auto roaring_iter = roarings.crbegin();
452 roaring_iter != roarings.crend(); ++roaring_iter) {
453 if (!roaring_iter->second.isEmpty()) {
454 return uniteBytes(roaring_iter->first,
455 roaring_iter->second.maximum());
456 }
457 }
458 // we put std::numeric_limits<>::max/min in parentheses
459 // to avoid a clash with the Windows.h header under Windows
460 return (std::numeric_limits<uint64_t>::min)();
461 }
462
466 uint64_t minimum() const {
467 for (auto roaring_iter = roarings.cbegin();
468 roaring_iter != roarings.cend(); ++roaring_iter) {
469 if (!roaring_iter->second.isEmpty()) {
470 return uniteBytes(roaring_iter->first,
471 roaring_iter->second.minimum());
472 }
473 }
474 // we put std::numeric_limits<>::max/min in parentheses
475 // to avoid a clash with the Windows.h header under Windows
476 return (std::numeric_limits<uint64_t>::max)();
477 }
478
482 bool contains(uint32_t x) const {
483 auto iter = roarings.find(0);
484 if (iter == roarings.end()) {
485 return false;
486 }
487 return iter->second.contains(x);
488 }
489 bool contains(uint64_t x) const {
490 auto iter = roarings.find(highBytes(x));
491 if (iter == roarings.end()) {
492 return false;
493 }
494 return iter->second.contains(lowBytes(x));
495 }
496
497 // TODO: implement `containsRange`
498
508 if (this == &other) {
509 // ANDing *this with itself is a no-op.
510 return *this;
511 }
512
513 // Logic table summarizing what to do when a given outer key is
514 // present vs. absent from self and other.
515 //
516 // self other (self & other) work to do
517 // --------------------------------------------
518 // absent absent empty None
519 // absent present empty None
520 // present absent empty Erase self
521 // present present empty or not Intersect self with other, but
522 // erase self if result is empty.
523 //
524 // Because there is only work to do when a key is present in 'self', the
525 // main for loop iterates over entries in 'self'.
526
527 decltype(roarings.begin()) self_next;
528 for (auto self_iter = roarings.begin(); self_iter != roarings.end();
529 self_iter = self_next) {
530 // Do the 'next' operation now, so we don't have to worry about
531 // invalidation of self_iter down below with the 'erase' operation.
532 self_next = std::next(self_iter);
533
534 auto self_key = self_iter->first;
535 auto &self_bitmap = self_iter->second;
536
537 auto other_iter = other.roarings.find(self_key);
538 if (other_iter == other.roarings.end()) {
539 // 'other' doesn't have self_key. In the logic table above,
540 // this reflects the case (self.present & other.absent).
541 // So, erase self.
542 roarings.erase(self_iter);
543 continue;
544 }
545
546 // Both sides have self_key. In the logic table above, this reflects
547 // the case (self.present & other.present). So, intersect self with
548 // other.
549 const auto &other_bitmap = other_iter->second;
550 self_bitmap &= other_bitmap;
551 if (self_bitmap.isEmpty()) {
552 // ...but if intersection is empty, remove it altogether.
553 roarings.erase(self_iter);
554 }
555 }
556 return *this;
557 }
558
565 if (this == &other) {
566 // Subtracting *this from itself results in the empty map.
567 roarings.clear();
568 return *this;
569 }
570
571 // Logic table summarizing what to do when a given outer key is
572 // present vs. absent from self and other.
573 //
574 // self other (self - other) work to do
575 // --------------------------------------------
576 // absent absent empty None
577 // absent present empty None
578 // present absent unchanged None
579 // present present empty or not Subtract other from self, but
580 // erase self if result is empty
581 //
582 // Because there is only work to do when a key is present in both 'self'
583 // and 'other', the main while loop ping-pongs back and forth until it
584 // finds the next key that is the same on both sides.
585
586 auto self_iter = roarings.begin();
587 auto other_iter = other.roarings.cbegin();
588
589 while (self_iter != roarings.end() &&
590 other_iter != other.roarings.cend()) {
591 auto self_key = self_iter->first;
592 auto other_key = other_iter->first;
593 if (self_key < other_key) {
594 // Because self_key is < other_key, advance self_iter to the
595 // first point where self_key >= other_key (or end).
596 self_iter = roarings.lower_bound(other_key);
597 continue;
598 }
599
600 if (self_key > other_key) {
601 // Because self_key is > other_key, advance other_iter to the
602 // first point where other_key >= self_key (or end).
603 other_iter = other.roarings.lower_bound(self_key);
604 continue;
605 }
606
607 // Both sides have self_key. In the logic table above, this reflects
608 // the case (self.present & other.present). So subtract other from
609 // self.
610 auto &self_bitmap = self_iter->second;
611 const auto &other_bitmap = other_iter->second;
612 self_bitmap -= other_bitmap;
613
614 if (self_bitmap.isEmpty()) {
615 // ...but if subtraction is empty, remove it altogether.
616 self_iter = roarings.erase(self_iter);
617 } else {
618 ++self_iter;
619 }
620 ++other_iter;
621 }
622 return *this;
623 }
624
633 if (this == &other) {
634 // ORing *this with itself is a no-op.
635 return *this;
636 }
637
638 // Logic table summarizing what to do when a given outer key is
639 // present vs. absent from self and other.
640 //
641 // self other (self | other) work to do
642 // --------------------------------------------
643 // absent absent empty None
644 // absent present not empty Copy other to self and set flags
645 // present absent unchanged None
646 // present present not empty self |= other
647 //
648 // Because there is only work to do when a key is present in 'other',
649 // the main for loop iterates over entries in 'other'.
650
651 for (const auto &other_entry : other.roarings) {
652 const auto &other_bitmap = other_entry.second;
653
654 // Try to insert other_bitmap into self at other_key. We take
655 // advantage of the fact that std::map::insert will not overwrite an
656 // existing entry.
657 auto insert_result = roarings.insert(other_entry);
658 auto self_iter = insert_result.first;
659 auto insert_happened = insert_result.second;
660 auto &self_bitmap = self_iter->second;
661
662 if (insert_happened) {
663 // Key was not present in self, so insert was performed above.
664 // In the logic table above, this reflects the case
665 // (self.absent | other.present). Because the copy has already
666 // happened, thanks to the 'insert' operation above, we just
667 // need to set the copyOnWrite flag.
668 self_bitmap.setCopyOnWrite(copyOnWrite);
669 continue;
670 }
671
672 // Both sides have self_key, and the insert was not performed. In
673 // the logic table above, this reflects the case
674 // (self.present & other.present). So OR other into self.
675 self_bitmap |= other_bitmap;
676 }
677 return *this;
678 }
679
685 if (this == &other) {
686 // XORing *this with itself results in the empty map.
687 roarings.clear();
688 return *this;
689 }
690
691 // Logic table summarizing what to do when a given outer key is
692 // present vs. absent from self and other.
693 //
694 // self other (self ^ other) work to do
695 // --------------------------------------------
696 // absent absent empty None
697 // absent present non-empty Copy other to self and set flags
698 // present absent unchanged None
699 // present present empty or not XOR other into self, but erase self
700 // if result is empty.
701 //
702 // Because there is only work to do when a key is present in 'other',
703 // the main for loop iterates over entries in 'other'.
704
705 for (const auto &other_entry : other.roarings) {
706 const auto &other_bitmap = other_entry.second;
707
708 // Try to insert other_bitmap into self at other_key. We take
709 // advantage of the fact that std::map::insert will not overwrite an
710 // existing entry.
711 auto insert_result = roarings.insert(other_entry);
712 auto self_iter = insert_result.first;
713 auto insert_happened = insert_result.second;
714 auto &self_bitmap = self_iter->second;
715
716 if (insert_happened) {
717 // Key was not present in self, so insert was performed above.
718 // In the logic table above, this reflects the case
719 // (self.absent ^ other.present). Because the copy has already
720 // happened, thanks to the 'insert' operation above, we just
721 // need to set the copyOnWrite flag.
722 self_bitmap.setCopyOnWrite(copyOnWrite);
723 continue;
724 }
725
726 // Both sides have self_key, and the insert was not performed. In
727 // the logic table above, this reflects the case
728 // (self.present ^ other.present). So XOR other into self.
729 self_bitmap ^= other_bitmap;
730
731 if (self_bitmap.isEmpty()) {
732 // ...but if intersection is empty, remove it altogether.
733 roarings.erase(self_iter);
734 }
735 }
736 return *this;
737 }
738
742 void swap(Roaring64Map &r) { roarings.swap(r.roarings); }
743
750 uint64_t cardinality() const {
751 if (isFull()) {
752#if ROARING_EXCEPTIONS
753 throw std::length_error(
754 "bitmap is full, cardinality is 2^64, "
755 "unable to represent in a 64-bit integer");
756#else
758 "bitmap is full, cardinality is 2^64, "
759 "unable to represent in a 64-bit integer");
760#endif
761 }
762 return std::accumulate(
763 roarings.cbegin(), roarings.cend(), (uint64_t)0,
764 [](uint64_t previous,
765 const std::pair<const uint32_t, Roaring> &map_entry) {
766 return previous + map_entry.second.cardinality();
767 });
768 }
769
773 bool isEmpty() const {
774 return std::all_of(
775 roarings.cbegin(), roarings.cend(),
776 [](const std::pair<const uint32_t, Roaring> &map_entry) {
777 return map_entry.second.isEmpty();
778 });
779 }
780
784 bool isFull() const {
785 // This function is somewhat absurd. A full 64-bit bitmap would surely
786 // exceed our memory limits.
787#if SIZE_MAX >= UINT64_MAX
788 // only bother to check if map is fully saturated
789 //
790 // we put std::numeric_limits<>::max/min in parentheses
791 // to avoid a clash with the Windows.h header under Windows
792 return roarings.size() ==
793 ((uint64_t)(std::numeric_limits<uint32_t>::max)()) + 1
794 ? std::all_of(roarings.cbegin(), roarings.cend(),
795 [](const std::pair<const uint32_t, Roaring>
796 &roaring_map_entry) {
797 return roaring_map_entry.second.isFull();
798 })
799 : false;
800#else
801 // if SIZE_MAX < UINT64_MAX, then we cannot represent a full bitmap
802 // in a 64-bit integer, so we return false.
803 return false;
804#endif
805 }
806
810 bool isSubset(const Roaring64Map &r) const {
811 for (const auto &map_entry : roarings) {
812 if (map_entry.second.isEmpty()) {
813 continue;
814 }
815 auto roaring_iter = r.roarings.find(map_entry.first);
816 if (roaring_iter == r.roarings.cend())
817 return false;
818 else if (!map_entry.second.isSubset(roaring_iter->second))
819 return false;
820 }
821 return true;
822 }
823
830 bool isStrictSubset(const Roaring64Map &r) const {
831 return isSubset(r) && cardinality() != r.cardinality();
832 }
833
840 void toUint64Array(uint64_t *ans) const {
841 // Annoyingly, VS 2017 marks std::accumulate() as [[nodiscard]]
842 (void)std::accumulate(
843 roarings.cbegin(), roarings.cend(), ans,
844 [](uint64_t *previous,
845 const std::pair<const uint32_t, Roaring> &map_entry) {
846 for (uint32_t low_bits : map_entry.second)
847 *previous++ = uniteBytes(map_entry.first, low_bits);
848 return previous;
849 });
850 }
851
855 bool operator==(const Roaring64Map &r) const {
856 // we cannot use operator == on the map because either side may contain
857 // empty Roaring Bitmaps
858 auto lhs_iter = roarings.cbegin();
859 auto lhs_cend = roarings.cend();
860 auto rhs_iter = r.roarings.cbegin();
861 auto rhs_cend = r.roarings.cend();
862 while (lhs_iter != lhs_cend && rhs_iter != rhs_cend) {
863 auto lhs_key = lhs_iter->first, rhs_key = rhs_iter->first;
864 const auto &lhs_map = lhs_iter->second, &rhs_map = rhs_iter->second;
865 if (lhs_map.isEmpty()) {
866 ++lhs_iter;
867 continue;
868 }
869 if (rhs_map.isEmpty()) {
870 ++rhs_iter;
871 continue;
872 }
873 if (!(lhs_key == rhs_key)) {
874 return false;
875 }
876 if (!(lhs_map == rhs_map)) {
877 return false;
878 }
879 ++lhs_iter;
880 ++rhs_iter;
881 }
882 while (lhs_iter != lhs_cend) {
883 if (!lhs_iter->second.isEmpty()) {
884 return false;
885 }
886 ++lhs_iter;
887 }
888 while (rhs_iter != rhs_cend) {
889 if (!rhs_iter->second.isEmpty()) {
890 return false;
891 }
892 ++rhs_iter;
893 }
894 return true;
895 }
896
901 void flip(uint64_t min, uint64_t max) {
902 if (min >= max) {
903 return;
904 }
905 flipClosed(min, max - 1);
906 }
907
912 void flipClosed(uint32_t min, uint32_t max) {
913 auto iter = roarings.begin();
914 // Since min and max are uint32_t, highbytes(min or max) == 0. The inner
915 // bitmap we are looking for, if it exists, will be at the first slot of
916 // 'roarings'. If it does not exist, we have to create it.
917 if (iter == roarings.end() || iter->first != 0) {
918 iter = roarings.emplace_hint(iter, std::piecewise_construct,
919 std::forward_as_tuple(0),
920 std::forward_as_tuple());
921 auto &bitmap = iter->second;
922 bitmap.setCopyOnWrite(copyOnWrite);
923 }
924 auto &bitmap = iter->second;
925 bitmap.flipClosed(min, max);
926 eraseIfEmpty(iter);
927 }
928
933 void flipClosed(uint64_t min, uint64_t max) {
934 if (min > max) {
935 return;
936 }
937 uint32_t start_high = highBytes(min);
938 uint32_t start_low = lowBytes(min);
939 uint32_t end_high = highBytes(max);
940 uint32_t end_low = lowBytes(max);
941
942 // We put std::numeric_limits<>::max in parentheses to avoid a
943 // clash with the Windows.h header under Windows.
944 const uint32_t uint32_max = (std::numeric_limits<uint32_t>::max)();
945
946 // Fill in any nonexistent slots with empty Roarings. This simplifies
947 // the logic below, allowing it to simply iterate over the map between
948 // 'start_high' and 'end_high' in a linear fashion.
949 auto current_iter = ensureRangePopulated(start_high, end_high);
950
951 // If start and end land on the same inner bitmap, then we can do the
952 // whole operation in one call.
953 if (start_high == end_high) {
954 auto &bitmap = current_iter->second;
955 bitmap.flipClosed(start_low, end_low);
956 eraseIfEmpty(current_iter);
957 return;
958 }
959
960 // Because start and end don't land on the same inner bitmap,
961 // we need to do this in multiple steps:
962 // 1. Partially flip the first bitmap in the closed interval
963 // [start_low, uint32_max]
964 // 2. Flip intermediate bitmaps completely: [0, uint32_max]
965 // 3. Partially flip the last bitmap in the closed interval
966 // [0, end_low]
967
968 auto num_intermediate_bitmaps = end_high - start_high - 1;
969
970 // 1. Partially flip the first bitmap.
971 {
972 auto &bitmap = current_iter->second;
973 bitmap.flipClosed(start_low, uint32_max);
974 auto temp = current_iter++;
975 eraseIfEmpty(temp);
976 }
977
978 // 2. Flip intermediate bitmaps completely.
979 for (uint32_t i = 0; i != num_intermediate_bitmaps; ++i) {
980 auto &bitmap = current_iter->second;
981 bitmap.flipClosed(0, uint32_max);
982 auto temp = current_iter++;
983 eraseIfEmpty(temp);
984 }
985
986 // 3. Partially flip the last bitmap.
987 auto &bitmap = current_iter->second;
988 bitmap.flipClosed(0, end_low);
989 eraseIfEmpty(current_iter);
990 }
991
997 return std::accumulate(
998 roarings.begin(), roarings.end(), true,
999 [](bool previous, std::pair<const uint32_t, Roaring> &map_entry) {
1000 return map_entry.second.removeRunCompression() && previous;
1001 });
1002 }
1003
1011 return std::accumulate(
1012 roarings.begin(), roarings.end(), true,
1013 [](bool previous, std::pair<const uint32_t, Roaring> &map_entry) {
1014 return map_entry.second.runOptimize() && previous;
1015 });
1016 }
1017
1022 size_t shrinkToFit() {
1023 size_t savedBytes = 0;
1024 auto iter = roarings.begin();
1025 while (iter != roarings.cend()) {
1026 if (iter->second.isEmpty()) {
1027 // empty Roarings are 84 bytes
1028 savedBytes += 88;
1029 roarings.erase(iter++);
1030 } else {
1031 savedBytes += iter->second.shrinkToFit();
1032 iter++;
1033 }
1034 }
1035 return savedBytes;
1036 }
1037
1049 void iterate(api::roaring_iterator64 iterator, void *ptr) const {
1050 for (const auto &map_entry : roarings) {
1051 bool should_continue =
1052 roaring_iterate64(&map_entry.second.roaring, iterator,
1053 uint64_t(map_entry.first) << 32, ptr);
1054 if (!should_continue) {
1055 break;
1056 }
1057 }
1058 }
1059
1066 bool select(uint64_t rank, uint64_t *element) const {
1067 for (const auto &map_entry : roarings) {
1068 auto key = map_entry.first;
1069 const auto &bitmap = map_entry.second;
1070
1071 uint64_t sub_cardinality = bitmap.cardinality();
1072 if (rank < sub_cardinality) {
1073 uint32_t low_bytes;
1074 // Casting rank to uint32_t is safe because
1075 // rank < sub_cardinality and sub_cardinality <= 2^32.
1076 if (!bitmap.select((uint32_t)rank, &low_bytes)) {
1078 "Logic error: bitmap.select() "
1079 "returned false despite rank < cardinality()");
1080 }
1081 *element = uniteBytes(key, low_bytes);
1082 return true;
1083 }
1084 rank -= sub_cardinality;
1085 }
1086 return false;
1087 }
1088
1092 uint64_t rank(uint64_t x) const {
1093 uint64_t result = 0;
1094 // Find the first bitmap >= x's bucket. If that is the bucket x would be
1095 // in, find it's rank in that bucket. Either way, we're left with a
1096 // range of all buckets strictly smaller than x's bucket, add all their
1097 // cardinalities together.
1098 auto end = roarings.lower_bound(highBytes(x));
1099 if (end != roarings.cend() && end->first == highBytes(x)) {
1100 result += end->second.rank(lowBytes(x));
1101 }
1102 for (auto iter = roarings.cbegin(); iter != end; ++iter) {
1103 result += iter->second.cardinality();
1104 }
1105 return result;
1106 }
1107
1115 int64_t getIndex(uint64_t x) const {
1116 int64_t index = 0;
1117 auto roaring_destination = roarings.find(highBytes(x));
1118 if (roaring_destination != roarings.cend()) {
1119 for (auto roaring_iter = roarings.cbegin();
1120 roaring_iter != roaring_destination; ++roaring_iter) {
1121 index += roaring_iter->second.cardinality();
1122 }
1123 auto low_idx = roaring_destination->second.getIndex(lowBytes(x));
1124 if (low_idx < 0) return -1;
1125 index += low_idx;
1126 return index;
1127 }
1128 return -1;
1129 }
1130
1140 size_t write(char *buf, bool portable = true) const {
1141 const char *orig = buf;
1142 // push map size
1143 uint64_t map_size = roarings.size();
1144 std::memcpy(buf, &map_size, sizeof(uint64_t));
1145 buf += sizeof(uint64_t);
1146 std::for_each(roarings.cbegin(), roarings.cend(),
1147 [&buf, portable](
1148 const std::pair<const uint32_t, Roaring> &map_entry) {
1149 // push map key
1150 std::memcpy(buf, &map_entry.first, sizeof(uint32_t));
1151 // ^-- Note: `*((uint32_t*)buf) = map_entry.first;` is
1152 // undefined
1153
1154 buf += sizeof(uint32_t);
1155 // push map value Roaring
1156 buf += map_entry.second.write(buf, portable);
1157 });
1158 return buf - orig;
1159 }
1160
1173 static Roaring64Map read(const char *buf, bool portable = true) {
1174 Roaring64Map result;
1175 // get map size
1176 uint64_t map_size;
1177 std::memcpy(&map_size, buf, sizeof(uint64_t));
1178 buf += sizeof(uint64_t);
1179 for (uint64_t lcv = 0; lcv < map_size; lcv++) {
1180 // get map key
1181 uint32_t key;
1182 std::memcpy(&key, buf, sizeof(uint32_t));
1183 // ^-- Note: `uint32_t key = *((uint32_t*)buf);` is undefined
1184
1185 buf += sizeof(uint32_t);
1186 // read map value Roaring
1187 Roaring read_var = Roaring::read(buf, portable);
1188 // forward buffer past the last Roaring Bitmap
1189 buf += read_var.getSizeInBytes(portable);
1190 result.emplaceOrInsert(key, std::move(read_var));
1191 }
1192 return result;
1193 }
1194
1202 static Roaring64Map readSafe(const char *buf, size_t maxbytes) {
1203 if (maxbytes < sizeof(uint64_t)) {
1204 ROARING_TERMINATE("ran out of bytes");
1205 }
1206 Roaring64Map result;
1207 uint64_t map_size;
1208 std::memcpy(&map_size, buf, sizeof(uint64_t));
1209 buf += sizeof(uint64_t);
1210 maxbytes -= sizeof(uint64_t);
1211 for (uint64_t lcv = 0; lcv < map_size; lcv++) {
1212 if (maxbytes < sizeof(uint32_t)) {
1213 ROARING_TERMINATE("ran out of bytes");
1214 }
1215 uint32_t key;
1216 std::memcpy(&key, buf, sizeof(uint32_t));
1217 // ^-- Note: `uint32_t key = *((uint32_t*)buf);` is undefined
1218
1219 buf += sizeof(uint32_t);
1220 maxbytes -= sizeof(uint32_t);
1221 // read map value Roaring
1222 Roaring read_var = Roaring::readSafe(buf, maxbytes);
1223 // forward buffer past the last Roaring Bitmap
1224 size_t tz = read_var.getSizeInBytes(true);
1225 buf += tz;
1226 maxbytes -= tz;
1227 result.emplaceOrInsert(key, std::move(read_var));
1228 }
1229 return result;
1230 }
1231
1239 size_t getSizeInBytes(bool portable = true) const {
1240 // start with, respectively, map size and size of keys for each map
1241 // entry
1242 return std::accumulate(
1243 roarings.cbegin(), roarings.cend(),
1244 sizeof(uint64_t) + roarings.size() * sizeof(uint32_t),
1245 [=](size_t previous,
1246 const std::pair<const uint32_t, Roaring> &map_entry) {
1247 // add in bytes used by each Roaring
1248 return previous + map_entry.second.getSizeInBytes(portable);
1249 });
1250 }
1251
1252 static const Roaring64Map frozenView(const char *buf) {
1253 // size of bitmap buffer and key
1254 const size_t metadata_size = sizeof(size_t) + sizeof(uint32_t);
1255
1256 Roaring64Map result;
1257
1258 // get map size
1259 uint64_t map_size;
1260 memcpy(&map_size, buf, sizeof(uint64_t));
1261 buf += sizeof(uint64_t);
1262
1263 for (uint64_t lcv = 0; lcv < map_size; lcv++) {
1264 // pad to 32 bytes minus the metadata size
1265 while (((uintptr_t)buf + metadata_size) % 32 != 0) buf++;
1266
1267 // get bitmap size
1268 size_t len;
1269 memcpy(&len, buf, sizeof(size_t));
1270 buf += sizeof(size_t);
1271
1272 // get map key
1273 uint32_t key;
1274 memcpy(&key, buf, sizeof(uint32_t));
1275 buf += sizeof(uint32_t);
1276
1277 // read map value Roaring
1278 const Roaring read = Roaring::frozenView(buf, len);
1279 result.emplaceOrInsert(key, read);
1280
1281 // forward buffer past the last Roaring Bitmap
1282 buf += len;
1283 }
1284 return result;
1285 }
1286
1287 static const Roaring64Map portableDeserializeFrozen(const char *buf) {
1288 Roaring64Map result;
1289 // get map size
1290 uint64_t map_size;
1291 std::memcpy(&map_size, buf, sizeof(uint64_t));
1292 buf += sizeof(uint64_t);
1293 for (uint64_t lcv = 0; lcv < map_size; lcv++) {
1294 // get map key
1295 uint32_t key;
1296 std::memcpy(&key, buf, sizeof(uint32_t));
1297 buf += sizeof(uint32_t);
1298 // read map value Roaring
1300 // forward buffer past the last Roaring bitmap
1301 buf += read_var.getSizeInBytes(true);
1302 result.emplaceOrInsert(key, std::move(read_var));
1303 }
1304 return result;
1305 }
1306
1307 // As with serialized 64-bit bitmaps, 64-bit frozen bitmaps are serialized
1308 // by concatenating one or more Roaring::write output buffers with the
1309 // preceeding map key. Unlike standard bitmap serialization, frozen bitmaps
1310 // must be 32-byte aligned and requires a buffer length to parse. As a
1311 // result, each concatenated output of Roaring::writeFrozen is preceeded by
1312 // padding, the buffer size (size_t), and the map key (uint32_t). The
1313 // padding is used to ensure 32-byte alignment, but since it is followed by
1314 // the buffer size and map key, it actually pads to `(x - sizeof(size_t) +
1315 // sizeof(uint32_t)) mod 32` to leave room for the metadata.
1316 void writeFrozen(char *buf) const {
1317 // size of bitmap buffer and key
1318 const size_t metadata_size = sizeof(size_t) + sizeof(uint32_t);
1319
1320 // push map size
1321 uint64_t map_size = roarings.size();
1322 memcpy(buf, &map_size, sizeof(uint64_t));
1323 buf += sizeof(uint64_t);
1324
1325 for (auto &map_entry : roarings) {
1326 size_t frozenSizeInBytes = map_entry.second.getFrozenSizeInBytes();
1327
1328 // pad to 32 bytes minus the metadata size
1329 while (((uintptr_t)buf + metadata_size) % 32 != 0) buf++;
1330
1331 // push bitmap size
1332 memcpy(buf, &frozenSizeInBytes, sizeof(size_t));
1333 buf += sizeof(size_t);
1334
1335 // push map key
1336 memcpy(buf, &map_entry.first, sizeof(uint32_t));
1337 buf += sizeof(uint32_t);
1338
1339 // push map value Roaring
1340 map_entry.second.writeFrozen(buf);
1341 buf += map_entry.second.getFrozenSizeInBytes();
1342 }
1343 }
1344
1345 size_t getFrozenSizeInBytes() const {
1346 // size of bitmap size and map key
1347 const size_t metadata_size = sizeof(size_t) + sizeof(uint32_t);
1348 size_t ret = 0;
1349
1350 // map size
1351 ret += sizeof(uint64_t);
1352
1353 for (auto &map_entry : roarings) {
1354 // pad to 32 bytes minus the metadata size
1355 while ((ret + metadata_size) % 32 != 0) ret++;
1356 ret += metadata_size;
1357
1358 // frozen bitmaps must be 32-byte aligned
1359 ret += map_entry.second.getFrozenSizeInBytes();
1360 }
1361 return ret;
1362 }
1363
1374 return Roaring64Map(*this) &= o;
1375 }
1376
1382 return Roaring64Map(*this) -= o;
1383 }
1384
1390 return Roaring64Map(*this) |= o;
1391 }
1392
1398 return Roaring64Map(*this) ^= o;
1399 }
1400
1404 void setCopyOnWrite(bool val) {
1405 if (copyOnWrite == val) return;
1406 copyOnWrite = val;
1407 std::for_each(roarings.begin(), roarings.end(),
1408 [=](std::pair<const uint32_t, Roaring> &map_entry) {
1409 map_entry.second.setCopyOnWrite(val);
1410 });
1411 }
1412
1417 void printf() const {
1418 auto sink = [](const std::string &s) { fputs(s.c_str(), stdout); };
1419 printToSink(sink);
1420 sink("\n");
1421 }
1422
1426 std::string toString() const {
1427 std::string result;
1428 auto sink = [&result](const std::string &s) { result += s; };
1429 printToSink(sink);
1430 return result;
1431 }
1432
1436 bool getCopyOnWrite() const { return copyOnWrite; }
1437
1442 static Roaring64Map fastunion(size_t n, const Roaring64Map **inputs) {
1443 // The strategy here is to basically do a "group by" operation.
1444 // We group the input roarings by key, do a 32-bit
1445 // roaring_bitmap_or_many on each group, and collect the results.
1446 // We accomplish the "group by" operation using a priority queue, which
1447 // tracks the next key for each of our input maps. At each step, our
1448 // algorithm takes the next subset of maps that share the same next key,
1449 // runs roaring_bitmap_or_many on those bitmaps, and then advances the
1450 // current_iter on all the affected entries and then repeats.
1451
1452 // There is an entry in our priority queue for each of the 'n' inputs.
1453 // For a given Roaring64Map, we look at its underlying 'roarings'
1454 // std::map, and take its begin() and end(). This forms our half-open
1455 // interval [current_iter, end_iter), which we keep in the priority
1456 // queue as a pq_entry. These entries are updated (removed and then
1457 // reinserted with the pq_entry.iterator field advanced by one step) as
1458 // our algorithm progresses. But when a given interval becomes empty
1459 // (i.e. pq_entry.iterator == pq_entry.end) it is not returned to the
1460 // priority queue.
1461 struct pq_entry {
1462 roarings_t::const_iterator iterator;
1463 roarings_t::const_iterator end;
1464 };
1465
1466 // Custom comparator for the priority queue.
1467 auto pq_comp = [](const pq_entry &lhs, const pq_entry &rhs) {
1468 auto left_key = lhs.iterator->first;
1469 auto right_key = rhs.iterator->first;
1470
1471 // We compare in the opposite direction than normal because priority
1472 // queues normally order from largest to smallest, but we want
1473 // smallest to largest.
1474 return left_key > right_key;
1475 };
1476
1477 // Create and populate the priority queue.
1478 std::priority_queue<pq_entry, std::vector<pq_entry>, decltype(pq_comp)>
1479 pq(pq_comp);
1480 for (size_t i = 0; i < n; ++i) {
1481 const auto &roarings = inputs[i]->roarings;
1482 if (roarings.begin() != roarings.end()) {
1483 pq.push({roarings.begin(), roarings.end()});
1484 }
1485 }
1486
1487 // A reusable vector that holds the pointers to the inner bitmaps that
1488 // we pass to the underlying 32-bit fastunion operation.
1489 std::vector<const roaring_bitmap_t *> group_bitmaps;
1490
1491 // Summary of the algorithm:
1492 // 1. While the priority queue is not empty:
1493 // A. Get its lowest key. Call this group_key
1494 // B. While the lowest entry in the priority queue has a key equal to
1495 // group_key:
1496 // 1. Remove this entry (the pair {current_iter, end_iter}) from
1497 // the priority queue.
1498 // 2. Add the bitmap pointed to by current_iter to a list of
1499 // 32-bit bitmaps to process.
1500 // 3. Advance current_iter. Now it will point to a bitmap entry
1501 // with some key greater than group_key (or it will point to
1502 // end()).
1503 // 4. If current_iter != end_iter, reinsert the pair into the
1504 // priority queue.
1505 // C. Invoke the 32-bit roaring_bitmap_or_many() and add to result
1506 Roaring64Map result;
1507 while (!pq.empty()) {
1508 // Find the next key (the lowest key) in the priority queue.
1509 auto group_key = pq.top().iterator->first;
1510
1511 // The purpose of the inner loop is to gather all the inner bitmaps
1512 // that share "group_key" into "group_bitmaps" so that they can be
1513 // fed to roaring_bitmap_or_many(). While we are doing this, we
1514 // advance those iterators to their next value and reinsert them
1515 // into the priority queue (unless they reach their end).
1516 group_bitmaps.clear();
1517 while (!pq.empty()) {
1518 auto candidate_current_iter = pq.top().iterator;
1519 auto candidate_end_iter = pq.top().end;
1520
1521 auto candidate_key = candidate_current_iter->first;
1522 const auto &candidate_bitmap = candidate_current_iter->second;
1523
1524 // This element will either be in the group (having
1525 // key == group_key) or it will not be in the group (having
1526 // key > group_key). (Note it cannot have key < group_key
1527 // because of the ordered nature of the priority queue itself
1528 // and the ordered nature of all the underlying roaring maps).
1529 if (candidate_key != group_key) {
1530 // This entry, and (thanks to the nature of the priority
1531 // queue) all other entries as well, are all greater than
1532 // group_key, so we're done collecting elements for the
1533 // current group. Because of the way this loop was written,
1534 // the group will will always contain at least one element.
1535 break;
1536 }
1537
1538 group_bitmaps.push_back(&candidate_bitmap.roaring);
1539 // Remove this entry from the priority queue. Note this
1540 // invalidates pq.top() so make sure you don't have any dangling
1541 // references to it.
1542 pq.pop();
1543
1544 // Advance 'candidate_current_iter' and insert a new entry
1545 // {candidate_current_iter, candidate_end_iter} into the
1546 // priority queue (unless it has reached its end).
1547 ++candidate_current_iter;
1548 if (candidate_current_iter != candidate_end_iter) {
1549 pq.push({candidate_current_iter, candidate_end_iter});
1550 }
1551 }
1552
1553 // Use the fast inner union to combine these.
1554 auto *inner_result = roaring_bitmap_or_many(group_bitmaps.size(),
1555 group_bitmaps.data());
1556 // Insert the 32-bit result at end of the 'roarings' map of the
1557 // result we are building.
1558 result.roarings.insert(
1559 result.roarings.end(),
1560 std::make_pair(group_key, Roaring(inner_result)));
1561 }
1562 return result;
1563 }
1564
1569
1579 const_iterator begin() const;
1580
1585 const_iterator end() const;
1586
1587 private:
1588 typedef std::map<uint32_t, Roaring> roarings_t;
1589 roarings_t roarings{}; // The empty constructor silences warnings from
1590 // pedantic static analyzers.
1591 bool copyOnWrite{false};
1592 static constexpr uint32_t highBytes(const uint64_t in) {
1593 return uint32_t(in >> 32);
1594 }
1595 static constexpr uint32_t lowBytes(const uint64_t in) {
1596 return uint32_t(in);
1597 }
1598 static constexpr uint64_t uniteBytes(const uint32_t highBytes,
1599 const uint32_t lowBytes) {
1600 return (uint64_t(highBytes) << 32) | uint64_t(lowBytes);
1601 }
1602 // this is needed to tolerate gcc's C++11 libstdc++ lacking emplace
1603 // prior to version 4.8
1604 void emplaceOrInsert(const uint32_t key, const Roaring &value) {
1605#if defined(__GLIBCXX__) && __GLIBCXX__ < 20130322
1606 roarings.insert(std::make_pair(key, value));
1607#else
1608 roarings.emplace(std::make_pair(key, value));
1609#endif
1610 }
1611
1612 void emplaceOrInsert(const uint32_t key, Roaring &&value) {
1613#if defined(__GLIBCXX__) && __GLIBCXX__ < 20130322
1614 roarings.insert(std::make_pair(key, std::move(value)));
1615#else
1616 roarings.emplace(key, std::move(value));
1617#endif
1618 }
1619
1620 /*
1621 * Look up 'key' in the 'roarings' map. If it does not exist, create it.
1622 * Also, set its copyOnWrite flag to 'copyOnWrite'. Then return a reference
1623 * to the (already existing or newly created) inner bitmap.
1624 */
1625 Roaring &lookupOrCreateInner(uint32_t key) {
1626 auto &bitmap = roarings[key];
1627 bitmap.setCopyOnWrite(copyOnWrite);
1628 return bitmap;
1629 }
1630
1634 void printToSink(
1635 const std::function<void(const std::string &)> &sink) const {
1636 sink("{");
1637
1638 // Storage for snprintf. Big enough to store the decimal representation
1639 // of the largest uint64_t value and trailing \0.
1640 char buffer[32];
1641 const char *separator = "";
1642 // Reusable, and therefore avoids many repeated heap allocations.
1643 std::string callback_string;
1644 for (const auto &entry : roarings) {
1645 auto high_bits = entry.first;
1646 const auto &bitmap = entry.second;
1647 for (const auto low_bits : bitmap) {
1648 auto value = uniteBytes(high_bits, low_bits);
1649 snprintf(buffer, sizeof(buffer), "%" PRIu64, value);
1650 callback_string = separator;
1651 callback_string.append(buffer);
1652 sink(callback_string);
1653 separator = ",";
1654 }
1655 }
1656 sink("}");
1657 }
1658
1665 roarings_t::iterator ensureRangePopulated(uint32_t start_high,
1666 uint32_t end_high) {
1667 if (start_high > end_high) {
1668 ROARING_TERMINATE("Logic error: start_high > end_high");
1669 }
1670 // next_populated_iter points to the first entry in the outer map with
1671 // key >= start_high, or end().
1672 auto next_populated_iter = roarings.lower_bound(start_high);
1673
1674 // Use uint64_t to avoid an infinite loop when end_high == uint32_max.
1675 roarings_t::iterator start_iter{}; // Definitely assigned in loop.
1676 for (uint64_t slot = start_high; slot <= end_high; ++slot) {
1677 roarings_t::iterator slot_iter;
1678 if (next_populated_iter != roarings.end() &&
1679 next_populated_iter->first == slot) {
1680 // 'slot' index has caught up to next_populated_iter.
1681 // Note it here and advance next_populated_iter.
1682 slot_iter = next_populated_iter++;
1683 } else {
1684 // 'slot' index has not yet caught up to next_populated_iter.
1685 // Make a fresh entry {key = 'slot', value = Roaring()}, insert
1686 // it just prior to next_populated_iter, and set its copy
1687 // on write flag. We take pains to use emplace_hint and
1688 // piecewise_construct to minimize effort.
1689 slot_iter = roarings.emplace_hint(
1690 next_populated_iter, std::piecewise_construct,
1691 std::forward_as_tuple(uint32_t(slot)),
1692 std::forward_as_tuple());
1693 auto &bitmap = slot_iter->second;
1694 bitmap.setCopyOnWrite(copyOnWrite);
1695 }
1696
1697 // Make a note of the iterator of the starting slot. It will be
1698 // needed for the return value.
1699 if (slot == start_high) {
1700 start_iter = slot_iter;
1701 }
1702 }
1703 return start_iter;
1704 }
1705
1710 void eraseIfEmpty(roarings_t::iterator iter) {
1711 const auto &bitmap = iter->second;
1712 if (bitmap.isEmpty()) {
1713 roarings.erase(iter);
1714 }
1715 }
1716};
1717
1724 public:
1725 typedef std::bidirectional_iterator_tag iterator_category;
1726 typedef uint64_t *pointer;
1727 typedef uint64_t &reference;
1728 typedef uint64_t value_type;
1729 typedef int64_t difference_type;
1731
1733 bool exhausted = false)
1734 : p(&parent.roarings) {
1735 if (exhausted || parent.roarings.empty()) {
1736 map_iter = p->cend();
1737 } else {
1738 map_iter = parent.roarings.cbegin();
1739 roaring_iterator_init(&map_iter->second.roaring, &i);
1740 while (!i.has_value) {
1741 map_iter++;
1742 if (map_iter == p->cend()) return;
1743 roaring_iterator_init(&map_iter->second.roaring, &i);
1744 }
1745 }
1746 }
1747
1752 return Roaring64Map::uniteBytes(map_iter->first, i.current_value);
1753 }
1754
1755 bool operator<(const type_of_iterator &o) const {
1756 if (map_iter == p->cend()) return false;
1757 if (o.map_iter == o.p->cend()) return true;
1758 return **this < *o;
1759 }
1760
1761 bool operator<=(const type_of_iterator &o) const {
1762 if (o.map_iter == o.p->cend()) return true;
1763 if (map_iter == p->cend()) return false;
1764 return **this <= *o;
1765 }
1766
1767 bool operator>(const type_of_iterator &o) const {
1768 if (o.map_iter == o.p->cend()) return false;
1769 if (map_iter == p->cend()) return true;
1770 return **this > *o;
1771 }
1772
1773 bool operator>=(const type_of_iterator &o) const {
1774 if (map_iter == p->cend()) return true;
1775 if (o.map_iter == o.p->cend()) return false;
1776 return **this >= *o;
1777 }
1778
1779 type_of_iterator &operator++() { // ++i, must returned inc. value
1780 if (i.has_value == true) roaring_uint32_iterator_advance(&i);
1781 while (!i.has_value) {
1782 ++map_iter;
1783 if (map_iter == p->cend()) return *this;
1784 roaring_iterator_init(&map_iter->second.roaring, &i);
1785 }
1786 return *this;
1787 }
1788
1789 type_of_iterator operator++(int) { // i++, must return orig. value
1792 while (!i.has_value) {
1793 ++map_iter;
1794 if (map_iter == p->cend()) return orig;
1795 roaring_iterator_init(&map_iter->second.roaring, &i);
1796 }
1797 return orig;
1798 }
1799
1805 map_iter = p->lower_bound(Roaring64Map::highBytes(x));
1806 if (map_iter != p->cend()) {
1807 roaring_iterator_init(&map_iter->second.roaring, &i);
1808 if (map_iter->first == Roaring64Map::highBytes(x)) {
1810 &i, Roaring64Map::lowBytes(x)))
1811 return true;
1812 ++map_iter;
1813 if (map_iter == p->cend()) return false;
1814 roaring_iterator_init(&map_iter->second.roaring, &i);
1815 }
1816 return true;
1817 }
1818 return false;
1819 }
1820
1822 CROARING_DEPRECATED bool move(const value_type &x) {
1823 return move_equalorlarger(x);
1824 }
1825
1826 type_of_iterator &operator--() { // --i, must return dec.value
1827 if (map_iter == p->cend()) {
1828 --map_iter;
1829 roaring_iterator_init_last(&map_iter->second.roaring, &i);
1830 if (i.has_value) return *this;
1831 }
1832
1834 while (!i.has_value) {
1835 if (map_iter == p->cbegin()) return *this;
1836 map_iter--;
1837 roaring_iterator_init_last(&map_iter->second.roaring, &i);
1838 }
1839 return *this;
1840 }
1841
1842 type_of_iterator operator--(int) { // i--, must return orig. value
1844 if (map_iter == p->cend()) {
1845 --map_iter;
1846 roaring_iterator_init_last(&map_iter->second.roaring, &i);
1847 return orig;
1848 }
1849
1851 while (!i.has_value) {
1852 if (map_iter == p->cbegin()) return orig;
1853 map_iter--;
1854 roaring_iterator_init_last(&map_iter->second.roaring, &i);
1855 }
1856 return orig;
1857 }
1858
1860 if (map_iter == p->cend() && o.map_iter == o.p->cend()) return true;
1861 if (o.map_iter == o.p->cend()) return false;
1862 return **this == *o;
1863 }
1864
1866 if (map_iter == p->cend() && o.map_iter == o.p->cend()) return false;
1867 if (o.map_iter == o.p->cend()) return true;
1868 return **this != *o;
1869 }
1870
1871 private:
1872 const std::map<uint32_t, Roaring> *p{nullptr};
1873 std::map<uint32_t, Roaring>::const_iterator
1874 map_iter{}; // The empty constructor silences warnings from pedantic
1875 // static analyzers.
1876 api::roaring_uint32_iterator_t
1877 i{}; // The empty constructor silences warnings from pedantic static
1878 // analyzers.
1879};
1880
1884
1888
1889} // namespace roaring
1890
1891#endif /* INCLUDE_ROARING_64_MAP_HH_ */
bool operator<(const type_of_iterator &o) const
bool operator<=(const type_of_iterator &o) const
bool operator!=(const Roaring64MapSetBitBiDirectionalIterator &o) const
Roaring64MapSetBitBiDirectionalIterator(const Roaring64Map &parent, bool exhausted=false)
bool operator>(const type_of_iterator &o) const
CROARING_DEPRECATED bool move(const value_type &x)
std::bidirectional_iterator_tag iterator_category
bool operator==(const Roaring64MapSetBitBiDirectionalIterator &o) const
Roaring64MapSetBitBiDirectionalIterator type_of_iterator
bool operator>=(const type_of_iterator &o) const
void addMany(size_t n_args, const uint32_t *vals)
void flip(uint64_t min, uint64_t max)
friend class Roaring64MapSetBitBiDirectionalIterator
Roaring64Map(size_t n, const uint64_t *data)
uint64_t rank(uint64_t x) const
size_t getFrozenSizeInBytes() const
Roaring64Map operator-(const Roaring64Map &o) const
void flipClosed(uint32_t min, uint32_t max)
bool contains(uint32_t x) const
Roaring64Map & operator^=(const Roaring64Map &other)
uint64_t cardinality() const
const_iterator end() const
void remove(uint64_t x)
Roaring64Map & operator|=(const Roaring64Map &other)
bool contains(uint64_t x) const
Roaring64Map(size_t n, const uint32_t *data)
std::string toString() const
Roaring64Map(const Roaring &r)
Roaring64MapSetBitBiDirectionalIterator const_iterator
bool operator==(const Roaring64Map &r) const
uint64_t maximum() const
bool isSubset(const Roaring64Map &r) const
const_iterator begin() const
size_t write(char *buf, bool portable=true) const
void removeRangeClosed(uint64_t min, uint64_t max)
Roaring64Map & operator-=(const Roaring64Map &other)
bool removeChecked(uint32_t x)
Roaring64Map operator|(const Roaring64Map &o) const
bool addChecked(uint64_t x)
void addRangeClosed(uint64_t min, uint64_t max)
bool getCopyOnWrite() const
Roaring64Map(Roaring &&r)
static Roaring64Map readSafe(const char *buf, size_t maxbytes)
void add(uint32_t x)
static Roaring64Map fastunion(size_t n, const Roaring64Map **inputs)
Roaring64Map & operator=(Roaring64Map &&r) noexcept=default
Roaring64Map & operator=(std::initializer_list< uint64_t > l)
Roaring64Map(const Roaring64Map &r)=default
Roaring64Map operator^(const Roaring64Map &o) const
static const Roaring64Map frozenView(const char *buf)
static Roaring64Map read(const char *buf, bool portable=true)
void addMany(size_t n_args, const uint64_t *vals)
static Roaring64Map bitmapOfList(std::initializer_list< uint64_t > l)
void addRange(uint64_t min, uint64_t max)
Roaring64Map operator&(const Roaring64Map &o) const
static Roaring64Map bitmapOf(size_t n...)
bool removeChecked(uint64_t x)
Roaring64Map(roaring_bitmap_t *s)
uint64_t minimum() const
Roaring64MapSetBitBiDirectionalIterator const_bidirectional_iterator
void setCopyOnWrite(bool val)
Roaring64Map(Roaring64Map &&r) noexcept=default
void flipClosed(uint64_t min, uint64_t max)
void toUint64Array(uint64_t *ans) const
static const Roaring64Map portableDeserializeFrozen(const char *buf)
size_t getSizeInBytes(bool portable=true) const
Roaring64Map & operator&=(const Roaring64Map &other)
void remove(uint32_t x)
void removeRange(uint64_t min, uint64_t max)
void iterate(api::roaring_iterator64 iterator, void *ptr) const
void removeRangeClosed(uint32_t min, uint32_t max)
void swap(Roaring64Map &r)
void addRangeClosed(uint32_t min, uint32_t max)
void add(uint64_t x)
bool select(uint64_t rank, uint64_t *element) const
void writeFrozen(char *buf) const
Roaring64Map & operator=(const Roaring64Map &r)=default
Roaring64Map(std::initializer_list< uint64_t > l)
bool isStrictSubset(const Roaring64Map &r) const
bool addChecked(uint32_t x)
int64_t getIndex(uint64_t x) const
static Roaring readSafe(const char *buf, size_t maxbytes)
Definition roaring.hh:680
bool addChecked(uint32_t x) noexcept
Definition roaring.hh:207
void addRangeClosed(const uint32_t min, const uint32_t max) noexcept
Definition roaring.hh:221
static Roaring read(const char *buf, bool portable=true)
Definition roaring.hh:647
void add(uint32_t x) noexcept
Definition roaring.hh:200
void addBulk(BulkContext &context, uint32_t x) noexcept
Definition roaring.hh:240
void addMany(size_t n_args, const uint32_t *vals) noexcept
Definition roaring.hh:228
static const Roaring frozenView(const char *buf, size_t length)
Definition roaring.hh:709
static const Roaring portableDeserializeFrozen(const char *buf)
Definition roaring.hh:724
size_t getSizeInBytes(bool portable=true) const noexcept
Definition roaring.hh:697
Roaring64MapSetBitBiDirectionalIterator Roaring64MapSetBitForwardIterator
void roaring_iterator_init_last(const roaring_bitmap_t *r, roaring_uint32_iterator_t *newit)
bool roaring_iterate64(const roaring_bitmap_t *r, roaring_iterator64 iterator, uint64_t high_bits, void *ptr)
void roaring_iterator_init(const roaring_bitmap_t *r, roaring_uint32_iterator_t *newit)
roaring_bitmap_t * roaring_bitmap_or_many(size_t number, const roaring_bitmap_t **rs)
bool roaring_uint32_iterator_move_equalorlarger(roaring_uint32_iterator_t *it, uint32_t val)
bool roaring_uint32_iterator_previous(roaring_uint32_iterator_t *it)
bool roaring_uint32_iterator_advance(roaring_uint32_iterator_t *it)
#define ROARING_TERMINATE(_s)
Definition roaring.hh:31