#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/Allocator.h"
#include "llvm/Support/RecyclingAllocator.h"
#include <iterator>
};
+template <typename T>
+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 {
NodeRef() {}
/// operator bool - Detect a null ref.
- operator bool() const { return pip.getOpaqueValue(); }
+ LLVM_EXPLICIT operator bool() const { return pip.getOpaqueValue(); }
/// NodeRef - Create a reference to the node p with n elements.
template <typename NodeT>
/// 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.
// 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.
//
//===----------------------------------------------------------------------===//
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.
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.
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<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(); }
/// 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 <typename KeyT, typename ValT, unsigned N, typename Traits>
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;
}
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());
return Traits::startLess(ak, bk) ? bk : ak;
}
- /// stop - End of the overlaping interval.
+ /// stop - End of the overlapping interval.
KeyType stop() const {
KeyType ak = a().stop();
KeyType bk = b().stop();
/// skipA - Move to the next overlap that doesn't involve a().
void skipA() {
++posA;
- if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
- return;
- // Second half-loop of advance().
- posB.advanceTo(posA.start());
- if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
- return;
advance();
}
/// skipB - Move to the next overlap that doesn't involve b().
void skipB() {
++posB;
- if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
- return;
advance();
}
/// advanceTo - Move to the first overlapping interval with
/// stopLess(x, stop()).
void advanceTo(KeyType x) {
- posA.advanceTo(x);
- posB.advanceTo(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();
}
};
projects / oota-llvm.git / blobdiff