diff options
| -rw-r--r-- | include/llvm/ADT/IntervalMap.h | 1705 | ||||
| -rw-r--r-- | lib/Support/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | lib/Support/IntervalMap.cpp | 60 | ||||
| -rw-r--r-- | unittests/ADT/IntervalMapTest.cpp | 357 | ||||
| -rw-r--r-- | unittests/CMakeLists.txt | 1 |
5 files changed, 2124 insertions, 0 deletions
diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h new file mode 100644 index 0000000000..f54a0abf6c --- /dev/null +++ b/include/llvm/ADT/IntervalMap.h @@ -0,0 +1,1705 @@ +//===- 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 <typename KeyT, typename ValT, unsigned N, typename Traits> +// 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 <typename KeyT, typename ValT, unsigned N, typename Traits> +// class IntervalMap::const_iterator : +// public std::iterator<std::bidirectional_iterator_tag, ValT> { +// 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 <typename KeyT, typename ValT, unsigned N, typename Traits> +// 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 <limits> +#include <iterator> + +// FIXME: Remove debugging code +#ifndef NDEBUG +#include "llvm/Support/raw_ostream.h" +#endif + +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 <typename T> +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 <typename, typename, unsigned, typename> class LeafNode; +template <typename, typename, unsigned, typename> class BranchNode; + +typedef std::pair<unsigned,unsigned> IdxPair; + + +//===----------------------------------------------------------------------===// +//--- Node Storage ---// +//===----------------------------------------------------------------------===// +// +// Both leaf and branch nodes store vectors of (key,value) pairs. +// Leaves store ((KeyT, KeyT), ValT) pairs, branches use (KeyT, NodeRef). +// +// 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): +// +// KT VT N Waste Used by +// 4 4 24 0 Branch<4> (32-bit pointers) +// 4 8 16 0 Branch<4> +// 8 4 16 0 Leaf<4,4> +// 8 8 12 0 Leaf<4,8>, Branch<8> +// 16 4 9 12 Leaf<8,4> +// 16 8 8 0 Leaf<8,8> +// +//===----------------------------------------------------------------------===// + +template <typename KT, typename VT, unsigned N> +class NodeBase { +public: + enum { Capacity = N }; + + KT key[N]; + VT val[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 <unsigned M> + void copy(const NodeBase<KT, VT, M> &Other, unsigned i, + unsigned j, unsigned Count) { + assert(i + Count <= M && "Invalid source range"); + assert(j + Count <= N && "Invalid dest range"); + std::copy(Other.key + i, Other.key + i + Count, key + j); + std::copy(Other.val + i, Other.val + i + Count, val + j); + } + + /// lmove - Move elements to the left. + /// @param i Beginning of the source range. + /// @param j Beginning of the destination range. + /// @param count Number of elements to copy. + void lmove(unsigned i, unsigned j, unsigned Count) { + assert(j <= i && "Use rmove shift elements right"); + copy(*this, i, j, Count); + } + + /// rmove - Move elements to the right. + /// @param i Beginning of the source range. + /// @param j Beginning of the destination range. + /// @param count Number of elements to copy. + void rmove(unsigned i, unsigned j, unsigned Count) { + assert(i <= j && "Use lmove shift elements left"); + assert(j + Count <= N && "Invalid range"); + std::copy_backward(key + i, key + i + Count, key + j + Count); + std::copy_backward(val + i, val + i + Count, val + j + Count); + } + + /// 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) { + lmove(j, i, Size - j); + } + + /// 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) { + rmove(i, i + 1, Size - i); + } + + /// xferLeft - Transfer elements to a left sibling node. + /// @param size Number of elements in this. + /// @param sib Left sibling node. + /// @param ssize Number of elements in sib. + /// @param count Number of elements to transfer. + void xferLeft(unsigned Size, NodeBase &Sib, unsigned SSize, unsigned Count) { + Sib.copy(*this, 0, SSize, Count); + erase(0, Count, Size); + } + + /// xferRight - Transfer elements to a right sibling node. + /// @param size Number of elements in this. + /// @param sib Right sibling node. + /// @param ssize Number of elements in sib. + /// @param count Number of elements to transfer. + void xferRight(unsigned Size, NodeBase &Sib, unsigned SSize, unsigned Count) { + Sib.rmove(0, Count, SSize); + Sib.copy(*this, Size-Count, 0, Count); + } + + /// adjLeftSib - 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 adjLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add) { + if (Add > 0) { + // We want to grow, copy from sib. + unsigned Count = std::min(std::min(unsigned(Add), SSize), N - Size); + Sib.xferRight(SSize, *this, Size, Count); + return Count; + } else { + // We want to shrink, copy to sib. + unsigned Count = std::min(std::min(unsigned(-Add), Size), N - SSize); + xferLeft(Size, Sib, SSize, Count); + return -Count; + } + } +}; + + +//===----------------------------------------------------------------------===// +//--- 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 <typename KeyT, typename ValT> +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<unsigned>(2*sizeof(KeyT)+sizeof(ValT)), + MinLeafSize = 3, + LeafSize = DesiredLeafSize > MinLeafSize ? DesiredLeafSize : MinLeafSize, + + // Now that we have the leaf branching factor, compute the actual allocation + // unit size by rounding up to a whole number of cache lines. + LeafBytes = sizeof(NodeBase<std::pair<KeyT, KeyT>, ValT, LeafSize>), + AllocBytes = (LeafBytes + CacheLineBytes-1) & ~(CacheLineBytes-1), + + // Determine the branching factor for branch nodes. + BranchSize = AllocBytes / + static_cast<unsigned>(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<BumpPtrAllocator, char, + AllocBytes, CacheLineBytes> Allocator; + +}; + + +//===----------------------------------------------------------------------===// +//--- 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. +// +//===----------------------------------------------------------------------===// + +struct CacheAlignedPointerTraits { + static inline void *getAsVoidPointer(void *P) { return P; } + static inline void *getFromVoidPointer(void *P) { return P; } + enum { NumLowBitsAvailable = Log2CacheLine }; +}; + +template <typename KeyT, typename ValT, typename Traits> +class NodeRef { +public: + typedef LeafNode<KeyT, ValT, NodeSizer<KeyT, ValT>::LeafSize, Traits> Leaf; + typedef BranchNode<KeyT, ValT, NodeSizer<KeyT, ValT>::BranchSize, + Traits> Branch; + +private: + PointerIntPair<void*, Log2CacheLine, unsigned, CacheAlignedPointerTraits> 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 leaf node p with n elements. + NodeRef(Leaf *p, unsigned n) : pip(p, n - 1) {} + + /// NodeRef - Create a reference to the branch node p with n elements. + NodeRef(Branch *p, unsigned n) : pip(p, n - 1) {} + + /// size - Return the number of elements in the referenced node. + unsigned size() const { return pip.getInt() + 1; } + + /// setSize - Update the node size. + void setSize(unsigned n) { pip.setInt(n - 1); } + + /// leaf - Return the referenced leaf node. + /// Note there are no dynamic type checks. + Leaf &leaf() const { + return *reinterpret_cast<Leaf*>(pip.getPointer()); + } + + /// branch - Return the referenced branch node. + /// Note there are no dynamic type checks. + Branch &branch() const { + return *reinterpret_cast<Branch*>(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); + } +}; + +//===----------------------------------------------------------------------===// +//--- Leaf nodes ---// +//===----------------------------------------------------------------------===// +// +// 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(key[i].start, key[i].stop) - Non-empty, sane intervals. +// +// - Traits::stopLess(key[i].stop, key[i + 1].start) - Sorted. +// +// - val[i] != val[i + 1] || +// !Traits::adjacent(key[i].stop, key[i + 1].start) - Fully coalesced. +// +//===----------------------------------------------------------------------===// + +template <typename KeyT, typename ValT, unsigned N, typename Traits> +class LeafNode : public NodeBase<std::pair<KeyT, KeyT>, ValT, N> { +public: + const KeyT &start(unsigned i) const { return this->key[i].first; } + const KeyT &stop(unsigned i) const { return this->key[i].second; } + const ValT &value(unsigned i) const { return this->val[i]; } + + KeyT &start(unsigned i) { return this->key[i].first; } + KeyT &stop(unsigned i) { return this->key[i].second; } + ValT &value(unsigned i) { return this->val[i]; } + + /// 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); + } + + IdxPair insertFrom(unsigned i, unsigned Size, KeyT a, KeyT b, ValT y); + unsigned extendStop(unsigned i, unsigned Size, KeyT b); + +#ifndef NDEBUG + void dump(unsigned Size) { + errs() << " N" << this << " [shape=record label=\"{ " << Size << '/' << N; + for (unsigned i = 0; i != Size; ++i) + errs() << " | {" << start(i) << '-' << stop(i) << "|" << value(i) << '}'; + errs() << "}\"];\n"; + } +#endif + +}; + +/// 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 <typename KeyT, typename ValT, unsigned N, typename Traits> +IdxPair LeafNode<KeyT, ValT, N, Traits>:: +insertFrom(unsigned i, unsigned Size, KeyT a, KeyT b, ValT y) { + 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))); + + // 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)); + + // Detect overflow. + if (i == N) + return IdxPair(i, 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)); + } + + // Try to coalesce with following interval. + if (value(i) == y && Traits::adjacent(b, start(i))) { + start(i) = a; + return IdxPair(i, Size); + } + + // We must insert before i. Detect overflow. + if (Size == N) + return IdxPair(i, N + 1); + + // Insert before i. + this->shift(i, Size); + start(i) = a; + stop(i) = b; + value(i) = y; + return IdxPair(i, Size + 1); +} + +/// extendStop - Extend stop(i) to b, coalescing with following intervals. +/// @param i Interval to extend. +/// @param size Number of elements in node. +/// @param b New interval end point. +/// @return New node size after coalescing. +template <typename KeyT, typename ValT, unsigned N, typename Traits> +unsigned LeafNode<KeyT, ValT, N, Traits>:: +extendStop(unsigned i, unsigned Size, KeyT b) { + assert(i < Size && Size <= N && "Bad indices"); + + // Are we even extending the interval? + if (Traits::startLess(b, stop(i))) + return Size; + + // Find the first interval that may be preserved. + unsigned j = findFrom(i + 1, Size, b); + if (j < Size) { + // Would key[i] overlap key[j] after the extension? + if (Traits::stopLess(b, start(j))) { + // Not overlapping. Perhaps adjacent and coalescable? + if (value(i) == value(j) && Traits::adjacent(b, start(j))) + b = stop(j++); + } else { + // Overlap. Include key[j] in the new interval. + assert(value(i) == value(j) && "Overlapping values"); + b = stop(j++); + } + } + stop(i) = b; + + // Entries [i+1;j) were coalesced. + if (i + 1 < j && j < Size) + this->erase(i + 1, j, Size); + return Size - (j - (i + 1)); +} + + +//===----------------------------------------------------------------------===// +//--- Branch nodes ---// +//===----------------------------------------------------------------------===// +// +// 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 <typename KeyT, typename ValT, unsigned N, typename Traits> +class BranchNode : public NodeBase<KeyT, NodeRef<KeyT, ValT, Traits>, N> { + typedef NodeRef<KeyT, ValT, Traits> NodeRefT; +public: + const KeyT &stop(unsigned i) const { return this->key[i]; } + const NodeRefT &subtree(unsigned i) const { return this->val[i]; } + + KeyT &stop(unsigned i) { return this->key[i]; } + NodeRefT &subtree(unsigned i) { return this->val[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 + NodeRefT safeLookup(KeyT x) const { + return subtree(safeFind(0, x)); + } + + /// insert - Insert a new (subtree, stop) pair. + /// @param i Insert position, following entries will be shifted. + /// @param size Number of elements in node. + /// @param node Subtree to insert. + /// @param stp Last key in subtree. + void insert(unsigned i, unsigned Size, NodeRefT Node, KeyT Stop) { + assert(Size < N && "branch node overflow"); + assert(i <= Size && "Bad insert position"); + this->shift(i, Size); + subtree(i) = Node; + stop(i) = Stop; + } + +#ifndef NDEBUG + void dump(unsigned Size) { + errs() << " N" << this << " [shape=record label=\"" << Size << '/' << N; + for (unsigned i = 0; i != Size; ++i) + errs() << " | <s" << i << "> " << stop(i); + errs() << "\"];\n"; + for (unsigned i = 0; i != Size; ++i) + errs() << " N" << this << ":s" << i << " -> N" + << &subtree(i).branch() << ";\n"; + } +#endif + +}; + +} // namespace IntervalMapImpl + + +//===----------------------------------------------------------------------===// +//--- IntervalMap ----// +//===----------------------------------------------------------------------===// + +template <typename KeyT, typename ValT, + unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize, + typename Traits = IntervalMapInfo<KeyT> > +class IntervalMap { + typedef IntervalMapImpl::NodeRef<KeyT, ValT, Traits> NodeRef; + typedef IntervalMapImpl::NodeSizer<KeyT, ValT> NodeSizer; + typedef typename NodeRef::Leaf Leaf; + typedef typename NodeRef::Branch Branch; + typedef IntervalMapImpl::LeafNode<KeyT, ValT, N, Traits> 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(NodeRef)), + RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1 + }; + + typedef IntervalMapImpl::BranchNode<KeyT, ValT, RootBranchCap, Traits> 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 NodeSizer::Allocator Allocator; + +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 <typename T> + 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 &rootLeaf() { + assert(!branched() && "Cannot acces leaf data in branched root"); + return dataAs<RootLeaf>(); + } + RootBranchData &rootBranchData() const { + assert(branched() && "Cannot access branch data in non-branched root"); + return dataAs<RootBranchData>(); + } + RootBranchData &rootBranchData() { + assert(branched() && "Cannot access branch data in non-branched root"); + return dataAs<RootBranchData>(); + } + const RootBranch &rootBranch() const { return rootBranchData().node; } + RootBranch &rootBranch() { return rootBranchData().node; } + KeyT rootBranchStart() const { return rootBranchData().start; } + KeyT &rootBranchStart() { return rootBranchData().start; } + + Leaf *allocLeaf() { + return new(allocator.template Allocate<Leaf>()) Leaf(); + } + void freeLeaf(Leaf *P) { + P->~Leaf(); + allocator.Deallocate(P); + } + + Branch *allocBranch() { + return new(allocator.template Allocate<Branch>()) Branch(); + } + void freeBranch(Branch *P) { + P->~Branch(); + 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)(NodeRef, unsigned Level)); + +public: + explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) { + assert((uintptr_t(data) & (alignOf<RootLeaf>() - 1)) == 0 && + "Insufficient alignment"); + new(&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) { + find(a).insert(a, b, y); + } + + class const_iterator; + class iterator; + friend class const_iterator; + friend class iterator; + + const_iterator begin() const { + iterator I(*this); + I.goToBegin(); + return I; + } + + iterator begin() { + iterator I(*this); + I.goToBegin(); + return I; + } + + const_iterator end() 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 { + iterator I(*this); + I.find(x); + return I; + } + + iterator find(KeyT x) { + iterator I(*this); + I.find(x); + return I; + } + +#ifndef NDEBUG + void dump(); + void dumpNode(NodeRef Node, unsigned Height); +#endif +}; + +/// treeSafeLookup - Return the mapped value at x or NotFound, assuming a +/// branched root. +template <typename KeyT, typename ValT, unsigned N, typename Traits> +ValT IntervalMap<KeyT, ValT, N, Traits>:: +treeSafeLookup(KeyT x, ValT NotFound) const { + assert(branched() && "treeLookup assumes a branched root"); + + NodeRef NR = rootBranch().safeLookup(x); + for (unsigned h = height-1; h; --h) + NR = NR.branch().safeLookup(x); + return NR.leaf().safeLookup(x, NotFound); +} + + +// branchRoot - Switch from a leaf root to a branched root. +// Return the new (root offset, node offset) corresponding to Position. +template <typename KeyT, typename ValT, unsigned N, typename Traits> +IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>:: +branchRoot(unsigned Position) { + // 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. |