EIC code displayed by LXR master/​include/​llvm/​ADT/​CoalescingBitVector.h	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2026-05-10 08:43:03

 //===- llvm/ADT/CoalescingBitVector.h - A coalescing bitvector --*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// A bitvector that uses an IntervalMap to coalesce adjacent elements
 /// into intervals.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_COALESCINGBITVECTOR_H
 #define LLVM_ADT_COALESCINGBITVECTOR_H
 
 #include "llvm/ADT/IntervalMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 #include <initializer_list>
 
 namespace llvm {
 
 /// A bitvector that, under the hood, relies on an IntervalMap to coalesce
 /// elements into intervals. Good for representing sets which predominantly
 /// contain contiguous ranges. Bad for representing sets with lots of gaps
 /// between elements.
 ///
 /// Compared to SparseBitVector, CoalescingBitVector offers more predictable
 /// performance for non-sequential find() operations.
 ///
 /// \tparam IndexT - The type of the index into the bitvector.
 template <typename IndexT> class CoalescingBitVector {
   static_assert(std::is_unsigned<IndexT>::value,
                 "Index must be an unsigned integer.");
 
   using ThisT = CoalescingBitVector<IndexT>;
 
   /// An interval map for closed integer ranges. The mapped values are unused.
   using MapT = IntervalMap<IndexT, char>;
 
   using UnderlyingIterator = typename MapT::const_iterator;
 
   using IntervalT = std::pair<IndexT, IndexT>;
 
 public:
   using Allocator = typename MapT::Allocator;
 
   /// Construct by passing in a CoalescingBitVector<IndexT>::Allocator
   /// reference.
   CoalescingBitVector(Allocator &Alloc)
       : Alloc(&Alloc), Intervals(Alloc) {}
 
   /// \name Copy/move constructors and assignment operators.
   /// @{
 
   CoalescingBitVector(const ThisT &Other)
       : Alloc(Other.Alloc), Intervals(*Other.Alloc) {
     set(Other);
   }
 
   ThisT &operator=(const ThisT &Other) {
     clear();
     set(Other);
     return *this;
   }
 
   CoalescingBitVector(ThisT &&Other) = delete;
   ThisT &operator=(ThisT &&Other) = delete;
 
   /// @}
 
   /// Clear all the bits.
   void clear() { Intervals.clear(); }
 
   /// Check whether no bits are set.
   bool empty() const { return Intervals.empty(); }
 
   /// Count the number of set bits.
   unsigned count() const {
     unsigned Bits = 0;
     for (auto It = Intervals.begin(), End = Intervals.end(); It != End; ++It)
       Bits += 1 + It.stop() - It.start();
     return Bits;
   }
 
   /// Set the bit at \p Index.
   ///
   /// This method does /not/ support setting a bit that has already been set,
   /// for efficiency reasons. If possible, restructure your code to not set the
   /// same bit multiple times, or use \ref test_and_set.
   void set(IndexT Index) {
     assert(!test(Index) && "Setting already-set bits not supported/efficient, "
                            "IntervalMap will assert");
     insert(Index, Index);
   }
 
   /// Set the bits set in \p Other.
   ///
   /// This method does /not/ support setting already-set bits, see \ref set
   /// for the rationale. For a safe set union operation, use \ref operator|=.
   void set(const ThisT &Other) {
     for (auto It = Other.Intervals.begin(), End = Other.Intervals.end();
          It != End; ++It)
       insert(It.start(), It.stop());
   }
 
   /// Set the bits at \p Indices. Used for testing, primarily.
   void set(std::initializer_list<IndexT> Indices) {
     for (IndexT Index : Indices)
       set(Index);
   }
 
   /// Check whether the bit at \p Index is set.
   bool test(IndexT Index) const {
     const auto It = Intervals.find(Index);
     if (It == Intervals.end())
       return false;
     assert(It.stop() >= Index && "Interval must end after Index");
     return It.start() <= Index;
   }
 
   /// Set the bit at \p Index. Supports setting an already-set bit.
   void test_and_set(IndexT Index) {
     if (!test(Index))
       set(Index);
   }
 
   /// Reset the bit at \p Index. Supports resetting an already-unset bit.
   void reset(IndexT Index) {
     auto It = Intervals.find(Index);
     if (It == Intervals.end())
       return;
 
     // Split the interval containing Index into up to two parts: one from
     // [Start, Index-1] and another from [Index+1, Stop]. If Index is equal to
     // either Start or Stop, we create one new interval. If Index is equal to
     // both Start and Stop, we simply erase the existing interval.
     IndexT Start = It.start();
     if (Index < Start)
       // The index was not set.
       return;
     IndexT Stop = It.stop();
     assert(Index <= Stop && "Wrong interval for index");
     It.erase();
     if (Start < Index)
       insert(Start, Index - 1);
     if (Index < Stop)
       insert(Index + 1, Stop);
   }
 
   /// Set union. If \p RHS is guaranteed to not overlap with this, \ref set may
   /// be a faster alternative.
   void operator|=(const ThisT &RHS) {
     // Get the overlaps between the two interval maps.
     SmallVector<IntervalT, 8> Overlaps;
     getOverlaps(RHS, Overlaps);
 
     // Insert the non-overlapping parts of all the intervals from RHS.
     for (auto It = RHS.Intervals.begin(), End = RHS.Intervals.end();
          It != End; ++It) {
       IndexT Start = It.start();
       IndexT Stop = It.stop();
       SmallVector<IntervalT, 8> NonOverlappingParts;
       getNonOverlappingParts(Start, Stop, Overlaps, NonOverlappingParts);
       for (IntervalT AdditivePortion : NonOverlappingParts)
         insert(AdditivePortion.first, AdditivePortion.second);
     }
   }
 
   /// Set intersection.
   void operator&=(const ThisT &RHS) {
     // Get the overlaps between the two interval maps (i.e. the intersection).
     SmallVector<IntervalT, 8> Overlaps;
     getOverlaps(RHS, Overlaps);
     // Rebuild the interval map, including only the overlaps.
     clear();
     for (IntervalT Overlap : Overlaps)
       insert(Overlap.first, Overlap.second);
   }
 
   /// Reset all bits present in \p Other.
   void intersectWithComplement(const ThisT &Other) {
     SmallVector<IntervalT, 8> Overlaps;
     if (!getOverlaps(Other, Overlaps)) {
       // If there is no overlap with Other, the intersection is empty.
       return;
     }
 
     // Delete the overlapping intervals. Split up intervals that only partially
     // intersect an overlap.
     for (IntervalT Overlap : Overlaps) {
       IndexT OlapStart, OlapStop;
       std::tie(OlapStart, OlapStop) = Overlap;
 
       auto It = Intervals.find(OlapStart);
       IndexT CurrStart = It.start();
       IndexT CurrStop = It.stop();
       assert(CurrStart <= OlapStart && OlapStop <= CurrStop &&
              "Expected some intersection!");
 
       // Split the overlap interval into up to two parts: one from [CurrStart,
       // OlapStart-1] and another from [OlapStop+1, CurrStop]. If OlapStart is
       // equal to CurrStart, the first split interval is unnecessary. Ditto for
       // when OlapStop is equal to CurrStop, we omit the second split interval.
       It.erase();
       if (CurrStart < OlapStart)
         insert(CurrStart, OlapStart - 1);
       if (OlapStop < CurrStop)
         insert(OlapStop + 1, CurrStop);
     }
   }
 
   bool operator==(const ThisT &RHS) const {
     // We cannot just use std::equal because it checks the dereferenced values
     // of an iterator pair for equality, not the iterators themselves. In our
     // case that results in comparison of the (unused) IntervalMap values.
     auto ItL = Intervals.begin();
     auto ItR = RHS.Intervals.begin();
     while (ItL != Intervals.end() && ItR != RHS.Intervals.end() &&
            ItL.start() == ItR.start() && ItL.stop() == ItR.stop()) {
       ++ItL;
       ++ItR;
     }
     return ItL == Intervals.end() && ItR == RHS.Intervals.end();
   }
 
   bool operator!=(const ThisT &RHS) const { return !operator==(RHS); }
 
   class const_iterator {
     friend class CoalescingBitVector;
 
   public:
     using iterator_category = std::forward_iterator_tag;
     using value_type = IndexT;
     using difference_type = std::ptrdiff_t;
     using pointer = value_type *;
     using reference = value_type &;
 
   private:
     // For performance reasons, make the offset at the end different than the
     // one used in \ref begin, to optimize the common `It == end()` pattern.
     static constexpr unsigned kIteratorAtTheEndOffset = ~0u;
 
     UnderlyingIterator MapIterator;
     unsigned OffsetIntoMapIterator = 0;
 
     // Querying the start/stop of an IntervalMap iterator can be very expensive.
     // Cache these values for performance reasons.
     IndexT CachedStart = IndexT();
     IndexT CachedStop = IndexT();
 
     void setToEnd() {
       OffsetIntoMapIterator = kIteratorAtTheEndOffset;
       CachedStart = IndexT();
       CachedStop = IndexT();
     }
 
     /// MapIterator has just changed, reset the cached state to point to the
     /// start of the new underlying iterator.
     void resetCache() {
       if (MapIterator.valid()) {
         OffsetIntoMapIterator = 0;
         CachedStart = MapIterator.start();
         CachedStop = MapIterator.stop();
       } else {
         setToEnd();
       }
     }
 
     /// Advance the iterator to \p Index, if it is contained within the current
     /// interval. The public-facing method which supports advancing past the
     /// current interval is \ref advanceToLowerBound.
     void advanceTo(IndexT Index) {
       assert(Index <= CachedStop && "Cannot advance to OOB index");
       if (Index < CachedStart)
         // We're already past this index.
         return;
       OffsetIntoMapIterator = Index - CachedStart;
     }
 
     const_iterator(UnderlyingIterator MapIt) : MapIterator(MapIt) {
       resetCache();
     }
 
   public:
     const_iterator() { setToEnd(); }
 
     bool operator==(const const_iterator &RHS) const {
       // Do /not/ compare MapIterator for equality, as this is very expensive.
       // The cached start/stop values make that check unnecessary.
       return std::tie(OffsetIntoMapIterator, CachedStart, CachedStop) ==
              std::tie(RHS.OffsetIntoMapIterator, RHS.CachedStart,
                       RHS.CachedStop);
     }
 
     bool operator!=(const const_iterator &RHS) const {
       return !operator==(RHS);
     }
 
     IndexT operator*() const { return CachedStart + OffsetIntoMapIterator; }
 
     const_iterator &operator++() { // Pre-increment (++It).
       if (CachedStart + OffsetIntoMapIterator < CachedStop) {
         // Keep going within the current interval.
         ++OffsetIntoMapIterator;
       } else {
         // We reached the end of the current interval: advance.
         ++MapIterator;
         resetCache();
       }
       return *this;
     }
 
     const_iterator operator++(int) { // Post-increment (It++).
       const_iterator tmp = *this;
       operator++();
       return tmp;
     }
 
     /// Advance the iterator to the first set bit AT, OR AFTER, \p Index. If
     /// no such set bit exists, advance to end(). This is like std::lower_bound.
     /// This is useful if \p Index is close to the current iterator position.
     /// However, unlike \ref find(), this has worst-case O(n) performance.
     void advanceToLowerBound(IndexT Index) {
       if (OffsetIntoMapIterator == kIteratorAtTheEndOffset)
         return;
 
       // Advance to the first interval containing (or past) Index, or to end().
       while (Index > CachedStop) {
         ++MapIterator;
         resetCache();
         if (OffsetIntoMapIterator == kIteratorAtTheEndOffset)
           return;
       }
 
       advanceTo(Index);
     }
   };
 
   const_iterator begin() const { return const_iterator(Intervals.begin()); }
 
   const_iterator end() const { return const_iterator(); }
 
   /// Return an iterator pointing to the first set bit AT, OR AFTER, \p Index.
   /// If no such set bit exists, return end(). This is like std::lower_bound.
   /// This has worst-case logarithmic performance (roughly O(log(gaps between
   /// contiguous ranges))).
   const_iterator find(IndexT Index) const {
     auto UnderlyingIt = Intervals.find(Index);
     if (UnderlyingIt == Intervals.end())
       return end();
     auto It = const_iterator(UnderlyingIt);
     It.advanceTo(Index);
     return It;
   }
 
   /// Return a range iterator which iterates over all of the set bits in the
   /// half-open range [Start, End).
   iterator_range<const_iterator> half_open_range(IndexT Start,
                                                  IndexT End) const {
     assert(Start < End && "Not a valid range");
     auto StartIt = find(Start);
     if (StartIt == end() || *StartIt >= End)
       return {end(), end()};
     auto EndIt = StartIt;
     EndIt.advanceToLowerBound(End);
     return {StartIt, EndIt};
   }
 
   void print(raw_ostream &OS) const {
     OS << "{";
     for (auto It = Intervals.begin(), End = Intervals.end(); It != End;
          ++It) {
       OS << "[" << It.start();
       if (It.start() != It.stop())
         OS << ", " << It.stop();
       OS << "]";
     }
     OS << "}";
   }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   LLVM_DUMP_METHOD void dump() const {
     // LLDB swallows the first line of output after callling dump(). Add
     // newlines before/after the braces to work around this.
     dbgs() << "\n";
     print(dbgs());
     dbgs() << "\n";
   }
 #endif
 
 private:
   void insert(IndexT Start, IndexT End) { Intervals.insert(Start, End, 0); }
 
   /// Record the overlaps between \p this and \p Other in \p Overlaps. Return
   /// true if there is any overlap.
   bool getOverlaps(const ThisT &Other,
                    SmallVectorImpl<IntervalT> &Overlaps) const {
     for (IntervalMapOverlaps<MapT, MapT> I(Intervals, Other.Intervals);
          I.valid(); ++I)
       Overlaps.emplace_back(I.start(), I.stop());
     assert(llvm::is_sorted(Overlaps,
                            [](IntervalT LHS, IntervalT RHS) {
                              return LHS.second < RHS.first;
                            }) &&
            "Overlaps must be sorted");
     return !Overlaps.empty();
   }
 
   /// Given the set of overlaps between this and some other bitvector, and an
   /// interval [Start, Stop] from that bitvector, determine the portions of the
   /// interval which do not overlap with this.
   void getNonOverlappingParts(IndexT Start, IndexT Stop,
                               const SmallVectorImpl<IntervalT> &Overlaps,
                               SmallVectorImpl<IntervalT> &NonOverlappingParts) {
     IndexT NextUncoveredBit = Start;
     for (IntervalT Overlap : Overlaps) {
       IndexT OlapStart, OlapStop;
       std::tie(OlapStart, OlapStop) = Overlap;
 
       // [Start;Stop] and [OlapStart;OlapStop] overlap iff OlapStart <= Stop
       // and Start <= OlapStop.
       bool DoesOverlap = OlapStart <= Stop && Start <= OlapStop;
       if (!DoesOverlap)
         continue;
 
       // Cover the range [NextUncoveredBit, OlapStart). This puts the start of
       // the next uncovered range at OlapStop+1.
       if (NextUncoveredBit < OlapStart)
         NonOverlappingParts.emplace_back(NextUncoveredBit, OlapStart - 1);
       NextUncoveredBit = OlapStop + 1;
       if (NextUncoveredBit > Stop)
         break;
     }
     if (NextUncoveredBit <= Stop)
       NonOverlappingParts.emplace_back(NextUncoveredBit, Stop);
   }
 
   Allocator *Alloc;
   MapT Intervals;
 };
 
 } // namespace llvm
 
 #endif // LLVM_ADT_COALESCINGBITVECTOR_H

This page was automatically generated by the 2.3.7 LXR engine. The LXR team