X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FIntervalMap.h;h=931b67e40911dd801fa865e4c86c3fd22e41c6a3;hb=c312f098999d4640cf91934632ccecfc9ef30b85;hp=e1438a3b6239f455fab99518f13240d75f48c416;hpb=b0b7214fc90febbbe71e1e989130194ce2b70a36;p=oota-llvm.git diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h index e1438a3b623..931b67e4091 100644 --- a/include/llvm/ADT/IntervalMap.h +++ b/include/llvm/ADT/IntervalMap.h @@ -103,12 +103,8 @@ #include "llvm/ADT/PointerIntPair.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 { @@ -167,7 +163,7 @@ typedef std::pair IdxPair; //===----------------------------------------------------------------------===// -//--- Node Storage ---// +//--- IntervalMapImpl::NodeBase ---// //===----------------------------------------------------------------------===// // // Both leaf and branch nodes store vectors of pairs. @@ -211,8 +207,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 +229,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). @@ -301,7 +301,7 @@ public: } }; -/// adjustSiblingSizes - Move elements between sibling nodes. +/// IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes. /// @param Node Array of pointers to sibling nodes. /// @param Nodes Number of nodes. /// @param CurSize Array of current node sizes, will be overwritten. @@ -348,9 +348,10 @@ void adjustSiblingSizes(NodeT *Node[], unsigned Nodes, #endif } -/// distribute - Compute a new distribution of node elements after an overflow -/// or underflow. Reserve space for a new element at Position, and compute the -/// node that will hold Position after redistributing node elements. +/// IntervalMapImpl::distribute - Compute a new distribution of node elements +/// after an overflow or underflow. Reserve space for a new element at Position, +/// and compute the node that will hold Position after redistributing node +/// elements. /// /// It is required that /// @@ -386,7 +387,7 @@ IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity, //===----------------------------------------------------------------------===// -//--- NodeSizer ---// +//--- IntervalMapImpl::NodeSizer ---// //===----------------------------------------------------------------------===// // // Compute node sizes from key and value types. @@ -442,7 +443,7 @@ struct NodeSizer { //===----------------------------------------------------------------------===// -//--- NodeRef ---// +//--- IntervalMapImpl::NodeRef ---// //===----------------------------------------------------------------------===// // // B+-tree nodes can be leaves or branches, so we need a polymorphic node @@ -462,13 +463,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: @@ -516,7 +516,7 @@ public: }; //===----------------------------------------------------------------------===// -//--- Leaf nodes ---// +//--- IntervalMapImpl::LeafNode ---// //===----------------------------------------------------------------------===// // // Leaf nodes store up to N disjoint intervals with corresponding values. @@ -586,18 +586,7 @@ 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(raw_ostream &OS, unsigned Size) { - OS << " N" << this << " [shape=record label=\"{ " << Size << '/' << N; - for (unsigned i = 0; i != Size; ++i) - OS << " | {" << start(i) << '-' << stop(i) << "|" << value(i) << '}'; - OS << "}\"];\n"; - } -#endif - + unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y); }; /// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as @@ -610,96 +599,63 @@ public: /// @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. @@ -774,29 +730,16 @@ public: subtree(i) = Node; stop(i) = Stop; } - -#ifndef NDEBUG - void dump(raw_ostream &OS, unsigned Size) { - OS << " N" << this << " [shape=record label=\"" << Size << '/' << N; - for (unsigned i = 0; i != Size; ++i) - OS << " | " << stop(i); - OS << "\"];\n"; - for (unsigned i = 0; i != Size; ++i) - OS << " N" << this << ":s" << i << " -> N" - << &subtree(i).template get() << ";\n"; - } -#endif - }; //===----------------------------------------------------------------------===// -//--- Path ---// +//--- IntervalMapImpl::Path ---// //===----------------------------------------------------------------------===// // // A Path is used by iterators to represent a position in a B+-tree, and the // path to get there from the root. // -// The Path class also constains the tree navigation code that doesn't have to +// The Path class also contains the tree navigation code that doesn't have to // be templatized. // //===----------------------------------------------------------------------===// @@ -869,6 +812,11 @@ public: 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. @@ -922,10 +870,18 @@ public: /// @param Level Move node(Level). void moveRight(unsigned Level); - /// atLastBranch - Return true if the path is at the last branch of the node - /// at 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 atLastBranch(unsigned Level) const { + bool atLastEntry(unsigned Level) const { return path[Level].offset == path[Level].size - 1; } @@ -940,14 +896,6 @@ public: moveLeft(Level); ++path[Level].offset; } - -#ifndef NDEBUG - void dump() const { - for (unsigned l = 0, e = path.size(); l != e; ++l) - errs() << l << ": " << path[l].node << ' ' << path[l].size << ' ' - << path[l].offset << '\n'; - } -#endif }; } // namespace IntervalMapImpl @@ -992,6 +940,9 @@ class IntervalMap { 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. @@ -1120,7 +1071,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. @@ -1132,7 +1088,7 @@ public: friend class iterator; const_iterator begin() const { - iterator I(*this); + const_iterator I(*this); I.goToBegin(); return I; } @@ -1144,7 +1100,7 @@ public: } const_iterator end() const { - iterator I(*this); + const_iterator I(*this); I.goToEnd(); return I; } @@ -1158,7 +1114,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; } @@ -1168,12 +1124,6 @@ public: I.find(x); return I; } - -#ifndef NDEBUG - raw_ostream *OS; - void dump(); - void dumpNode(IntervalMapImpl::NodeRef Node, unsigned Height); -#endif }; /// treeSafeLookup - Return the mapped value at x or NotFound, assuming a @@ -1317,34 +1267,8 @@ clear() { rootSize = 0; } -#ifndef NDEBUG -template -void IntervalMap:: -dumpNode(IntervalMapImpl::NodeRef Node, unsigned Height) { - if (Height) - Node.get().dump(*OS, Node.size()); - else - Node.get().dump(*OS, Node.size()); -} - -template -void IntervalMap:: -dump() { - std::string errors; - raw_fd_ostream ofs("tree.dot", errors); - OS = &ofs; - ofs << "digraph {\n"; - if (branched()) - rootBranch().dump(ofs, rootSize); - else - rootLeaf().dump(ofs, rootSize); - visitNodes(&IntervalMap::dumpNode); - ofs << "}\n"; -} -#endif - //===----------------------------------------------------------------------===// -//--- const_iterator ----// +//--- IntervalMap::const_iterator ----// //===----------------------------------------------------------------------===// template @@ -1360,7 +1284,8 @@ protected: // The path may be partially filled, but never between iterator calls. IntervalMapImpl::Path path; - explicit const_iterator(IntervalMap &map) : map(&map) {} + explicit const_iterator(const IntervalMap &map) : + map(const_cast(&map)) {} bool branched() const { assert(map && "Invalid iterator"); @@ -1376,35 +1301,53 @@ protected: void pathFillFind(KeyT x); void treeFind(KeyT x); + void treeAdvanceTo(KeyT x); -public: - /// valid - Return true if the current position is valid, false for end(). - bool valid() const { return path.valid(); } - - /// start - Return the beginning of the current interval. - const KeyT &start() const { + /// unsafeStart - Writable access to start() for iterator. + KeyT &unsafeStart() const { assert(valid() && "Cannot access invalid iterator"); return branched() ? path.leaf().start(path.leafOffset()) : path.leaf().start(path.leafOffset()); } - /// stop - Return the end of the current interval. - const KeyT &stop() const { + /// unsafeStop - Writable access to stop() for iterator. + KeyT &unsafeStop() const { assert(valid() && "Cannot access invalid iterator"); return branched() ? path.leaf().stop(path.leafOffset()) : path.leaf().stop(path.leafOffset()); } - /// value - Return the mapped value at the current interval. - const ValT &value() const { + /// unsafeValue - Writable access to value() for iterator. + ValT &unsafeValue() const { assert(valid() && "Cannot access invalid iterator"); return branched() ? path.leaf().value(path.leafOffset()) : path.leaf().value(path.leafOffset()); } - const ValT &operator*() const { - return value(); - } +public: + /// const_iterator - Create an iterator that isn't pointing anywhere. + const_iterator() : map(0) {} + + /// 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 { return unsafeValue(); } + + const ValT &operator*() const { return value(); } bool operator==(const const_iterator &RHS) const { assert(map == RHS.map && "Cannot compare iterators from different maps"); @@ -1475,6 +1418,8 @@ public: /// 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 @@ -1484,7 +1429,8 @@ public: }; -// 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) { @@ -1497,7 +1443,8 @@ const_iterator::pathFillFind(KeyT x) { path.push(NR, NR.get().safeFind(0, x)); } -// treeFind - Find in a branched tree. +/// treeFind - Find in a branched tree. +/// @param x Key to search for. template void IntervalMap:: const_iterator::treeFind(KeyT x) { @@ -1506,9 +1453,46 @@ const_iterator::treeFind(KeyT x) { pathFillFind(x); } +/// treeAdvanceTo - Find position after the current one. +/// @param x Key to search for. +template +void IntervalMap:: +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; + } + + // Drop the current leaf. + path.pop(); + + // 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 ----// //===----------------------------------------------------------------------===// template @@ -1523,15 +1507,137 @@ class IntervalMap::iterator : public const_iterator { template bool overflow(unsigned Level); void treeInsert(KeyT a, KeyT b, ValT y); void eraseNode(unsigned Level); - void treeErase(); + 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; + } + }; +/// 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 +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:: @@ -1543,13 +1649,61 @@ iterator::setNodeStop(unsigned Level, KeyT Stop) { // Update nodes pointing to the current node. while (--Level) { P.node(Level).stop(P.offset(Level)) = Stop; - if (!P.atLastBranch(Level)) + if (!P.atLastEntry(Level)) return; } // Update root separately since it has a different layout. P.node(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. @@ -1594,7 +1748,7 @@ iterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) { } P.node(Level).insert(P.offset(Level), P.size(Level), Node, Stop); P.setSize(Level, P.size(Level) + 1); - if (P.atLastBranch(Level)) + if (P.atLastEntry(Level)) setNodeStop(Level, Stop); P.reset(Level + 1); return SplitRoot; @@ -1610,12 +1764,11 @@ iterator::insert(KeyT a, KeyT b, ValT y) { IntervalMapImpl::Path &P = this->path; // Try simple root leaf insert. - IdxPair IP = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y); + unsigned Size = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y); // Was the root node insert successful? - if (IP.second <= RootLeaf::Capacity) { - P.leafOffset() = IP.first; - P.setSize(0, IM.rootSize = IP.second); + if (Size <= RootLeaf::Capacity) { + P.setSize(0, IM.rootSize = Size); return; } @@ -1632,14 +1785,15 @@ template void IntervalMap:: iterator::treeInsert(KeyT a, KeyT b, ValT y) { using namespace IntervalMapImpl; - IntervalMap &IM = *this->map; Path &P = this->path; + if (!P.valid()) + P.legalizeForInsert(this->map->height); + // Check if this insertion will extend the node to the left. - if (P.valid() && P.leafOffset() == 0 && - Traits::startLess(a, P.leaf().start(0))) { + 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(IM.height)) { + if (NodeRef Sib = P.getLeftSibling(P.height())) { Leaf &SibLeaf = Sib.get(); unsigned SibOfs = Sib.size() - 1; if (SibLeaf.value(SibOfs) == y && @@ -1650,42 +1804,44 @@ iterator::treeInsert(KeyT a, KeyT b, ValT y) { // 2. Extend a to SibLeaf, erase the SibLeaf entry and continue. // We prefer 1., but need 2 when coalescing to the right as well. Leaf &CurLeaf = P.leaf(); - P.moveLeft(IM.height); + P.moveLeft(P.height()); if (Traits::stopLess(b, CurLeaf.start(0)) && (y != CurLeaf.value(0) || !Traits::adjacent(b, CurLeaf.start(0)))) { // Easy, just extend SibLeaf and we're done. - setNodeStop(IM.height, SibLeaf.stop(SibOfs) = b); + setNodeStop(P.height(), SibLeaf.stop(SibOfs) = b); return; } else { // We have both left and right coalescing. Erase the old SibLeaf entry // and continue inserting the larger interval. a = SibLeaf.start(SibOfs); - erase(); + treeErase(/* UpdateRoot= */false); } } } else { // No left sibling means we are at begin(). Update cached bound. - IM.rootBranchStart() = a; + this->map->rootBranchStart() = a; } } - P.legalizeForInsert(IM.height); - IdxPair IP = P.leaf().insertFrom(P.leafOffset(), P.leafSize(), a, b, y); + // When we are inserting at the end of a leaf node, we must update stops. + unsigned Size = P.leafSize(); + bool Grow = P.leafOffset() == Size; + Size = P.leaf().insertFrom(P.leafOffset(), Size, a, b, y); // Leaf insertion unsuccessful? Overflow and try again. - if (IP.second > Leaf::Capacity) { - overflow(IM.height); - IP = P.leaf().insertFrom(P.leafOffset(), P.leafSize(), a, b, y); - assert(IP.second <= Leaf::Capacity && "overflow() didn't make room"); + 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.leafOffset() = IP.first; - P.setSize(IM.height, IP.second); + P.setSize(P.height(), Size); // Insert was the last node entry, update stops. - if (IP.first == IP.second - 1) - setNodeStop(IM.height, P.leaf().stop(IP.first)); + if (Grow) + setNodeStop(P.height(), b); } /// erase - erase the current interval and move to the next position. @@ -1704,7 +1860,7 @@ iterator::erase() { /// treeErase - erase() for a branched tree. template void IntervalMap:: -iterator::treeErase() { +iterator::treeErase(bool UpdateRoot) { IntervalMap &IM = *this->map; IntervalMapImpl::Path &P = this->path; Leaf &Node = P.leaf(); @@ -1713,6 +1869,9 @@ iterator::treeErase() { 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; } @@ -1724,7 +1883,8 @@ iterator::treeErase() { 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 @@ -1817,7 +1977,7 @@ iterator::overflow(unsigned Level) { CurSize[Nodes] = CurSize[NewNode]; Node[Nodes] = Node[NewNode]; CurSize[NewNode] = 0; - Node[NewNode] = this->map->newNode(); + Node[NewNode] = this->map->template newNode(); ++Nodes; } @@ -1858,6 +2018,129 @@ iterator::overflow(unsigned Level) { 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