//===- llvm/ADT/IntervalMap.h - A sorted interval map -----------*- C++ -*-===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file implements a coalescing interval map for small objects. // // KeyT objects are mapped to ValT objects. Intervals of keys that map to the // same value are represented in a compressed form. // // Iterators provide ordered access to the compressed intervals rather than the // individual keys, and insert and erase operations use key intervals as well. // // Like SmallVector, IntervalMap will store the first N intervals in the map // object itself without any allocations. When space is exhausted it switches to // a B+-tree representation with very small overhead for small key and value // objects. // // A Traits class specifies how keys are compared. It also allows IntervalMap to // work with both closed and half-open intervals. // // Keys and values are not stored next to each other in a std::pair, so we don't // provide such a value_type. Dereferencing iterators only returns the mapped // value. The interval bounds are accessible through the start() and stop() // iterator methods. // // IntervalMap is optimized for small key and value objects, 4 or 8 bytes each // is the optimal size. For large objects use std::map instead. // //===----------------------------------------------------------------------===// // // Synopsis: // // template // class IntervalMap { // public: // typedef KeyT key_type; // typedef ValT mapped_type; // typedef RecyclingAllocator<...> Allocator; // class iterator; // class const_iterator; // // explicit IntervalMap(Allocator&); // ~IntervalMap(): // // bool empty() const; // KeyT start() const; // KeyT stop() const; // ValT lookup(KeyT x, Value NotFound = Value()) const; // // const_iterator begin() const; // const_iterator end() const; // iterator begin(); // iterator end(); // const_iterator find(KeyT x) const; // iterator find(KeyT x); // // void insert(KeyT a, KeyT b, ValT y); // void clear(); // }; // // template // class IntervalMap::const_iterator : // public std::iterator { // public: // bool operator==(const const_iterator &) const; // bool operator!=(const const_iterator &) const; // bool valid() const; // // const KeyT &start() const; // const KeyT &stop() const; // const ValT &value() const; // const ValT &operator*() const; // const ValT *operator->() const; // // const_iterator &operator++(); // const_iterator &operator++(int); // const_iterator &operator--(); // const_iterator &operator--(int); // void goToBegin(); // void goToEnd(); // void find(KeyT x); // void advanceTo(KeyT x); // }; // // template // class IntervalMap::iterator : public const_iterator { // public: // void insert(KeyT a, KeyT b, Value y); // void erase(); // }; // //===----------------------------------------------------------------------===// #ifndef LLVM_ADT_INTERVALMAP_H #define LLVM_ADT_INTERVALMAP_H #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/PointerIntPair.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/RecyclingAllocator.h" #include namespace llvm { //===----------------------------------------------------------------------===// //--- Key traits ---// //===----------------------------------------------------------------------===// // // The IntervalMap works with closed or half-open intervals. // Adjacent intervals that map to the same value are coalesced. // // The IntervalMapInfo traits class is used to determine if a key is contained // in an interval, and if two intervals are adjacent so they can be coalesced. // The provided implementation works for closed integer intervals, other keys // probably need a specialized version. // // The point x is contained in [a;b] when !startLess(x, a) && !stopLess(b, x). // // It is assumed that (a;b] half-open intervals are not used, only [a;b) is // allowed. This is so that stopLess(a, b) can be used to determine if two // intervals overlap. // //===----------------------------------------------------------------------===// template struct IntervalMapInfo { /// startLess - Return true if x is not in [a;b]. /// This is x < a both for closed intervals and for [a;b) half-open intervals. static inline bool startLess(const T &x, const T &a) { return x < a; } /// stopLess - Return true if x is not in [a;b]. /// This is b < x for a closed interval, b <= x for [a;b) half-open intervals. 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. /// This is a+1 == b for closed intervals, a == b for half-open intervals. static inline bool adjacent(const T &a, const T &b) { return a+1 == b; } }; /// IntervalMapImpl - Namespace used for IntervalMap implementation details. /// It should be considered private to the implementation. namespace IntervalMapImpl { // Forward declarations. template class LeafNode; template class BranchNode; typedef std::pair IdxPair; //===----------------------------------------------------------------------===// //--- IntervalMapImpl::NodeBase ---// //===----------------------------------------------------------------------===// // // Both leaf and branch nodes store vectors of pairs. // Leaves store ((KeyT, KeyT), ValT) pairs, branches use (NodeRef, KeyT). // // Keys and values are stored in separate arrays to avoid padding caused by // different object alignments. This also helps improve locality of reference // when searching the keys. // // The nodes don't know how many elements they contain - that information is // stored elsewhere. Omitting the size field prevents padding and allows a node // to fill the allocated cache lines completely. // // These are typical key and value sizes, the node branching factor (N), and // wasted space when nodes are sized to fit in three cache lines (192 bytes): // // T1 T2 N Waste Used by // 4 4 24 0 Branch<4> (32-bit pointers) // 8 4 16 0 Leaf<4,4>, Branch<4> // 8 8 12 0 Leaf<4,8>, Branch<8> // 16 4 9 12 Leaf<8,4> // 16 8 8 0 Leaf<8,8> // //===----------------------------------------------------------------------===// template class NodeBase { public: enum { Capacity = N }; T1 first[N]; T2 second[N]; /// copy - Copy elements from another node. /// @param Other Node elements are copied from. /// @param i Beginning of the source range in other. /// @param j Beginning of the destination range in this. /// @param Count Number of elements to copy. template void copy(const NodeBase &Other, unsigned i, unsigned j, unsigned Count) { assert(i + Count <= M && "Invalid source range"); assert(j + Count <= N && "Invalid dest range"); 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. /// @param i Beginning of the source range. /// @param j Beginning of the destination range. /// @param Count Number of elements to copy. void moveLeft(unsigned i, unsigned j, unsigned Count) { assert(j <= i && "Use moveRight shift elements right"); copy(*this, i, j, Count); } /// moveRight - Move elements to the right. /// @param i Beginning of the source range. /// @param j Beginning of the destination range. /// @param Count Number of elements to copy. void moveRight(unsigned i, unsigned j, unsigned Count) { assert(i <= j && "Use moveLeft shift elements left"); assert(j + Count <= N && "Invalid range"); while (Count--) { first[j + Count] = first[i + Count]; second[j + Count] = second[i + Count]; } } /// erase - Erase elements [i;j). /// @param i Beginning of the range to erase. /// @param j End of the range. (Exclusive). /// @param Size Number of elements in node. void erase(unsigned i, unsigned j, unsigned Size) { 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. void shift(unsigned i, unsigned Size) { moveRight(i, i + 1, Size - i); } /// transferToLeftSib - Transfer elements to a left sibling node. /// @param Size Number of elements in this. /// @param Sib Left sibling node. /// @param SSize Number of elements in sib. /// @param Count Number of elements to transfer. void transferToLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, unsigned Count) { Sib.copy(*this, 0, SSize, Count); erase(0, Count, Size); } /// transferToRightSib - Transfer elements to a right sibling node. /// @param Size Number of elements in this. /// @param Sib Right sibling node. /// @param SSize Number of elements in sib. /// @param Count Number of elements to transfer. void transferToRightSib(unsigned Size, NodeBase &Sib, unsigned SSize, unsigned Count) { Sib.moveRight(0, Count, SSize); Sib.copy(*this, Size-Count, 0, Count); } /// adjustFromLeftSib - Adjust the number if elements in this node by moving /// elements to or from a left sibling node. /// @param Size Number of elements in this. /// @param Sib Right sibling node. /// @param SSize Number of elements in sib. /// @param Add The number of elements to add to this node, possibly < 0. /// @return Number of elements added to this node, possibly negative. int adjustFromLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add) { if (Add > 0) { // We want to grow, copy from sib. unsigned Count = std::min(std::min(unsigned(Add), SSize), N - Size); Sib.transferToRightSib(SSize, *this, Size, Count); return Count; } else { // We want to shrink, copy to sib. unsigned Count = std::min(std::min(unsigned(-Add), Size), N - SSize); transferToLeftSib(Size, Sib, SSize, Count); return -Count; } } }; /// IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes. /// @param Node Array of pointers to sibling nodes. /// @param Nodes Number of nodes. /// @param CurSize Array of current node sizes, will be overwritten. /// @param NewSize Array of desired node sizes. template void adjustSiblingSizes(NodeT *Node[], unsigned Nodes, unsigned CurSize[], const unsigned NewSize[]) { // Move elements right. for (int n = Nodes - 1; n; --n) { if (CurSize[n] == NewSize[n]) continue; for (int m = n - 1; m != -1; --m) { int d = Node[n]->adjustFromLeftSib(CurSize[n], *Node[m], CurSize[m], NewSize[n] - CurSize[n]); CurSize[m] -= d; CurSize[n] += d; // Keep going if the current node was exhausted. if (CurSize[n] >= NewSize[n]) break; } } if (Nodes == 0) return; // Move elements left. for (unsigned n = 0; n != Nodes - 1; ++n) { if (CurSize[n] == NewSize[n]) continue; for (unsigned m = n + 1; m != Nodes; ++m) { int d = Node[m]->adjustFromLeftSib(CurSize[m], *Node[n], CurSize[n], CurSize[n] - NewSize[n]); CurSize[m] += d; CurSize[n] -= d; // Keep going if the current node was exhausted. if (CurSize[n] >= NewSize[n]) break; } } #ifndef NDEBUG for (unsigned n = 0; n != Nodes; n++) assert(CurSize[n] == NewSize[n] && "Insufficient element shuffle"); #endif } /// IntervalMapImpl::distribute - Compute a new distribution of node elements /// after an overflow or underflow. Reserve space for a new element at Position, /// and compute the node that will hold Position after redistributing node /// elements. /// /// It is required that /// /// Elements == sum(CurSize), and /// Elements + Grow <= Nodes * Capacity. /// /// NewSize[] will be filled in such that: /// /// sum(NewSize) == Elements, and /// NewSize[i] <= Capacity. /// /// The returned index is the node where Position will go, so: /// /// sum(NewSize[0..idx-1]) <= Position /// sum(NewSize[0..idx]) >= Position /// /// The last equality, sum(NewSize[0..idx]) == Position, can only happen when /// Grow is set and NewSize[idx] == Capacity-1. The index points to the node /// before the one holding the Position'th element where there is room for an /// insertion. /// /// @param Nodes The number of nodes. /// @param Elements Total elements in all nodes. /// @param Capacity The capacity of each node. /// @param CurSize Array[Nodes] of current node sizes, or NULL. /// @param NewSize Array[Nodes] to receive the new node sizes. /// @param Position Insert position. /// @param Grow Reserve space for a new element at Position. /// @return (node, offset) for Position. IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity, const unsigned *CurSize, unsigned NewSize[], unsigned Position, bool Grow); //===----------------------------------------------------------------------===// //--- IntervalMapImpl::NodeSizer ---// //===----------------------------------------------------------------------===// // // Compute node sizes from key and value types. // // The branching factors are chosen to make nodes fit in three cache lines. // This may not be possible if keys or values are very large. Such large objects // are handled correctly, but a std::map would probably give better performance. // //===----------------------------------------------------------------------===// enum { // Cache line size. Most architectures have 32 or 64 byte cache lines. // We use 64 bytes here because it provides good branching factors. Log2CacheLine = 6, CacheLineBytes = 1 << Log2CacheLine, DesiredNodeBytes = 3 * CacheLineBytes }; template struct NodeSizer { enum { // Compute the leaf node branching factor that makes a node fit in three // cache lines. The branching factor must be at least 3, or some B+-tree // balancing algorithms won't work. // LeafSize can't be larger than CacheLineBytes. This is required by the // PointerIntPair used by NodeRef. DesiredLeafSize = DesiredNodeBytes / static_cast(2*sizeof(KeyT)+sizeof(ValT)), MinLeafSize = 3, LeafSize = DesiredLeafSize > MinLeafSize ? DesiredLeafSize : MinLeafSize }; typedef NodeBase, ValT, LeafSize> LeafBase; enum { // Now that we have the leaf branching factor, compute the actual allocation // unit size by rounding up to a whole number of cache lines. AllocBytes = (sizeof(LeafBase) + CacheLineBytes-1) & ~(CacheLineBytes-1), // Determine the branching factor for branch nodes. BranchSize = AllocBytes / static_cast(sizeof(KeyT) + sizeof(void*)) }; /// Allocator - The recycling allocator used for both branch and leaf nodes. /// This typedef is very likely to be identical for all IntervalMaps with /// reasonably sized entries, so the same allocator can be shared among /// different kinds of maps. typedef RecyclingAllocator Allocator; }; //===----------------------------------------------------------------------===// //--- IntervalMapImpl::NodeRef ---// //===----------------------------------------------------------------------===// // // B+-tree nodes can be leaves or branches, so we need a polymorphic node // pointer that can point to both kinds. // // All nodes are cache line aligned and the low 6 bits of a node pointer are // always 0. These bits are used to store the number of elements in the // referenced node. Besides saving space, placing node sizes in the parents // allow tree balancing algorithms to run without faulting cache lines for nodes // that may not need to be modified. // // A NodeRef doesn't know whether it references a leaf node or a branch node. // It is the responsibility of the caller to use the correct types. // // Nodes are never supposed to be empty, and it is invalid to store a node size // of 0 in a NodeRef. The valid range of sizes is 1-64. // //===----------------------------------------------------------------------===// 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: /// NodeRef - Create a null ref. NodeRef() {} /// operator bool - Detect a null ref. operator bool() const { return pip.getOpaqueValue(); } /// NodeRef - Create a reference to the node p with n elements. template NodeRef(NodeT *p, unsigned n) : pip(p, n - 1) { assert(n <= NodeT::Capacity && "Size too big for node"); } /// size - Return the number of elements in the referenced node. unsigned size() const { return pip.getInt() + 1; } /// setSize - Update the node size. void setSize(unsigned n) { pip.setInt(n - 1); } /// subtree - Access the i'th subtree reference in a branch node. /// This depends on branch nodes storing the NodeRef array as their first /// member. NodeRef &subtree(unsigned i) const { return reinterpret_cast(pip.getPointer())[i]; } /// get - Dereference as a NodeT reference. template NodeT &get() const { return *reinterpret_cast(pip.getPointer()); } bool operator==(const NodeRef &RHS) const { if (pip == RHS.pip) return true; assert(pip.getPointer() != RHS.pip.getPointer() && "Inconsistent NodeRefs"); return false; } bool operator!=(const NodeRef &RHS) const { return !operator==(RHS); } }; //===----------------------------------------------------------------------===// //--- IntervalMapImpl::LeafNode ---// //===----------------------------------------------------------------------===// // // Leaf nodes store up to N disjoint intervals with corresponding values. // // The intervals are kept sorted and fully coalesced so there are no adjacent // intervals mapping to the same value. // // These constraints are always satisfied: // // - Traits::stopLess(start(i), stop(i)) - Non-empty, sane intervals. // // - Traits::stopLess(stop(i), start(i + 1) - Sorted. // // - value(i) != value(i + 1) || !Traits::adjacent(stop(i), start(i + 1)) // - Fully coalesced. // //===----------------------------------------------------------------------===// template class LeafNode : public NodeBase, ValT, N> { public: const KeyT &start(unsigned i) const { return this->first[i].first; } const KeyT &stop(unsigned i) const { return this->first[i].second; } const ValT &value(unsigned i) const { return this->second[i]; } KeyT &start(unsigned i) { return this->first[i].first; } KeyT &stop(unsigned i) { return this->first[i].second; } ValT &value(unsigned i) { return this->second[i]; } /// findFrom - Find the first interval after i that may contain x. /// @param i Starting index for the search. /// @param Size Number of elements in node. /// @param x Key to search for. /// @return First index with !stopLess(key[i].stop, x), or size. /// This is the first interval that can possibly contain x. unsigned findFrom(unsigned i, unsigned Size, KeyT x) const { assert(i <= Size && Size <= N && "Bad indices"); assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && "Index is past the needed point"); while (i != Size && Traits::stopLess(stop(i), x)) ++i; return i; } /// safeFind - Find an interval that is known to exist. This is the same as /// findFrom except is it assumed that x is at least within range of the last /// interval. /// @param i Starting index for the search. /// @param x Key to search for. /// @return First index with !stopLess(key[i].stop, x), never size. /// This is the first interval that can possibly contain x. unsigned safeFind(unsigned i, KeyT x) const { assert(i < N && "Bad index"); assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && "Index is past the needed point"); while (Traits::stopLess(stop(i), x)) ++i; assert(i < N && "Unsafe intervals"); return i; } /// safeLookup - Lookup mapped value for a safe key. /// It is assumed that x is within range of the last entry. /// @param x Key to search for. /// @param NotFound Value to return if x is not in any interval. /// @return The mapped value at x or NotFound. ValT safeLookup(KeyT x, ValT NotFound) const { unsigned i = safeFind(0, x); return Traits::startLess(x, start(i)) ? NotFound : value(i); } unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y); }; /// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as /// possible. This may cause the node to grow by 1, or it may cause the node /// to shrink because of coalescing. /// @param i Starting index = insertFrom(0, size, a) /// @param Size Number of elements in node. /// @param a Interval start. /// @param b Interval stop. /// @param y Value be mapped. /// @return (insert position, new size), or (i, Capacity+1) on overflow. template 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)) { 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 N + 1; // Add new interval at end. if (i == Size) { start(i) = a; stop(i) = b; value(i) = y; return Size + 1; } // Try to coalesce with following interval. if (value(i) == y && Traits::adjacent(b, start(i))) { start(i) = a; return Size; } // We must insert before i. Detect overflow. if (Size == N) return N + 1; // Insert before i. this->shift(i, Size); start(i) = a; stop(i) = b; value(i) = y; return Size + 1; } //===----------------------------------------------------------------------===// //--- IntervalMapImpl::BranchNode ---// //===----------------------------------------------------------------------===// // // A branch node stores references to 1--N subtrees all of the same height. // // The key array in a branch node holds the rightmost stop key of each subtree. // It is redundant to store the last stop key since it can be found in the // parent node, but doing so makes tree balancing a lot simpler. // // It is unusual for a branch node to only have one subtree, but it can happen // in the root node if it is smaller than the normal nodes. // // When all of the leaf nodes from all the subtrees are concatenated, they must // satisfy the same constraints as a single leaf node. They must be sorted, // sane, and fully coalesced. // //===----------------------------------------------------------------------===// template class BranchNode : public NodeBase { public: const KeyT &stop(unsigned i) const { return this->second[i]; } const NodeRef &subtree(unsigned i) const { return this->first[i]; } KeyT &stop(unsigned i) { return this->second[i]; } NodeRef &subtree(unsigned i) { return this->first[i]; } /// findFrom - Find the first subtree after i that may contain x. /// @param i Starting index for the search. /// @param Size Number of elements in node. /// @param x Key to search for. /// @return First index with !stopLess(key[i], x), or size. /// This is the first subtree that can possibly contain x. unsigned findFrom(unsigned i, unsigned Size, KeyT x) const { assert(i <= Size && Size <= N && "Bad indices"); assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && "Index to findFrom is past the needed point"); while (i != Size && Traits::stopLess(stop(i), x)) ++i; return i; } /// safeFind - Find a subtree that is known to exist. This is the same as /// findFrom except is it assumed that x is in range. /// @param i Starting index for the search. /// @param x Key to search for. /// @return First index with !stopLess(key[i], x), never size. /// This is the first subtree that can possibly contain x. unsigned safeFind(unsigned i, KeyT x) const { assert(i < N && "Bad index"); assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && "Index is past the needed point"); while (Traits::stopLess(stop(i), x)) ++i; assert(i < N && "Unsafe intervals"); return i; } /// safeLookup - Get the subtree containing x, Assuming that x is in range. /// @param x Key to search for. /// @return Subtree containing x NodeRef safeLookup(KeyT x) const { return subtree(safeFind(0, x)); } /// insert - Insert a new (subtree, stop) pair. /// @param i Insert position, following entries will be shifted. /// @param Size Number of elements in node. /// @param Node Subtree to insert. /// @param Stop Last key in subtree. void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop) { assert(Size < N && "branch node overflow"); assert(i <= Size && "Bad insert position"); this->shift(i, Size); subtree(i) = Node; stop(i) = Stop; } }; //===----------------------------------------------------------------------===// //--- IntervalMapImpl::Path ---// //===----------------------------------------------------------------------===// // // A Path is used by iterators to represent a position in a B+-tree, and the // path to get there from the root. // // The Path class also constains 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)); } /// 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 //===----------------------------------------------------------------------===// //--- IntervalMap ----// //===----------------------------------------------------------------------===// template ::LeafSize, typename Traits = IntervalMapInfo > class IntervalMap { typedef IntervalMapImpl::NodeSizer Sizer; typedef IntervalMapImpl::LeafNode Leaf; typedef IntervalMapImpl::BranchNode Branch; typedef IntervalMapImpl::LeafNode RootLeaf; typedef IntervalMapImpl::IdxPair IdxPair; // The RootLeaf capacity is given as a template parameter. We must compute the // corresponding RootBranch capacity. enum { DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) / (sizeof(KeyT) + sizeof(IntervalMapImpl::NodeRef)), RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1 }; typedef IntervalMapImpl::BranchNode RootBranch; // When branched, we store a global start key as well as the branch node. struct RootBranchData { KeyT start; 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]; // Tree height. // 0: Leaves in root. // 1: Root points to leaf. // 2: root->branch->leaf ... unsigned height; // Number of entries in the root node. unsigned rootSize; // Allocator used for creating external nodes. Allocator &allocator; /// dataAs - Represent data as a node type without breaking aliasing rules. template T &dataAs() const { union { const char *d; T *t; } u; u.d = data; return *u.t; } const RootLeaf &rootLeaf() const { assert(!branched() && "Cannot acces leaf data in branched root"); return dataAs(); } RootLeaf &rootLeaf() { assert(!branched() && "Cannot acces leaf data in branched root"); return dataAs(); } RootBranchData &rootBranchData() const { assert(branched() && "Cannot access branch data in non-branched root"); return dataAs(); } RootBranchData &rootBranchData() { assert(branched() && "Cannot access branch data in non-branched root"); return dataAs(); } const RootBranch &rootBranch() const { return rootBranchData().node; } RootBranch &rootBranch() { return rootBranchData().node; } KeyT rootBranchStart() const { return rootBranchData().start; } KeyT &rootBranchStart() { return rootBranchData().start; } template NodeT *newNode() { return new(allocator.template Allocate()) NodeT(); } template void deleteNode(NodeT *P) { P->~NodeT(); allocator.Deallocate(P); } IdxPair branchRoot(unsigned Position); IdxPair splitRoot(unsigned Position); void switchRootToBranch() { rootLeaf().~RootLeaf(); height = 1; new (&rootBranchData()) RootBranchData(); } void switchRootToLeaf() { rootBranchData().~RootBranchData(); height = 0; new(&rootLeaf()) RootLeaf(); } bool branched() const { return height > 0; } ValT treeSafeLookup(KeyT x, ValT NotFound) const; void visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, unsigned Level)); void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level); public: explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) { assert((uintptr_t(data) & (alignOf() - 1)) == 0 && "Insufficient alignment"); new(&rootLeaf()) RootLeaf(); } ~IntervalMap() { clear(); rootLeaf().~RootLeaf(); } /// empty - Return true when no intervals are mapped. bool empty() const { return rootSize == 0; } /// start - Return the smallest mapped key in a non-empty map. KeyT start() const { assert(!empty() && "Empty IntervalMap has no start"); return !branched() ? rootLeaf().start(0) : rootBranchStart(); } /// stop - Return the largest mapped key in a non-empty map. KeyT stop() const { assert(!empty() && "Empty IntervalMap has no stop"); return !branched() ? rootLeaf().stop(rootSize - 1) : rootBranch().stop(rootSize - 1); } /// lookup - Return the mapped value at x or NotFound. ValT lookup(KeyT x, ValT NotFound = ValT()) const { if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x)) return NotFound; return branched() ? treeSafeLookup(x, NotFound) : rootLeaf().safeLookup(x, NotFound); } /// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals. /// 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) { if (branched() || rootSize == RootLeaf::Capacity) return find(a).insert(a, b, y); // Easy insert into root leaf. unsigned p = rootLeaf().findFrom(0, rootSize, a); rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y); } /// clear - Remove all entries. void clear(); class const_iterator; class iterator; friend class const_iterator; friend class iterator; const_iterator begin() const { const_iterator I(*this); I.goToBegin(); return I; } iterator begin() { iterator I(*this); I.goToBegin(); return I; } const_iterator end() const { const_iterator I(*this); I.goToEnd(); return I; } iterator end() { iterator I(*this); I.goToEnd(); return I; } /// find - Return an iterator pointing to the first interval ending at or /// after x, or end(). const_iterator find(KeyT x) const { const_iterator I(*this); I.find(x); return I; } iterator find(KeyT x) { iterator I(*this); I.find(x); return I; } }; /// treeSafeLookup - Return the mapped value at x or NotFound, assuming a /// branched root. template ValT IntervalMap:: treeSafeLookup(KeyT x, ValT NotFound) const { assert(branched() && "treeLookup assumes a branched root"); IntervalMapImpl::NodeRef NR = rootBranch().safeLookup(x); for (unsigned h = height-1; h; --h) NR = NR.get().safeLookup(x); return NR.get().safeLookup(x, NotFound); } // branchRoot - Switch from a leaf root to a branched root. // Return the new (root offset, node offset) corresponding to Position. template IntervalMapImpl::IdxPair IntervalMap:: branchRoot(unsigned Position) { using namespace IntervalMapImpl; // How many external leaf nodes to hold RootLeaf+1? const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1; // Compute element distribution among new nodes. unsigned size[Nodes]; IdxPair NewOffset(0, Position); // Is is very common for the root node to be smaller than external nodes. if (Nodes == 1) size[0] = rootSize; else NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, size, Position, true); // Allocate new nodes. unsigned pos = 0; NodeRef node[Nodes]; for (unsigned n = 0; n != Nodes; ++n) { Leaf *L = newNode(); L->copy(rootLeaf(), pos, 0, size[n]); node[n] = NodeRef(L, size[n]); pos += size[n]; } // Destroy the old leaf node, construct branch node instead. switchRootToBranch(); for (unsigned n = 0; n != Nodes; ++n) { rootBranch().stop(n) = node[n].template get().stop(size[n]-1); rootBranch().subtree(n) = node[n]; } rootBranchStart() = node[0].template get().start(0); rootSize = Nodes; return NewOffset; } // splitRoot - Split the current BranchRoot into multiple Branch nodes. // Return the new (root offset, node offset) corresponding to Position. template IntervalMapImpl::IdxPair IntervalMap:: splitRoot(unsigned Position) { using namespace IntervalMapImpl; // How many external leaf nodes to hold RootBranch+1? const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1; // Compute element distribution among new nodes. unsigned Size[Nodes]; IdxPair NewOffset(0, Position); // Is is very common for the root node to be smaller than external nodes. if (Nodes == 1) Size[0] = rootSize; else NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, Size, Position, true); // Allocate new nodes. unsigned Pos = 0; NodeRef Node[Nodes]; for (unsigned n = 0; n != Nodes; ++n) { Branch *B = newNode(); B->copy(rootBranch(), Pos, 0, Size[n]); Node[n] = NodeRef(B, Size[n]); Pos += Size[n]; } for (unsigned n = 0; n != Nodes; ++n) { rootBranch().stop(n) = Node[n].template get().stop(Size[n]-1); rootBranch().subtree(n) = Node[n]; } rootSize = Nodes; ++height; return NewOffset; } /// visitNodes - Visit each external node. template void IntervalMap:: visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, unsigned Height)) { if (!branched()) return; SmallVector Refs, NextRefs; // Collect level 0 nodes from the root. for (unsigned i = 0; i != rootSize; ++i) Refs.push_back(rootBranch().subtree(i)); // Visit all branch nodes. for (unsigned h = height - 1; h; --h) { for (unsigned i = 0, e = Refs.size(); i != e; ++i) { for (unsigned j = 0, s = Refs[i].size(); j != s; ++j) NextRefs.push_back(Refs[i].subtree(j)); (this->*f)(Refs[i], h); } Refs.clear(); Refs.swap(NextRefs); } // Visit all leaf nodes. for (unsigned i = 0, e = Refs.size(); i != e; ++i) (this->*f)(Refs[i], 0); } template void IntervalMap:: deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) { if (Level) deleteNode(&Node.get()); else deleteNode(&Node.get()); } template void IntervalMap:: clear() { if (branched()) { visitNodes(&IntervalMap::deleteNode); switchRootToLeaf(); } rootSize = 0; } //===----------------------------------------------------------------------===// //--- IntervalMap::const_iterator ----// //===----------------------------------------------------------------------===// template class IntervalMap::const_iterator : public std::iterator { protected: friend class IntervalMap; // The map referred to. IntervalMap *map; // We store a full path from the root to the current position. // The path may be partially filled, but never between iterator calls. IntervalMapImpl::Path path; explicit const_iterator(const IntervalMap &map) : map(const_cast(&map)) {} bool branched() const { assert(map && "Invalid iterator"); return map->branched(); } void setRoot(unsigned Offset) { if (branched()) path.setRoot(&map->rootBranch(), map->rootSize, Offset); else path.setRoot(&map->rootLeaf(), map->rootSize, Offset); } void pathFillFind(KeyT x); void treeFind(KeyT x); void treeAdvanceTo(KeyT x); /// 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()); } /// 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()); } /// 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()); } 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(); } /// 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"); 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 { return !operator==(RHS); } /// goToBegin - Move to the first interval in map. void goToBegin() { setRoot(0); if (branched()) path.fillLeft(map->height); } /// goToEnd - Move beyond the last interval in map. void goToEnd() { setRoot(map->rootSize); } /// preincrement - move to the next interval. const_iterator &operator++() { assert(valid() && "Cannot increment end()"); if (++path.leafOffset() == path.leafSize() && branched()) path.moveRight(map->height); return *this; } /// postincrement - Dont do that! const_iterator operator++(int) { const_iterator tmp = *this; operator++(); return tmp; } /// predecrement - move to the previous interval. const_iterator &operator--() { if (path.leafOffset() && (valid() || !branched())) --path.leafOffset(); else path.moveLeft(map->height); return *this; } /// postdecrement - Dont do that! const_iterator operator--(int) { const_iterator tmp = *this; operator--(); return tmp; } /// find - Move to the first interval with stop >= x, or end(). /// This is a full search from the root, the current position is ignored. void find(KeyT x) { if (branched()) treeFind(x); else 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 path.leafOffset() = map->rootLeaf().findFrom(path.leafOffset(), map->rootSize, 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 = path.subtree(path.height()); for (unsigned i = map->height - path.height() - 1; i; --i) { unsigned p = NR.get().safeFind(0, x); path.push(NR, p); NR = NR.subtree(p); } path.push(NR, NR.get().safeFind(0, x)); } /// treeFind - Find in a branched tree. /// @param x Key to search for. template void IntervalMap:: const_iterator::treeFind(KeyT x) { setRoot(map->rootBranch().findFrom(0, map->rootSize, x)); if (valid()) 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); } //===----------------------------------------------------------------------===// //--- IntervalMap::iterator ----// //===----------------------------------------------------------------------===// template class IntervalMap::iterator : public const_iterator { friend class IntervalMap; typedef IntervalMapImpl::IdxPair IdxPair; explicit iterator(IntervalMap &map) : const_iterator(map) {} 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; } }; /// 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:: iterator::setNodeStop(unsigned Level, KeyT Stop) { // 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; } // Update root separately since it has a different layout. P.node(Level).stop(P.offset(Level)) = Stop; } template void IntervalMap:: iterator::setStart(KeyT a) { assert(Traits::stopLess(a, this->stop()) && "Cannot move start beyond stop"); KeyT &CurStart = this->unsafeStart(); if (!Traits::startLess(a, CurStart) || !canCoalesceLeft(a, this->value())) { CurStart = a; return; } // Coalesce with the interval to the left. --*this; a = this->start(); erase(); setStartUnchecked(a); } template void IntervalMap:: iterator::setStop(KeyT b) { assert(Traits::stopLess(this->start(), b) && "Cannot move stop beyond start"); if (Traits::startLess(b, this->stop()) || !canCoalesceRight(b, this->value())) { setStopUnchecked(b); return; } // Coalesce with interval to the right. KeyT a = this->start(); erase(); setStartUnchecked(a); } template void IntervalMap:: iterator::setValue(ValT x) { setValueUnchecked(x); if (canCoalesceRight(this->stop(), x)) { KeyT a = this->start(); erase(); setStartUnchecked(a); } if (canCoalesceLeft(this->start(), x)) { --*this; KeyT a = this->start(); erase(); setStartUnchecked(a); } } /// insertNode - insert a node before the current path at level. /// Leave the current path pointing at the new node. /// @param Level path index of the node to be inserted. /// @param Node The node to be inserted. /// @param Stop The last index in the new node. /// @return True if the tree height was increased. template bool IntervalMap:: iterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) { assert(Level && "Cannot insert next to the root"); bool SplitRoot = false; IntervalMap &IM = *this->map; IntervalMapImpl::Path &P = this->path; if (Level == 1) { // Insert into the root branch node. if (IM.rootSize < RootBranch::Capacity) { 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(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. P.legalizeForInsert(--Level); // Insert into the branch node at Level-1. if (P.size(Level) == Branch::Capacity) { // Branch node is full, handle handle the overflow. assert(!SplitRoot && "Cannot overflow after splitting the root"); SplitRoot = overflow(Level); Level += SplitRoot; } P.node(Level).insert(P.offset(Level), P.size(Level), Node, Stop); P.setSize(Level, P.size(Level) + 1); if (P.atLastEntry(Level)) setNodeStop(Level, Stop); P.reset(Level + 1); return SplitRoot; } // insert template void IntervalMap:: iterator::insert(KeyT a, KeyT b, ValT y) { if (this->branched()) return treeInsert(a, b, y); 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; } // Root leaf node is full, we must branch. IdxPair Offset = IM.branchRoot(P.leafOffset()); P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset); // Now it fits in the new leaf. treeInsert(a, b, y); } template void IntervalMap:: iterator::treeInsert(KeyT a, KeyT b, ValT y) { 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; } // 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). /// @param Level path index of the overflowing node. /// @return True when the tree height was changed. template template bool IntervalMap:: iterator::overflow(unsigned Level) { using namespace IntervalMapImpl; Path &P = this->path; unsigned CurSize[4]; NodeT *Node[4]; unsigned Nodes = 0; unsigned Elements = 0; unsigned Offset = P.offset(Level); // Do we have a left sibling? NodeRef LeftSib = P.getLeftSibling(Level); if (LeftSib) { Offset += Elements = CurSize[Nodes] = LeftSib.size(); Node[Nodes++] = &LeftSib.get(); } // Current node. Elements += CurSize[Nodes] = P.size(Level); Node[Nodes++] = &P.node(Level); // Do we have a right sibling? NodeRef RightSib = P.getRightSibling(Level); if (RightSib) { Elements += CurSize[Nodes] = RightSib.size(); Node[Nodes++] = &RightSib.get(); } // Do we need to allocate a new node? unsigned NewNode = 0; if (Elements + 1 > Nodes * NodeT::Capacity) { // Insert NewNode at the penultimate position, or after a single node. NewNode = Nodes == 1 ? 1 : Nodes - 1; CurSize[Nodes] = CurSize[NewNode]; Node[Nodes] = Node[NewNode]; CurSize[NewNode] = 0; Node[NewNode] = this->map->newNode(); ++Nodes; } // Compute the new element distribution. 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) P.moveLeft(Level); // Elements have been rearranged, now update node sizes and stops. bool SplitRoot = false; unsigned Pos = 0; for (;;) { KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1); if (NewNode && Pos == NewNode) { SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop); Level += SplitRoot; } else { P.setSize(Level, NewSize[Pos]); setNodeStop(Level, Stop); } if (Pos + 1 == Nodes) break; P.moveRight(Level); ++Pos; } // Where was I? Find NewOffset. while(Pos != NewOffset.first) { P.moveLeft(Level); --Pos; } 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