X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FIntervalMap.h;h=f8843b2a4e507a81de13fd73522e801c95fdf0fc;hb=00552e3875ee5f382db6c98286a241a7d0efe1b8;hp=ae79e845088d3e0d1f6d944b34c789a36374863f;hpb=cb9e08f328892eaf46825d7426216995ca673a67;p=oota-llvm.git diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h index ae79e845088..f8843b2a4e5 100644 --- a/include/llvm/ADT/IntervalMap.h +++ b/include/llvm/ADT/IntervalMap.h @@ -99,8 +99,9 @@ #ifndef LLVM_ADT_INTERVALMAP_H #define LLVM_ADT_INTERVALMAP_H -#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/AlignOf.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/RecyclingAllocator.h" #include @@ -151,6 +152,26 @@ struct IntervalMapInfo { }; +template +struct IntervalMapHalfOpenInfo { + + /// startLess - Return true if x is not in [a;b). + static inline bool startLess(const T &x, const T &a) { + return x < a; + } + + /// stopLess - Return true if x is not in [a;b). + static inline bool stopLess(const T &b, const T &x) { + return b <= x; + } + + /// adjacent - Return true when the intervals [x;a) and [b;y) can coalesce. + static inline bool adjacent(const T &a, const T &b) { + return a == b; + } + +}; + /// IntervalMapImpl - Namespace used for IntervalMap implementation details. /// It should be considered private to the implementation. namespace IntervalMapImpl { @@ -476,7 +497,7 @@ public: NodeRef() {} /// operator bool - Detect a null ref. - operator bool() const { return pip.getOpaqueValue(); } + explicit operator bool() const { return pip.getOpaqueValue(); } /// NodeRef - Create a reference to the node p with n elements. template @@ -592,7 +613,7 @@ public: /// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as /// possible. This may cause the node to grow by 1, or it may cause the node /// to shrink because of coalescing. -/// @param i Starting index = insertFrom(0, size, a) +/// @param Pos Starting index = insertFrom(0, size, a) /// @param Size Number of elements in node. /// @param a Interval start. /// @param b Interval stop. @@ -739,7 +760,7 @@ public: // A Path is used by iterators to represent a position in a B+-tree, and the // path to get there from the root. // -// The Path class also constains the tree navigation code that doesn't have to +// The Path class also contains the tree navigation code that doesn't have to // be templatized. // //===----------------------------------------------------------------------===// @@ -933,24 +954,15 @@ class IntervalMap { RootBranch node; }; - enum { - RootDataSize = sizeof(RootBranchData) > sizeof(RootLeaf) ? - sizeof(RootBranchData) : sizeof(RootLeaf) - }; - public: typedef typename Sizer::Allocator Allocator; + typedef KeyT KeyType; + typedef ValT ValueType; typedef Traits KeyTraits; private: // The root data is either a RootLeaf or a RootBranchData instance. - // We can't put them in a union since C++03 doesn't allow non-trivial - // constructors in unions. - // Instead, we use a char array with pointer alignment. The alignment is - // ensured by the allocator member in the class, but still verified in the - // constructor. We don't support keys or values that are more aligned than a - // pointer. - char data[RootDataSize]; + AlignedCharArrayUnion data; // Tree height. // 0: Leaves in root. @@ -971,7 +983,7 @@ private: const char *d; T *t; } u; - u.d = data; + u.d = data.buffer; return *u.t; } @@ -1029,7 +1041,7 @@ private: public: explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) { - assert((uintptr_t(data) & (alignOf() - 1)) == 0 && + assert((uintptr_t(data.buffer) & (alignOf() - 1)) == 0 && "Insufficient alignment"); new(&rootLeaf()) RootLeaf(); } @@ -1155,7 +1167,7 @@ branchRoot(unsigned Position) { if (Nodes == 1) size[0] = rootSize; else - NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, size, + NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, nullptr, size, Position, true); // Allocate new nodes. @@ -1196,7 +1208,7 @@ splitRoot(unsigned Position) { if (Nodes == 1) Size[0] = rootSize; else - NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, Size, + NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, nullptr, Size, Position, true); // Allocate new nodes. @@ -1324,11 +1336,18 @@ protected: public: /// const_iterator - Create an iterator that isn't pointing anywhere. - const_iterator() : map(0) {} + const_iterator() : map(nullptr) {} + + /// setMap - Change the map iterated over. This call must be followed by a + /// call to goToBegin(), goToEnd(), or find() + void setMap(const IntervalMap &m) { map = const_cast(&m); } /// valid - Return true if the current position is valid, false for end(). bool valid() const { return path.valid(); } + /// atBegin - Return true if the current position is the first map entry. + bool atBegin() const { return path.atBegin(); } + /// start - Return the beginning of the current interval. const KeyT &start() const { return unsafeStart(); } @@ -1409,6 +1428,8 @@ public: /// The search is started from the current position, and no earlier positions /// can be found. This is much faster than find() for small moves. void advanceTo(KeyT x) { + if (!valid()) + return; if (branched()) treeAdvanceTo(x); else @@ -1925,7 +1946,7 @@ iterator::eraseNode(unsigned Level) { /// overflow - Distribute entries of the current node evenly among /// its siblings and ensure that the current node is not full. /// This may require allocating a new node. -/// @param NodeT The type of node at Level (Leaf or Branch). +/// @tparam NodeT The type of node at Level (Leaf or Branch). /// @param Level path index of the overflowing node. /// @return True when the tree height was changed. template @@ -1966,7 +1987,7 @@ iterator::overflow(unsigned Level) { CurSize[Nodes] = CurSize[NewNode]; Node[Nodes] = Node[NewNode]; CurSize[NewNode] = 0; - Node[NewNode] = this->map->newNode(); + Node[NewNode] = this->map->template newNode(); ++Nodes; } @@ -2025,6 +2046,7 @@ iterator::overflow(unsigned Level) { /// template class IntervalMapOverlaps { + typedef typename MapA::KeyType KeyType; typedef typename MapA::KeyTraits Traits; typename MapA::const_iterator posA; typename MapB::const_iterator posB; @@ -2033,14 +2055,31 @@ class IntervalMapOverlaps { /// either meets end. /// Don't move the iterators if they are already overlapping. void advance() { + if (!valid()) + return; + + if (Traits::stopLess(posA.stop(), posB.start())) { + // A ends before B begins. Catch up. + posA.advanceTo(posB.start()); + if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start())) + return; + } else if (Traits::stopLess(posB.stop(), posA.start())) { + // B ends before A begins. Catch up. + posB.advanceTo(posA.start()); + if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start())) + return; + } else + // Already overlapping. + return; + for (;;) { // Make a.end > b.start. posA.advanceTo(posB.start()); - if (!posA.valid() || !Traits::stopLess(posB.end(), posA.start())) + if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start())) return; // Make b.end > a.start. posB.advanceTo(posA.start()); - if (!posB.valid() || !Traits::stopLess(posA.end(), posB.start())) + if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start())) return; } } @@ -2049,10 +2088,7 @@ public: /// IntervalMapOverlaps - Create an iterator for the overlaps of a and b. IntervalMapOverlaps(const MapA &a, const MapB &b) : posA(b.empty() ? a.end() : a.find(b.start())), - posB(posA.valid() ? b.find(posA.start()) : b.end()) { - if (valid()) - advance(); - } + posB(posA.valid() ? b.find(posA.start()) : b.end()) { advance(); } /// valid - Return true if iterator is at an overlap. bool valid() const { @@ -2065,37 +2101,55 @@ public: /// b - access the right hand side in the overlap. const typename MapB::const_iterator &b() const { return posB; } + /// start - Beginning of the overlapping interval. + KeyType start() const { + KeyType ak = a().start(); + KeyType bk = b().start(); + return Traits::startLess(ak, bk) ? bk : ak; + } + + /// stop - End of the overlapping interval. + KeyType stop() const { + KeyType ak = a().stop(); + KeyType bk = b().stop(); + return Traits::startLess(ak, bk) ? ak : bk; + } + /// skipA - Move to the next overlap that doesn't involve a(). void skipA() { ++posA; - if (!posA.valid() || !Traits::stopLess(posB.end(), posA.start())) - return; - // Second half-loop of advance(). - posB.advanceTo(posA.start()); - if (!posB.valid() || !Traits::stopLess(posA.end(), posB.start())) - return ; advance(); } /// skipB - Move to the next overlap that doesn't involve b(). void skipB() { ++posB; - if (!posB.valid() || !Traits::stopLess(posA.end(), posB.start())) - return; advance(); } /// Preincrement - Move to the next overlap. IntervalMapOverlaps &operator++() { // Bump the iterator that ends first. The other one may have more overlaps. - if (Traits::startLess(posB.end(), posA.end())) + if (Traits::startLess(posB.stop(), posA.stop())) skipB(); else skipA(); return *this; } -}; + /// advanceTo - Move to the first overlapping interval with + /// stopLess(x, stop()). + void advanceTo(KeyType x) { + if (!valid()) + return; + // Make sure advanceTo sees monotonic keys. + if (Traits::stopLess(posA.stop(), x)) + posA.advanceTo(x); + if (Traits::stopLess(posB.stop(), x)) + posB.advanceTo(x); + advance(); + } +}; } // namespace llvm