#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 <limits>
#include <iterator>
-// FIXME: Remove debugging code.
-#include "llvm/Support/raw_ostream.h"
-
namespace llvm {
};
+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 {
//===----------------------------------------------------------------------===//
-//--- Node Storage ---//
+//--- IntervalMapImpl::NodeBase ---//
//===----------------------------------------------------------------------===//
//
// Both leaf and branch nodes store vectors of pairs.
unsigned j, unsigned Count) {
assert(i + Count <= M && "Invalid source range");
assert(j + Count <= N && "Invalid dest range");
- std::copy(Other.first + i, Other.first + i + Count, first + j);
- std::copy(Other.second + i, Other.second + i + Count, second + j);
+ for (unsigned e = i + Count; i != e; ++i, ++j) {
+ first[j] = Other.first[i];
+ second[j] = Other.second[i];
+ }
}
/// moveLeft - Move elements to the left.
void moveRight(unsigned i, unsigned j, unsigned Count) {
assert(i <= j && "Use moveLeft shift elements left");
assert(j + Count <= N && "Invalid range");
- std::copy_backward(first + i, first + i + Count, first + j + Count);
- std::copy_backward(second + i, second + i + Count, second + j + Count);
+ while (Count--) {
+ first[j + Count] = first[i + Count];
+ second[j + Count] = second[i + Count];
+ }
}
/// erase - Erase elements [i;j).
}
};
-/// adjustSiblingSizes - Move elements between sibling nodes.
+/// IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes.
/// @param Node Array of pointers to sibling nodes.
/// @param Nodes Number of nodes.
/// @param CurSize Array of current node sizes, will be overwritten.
#endif
}
-/// distribute - Compute a new distribution of node elements after an overflow
-/// or underflow. Reserve space for a new element at Position, and compute the
-/// node that will hold Position after redistributing node elements.
+/// IntervalMapImpl::distribute - Compute a new distribution of node elements
+/// after an overflow or underflow. Reserve space for a new element at Position,
+/// and compute the node that will hold Position after redistributing node
+/// elements.
///
/// It is required that
///
//===----------------------------------------------------------------------===//
-//--- NodeSizer ---//
+//--- IntervalMapImpl::NodeSizer ---//
//===----------------------------------------------------------------------===//
//
// Compute node sizes from key and value types.
//===----------------------------------------------------------------------===//
-//--- NodeRef ---//
+//--- IntervalMapImpl::NodeRef ---//
//===----------------------------------------------------------------------===//
//
// B+-tree nodes can be leaves or branches, so we need a polymorphic node
//
//===----------------------------------------------------------------------===//
-struct CacheAlignedPointerTraits {
- static inline void *getAsVoidPointer(void *P) { return P; }
- static inline void *getFromVoidPointer(void *P) { return P; }
- enum { NumLowBitsAvailable = Log2CacheLine };
-};
-
class NodeRef {
+ struct CacheAlignedPointerTraits {
+ static inline void *getAsVoidPointer(void *P) { return P; }
+ static inline void *getFromVoidPointer(void *P) { return P; }
+ enum { NumLowBitsAvailable = Log2CacheLine };
+ };
PointerIntPair<void*, Log2CacheLine, unsigned, CacheAlignedPointerTraits> pip;
public:
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>
};
//===----------------------------------------------------------------------===//
-//--- Leaf nodes ---//
+//--- IntervalMapImpl::LeafNode ---//
//===----------------------------------------------------------------------===//
//
// Leaf nodes store up to N disjoint intervals with corresponding values.
return Traits::startLess(x, start(i)) ? NotFound : value(i);
}
- IdxPair insertFrom(unsigned i, unsigned Size, KeyT a, KeyT b, ValT y);
- unsigned extendStop(unsigned i, unsigned Size, KeyT b);
-
-#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
-
+ unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y);
};
/// 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.
/// @param y Value be mapped.
/// @return (insert position, new size), or (i, Capacity+1) on overflow.
template <typename KeyT, typename ValT, unsigned N, typename Traits>
-IdxPair LeafNode<KeyT, ValT, N, Traits>::
-insertFrom(unsigned i, unsigned Size, KeyT a, KeyT b, ValT y) {
+unsigned LeafNode<KeyT, ValT, N, Traits>::
+insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y) {
+ unsigned i = Pos;
assert(i <= Size && Size <= N && "Invalid index");
assert(!Traits::stopLess(b, a) && "Invalid interval");
// Verify the findFrom invariant.
assert((i == 0 || Traits::stopLess(stop(i - 1), a)));
assert((i == Size || !Traits::stopLess(stop(i), a)));
+ assert((i == Size || Traits::stopLess(b, start(i))) && "Overlapping insert");
// Coalesce with previous interval.
- if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a))
- return IdxPair(i - 1, extendStop(i - 1, Size, b));
+ if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a)) {
+ Pos = i - 1;
+ // Also coalesce with next interval?
+ if (i != Size && value(i) == y && Traits::adjacent(b, start(i))) {
+ stop(i - 1) = stop(i);
+ this->erase(i, Size);
+ return Size - 1;
+ }
+ stop(i - 1) = b;
+ return Size;
+ }
// Detect overflow.
if (i == N)
- return IdxPair(i, N + 1);
+ return N + 1;
// Add new interval at end.
if (i == Size) {
start(i) = a;
stop(i) = b;
value(i) = y;
- return IdxPair(i, Size + 1);
- }
-
- // Overlapping intervals?
- if (!Traits::stopLess(b, start(i))) {
- assert(value(i) == y && "Inconsistent values in overlapping intervals");
- if (Traits::startLess(a, start(i)))
- start(i) = a;
- return IdxPair(i, extendStop(i, Size, b));
+ return Size + 1;
}
// Try to coalesce with following interval.
if (value(i) == y && Traits::adjacent(b, start(i))) {
start(i) = a;
- return IdxPair(i, Size);
+ return Size;
}
// We must insert before i. Detect overflow.
if (Size == N)
- return IdxPair(i, N + 1);
+ return N + 1;
// Insert before i.
this->shift(i, Size);
start(i) = a;
stop(i) = b;
value(i) = y;
- return IdxPair(i, Size + 1);
-}
-
-/// extendStop - Extend stop(i) to b, coalescing with following intervals.
-/// @param i Interval to extend.
-/// @param Size Number of elements in node.
-/// @param b New interval end point.
-/// @return New node size after coalescing.
-template <typename KeyT, typename ValT, unsigned N, typename Traits>
-unsigned LeafNode<KeyT, ValT, N, Traits>::
-extendStop(unsigned i, unsigned Size, KeyT b) {
- assert(i < Size && Size <= N && "Bad indices");
-
- // Are we even extending the interval?
- if (Traits::startLess(b, stop(i)))
- return Size;
-
- // Find the first interval that may be preserved.
- unsigned j = findFrom(i + 1, Size, b);
- if (j < Size) {
- // Would key[i] overlap key[j] after the extension?
- if (Traits::stopLess(b, start(j))) {
- // Not overlapping. Perhaps adjacent and coalescable?
- if (value(i) == value(j) && Traits::adjacent(b, start(j)))
- b = stop(j++);
- } else {
- // Overlap. Include key[j] in the new interval.
- assert(value(i) == value(j) && "Overlapping values");
- b = stop(j++);
- }
- }
- stop(i) = b;
-
- // Entries [i+1;j) were coalesced.
- if (i + 1 < j && j < Size)
- this->erase(i + 1, j, Size);
- return Size - (j - (i + 1));
+ return Size + 1;
}
//===----------------------------------------------------------------------===//
-//--- Branch nodes ---//
+//--- IntervalMapImpl::BranchNode ---//
//===----------------------------------------------------------------------===//
//
// A branch node stores references to 1--N subtrees all of the same height.
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
-
};
//===----------------------------------------------------------------------===//
-//--- Path ---//
+//--- IntervalMapImpl::Path ---//
//===----------------------------------------------------------------------===//
//
// 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.
//
//===----------------------------------------------------------------------===//
return true;
}
- /// atLastBranch - Return true if the path is at the last branch of the node
- /// at Level.
+ /// atLastEntry - Return true if the path is at the last entry of the node at
+ /// Level.
/// @param Level Node to examine.
- bool atLastBranch(unsigned Level) const {
+ bool atLastEntry(unsigned Level) const {
return path[Level].offset == path[Level].size - 1;
}
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.
// Easy insert into root leaf.
unsigned p = rootLeaf().findFrom(0, rootSize, a);
- rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y).second;
+ rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y);
}
/// clear - Remove all entries.
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
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.
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
-
//===----------------------------------------------------------------------===//
-//--- const_iterator ----//
+//--- IntervalMap::const_iterator ----//
//===----------------------------------------------------------------------===//
template <typename KeyT, typename ValT, unsigned N, typename Traits>
// 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");
void treeFind(KeyT x);
void treeAdvanceTo(KeyT x);
-public:
- /// const_iterator - Create an iterator that isn't pointing anywhere.
- const_iterator() : map(0) {}
-
- /// valid - Return true if the current position is valid, false for end().
- bool valid() const { return path.valid(); }
-
- /// start - Return the beginning of the current interval.
- const KeyT &start() const {
+ /// unsafeStart - Writable access to start() for iterator.
+ KeyT &unsafeStart() const {
assert(valid() && "Cannot access invalid iterator");
return branched() ? path.leaf<Leaf>().start(path.leafOffset()) :
path.leaf<RootLeaf>().start(path.leafOffset());
}
- /// stop - Return the end of the current interval.
- const KeyT &stop() const {
+ /// unsafeStop - Writable access to stop() for iterator.
+ KeyT &unsafeStop() const {
assert(valid() && "Cannot access invalid iterator");
return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) :
path.leaf<RootLeaf>().stop(path.leafOffset());
}
- /// value - Return the mapped value at the current interval.
- const ValT &value() const {
+ /// unsafeValue - Writable access to value() for iterator.
+ ValT &unsafeValue() const {
assert(valid() && "Cannot access invalid iterator");
return branched() ? path.leaf<Leaf>().value(path.leafOffset()) :
path.leaf<RootLeaf>().value(path.leafOffset());
}
- const ValT &operator*() const {
- return value();
- }
+public:
+ /// const_iterator - Create an iterator that isn't pointing anywhere.
+ 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(); }
+
+ /// stop - Return the end of the current interval.
+ const KeyT &stop() const { return unsafeStop(); }
+
+ /// value - Return the mapped value at the current interval.
+ const ValT &value() const { return unsafeValue(); }
+
+ const ValT &operator*() const { return value(); }
bool operator==(const const_iterator &RHS) const {
assert(map == RHS.map && "Cannot compare iterators from different maps");
/// 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
}
//===----------------------------------------------------------------------===//
-//--- iterator ----//
+//--- IntervalMap::iterator ----//
//===----------------------------------------------------------------------===//
template <typename KeyT, typename ValT, unsigned N, typename Traits>
void treeInsert(KeyT a, KeyT b, ValT y);
void eraseNode(unsigned Level);
void treeErase(bool UpdateRoot = true);
+ bool canCoalesceLeft(KeyT Start, ValT x);
+ bool canCoalesceRight(KeyT Stop, ValT x);
+
public:
/// iterator - Create null iterator.
iterator() {}
+ /// setStart - Move the start of the current interval.
+ /// This may cause coalescing with the previous interval.
+ /// @param a New start key, must not overlap the previous interval.
+ void setStart(KeyT a);
+
+ /// setStop - Move the end of the current interval.
+ /// This may cause coalescing with the following interval.
+ /// @param b New stop key, must not overlap the following interval.
+ void setStop(KeyT b);
+
+ /// setValue - Change the mapped value of the current interval.
+ /// This may cause coalescing with the previous and following intervals.
+ /// @param x New value.
+ void setValue(ValT x);
+
+ /// setStartUnchecked - Move the start of the current interval without
+ /// checking for coalescing or overlaps.
+ /// This should only be used when it is known that coalescing is not required.
+ /// @param a New start key.
+ void setStartUnchecked(KeyT a) { this->unsafeStart() = a; }
+
+ /// setStopUnchecked - Move the end of the current interval without checking
+ /// for coalescing or overlaps.
+ /// This should only be used when it is known that coalescing is not required.
+ /// @param b New stop key.
+ void setStopUnchecked(KeyT b) {
+ this->unsafeStop() = b;
+ // Update keys in branch nodes as well.
+ if (this->path.atLastEntry(this->path.height()))
+ setNodeStop(this->path.height(), b);
+ }
+
+ /// setValueUnchecked - Change the mapped value of the current interval
+ /// without checking for coalescing.
+ /// @param x New value.
+ void setValueUnchecked(ValT x) { this->unsafeValue() = x; }
+
/// insert - Insert mapping [a;b] -> y before the current position.
void insert(KeyT a, KeyT b, ValT y);
};
+/// canCoalesceLeft - Can the current interval coalesce to the left after
+/// changing start or value?
+/// @param Start New start of current interval.
+/// @param Value New value for current interval.
+/// @return True when updating the current interval would enable coalescing.
+template <typename KeyT, typename ValT, unsigned N, typename Traits>
+bool IntervalMap<KeyT, ValT, N, Traits>::
+iterator::canCoalesceLeft(KeyT Start, ValT Value) {
+ using namespace IntervalMapImpl;
+ Path &P = this->path;
+ if (!this->branched()) {
+ unsigned i = P.leafOffset();
+ RootLeaf &Node = P.leaf<RootLeaf>();
+ return i && Node.value(i-1) == Value &&
+ Traits::adjacent(Node.stop(i-1), Start);
+ }
+ // Branched.
+ if (unsigned i = P.leafOffset()) {
+ Leaf &Node = P.leaf<Leaf>();
+ return Node.value(i-1) == Value && Traits::adjacent(Node.stop(i-1), Start);
+ } else if (NodeRef NR = P.getLeftSibling(P.height())) {
+ unsigned i = NR.size() - 1;
+ Leaf &Node = NR.get<Leaf>();
+ return Node.value(i) == Value && Traits::adjacent(Node.stop(i), Start);
+ }
+ return false;
+}
+
+/// canCoalesceRight - Can the current interval coalesce to the right after
+/// changing stop or value?
+/// @param Stop New stop of current interval.
+/// @param Value New value for current interval.
+/// @return True when updating the current interval would enable coalescing.
+template <typename KeyT, typename ValT, unsigned N, typename Traits>
+bool IntervalMap<KeyT, ValT, N, Traits>::
+iterator::canCoalesceRight(KeyT Stop, ValT Value) {
+ using namespace IntervalMapImpl;
+ Path &P = this->path;
+ unsigned i = P.leafOffset() + 1;
+ if (!this->branched()) {
+ if (i >= P.leafSize())
+ return false;
+ RootLeaf &Node = P.leaf<RootLeaf>();
+ return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));
+ }
+ // Branched.
+ if (i < P.leafSize()) {
+ Leaf &Node = P.leaf<Leaf>();
+ return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));
+ } else if (NodeRef NR = P.getRightSibling(P.height())) {
+ Leaf &Node = NR.get<Leaf>();
+ return Node.value(0) == Value && Traits::adjacent(Stop, Node.start(0));
+ }
+ return false;
+}
+
/// setNodeStop - Update the stop key of the current node at level and above.
template <typename KeyT, typename ValT, unsigned N, typename Traits>
void IntervalMap<KeyT, ValT, N, Traits>::
// Update nodes pointing to the current node.
while (--Level) {
P.node<Branch>(Level).stop(P.offset(Level)) = Stop;
- if (!P.atLastBranch(Level))
+ if (!P.atLastEntry(Level))
return;
}
// Update root separately since it has a different layout.
P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop;
}
+template <typename KeyT, typename ValT, unsigned N, typename Traits>
+void IntervalMap<KeyT, ValT, N, Traits>::
+iterator::setStart(KeyT a) {
+ assert(Traits::stopLess(a, this->stop()) && "Cannot move start beyond stop");
+ KeyT &CurStart = this->unsafeStart();
+ if (!Traits::startLess(a, CurStart) || !canCoalesceLeft(a, this->value())) {
+ CurStart = a;
+ return;
+ }
+ // Coalesce with the interval to the left.
+ --*this;
+ a = this->start();
+ erase();
+ setStartUnchecked(a);
+}
+
+template <typename KeyT, typename ValT, unsigned N, typename Traits>
+void IntervalMap<KeyT, ValT, N, Traits>::
+iterator::setStop(KeyT b) {
+ assert(Traits::stopLess(this->start(), b) && "Cannot move stop beyond start");
+ if (Traits::startLess(b, this->stop()) ||
+ !canCoalesceRight(b, this->value())) {
+ setStopUnchecked(b);
+ return;
+ }
+ // Coalesce with interval to the right.
+ KeyT a = this->start();
+ erase();
+ setStartUnchecked(a);
+}
+
+template <typename KeyT, typename ValT, unsigned N, typename Traits>
+void IntervalMap<KeyT, ValT, N, Traits>::
+iterator::setValue(ValT x) {
+ setValueUnchecked(x);
+ if (canCoalesceRight(this->stop(), x)) {
+ KeyT a = this->start();
+ erase();
+ setStartUnchecked(a);
+ }
+ if (canCoalesceLeft(this->start(), x)) {
+ --*this;
+ KeyT a = this->start();
+ erase();
+ setStartUnchecked(a);
+ }
+}
+
/// insertNode - insert a node before the current path at level.
/// Leave the current path pointing at the new node.
/// @param Level path index of the node to be inserted.
}
P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop);
P.setSize(Level, P.size(Level) + 1);
- if (P.atLastBranch(Level))
+ if (P.atLastEntry(Level))
setNodeStop(Level, Stop);
P.reset(Level + 1);
return SplitRoot;
IntervalMapImpl::Path &P = this->path;
// Try simple root leaf insert.
- IdxPair IP = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y);
+ unsigned Size = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y);
// Was the root node insert successful?
- if (IP.second <= RootLeaf::Capacity) {
- P.leafOffset() = IP.first;
- P.setSize(0, IM.rootSize = IP.second);
+ if (Size <= RootLeaf::Capacity) {
+ P.setSize(0, IM.rootSize = Size);
return;
}
void IntervalMap<KeyT, ValT, N, Traits>::
iterator::treeInsert(KeyT a, KeyT b, ValT y) {
using namespace IntervalMapImpl;
- IntervalMap &IM = *this->map;
Path &P = this->path;
+ if (!P.valid())
+ P.legalizeForInsert(this->map->height);
+
// Check if this insertion will extend the node to the left.
- if (P.valid() && P.leafOffset() == 0 &&
- Traits::startLess(a, P.leaf<Leaf>().start(0))) {
+ if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<Leaf>().start(0))) {
// Node is growing to the left, will it affect a left sibling node?
- if (NodeRef Sib = P.getLeftSibling(IM.height)) {
+ if (NodeRef Sib = P.getLeftSibling(P.height())) {
Leaf &SibLeaf = Sib.get<Leaf>();
unsigned SibOfs = Sib.size() - 1;
if (SibLeaf.value(SibOfs) == y &&
// 2. Extend a to SibLeaf, erase the SibLeaf entry and continue.
// We prefer 1., but need 2 when coalescing to the right as well.
Leaf &CurLeaf = P.leaf<Leaf>();
- P.moveLeft(IM.height);
+ P.moveLeft(P.height());
if (Traits::stopLess(b, CurLeaf.start(0)) &&
(y != CurLeaf.value(0) || !Traits::adjacent(b, CurLeaf.start(0)))) {
// Easy, just extend SibLeaf and we're done.
- setNodeStop(IM.height, SibLeaf.stop(SibOfs) = b);
+ setNodeStop(P.height(), SibLeaf.stop(SibOfs) = b);
return;
} else {
// We have both left and right coalescing. Erase the old SibLeaf entry
}
} else {
// No left sibling means we are at begin(). Update cached bound.
- IM.rootBranchStart() = a;
+ this->map->rootBranchStart() = a;
}
}
- P.legalizeForInsert(IM.height);
- IdxPair IP = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y);
+ // When we are inserting at the end of a leaf node, we must update stops.
+ unsigned Size = P.leafSize();
+ bool Grow = P.leafOffset() == Size;
+ Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), Size, a, b, y);
// Leaf insertion unsuccessful? Overflow and try again.
- if (IP.second > Leaf::Capacity) {
- overflow<Leaf>(IM.height);
- IP = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y);
- assert(IP.second <= Leaf::Capacity && "overflow() didn't make room");
+ if (Size > Leaf::Capacity) {
+ overflow<Leaf>(P.height());
+ Grow = P.leafOffset() == P.leafSize();
+ Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y);
+ assert(Size <= Leaf::Capacity && "overflow() didn't make room");
}
// Inserted, update offset and leaf size.
- P.leafOffset() = IP.first;
- P.setSize(IM.height, IP.second);
+ P.setSize(P.height(), Size);
// Insert was the last node entry, update stops.
- if (IP.first == IP.second - 1)
- setNodeStop(IM.height, P.leaf<Leaf>().stop(IP.first));
+ if (Grow)
+ setNodeStop(P.height(), b);
}
/// erase - erase the current interval and move to the next position.
/// 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;
}
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