X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FIntervalMap.h;h=46549eed99394f4fa95c12c06c83a5706133769c;hb=2cd5836249784d4797cd4d79504debec4cb4ce37;hp=8606a178b7b7ec90c6822cddac7da5c1ab7fcf50;hpb=528900d9a46cf4acde3a90494f286116159d5e59;p=oota-llvm.git diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h index 8606a178b7b..46549eed993 100644 --- a/include/llvm/ADT/IntervalMap.h +++ b/include/llvm/ADT/IntervalMap.h @@ -99,18 +99,12 @@ #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 #include -// FIXME: Remove debugging code -#ifndef NDEBUG -#include "llvm/Support/raw_ostream.h" -#endif - namespace llvm { @@ -157,6 +151,26 @@ struct IntervalMapInfo { }; +template +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 { @@ -169,11 +183,11 @@ typedef std::pair IdxPair; //===----------------------------------------------------------------------===// -//--- 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 @@ -186,118 +200,214 @@ typedef std::pair IdxPair; // 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 +template 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 Other Node elements are copied from. /// @param i Beginning of the source range in other. /// @param j Beginning of the destination range in this. - /// @param count Number of elements to copy. + /// @param Count Number of elements to copy. template - void copy(const NodeBase &Other, unsigned i, + void copy(const NodeBase &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]; + } } - /// lmove - Move elements to the left. + /// moveLeft - Move elements to the left. /// @param i Beginning of the source range. /// @param j Beginning of the destination range. - /// @param count Number of elements to copy. - void lmove(unsigned i, unsigned j, unsigned Count) { - assert(j <= i && "Use rmove shift elements right"); + /// @param Count Number of elements to copy. + void moveLeft(unsigned i, unsigned j, unsigned Count) { + assert(j <= i && "Use moveRight shift elements right"); copy(*this, i, j, Count); } - /// rmove - Move elements to the right. + /// moveRight - Move elements to the right. /// @param i Beginning of the source range. /// @param j Beginning of the destination range. - /// @param count Number of elements to copy. - void rmove(unsigned i, unsigned j, unsigned Count) { - assert(i <= j && "Use lmove shift elements left"); + /// @param Count Number of elements to copy. + 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). /// @param i Beginning of the range to erase. /// @param j End of the range. (Exclusive). - /// @param size Number of elements in node. + /// @param Size Number of elements in node. void erase(unsigned i, unsigned j, unsigned Size) { - lmove(j, i, Size - 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. + /// @param Size Number of elements in node. void shift(unsigned i, unsigned Size) { - rmove(i, i + 1, Size - i); + moveRight(i, i + 1, Size - i); } - /// xferLeft - Transfer elements to a left sibling node. - /// @param size Number of elements in this. - /// @param sib Left sibling node. - /// @param ssize Number of elements in sib. - /// @param count Number of elements to transfer. - void xferLeft(unsigned Size, NodeBase &Sib, unsigned SSize, unsigned Count) { + /// transferToLeftSib - Transfer elements to a left sibling node. + /// @param Size Number of elements in this. + /// @param Sib Left sibling node. + /// @param SSize Number of elements in sib. + /// @param Count Number of elements to transfer. + void transferToLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, + unsigned Count) { Sib.copy(*this, 0, SSize, Count); erase(0, Count, Size); } - /// xferRight - Transfer elements to a right sibling node. - /// @param size Number of elements in this. - /// @param sib Right sibling node. - /// @param ssize Number of elements in sib. - /// @param count Number of elements to transfer. - void xferRight(unsigned Size, NodeBase &Sib, unsigned SSize, unsigned Count) { - Sib.rmove(0, Count, SSize); + /// transferToRightSib - Transfer elements to a right sibling node. + /// @param Size Number of elements in this. + /// @param Sib Right sibling node. + /// @param SSize Number of elements in sib. + /// @param Count Number of elements to transfer. + void transferToRightSib(unsigned Size, NodeBase &Sib, unsigned SSize, + unsigned Count) { + Sib.moveRight(0, Count, SSize); Sib.copy(*this, Size-Count, 0, Count); } - /// adjLeftSib - Adjust the number if elements in this node by moving + /// adjustFromLeftSib - Adjust the number if elements in this node by moving /// elements to or from a left sibling node. - /// @param size Number of elements in this. - /// @param sib Right sibling node. - /// @param ssize Number of elements in sib. - /// @param add The number of elements to add to this node, possibly < 0. + /// @param Size Number of elements in this. + /// @param Sib Right sibling node. + /// @param SSize Number of elements in sib. + /// @param Add The number of elements to add to this node, possibly < 0. /// @return Number of elements added to this node, possibly negative. - int adjLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add) { + int adjustFromLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add) { if (Add > 0) { // We want to grow, copy from sib. unsigned Count = std::min(std::min(unsigned(Add), SSize), N - Size); - Sib.xferRight(SSize, *this, Size, Count); + Sib.transferToRightSib(SSize, *this, Size, Count); return Count; } else { // We want to shrink, copy to sib. unsigned Count = std::min(std::min(unsigned(-Add), Size), N - SSize); - xferLeft(Size, Sib, SSize, Count); + transferToLeftSib(Size, Sib, SSize, Count); return -Count; } } }; +/// 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 +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. @@ -353,7 +463,7 @@ struct NodeSizer { //===----------------------------------------------------------------------===// -//--- NodeRef ---// +//--- IntervalMapImpl::NodeRef ---// //===----------------------------------------------------------------------===// // // B+-tree nodes can be leaves or branches, so we need a polymorphic node @@ -373,20 +483,12 @@ struct NodeSizer { // //===----------------------------------------------------------------------===// -struct CacheAlignedPointerTraits { - static inline void *getAsVoidPointer(void *P) { return P; } - static inline void *getFromVoidPointer(void *P) { return P; } - enum { NumLowBitsAvailable = Log2CacheLine }; -}; - -template class NodeRef { -public: - typedef LeafNode::LeafSize, Traits> Leaf; - typedef BranchNode::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 pip; public: @@ -394,13 +496,13 @@ 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) {} + LLVM_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 + 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; } @@ -408,16 +510,17 @@ public: /// 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(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(pip.getPointer())[i]; } - /// branch - Return the referenced branch node. - /// Note there are no dynamic type checks. - Branch &branch() const { - return *reinterpret_cast(pip.getPointer()); + /// get - Dereference as a NodeT reference. + template + NodeT &get() const { + return *reinterpret_cast(pip.getPointer()); } bool operator==(const NodeRef &RHS) const { @@ -433,7 +536,7 @@ public: }; //===----------------------------------------------------------------------===// -//--- Leaf nodes ---// +//--- IntervalMapImpl::LeafNode ---// //===----------------------------------------------------------------------===// // // Leaf nodes store up to N disjoint intervals with corresponding values. @@ -443,29 +546,29 @@ public: // // 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 class LeafNode : public NodeBase, 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. - /// @param size Number of elements in node. + /// @param Size Number of elements in node. /// @param x Key to search for. /// @return First index with !stopLess(key[i].stop, x), or size. /// This is the first interval that can possibly contain x. @@ -503,120 +606,76 @@ public: 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 size Number of elements in node. +/// @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 -IdxPair LeafNode:: -insertFrom(unsigned i, unsigned Size, KeyT a, KeyT b, ValT y) { +unsigned LeafNode:: +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 -unsigned LeafNode:: -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. @@ -635,18 +694,17 @@ extendStop(unsigned i, unsigned Size, KeyT b) { //===----------------------------------------------------------------------===// template -class BranchNode : public NodeBase, N> { - typedef NodeRef NodeRefT; +class BranchNode : public NodeBase { 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. - /// @param size Number of elements in node. + /// @param Size Number of elements in node. /// @param x Key to search for. /// @return First index with !stopLess(key[i], x), or size. /// This is the first subtree that can possibly contain x. @@ -676,35 +734,188 @@ public: /// 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)); } /// insert - Insert a new (subtree, stop) pair. /// @param i Insert position, following entries will be shifted. - /// @param size Number of elements in node. - /// @param node Subtree to insert. - /// @param stp Last key in subtree. - void insert(unsigned i, unsigned Size, NodeRefT Node, KeyT Stop) { + /// @param Size Number of elements in node. + /// @param Node Subtree to insert. + /// @param Stop Last key in subtree. + 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(node)[i]; + } + }; + + /// path - The path entries, path[0] is the root node, path.back() is a leaf. + SmallVector path; + +public: + // Node accessors. + template NodeT &node(unsigned Level) const { + return *reinterpret_cast(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() << " | " << stop(i); - errs() << "\"];\n"; - for (unsigned i = 0; i != Size; ++i) - errs() << " N" << this << ":s" << i << " -> N" - << &subtree(i).branch() << ";\n"; + // Leaf accessors. + template NodeT &leaf() const { + return *reinterpret_cast(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 @@ -718,10 +929,10 @@ template ::LeafSize, typename Traits = IntervalMapInfo > class IntervalMap { - typedef IntervalMapImpl::NodeRef NodeRef; - typedef IntervalMapImpl::NodeSizer NodeSizer; - typedef typename NodeRef::Leaf Leaf; - typedef typename NodeRef::Branch Branch; + typedef IntervalMapImpl::NodeSizer Sizer; + typedef IntervalMapImpl::LeafNode Leaf; + typedef IntervalMapImpl::BranchNode + Branch; typedef IntervalMapImpl::LeafNode RootLeaf; typedef IntervalMapImpl::IdxPair IdxPair; @@ -729,11 +940,12 @@ class IntervalMap { // 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 RootBranch; + typedef IntervalMapImpl::BranchNode + RootBranch; // When branched, we store a global start key as well as the branch node. struct RootBranchData { @@ -747,7 +959,10 @@ class IntervalMap { }; 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. @@ -803,23 +1018,15 @@ private: KeyT rootBranchStart() const { return rootBranchData().start; } KeyT &rootBranchStart() { return rootBranchData().start; } - Leaf *allocLeaf() { - return new(allocator.template Allocate()) Leaf(); - } - void freeLeaf(Leaf *P) { - P->~Leaf(); - allocator.Deallocate(P); + template NodeT *newNode() { + return new(allocator.template Allocate()) NodeT(); } - Branch *allocBranch() { - return new(allocator.template Allocate()) Branch(); - } - void freeBranch(Branch *P) { - P->~Branch(); + template void deleteNode(NodeT *P) { + P->~NodeT(); allocator.Deallocate(P); } - IdxPair branchRoot(unsigned Position); IdxPair splitRoot(unsigned Position); @@ -838,8 +1045,9 @@ private: bool branched() const { return height > 0; } ValT treeSafeLookup(KeyT x, ValT NotFound) const; - - void visitNodes(void (IntervalMap::*f)(NodeRef, 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) { @@ -848,6 +1056,11 @@ public: new(&rootLeaf()) RootLeaf(); } + ~IntervalMap() { + clear(); + rootLeaf().~RootLeaf(); + } + /// empty - Return true when no intervals are mapped. bool empty() const { return rootSize == 0; @@ -878,16 +1091,24 @@ public: /// 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. + void clear(); + class const_iterator; class iterator; friend class const_iterator; friend class iterator; const_iterator begin() const { - iterator I(*this); + const_iterator I(*this); I.goToBegin(); return I; } @@ -899,7 +1120,7 @@ public: } const_iterator end() const { - iterator I(*this); + const_iterator I(*this); I.goToEnd(); return I; } @@ -913,7 +1134,7 @@ public: /// find - Return an iterator pointing to the first interval ending at or /// after x, or end(). const_iterator find(KeyT x) const { - iterator I(*this); + const_iterator I(*this); I.find(x); return I; } @@ -923,11 +1144,6 @@ public: 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 @@ -937,10 +1153,10 @@ ValT IntervalMap:: 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().safeLookup(x); + return NR.get().safeLookup(x, NotFound); } @@ -949,6 +1165,7 @@ treeSafeLookup(KeyT x, ValT NotFound) const { template IntervalMapImpl::IdxPair IntervalMap:: branchRoot(unsigned Position) { + using namespace IntervalMapImpl; // How many external leaf nodes to hold RootLeaf+1? const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1; @@ -960,25 +1177,26 @@ branchRoot(unsigned Position) { 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(); + 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().stop(size[n]-1); rootBranch().subtree(n) = node[n]; } - rootBranchStart() = node[0].leaf().start(0); + rootBranchStart() = node[0].template get().start(0); rootSize = Nodes; return NewOffset; } @@ -988,6 +1206,7 @@ branchRoot(unsigned Position) { template IntervalMapImpl::IdxPair IntervalMap:: splitRoot(unsigned Position) { + using namespace IntervalMapImpl; // How many external leaf nodes to hold RootBranch+1? const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1; @@ -999,33 +1218,35 @@ splitRoot(unsigned Position) { 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(); + 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().stop(Size[n]-1); rootBranch().subtree(n) = Node[n]; } rootSize = Nodes; + ++height; return NewOffset; } /// visitNodes - Visit each external node. template void IntervalMap:: -visitNodes(void (IntervalMap::*f)(NodeRef, unsigned Height)) { +visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, unsigned Height)) { if (!branched()) return; - SmallVector Refs, NextRefs; + SmallVector Refs, NextRefs; // Collect level 0 nodes from the root. for (unsigned i = 0; i != rootSize; ++i) @@ -1034,9 +1255,8 @@ visitNodes(void (IntervalMap::*f)(NodeRef, unsigned Height)) { // 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(); @@ -1048,31 +1268,27 @@ visitNodes(void (IntervalMap::*f)(NodeRef, unsigned Height)) { (this->*f)(Refs[i], 0); } -#ifndef NDEBUG template void IntervalMap:: -dumpNode(NodeRef Node, unsigned Height) { - if (Height) - Node.branch().dump(Node.size()); +deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) { + if (Level) + deleteNode(&Node.get()); else - Node.leaf().dump(Node.size()); + deleteNode(&Node.get()); } template void IntervalMap:: -dump() { - errs() << "digraph {\n"; - if (branched()) - rootBranch().dump(rootSize); - else - rootLeaf().dump(rootSize); - visitNodes(&IntervalMap::dumpNode); - errs() << "}\n"; +clear() { + if (branched()) { + visitNodes(&IntervalMap::deleteNode); + switchRootToLeaf(); + } + rootSize = 0; } -#endif //===----------------------------------------------------------------------===// -//--- const_iterator ----// +//--- IntervalMap::const_iterator ----// //===----------------------------------------------------------------------===// template @@ -1080,117 +1296,86 @@ class IntervalMap::const_iterator : public std::iterator { protected: friend class IntervalMap; - typedef std::pair PathEntry; - typedef SmallVector 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(&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().start(path.leafOffset()) : + path.leaf().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().stop(path.leafOffset()) : + path.leaf().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().value(path.leafOffset()) : + path.leaf().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(&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() == &RHS.path.template leaf(); } bool operator!=(const const_iterator &RHS) const { @@ -1199,27 +1384,21 @@ public: /// 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; } @@ -1232,13 +1411,10 @@ public: /// predecrement - move to the previous interval. const_iterator &operator--() { - if (!branched()) { - assert(rootOffset && "Cannot decrement begin()"); - --rootOffset; - } else if (treeLeafOffset()) - --treeLeafOffset(); + if (path.leafOffset() && (valid() || !branched())) + --path.leafOffset(); else - treeDecrement(); + path.moveLeft(map->height); return *this; } @@ -1255,209 +1431,90 @@ public: 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 -void IntervalMap:: -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 void IntervalMap:: 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().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().safeFind(0, x)); } -// pathFillRight - Complete path by adding rightmost entries. +/// treeFind - Find in a branched tree. +/// @param x Key to search for. template void IntervalMap:: -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 IntervalMap::NodeRef -IntervalMap:: -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 IntervalMap::NodeRef -IntervalMap:: -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 void IntervalMap:: -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().stop(path.leafSize() - 1), x)) { + path.leafOffset() = path.leaf().safeFind(path.leafOffset(), x); + return; + } -// treeDecrement - Move to the end of the previous leaf node. -template -void IntervalMap:: -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 -void IntervalMap:: -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(l).stop(path.offset(l)), x)) { + // The branch node at l+1 is usable + path.offset(l + 1) = + path.node(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(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 class IntervalMap::iterator : public const_iterator { friend class IntervalMap; @@ -1465,79 +1522,256 @@ class IntervalMap::iterator : public const_iterator { 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 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 -void IntervalMap:: -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:: +iterator::canCoalesceLeft(KeyT Start, ValT Value) { + using namespace IntervalMapImpl; + Path &P = this->path; + if (!this->branched()) { + unsigned i = P.leafOffset(); + RootLeaf &Node = P.leaf(); + return i && Node.value(i-1) == Value && + Traits::adjacent(Node.stop(i-1), Start); + } + // Branched. + if (unsigned i = P.leafOffset()) { + Leaf &Node = P.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(); + 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 +bool IntervalMap:: +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(); + return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i)); + } + // Branched. + if (i < P.leafSize()) { + Leaf &Node = P.leaf(); + return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i)); + } else if (NodeRef NR = P.getRightSibling(P.height())) { + Leaf &Node = NR.get(); + 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 void IntervalMap:: 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(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(Level).stop(P.offset(Level)) = Stop; +} + +template +void IntervalMap:: +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 +void IntervalMap:: +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 +void IntervalMap:: +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 -void IntervalMap:: -iterator::insertNode(unsigned Level, NodeRef Node, KeyT Stop) { - if (!Level) { +bool IntervalMap:: +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(Level); + Level += SplitRoot; + } + P.node(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 @@ -1546,18 +1780,23 @@ void IntervalMap:: 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); } @@ -1565,144 +1804,363 @@ iterator::insert(KeyT a, KeyT b, ValT y) { template void IntervalMap:: 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().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(); + 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(); + 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().insertFrom(P.leafOffset(), Size, a, b, y); + + // Leaf insertion unsuccessful? Overflow and try again. + if (Size > Leaf::Capacity) { + overflow(P.height()); + Grow = P.leafOffset() == P.leafSize(); + Size = P.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 +void IntervalMap:: +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 +void IntervalMap:: +iterator::treeErase(bool UpdateRoot) { + IntervalMap &IM = *this->map; + IntervalMapImpl::Path &P = this->path; + Leaf &Node = P.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().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().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 void IntervalMap:: -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(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 +template +bool IntervalMap:: +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(); } - // Current leaf node. - Elements += CurSize[Nodes] = this->treeLeafSize(); - Node[Nodes++] = &this->treeLeaf(); + // Current node. + Elements += CurSize[Nodes] = P.size(Level); + Node[Nodes++] = &P.node(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(); } // 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(); ++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]->adjLeftSib(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]->adjLeftSib(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 +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