1 //===- llvm/ADT/IntervalMap.h - A sorted interval map -----------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a coalescing interval map for small objects.
12 // KeyT objects are mapped to ValT objects. Intervals of keys that map to the
13 // same value are represented in a compressed form.
15 // Iterators provide ordered access to the compressed intervals rather than the
16 // individual keys, and insert and erase operations use key intervals as well.
18 // Like SmallVector, IntervalMap will store the first N intervals in the map
19 // object itself without any allocations. When space is exhausted it switches to
20 // a B+-tree representation with very small overhead for small key and value
23 // A Traits class specifies how keys are compared. It also allows IntervalMap to
24 // work with both closed and half-open intervals.
26 // Keys and values are not stored next to each other in a std::pair, so we don't
27 // provide such a value_type. Dereferencing iterators only returns the mapped
28 // value. The interval bounds are accessible through the start() and stop()
31 // IntervalMap is optimized for small key and value objects, 4 or 8 bytes each
32 // is the optimal size. For large objects use std::map instead.
34 //===----------------------------------------------------------------------===//
38 // template <typename KeyT, typename ValT, unsigned N, typename Traits>
39 // class IntervalMap {
41 // typedef KeyT key_type;
42 // typedef ValT mapped_type;
43 // typedef RecyclingAllocator<...> Allocator;
45 // class const_iterator;
47 // explicit IntervalMap(Allocator&);
50 // bool empty() const;
51 // KeyT start() const;
53 // ValT lookup(KeyT x, Value NotFound = Value()) const;
55 // const_iterator begin() const;
56 // const_iterator end() const;
59 // const_iterator find(KeyT x) const;
60 // iterator find(KeyT x);
62 // void insert(KeyT a, KeyT b, ValT y);
66 // template <typename KeyT, typename ValT, unsigned N, typename Traits>
67 // class IntervalMap::const_iterator :
68 // public std::iterator<std::bidirectional_iterator_tag, ValT> {
70 // bool operator==(const const_iterator &) const;
71 // bool operator!=(const const_iterator &) const;
72 // bool valid() const;
74 // const KeyT &start() const;
75 // const KeyT &stop() const;
76 // const ValT &value() const;
77 // const ValT &operator*() const;
78 // const ValT *operator->() const;
80 // const_iterator &operator++();
81 // const_iterator &operator++(int);
82 // const_iterator &operator--();
83 // const_iterator &operator--(int);
87 // void advanceTo(KeyT x);
90 // template <typename KeyT, typename ValT, unsigned N, typename Traits>
91 // class IntervalMap::iterator : public const_iterator {
93 // void insert(KeyT a, KeyT b, Value y);
97 //===----------------------------------------------------------------------===//
99 #ifndef LLVM_ADT_INTERVALMAP_H
100 #define LLVM_ADT_INTERVALMAP_H
102 #include "llvm/ADT/SmallVector.h"
103 #include "llvm/ADT/PointerIntPair.h"
104 #include "llvm/Support/Allocator.h"
105 #include "llvm/Support/RecyclingAllocator.h"
109 // FIXME: Remove debugging code.
110 #include "llvm/Support/raw_ostream.h"
115 //===----------------------------------------------------------------------===//
116 //--- Key traits ---//
117 //===----------------------------------------------------------------------===//
119 // The IntervalMap works with closed or half-open intervals.
120 // Adjacent intervals that map to the same value are coalesced.
122 // The IntervalMapInfo traits class is used to determine if a key is contained
123 // in an interval, and if two intervals are adjacent so they can be coalesced.
124 // The provided implementation works for closed integer intervals, other keys
125 // probably need a specialized version.
127 // The point x is contained in [a;b] when !startLess(x, a) && !stopLess(b, x).
129 // It is assumed that (a;b] half-open intervals are not used, only [a;b) is
130 // allowed. This is so that stopLess(a, b) can be used to determine if two
131 // intervals overlap.
133 //===----------------------------------------------------------------------===//
135 template <typename T>
136 struct IntervalMapInfo {
138 /// startLess - Return true if x is not in [a;b].
139 /// This is x < a both for closed intervals and for [a;b) half-open intervals.
140 static inline bool startLess(const T &x, const T &a) {
144 /// stopLess - Return true if x is not in [a;b].
145 /// This is b < x for a closed interval, b <= x for [a;b) half-open intervals.
146 static inline bool stopLess(const T &b, const T &x) {
150 /// adjacent - Return true when the intervals [x;a] and [b;y] can coalesce.
151 /// This is a+1 == b for closed intervals, a == b for half-open intervals.
152 static inline bool adjacent(const T &a, const T &b) {
158 /// IntervalMapImpl - Namespace used for IntervalMap implementation details.
159 /// It should be considered private to the implementation.
160 namespace IntervalMapImpl {
162 // Forward declarations.
163 template <typename, typename, unsigned, typename> class LeafNode;
164 template <typename, typename, unsigned, typename> class BranchNode;
166 typedef std::pair<unsigned,unsigned> IdxPair;
169 //===----------------------------------------------------------------------===//
170 //--- Node Storage ---//
171 //===----------------------------------------------------------------------===//
173 // Both leaf and branch nodes store vectors of pairs.
174 // Leaves store ((KeyT, KeyT), ValT) pairs, branches use (NodeRef, KeyT).
176 // Keys and values are stored in separate arrays to avoid padding caused by
177 // different object alignments. This also helps improve locality of reference
178 // when searching the keys.
180 // The nodes don't know how many elements they contain - that information is
181 // stored elsewhere. Omitting the size field prevents padding and allows a node
182 // to fill the allocated cache lines completely.
184 // These are typical key and value sizes, the node branching factor (N), and
185 // wasted space when nodes are sized to fit in three cache lines (192 bytes):
187 // T1 T2 N Waste Used by
188 // 4 4 24 0 Branch<4> (32-bit pointers)
189 // 8 4 16 0 Leaf<4,4>, Branch<4>
190 // 8 8 12 0 Leaf<4,8>, Branch<8>
191 // 16 4 9 12 Leaf<8,4>
192 // 16 8 8 0 Leaf<8,8>
194 //===----------------------------------------------------------------------===//
196 template <typename T1, typename T2, unsigned N>
199 enum { Capacity = N };
204 /// copy - Copy elements from another node.
205 /// @param Other Node elements are copied from.
206 /// @param i Beginning of the source range in other.
207 /// @param j Beginning of the destination range in this.
208 /// @param Count Number of elements to copy.
209 template <unsigned M>
210 void copy(const NodeBase<T1, T2, M> &Other, unsigned i,
211 unsigned j, unsigned Count) {
212 assert(i + Count <= M && "Invalid source range");
213 assert(j + Count <= N && "Invalid dest range");
214 std::copy(Other.first + i, Other.first + i + Count, first + j);
215 std::copy(Other.second + i, Other.second + i + Count, second + j);
218 /// moveLeft - Move elements to the left.
219 /// @param i Beginning of the source range.
220 /// @param j Beginning of the destination range.
221 /// @param Count Number of elements to copy.
222 void moveLeft(unsigned i, unsigned j, unsigned Count) {
223 assert(j <= i && "Use moveRight shift elements right");
224 copy(*this, i, j, Count);
227 /// moveRight - Move elements to the right.
228 /// @param i Beginning of the source range.
229 /// @param j Beginning of the destination range.
230 /// @param Count Number of elements to copy.
231 void moveRight(unsigned i, unsigned j, unsigned Count) {
232 assert(i <= j && "Use moveLeft shift elements left");
233 assert(j + Count <= N && "Invalid range");
234 std::copy_backward(first + i, first + i + Count, first + j + Count);
235 std::copy_backward(second + i, second + i + Count, second + j + Count);
238 /// erase - Erase elements [i;j).
239 /// @param i Beginning of the range to erase.
240 /// @param j End of the range. (Exclusive).
241 /// @param Size Number of elements in node.
242 void erase(unsigned i, unsigned j, unsigned Size) {
243 moveLeft(j, i, Size - j);
246 /// shift - Shift elements [i;size) 1 position to the right.
247 /// @param i Beginning of the range to move.
248 /// @param Size Number of elements in node.
249 void shift(unsigned i, unsigned Size) {
250 moveRight(i, i + 1, Size - i);
253 /// transferToLeftSib - Transfer elements to a left sibling node.
254 /// @param Size Number of elements in this.
255 /// @param Sib Left sibling node.
256 /// @param SSize Number of elements in sib.
257 /// @param Count Number of elements to transfer.
258 void transferToLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize,
260 Sib.copy(*this, 0, SSize, Count);
261 erase(0, Count, Size);
264 /// transferToRightSib - Transfer elements to a right sibling node.
265 /// @param Size Number of elements in this.
266 /// @param Sib Right sibling node.
267 /// @param SSize Number of elements in sib.
268 /// @param Count Number of elements to transfer.
269 void transferToRightSib(unsigned Size, NodeBase &Sib, unsigned SSize,
271 Sib.moveRight(0, Count, SSize);
272 Sib.copy(*this, Size-Count, 0, Count);
275 /// adjustFromLeftSib - Adjust the number if elements in this node by moving
276 /// elements to or from a left sibling node.
277 /// @param Size Number of elements in this.
278 /// @param Sib Right sibling node.
279 /// @param SSize Number of elements in sib.
280 /// @param Add The number of elements to add to this node, possibly < 0.
281 /// @return Number of elements added to this node, possibly negative.
282 int adjustFromLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add) {
284 // We want to grow, copy from sib.
285 unsigned Count = std::min(std::min(unsigned(Add), SSize), N - Size);
286 Sib.transferToRightSib(SSize, *this, Size, Count);
289 // We want to shrink, copy to sib.
290 unsigned Count = std::min(std::min(unsigned(-Add), Size), N - SSize);
291 transferToLeftSib(Size, Sib, SSize, Count);
298 //===----------------------------------------------------------------------===//
299 //--- NodeSizer ---//
300 //===----------------------------------------------------------------------===//
302 // Compute node sizes from key and value types.
304 // The branching factors are chosen to make nodes fit in three cache lines.
305 // This may not be possible if keys or values are very large. Such large objects
306 // are handled correctly, but a std::map would probably give better performance.
308 //===----------------------------------------------------------------------===//
311 // Cache line size. Most architectures have 32 or 64 byte cache lines.
312 // We use 64 bytes here because it provides good branching factors.
314 CacheLineBytes = 1 << Log2CacheLine,
315 DesiredNodeBytes = 3 * CacheLineBytes
318 template <typename KeyT, typename ValT>
321 // Compute the leaf node branching factor that makes a node fit in three
322 // cache lines. The branching factor must be at least 3, or some B+-tree
323 // balancing algorithms won't work.
324 // LeafSize can't be larger than CacheLineBytes. This is required by the
325 // PointerIntPair used by NodeRef.
326 DesiredLeafSize = DesiredNodeBytes /
327 static_cast<unsigned>(2*sizeof(KeyT)+sizeof(ValT)),
329 LeafSize = DesiredLeafSize > MinLeafSize ? DesiredLeafSize : MinLeafSize
332 typedef NodeBase<std::pair<KeyT, KeyT>, ValT, LeafSize> LeafBase;
335 // Now that we have the leaf branching factor, compute the actual allocation
336 // unit size by rounding up to a whole number of cache lines.
337 AllocBytes = (sizeof(LeafBase) + CacheLineBytes-1) & ~(CacheLineBytes-1),
339 // Determine the branching factor for branch nodes.
340 BranchSize = AllocBytes /
341 static_cast<unsigned>(sizeof(KeyT) + sizeof(void*))
344 /// Allocator - The recycling allocator used for both branch and leaf nodes.
345 /// This typedef is very likely to be identical for all IntervalMaps with
346 /// reasonably sized entries, so the same allocator can be shared among
347 /// different kinds of maps.
348 typedef RecyclingAllocator<BumpPtrAllocator, char,
349 AllocBytes, CacheLineBytes> Allocator;
354 //===----------------------------------------------------------------------===//
356 //===----------------------------------------------------------------------===//
358 // B+-tree nodes can be leaves or branches, so we need a polymorphic node
359 // pointer that can point to both kinds.
361 // All nodes are cache line aligned and the low 6 bits of a node pointer are
362 // always 0. These bits are used to store the number of elements in the
363 // referenced node. Besides saving space, placing node sizes in the parents
364 // allow tree balancing algorithms to run without faulting cache lines for nodes
365 // that may not need to be modified.
367 // A NodeRef doesn't know whether it references a leaf node or a branch node.
368 // It is the responsibility of the caller to use the correct types.
370 // Nodes are never supposed to be empty, and it is invalid to store a node size
371 // of 0 in a NodeRef. The valid range of sizes is 1-64.
373 //===----------------------------------------------------------------------===//
375 struct CacheAlignedPointerTraits {
376 static inline void *getAsVoidPointer(void *P) { return P; }
377 static inline void *getFromVoidPointer(void *P) { return P; }
378 enum { NumLowBitsAvailable = Log2CacheLine };
382 PointerIntPair<void*, Log2CacheLine, unsigned, CacheAlignedPointerTraits> pip;
385 /// NodeRef - Create a null ref.
388 /// operator bool - Detect a null ref.
389 operator bool() const { return pip.getOpaqueValue(); }
391 /// NodeRef - Create a reference to the node p with n elements.
392 template <typename NodeT>
393 NodeRef(NodeT *p, unsigned n) : pip(p, n - 1) {
394 assert(n <= NodeT::Capacity && "Size too big for node");
397 /// size - Return the number of elements in the referenced node.
398 unsigned size() const { return pip.getInt() + 1; }
400 /// setSize - Update the node size.
401 void setSize(unsigned n) { pip.setInt(n - 1); }
403 /// subtree - Access the i'th subtree reference in a branch node.
404 /// This depends on branch nodes storing the NodeRef array as their first
406 NodeRef &subtree(unsigned i) {
407 return reinterpret_cast<NodeRef*>(pip.getPointer())[i];
410 /// get - Dereference as a NodeT reference.
411 template <typename NodeT>
413 return *reinterpret_cast<NodeT*>(pip.getPointer());
416 bool operator==(const NodeRef &RHS) const {
419 assert(pip.getPointer() != RHS.pip.getPointer() && "Inconsistent NodeRefs");
423 bool operator!=(const NodeRef &RHS) const {
424 return !operator==(RHS);
428 //===----------------------------------------------------------------------===//
429 //--- Leaf nodes ---//
430 //===----------------------------------------------------------------------===//
432 // Leaf nodes store up to N disjoint intervals with corresponding values.
434 // The intervals are kept sorted and fully coalesced so there are no adjacent
435 // intervals mapping to the same value.
437 // These constraints are always satisfied:
439 // - Traits::stopLess(start(i), stop(i)) - Non-empty, sane intervals.
441 // - Traits::stopLess(stop(i), start(i + 1) - Sorted.
443 // - value(i) != value(i + 1) || !Traits::adjacent(stop(i), start(i + 1))
444 // - Fully coalesced.
446 //===----------------------------------------------------------------------===//
448 template <typename KeyT, typename ValT, unsigned N, typename Traits>
449 class LeafNode : public NodeBase<std::pair<KeyT, KeyT>, ValT, N> {
451 const KeyT &start(unsigned i) const { return this->first[i].first; }
452 const KeyT &stop(unsigned i) const { return this->first[i].second; }
453 const ValT &value(unsigned i) const { return this->second[i]; }
455 KeyT &start(unsigned i) { return this->first[i].first; }
456 KeyT &stop(unsigned i) { return this->first[i].second; }
457 ValT &value(unsigned i) { return this->second[i]; }
459 /// findFrom - Find the first interval after i that may contain x.
460 /// @param i Starting index for the search.
461 /// @param Size Number of elements in node.
462 /// @param x Key to search for.
463 /// @return First index with !stopLess(key[i].stop, x), or size.
464 /// This is the first interval that can possibly contain x.
465 unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
466 assert(i <= Size && Size <= N && "Bad indices");
467 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
468 "Index is past the needed point");
469 while (i != Size && Traits::stopLess(stop(i), x)) ++i;
473 /// safeFind - Find an interval that is known to exist. This is the same as
474 /// findFrom except is it assumed that x is at least within range of the last
476 /// @param i Starting index for the search.
477 /// @param x Key to search for.
478 /// @return First index with !stopLess(key[i].stop, x), never size.
479 /// This is the first interval that can possibly contain x.
480 unsigned safeFind(unsigned i, KeyT x) const {
481 assert(i < N && "Bad index");
482 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
483 "Index is past the needed point");
484 while (Traits::stopLess(stop(i), x)) ++i;
485 assert(i < N && "Unsafe intervals");
489 /// safeLookup - Lookup mapped value for a safe key.
490 /// It is assumed that x is within range of the last entry.
491 /// @param x Key to search for.
492 /// @param NotFound Value to return if x is not in any interval.
493 /// @return The mapped value at x or NotFound.
494 ValT safeLookup(KeyT x, ValT NotFound) const {
495 unsigned i = safeFind(0, x);
496 return Traits::startLess(x, start(i)) ? NotFound : value(i);
499 IdxPair insertFrom(unsigned i, unsigned Size, KeyT a, KeyT b, ValT y);
500 unsigned extendStop(unsigned i, unsigned Size, KeyT b);
503 void dump(unsigned Size) {
504 errs() << " N" << this << " [shape=record label=\"{ " << Size << '/' << N;
505 for (unsigned i = 0; i != Size; ++i)
506 errs() << " | {" << start(i) << '-' << stop(i) << "|" << value(i) << '}';
513 /// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as
514 /// possible. This may cause the node to grow by 1, or it may cause the node
515 /// to shrink because of coalescing.
516 /// @param i Starting index = insertFrom(0, size, a)
517 /// @param Size Number of elements in node.
518 /// @param a Interval start.
519 /// @param b Interval stop.
520 /// @param y Value be mapped.
521 /// @return (insert position, new size), or (i, Capacity+1) on overflow.
522 template <typename KeyT, typename ValT, unsigned N, typename Traits>
523 IdxPair LeafNode<KeyT, ValT, N, Traits>::
524 insertFrom(unsigned i, unsigned Size, KeyT a, KeyT b, ValT y) {
525 assert(i <= Size && Size <= N && "Invalid index");
526 assert(!Traits::stopLess(b, a) && "Invalid interval");
528 // Verify the findFrom invariant.
529 assert((i == 0 || Traits::stopLess(stop(i - 1), a)));
530 assert((i == Size || !Traits::stopLess(stop(i), a)));
532 // Coalesce with previous interval.
533 if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a))
534 return IdxPair(i - 1, extendStop(i - 1, Size, b));
538 return IdxPair(i, N + 1);
540 // Add new interval at end.
545 return IdxPair(i, Size + 1);
548 // Overlapping intervals?
549 if (!Traits::stopLess(b, start(i))) {
550 assert(value(i) == y && "Inconsistent values in overlapping intervals");
551 if (Traits::startLess(a, start(i)))
553 return IdxPair(i, extendStop(i, Size, b));
556 // Try to coalesce with following interval.
557 if (value(i) == y && Traits::adjacent(b, start(i))) {
559 return IdxPair(i, Size);
562 // We must insert before i. Detect overflow.
564 return IdxPair(i, N + 1);
567 this->shift(i, Size);
571 return IdxPair(i, Size + 1);
574 /// extendStop - Extend stop(i) to b, coalescing with following intervals.
575 /// @param i Interval to extend.
576 /// @param Size Number of elements in node.
577 /// @param b New interval end point.
578 /// @return New node size after coalescing.
579 template <typename KeyT, typename ValT, unsigned N, typename Traits>
580 unsigned LeafNode<KeyT, ValT, N, Traits>::
581 extendStop(unsigned i, unsigned Size, KeyT b) {
582 assert(i < Size && Size <= N && "Bad indices");
584 // Are we even extending the interval?
585 if (Traits::startLess(b, stop(i)))
588 // Find the first interval that may be preserved.
589 unsigned j = findFrom(i + 1, Size, b);
591 // Would key[i] overlap key[j] after the extension?
592 if (Traits::stopLess(b, start(j))) {
593 // Not overlapping. Perhaps adjacent and coalescable?
594 if (value(i) == value(j) && Traits::adjacent(b, start(j)))
597 // Overlap. Include key[j] in the new interval.
598 assert(value(i) == value(j) && "Overlapping values");
604 // Entries [i+1;j) were coalesced.
605 if (i + 1 < j && j < Size)
606 this->erase(i + 1, j, Size);
607 return Size - (j - (i + 1));
611 //===----------------------------------------------------------------------===//
612 //--- Branch nodes ---//
613 //===----------------------------------------------------------------------===//
615 // A branch node stores references to 1--N subtrees all of the same height.
617 // The key array in a branch node holds the rightmost stop key of each subtree.
618 // It is redundant to store the last stop key since it can be found in the
619 // parent node, but doing so makes tree balancing a lot simpler.
621 // It is unusual for a branch node to only have one subtree, but it can happen
622 // in the root node if it is smaller than the normal nodes.
624 // When all of the leaf nodes from all the subtrees are concatenated, they must
625 // satisfy the same constraints as a single leaf node. They must be sorted,
626 // sane, and fully coalesced.
628 //===----------------------------------------------------------------------===//
630 template <typename KeyT, typename ValT, unsigned N, typename Traits>
631 class BranchNode : public NodeBase<NodeRef, KeyT, N> {
633 const KeyT &stop(unsigned i) const { return this->second[i]; }
634 const NodeRef &subtree(unsigned i) const { return this->first[i]; }
636 KeyT &stop(unsigned i) { return this->second[i]; }
637 NodeRef &subtree(unsigned i) { return this->first[i]; }
639 /// findFrom - Find the first subtree after i that may contain x.
640 /// @param i Starting index for the search.
641 /// @param Size Number of elements in node.
642 /// @param x Key to search for.
643 /// @return First index with !stopLess(key[i], x), or size.
644 /// This is the first subtree that can possibly contain x.
645 unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
646 assert(i <= Size && Size <= N && "Bad indices");
647 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
648 "Index to findFrom is past the needed point");
649 while (i != Size && Traits::stopLess(stop(i), x)) ++i;
653 /// safeFind - Find a subtree that is known to exist. This is the same as
654 /// findFrom except is it assumed that x is in range.
655 /// @param i Starting index for the search.
656 /// @param x Key to search for.
657 /// @return First index with !stopLess(key[i], x), never size.
658 /// This is the first subtree that can possibly contain x.
659 unsigned safeFind(unsigned i, KeyT x) const {
660 assert(i < N && "Bad index");
661 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
662 "Index is past the needed point");
663 while (Traits::stopLess(stop(i), x)) ++i;
664 assert(i < N && "Unsafe intervals");
668 /// safeLookup - Get the subtree containing x, Assuming that x is in range.
669 /// @param x Key to search for.
670 /// @return Subtree containing x
671 NodeRef safeLookup(KeyT x) const {
672 return subtree(safeFind(0, x));
675 /// insert - Insert a new (subtree, stop) pair.
676 /// @param i Insert position, following entries will be shifted.
677 /// @param Size Number of elements in node.
678 /// @param Node Subtree to insert.
679 /// @param Stop Last key in subtree.
680 void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop) {
681 assert(Size < N && "branch node overflow");
682 assert(i <= Size && "Bad insert position");
683 this->shift(i, Size);
689 void dump(unsigned Size) {
690 errs() << " N" << this << " [shape=record label=\"" << Size << '/' << N;
691 for (unsigned i = 0; i != Size; ++i)
692 errs() << " | <s" << i << "> " << stop(i);
694 for (unsigned i = 0; i != Size; ++i)
695 errs() << " N" << this << ":s" << i << " -> N"
696 << &subtree(i).template get<BranchNode>() << ";\n";
702 } // namespace IntervalMapImpl
705 //===----------------------------------------------------------------------===//
706 //--- IntervalMap ----//
707 //===----------------------------------------------------------------------===//
709 template <typename KeyT, typename ValT,
710 unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize,
711 typename Traits = IntervalMapInfo<KeyT> >
713 typedef IntervalMapImpl::NodeSizer<KeyT, ValT> Sizer;
714 typedef IntervalMapImpl::LeafNode<KeyT, ValT, Sizer::LeafSize, Traits> Leaf;
715 typedef IntervalMapImpl::BranchNode<KeyT, ValT, Sizer::BranchSize, Traits>
717 typedef IntervalMapImpl::LeafNode<KeyT, ValT, N, Traits> RootLeaf;
718 typedef IntervalMapImpl::IdxPair IdxPair;
720 // The RootLeaf capacity is given as a template parameter. We must compute the
721 // corresponding RootBranch capacity.
723 DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) /
724 (sizeof(KeyT) + sizeof(IntervalMapImpl::NodeRef)),
725 RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1
728 typedef IntervalMapImpl::BranchNode<KeyT, ValT, RootBranchCap, Traits>
731 // When branched, we store a global start key as well as the branch node.
732 struct RootBranchData {
738 RootDataSize = sizeof(RootBranchData) > sizeof(RootLeaf) ?
739 sizeof(RootBranchData) : sizeof(RootLeaf)
743 typedef typename Sizer::Allocator Allocator;
746 // The root data is either a RootLeaf or a RootBranchData instance.
747 // We can't put them in a union since C++03 doesn't allow non-trivial
748 // constructors in unions.
749 // Instead, we use a char array with pointer alignment. The alignment is
750 // ensured by the allocator member in the class, but still verified in the
751 // constructor. We don't support keys or values that are more aligned than a
753 char data[RootDataSize];
756 // 0: Leaves in root.
757 // 1: Root points to leaf.
758 // 2: root->branch->leaf ...
761 // Number of entries in the root node.
764 // Allocator used for creating external nodes.
765 Allocator &allocator;
767 /// dataAs - Represent data as a node type without breaking aliasing rules.
768 template <typename T>
778 const RootLeaf &rootLeaf() const {
779 assert(!branched() && "Cannot acces leaf data in branched root");
780 return dataAs<RootLeaf>();
782 RootLeaf &rootLeaf() {
783 assert(!branched() && "Cannot acces leaf data in branched root");
784 return dataAs<RootLeaf>();
786 RootBranchData &rootBranchData() const {
787 assert(branched() && "Cannot access branch data in non-branched root");
788 return dataAs<RootBranchData>();
790 RootBranchData &rootBranchData() {
791 assert(branched() && "Cannot access branch data in non-branched root");
792 return dataAs<RootBranchData>();
794 const RootBranch &rootBranch() const { return rootBranchData().node; }
795 RootBranch &rootBranch() { return rootBranchData().node; }
796 KeyT rootBranchStart() const { return rootBranchData().start; }
797 KeyT &rootBranchStart() { return rootBranchData().start; }
800 return new(allocator.template Allocate<Leaf>()) Leaf();
802 void deleteLeaf(Leaf *P) {
804 allocator.Deallocate(P);
807 Branch *allocBranch() {
808 return new(allocator.template Allocate<Branch>()) Branch();
810 void deleteBranch(Branch *P) {
812 allocator.Deallocate(P);
816 IdxPair branchRoot(unsigned Position);
817 IdxPair splitRoot(unsigned Position);
819 void switchRootToBranch() {
820 rootLeaf().~RootLeaf();
822 new (&rootBranchData()) RootBranchData();
825 void switchRootToLeaf() {
826 rootBranchData().~RootBranchData();
828 new(&rootLeaf()) RootLeaf();
831 bool branched() const { return height > 0; }
833 ValT treeSafeLookup(KeyT x, ValT NotFound) const;
834 void visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef,
836 void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level);
839 explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) {
840 assert((uintptr_t(data) & (alignOf<RootLeaf>() - 1)) == 0 &&
841 "Insufficient alignment");
842 new(&rootLeaf()) RootLeaf();
847 rootLeaf().~RootLeaf();
850 /// empty - Return true when no intervals are mapped.
852 return rootSize == 0;
855 /// start - Return the smallest mapped key in a non-empty map.
857 assert(!empty() && "Empty IntervalMap has no start");
858 return !branched() ? rootLeaf().start(0) : rootBranchStart();
861 /// stop - Return the largest mapped key in a non-empty map.
863 assert(!empty() && "Empty IntervalMap has no stop");
864 return !branched() ? rootLeaf().stop(rootSize - 1) :
865 rootBranch().stop(rootSize - 1);
868 /// lookup - Return the mapped value at x or NotFound.
869 ValT lookup(KeyT x, ValT NotFound = ValT()) const {
870 if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x))
872 return branched() ? treeSafeLookup(x, NotFound) :
873 rootLeaf().safeLookup(x, NotFound);
876 /// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
877 /// It is assumed that no key in the interval is mapped to another value, but
878 /// overlapping intervals already mapped to y will be coalesced.
879 void insert(KeyT a, KeyT b, ValT y) {
880 find(a).insert(a, b, y);
883 /// clear - Remove all entries.
886 class const_iterator;
888 friend class const_iterator;
889 friend class iterator;
891 const_iterator begin() const {
903 const_iterator end() const {
915 /// find - Return an iterator pointing to the first interval ending at or
916 /// after x, or end().
917 const_iterator find(KeyT x) const {
923 iterator find(KeyT x) {
931 void dumpNode(IntervalMapImpl::NodeRef Node, unsigned Height);
935 /// treeSafeLookup - Return the mapped value at x or NotFound, assuming a
937 template <typename KeyT, typename ValT, unsigned N, typename Traits>
938 ValT IntervalMap<KeyT, ValT, N, Traits>::
939 treeSafeLookup(KeyT x, ValT NotFound) const {
940 assert(branched() && "treeLookup assumes a branched root");
942 IntervalMapImpl::NodeRef NR = rootBranch().safeLookup(x);
943 for (unsigned h = height-1; h; --h)
944 NR = NR.get<Branch>().safeLookup(x);
945 return NR.get<Leaf>().safeLookup(x, NotFound);
949 // branchRoot - Switch from a leaf root to a branched root.
950 // Return the new (root offset, node offset) corresponding to Position.
951 template <typename KeyT, typename ValT, unsigned N, typename Traits>
952 IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
953 branchRoot(unsigned Position) {
954 using namespace IntervalMapImpl;
955 // How many external leaf nodes to hold RootLeaf+1?
956 const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1;
958 // Compute element distribution among new nodes.
959 unsigned size[Nodes];
960 IdxPair NewOffset(0, Position);
962 // Is is very common for the root node to be smaller than external nodes.
966 NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, size,
969 // Allocate new nodes.
972 for (unsigned n = 0; n != Nodes; ++n) {
973 node[n] = NodeRef(allocLeaf(), size[n]);
974 node[n].template get<Leaf>().copy(rootLeaf(), pos, 0, size[n]);
978 // Destroy the old leaf node, construct branch node instead.
979 switchRootToBranch();
980 for (unsigned n = 0; n != Nodes; ++n) {
981 rootBranch().stop(n) = node[n].template get<Leaf>().stop(size[n]-1);
982 rootBranch().subtree(n) = node[n];
984 rootBranchStart() = node[0].template get<Leaf>().start(0);
989 // splitRoot - Split the current BranchRoot into multiple Branch nodes.
990 // Return the new (root offset, node offset) corresponding to Position.
991 template <typename KeyT, typename ValT, unsigned N, typename Traits>
992 IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
993 splitRoot(unsigned Position) {
994 using namespace IntervalMapImpl;
995 // How many external leaf nodes to hold RootBranch+1?
996 const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1;
998 // Compute element distribution among new nodes.
999 unsigned Size[Nodes];
1000 IdxPair NewOffset(0, Position);
1002 // Is is very common for the root node to be smaller than external nodes.
1006 NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, Size,
1009 // Allocate new nodes.
1011 NodeRef Node[Nodes];
1012 for (unsigned n = 0; n != Nodes; ++n) {
1013 Node[n] = NodeRef(allocBranch(), Size[n]);
1014 Node[n].template get<Branch>().copy(rootBranch(), Pos, 0, Size[n]);
1018 for (unsigned n = 0; n != Nodes; ++n) {
1019 rootBranch().stop(n) = Node[n].template get<Branch>().stop(Size[n]-1);
1020 rootBranch().subtree(n) = Node[n];
1027 /// visitNodes - Visit each external node.
1028 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1029 void IntervalMap<KeyT, ValT, N, Traits>::
1030 visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, unsigned Height)) {
1033 SmallVector<IntervalMapImpl::NodeRef, 4> Refs, NextRefs;
1035 // Collect level 0 nodes from the root.
1036 for (unsigned i = 0; i != rootSize; ++i)
1037 Refs.push_back(rootBranch().subtree(i));
1039 // Visit all branch nodes.
1040 for (unsigned h = height - 1; h; --h) {
1041 for (unsigned i = 0, e = Refs.size(); i != e; ++i) {
1042 for (unsigned j = 0, s = Refs[i].size(); j != s; ++j)
1043 NextRefs.push_back(Refs[i].subtree(j));
1044 (this->*f)(Refs[i], h);
1047 Refs.swap(NextRefs);
1050 // Visit all leaf nodes.
1051 for (unsigned i = 0, e = Refs.size(); i != e; ++i)
1052 (this->*f)(Refs[i], 0);
1055 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1056 void IntervalMap<KeyT, ValT, N, Traits>::
1057 deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) {
1059 deleteBranch(&Node.get<Branch>());
1061 deleteLeaf(&Node.get<Leaf>());
1064 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1065 void IntervalMap<KeyT, ValT, N, Traits>::
1068 visitNodes(&IntervalMap::deleteNode);
1075 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1076 void IntervalMap<KeyT, ValT, N, Traits>::
1077 dumpNode(IntervalMapImpl::NodeRef Node, unsigned Height) {
1079 Node.get<Branch>().dump(Node.size());
1081 Node.get<Leaf>().dump(Node.size());
1084 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1085 void IntervalMap<KeyT, ValT, N, Traits>::
1087 errs() << "digraph {\n";
1089 rootBranch().dump(rootSize);
1091 rootLeaf().dump(rootSize);
1092 visitNodes(&IntervalMap::dumpNode);
1097 //===----------------------------------------------------------------------===//
1098 //--- const_iterator ----//
1099 //===----------------------------------------------------------------------===//
1101 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1102 class IntervalMap<KeyT, ValT, N, Traits>::const_iterator :
1103 public std::iterator<std::bidirectional_iterator_tag, ValT> {
1105 friend class IntervalMap;
1106 typedef std::pair<IntervalMapImpl::NodeRef, unsigned> PathEntry;
1107 typedef SmallVector<PathEntry, 4> Path;
1109 // The map referred to.
1112 // The offset into map's root node.
1113 unsigned rootOffset;
1115 // We store a full path from the root to the current position.
1117 // When rootOffset == map->rootSize, we are at end() and path() is empty.
1118 // Otherwise, when branched these conditions hold:
1120 // 1. path.front().first == rootBranch().subtree(rootOffset)
1121 // 2. path[i].first == path[i-1].first.subtree(path[i-1].second)
1122 // 3. path.size() == map->height.
1124 // Thus, path.back() always refers to the current leaf node unless the root is
1127 // The path may be partially filled, but never between iterator calls.
1130 explicit const_iterator(IntervalMap &map)
1131 : map(&map), rootOffset(map.rootSize) {}
1133 bool branched() const {
1134 assert(map && "Invalid iterator");
1135 return map->branched();
1138 IntervalMapImpl::NodeRef pathNode(unsigned h) const { return path[h].first; }
1139 IntervalMapImpl::NodeRef &pathNode(unsigned h) { return path[h].first; }
1140 unsigned pathOffset(unsigned h) const { return path[h].second; }
1141 unsigned &pathOffset(unsigned h) { return path[h].second; }
1143 Leaf &treeLeaf() const {
1144 assert(branched() && path.size() == map->height);
1145 return path.back().first.template get<Leaf>();
1147 unsigned treeLeafSize() const {
1148 assert(branched() && path.size() == map->height);
1149 return path.back().first.size();
1151 unsigned &treeLeafOffset() {
1152 assert(branched() && path.size() == map->height);
1153 return path.back().second;
1155 unsigned treeLeafOffset() const {
1156 assert(branched() && path.size() == map->height);
1157 return path.back().second;
1160 // Get the next node ptr for an incomplete path.
1161 IntervalMapImpl::NodeRef pathNextDown() {
1162 assert(path.size() < map->height && "Path is already complete");
1165 return map->rootBranch().subtree(rootOffset);
1167 return path.back().first.subtree(path.back().second);
1170 void pathFillLeft();
1171 void pathFillFind(KeyT x);
1172 void pathFillRight();
1174 IntervalMapImpl::NodeRef leftSibling(unsigned level) const;
1175 IntervalMapImpl::NodeRef rightSibling(unsigned level) const;
1177 void treeIncrement();
1178 void treeDecrement();
1179 void treeFind(KeyT x);
1182 /// valid - Return true if the current position is valid, false for end().
1183 bool valid() const {
1184 assert(map && "Invalid iterator");
1185 return rootOffset < map->rootSize;
1188 /// start - Return the beginning of the current interval.
1189 const KeyT &start() const {
1190 assert(valid() && "Cannot access invalid iterator");
1191 return branched() ? treeLeaf().start(treeLeafOffset()) :
1192 map->rootLeaf().start(rootOffset);
1195 /// stop - Return the end of the current interval.
1196 const KeyT &stop() const {
1197 assert(valid() && "Cannot access invalid iterator");
1198 return branched() ? treeLeaf().stop(treeLeafOffset()) :
1199 map->rootLeaf().stop(rootOffset);
1202 /// value - Return the mapped value at the current interval.
1203 const ValT &value() const {
1204 assert(valid() && "Cannot access invalid iterator");
1205 return branched() ? treeLeaf().value(treeLeafOffset()) :
1206 map->rootLeaf().value(rootOffset);
1209 const ValT &operator*() const {
1213 bool operator==(const const_iterator &RHS) const {
1214 assert(map == RHS.map && "Cannot compare iterators from different maps");
1215 return rootOffset == RHS.rootOffset &&
1216 (!valid() || !branched() || path.back() == RHS.path.back());
1219 bool operator!=(const const_iterator &RHS) const {
1220 return !operator==(RHS);
1223 /// goToBegin - Move to the first interval in map.
1231 /// goToEnd - Move beyond the last interval in map.
1233 rootOffset = map->rootSize;
1237 /// preincrement - move to the next interval.
1238 const_iterator &operator++() {
1239 assert(valid() && "Cannot increment end()");
1242 else if (treeLeafOffset() != treeLeafSize() - 1)
1249 /// postincrement - Dont do that!
1250 const_iterator operator++(int) {
1251 const_iterator tmp = *this;
1256 /// predecrement - move to the previous interval.
1257 const_iterator &operator--() {
1259 assert(rootOffset && "Cannot decrement begin()");
1261 } else if (valid() && treeLeafOffset())
1268 /// postdecrement - Dont do that!
1269 const_iterator operator--(int) {
1270 const_iterator tmp = *this;
1275 /// find - Move to the first interval with stop >= x, or end().
1276 /// This is a full search from the root, the current position is ignored.
1281 rootOffset = map->rootLeaf().findFrom(0, map->rootSize, x);
1284 /// advanceTo - Move to the first interval with stop >= x, or end().
1285 /// The search is started from the current position, and no earlier positions
1286 /// can be found. This is much faster than find() for small moves.
1287 void advanceTo(KeyT x) {
1291 rootOffset = map->rootLeaf().findFrom(rootOffset, map->rootSize, x);
1296 // pathFillLeft - Complete path by following left-most branches.
1297 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1298 void IntervalMap<KeyT, ValT, N, Traits>::
1299 const_iterator::pathFillLeft() {
1300 IntervalMapImpl::NodeRef NR = pathNextDown();
1301 for (unsigned i = map->height - path.size() - 1; i; --i) {
1302 path.push_back(PathEntry(NR, 0));
1305 path.push_back(PathEntry(NR, 0));
1308 // pathFillFind - Complete path by searching for x.
1309 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1310 void IntervalMap<KeyT, ValT, N, Traits>::
1311 const_iterator::pathFillFind(KeyT x) {
1312 IntervalMapImpl::NodeRef NR = pathNextDown();
1313 for (unsigned i = map->height - path.size() - 1; i; --i) {
1314 unsigned p = NR.get<Branch>().safeFind(0, x);
1315 path.push_back(PathEntry(NR, p));
1318 path.push_back(PathEntry(NR, NR.get<Leaf>().safeFind(0, x)));
1321 // pathFillRight - Complete path by adding rightmost entries.
1322 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1323 void IntervalMap<KeyT, ValT, N, Traits>::
1324 const_iterator::pathFillRight() {
1325 IntervalMapImpl::NodeRef NR = pathNextDown();
1326 for (unsigned i = map->height - path.size() - 1; i; --i) {
1327 unsigned p = NR.size() - 1;
1328 path.push_back(PathEntry(NR, p));
1331 path.push_back(PathEntry(NR, NR.size() - 1));
1334 /// leftSibling - find the left sibling node to path[level].
1335 /// @param level 0 is just below the root, map->height - 1 for the leaves.
1336 /// @return The left sibling NodeRef, or NULL.
1337 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1338 IntervalMapImpl::NodeRef IntervalMap<KeyT, ValT, N, Traits>::
1339 const_iterator::leftSibling(unsigned level) const {
1340 using namespace IntervalMapImpl;
1341 assert(branched() && "Not at a branched node");
1342 assert(level <= path.size() && "Bad level");
1344 // Go up the tree until we can go left.
1346 while (h && pathOffset(h - 1) == 0)
1349 // We are at the first leaf node, no left sibling.
1350 if (!h && rootOffset == 0)
1353 // NR is the subtree containing our left sibling.
1355 pathNode(h - 1).subtree(pathOffset(h - 1) - 1) :
1356 map->rootBranch().subtree(rootOffset - 1);
1358 // Keep right all the way down.
1359 for (; h != level; ++h)
1360 NR = NR.subtree(NR.size() - 1);
1364 /// rightSibling - find the right sibling node to path[level].
1365 /// @param level 0 is just below the root, map->height - 1 for the leaves.
1366 /// @return The right sibling NodeRef, or NULL.
1367 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1368 IntervalMapImpl::NodeRef IntervalMap<KeyT, ValT, N, Traits>::
1369 const_iterator::rightSibling(unsigned level) const {
1370 using namespace IntervalMapImpl;
1371 assert(branched() && "Not at a branched node");
1372 assert(level <= this->path.size() && "Bad level");
1374 // Go up the tree until we can go right.
1376 while (h && pathOffset(h - 1) == pathNode(h - 1).size() - 1)
1379 // We are at the last leaf node, no right sibling.
1380 if (!h && rootOffset == map->rootSize - 1)
1383 // NR is the subtree containing our right sibling.
1385 pathNode(h - 1).subtree(pathOffset(h - 1) + 1) :
1386 map->rootBranch().subtree(rootOffset + 1);
1388 // Keep left all the way down.
1389 for (; h != level; ++h)
1394 // treeIncrement - Move to the beginning of the next leaf node.
1395 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1396 void IntervalMap<KeyT, ValT, N, Traits>::
1397 const_iterator::treeIncrement() {
1398 assert(branched() && "treeIncrement is not for small maps");
1399 assert(path.size() == map->height && "inconsistent iterator");
1401 while (!path.empty() && path.back().second == path.back().first.size() - 1);
1407 ++path.back().second;
1411 // treeDecrement - Move to the end of the previous leaf node.
1412 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1413 void IntervalMap<KeyT, ValT, N, Traits>::
1414 const_iterator::treeDecrement() {
1415 assert(branched() && "treeDecrement is not for small maps");
1417 assert(path.size() == map->height && "inconsistent iterator");
1419 while (!path.empty() && path.back().second == 0);
1422 assert(rootOffset && "cannot treeDecrement() on begin()");
1425 --path.back().second;
1429 // treeFind - Find in a branched tree.
1430 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1431 void IntervalMap<KeyT, ValT, N, Traits>::
1432 const_iterator::treeFind(KeyT x) {
1434 rootOffset = map->rootBranch().findFrom(0, map->rootSize, x);
1440 //===----------------------------------------------------------------------===//
1441 //--- iterator ----//
1442 //===----------------------------------------------------------------------===//
1444 namespace IntervalMapImpl {
1446 /// distribute - Compute a new distribution of node elements after an overflow
1447 /// or underflow. Reserve space for a new element at Position, and compute the
1448 /// node that will hold Position after redistributing node elements.
1450 /// It is required that
1452 /// Elements == sum(CurSize), and
1453 /// Elements + Grow <= Nodes * Capacity.
1455 /// NewSize[] will be filled in such that:
1457 /// sum(NewSize) == Elements, and
1458 /// NewSize[i] <= Capacity.
1460 /// The returned index is the node where Position will go, so:
1462 /// sum(NewSize[0..idx-1]) <= Position
1463 /// sum(NewSize[0..idx]) >= Position
1465 /// The last equality, sum(NewSize[0..idx]) == Position, can only happen when
1466 /// Grow is set and NewSize[idx] == Capacity-1. The index points to the node
1467 /// before the one holding the Position'th element where there is room for an
1470 /// @param Nodes The number of nodes.
1471 /// @param Elements Total elements in all nodes.
1472 /// @param Capacity The capacity of each node.
1473 /// @param CurSize Array[Nodes] of current node sizes, or NULL.
1474 /// @param NewSize Array[Nodes] to receive the new node sizes.
1475 /// @param Position Insert position.
1476 /// @param Grow Reserve space for a new element at Position.
1477 /// @return (node, offset) for Position.
1478 IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,
1479 const unsigned *CurSize, unsigned NewSize[],
1480 unsigned Position, bool Grow);
1484 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1485 class IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator {
1486 friend class IntervalMap;
1487 typedef IntervalMapImpl::IdxPair IdxPair;
1489 explicit iterator(IntervalMap &map) : const_iterator(map) {}
1491 void setNodeSize(unsigned Level, unsigned Size);
1492 void setNodeStop(unsigned Level, KeyT Stop);
1493 bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop);
1494 template <typename NodeT> bool overflow(unsigned Level);
1495 void treeInsert(KeyT a, KeyT b, ValT y);
1498 /// insert - Insert mapping [a;b] -> y before the current position.
1499 void insert(KeyT a, KeyT b, ValT y);
1503 /// setNodeSize - Set the size of the node at path[level], updating both path
1504 /// and the real tree.
1505 /// @param level 0 is just below the root, map->height - 1 for the leaves.
1506 /// @param size New node size.
1507 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1508 void IntervalMap<KeyT, ValT, N, Traits>::
1509 iterator::setNodeSize(unsigned Level, unsigned Size) {
1510 this->pathNode(Level).setSize(Size);
1512 this->pathNode(Level-1).subtree(this->pathOffset(Level-1)).setSize(Size);
1514 this->map->rootBranch().subtree(this->rootOffset).setSize(Size);
1517 /// setNodeStop - Update the stop key of the current node at level and above.
1518 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1519 void IntervalMap<KeyT, ValT, N, Traits>::
1520 iterator::setNodeStop(unsigned Level, KeyT Stop) {
1522 this->pathNode(Level).template get<Branch>()
1523 .stop(this->pathOffset(Level)) = Stop;
1524 if (this->pathOffset(Level) != this->pathNode(Level).size() - 1)
1527 this->map->rootBranch().stop(this->rootOffset) = Stop;
1530 /// insertNode - insert a node before the current path at level.
1531 /// Leave the current path pointing at the new node.
1532 /// @param Level path index of the node to be inserted.
1533 /// @param Node The node to be inserted.
1534 /// @param Stop The last index in the new node.
1535 /// @return True if the tree height was increased.
1536 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1537 bool IntervalMap<KeyT, ValT, N, Traits>::
1538 iterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) {
1539 bool SplitRoot = false;
1542 // Insert into the root branch node.
1543 IntervalMap &IM = *this->map;
1544 if (IM.rootSize < RootBranch::Capacity) {
1545 IM.rootBranch().insert(this->rootOffset, IM.rootSize, Node, Stop);
1550 // We need to split the root while keeping our position.
1552 IdxPair Offset = IM.splitRoot(this->rootOffset);
1553 this->rootOffset = Offset.first;
1554 this->path.insert(this->path.begin(),std::make_pair(
1555 this->map->rootBranch().subtree(Offset.first), Offset.second));
1559 // When inserting before end(), make sure we have a valid path.
1560 if (!this->valid()) {
1561 this->treeDecrement();
1562 ++this->pathOffset(Level-1);
1565 // Insert into the branch node at level-1.
1566 if (this->pathNode(Level-1).size() == Branch::Capacity) {
1567 assert(!SplitRoot && "Cannot overflow after splitting the root");
1568 SplitRoot = overflow<Branch>(Level - 1);
1571 IntervalMapImpl::NodeRef NR = this->pathNode(Level-1);
1572 unsigned Offset = this->pathOffset(Level-1);
1573 NR.get<Branch>().insert(Offset, NR.size(), Node, Stop);
1574 setNodeSize(Level - 1, NR.size() + 1);
1579 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1580 void IntervalMap<KeyT, ValT, N, Traits>::
1581 iterator::insert(KeyT a, KeyT b, ValT y) {
1582 if (this->branched())
1583 return treeInsert(a, b, y);
1584 IdxPair IP = this->map->rootLeaf().insertFrom(this->rootOffset,
1585 this->map->rootSize,
1587 if (IP.second <= RootLeaf::Capacity) {
1588 this->rootOffset = IP.first;
1589 this->map->rootSize = IP.second;
1592 IdxPair Offset = this->map->branchRoot(this->rootOffset);
1593 this->rootOffset = Offset.first;
1594 this->path.push_back(std::make_pair(
1595 this->map->rootBranch().subtree(Offset.first), Offset.second));
1596 treeInsert(a, b, y);
1600 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1601 void IntervalMap<KeyT, ValT, N, Traits>::
1602 iterator::treeInsert(KeyT a, KeyT b, ValT y) {
1603 if (!this->valid()) {
1604 // end() has an empty path. Go back to the last leaf node and use an
1605 // invalid offset instead.
1606 this->treeDecrement();
1607 ++this->treeLeafOffset();
1609 IdxPair IP = this->treeLeaf().insertFrom(this->treeLeafOffset(),
1610 this->treeLeafSize(), a, b, y);
1611 this->treeLeafOffset() = IP.first;
1612 if (IP.second <= Leaf::Capacity) {
1613 setNodeSize(this->map->height - 1, IP.second);
1614 if (IP.first == IP.second - 1)
1615 setNodeStop(this->map->height - 1, this->treeLeaf().stop(IP.first));
1618 // Leaf node has no space.
1619 overflow<Leaf>(this->map->height - 1);
1620 IP = this->treeLeaf().insertFrom(this->treeLeafOffset(),
1621 this->treeLeafSize(), a, b, y);
1622 this->treeLeafOffset() = IP.first;
1623 setNodeSize(this->map->height-1, IP.second);
1624 if (IP.first == IP.second - 1)
1625 setNodeStop(this->map->height - 1, this->treeLeaf().stop(IP.first));
1627 // FIXME: Handle cross-node coalescing.
1630 /// overflow - Distribute entries of the current node evenly among
1631 /// its siblings and ensure that the current node is not full.
1632 /// This may require allocating a new node.
1633 /// @param NodeT The type of node at Level (Leaf or Branch).
1634 /// @param Level path index of the overflowing node.
1635 /// @return True when the tree height was changed.
1636 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1637 template <typename NodeT>
1638 bool IntervalMap<KeyT, ValT, N, Traits>::
1639 iterator::overflow(unsigned Level) {
1640 using namespace IntervalMapImpl;
1641 unsigned CurSize[4];
1644 unsigned Elements = 0;
1645 unsigned Offset = this->pathOffset(Level);
1647 // Do we have a left sibling?
1648 NodeRef LeftSib = this->leftSibling(Level);
1650 Offset += Elements = CurSize[Nodes] = LeftSib.size();
1651 Node[Nodes++] = &LeftSib.get<NodeT>();
1655 NodeRef CurNode = this->pathNode(Level);
1656 Elements += CurSize[Nodes] = CurNode.size();
1657 Node[Nodes++] = &CurNode.get<NodeT>();
1659 // Do we have a right sibling?
1660 NodeRef RightSib = this->rightSibling(Level);
1662 Offset += Elements = CurSize[Nodes] = RightSib.size();
1663 Node[Nodes++] = &RightSib.get<NodeT>();
1666 // Do we need to allocate a new node?
1667 unsigned NewNode = 0;
1668 if (Elements + 1 > Nodes * NodeT::Capacity) {
1669 // Insert NewNode at the penultimate position, or after a single node.
1670 NewNode = Nodes == 1 ? 1 : Nodes - 1;
1671 CurSize[Nodes] = CurSize[NewNode];
1672 Node[Nodes] = Node[NewNode];
1673 CurSize[NewNode] = 0;
1674 Node[NewNode] = new(this->map->allocator.template Allocate<NodeT>())NodeT();
1678 // Compute the new element distribution.
1679 unsigned NewSize[4];
1680 IdxPair NewOffset = distribute(Nodes, Elements, NodeT::Capacity,
1681 CurSize, NewSize, Offset, true);
1683 // Move current location to the leftmost node.
1685 this->treeDecrement();
1687 // Move elements right.
1688 for (int n = Nodes - 1; n; --n) {
1689 if (CurSize[n] == NewSize[n])
1691 for (int m = n - 1; m != -1; --m) {
1692 int d = Node[n]->adjustFromLeftSib(CurSize[n], *Node[m], CurSize[m],
1693 NewSize[n] - CurSize[n]);
1696 // Keep going if the current node was exhausted.
1697 if (CurSize[n] >= NewSize[n])
1702 // Move elements left.
1703 for (unsigned n = 0; n != Nodes - 1; ++n) {
1704 if (CurSize[n] == NewSize[n])
1706 for (unsigned m = n + 1; m != Nodes; ++m) {
1707 int d = Node[m]->adjustFromLeftSib(CurSize[m], *Node[n], CurSize[n],
1708 CurSize[n] - NewSize[n]);
1711 // Keep going if the current node was exhausted.
1712 if (CurSize[n] >= NewSize[n])
1718 for (unsigned n = 0; n != Nodes; n++)
1719 assert(CurSize[n] == NewSize[n] && "Insufficient element shuffle");
1722 // Elements have been rearranged, now update node sizes and stops.
1723 bool SplitRoot = false;
1726 KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1);
1727 if (NewNode && Pos == NewNode) {
1728 SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop);
1731 setNodeSize(Level, NewSize[Pos]);
1732 setNodeStop(Level, Stop);
1734 if (Pos + 1 == Nodes)
1736 this->treeIncrement();
1740 // Where was I? Find NewOffset.
1741 while(Pos != NewOffset.first) {
1742 this->treeDecrement();
1745 this->pathOffset(Level) = NewOffset.second;