X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FIntervalMap.h;h=931b67e40911dd801fa865e4c86c3fd22e41c6a3;hb=ac24e251014de60a16558fc0a1f2340c334d2aa8;hp=33569269c682d973ffac6415a26891a17ca75b58;hpb=7a26aca73ff2c8c4cb3205a776cc6743949b1fb7;p=oota-llvm.git diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h index 33569269c68..931b67e4091 100644 --- a/include/llvm/ADT/IntervalMap.h +++ b/include/llvm/ADT/IntervalMap.h @@ -105,9 +105,6 @@ #include "llvm/Support/RecyclingAllocator.h" #include -// FIXME: Remove debugging code. -#include "llvm/Support/raw_ostream.h" - namespace llvm { @@ -590,16 +587,6 @@ public: } unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y); - -#ifndef NDEBUG - void dump(raw_ostream &OS, unsigned Size) { - OS << " N" << this << " [shape=record label=\"{ " << Size << '/' << N; - for (unsigned i = 0; i != Size; ++i) - OS << " | {" << start(i) << '-' << stop(i) << "|" << value(i) << '}'; - OS << "}\"];\n"; - } -#endif - }; /// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as @@ -743,19 +730,6 @@ public: subtree(i) = Node; stop(i) = Stop; } - -#ifndef NDEBUG - void dump(raw_ostream &OS, unsigned Size) { - OS << " N" << this << " [shape=record label=\"" << Size << '/' << N; - for (unsigned i = 0; i != Size; ++i) - OS << " | " << stop(i); - OS << "\"];\n"; - for (unsigned i = 0; i != Size; ++i) - OS << " N" << this << ":s" << i << " -> N" - << &subtree(i).template get() << ";\n"; - } -#endif - }; //===----------------------------------------------------------------------===// @@ -765,7 +739,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. // //===----------------------------------------------------------------------===// @@ -922,14 +896,6 @@ public: moveLeft(Level); ++path[Level].offset; } - -#ifndef NDEBUG - void dump() const { - for (unsigned l = 0, e = path.size(); l != e; ++l) - errs() << l << ": " << path[l].node << ' ' << path[l].size << ' ' - << path[l].offset << '\n'; - } -#endif }; } // namespace IntervalMapImpl @@ -974,6 +940,9 @@ class IntervalMap { 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. @@ -1119,7 +1088,7 @@ public: friend class iterator; const_iterator begin() const { - iterator I(*this); + const_iterator I(*this); I.goToBegin(); return I; } @@ -1131,7 +1100,7 @@ public: } const_iterator end() const { - iterator I(*this); + const_iterator I(*this); I.goToEnd(); return I; } @@ -1145,7 +1114,7 @@ public: /// find - Return an iterator pointing to the first interval ending at or /// after x, or end(). const_iterator find(KeyT x) const { - iterator I(*this); + const_iterator I(*this); I.find(x); return I; } @@ -1155,12 +1124,6 @@ public: I.find(x); return I; } - -#ifndef NDEBUG - raw_ostream *OS; - void dump(); - void dumpNode(IntervalMapImpl::NodeRef Node, unsigned Height); -#endif }; /// treeSafeLookup - Return the mapped value at x or NotFound, assuming a @@ -1304,32 +1267,6 @@ clear() { rootSize = 0; } -#ifndef NDEBUG -template -void IntervalMap:: -dumpNode(IntervalMapImpl::NodeRef Node, unsigned Height) { - if (Height) - Node.get().dump(*OS, Node.size()); - else - Node.get().dump(*OS, Node.size()); -} - -template -void IntervalMap:: -dump() { - std::string errors; - raw_fd_ostream ofs("tree.dot", errors); - OS = &ofs; - ofs << "digraph {\n"; - if (branched()) - rootBranch().dump(ofs, rootSize); - else - rootLeaf().dump(ofs, rootSize); - visitNodes(&IntervalMap::dumpNode); - ofs << "}\n"; -} -#endif - //===----------------------------------------------------------------------===// //--- IntervalMap::const_iterator ----// //===----------------------------------------------------------------------===// @@ -1347,7 +1284,8 @@ protected: // The path may be partially filled, but never between iterator calls. IntervalMapImpl::Path path; - explicit const_iterator(IntervalMap &map) : map(&map) {} + explicit const_iterator(const IntervalMap &map) : + map(const_cast(&map)) {} bool branched() const { assert(map && "Invalid iterator"); @@ -1390,9 +1328,16 @@ public: /// const_iterator - Create an iterator that isn't pointing anywhere. const_iterator() : map(0) {} + /// 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(); } @@ -1473,6 +1418,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 @@ -2030,7 +1977,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; } @@ -2071,6 +2018,129 @@ iterator::overflow(unsigned Level) { return SplitRoot; } +//===----------------------------------------------------------------------===// +//--- IntervalMapOverlaps ----// +//===----------------------------------------------------------------------===// + +/// IntervalMapOverlaps - Iterate over the overlaps of mapped intervals in two +/// IntervalMaps. The maps may be different, but the KeyT and Traits types +/// should be the same. +/// +/// Typical uses: +/// +/// 1. Test for overlap: +/// bool overlap = IntervalMapOverlaps(a, b).valid(); +/// +/// 2. Enumerate overlaps: +/// for (IntervalMapOverlaps I(a, b); I.valid() ; ++I) { ... } +/// +template +class IntervalMapOverlaps { + typedef typename MapA::KeyType KeyType; + typedef typename MapA::KeyTraits Traits; + typename MapA::const_iterator posA; + typename MapB::const_iterator posB; + + /// advance - Move posA and posB forward until reaching an overlap, or until + /// 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.stop(), posA.start())) + return; + // Make b.end > a.start. + posB.advanceTo(posA.start()); + if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start())) + return; + } + } + +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()) { advance(); } + + /// valid - Return true if iterator is at an overlap. + bool valid() const { + return posA.valid() && posB.valid(); + } + + /// a - access the left hand side in the overlap. + const typename MapA::const_iterator &a() const { return posA; } + + /// 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; + advance(); + } + + /// skipB - Move to the next overlap that doesn't involve b(). + void skipB() { + ++posB; + 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.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 #endif