#include "llvm/Support/RecyclingAllocator.h"
#include <iterator>
-// FIXME: Remove debugging code.
-#include "llvm/Support/raw_ostream.h"
-
namespace llvm {
}
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
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 << " | <s" << i << "> " << stop(i);
- OS << "\"];\n";
- for (unsigned i = 0; i != Size; ++i)
- OS << " N" << this << ":s" << i << " -> N"
- << &subtree(i).template get<BranchNode>() << ";\n";
- }
-#endif
-
};
//===----------------------------------------------------------------------===//
// 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.
//
//===----------------------------------------------------------------------===//
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
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.
friend class iterator;
const_iterator begin() const {
- iterator I(*this);
+ const_iterator I(*this);
I.goToBegin();
return I;
}
}
const_iterator end() const {
- iterator I(*this);
+ const_iterator I(*this);
I.goToEnd();
return I;
}
/// 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;
}
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
rootSize = 0;
}
-#ifndef NDEBUG
-template <typename KeyT, typename ValT, unsigned N, typename Traits>
-void IntervalMap<KeyT, ValT, N, Traits>::
-dumpNode(IntervalMapImpl::NodeRef Node, unsigned Height) {
- if (Height)
- Node.get<Branch>().dump(*OS, Node.size());
- else
- Node.get<Leaf>().dump(*OS, Node.size());
-}
-
-template <typename KeyT, typename ValT, unsigned N, typename Traits>
-void IntervalMap<KeyT, ValT, N, Traits>::
-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 ----//
//===----------------------------------------------------------------------===//
// 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<IntervalMap*>(&map)) {}
bool branched() const {
assert(map && "Invalid iterator");
/// 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<IntervalMap*>(&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(); }
/// 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
CurSize[Nodes] = CurSize[NewNode];
Node[Nodes] = Node[NewNode];
CurSize[NewNode] = 0;
- Node[NewNode] = this->map->newNode<NodeT>();
+ Node[NewNode] = this->map->template newNode<NodeT>();
++Nodes;
}
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 <typename MapA, typename MapB>
+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
projects / oota-llvm.git / blobdiff