#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 <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 (key,value) pairs.
-// Leaves store ((KeyT, KeyT), ValT) pairs, branches use (KeyT, NodeRef).
+// Both leaf and branch nodes store vectors of pairs.
+// Leaves store ((KeyT, KeyT), ValT) pairs, branches use (NodeRef, KeyT).
//
// Keys and values are stored in separate arrays to avoid padding caused by
// different object alignments. This also helps improve locality of reference
// These are typical key and value sizes, the node branching factor (N), and
// wasted space when nodes are sized to fit in three cache lines (192 bytes):
//
-// KT VT N Waste Used by
+// T1 T2 N Waste Used by
// 4 4 24 0 Branch<4> (32-bit pointers)
-// 4 8 16 0 Branch<4>
-// 8 4 16 0 Leaf<4,4>
+// 8 4 16 0 Leaf<4,4>, Branch<4>
// 8 8 12 0 Leaf<4,8>, Branch<8>
// 16 4 9 12 Leaf<8,4>
// 16 8 8 0 Leaf<8,8>
//
//===----------------------------------------------------------------------===//
-template <typename KT, typename VT, unsigned N>
+template <typename T1, typename T2, unsigned N>
class NodeBase {
public:
enum { Capacity = N };
- KT key[N];
- VT val[N];
+ T1 first[N];
+ T2 second[N];
/// copy - Copy elements from another node.
/// @param Other Node elements are copied from.
/// @param j Beginning of the destination range in this.
/// @param Count Number of elements to copy.
template <unsigned M>
- void copy(const NodeBase<KT, VT, M> &Other, unsigned i,
+ void copy(const NodeBase<T1, T2, M> &Other, unsigned i,
unsigned j, unsigned Count) {
assert(i + Count <= M && "Invalid source range");
assert(j + Count <= N && "Invalid dest range");
- std::copy(Other.key + i, Other.key + i + Count, key + j);
- std::copy(Other.val + i, Other.val + i + Count, val + 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(key + i, key + i + Count, key + j + Count);
- std::copy_backward(val + i, val + i + Count, val + j + Count);
+ while (Count--) {
+ first[j + Count] = first[i + Count];
+ second[j + Count] = second[i + Count];
+ }
}
/// erase - Erase elements [i;j).
moveLeft(j, i, Size - j);
}
+ /// erase - Erase element at i.
+ /// @param i Index of element to erase.
+ /// @param Size Number of elements in node.
+ void erase(unsigned i, unsigned Size) {
+ erase(i, i+1, Size);
+ }
+
/// shift - Shift elements [i;size) 1 position to the right.
/// @param i Beginning of the range to move.
/// @param Size Number of elements in node.
}
};
+/// 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.
+/// @param NewSize Array of desired node sizes.
+template <typename NodeT>
+void adjustSiblingSizes(NodeT *Node[], unsigned Nodes,
+ unsigned CurSize[], const unsigned NewSize[]) {
+ // Move elements right.
+ for (int n = Nodes - 1; n; --n) {
+ if (CurSize[n] == NewSize[n])
+ continue;
+ for (int m = n - 1; m != -1; --m) {
+ int d = Node[n]->adjustFromLeftSib(CurSize[n], *Node[m], CurSize[m],
+ NewSize[n] - CurSize[n]);
+ CurSize[m] -= d;
+ CurSize[n] += d;
+ // Keep going if the current node was exhausted.
+ if (CurSize[n] >= NewSize[n])
+ break;
+ }
+ }
+
+ if (Nodes == 0)
+ return;
+
+ // Move elements left.
+ for (unsigned n = 0; n != Nodes - 1; ++n) {
+ if (CurSize[n] == NewSize[n])
+ continue;
+ for (unsigned m = n + 1; m != Nodes; ++m) {
+ int d = Node[m]->adjustFromLeftSib(CurSize[m], *Node[n], CurSize[n],
+ CurSize[n] - NewSize[n]);
+ CurSize[m] += d;
+ CurSize[n] -= d;
+ // Keep going if the current node was exhausted.
+ if (CurSize[n] >= NewSize[n])
+ break;
+ }
+ }
+
+#ifndef NDEBUG
+ for (unsigned n = 0; n != Nodes; n++)
+ assert(CurSize[n] == NewSize[n] && "Insufficient element shuffle");
+#endif
+}
+
+/// 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
+///
+/// Elements == sum(CurSize), and
+/// Elements + Grow <= Nodes * Capacity.
+///
+/// NewSize[] will be filled in such that:
+///
+/// sum(NewSize) == Elements, and
+/// NewSize[i] <= Capacity.
+///
+/// The returned index is the node where Position will go, so:
+///
+/// sum(NewSize[0..idx-1]) <= Position
+/// sum(NewSize[0..idx]) >= Position
+///
+/// The last equality, sum(NewSize[0..idx]) == Position, can only happen when
+/// Grow is set and NewSize[idx] == Capacity-1. The index points to the node
+/// before the one holding the Position'th element where there is room for an
+/// insertion.
+///
+/// @param Nodes The number of nodes.
+/// @param Elements Total elements in all nodes.
+/// @param Capacity The capacity of each node.
+/// @param CurSize Array[Nodes] of current node sizes, or NULL.
+/// @param NewSize Array[Nodes] to receive the new node sizes.
+/// @param Position Insert position.
+/// @param Grow Reserve space for a new element at Position.
+/// @return (node, offset) for Position.
+IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,
+ const unsigned *CurSize, unsigned NewSize[],
+ unsigned Position, bool Grow);
+
//===----------------------------------------------------------------------===//
-//--- 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 };
-};
-
-template <typename KeyT, typename ValT, typename Traits>
class NodeRef {
-public:
- typedef LeafNode<KeyT, ValT, NodeSizer<KeyT, ValT>::LeafSize, Traits> Leaf;
- typedef BranchNode<KeyT, ValT, NodeSizer<KeyT, ValT>::BranchSize,
- Traits> Branch;
-
-private:
+ 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(); }
-
- /// NodeRef - Create a reference to the leaf node p with n elements.
- NodeRef(Leaf *p, unsigned n) : pip(p, n - 1) {}
+ explicit operator bool() const { return pip.getOpaqueValue(); }
- /// NodeRef - Create a reference to the branch node p with n elements.
- NodeRef(Branch *p, unsigned n) : pip(p, n - 1) {}
+ /// NodeRef - Create a reference to the node p with n elements.
+ template <typename NodeT>
+ NodeRef(NodeT *p, unsigned n) : pip(p, n - 1) {
+ assert(n <= NodeT::Capacity && "Size too big for node");
+ }
/// size - Return the number of elements in the referenced node.
unsigned size() const { return pip.getInt() + 1; }
/// setSize - Update the node size.
void setSize(unsigned n) { pip.setInt(n - 1); }
- /// leaf - Return the referenced leaf node.
- /// Note there are no dynamic type checks.
- Leaf &leaf() const {
- return *reinterpret_cast<Leaf*>(pip.getPointer());
+ /// subtree - Access the i'th subtree reference in a branch node.
+ /// This depends on branch nodes storing the NodeRef array as their first
+ /// member.
+ NodeRef &subtree(unsigned i) const {
+ return reinterpret_cast<NodeRef*>(pip.getPointer())[i];
}
- /// branch - Return the referenced branch node.
- /// Note there are no dynamic type checks.
- Branch &branch() const {
- return *reinterpret_cast<Branch*>(pip.getPointer());
+ /// get - Dereference as a NodeT reference.
+ template <typename NodeT>
+ NodeT &get() const {
+ return *reinterpret_cast<NodeT*>(pip.getPointer());
}
bool operator==(const NodeRef &RHS) const {
};
//===----------------------------------------------------------------------===//
-//--- Leaf nodes ---//
+//--- IntervalMapImpl::LeafNode ---//
//===----------------------------------------------------------------------===//
//
// Leaf nodes store up to N disjoint intervals with corresponding values.
//
// These constraints are always satisfied:
//
-// - Traits::stopLess(key[i].start, key[i].stop) - Non-empty, sane intervals.
+// - Traits::stopLess(start(i), stop(i)) - Non-empty, sane intervals.
//
-// - Traits::stopLess(key[i].stop, key[i + 1].start) - Sorted.
+// - Traits::stopLess(stop(i), start(i + 1) - Sorted.
//
-// - val[i] != val[i + 1] ||
-// !Traits::adjacent(key[i].stop, key[i + 1].start) - Fully coalesced.
+// - value(i) != value(i + 1) || !Traits::adjacent(stop(i), start(i + 1))
+// - Fully coalesced.
//
//===----------------------------------------------------------------------===//
template <typename KeyT, typename ValT, unsigned N, typename Traits>
class LeafNode : public NodeBase<std::pair<KeyT, KeyT>, ValT, N> {
public:
- const KeyT &start(unsigned i) const { return this->key[i].first; }
- const KeyT &stop(unsigned i) const { return this->key[i].second; }
- const ValT &value(unsigned i) const { return this->val[i]; }
+ const KeyT &start(unsigned i) const { return this->first[i].first; }
+ const KeyT &stop(unsigned i) const { return this->first[i].second; }
+ const ValT &value(unsigned i) const { return this->second[i]; }
- KeyT &start(unsigned i) { return this->key[i].first; }
- KeyT &stop(unsigned i) { return this->key[i].second; }
- ValT &value(unsigned i) { return this->val[i]; }
+ KeyT &start(unsigned i) { return this->first[i].first; }
+ KeyT &stop(unsigned i) { return this->first[i].second; }
+ ValT &value(unsigned i) { return this->second[i]; }
/// findFrom - Find the first interval after i that may contain x.
/// @param i Starting index for the search.
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(unsigned Size) {
- errs() << " N" << this << " [shape=record label=\"{ " << Size << '/' << N;
- for (unsigned i = 0; i != Size; ++i)
- errs() << " | {" << start(i) << '-' << stop(i) << "|" << value(i) << '}';
- errs() << "}\"];\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.
//===----------------------------------------------------------------------===//
template <typename KeyT, typename ValT, unsigned N, typename Traits>
-class BranchNode : public NodeBase<KeyT, NodeRef<KeyT, ValT, Traits>, N> {
- typedef NodeRef<KeyT, ValT, Traits> NodeRefT;
+class BranchNode : public NodeBase<NodeRef, KeyT, N> {
public:
- const KeyT &stop(unsigned i) const { return this->key[i]; }
- const NodeRefT &subtree(unsigned i) const { return this->val[i]; }
+ const KeyT &stop(unsigned i) const { return this->second[i]; }
+ const NodeRef &subtree(unsigned i) const { return this->first[i]; }
- KeyT &stop(unsigned i) { return this->key[i]; }
- NodeRefT &subtree(unsigned i) { return this->val[i]; }
+ KeyT &stop(unsigned i) { return this->second[i]; }
+ NodeRef &subtree(unsigned i) { return this->first[i]; }
/// findFrom - Find the first subtree after i that may contain x.
/// @param i Starting index for the search.
/// safeLookup - Get the subtree containing x, Assuming that x is in range.
/// @param x Key to search for.
/// @return Subtree containing x
- NodeRefT safeLookup(KeyT x) const {
+ NodeRef safeLookup(KeyT x) const {
return subtree(safeFind(0, x));
}
/// @param Size Number of elements in node.
/// @param Node Subtree to insert.
/// @param Stop Last key in subtree.
- void insert(unsigned i, unsigned Size, NodeRefT Node, KeyT Stop) {
+ void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop) {
assert(Size < N && "branch node overflow");
assert(i <= Size && "Bad insert position");
this->shift(i, Size);
subtree(i) = Node;
stop(i) = Stop;
}
+};
+
+//===----------------------------------------------------------------------===//
+//--- 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 contains the tree navigation code that doesn't have to
+// be templatized.
+//
+//===----------------------------------------------------------------------===//
+
+class Path {
+ /// Entry - Each step in the path is a node pointer and an offset into that
+ /// node.
+ struct Entry {
+ void *node;
+ unsigned size;
+ unsigned offset;
+
+ Entry(void *Node, unsigned Size, unsigned Offset)
+ : node(Node), size(Size), offset(Offset) {}
+
+ Entry(NodeRef Node, unsigned Offset)
+ : node(&Node.subtree(0)), size(Node.size()), offset(Offset) {}
+
+ NodeRef &subtree(unsigned i) const {
+ return reinterpret_cast<NodeRef*>(node)[i];
+ }
+ };
+
+ /// path - The path entries, path[0] is the root node, path.back() is a leaf.
+ SmallVector<Entry, 4> path;
+
+public:
+ // Node accessors.
+ template <typename NodeT> NodeT &node(unsigned Level) const {
+ return *reinterpret_cast<NodeT*>(path[Level].node);
+ }
+ unsigned size(unsigned Level) const { return path[Level].size; }
+ unsigned offset(unsigned Level) const { return path[Level].offset; }
+ unsigned &offset(unsigned Level) { return path[Level].offset; }
-#ifndef NDEBUG
- void dump(unsigned Size) {
- errs() << " N" << this << " [shape=record label=\"" << Size << '/' << N;
- for (unsigned i = 0; i != Size; ++i)
- errs() << " | <s" << i << "> " << stop(i);
- errs() << "\"];\n";
- for (unsigned i = 0; i != Size; ++i)
- errs() << " N" << this << ":s" << i << " -> N"
- << &subtree(i).branch() << ";\n";
+ // Leaf accessors.
+ template <typename NodeT> NodeT &leaf() const {
+ return *reinterpret_cast<NodeT*>(path.back().node);
}
-#endif
+ unsigned leafSize() const { return path.back().size; }
+ unsigned leafOffset() const { return path.back().offset; }
+ unsigned &leafOffset() { return path.back().offset; }
+
+ /// valid - Return true if path is at a valid node, not at end().
+ bool valid() const {
+ return !path.empty() && path.front().offset < path.front().size;
+ }
+
+ /// height - Return the height of the tree corresponding to this path.
+ /// This matches map->height in a full path.
+ unsigned height() const { return path.size() - 1; }
+ /// subtree - Get the subtree referenced from Level. When the path is
+ /// consistent, node(Level + 1) == subtree(Level).
+ /// @param Level 0..height-1. The leaves have no subtrees.
+ NodeRef &subtree(unsigned Level) const {
+ return path[Level].subtree(path[Level].offset);
+ }
+
+ /// reset - Reset cached information about node(Level) from subtree(Level -1).
+ /// @param Level 1..height. THe node to update after parent node changed.
+ void reset(unsigned Level) {
+ path[Level] = Entry(subtree(Level - 1), offset(Level));
+ }
+
+ /// push - Add entry to path.
+ /// @param Node Node to add, should be subtree(path.size()-1).
+ /// @param Offset Offset into Node.
+ void push(NodeRef Node, unsigned Offset) {
+ path.push_back(Entry(Node, Offset));
+ }
+
+ /// pop - Remove the last path entry.
+ void pop() {
+ path.pop_back();
+ }
+
+ /// setSize - Set the size of a node both in the path and in the tree.
+ /// @param Level 0..height. Note that setting the root size won't change
+ /// map->rootSize.
+ /// @param Size New node size.
+ void setSize(unsigned Level, unsigned Size) {
+ path[Level].size = Size;
+ if (Level)
+ subtree(Level - 1).setSize(Size);
+ }
+
+ /// setRoot - Clear the path and set a new root node.
+ /// @param Node New root node.
+ /// @param Size New root size.
+ /// @param Offset Offset into root node.
+ void setRoot(void *Node, unsigned Size, unsigned Offset) {
+ path.clear();
+ path.push_back(Entry(Node, Size, Offset));
+ }
+
+ /// replaceRoot - Replace the current root node with two new entries after the
+ /// tree height has increased.
+ /// @param Root The new root node.
+ /// @param Size Number of entries in the new root.
+ /// @param Offsets Offsets into the root and first branch nodes.
+ void replaceRoot(void *Root, unsigned Size, IdxPair Offsets);
+
+ /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
+ /// @param Level Get the sibling to node(Level).
+ /// @return Left sibling, or NodeRef().
+ NodeRef getLeftSibling(unsigned Level) const;
+
+ /// moveLeft - Move path to the left sibling at Level. Leave nodes below Level
+ /// unaltered.
+ /// @param Level Move node(Level).
+ void moveLeft(unsigned Level);
+
+ /// fillLeft - Grow path to Height by taking leftmost branches.
+ /// @param Height The target height.
+ void fillLeft(unsigned Height) {
+ while (height() < Height)
+ push(subtree(height()), 0);
+ }
+
+ /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
+ /// @param Level Get the sinbling to node(Level).
+ /// @return Left sibling, or NodeRef().
+ NodeRef getRightSibling(unsigned Level) const;
+
+ /// moveRight - Move path to the left sibling at Level. Leave nodes below
+ /// Level unaltered.
+ /// @param Level Move node(Level).
+ void moveRight(unsigned Level);
+
+ /// atBegin - Return true if path is at begin().
+ bool atBegin() const {
+ for (unsigned i = 0, e = path.size(); i != e; ++i)
+ if (path[i].offset != 0)
+ return false;
+ return true;
+ }
+
+ /// atLastEntry - Return true if the path is at the last entry of the node at
+ /// Level.
+ /// @param Level Node to examine.
+ bool atLastEntry(unsigned Level) const {
+ return path[Level].offset == path[Level].size - 1;
+ }
+
+ /// legalizeForInsert - Prepare the path for an insertion at Level. When the
+ /// path is at end(), node(Level) may not be a legal node. legalizeForInsert
+ /// ensures that node(Level) is real by moving back to the last node at Level,
+ /// and setting offset(Level) to size(Level) if required.
+ /// @param Level The level where an insertion is about to take place.
+ void legalizeForInsert(unsigned Level) {
+ if (valid())
+ return;
+ moveLeft(Level);
+ ++path[Level].offset;
+ }
};
} // namespace IntervalMapImpl
unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize,
typename Traits = IntervalMapInfo<KeyT> >
class IntervalMap {
- typedef IntervalMapImpl::NodeRef<KeyT, ValT, Traits> NodeRef;
- typedef IntervalMapImpl::NodeSizer<KeyT, ValT> NodeSizer;
- typedef typename NodeRef::Leaf Leaf;
- typedef typename NodeRef::Branch Branch;
+ typedef IntervalMapImpl::NodeSizer<KeyT, ValT> Sizer;
+ typedef IntervalMapImpl::LeafNode<KeyT, ValT, Sizer::LeafSize, Traits> Leaf;
+ typedef IntervalMapImpl::BranchNode<KeyT, ValT, Sizer::BranchSize, Traits>
+ Branch;
typedef IntervalMapImpl::LeafNode<KeyT, ValT, N, Traits> RootLeaf;
typedef IntervalMapImpl::IdxPair IdxPair;
// corresponding RootBranch capacity.
enum {
DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) /
- (sizeof(KeyT) + sizeof(NodeRef)),
+ (sizeof(KeyT) + sizeof(IntervalMapImpl::NodeRef)),
RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1
};
- typedef IntervalMapImpl::BranchNode<KeyT, ValT, RootBranchCap, Traits> RootBranch;
+ typedef IntervalMapImpl::BranchNode<KeyT, ValT, RootBranchCap, Traits>
+ RootBranch;
// When branched, we store a global start key as well as the branch node.
struct RootBranchData {
RootBranch node;
};
- enum {
- RootDataSize = sizeof(RootBranchData) > sizeof(RootLeaf) ?
- sizeof(RootBranchData) : sizeof(RootLeaf)
- };
-
public:
- typedef typename NodeSizer::Allocator Allocator;
+ 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<RootLeaf, RootBranchData> data;
// Tree height.
// 0: Leaves in root.
const char *d;
T *t;
} u;
- u.d = data;
+ u.d = data.buffer;
return *u.t;
}
KeyT rootBranchStart() const { return rootBranchData().start; }
KeyT &rootBranchStart() { return rootBranchData().start; }
- Leaf *allocLeaf() {
- return new(allocator.template Allocate<Leaf>()) Leaf();
- }
- void deleteLeaf(Leaf *P) {
- P->~Leaf();
- allocator.Deallocate(P);
+ template <typename NodeT> NodeT *newNode() {
+ return new(allocator.template Allocate<NodeT>()) NodeT();
}
- Branch *allocBranch() {
- return new(allocator.template Allocate<Branch>()) Branch();
- }
- void deleteBranch(Branch *P) {
- P->~Branch();
+ template <typename NodeT> void deleteNode(NodeT *P) {
+ P->~NodeT();
allocator.Deallocate(P);
}
-
IdxPair branchRoot(unsigned Position);
IdxPair splitRoot(unsigned Position);
bool branched() const { return height > 0; }
ValT treeSafeLookup(KeyT x, ValT NotFound) const;
- void visitNodes(void (IntervalMap::*f)(NodeRef, unsigned Level));
- void deleteNode(NodeRef Node, unsigned Level);
+ void visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef,
+ unsigned Level));
+ void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level);
public:
explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) {
- assert((uintptr_t(data) & (alignOf<RootLeaf>() - 1)) == 0 &&
+ assert((uintptr_t(data.buffer) & (alignOf<RootLeaf>() - 1)) == 0 &&
"Insufficient alignment");
new(&rootLeaf()) RootLeaf();
}
/// It is assumed that no key in the interval is mapped to another value, but
/// overlapping intervals already mapped to y will be coalesced.
void insert(KeyT a, KeyT b, ValT y) {
- find(a).insert(a, b, y);
+ if (branched() || rootSize == RootLeaf::Capacity)
+ return find(a).insert(a, b, y);
+
+ // Easy insert into root leaf.
+ unsigned p = rootLeaf().findFrom(0, rootSize, a);
+ 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
- void dump();
- void dumpNode(NodeRef Node, unsigned Height);
-#endif
};
/// treeSafeLookup - Return the mapped value at x or NotFound, assuming a
treeSafeLookup(KeyT x, ValT NotFound) const {
assert(branched() && "treeLookup assumes a branched root");
- NodeRef NR = rootBranch().safeLookup(x);
+ IntervalMapImpl::NodeRef NR = rootBranch().safeLookup(x);
for (unsigned h = height-1; h; --h)
- NR = NR.branch().safeLookup(x);
- return NR.leaf().safeLookup(x, NotFound);
+ NR = NR.get<Branch>().safeLookup(x);
+ return NR.get<Leaf>().safeLookup(x, NotFound);
}
template <typename KeyT, typename ValT, unsigned N, typename Traits>
IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
branchRoot(unsigned Position) {
+ using namespace IntervalMapImpl;
// How many external leaf nodes to hold RootLeaf+1?
const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1;
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.
unsigned pos = 0;
NodeRef node[Nodes];
for (unsigned n = 0; n != Nodes; ++n) {
- node[n] = NodeRef(allocLeaf(), size[n]);
- node[n].leaf().copy(rootLeaf(), pos, 0, size[n]);
+ Leaf *L = newNode<Leaf>();
+ L->copy(rootLeaf(), pos, 0, size[n]);
+ node[n] = NodeRef(L, size[n]);
pos += size[n];
}
// Destroy the old leaf node, construct branch node instead.
switchRootToBranch();
for (unsigned n = 0; n != Nodes; ++n) {
- rootBranch().stop(n) = node[n].leaf().stop(size[n]-1);
+ rootBranch().stop(n) = node[n].template get<Leaf>().stop(size[n]-1);
rootBranch().subtree(n) = node[n];
}
- rootBranchStart() = node[0].leaf().start(0);
+ rootBranchStart() = node[0].template get<Leaf>().start(0);
rootSize = Nodes;
return NewOffset;
}
template <typename KeyT, typename ValT, unsigned N, typename Traits>
IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
splitRoot(unsigned Position) {
+ using namespace IntervalMapImpl;
// How many external leaf nodes to hold RootBranch+1?
const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1;
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.
unsigned Pos = 0;
NodeRef Node[Nodes];
for (unsigned n = 0; n != Nodes; ++n) {
- Node[n] = NodeRef(allocBranch(), Size[n]);
- Node[n].branch().copy(rootBranch(), Pos, 0, Size[n]);
+ Branch *B = newNode<Branch>();
+ B->copy(rootBranch(), Pos, 0, Size[n]);
+ Node[n] = NodeRef(B, Size[n]);
Pos += Size[n];
}
for (unsigned n = 0; n != Nodes; ++n) {
- rootBranch().stop(n) = Node[n].branch().stop(Size[n]-1);
+ rootBranch().stop(n) = Node[n].template get<Branch>().stop(Size[n]-1);
rootBranch().subtree(n) = Node[n];
}
rootSize = Nodes;
+ ++height;
return NewOffset;
}
/// visitNodes - Visit each external node.
template <typename KeyT, typename ValT, unsigned N, typename Traits>
void IntervalMap<KeyT, ValT, N, Traits>::
-visitNodes(void (IntervalMap::*f)(NodeRef, unsigned Height)) {
+visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, unsigned Height)) {
if (!branched())
return;
- SmallVector<NodeRef, 4> Refs, NextRefs;
+ SmallVector<IntervalMapImpl::NodeRef, 4> Refs, NextRefs;
// Collect level 0 nodes from the root.
for (unsigned i = 0; i != rootSize; ++i)
// Visit all branch nodes.
for (unsigned h = height - 1; h; --h) {
for (unsigned i = 0, e = Refs.size(); i != e; ++i) {
- Branch &B = Refs[i].branch();
for (unsigned j = 0, s = Refs[i].size(); j != s; ++j)
- NextRefs.push_back(B.subtree(j));
+ NextRefs.push_back(Refs[i].subtree(j));
(this->*f)(Refs[i], h);
}
Refs.clear();
template <typename KeyT, typename ValT, unsigned N, typename Traits>
void IntervalMap<KeyT, ValT, N, Traits>::
-deleteNode(NodeRef Node, unsigned Level) {
+deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) {
if (Level)
- deleteBranch(&Node.branch());
+ deleteNode(&Node.get<Branch>());
else
- deleteLeaf(&Node.leaf());
+ deleteNode(&Node.get<Leaf>());
}
template <typename KeyT, typename ValT, unsigned N, typename Traits>
rootSize = 0;
}
-#ifndef NDEBUG
-template <typename KeyT, typename ValT, unsigned N, typename Traits>
-void IntervalMap<KeyT, ValT, N, Traits>::
-dumpNode(NodeRef Node, unsigned Height) {
- if (Height)
- Node.branch().dump(Node.size());
- else
- Node.leaf().dump(Node.size());
-}
-
-template <typename KeyT, typename ValT, unsigned N, typename Traits>
-void IntervalMap<KeyT, ValT, N, Traits>::
-dump() {
- errs() << "digraph {\n";
- if (branched())
- rootBranch().dump(rootSize);
- else
- rootLeaf().dump(rootSize);
- visitNodes(&IntervalMap::dumpNode);
- errs() << "}\n";
-}
-#endif
-
//===----------------------------------------------------------------------===//
-//--- const_iterator ----//
+//--- IntervalMap::const_iterator ----//
//===----------------------------------------------------------------------===//
template <typename KeyT, typename ValT, unsigned N, typename Traits>
public std::iterator<std::bidirectional_iterator_tag, ValT> {
protected:
friend class IntervalMap;
- typedef std::pair<NodeRef, unsigned> PathEntry;
- typedef SmallVector<PathEntry, 4> Path;
// The map referred to.
IntervalMap *map;
- // The offset into map's root node.
- unsigned rootOffset;
-
// We store a full path from the root to the current position.
- //
- // When rootOffset == map->rootSize, we are at end() and path() is empty.
- // Otherwise, when branched these conditions hold:
- //
- // 1. path.front().first == rootBranch().subtree(rootOffset)
- // 2. path[i].first == path[i-1].first.branch().subtree(path[i-1].second)
- // 3. path.size() == map->height.
- //
- // Thus, path.back() always refers to the current leaf node unless the root is
- // unbranched.
- //
// The path may be partially filled, but never between iterator calls.
- Path path;
+ IntervalMapImpl::Path path;
- explicit const_iterator(IntervalMap &map)
- : map(&map), rootOffset(map.rootSize) {}
+ explicit const_iterator(const IntervalMap &map) :
+ map(const_cast<IntervalMap*>(&map)) {}
bool branched() const {
assert(map && "Invalid iterator");
return map->branched();
}
- NodeRef pathNode(unsigned h) const { return path[h].first; }
- NodeRef &pathNode(unsigned h) { return path[h].first; }
- unsigned pathOffset(unsigned h) const { return path[h].second; }
- unsigned &pathOffset(unsigned h) { return path[h].second; }
-
- Leaf &treeLeaf() const {
- assert(branched() && path.size() == map->height);
- return path.back().first.leaf();
- }
- unsigned treeLeafSize() const {
- assert(branched() && path.size() == map->height);
- return path.back().first.size();
- }
- unsigned &treeLeafOffset() {
- assert(branched() && path.size() == map->height);
- return path.back().second;
- }
- unsigned treeLeafOffset() const {
- assert(branched() && path.size() == map->height);
- return path.back().second;
- }
-
- // Get the next node ptr for an incomplete path.
- NodeRef pathNextDown() {
- assert(path.size() < map->height && "Path is already complete");
-
- if (path.empty())
- return map->rootBranch().subtree(rootOffset);
+ void setRoot(unsigned Offset) {
+ if (branched())
+ path.setRoot(&map->rootBranch(), map->rootSize, Offset);
else
- return path.back().first.branch().subtree(path.back().second);
+ path.setRoot(&map->rootLeaf(), map->rootSize, Offset);
}
- void pathFillLeft();
void pathFillFind(KeyT x);
- void pathFillRight();
-
- NodeRef leftSibling(unsigned level) const;
- NodeRef rightSibling(unsigned level) const;
-
- void treeIncrement();
- void treeDecrement();
void treeFind(KeyT x);
+ void treeAdvanceTo(KeyT x);
-public:
- /// valid - Return true if the current position is valid, false for end().
- bool valid() const {
- assert(map && "Invalid iterator");
- return rootOffset < map->rootSize;
+ /// 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());
}
- /// start - Return the beginning of the current interval.
- const KeyT &start() const {
+ /// unsafeStop - Writable access to stop() for iterator.
+ KeyT &unsafeStop() const {
assert(valid() && "Cannot access invalid iterator");
- return branched() ? treeLeaf().start(treeLeafOffset()) :
- map->rootLeaf().start(rootOffset);
+ return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) :
+ path.leaf<RootLeaf>().stop(path.leafOffset());
}
- /// stop - Return the end of the current interval.
- const KeyT &stop() const {
+ /// unsafeValue - Writable access to value() for iterator.
+ ValT &unsafeValue() const {
assert(valid() && "Cannot access invalid iterator");
- return branched() ? treeLeaf().stop(treeLeafOffset()) :
- map->rootLeaf().stop(rootOffset);
+ return branched() ? path.leaf<Leaf>().value(path.leafOffset()) :
+ path.leaf<RootLeaf>().value(path.leafOffset());
}
+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 {
- assert(valid() && "Cannot access invalid iterator");
- return branched() ? treeLeaf().value(treeLeafOffset()) :
- map->rootLeaf().value(rootOffset);
- }
+ const ValT &value() const { return unsafeValue(); }
- const ValT &operator*() const {
- return value();
- }
+ const ValT &operator*() const { return value(); }
bool operator==(const const_iterator &RHS) const {
assert(map == RHS.map && "Cannot compare iterators from different maps");
- return rootOffset == RHS.rootOffset &&
- (!valid() || !branched() || path.back() == RHS.path.back());
+ if (!valid())
+ return !RHS.valid();
+ if (path.leafOffset() != RHS.path.leafOffset())
+ return false;
+ return &path.template leaf<Leaf>() == &RHS.path.template leaf<Leaf>();
}
bool operator!=(const const_iterator &RHS) const {
/// goToBegin - Move to the first interval in map.
void goToBegin() {
- rootOffset = 0;
- path.clear();
+ setRoot(0);
if (branched())
- pathFillLeft();
+ path.fillLeft(map->height);
}
/// goToEnd - Move beyond the last interval in map.
void goToEnd() {
- rootOffset = map->rootSize;
- path.clear();
+ setRoot(map->rootSize);
}
/// preincrement - move to the next interval.
const_iterator &operator++() {
assert(valid() && "Cannot increment end()");
- if (!branched())
- ++rootOffset;
- else if (treeLeafOffset() != treeLeafSize() - 1)
- ++treeLeafOffset();
- else
- treeIncrement();
+ if (++path.leafOffset() == path.leafSize() && branched())
+ path.moveRight(map->height);
return *this;
}
/// predecrement - move to the previous interval.
const_iterator &operator--() {
- if (!branched()) {
- assert(rootOffset && "Cannot decrement begin()");
- --rootOffset;
- } else if (valid() && treeLeafOffset())
- --treeLeafOffset();
+ if (path.leafOffset() && (valid() || !branched()))
+ --path.leafOffset();
else
- treeDecrement();
+ path.moveLeft(map->height);
return *this;
}
if (branched())
treeFind(x);
else
- rootOffset = map->rootLeaf().findFrom(0, map->rootSize, x);
+ setRoot(map->rootLeaf().findFrom(0, map->rootSize, x));
}
/// advanceTo - Move to the first interval with stop >= x, or end().
/// 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
- rootOffset = map->rootLeaf().findFrom(rootOffset, map->rootSize, x);
+ path.leafOffset() =
+ map->rootLeaf().findFrom(path.leafOffset(), map->rootSize, x);
}
};
-// pathFillLeft - Complete path by following left-most branches.
-template <typename KeyT, typename ValT, unsigned N, typename Traits>
-void IntervalMap<KeyT, ValT, N, Traits>::
-const_iterator::pathFillLeft() {
- NodeRef NR = pathNextDown();
- for (unsigned i = map->height - path.size() - 1; i; --i) {
- path.push_back(PathEntry(NR, 0));
- NR = NR.branch().subtree(0);
- }
- path.push_back(PathEntry(NR, 0));
-}
-
-// pathFillFind - Complete path by searching for x.
+/// pathFillFind - Complete path by searching for x.
+/// @param x Key to search for.
template <typename KeyT, typename ValT, unsigned N, typename Traits>
void IntervalMap<KeyT, ValT, N, Traits>::
const_iterator::pathFillFind(KeyT x) {
- NodeRef NR = pathNextDown();
- for (unsigned i = map->height - path.size() - 1; i; --i) {
- unsigned p = NR.branch().safeFind(0, x);
- path.push_back(PathEntry(NR, p));
- NR = NR.branch().subtree(p);
+ IntervalMapImpl::NodeRef NR = path.subtree(path.height());
+ for (unsigned i = map->height - path.height() - 1; i; --i) {
+ unsigned p = NR.get<Branch>().safeFind(0, x);
+ path.push(NR, p);
+ NR = NR.subtree(p);
}
- path.push_back(PathEntry(NR, NR.leaf().safeFind(0, x)));
+ path.push(NR, NR.get<Leaf>().safeFind(0, x));
}
-// pathFillRight - Complete path by adding rightmost entries.
+/// treeFind - Find in a branched tree.
+/// @param x Key to search for.
template <typename KeyT, typename ValT, unsigned N, typename Traits>
void IntervalMap<KeyT, ValT, N, Traits>::
-const_iterator::pathFillRight() {
- NodeRef NR = pathNextDown();
- for (unsigned i = map->height - path.size() - 1; i; --i) {
- unsigned p = NR.size() - 1;
- path.push_back(PathEntry(NR, p));
- NR = NR.branch().subtree(p);
- }
- path.push_back(PathEntry(NR, NR.size() - 1));
-}
-
-/// leftSibling - find the left sibling node to path[level].
-/// @param level 0 is just below the root, map->height - 1 for the leaves.
-/// @return The left sibling NodeRef, or NULL.
-template <typename KeyT, typename ValT, unsigned N, typename Traits>
-typename IntervalMap<KeyT, ValT, N, Traits>::NodeRef
-IntervalMap<KeyT, ValT, N, Traits>::
-const_iterator::leftSibling(unsigned level) const {
- assert(branched() && "Not at a branched node");
- assert(level <= path.size() && "Bad level");
-
- // Go up the tree until we can go left.
- unsigned h = level;
- while (h && pathOffset(h - 1) == 0)
- --h;
-
- // We are at the first leaf node, no left sibling.
- if (!h && rootOffset == 0)
- return NodeRef();
-
- // NR is the subtree containing our left sibling.
- NodeRef NR = h ?
- pathNode(h - 1).branch().subtree(pathOffset(h - 1) - 1) :
- map->rootBranch().subtree(rootOffset - 1);
-
- // Keep right all the way down.
- for (; h != level; ++h)
- NR = NR.branch().subtree(NR.size() - 1);
- return NR;
-}
-
-/// rightSibling - find the right sibling node to path[level].
-/// @param level 0 is just below the root, map->height - 1 for the leaves.
-/// @return The right sibling NodeRef, or NULL.
-template <typename KeyT, typename ValT, unsigned N, typename Traits>
-typename IntervalMap<KeyT, ValT, N, Traits>::NodeRef
-IntervalMap<KeyT, ValT, N, Traits>::
-const_iterator::rightSibling(unsigned level) const {
- assert(branched() && "Not at a branched node");
- assert(level <= this->path.size() && "Bad level");
-
- // Go up the tree until we can go right.
- unsigned h = level;
- while (h && pathOffset(h - 1) == pathNode(h - 1).size() - 1)
- --h;
-
- // We are at the last leaf node, no right sibling.
- if (!h && rootOffset == map->rootSize - 1)
- return NodeRef();
-
- // NR is the subtree containing our right sibling.
- NodeRef NR = h ?
- pathNode(h - 1).branch().subtree(pathOffset(h - 1) + 1) :
- map->rootBranch().subtree(rootOffset + 1);
-
- // Keep left all the way down.
- for (; h != level; ++h)
- NR = NR.branch().subtree(0);
- return NR;
+const_iterator::treeFind(KeyT x) {
+ setRoot(map->rootBranch().findFrom(0, map->rootSize, x));
+ if (valid())
+ pathFillFind(x);
}
-// treeIncrement - Move to the beginning of the next leaf node.
+/// treeAdvanceTo - Find position after the current one.
+/// @param x Key to search for.
template <typename KeyT, typename ValT, unsigned N, typename Traits>
void IntervalMap<KeyT, ValT, N, Traits>::
-const_iterator::treeIncrement() {
- assert(branched() && "treeIncrement is not for small maps");
- assert(path.size() == map->height && "inconsistent iterator");
- do path.pop_back();
- while (!path.empty() && path.back().second == path.back().first.size() - 1);
- if (path.empty()) {
- ++rootOffset;
- if (!valid())
- return;
- } else
- ++path.back().second;
- pathFillLeft();
-}
+const_iterator::treeAdvanceTo(KeyT x) {
+ // Can we stay on the same leaf node?
+ if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) {
+ path.leafOffset() = path.leaf<Leaf>().safeFind(path.leafOffset(), x);
+ return;
+ }
-// treeDecrement - Move to the end of the previous leaf node.
-template <typename KeyT, typename ValT, unsigned N, typename Traits>
-void IntervalMap<KeyT, ValT, N, Traits>::
-const_iterator::treeDecrement() {
- assert(branched() && "treeDecrement is not for small maps");
- if (valid()) {
- assert(path.size() == map->height && "inconsistent iterator");
- do path.pop_back();
- while (!path.empty() && path.back().second == 0);
- }
- if (path.empty()) {
- assert(rootOffset && "cannot treeDecrement() on begin()");
- --rootOffset;
- } else
- --path.back().second;
- pathFillRight();
-}
+ // Drop the current leaf.
+ path.pop();
-// treeFind - Find in a branched tree.
-template <typename KeyT, typename ValT, unsigned N, typename Traits>
-void IntervalMap<KeyT, ValT, N, Traits>::
-const_iterator::treeFind(KeyT x) {
- path.clear();
- rootOffset = map->rootBranch().findFrom(0, map->rootSize, x);
+ // Search towards the root for a usable subtree.
+ if (path.height()) {
+ for (unsigned l = path.height() - 1; l; --l) {
+ if (!Traits::stopLess(path.node<Branch>(l).stop(path.offset(l)), x)) {
+ // The branch node at l+1 is usable
+ path.offset(l + 1) =
+ path.node<Branch>(l + 1).safeFind(path.offset(l + 1), x);
+ return pathFillFind(x);
+ }
+ path.pop();
+ }
+ // Is the level-1 Branch usable?
+ if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) {
+ path.offset(1) = path.node<Branch>(1).safeFind(path.offset(1), x);
+ return pathFillFind(x);
+ }
+ }
+
+ // We reached the root.
+ setRoot(map->rootBranch().findFrom(path.offset(0), map->rootSize, x));
if (valid())
pathFillFind(x);
}
-
//===----------------------------------------------------------------------===//
-//--- iterator ----//
+//--- IntervalMap::iterator ----//
//===----------------------------------------------------------------------===//
-namespace 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
- ///
- /// Elements == sum(CurSize), and
- /// Elements + Grow <= Nodes * Capacity.
- ///
- /// NewSize[] will be filled in such that:
- ///
- /// sum(NewSize) == Elements, and
- /// NewSize[i] <= Capacity.
- ///
- /// The returned index is the node where Position will go, so:
- ///
- /// sum(NewSize[0..idx-1]) <= Position
- /// sum(NewSize[0..idx]) >= Position
- ///
- /// The last equality, sum(NewSize[0..idx]) == Position, can only happen when
- /// Grow is set and NewSize[idx] == Capacity-1. The index points to the node
- /// before the one holding the Position'th element where there is room for an
- /// insertion.
- ///
- /// @param Nodes The number of nodes.
- /// @param Elements Total elements in all nodes.
- /// @param Capacity The capacity of each node.
- /// @param CurSize Array[Nodes] of current node sizes, or NULL.
- /// @param NewSize Array[Nodes] to receive the new node sizes.
- /// @param Position Insert position.
- /// @param Grow Reserve space for a new element at Position.
- /// @return (node, offset) for Position.
- IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,
- const unsigned *CurSize, unsigned NewSize[],
- unsigned Position, bool Grow);
-
-}
-
template <typename KeyT, typename ValT, unsigned N, typename Traits>
class IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator {
friend class IntervalMap;
explicit iterator(IntervalMap &map) : const_iterator(map) {}
- void setNodeSize(unsigned Level, unsigned Size);
void setNodeStop(unsigned Level, KeyT Stop);
- void insertNode(unsigned Level, NodeRef Node, KeyT Stop);
- void overflowLeaf();
+ bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop);
+ template <typename NodeT> bool overflow(unsigned Level);
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);
+ /// erase - Erase the current interval.
+ void erase();
+
+ iterator &operator++() {
+ const_iterator::operator++();
+ return *this;
+ }
+
+ iterator operator++(int) {
+ iterator tmp = *this;
+ operator++();
+ return tmp;
+ }
+
+ iterator &operator--() {
+ const_iterator::operator--();
+ return *this;
+ }
+
+ iterator operator--(int) {
+ iterator tmp = *this;
+ operator--();
+ return tmp;
+ }
+
};
-/// setNodeSize - Set the size of the node at path[level], updating both path
-/// and the real tree.
-/// @param level 0 is just below the root, map->height - 1 for the leaves.
-/// @param size New node size.
+/// 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>
-void IntervalMap<KeyT, ValT, N, Traits>::
-iterator::setNodeSize(unsigned Level, unsigned Size) {
- this->pathNode(Level).setSize(Size);
- if (Level)
- this->pathNode(Level-1).branch()
- .subtree(this->pathOffset(Level-1)).setSize(Size);
- else
- this->map->rootBranch().subtree(this->rootOffset).setSize(Size);
+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>::
iterator::setNodeStop(unsigned Level, KeyT Stop) {
- while (Level--) {
- this->pathNode(Level).branch().stop(this->pathOffset(Level)) = Stop;
- if (this->pathOffset(Level) != this->pathNode(Level).size() - 1)
+ // There are no references to the root node, so nothing to update.
+ if (!Level)
+ return;
+ IntervalMapImpl::Path &P = this->path;
+ // Update nodes pointing to the current node.
+ while (--Level) {
+ P.node<Branch>(Level).stop(P.offset(Level)) = Stop;
+ if (!P.atLastEntry(Level))
return;
}
- this->map->rootBranch().stop(this->rootOffset) = Stop;
+ // 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.
+/// @param Node The node to be inserted.
+/// @param Stop The last index in the new node.
+/// @return True if the tree height was increased.
template <typename KeyT, typename ValT, unsigned N, typename Traits>
-void IntervalMap<KeyT, ValT, N, Traits>::
-iterator::insertNode(unsigned Level, NodeRef Node, KeyT Stop) {
- if (!Level) {
+bool IntervalMap<KeyT, ValT, N, Traits>::
+iterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) {
+ assert(Level && "Cannot insert next to the root");
+ bool SplitRoot = false;
+ IntervalMap &IM = *this->map;
+ IntervalMapImpl::Path &P = this->path;
+
+ if (Level == 1) {
// Insert into the root branch node.
- IntervalMap &IM = *this->map;
if (IM.rootSize < RootBranch::Capacity) {
- IM.rootBranch().insert(this->rootOffset, IM.rootSize, Node, Stop);
- ++IM.rootSize;
- return;
+ IM.rootBranch().insert(P.offset(0), IM.rootSize, Node, Stop);
+ P.setSize(0, ++IM.rootSize);
+ P.reset(Level);
+ return SplitRoot;
}
// We need to split the root while keeping our position.
- IdxPair Offset = IM.splitRoot(this->rootOffset);
- this->rootOffset = Offset.first;
- this->path.insert(this->path.begin(),std::make_pair(
- this->map->rootBranch().subtree(Offset.first), Offset.second));
- Level = 1;
- }
+ SplitRoot = true;
+ IdxPair Offset = IM.splitRoot(P.offset(0));
+ P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset);
- // When inserting before end(), make sure we have a valid path.
- if (!this->valid()) {
- this->treeDecrement();
- ++this->pathOffset(Level-1);
+ // Fall through to insert at the new higher level.
+ ++Level;
}
- // Insert into the branch node at level-1.
- NodeRef NR = this->pathNode(Level-1);
- unsigned Offset = this->pathOffset(Level-1);
- assert(NR.size() < Branch::Capacity && "Branch overflow");
- NR.branch().insert(Offset, NR.size(), Node, Stop);
- setNodeSize(Level - 1, NR.size() + 1);
+ // When inserting before end(), make sure we have a valid path.
+ P.legalizeForInsert(--Level);
+
+ // Insert into the branch node at Level-1.
+ if (P.size(Level) == Branch::Capacity) {
+ // Branch node is full, handle handle the overflow.
+ assert(!SplitRoot && "Cannot overflow after splitting the root");
+ SplitRoot = overflow<Branch>(Level);
+ Level += SplitRoot;
+ }
+ P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop);
+ P.setSize(Level, P.size(Level) + 1);
+ if (P.atLastEntry(Level))
+ setNodeStop(Level, Stop);
+ P.reset(Level + 1);
+ return SplitRoot;
}
// insert
iterator::insert(KeyT a, KeyT b, ValT y) {
if (this->branched())
return treeInsert(a, b, y);
- IdxPair IP = this->map->rootLeaf().insertFrom(this->rootOffset,
- this->map->rootSize,
- a, b, y);
- if (IP.second <= RootLeaf::Capacity) {
- this->rootOffset = IP.first;
- this->map->rootSize = IP.second;
+ IntervalMap &IM = *this->map;
+ IntervalMapImpl::Path &P = this->path;
+
+ // Try simple root leaf insert.
+ unsigned Size = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y);
+
+ // Was the root node insert successful?
+ if (Size <= RootLeaf::Capacity) {
+ P.setSize(0, IM.rootSize = Size);
return;
}
- IdxPair Offset = this->map->branchRoot(this->rootOffset);
- this->rootOffset = Offset.first;
- this->path.push_back(std::make_pair(
- this->map->rootBranch().subtree(Offset.first), Offset.second));
+
+ // Root leaf node is full, we must branch.
+ IdxPair Offset = IM.branchRoot(P.leafOffset());
+ P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset);
+
+ // Now it fits in the new leaf.
treeInsert(a, b, y);
}
template <typename KeyT, typename ValT, unsigned N, typename Traits>
void IntervalMap<KeyT, ValT, N, Traits>::
iterator::treeInsert(KeyT a, KeyT b, ValT y) {
- if (!this->valid()) {
- // end() has an empty path. Go back to the last leaf node and use an
- // invalid offset instead.
- this->treeDecrement();
- ++this->treeLeafOffset();
- }
- IdxPair IP = this->treeLeaf().insertFrom(this->treeLeafOffset(),
- this->treeLeafSize(), a, b, y);
- this->treeLeafOffset() = IP.first;
- if (IP.second <= Leaf::Capacity) {
- setNodeSize(this->map->height - 1, IP.second);
- if (IP.first == IP.second - 1)
- setNodeStop(this->map->height - 1, this->treeLeaf().stop(IP.first));
+ using namespace IntervalMapImpl;
+ 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.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(P.height())) {
+ Leaf &SibLeaf = Sib.get<Leaf>();
+ unsigned SibOfs = Sib.size() - 1;
+ if (SibLeaf.value(SibOfs) == y &&
+ Traits::adjacent(SibLeaf.stop(SibOfs), a)) {
+ // This insertion will coalesce with the last entry in SibLeaf. We can
+ // handle it in two ways:
+ // 1. Extend SibLeaf.stop to b and be done, or
+ // 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(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(P.height(), SibLeaf.stop(SibOfs) = b);
+ return;
+ } else {
+ // We have both left and right coalescing. Erase the old SibLeaf entry
+ // and continue inserting the larger interval.
+ a = SibLeaf.start(SibOfs);
+ treeErase(/* UpdateRoot= */false);
+ }
+ }
+ } else {
+ // No left sibling means we are at begin(). Update cached bound.
+ this->map->rootBranchStart() = a;
+ }
+ }
+
+ // 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 (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.setSize(P.height(), Size);
+
+ // Insert was the last node entry, update stops.
+ if (Grow)
+ setNodeStop(P.height(), b);
+}
+
+/// erase - erase the current interval and move to the next position.
+template <typename KeyT, typename ValT, unsigned N, typename Traits>
+void IntervalMap<KeyT, ValT, N, Traits>::
+iterator::erase() {
+ IntervalMap &IM = *this->map;
+ IntervalMapImpl::Path &P = this->path;
+ assert(P.valid() && "Cannot erase end()");
+ if (this->branched())
+ return treeErase();
+ IM.rootLeaf().erase(P.leafOffset(), IM.rootSize);
+ P.setSize(0, --IM.rootSize);
+}
+
+/// treeErase - erase() for a branched tree.
+template <typename KeyT, typename ValT, unsigned N, typename Traits>
+void IntervalMap<KeyT, ValT, N, Traits>::
+iterator::treeErase(bool UpdateRoot) {
+ IntervalMap &IM = *this->map;
+ IntervalMapImpl::Path &P = this->path;
+ Leaf &Node = P.leaf<Leaf>();
+
+ // Nodes are not allowed to become empty.
+ if (P.leafSize() == 1) {
+ IM.deleteNode(&Node);
+ eraseNode(IM.height);
+ // Update rootBranchStart if we erased begin().
+ if (UpdateRoot && IM.branched() && P.valid() && P.atBegin())
+ IM.rootBranchStart() = P.leaf<Leaf>().start(0);
return;
}
- // Leaf node has no space.
- overflowLeaf();
- IP = this->treeLeaf().insertFrom(this->treeLeafOffset(),
- this->treeLeafSize(), a, b, y);
- this->treeLeafOffset() = IP.first;
- setNodeSize(this->map->height-1, IP.second);
- if (IP.first == IP.second - 1)
- setNodeStop(this->map->height - 1, this->treeLeaf().stop(IP.first));
- // FIXME: Handle cross-node coalescing.
+ // Erase current entry.
+ Node.erase(P.leafOffset(), P.leafSize());
+ unsigned NewSize = P.leafSize() - 1;
+ P.setSize(IM.height, NewSize);
+ // When we erase the last entry, update stop and move to a legal position.
+ if (P.leafOffset() == NewSize) {
+ setNodeStop(IM.height, Node.stop(NewSize - 1));
+ P.moveRight(IM.height);
+ } else if (UpdateRoot && P.atBegin())
+ IM.rootBranchStart() = P.leaf<Leaf>().start(0);
}
-// overflowLeaf - Distribute entries of the current leaf node evenly among
-// its siblings and ensure that the current node is not full.
-// This may require allocating a new node.
+/// eraseNode - Erase the current node at Level from its parent and move path to
+/// the first entry of the next sibling node.
+/// The node must be deallocated by the caller.
+/// @param Level 1..height, the root node cannot be erased.
template <typename KeyT, typename ValT, unsigned N, typename Traits>
void IntervalMap<KeyT, ValT, N, Traits>::
-iterator::overflowLeaf() {
+iterator::eraseNode(unsigned Level) {
+ assert(Level && "Cannot erase root node");
+ IntervalMap &IM = *this->map;
+ IntervalMapImpl::Path &P = this->path;
+
+ if (--Level == 0) {
+ IM.rootBranch().erase(P.offset(0), IM.rootSize);
+ P.setSize(0, --IM.rootSize);
+ // If this cleared the root, switch to height=0.
+ if (IM.empty()) {
+ IM.switchRootToLeaf();
+ this->setRoot(0);
+ return;
+ }
+ } else {
+ // Remove node ref from branch node at Level.
+ Branch &Parent = P.node<Branch>(Level);
+ if (P.size(Level) == 1) {
+ // Branch node became empty, remove it recursively.
+ IM.deleteNode(&Parent);
+ eraseNode(Level);
+ } else {
+ // Branch node won't become empty.
+ Parent.erase(P.offset(Level), P.size(Level));
+ unsigned NewSize = P.size(Level) - 1;
+ P.setSize(Level, NewSize);
+ // If we removed the last branch, update stop and move to a legal pos.
+ if (P.offset(Level) == NewSize) {
+ setNodeStop(Level, Parent.stop(NewSize - 1));
+ P.moveRight(Level);
+ }
+ }
+ }
+ // Update path cache for the new right sibling position.
+ if (P.valid()) {
+ P.reset(Level + 1);
+ P.offset(Level + 1) = 0;
+ }
+}
+
+/// 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.
+/// @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>
+template <typename NodeT>
+bool IntervalMap<KeyT, ValT, N, Traits>::
+iterator::overflow(unsigned Level) {
+ using namespace IntervalMapImpl;
+ Path &P = this->path;
unsigned CurSize[4];
- Leaf *Node[4];
+ NodeT *Node[4];
unsigned Nodes = 0;
unsigned Elements = 0;
- unsigned Offset = this->treeLeafOffset();
+ unsigned Offset = P.offset(Level);
// Do we have a left sibling?
- NodeRef LeftSib = this->leftSibling(this->map->height-1);
+ NodeRef LeftSib = P.getLeftSibling(Level);
if (LeftSib) {
Offset += Elements = CurSize[Nodes] = LeftSib.size();
- Node[Nodes++] = &LeftSib.leaf();
+ Node[Nodes++] = &LeftSib.get<NodeT>();
}
- // Current leaf node.
- Elements += CurSize[Nodes] = this->treeLeafSize();
- Node[Nodes++] = &this->treeLeaf();
+ // Current node.
+ Elements += CurSize[Nodes] = P.size(Level);
+ Node[Nodes++] = &P.node<NodeT>(Level);
// Do we have a right sibling?
- NodeRef RightSib = this->rightSibling(this->map->height-1);
+ NodeRef RightSib = P.getRightSibling(Level);
if (RightSib) {
- Offset += Elements = CurSize[Nodes] = RightSib.size();
- Node[Nodes++] = &RightSib.leaf();
+ Elements += CurSize[Nodes] = RightSib.size();
+ Node[Nodes++] = &RightSib.get<NodeT>();
}
// Do we need to allocate a new node?
unsigned NewNode = 0;
- if (Elements + 1 > Nodes * Leaf::Capacity) {
+ if (Elements + 1 > Nodes * NodeT::Capacity) {
// Insert NewNode at the penultimate position, or after a single node.
NewNode = Nodes == 1 ? 1 : Nodes - 1;
CurSize[Nodes] = CurSize[NewNode];
Node[Nodes] = Node[NewNode];
CurSize[NewNode] = 0;
- Node[NewNode] = this->map->allocLeaf();
+ Node[NewNode] = this->map->template newNode<NodeT>();
++Nodes;
}
// Compute the new element distribution.
unsigned NewSize[4];
- IdxPair NewOffset =
- IntervalMapImpl::distribute(Nodes, Elements, Leaf::Capacity,
- CurSize, NewSize, Offset, true);
+ IdxPair NewOffset = distribute(Nodes, Elements, NodeT::Capacity,
+ CurSize, NewSize, Offset, true);
+ adjustSiblingSizes(Node, Nodes, CurSize, NewSize);
// Move current location to the leftmost node.
if (LeftSib)
- this->treeDecrement();
-
- // Move elements right.
- for (int n = Nodes - 1; n; --n) {
- if (CurSize[n] == NewSize[n])
- continue;
- for (int m = n - 1; m != -1; --m) {
- int d = Node[n]->adjustFromLeftSib(CurSize[n], *Node[m], CurSize[m],
- NewSize[n] - CurSize[n]);
- CurSize[m] -= d;
- CurSize[n] += d;
- // Keep going if the current node was exhausted.
- if (CurSize[n] >= NewSize[n])
- break;
- }
- }
-
- // Move elements left.
- for (unsigned n = 0; n != Nodes - 1; ++n) {
- if (CurSize[n] == NewSize[n])
- continue;
- for (unsigned m = n + 1; m != Nodes; ++m) {
- int d = Node[m]->adjustFromLeftSib(CurSize[m], *Node[n], CurSize[n],
- CurSize[n] - NewSize[n]);
- CurSize[m] += d;
- CurSize[n] -= d;
- // Keep going if the current node was exhausted.
- if (CurSize[n] >= NewSize[n])
- break;
- }
- }
-
-#ifndef NDEBUG
- for (unsigned n = 0; n != Nodes; n++)
- assert(CurSize[n] == NewSize[n] && "Insufficient element shuffle");
-#endif
+ P.moveLeft(Level);
// Elements have been rearranged, now update node sizes and stops.
+ bool SplitRoot = false;
unsigned Pos = 0;
for (;;) {
KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1);
- if (NewNode && Pos == NewNode)
- insertNode(this->map->height - 1, NodeRef(Node[Pos], NewSize[Pos]), Stop);
- else {
- setNodeSize(this->map->height - 1, NewSize[Pos]);
- setNodeStop(this->map->height - 1, Stop);
+ if (NewNode && Pos == NewNode) {
+ SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop);
+ Level += SplitRoot;
+ } else {
+ P.setSize(Level, NewSize[Pos]);
+ setNodeStop(Level, Stop);
}
if (Pos + 1 == Nodes)
break;
- this->treeIncrement();
+ P.moveRight(Level);
++Pos;
}
// Where was I? Find NewOffset.
while(Pos != NewOffset.first) {
- this->treeDecrement();
+ P.moveLeft(Level);
--Pos;
}
- this->treeLeafOffset() = NewOffset.second;
+ P.offset(Level) = NewOffset.second;
+ 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