X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FIntervalMap.h;h=f8843b2a4e507a81de13fd73522e801c95fdf0fc;hb=HEAD;hp=314af5092397d61de57686f6b1edda7229e9bcad;hpb=6c76f5fa2fb839c736c572f45c138e5b3f549530;p=oota-llvm.git diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h index 314af509239..f8843b2a4e5 100644 --- a/include/llvm/ADT/IntervalMap.h +++ b/include/llvm/ADT/IntervalMap.h @@ -99,16 +99,13 @@ #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 #include -// FIXME: Remove debugging code. -#include "llvm/Support/raw_ostream.h" - namespace llvm { @@ -155,6 +152,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 { @@ -167,7 +184,7 @@ typedef std::pair IdxPair; //===----------------------------------------------------------------------===// -//--- Node Storage ---// +//--- IntervalMapImpl::NodeBase ---// //===----------------------------------------------------------------------===// // // Both leaf and branch nodes store vectors of pairs. @@ -211,8 +228,10 @@ public: unsigned j, unsigned Count) { assert(i + Count <= M && "Invalid source range"); assert(j + Count <= N && "Invalid dest range"); - std::copy(Other.first + i, Other.first + i + Count, first + j); - std::copy(Other.second + i, Other.second + i + Count, second + j); + for (unsigned e = i + Count; i != e; ++i, ++j) { + first[j] = Other.first[i]; + second[j] = Other.second[i]; + } } /// moveLeft - Move elements to the left. @@ -231,8 +250,10 @@ public: void moveRight(unsigned i, unsigned j, unsigned Count) { assert(i <= j && "Use moveLeft shift elements left"); assert(j + Count <= N && "Invalid range"); - std::copy_backward(first + i, first + i + Count, first + j + Count); - std::copy_backward(second + i, second + i + Count, second + j + Count); + while (Count--) { + first[j + Count] = first[i + Count]; + second[j + Count] = second[i + Count]; + } } /// erase - Erase elements [i;j). @@ -243,6 +264,13 @@ public: 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. @@ -294,9 +322,93 @@ public: } }; +/// 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. @@ -352,7 +464,7 @@ struct NodeSizer { //===----------------------------------------------------------------------===// -//--- NodeRef ---// +//--- IntervalMapImpl::NodeRef ---// //===----------------------------------------------------------------------===// // // B+-tree nodes can be leaves or branches, so we need a polymorphic node @@ -372,13 +484,12 @@ struct NodeSizer { // //===----------------------------------------------------------------------===// -struct CacheAlignedPointerTraits { - static inline void *getAsVoidPointer(void *P) { return P; } - static inline void *getFromVoidPointer(void *P) { return P; } - enum { NumLowBitsAvailable = Log2CacheLine }; -}; - class NodeRef { + struct CacheAlignedPointerTraits { + static inline void *getAsVoidPointer(void *P) { return P; } + static inline void *getFromVoidPointer(void *P) { return P; } + enum { NumLowBitsAvailable = Log2CacheLine }; + }; PointerIntPair pip; public: @@ -386,7 +497,7 @@ public: NodeRef() {} /// operator bool - Detect a null ref. - operator bool() const { return pip.getOpaqueValue(); } + explicit operator bool() const { return pip.getOpaqueValue(); } /// NodeRef - Create a reference to the node p with n elements. template @@ -403,7 +514,7 @@ public: /// 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) { + NodeRef &subtree(unsigned i) const { return reinterpret_cast(pip.getPointer())[i]; } @@ -426,7 +537,7 @@ public: }; //===----------------------------------------------------------------------===// -//--- Leaf nodes ---// +//--- IntervalMapImpl::LeafNode ---// //===----------------------------------------------------------------------===// // // Leaf nodes store up to N disjoint intervals with corresponding values. @@ -496,120 +607,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 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. @@ -684,19 +751,172 @@ public: subtree(i) = Node; stop(i) = Stop; } +}; -#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).template get() << ";\n"; +//===----------------------------------------------------------------------===// +//--- 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; } + + // Leaf accessors. + template NodeT &leaf() const { + return *reinterpret_cast(path.back().node); + } + 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)); } -#endif + /// 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 @@ -734,23 +954,15 @@ class IntervalMap { RootBranch node; }; - enum { - RootDataSize = sizeof(RootBranchData) > sizeof(RootLeaf) ? - sizeof(RootBranchData) : sizeof(RootLeaf) - }; - public: typedef typename Sizer::Allocator Allocator; + typedef KeyT KeyType; + typedef ValT ValueType; + typedef Traits KeyTraits; private: // The root data is either a RootLeaf or a RootBranchData instance. - // 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 data; // Tree height. // 0: Leaves in root. @@ -771,7 +983,7 @@ private: const char *d; T *t; } u; - u.d = data; + u.d = data.buffer; return *u.t; } @@ -796,23 +1008,15 @@ private: KeyT rootBranchStart() const { return rootBranchData().start; } KeyT &rootBranchStart() { return rootBranchData().start; } - Leaf *allocLeaf() { - return new(allocator.template Allocate()) Leaf(); - } - void deleteLeaf(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 deleteBranch(Branch *P) { - P->~Branch(); + template void deleteNode(NodeT *P) { + P->~NodeT(); allocator.Deallocate(P); } - IdxPair branchRoot(unsigned Position); IdxPair splitRoot(unsigned Position); @@ -837,7 +1041,7 @@ private: public: explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) { - assert((uintptr_t(data) & (alignOf() - 1)) == 0 && + assert((uintptr_t(data.buffer) & (alignOf() - 1)) == 0 && "Insufficient alignment"); new(&rootLeaf()) RootLeaf(); } @@ -877,7 +1081,12 @@ 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. @@ -889,7 +1098,7 @@ public: friend class iterator; const_iterator begin() const { - iterator I(*this); + const_iterator I(*this); I.goToBegin(); return I; } @@ -901,7 +1110,7 @@ public: } const_iterator end() const { - iterator I(*this); + const_iterator I(*this); I.goToEnd(); return I; } @@ -915,7 +1124,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; } @@ -925,11 +1134,6 @@ public: I.find(x); return I; } - -#ifndef NDEBUG - void dump(); - void dumpNode(IntervalMapImpl::NodeRef Node, unsigned Height); -#endif }; /// treeSafeLookup - Return the mapped value at x or NotFound, assuming a @@ -963,15 +1167,16 @@ 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].template get().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]; } @@ -1003,15 +1208,16 @@ 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].template get().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]; } @@ -1056,9 +1262,9 @@ template void IntervalMap:: deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) { if (Level) - deleteBranch(&Node.get()); + deleteNode(&Node.get()); else - deleteLeaf(&Node.get()); + deleteNode(&Node.get()); } template @@ -1071,31 +1277,8 @@ clear() { rootSize = 0; } -#ifndef NDEBUG -template -void IntervalMap:: -dumpNode(IntervalMapImpl::NodeRef Node, unsigned Height) { - if (Height) - Node.get().dump(Node.size()); - else - Node.get().dump(Node.size()); -} - -template -void IntervalMap:: -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 @@ -1103,117 +1286,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.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(); } - IntervalMapImpl::NodeRef pathNode(unsigned h) const { return path[h].first; } - IntervalMapImpl::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.template get(); - } - 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. - IntervalMapImpl::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.subtree(path.back().second); + path.setRoot(&map->rootLeaf(), map->rootSize, Offset); } - void pathFillLeft(); void pathFillFind(KeyT x); - void pathFillRight(); - - IntervalMapImpl::NodeRef leftSibling(unsigned level) const; - IntervalMapImpl::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 { @@ -1222,27 +1374,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; } @@ -1255,13 +1401,10 @@ public: /// 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; } @@ -1278,209 +1421,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() { - IntervalMapImpl::NodeRef NR = pathNextDown(); - for (unsigned i = map->height - path.size() - 1; i; --i) { - path.push_back(PathEntry(NR, 0)); - NR = NR.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) { - IntervalMapImpl::NodeRef NR = pathNextDown(); - for (unsigned i = map->height - path.size() - 1; i; --i) { + 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_back(PathEntry(NR, p)); + path.push(NR, p); NR = NR.subtree(p); } - path.push_back(PathEntry(NR, NR.get().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() { - IntervalMapImpl::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.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 -IntervalMapImpl::NodeRef IntervalMap:: -const_iterator::leftSibling(unsigned level) const { - using namespace IntervalMapImpl; - 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).subtree(pathOffset(h - 1) - 1) : - map->rootBranch().subtree(rootOffset - 1); - - // Keep right all the way down. - for (; h != level; ++h) - NR = NR.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 -IntervalMapImpl::NodeRef IntervalMap:: -const_iterator::rightSibling(unsigned level) const { - using namespace IntervalMapImpl; - 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).subtree(pathOffset(h - 1) + 1) : - map->rootBranch().subtree(rootOffset + 1); - - // Keep left all the way down. - for (; h != level; ++h) - NR = NR.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; @@ -1488,43 +1512,206 @@ 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); 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).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).template get() - .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. @@ -1536,42 +1723,44 @@ iterator::setNodeStop(unsigned Level, KeyT Stop) { template 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) { + 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; + 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. SplitRoot = true; - 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; + IdxPair Offset = IM.splitRoot(P.offset(0)); + P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset); + + // Fall through to insert at the new higher level. + ++Level; } // When inserting before end(), make sure we have a valid path. - if (!this->valid()) { - this->treeDecrement(); - ++this->pathOffset(Level-1); - } + P.legalizeForInsert(--Level); - // Insert into the branch node at level-1. - if (this->pathNode(Level-1).size() == Branch::Capacity) { + // 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 - 1); + SplitRoot = overflow(Level); Level += SplitRoot; } - IntervalMapImpl::NodeRef NR = this->pathNode(Level-1); - unsigned Offset = this->pathOffset(Level-1); - NR.get().insert(Offset, NR.size(), Node, Stop); - setNodeSize(Level - 1, NR.size() + 1); + 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; } @@ -1581,18 +1770,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); } @@ -1600,37 +1794,159 @@ 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. - overflow(this->map->height - 1); - 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); +} + +/// 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::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. -/// @param NodeT The type of node at Level (Leaf or Branch). +/// @tparam NodeT The type of node at Level (Leaf or Branch). /// @param Level path index of the overflowing node. /// @return True when the tree height was changed. template @@ -1638,28 +1954,28 @@ template bool IntervalMap:: iterator::overflow(unsigned Level) { using namespace IntervalMapImpl; + Path &P = this->path; unsigned CurSize[4]; NodeT *Node[4]; unsigned Nodes = 0; unsigned Elements = 0; - unsigned Offset = this->pathOffset(Level); + unsigned Offset = P.offset(Level); // Do we have a left sibling? - NodeRef LeftSib = this->leftSibling(Level); + NodeRef LeftSib = P.getLeftSibling(Level); if (LeftSib) { Offset += Elements = CurSize[Nodes] = LeftSib.size(); Node[Nodes++] = &LeftSib.get(); } // Current node. - NodeRef CurNode = this->pathNode(Level); - Elements += CurSize[Nodes] = CurNode.size(); - Node[Nodes++] = &CurNode.get(); + Elements += CurSize[Nodes] = P.size(Level); + Node[Nodes++] = &P.node(Level); // Do we have a right sibling? - NodeRef RightSib = this->rightSibling(Level); + NodeRef RightSib = P.getRightSibling(Level); if (RightSib) { - Offset += Elements = CurSize[Nodes] = RightSib.size(); + Elements += CurSize[Nodes] = RightSib.size(); Node[Nodes++] = &RightSib.get(); } @@ -1671,7 +1987,7 @@ iterator::overflow(unsigned Level) { CurSize[Nodes] = CurSize[NewNode]; Node[Nodes] = Node[NewNode]; CurSize[NewNode] = 0; - Node[NewNode] = new(this->map->allocator.template Allocate())NodeT(); + Node[NewNode] = this->map->template newNode(); ++Nodes; } @@ -1679,45 +1995,11 @@ iterator::overflow(unsigned Level) { unsigned NewSize[4]; 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; @@ -1728,24 +2010,147 @@ iterator::overflow(unsigned Level) { SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop); Level += SplitRoot; } else { - setNodeSize(Level, NewSize[Pos]); + 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->pathOffset(Level) = 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