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);
297 /// adjustSiblingSizes - Move elements between sibling nodes.
298 /// @param Node Array of pointers to sibling nodes.
299 /// @param Nodes Number of nodes.
300 /// @param CurSize Array of current node sizes, will be overwritten.
301 /// @param NewSize Array of desired node sizes.
302 template <typename NodeT>
303 void adjustSiblingSizes(NodeT *Node[], unsigned Nodes,
304 unsigned CurSize[], const unsigned NewSize[]) {
305 // Move elements right.
306 for (int n = Nodes - 1; n; --n) {
307 if (CurSize[n] == NewSize[n]) {
311 for (int m = n - 1; m != -1; --m) {
312 int d = Node[n]->adjustFromLeftSib(CurSize[n], *Node[m], CurSize[m],
313 NewSize[n] - CurSize[n]);
316 // Keep going if the current node was exhausted.
317 if (CurSize[n] >= NewSize[n])
325 // Move elements left.
326 for (unsigned n = 0; n != Nodes - 1; ++n) {
327 if (CurSize[n] == NewSize[n])
329 for (unsigned m = n + 1; m != Nodes; ++m) {
330 int d = Node[m]->adjustFromLeftSib(CurSize[m], *Node[n], CurSize[n],
331 CurSize[n] - NewSize[n]);
334 // Keep going if the current node was exhausted.
335 if (CurSize[n] >= NewSize[n])
341 for (unsigned n = 0; n != Nodes; n++)
342 assert(CurSize[n] == NewSize[n] && "Insufficient element shuffle");
346 /// distribute - Compute a new distribution of node elements after an overflow
347 /// or underflow. Reserve space for a new element at Position, and compute the
348 /// node that will hold Position after redistributing node elements.
350 /// It is required that
352 /// Elements == sum(CurSize), and
353 /// Elements + Grow <= Nodes * Capacity.
355 /// NewSize[] will be filled in such that:
357 /// sum(NewSize) == Elements, and
358 /// NewSize[i] <= Capacity.
360 /// The returned index is the node where Position will go, so:
362 /// sum(NewSize[0..idx-1]) <= Position
363 /// sum(NewSize[0..idx]) >= Position
365 /// The last equality, sum(NewSize[0..idx]) == Position, can only happen when
366 /// Grow is set and NewSize[idx] == Capacity-1. The index points to the node
367 /// before the one holding the Position'th element where there is room for an
370 /// @param Nodes The number of nodes.
371 /// @param Elements Total elements in all nodes.
372 /// @param Capacity The capacity of each node.
373 /// @param CurSize Array[Nodes] of current node sizes, or NULL.
374 /// @param NewSize Array[Nodes] to receive the new node sizes.
375 /// @param Position Insert position.
376 /// @param Grow Reserve space for a new element at Position.
377 /// @return (node, offset) for Position.
378 IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,
379 const unsigned *CurSize, unsigned NewSize[],
380 unsigned Position, bool Grow);
383 //===----------------------------------------------------------------------===//
384 //--- NodeSizer ---//
385 //===----------------------------------------------------------------------===//
387 // Compute node sizes from key and value types.
389 // The branching factors are chosen to make nodes fit in three cache lines.
390 // This may not be possible if keys or values are very large. Such large objects
391 // are handled correctly, but a std::map would probably give better performance.
393 //===----------------------------------------------------------------------===//
396 // Cache line size. Most architectures have 32 or 64 byte cache lines.
397 // We use 64 bytes here because it provides good branching factors.
399 CacheLineBytes = 1 << Log2CacheLine,
400 DesiredNodeBytes = 3 * CacheLineBytes
403 template <typename KeyT, typename ValT>
406 // Compute the leaf node branching factor that makes a node fit in three
407 // cache lines. The branching factor must be at least 3, or some B+-tree
408 // balancing algorithms won't work.
409 // LeafSize can't be larger than CacheLineBytes. This is required by the
410 // PointerIntPair used by NodeRef.
411 DesiredLeafSize = DesiredNodeBytes /
412 static_cast<unsigned>(2*sizeof(KeyT)+sizeof(ValT)),
414 LeafSize = DesiredLeafSize > MinLeafSize ? DesiredLeafSize : MinLeafSize
417 typedef NodeBase<std::pair<KeyT, KeyT>, ValT, LeafSize> LeafBase;
420 // Now that we have the leaf branching factor, compute the actual allocation
421 // unit size by rounding up to a whole number of cache lines.
422 AllocBytes = (sizeof(LeafBase) + CacheLineBytes-1) & ~(CacheLineBytes-1),
424 // Determine the branching factor for branch nodes.
425 BranchSize = AllocBytes /
426 static_cast<unsigned>(sizeof(KeyT) + sizeof(void*))
429 /// Allocator - The recycling allocator used for both branch and leaf nodes.
430 /// This typedef is very likely to be identical for all IntervalMaps with
431 /// reasonably sized entries, so the same allocator can be shared among
432 /// different kinds of maps.
433 typedef RecyclingAllocator<BumpPtrAllocator, char,
434 AllocBytes, CacheLineBytes> Allocator;
439 //===----------------------------------------------------------------------===//
441 //===----------------------------------------------------------------------===//
443 // B+-tree nodes can be leaves or branches, so we need a polymorphic node
444 // pointer that can point to both kinds.
446 // All nodes are cache line aligned and the low 6 bits of a node pointer are
447 // always 0. These bits are used to store the number of elements in the
448 // referenced node. Besides saving space, placing node sizes in the parents
449 // allow tree balancing algorithms to run without faulting cache lines for nodes
450 // that may not need to be modified.
452 // A NodeRef doesn't know whether it references a leaf node or a branch node.
453 // It is the responsibility of the caller to use the correct types.
455 // Nodes are never supposed to be empty, and it is invalid to store a node size
456 // of 0 in a NodeRef. The valid range of sizes is 1-64.
458 //===----------------------------------------------------------------------===//
460 struct CacheAlignedPointerTraits {
461 static inline void *getAsVoidPointer(void *P) { return P; }
462 static inline void *getFromVoidPointer(void *P) { return P; }
463 enum { NumLowBitsAvailable = Log2CacheLine };
467 PointerIntPair<void*, Log2CacheLine, unsigned, CacheAlignedPointerTraits> pip;
470 /// NodeRef - Create a null ref.
473 /// operator bool - Detect a null ref.
474 operator bool() const { return pip.getOpaqueValue(); }
476 /// NodeRef - Create a reference to the node p with n elements.
477 template <typename NodeT>
478 NodeRef(NodeT *p, unsigned n) : pip(p, n - 1) {
479 assert(n <= NodeT::Capacity && "Size too big for node");
482 /// size - Return the number of elements in the referenced node.
483 unsigned size() const { return pip.getInt() + 1; }
485 /// setSize - Update the node size.
486 void setSize(unsigned n) { pip.setInt(n - 1); }
488 /// subtree - Access the i'th subtree reference in a branch node.
489 /// This depends on branch nodes storing the NodeRef array as their first
491 NodeRef &subtree(unsigned i) const {
492 return reinterpret_cast<NodeRef*>(pip.getPointer())[i];
495 /// get - Dereference as a NodeT reference.
496 template <typename NodeT>
498 return *reinterpret_cast<NodeT*>(pip.getPointer());
501 bool operator==(const NodeRef &RHS) const {
504 assert(pip.getPointer() != RHS.pip.getPointer() && "Inconsistent NodeRefs");
508 bool operator!=(const NodeRef &RHS) const {
509 return !operator==(RHS);
513 //===----------------------------------------------------------------------===//
514 //--- Leaf nodes ---//
515 //===----------------------------------------------------------------------===//
517 // Leaf nodes store up to N disjoint intervals with corresponding values.
519 // The intervals are kept sorted and fully coalesced so there are no adjacent
520 // intervals mapping to the same value.
522 // These constraints are always satisfied:
524 // - Traits::stopLess(start(i), stop(i)) - Non-empty, sane intervals.
526 // - Traits::stopLess(stop(i), start(i + 1) - Sorted.
528 // - value(i) != value(i + 1) || !Traits::adjacent(stop(i), start(i + 1))
529 // - Fully coalesced.
531 //===----------------------------------------------------------------------===//
533 template <typename KeyT, typename ValT, unsigned N, typename Traits>
534 class LeafNode : public NodeBase<std::pair<KeyT, KeyT>, ValT, N> {
536 const KeyT &start(unsigned i) const { return this->first[i].first; }
537 const KeyT &stop(unsigned i) const { return this->first[i].second; }
538 const ValT &value(unsigned i) const { return this->second[i]; }
540 KeyT &start(unsigned i) { return this->first[i].first; }
541 KeyT &stop(unsigned i) { return this->first[i].second; }
542 ValT &value(unsigned i) { return this->second[i]; }
544 /// findFrom - Find the first interval after i that may contain x.
545 /// @param i Starting index for the search.
546 /// @param Size Number of elements in node.
547 /// @param x Key to search for.
548 /// @return First index with !stopLess(key[i].stop, x), or size.
549 /// This is the first interval that can possibly contain x.
550 unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
551 assert(i <= Size && Size <= N && "Bad indices");
552 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
553 "Index is past the needed point");
554 while (i != Size && Traits::stopLess(stop(i), x)) ++i;
558 /// safeFind - Find an interval that is known to exist. This is the same as
559 /// findFrom except is it assumed that x is at least within range of the last
561 /// @param i Starting index for the search.
562 /// @param x Key to search for.
563 /// @return First index with !stopLess(key[i].stop, x), never size.
564 /// This is the first interval that can possibly contain x.
565 unsigned safeFind(unsigned i, KeyT x) const {
566 assert(i < N && "Bad index");
567 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
568 "Index is past the needed point");
569 while (Traits::stopLess(stop(i), x)) ++i;
570 assert(i < N && "Unsafe intervals");
574 /// safeLookup - Lookup mapped value for a safe key.
575 /// It is assumed that x is within range of the last entry.
576 /// @param x Key to search for.
577 /// @param NotFound Value to return if x is not in any interval.
578 /// @return The mapped value at x or NotFound.
579 ValT safeLookup(KeyT x, ValT NotFound) const {
580 unsigned i = safeFind(0, x);
581 return Traits::startLess(x, start(i)) ? NotFound : value(i);
584 IdxPair insertFrom(unsigned i, unsigned Size, KeyT a, KeyT b, ValT y);
585 unsigned extendStop(unsigned i, unsigned Size, KeyT b);
588 void dump(raw_ostream &OS, unsigned Size) {
589 OS << " N" << this << " [shape=record label=\"{ " << Size << '/' << N;
590 for (unsigned i = 0; i != Size; ++i)
591 OS << " | {" << start(i) << '-' << stop(i) << "|" << value(i) << '}';
598 /// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as
599 /// possible. This may cause the node to grow by 1, or it may cause the node
600 /// to shrink because of coalescing.
601 /// @param i Starting index = insertFrom(0, size, a)
602 /// @param Size Number of elements in node.
603 /// @param a Interval start.
604 /// @param b Interval stop.
605 /// @param y Value be mapped.
606 /// @return (insert position, new size), or (i, Capacity+1) on overflow.
607 template <typename KeyT, typename ValT, unsigned N, typename Traits>
608 IdxPair LeafNode<KeyT, ValT, N, Traits>::
609 insertFrom(unsigned i, unsigned Size, KeyT a, KeyT b, ValT y) {
610 assert(i <= Size && Size <= N && "Invalid index");
611 assert(!Traits::stopLess(b, a) && "Invalid interval");
613 // Verify the findFrom invariant.
614 assert((i == 0 || Traits::stopLess(stop(i - 1), a)));
615 assert((i == Size || !Traits::stopLess(stop(i), a)));
617 // Coalesce with previous interval.
618 if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a))
619 return IdxPair(i - 1, extendStop(i - 1, Size, b));
623 return IdxPair(i, N + 1);
625 // Add new interval at end.
630 return IdxPair(i, Size + 1);
633 // Overlapping intervals?
634 if (!Traits::stopLess(b, start(i))) {
635 assert(value(i) == y && "Inconsistent values in overlapping intervals");
636 if (Traits::startLess(a, start(i)))
638 return IdxPair(i, extendStop(i, Size, b));
641 // Try to coalesce with following interval.
642 if (value(i) == y && Traits::adjacent(b, start(i))) {
644 return IdxPair(i, Size);
647 // We must insert before i. Detect overflow.
649 return IdxPair(i, N + 1);
652 this->shift(i, Size);
656 return IdxPair(i, Size + 1);
659 /// extendStop - Extend stop(i) to b, coalescing with following intervals.
660 /// @param i Interval to extend.
661 /// @param Size Number of elements in node.
662 /// @param b New interval end point.
663 /// @return New node size after coalescing.
664 template <typename KeyT, typename ValT, unsigned N, typename Traits>
665 unsigned LeafNode<KeyT, ValT, N, Traits>::
666 extendStop(unsigned i, unsigned Size, KeyT b) {
667 assert(i < Size && Size <= N && "Bad indices");
669 // Are we even extending the interval?
670 if (Traits::startLess(b, stop(i)))
673 // Find the first interval that may be preserved.
674 unsigned j = findFrom(i + 1, Size, b);
676 // Would key[i] overlap key[j] after the extension?
677 if (Traits::stopLess(b, start(j))) {
678 // Not overlapping. Perhaps adjacent and coalescable?
679 if (value(i) == value(j) && Traits::adjacent(b, start(j)))
682 // Overlap. Include key[j] in the new interval.
683 assert(value(i) == value(j) && "Overlapping values");
689 // Entries [i+1;j) were coalesced.
690 if (i + 1 < j && j < Size)
691 this->erase(i + 1, j, Size);
692 return Size - (j - (i + 1));
696 //===----------------------------------------------------------------------===//
697 //--- Branch nodes ---//
698 //===----------------------------------------------------------------------===//
700 // A branch node stores references to 1--N subtrees all of the same height.
702 // The key array in a branch node holds the rightmost stop key of each subtree.
703 // It is redundant to store the last stop key since it can be found in the
704 // parent node, but doing so makes tree balancing a lot simpler.
706 // It is unusual for a branch node to only have one subtree, but it can happen
707 // in the root node if it is smaller than the normal nodes.
709 // When all of the leaf nodes from all the subtrees are concatenated, they must
710 // satisfy the same constraints as a single leaf node. They must be sorted,
711 // sane, and fully coalesced.
713 //===----------------------------------------------------------------------===//
715 template <typename KeyT, typename ValT, unsigned N, typename Traits>
716 class BranchNode : public NodeBase<NodeRef, KeyT, N> {
718 const KeyT &stop(unsigned i) const { return this->second[i]; }
719 const NodeRef &subtree(unsigned i) const { return this->first[i]; }
721 KeyT &stop(unsigned i) { return this->second[i]; }
722 NodeRef &subtree(unsigned i) { return this->first[i]; }
724 /// findFrom - Find the first subtree after i that may contain x.
725 /// @param i Starting index for the search.
726 /// @param Size Number of elements in node.
727 /// @param x Key to search for.
728 /// @return First index with !stopLess(key[i], x), or size.
729 /// This is the first subtree that can possibly contain x.
730 unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
731 assert(i <= Size && Size <= N && "Bad indices");
732 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
733 "Index to findFrom is past the needed point");
734 while (i != Size && Traits::stopLess(stop(i), x)) ++i;
738 /// safeFind - Find a subtree that is known to exist. This is the same as
739 /// findFrom except is it assumed that x is in range.
740 /// @param i Starting index for the search.
741 /// @param x Key to search for.
742 /// @return First index with !stopLess(key[i], x), never size.
743 /// This is the first subtree that can possibly contain x.
744 unsigned safeFind(unsigned i, KeyT x) const {
745 assert(i < N && "Bad index");
746 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
747 "Index is past the needed point");
748 while (Traits::stopLess(stop(i), x)) ++i;
749 assert(i < N && "Unsafe intervals");
753 /// safeLookup - Get the subtree containing x, Assuming that x is in range.
754 /// @param x Key to search for.
755 /// @return Subtree containing x
756 NodeRef safeLookup(KeyT x) const {
757 return subtree(safeFind(0, x));
760 /// insert - Insert a new (subtree, stop) pair.
761 /// @param i Insert position, following entries will be shifted.
762 /// @param Size Number of elements in node.
763 /// @param Node Subtree to insert.
764 /// @param Stop Last key in subtree.
765 void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop) {
766 assert(Size < N && "branch node overflow");
767 assert(i <= Size && "Bad insert position");
768 this->shift(i, Size);
774 void dump(raw_ostream &OS, unsigned Size) {
775 OS << " N" << this << " [shape=record label=\"" << Size << '/' << N;
776 for (unsigned i = 0; i != Size; ++i)
777 OS << " | <s" << i << "> " << stop(i);
779 for (unsigned i = 0; i != Size; ++i)
780 OS << " N" << this << ":s" << i << " -> N"
781 << &subtree(i).template get<BranchNode>() << ";\n";
787 //===----------------------------------------------------------------------===//
789 //===----------------------------------------------------------------------===//
791 // A Path is used by iterators to represent a position in a B+-tree, and the
792 // path to get there from the root.
794 // The Path class also constains the tree navigation code that doesn't have to
797 //===----------------------------------------------------------------------===//
800 /// Entry - Each step in the path is a node pointer and an offset into that
807 Entry(void *Node, unsigned Size, unsigned Offset)
808 : node(Node), size(Size), offset(Offset) {}
810 Entry(NodeRef Node, unsigned Offset)
811 : node(&Node.subtree(0)), size(Node.size()), offset(Offset) {}
813 NodeRef &subtree(unsigned i) const {
814 return reinterpret_cast<NodeRef*>(node)[i];
818 /// path - The path entries, path[0] is the root node, path.back() is a leaf.
819 SmallVector<Entry, 4> path;
823 template <typename NodeT> NodeT &node(unsigned Level) const {
824 return *reinterpret_cast<NodeT*>(path[Level].node);
826 unsigned size(unsigned Level) const { return path[Level].size; }
827 unsigned offset(unsigned Level) const { return path[Level].offset; }
828 unsigned &offset(unsigned Level) { return path[Level].offset; }
831 template <typename NodeT> NodeT &leaf() const {
832 return *reinterpret_cast<NodeT*>(path.back().node);
834 unsigned leafSize() const { return path.back().size; }
835 unsigned leafOffset() const { return path.back().offset; }
836 unsigned &leafOffset() { return path.back().offset; }
838 /// valid - Return true if path is at a valid node, not at end().
840 return !path.empty() && path.front().offset < path.front().size;
843 /// height - Return the height of the tree corresponding to this path.
844 /// This matches map->height in a full path.
845 unsigned height() const { return path.size() - 1; }
847 /// subtree - Get the subtree referenced from Level. When the path is
848 /// consistent, node(Level + 1) == subtree(Level).
849 /// @param Level 0..height-1. The leaves have no subtrees.
850 NodeRef &subtree(unsigned Level) const {
851 return path[Level].subtree(path[Level].offset);
854 /// reset - Reset cached information about node(Level) from subtree(Level -1).
855 /// @param Level 1..height. THe node to update after parent node changed.
856 void reset(unsigned Level) {
857 path[Level] = Entry(subtree(Level - 1), offset(Level));
860 /// push - Add entry to path.
861 /// @param Node Node to add, should be subtree(path.size()-1).
862 /// @param Offset Offset into Node.
863 void push(NodeRef Node, unsigned Offset) {
864 path.push_back(Entry(Node, Offset));
867 /// setSize - Set the size of a node both in the path and in the tree.
868 /// @param Level 0..height. Note that setting the root size won't change
870 /// @param Size New node size.
871 void setSize(unsigned Level, unsigned Size) {
872 path[Level].size = Size;
874 subtree(Level - 1).setSize(Size);
877 /// setRoot - Clear the path and set a new root node.
878 /// @param Node New root node.
879 /// @param Size New root size.
880 /// @param Offset Offset into root node.
881 void setRoot(void *Node, unsigned Size, unsigned Offset) {
883 path.push_back(Entry(Node, Size, Offset));
886 /// replaceRoot - Replace the current root node with two new entries after the
887 /// tree height has increased.
888 /// @param Root The new root node.
889 /// @param Size Number of entries in the new root.
890 /// @param Offsets Offsets into the root and first branch nodes.
891 void replaceRoot(void *Root, unsigned Size, IdxPair Offsets);
893 /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
894 /// @param Level Get the sibling to node(Level).
895 /// @return Left sibling, or NodeRef().
896 NodeRef getLeftSibling(unsigned Level) const;
898 /// moveLeft - Move path to the left sibling at Level. Leave nodes below Level
900 /// @param Level Move node(Level).
901 void moveLeft(unsigned Level);
903 /// fillLeft - Grow path to Height by taking leftmost branches.
904 /// @param Height The target height.
905 void fillLeft(unsigned Height) {
906 while (height() < Height)
907 push(subtree(height()), 0);
910 /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
911 /// @param Level Get the sinbling to node(Level).
912 /// @return Left sibling, or NodeRef().
913 NodeRef getRightSibling(unsigned Level) const;
915 /// moveRight - Move path to the left sibling at Level. Leave nodes below
917 /// @param Level Move node(Level).
918 void moveRight(unsigned Level);
920 /// atLastBranch - Return true if the path is at the last branch of the node
922 /// @param Level Node to examine.
923 bool atLastBranch(unsigned Level) const {
924 return path[Level].offset == path[Level].size - 1;
927 /// legalizeForInsert - Prepare the path for an insertion at Level. When the
928 /// path is at end(), node(Level) may not be a legal node. legalizeForInsert
929 /// ensures that node(Level) is real by moving back to the last node at Level,
930 /// and setting offset(Level) to size(Level) if required.
931 /// @param Level The level where an insertion is about to take place.
932 void legalizeForInsert(unsigned Level) {
936 ++path[Level].offset;
941 for (unsigned l = 0, e = path.size(); l != e; ++l)
942 errs() << l << ": " << path[l].node << ' ' << path[l].size << ' '
943 << path[l].offset << '\n';
948 } // namespace IntervalMapImpl
951 //===----------------------------------------------------------------------===//
952 //--- IntervalMap ----//
953 //===----------------------------------------------------------------------===//
955 template <typename KeyT, typename ValT,
956 unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize,
957 typename Traits = IntervalMapInfo<KeyT> >
959 typedef IntervalMapImpl::NodeSizer<KeyT, ValT> Sizer;
960 typedef IntervalMapImpl::LeafNode<KeyT, ValT, Sizer::LeafSize, Traits> Leaf;
961 typedef IntervalMapImpl::BranchNode<KeyT, ValT, Sizer::BranchSize, Traits>
963 typedef IntervalMapImpl::LeafNode<KeyT, ValT, N, Traits> RootLeaf;
964 typedef IntervalMapImpl::IdxPair IdxPair;
966 // The RootLeaf capacity is given as a template parameter. We must compute the
967 // corresponding RootBranch capacity.
969 DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) /
970 (sizeof(KeyT) + sizeof(IntervalMapImpl::NodeRef)),
971 RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1
974 typedef IntervalMapImpl::BranchNode<KeyT, ValT, RootBranchCap, Traits>
977 // When branched, we store a global start key as well as the branch node.
978 struct RootBranchData {
984 RootDataSize = sizeof(RootBranchData) > sizeof(RootLeaf) ?
985 sizeof(RootBranchData) : sizeof(RootLeaf)
989 typedef typename Sizer::Allocator Allocator;
992 // The root data is either a RootLeaf or a RootBranchData instance.
993 // We can't put them in a union since C++03 doesn't allow non-trivial
994 // constructors in unions.
995 // Instead, we use a char array with pointer alignment. The alignment is
996 // ensured by the allocator member in the class, but still verified in the
997 // constructor. We don't support keys or values that are more aligned than a
999 char data[RootDataSize];
1002 // 0: Leaves in root.
1003 // 1: Root points to leaf.
1004 // 2: root->branch->leaf ...
1007 // Number of entries in the root node.
1010 // Allocator used for creating external nodes.
1011 Allocator &allocator;
1013 /// dataAs - Represent data as a node type without breaking aliasing rules.
1014 template <typename T>
1024 const RootLeaf &rootLeaf() const {
1025 assert(!branched() && "Cannot acces leaf data in branched root");
1026 return dataAs<RootLeaf>();
1028 RootLeaf &rootLeaf() {
1029 assert(!branched() && "Cannot acces leaf data in branched root");
1030 return dataAs<RootLeaf>();
1032 RootBranchData &rootBranchData() const {
1033 assert(branched() && "Cannot access branch data in non-branched root");
1034 return dataAs<RootBranchData>();
1036 RootBranchData &rootBranchData() {
1037 assert(branched() && "Cannot access branch data in non-branched root");
1038 return dataAs<RootBranchData>();
1040 const RootBranch &rootBranch() const { return rootBranchData().node; }
1041 RootBranch &rootBranch() { return rootBranchData().node; }
1042 KeyT rootBranchStart() const { return rootBranchData().start; }
1043 KeyT &rootBranchStart() { return rootBranchData().start; }
1046 return new(allocator.template Allocate<Leaf>()) Leaf();
1048 void deleteLeaf(Leaf *P) {
1050 allocator.Deallocate(P);
1053 Branch *allocBranch() {
1054 return new(allocator.template Allocate<Branch>()) Branch();
1056 void deleteBranch(Branch *P) {
1058 allocator.Deallocate(P);
1062 IdxPair branchRoot(unsigned Position);
1063 IdxPair splitRoot(unsigned Position);
1065 void switchRootToBranch() {
1066 rootLeaf().~RootLeaf();
1068 new (&rootBranchData()) RootBranchData();
1071 void switchRootToLeaf() {
1072 rootBranchData().~RootBranchData();
1074 new(&rootLeaf()) RootLeaf();
1077 bool branched() const { return height > 0; }
1079 ValT treeSafeLookup(KeyT x, ValT NotFound) const;
1080 void visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef,
1082 void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level);
1085 explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) {
1086 assert((uintptr_t(data) & (alignOf<RootLeaf>() - 1)) == 0 &&
1087 "Insufficient alignment");
1088 new(&rootLeaf()) RootLeaf();
1093 rootLeaf().~RootLeaf();
1096 /// empty - Return true when no intervals are mapped.
1097 bool empty() const {
1098 return rootSize == 0;
1101 /// start - Return the smallest mapped key in a non-empty map.
1102 KeyT start() const {
1103 assert(!empty() && "Empty IntervalMap has no start");
1104 return !branched() ? rootLeaf().start(0) : rootBranchStart();
1107 /// stop - Return the largest mapped key in a non-empty map.
1109 assert(!empty() && "Empty IntervalMap has no stop");
1110 return !branched() ? rootLeaf().stop(rootSize - 1) :
1111 rootBranch().stop(rootSize - 1);
1114 /// lookup - Return the mapped value at x or NotFound.
1115 ValT lookup(KeyT x, ValT NotFound = ValT()) const {
1116 if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x))
1118 return branched() ? treeSafeLookup(x, NotFound) :
1119 rootLeaf().safeLookup(x, NotFound);
1122 /// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
1123 /// It is assumed that no key in the interval is mapped to another value, but
1124 /// overlapping intervals already mapped to y will be coalesced.
1125 void insert(KeyT a, KeyT b, ValT y) {
1126 find(a).insert(a, b, y);
1129 /// clear - Remove all entries.
1132 class const_iterator;
1134 friend class const_iterator;
1135 friend class iterator;
1137 const_iterator begin() const {
1149 const_iterator end() const {
1161 /// find - Return an iterator pointing to the first interval ending at or
1162 /// after x, or end().
1163 const_iterator find(KeyT x) const {
1169 iterator find(KeyT x) {
1178 void dumpNode(IntervalMapImpl::NodeRef Node, unsigned Height);
1182 /// treeSafeLookup - Return the mapped value at x or NotFound, assuming a
1184 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1185 ValT IntervalMap<KeyT, ValT, N, Traits>::
1186 treeSafeLookup(KeyT x, ValT NotFound) const {
1187 assert(branched() && "treeLookup assumes a branched root");
1189 IntervalMapImpl::NodeRef NR = rootBranch().safeLookup(x);
1190 for (unsigned h = height-1; h; --h)
1191 NR = NR.get<Branch>().safeLookup(x);
1192 return NR.get<Leaf>().safeLookup(x, NotFound);
1196 // branchRoot - Switch from a leaf root to a branched root.
1197 // Return the new (root offset, node offset) corresponding to Position.
1198 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1199 IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
1200 branchRoot(unsigned Position) {
1201 using namespace IntervalMapImpl;
1202 // How many external leaf nodes to hold RootLeaf+1?
1203 const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1;
1205 // Compute element distribution among new nodes.
1206 unsigned size[Nodes];
1207 IdxPair NewOffset(0, Position);
1209 // Is is very common for the root node to be smaller than external nodes.
1213 NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, size,
1216 // Allocate new nodes.
1218 NodeRef node[Nodes];
1219 for (unsigned n = 0; n != Nodes; ++n) {
1220 node[n] = NodeRef(allocLeaf(), size[n]);
1221 node[n].template get<Leaf>().copy(rootLeaf(), pos, 0, size[n]);
1225 // Destroy the old leaf node, construct branch node instead.
1226 switchRootToBranch();
1227 for (unsigned n = 0; n != Nodes; ++n) {
1228 rootBranch().stop(n) = node[n].template get<Leaf>().stop(size[n]-1);
1229 rootBranch().subtree(n) = node[n];
1231 rootBranchStart() = node[0].template get<Leaf>().start(0);
1236 // splitRoot - Split the current BranchRoot into multiple Branch nodes.
1237 // Return the new (root offset, node offset) corresponding to Position.
1238 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1239 IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
1240 splitRoot(unsigned Position) {
1241 using namespace IntervalMapImpl;
1242 // How many external leaf nodes to hold RootBranch+1?
1243 const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1;
1245 // Compute element distribution among new nodes.
1246 unsigned Size[Nodes];
1247 IdxPair NewOffset(0, Position);
1249 // Is is very common for the root node to be smaller than external nodes.
1253 NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, Size,
1256 // Allocate new nodes.
1258 NodeRef Node[Nodes];
1259 for (unsigned n = 0; n != Nodes; ++n) {
1260 Node[n] = NodeRef(allocBranch(), Size[n]);
1261 Node[n].template get<Branch>().copy(rootBranch(), Pos, 0, Size[n]);
1265 for (unsigned n = 0; n != Nodes; ++n) {
1266 rootBranch().stop(n) = Node[n].template get<Branch>().stop(Size[n]-1);
1267 rootBranch().subtree(n) = Node[n];
1274 /// visitNodes - Visit each external node.
1275 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1276 void IntervalMap<KeyT, ValT, N, Traits>::
1277 visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, unsigned Height)) {
1280 SmallVector<IntervalMapImpl::NodeRef, 4> Refs, NextRefs;
1282 // Collect level 0 nodes from the root.
1283 for (unsigned i = 0; i != rootSize; ++i)
1284 Refs.push_back(rootBranch().subtree(i));
1286 // Visit all branch nodes.
1287 for (unsigned h = height - 1; h; --h) {
1288 for (unsigned i = 0, e = Refs.size(); i != e; ++i) {
1289 for (unsigned j = 0, s = Refs[i].size(); j != s; ++j)
1290 NextRefs.push_back(Refs[i].subtree(j));
1291 (this->*f)(Refs[i], h);
1294 Refs.swap(NextRefs);
1297 // Visit all leaf nodes.
1298 for (unsigned i = 0, e = Refs.size(); i != e; ++i)
1299 (this->*f)(Refs[i], 0);
1302 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1303 void IntervalMap<KeyT, ValT, N, Traits>::
1304 deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) {
1306 deleteBranch(&Node.get<Branch>());
1308 deleteLeaf(&Node.get<Leaf>());
1311 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1312 void IntervalMap<KeyT, ValT, N, Traits>::
1315 visitNodes(&IntervalMap::deleteNode);
1322 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1323 void IntervalMap<KeyT, ValT, N, Traits>::
1324 dumpNode(IntervalMapImpl::NodeRef Node, unsigned Height) {
1326 Node.get<Branch>().dump(*OS, Node.size());
1328 Node.get<Leaf>().dump(*OS, Node.size());
1331 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1332 void IntervalMap<KeyT, ValT, N, Traits>::
1335 raw_fd_ostream ofs("tree.dot", errors);
1337 ofs << "digraph {\n";
1339 rootBranch().dump(ofs, rootSize);
1341 rootLeaf().dump(ofs, rootSize);
1342 visitNodes(&IntervalMap::dumpNode);
1347 //===----------------------------------------------------------------------===//
1348 //--- const_iterator ----//
1349 //===----------------------------------------------------------------------===//
1351 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1352 class IntervalMap<KeyT, ValT, N, Traits>::const_iterator :
1353 public std::iterator<std::bidirectional_iterator_tag, ValT> {
1355 friend class IntervalMap;
1357 // The map referred to.
1360 // We store a full path from the root to the current position.
1361 // The path may be partially filled, but never between iterator calls.
1362 IntervalMapImpl::Path path;
1364 explicit const_iterator(IntervalMap &map) : map(&map) {}
1366 bool branched() const {
1367 assert(map && "Invalid iterator");
1368 return map->branched();
1371 void setRoot(unsigned Offset) {
1373 path.setRoot(&map->rootBranch(), map->rootSize, Offset);
1375 path.setRoot(&map->rootLeaf(), map->rootSize, Offset);
1378 void pathFillFind(KeyT x);
1379 void treeFind(KeyT x);
1382 /// valid - Return true if the current position is valid, false for end().
1383 bool valid() const { return path.valid(); }
1385 /// start - Return the beginning of the current interval.
1386 const KeyT &start() const {
1387 assert(valid() && "Cannot access invalid iterator");
1388 return branched() ? path.leaf<Leaf>().start(path.leafOffset()) :
1389 path.leaf<RootLeaf>().start(path.leafOffset());
1392 /// stop - Return the end of the current interval.
1393 const KeyT &stop() const {
1394 assert(valid() && "Cannot access invalid iterator");
1395 return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) :
1396 path.leaf<RootLeaf>().stop(path.leafOffset());
1399 /// value - Return the mapped value at the current interval.
1400 const ValT &value() const {
1401 assert(valid() && "Cannot access invalid iterator");
1402 return branched() ? path.leaf<Leaf>().value(path.leafOffset()) :
1403 path.leaf<RootLeaf>().value(path.leafOffset());
1406 const ValT &operator*() const {
1410 bool operator==(const const_iterator &RHS) const {
1411 assert(map == RHS.map && "Cannot compare iterators from different maps");
1413 return !RHS.valid();
1414 if (path.leafOffset() != RHS.path.leafOffset())
1416 return &path.template leaf<Leaf>() == &RHS.path.template leaf<Leaf>();
1419 bool operator!=(const const_iterator &RHS) const {
1420 return !operator==(RHS);
1423 /// goToBegin - Move to the first interval in map.
1427 path.fillLeft(map->height);
1430 /// goToEnd - Move beyond the last interval in map.
1432 setRoot(map->rootSize);
1435 /// preincrement - move to the next interval.
1436 const_iterator &operator++() {
1437 assert(valid() && "Cannot increment end()");
1438 if (++path.leafOffset() == path.leafSize() && branched())
1439 path.moveRight(map->height);
1443 /// postincrement - Dont do that!
1444 const_iterator operator++(int) {
1445 const_iterator tmp = *this;
1450 /// predecrement - move to the previous interval.
1451 const_iterator &operator--() {
1452 if (path.leafOffset() && (valid() || !branched()))
1453 --path.leafOffset();
1455 path.moveLeft(map->height);
1459 /// postdecrement - Dont do that!
1460 const_iterator operator--(int) {
1461 const_iterator tmp = *this;
1466 /// find - Move to the first interval with stop >= x, or end().
1467 /// This is a full search from the root, the current position is ignored.
1472 setRoot(map->rootLeaf().findFrom(0, map->rootSize, x));
1475 /// advanceTo - Move to the first interval with stop >= x, or end().
1476 /// The search is started from the current position, and no earlier positions
1477 /// can be found. This is much faster than find() for small moves.
1478 void advanceTo(KeyT x) {
1483 map->rootLeaf().findFrom(path.leafOffset(), map->rootSize, x);
1488 // pathFillFind - Complete path by searching for x.
1489 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1490 void IntervalMap<KeyT, ValT, N, Traits>::
1491 const_iterator::pathFillFind(KeyT x) {
1492 IntervalMapImpl::NodeRef NR = path.subtree(path.height());
1493 for (unsigned i = map->height - path.height() - 1; i; --i) {
1494 unsigned p = NR.get<Branch>().safeFind(0, x);
1498 path.push(NR, NR.get<Leaf>().safeFind(0, x));
1501 // treeFind - Find in a branched tree.
1502 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1503 void IntervalMap<KeyT, ValT, N, Traits>::
1504 const_iterator::treeFind(KeyT x) {
1505 setRoot(map->rootBranch().findFrom(0, map->rootSize, x));
1511 //===----------------------------------------------------------------------===//
1512 //--- iterator ----//
1513 //===----------------------------------------------------------------------===//
1515 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1516 class IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator {
1517 friend class IntervalMap;
1518 typedef IntervalMapImpl::IdxPair IdxPair;
1520 explicit iterator(IntervalMap &map) : const_iterator(map) {}
1522 void setNodeStop(unsigned Level, KeyT Stop);
1523 bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop);
1524 template <typename NodeT> bool overflow(unsigned Level);
1525 void treeInsert(KeyT a, KeyT b, ValT y);
1528 /// insert - Insert mapping [a;b] -> y before the current position.
1529 void insert(KeyT a, KeyT b, ValT y);
1533 /// setNodeStop - Update the stop key of the current node at level and above.
1534 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1535 void IntervalMap<KeyT, ValT, N, Traits>::
1536 iterator::setNodeStop(unsigned Level, KeyT Stop) {
1537 // There are no references to the root node, so nothing to update.
1540 IntervalMapImpl::Path &P = this->path;
1541 // Update nodes pointing to the current node.
1543 P.node<Branch>(Level).stop(P.offset(Level)) = Stop;
1544 if (!P.atLastBranch(Level))
1547 // Update root separately since it has a different layout.
1548 P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop;
1551 /// insertNode - insert a node before the current path at level.
1552 /// Leave the current path pointing at the new node.
1553 /// @param Level path index of the node to be inserted.
1554 /// @param Node The node to be inserted.
1555 /// @param Stop The last index in the new node.
1556 /// @return True if the tree height was increased.
1557 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1558 bool IntervalMap<KeyT, ValT, N, Traits>::
1559 iterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) {
1560 assert(Level && "Cannot insert next to the root");
1561 bool SplitRoot = false;
1562 IntervalMap &IM = *this->map;
1563 IntervalMapImpl::Path &P = this->path;
1566 // Insert into the root branch node.
1567 if (IM.rootSize < RootBranch::Capacity) {
1568 IM.rootBranch().insert(P.offset(0), IM.rootSize, Node, Stop);
1569 P.setSize(0, ++IM.rootSize);
1574 // We need to split the root while keeping our position.
1576 IdxPair Offset = IM.splitRoot(P.offset(0));
1577 P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset);
1579 // Fall through to insert at the new higher level.
1583 // When inserting before end(), make sure we have a valid path.
1584 P.legalizeForInsert(--Level);
1586 // Insert into the branch node at Level-1.
1587 if (P.size(Level) == Branch::Capacity) {
1588 // Branch node is full, handle handle the overflow.
1589 assert(!SplitRoot && "Cannot overflow after splitting the root");
1590 SplitRoot = overflow<Branch>(Level);
1593 P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop);
1594 P.setSize(Level, P.size(Level) + 1);
1595 if (P.atLastBranch(Level))
1596 setNodeStop(Level, Stop);
1602 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1603 void IntervalMap<KeyT, ValT, N, Traits>::
1604 iterator::insert(KeyT a, KeyT b, ValT y) {
1605 if (this->branched())
1606 return treeInsert(a, b, y);
1607 IntervalMap &IM = *this->map;
1608 IntervalMapImpl::Path &P = this->path;
1610 // Try simple root leaf insert.
1611 IdxPair IP = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y);
1613 // Was the root node insert successful?
1614 if (IP.second <= RootLeaf::Capacity) {
1615 P.leafOffset() = IP.first;
1616 P.setSize(0, IM.rootSize = IP.second);
1620 // Root leaf node is full, we must branch.
1621 IdxPair Offset = IM.branchRoot(P.leafOffset());
1622 P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset);
1624 // Now it fits in the new leaf.
1625 treeInsert(a, b, y);
1629 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1630 void IntervalMap<KeyT, ValT, N, Traits>::
1631 iterator::treeInsert(KeyT a, KeyT b, ValT y) {
1632 IntervalMap &IM = *this->map;
1633 IntervalMapImpl::Path &P = this->path;
1635 P.legalizeForInsert(IM.height);
1636 IdxPair IP = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y);
1638 // Leaf insertion unsuccessful? Overflow and try again.
1639 if (IP.second > Leaf::Capacity) {
1640 overflow<Leaf>(IM.height);
1641 IP = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y);
1642 assert(IP.second <= Leaf::Capacity && "overflow() didn't make room");
1645 // Inserted, update offset and leaf size.
1646 P.leafOffset() = IP.first;
1647 P.setSize(IM.height, IP.second);
1649 // Insert was the last node entry, update stops.
1650 if (IP.first == IP.second - 1)
1651 setNodeStop(IM.height, P.leaf<Leaf>().stop(IP.first));
1653 // FIXME: Handle cross-node coalescing.
1656 /// overflow - Distribute entries of the current node evenly among
1657 /// its siblings and ensure that the current node is not full.
1658 /// This may require allocating a new node.
1659 /// @param NodeT The type of node at Level (Leaf or Branch).
1660 /// @param Level path index of the overflowing node.
1661 /// @return True when the tree height was changed.
1662 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1663 template <typename NodeT>
1664 bool IntervalMap<KeyT, ValT, N, Traits>::
1665 iterator::overflow(unsigned Level) {
1666 using namespace IntervalMapImpl;
1667 Path &P = this->path;
1668 unsigned CurSize[4];
1671 unsigned Elements = 0;
1672 unsigned Offset = P.offset(Level);
1674 // Do we have a left sibling?
1675 NodeRef LeftSib = P.getLeftSibling(Level);
1677 Offset += Elements = CurSize[Nodes] = LeftSib.size();
1678 Node[Nodes++] = &LeftSib.get<NodeT>();
1682 Elements += CurSize[Nodes] = P.size(Level);
1683 Node[Nodes++] = &P.node<NodeT>(Level);
1685 // Do we have a right sibling?
1686 NodeRef RightSib = P.getRightSibling(Level);
1688 Offset += Elements = CurSize[Nodes] = RightSib.size();
1689 Node[Nodes++] = &RightSib.get<NodeT>();
1692 // Do we need to allocate a new node?
1693 unsigned NewNode = 0;
1694 if (Elements + 1 > Nodes * NodeT::Capacity) {
1695 // Insert NewNode at the penultimate position, or after a single node.
1696 NewNode = Nodes == 1 ? 1 : Nodes - 1;
1697 CurSize[Nodes] = CurSize[NewNode];
1698 Node[Nodes] = Node[NewNode];
1699 CurSize[NewNode] = 0;
1700 Node[NewNode] = new(this->map->allocator.template Allocate<NodeT>())NodeT();
1704 // Compute the new element distribution.
1705 unsigned NewSize[4];
1706 IdxPair NewOffset = distribute(Nodes, Elements, NodeT::Capacity,
1707 CurSize, NewSize, Offset, true);
1708 adjustSiblingSizes(Node, Nodes, CurSize, NewSize);
1710 // Move current location to the leftmost node.
1714 // Elements have been rearranged, now update node sizes and stops.
1715 bool SplitRoot = false;
1718 KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1);
1719 if (NewNode && Pos == NewNode) {
1720 SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop);
1723 P.setSize(Level, NewSize[Pos]);
1724 setNodeStop(Level, Stop);
1726 if (Pos + 1 == Nodes)
1732 // Where was I? Find NewOffset.
1733 while(Pos != NewOffset.first) {
1737 P.offset(Level) = NewOffset.second;