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"
108 // FIXME: Remove debugging code.
109 #include "llvm/Support/raw_ostream.h"
114 //===----------------------------------------------------------------------===//
115 //--- Key traits ---//
116 //===----------------------------------------------------------------------===//
118 // The IntervalMap works with closed or half-open intervals.
119 // Adjacent intervals that map to the same value are coalesced.
121 // The IntervalMapInfo traits class is used to determine if a key is contained
122 // in an interval, and if two intervals are adjacent so they can be coalesced.
123 // The provided implementation works for closed integer intervals, other keys
124 // probably need a specialized version.
126 // The point x is contained in [a;b] when !startLess(x, a) && !stopLess(b, x).
128 // It is assumed that (a;b] half-open intervals are not used, only [a;b) is
129 // allowed. This is so that stopLess(a, b) can be used to determine if two
130 // intervals overlap.
132 //===----------------------------------------------------------------------===//
134 template <typename T>
135 struct IntervalMapInfo {
137 /// startLess - Return true if x is not in [a;b].
138 /// This is x < a both for closed intervals and for [a;b) half-open intervals.
139 static inline bool startLess(const T &x, const T &a) {
143 /// stopLess - Return true if x is not in [a;b].
144 /// This is b < x for a closed interval, b <= x for [a;b) half-open intervals.
145 static inline bool stopLess(const T &b, const T &x) {
149 /// adjacent - Return true when the intervals [x;a] and [b;y] can coalesce.
150 /// This is a+1 == b for closed intervals, a == b for half-open intervals.
151 static inline bool adjacent(const T &a, const T &b) {
157 /// IntervalMapImpl - Namespace used for IntervalMap implementation details.
158 /// It should be considered private to the implementation.
159 namespace IntervalMapImpl {
161 // Forward declarations.
162 template <typename, typename, unsigned, typename> class LeafNode;
163 template <typename, typename, unsigned, typename> class BranchNode;
165 typedef std::pair<unsigned,unsigned> IdxPair;
168 //===----------------------------------------------------------------------===//
169 //--- IntervalMapImpl::NodeBase ---//
170 //===----------------------------------------------------------------------===//
172 // Both leaf and branch nodes store vectors of pairs.
173 // Leaves store ((KeyT, KeyT), ValT) pairs, branches use (NodeRef, KeyT).
175 // Keys and values are stored in separate arrays to avoid padding caused by
176 // different object alignments. This also helps improve locality of reference
177 // when searching the keys.
179 // The nodes don't know how many elements they contain - that information is
180 // stored elsewhere. Omitting the size field prevents padding and allows a node
181 // to fill the allocated cache lines completely.
183 // These are typical key and value sizes, the node branching factor (N), and
184 // wasted space when nodes are sized to fit in three cache lines (192 bytes):
186 // T1 T2 N Waste Used by
187 // 4 4 24 0 Branch<4> (32-bit pointers)
188 // 8 4 16 0 Leaf<4,4>, Branch<4>
189 // 8 8 12 0 Leaf<4,8>, Branch<8>
190 // 16 4 9 12 Leaf<8,4>
191 // 16 8 8 0 Leaf<8,8>
193 //===----------------------------------------------------------------------===//
195 template <typename T1, typename T2, unsigned N>
198 enum { Capacity = N };
203 /// copy - Copy elements from another node.
204 /// @param Other Node elements are copied from.
205 /// @param i Beginning of the source range in other.
206 /// @param j Beginning of the destination range in this.
207 /// @param Count Number of elements to copy.
208 template <unsigned M>
209 void copy(const NodeBase<T1, T2, M> &Other, unsigned i,
210 unsigned j, unsigned Count) {
211 assert(i + Count <= M && "Invalid source range");
212 assert(j + Count <= N && "Invalid dest range");
213 for (unsigned e = i + Count; i != e; ++i, ++j) {
214 first[j] = Other.first[i];
215 second[j] = Other.second[i];
219 /// moveLeft - Move elements to the left.
220 /// @param i Beginning of the source range.
221 /// @param j Beginning of the destination range.
222 /// @param Count Number of elements to copy.
223 void moveLeft(unsigned i, unsigned j, unsigned Count) {
224 assert(j <= i && "Use moveRight shift elements right");
225 copy(*this, i, j, Count);
228 /// moveRight - Move elements to the right.
229 /// @param i Beginning of the source range.
230 /// @param j Beginning of the destination range.
231 /// @param Count Number of elements to copy.
232 void moveRight(unsigned i, unsigned j, unsigned Count) {
233 assert(i <= j && "Use moveLeft shift elements left");
234 assert(j + Count <= N && "Invalid range");
236 first[j + Count] = first[i + Count];
237 second[j + Count] = second[i + Count];
241 /// erase - Erase elements [i;j).
242 /// @param i Beginning of the range to erase.
243 /// @param j End of the range. (Exclusive).
244 /// @param Size Number of elements in node.
245 void erase(unsigned i, unsigned j, unsigned Size) {
246 moveLeft(j, i, Size - j);
249 /// erase - Erase element at i.
250 /// @param i Index of element to erase.
251 /// @param Size Number of elements in node.
252 void erase(unsigned i, unsigned Size) {
256 /// shift - Shift elements [i;size) 1 position to the right.
257 /// @param i Beginning of the range to move.
258 /// @param Size Number of elements in node.
259 void shift(unsigned i, unsigned Size) {
260 moveRight(i, i + 1, Size - i);
263 /// transferToLeftSib - Transfer elements to a left sibling node.
264 /// @param Size Number of elements in this.
265 /// @param Sib Left sibling node.
266 /// @param SSize Number of elements in sib.
267 /// @param Count Number of elements to transfer.
268 void transferToLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize,
270 Sib.copy(*this, 0, SSize, Count);
271 erase(0, Count, Size);
274 /// transferToRightSib - Transfer elements to a right sibling node.
275 /// @param Size Number of elements in this.
276 /// @param Sib Right sibling node.
277 /// @param SSize Number of elements in sib.
278 /// @param Count Number of elements to transfer.
279 void transferToRightSib(unsigned Size, NodeBase &Sib, unsigned SSize,
281 Sib.moveRight(0, Count, SSize);
282 Sib.copy(*this, Size-Count, 0, Count);
285 /// adjustFromLeftSib - Adjust the number if elements in this node by moving
286 /// elements to or from a left sibling node.
287 /// @param Size Number of elements in this.
288 /// @param Sib Right sibling node.
289 /// @param SSize Number of elements in sib.
290 /// @param Add The number of elements to add to this node, possibly < 0.
291 /// @return Number of elements added to this node, possibly negative.
292 int adjustFromLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add) {
294 // We want to grow, copy from sib.
295 unsigned Count = std::min(std::min(unsigned(Add), SSize), N - Size);
296 Sib.transferToRightSib(SSize, *this, Size, Count);
299 // We want to shrink, copy to sib.
300 unsigned Count = std::min(std::min(unsigned(-Add), Size), N - SSize);
301 transferToLeftSib(Size, Sib, SSize, Count);
307 /// IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes.
308 /// @param Node Array of pointers to sibling nodes.
309 /// @param Nodes Number of nodes.
310 /// @param CurSize Array of current node sizes, will be overwritten.
311 /// @param NewSize Array of desired node sizes.
312 template <typename NodeT>
313 void adjustSiblingSizes(NodeT *Node[], unsigned Nodes,
314 unsigned CurSize[], const unsigned NewSize[]) {
315 // Move elements right.
316 for (int n = Nodes - 1; n; --n) {
317 if (CurSize[n] == NewSize[n])
319 for (int m = n - 1; m != -1; --m) {
320 int d = Node[n]->adjustFromLeftSib(CurSize[n], *Node[m], CurSize[m],
321 NewSize[n] - CurSize[n]);
324 // Keep going if the current node was exhausted.
325 if (CurSize[n] >= NewSize[n])
333 // Move elements left.
334 for (unsigned n = 0; n != Nodes - 1; ++n) {
335 if (CurSize[n] == NewSize[n])
337 for (unsigned m = n + 1; m != Nodes; ++m) {
338 int d = Node[m]->adjustFromLeftSib(CurSize[m], *Node[n], CurSize[n],
339 CurSize[n] - NewSize[n]);
342 // Keep going if the current node was exhausted.
343 if (CurSize[n] >= NewSize[n])
349 for (unsigned n = 0; n != Nodes; n++)
350 assert(CurSize[n] == NewSize[n] && "Insufficient element shuffle");
354 /// IntervalMapImpl::distribute - Compute a new distribution of node elements
355 /// after an overflow or underflow. Reserve space for a new element at Position,
356 /// and compute the node that will hold Position after redistributing node
359 /// It is required that
361 /// Elements == sum(CurSize), and
362 /// Elements + Grow <= Nodes * Capacity.
364 /// NewSize[] will be filled in such that:
366 /// sum(NewSize) == Elements, and
367 /// NewSize[i] <= Capacity.
369 /// The returned index is the node where Position will go, so:
371 /// sum(NewSize[0..idx-1]) <= Position
372 /// sum(NewSize[0..idx]) >= Position
374 /// The last equality, sum(NewSize[0..idx]) == Position, can only happen when
375 /// Grow is set and NewSize[idx] == Capacity-1. The index points to the node
376 /// before the one holding the Position'th element where there is room for an
379 /// @param Nodes The number of nodes.
380 /// @param Elements Total elements in all nodes.
381 /// @param Capacity The capacity of each node.
382 /// @param CurSize Array[Nodes] of current node sizes, or NULL.
383 /// @param NewSize Array[Nodes] to receive the new node sizes.
384 /// @param Position Insert position.
385 /// @param Grow Reserve space for a new element at Position.
386 /// @return (node, offset) for Position.
387 IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,
388 const unsigned *CurSize, unsigned NewSize[],
389 unsigned Position, bool Grow);
392 //===----------------------------------------------------------------------===//
393 //--- IntervalMapImpl::NodeSizer ---//
394 //===----------------------------------------------------------------------===//
396 // Compute node sizes from key and value types.
398 // The branching factors are chosen to make nodes fit in three cache lines.
399 // This may not be possible if keys or values are very large. Such large objects
400 // are handled correctly, but a std::map would probably give better performance.
402 //===----------------------------------------------------------------------===//
405 // Cache line size. Most architectures have 32 or 64 byte cache lines.
406 // We use 64 bytes here because it provides good branching factors.
408 CacheLineBytes = 1 << Log2CacheLine,
409 DesiredNodeBytes = 3 * CacheLineBytes
412 template <typename KeyT, typename ValT>
415 // Compute the leaf node branching factor that makes a node fit in three
416 // cache lines. The branching factor must be at least 3, or some B+-tree
417 // balancing algorithms won't work.
418 // LeafSize can't be larger than CacheLineBytes. This is required by the
419 // PointerIntPair used by NodeRef.
420 DesiredLeafSize = DesiredNodeBytes /
421 static_cast<unsigned>(2*sizeof(KeyT)+sizeof(ValT)),
423 LeafSize = DesiredLeafSize > MinLeafSize ? DesiredLeafSize : MinLeafSize
426 typedef NodeBase<std::pair<KeyT, KeyT>, ValT, LeafSize> LeafBase;
429 // Now that we have the leaf branching factor, compute the actual allocation
430 // unit size by rounding up to a whole number of cache lines.
431 AllocBytes = (sizeof(LeafBase) + CacheLineBytes-1) & ~(CacheLineBytes-1),
433 // Determine the branching factor for branch nodes.
434 BranchSize = AllocBytes /
435 static_cast<unsigned>(sizeof(KeyT) + sizeof(void*))
438 /// Allocator - The recycling allocator used for both branch and leaf nodes.
439 /// This typedef is very likely to be identical for all IntervalMaps with
440 /// reasonably sized entries, so the same allocator can be shared among
441 /// different kinds of maps.
442 typedef RecyclingAllocator<BumpPtrAllocator, char,
443 AllocBytes, CacheLineBytes> Allocator;
448 //===----------------------------------------------------------------------===//
449 //--- IntervalMapImpl::NodeRef ---//
450 //===----------------------------------------------------------------------===//
452 // B+-tree nodes can be leaves or branches, so we need a polymorphic node
453 // pointer that can point to both kinds.
455 // All nodes are cache line aligned and the low 6 bits of a node pointer are
456 // always 0. These bits are used to store the number of elements in the
457 // referenced node. Besides saving space, placing node sizes in the parents
458 // allow tree balancing algorithms to run without faulting cache lines for nodes
459 // that may not need to be modified.
461 // A NodeRef doesn't know whether it references a leaf node or a branch node.
462 // It is the responsibility of the caller to use the correct types.
464 // Nodes are never supposed to be empty, and it is invalid to store a node size
465 // of 0 in a NodeRef. The valid range of sizes is 1-64.
467 //===----------------------------------------------------------------------===//
470 struct CacheAlignedPointerTraits {
471 static inline void *getAsVoidPointer(void *P) { return P; }
472 static inline void *getFromVoidPointer(void *P) { return P; }
473 enum { NumLowBitsAvailable = Log2CacheLine };
475 PointerIntPair<void*, Log2CacheLine, unsigned, CacheAlignedPointerTraits> pip;
478 /// NodeRef - Create a null ref.
481 /// operator bool - Detect a null ref.
482 operator bool() const { return pip.getOpaqueValue(); }
484 /// NodeRef - Create a reference to the node p with n elements.
485 template <typename NodeT>
486 NodeRef(NodeT *p, unsigned n) : pip(p, n - 1) {
487 assert(n <= NodeT::Capacity && "Size too big for node");
490 /// size - Return the number of elements in the referenced node.
491 unsigned size() const { return pip.getInt() + 1; }
493 /// setSize - Update the node size.
494 void setSize(unsigned n) { pip.setInt(n - 1); }
496 /// subtree - Access the i'th subtree reference in a branch node.
497 /// This depends on branch nodes storing the NodeRef array as their first
499 NodeRef &subtree(unsigned i) const {
500 return reinterpret_cast<NodeRef*>(pip.getPointer())[i];
503 /// get - Dereference as a NodeT reference.
504 template <typename NodeT>
506 return *reinterpret_cast<NodeT*>(pip.getPointer());
509 bool operator==(const NodeRef &RHS) const {
512 assert(pip.getPointer() != RHS.pip.getPointer() && "Inconsistent NodeRefs");
516 bool operator!=(const NodeRef &RHS) const {
517 return !operator==(RHS);
521 //===----------------------------------------------------------------------===//
522 //--- IntervalMapImpl::LeafNode ---//
523 //===----------------------------------------------------------------------===//
525 // Leaf nodes store up to N disjoint intervals with corresponding values.
527 // The intervals are kept sorted and fully coalesced so there are no adjacent
528 // intervals mapping to the same value.
530 // These constraints are always satisfied:
532 // - Traits::stopLess(start(i), stop(i)) - Non-empty, sane intervals.
534 // - Traits::stopLess(stop(i), start(i + 1) - Sorted.
536 // - value(i) != value(i + 1) || !Traits::adjacent(stop(i), start(i + 1))
537 // - Fully coalesced.
539 //===----------------------------------------------------------------------===//
541 template <typename KeyT, typename ValT, unsigned N, typename Traits>
542 class LeafNode : public NodeBase<std::pair<KeyT, KeyT>, ValT, N> {
544 const KeyT &start(unsigned i) const { return this->first[i].first; }
545 const KeyT &stop(unsigned i) const { return this->first[i].second; }
546 const ValT &value(unsigned i) const { return this->second[i]; }
548 KeyT &start(unsigned i) { return this->first[i].first; }
549 KeyT &stop(unsigned i) { return this->first[i].second; }
550 ValT &value(unsigned i) { return this->second[i]; }
552 /// findFrom - Find the first interval after i that may contain x.
553 /// @param i Starting index for the search.
554 /// @param Size Number of elements in node.
555 /// @param x Key to search for.
556 /// @return First index with !stopLess(key[i].stop, x), or size.
557 /// This is the first interval that can possibly contain x.
558 unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
559 assert(i <= Size && Size <= N && "Bad indices");
560 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
561 "Index is past the needed point");
562 while (i != Size && Traits::stopLess(stop(i), x)) ++i;
566 /// safeFind - Find an interval that is known to exist. This is the same as
567 /// findFrom except is it assumed that x is at least within range of the last
569 /// @param i Starting index for the search.
570 /// @param x Key to search for.
571 /// @return First index with !stopLess(key[i].stop, x), never size.
572 /// This is the first interval that can possibly contain x.
573 unsigned safeFind(unsigned i, KeyT x) const {
574 assert(i < N && "Bad index");
575 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
576 "Index is past the needed point");
577 while (Traits::stopLess(stop(i), x)) ++i;
578 assert(i < N && "Unsafe intervals");
582 /// safeLookup - Lookup mapped value for a safe key.
583 /// It is assumed that x is within range of the last entry.
584 /// @param x Key to search for.
585 /// @param NotFound Value to return if x is not in any interval.
586 /// @return The mapped value at x or NotFound.
587 ValT safeLookup(KeyT x, ValT NotFound) const {
588 unsigned i = safeFind(0, x);
589 return Traits::startLess(x, start(i)) ? NotFound : value(i);
592 unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y);
595 void dump(raw_ostream &OS, unsigned Size) {
596 OS << " N" << this << " [shape=record label=\"{ " << Size << '/' << N;
597 for (unsigned i = 0; i != Size; ++i)
598 OS << " | {" << start(i) << '-' << stop(i) << "|" << value(i) << '}';
605 /// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as
606 /// possible. This may cause the node to grow by 1, or it may cause the node
607 /// to shrink because of coalescing.
608 /// @param i Starting index = insertFrom(0, size, a)
609 /// @param Size Number of elements in node.
610 /// @param a Interval start.
611 /// @param b Interval stop.
612 /// @param y Value be mapped.
613 /// @return (insert position, new size), or (i, Capacity+1) on overflow.
614 template <typename KeyT, typename ValT, unsigned N, typename Traits>
615 unsigned LeafNode<KeyT, ValT, N, Traits>::
616 insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y) {
618 assert(i <= Size && Size <= N && "Invalid index");
619 assert(!Traits::stopLess(b, a) && "Invalid interval");
621 // Verify the findFrom invariant.
622 assert((i == 0 || Traits::stopLess(stop(i - 1), a)));
623 assert((i == Size || !Traits::stopLess(stop(i), a)));
624 assert((i == Size || Traits::stopLess(b, start(i))) && "Overlapping insert");
626 // Coalesce with previous interval.
627 if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a)) {
629 // Also coalesce with next interval?
630 if (i != Size && value(i) == y && Traits::adjacent(b, start(i))) {
631 stop(i - 1) = stop(i);
632 this->erase(i, Size);
643 // Add new interval at end.
651 // Try to coalesce with following interval.
652 if (value(i) == y && Traits::adjacent(b, start(i))) {
657 // We must insert before i. Detect overflow.
662 this->shift(i, Size);
670 //===----------------------------------------------------------------------===//
671 //--- IntervalMapImpl::BranchNode ---//
672 //===----------------------------------------------------------------------===//
674 // A branch node stores references to 1--N subtrees all of the same height.
676 // The key array in a branch node holds the rightmost stop key of each subtree.
677 // It is redundant to store the last stop key since it can be found in the
678 // parent node, but doing so makes tree balancing a lot simpler.
680 // It is unusual for a branch node to only have one subtree, but it can happen
681 // in the root node if it is smaller than the normal nodes.
683 // When all of the leaf nodes from all the subtrees are concatenated, they must
684 // satisfy the same constraints as a single leaf node. They must be sorted,
685 // sane, and fully coalesced.
687 //===----------------------------------------------------------------------===//
689 template <typename KeyT, typename ValT, unsigned N, typename Traits>
690 class BranchNode : public NodeBase<NodeRef, KeyT, N> {
692 const KeyT &stop(unsigned i) const { return this->second[i]; }
693 const NodeRef &subtree(unsigned i) const { return this->first[i]; }
695 KeyT &stop(unsigned i) { return this->second[i]; }
696 NodeRef &subtree(unsigned i) { return this->first[i]; }
698 /// findFrom - Find the first subtree after i that may contain x.
699 /// @param i Starting index for the search.
700 /// @param Size Number of elements in node.
701 /// @param x Key to search for.
702 /// @return First index with !stopLess(key[i], x), or size.
703 /// This is the first subtree that can possibly contain x.
704 unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
705 assert(i <= Size && Size <= N && "Bad indices");
706 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
707 "Index to findFrom is past the needed point");
708 while (i != Size && Traits::stopLess(stop(i), x)) ++i;
712 /// safeFind - Find a subtree that is known to exist. This is the same as
713 /// findFrom except is it assumed that x is in range.
714 /// @param i Starting index for the search.
715 /// @param x Key to search for.
716 /// @return First index with !stopLess(key[i], x), never size.
717 /// This is the first subtree that can possibly contain x.
718 unsigned safeFind(unsigned i, KeyT x) const {
719 assert(i < N && "Bad index");
720 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
721 "Index is past the needed point");
722 while (Traits::stopLess(stop(i), x)) ++i;
723 assert(i < N && "Unsafe intervals");
727 /// safeLookup - Get the subtree containing x, Assuming that x is in range.
728 /// @param x Key to search for.
729 /// @return Subtree containing x
730 NodeRef safeLookup(KeyT x) const {
731 return subtree(safeFind(0, x));
734 /// insert - Insert a new (subtree, stop) pair.
735 /// @param i Insert position, following entries will be shifted.
736 /// @param Size Number of elements in node.
737 /// @param Node Subtree to insert.
738 /// @param Stop Last key in subtree.
739 void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop) {
740 assert(Size < N && "branch node overflow");
741 assert(i <= Size && "Bad insert position");
742 this->shift(i, Size);
748 void dump(raw_ostream &OS, unsigned Size) {
749 OS << " N" << this << " [shape=record label=\"" << Size << '/' << N;
750 for (unsigned i = 0; i != Size; ++i)
751 OS << " | <s" << i << "> " << stop(i);
753 for (unsigned i = 0; i != Size; ++i)
754 OS << " N" << this << ":s" << i << " -> N"
755 << &subtree(i).template get<BranchNode>() << ";\n";
761 //===----------------------------------------------------------------------===//
762 //--- IntervalMapImpl::Path ---//
763 //===----------------------------------------------------------------------===//
765 // A Path is used by iterators to represent a position in a B+-tree, and the
766 // path to get there from the root.
768 // The Path class also constains the tree navigation code that doesn't have to
771 //===----------------------------------------------------------------------===//
774 /// Entry - Each step in the path is a node pointer and an offset into that
781 Entry(void *Node, unsigned Size, unsigned Offset)
782 : node(Node), size(Size), offset(Offset) {}
784 Entry(NodeRef Node, unsigned Offset)
785 : node(&Node.subtree(0)), size(Node.size()), offset(Offset) {}
787 NodeRef &subtree(unsigned i) const {
788 return reinterpret_cast<NodeRef*>(node)[i];
792 /// path - The path entries, path[0] is the root node, path.back() is a leaf.
793 SmallVector<Entry, 4> path;
797 template <typename NodeT> NodeT &node(unsigned Level) const {
798 return *reinterpret_cast<NodeT*>(path[Level].node);
800 unsigned size(unsigned Level) const { return path[Level].size; }
801 unsigned offset(unsigned Level) const { return path[Level].offset; }
802 unsigned &offset(unsigned Level) { return path[Level].offset; }
805 template <typename NodeT> NodeT &leaf() const {
806 return *reinterpret_cast<NodeT*>(path.back().node);
808 unsigned leafSize() const { return path.back().size; }
809 unsigned leafOffset() const { return path.back().offset; }
810 unsigned &leafOffset() { return path.back().offset; }
812 /// valid - Return true if path is at a valid node, not at end().
814 return !path.empty() && path.front().offset < path.front().size;
817 /// height - Return the height of the tree corresponding to this path.
818 /// This matches map->height in a full path.
819 unsigned height() const { return path.size() - 1; }
821 /// subtree - Get the subtree referenced from Level. When the path is
822 /// consistent, node(Level + 1) == subtree(Level).
823 /// @param Level 0..height-1. The leaves have no subtrees.
824 NodeRef &subtree(unsigned Level) const {
825 return path[Level].subtree(path[Level].offset);
828 /// reset - Reset cached information about node(Level) from subtree(Level -1).
829 /// @param Level 1..height. THe node to update after parent node changed.
830 void reset(unsigned Level) {
831 path[Level] = Entry(subtree(Level - 1), offset(Level));
834 /// push - Add entry to path.
835 /// @param Node Node to add, should be subtree(path.size()-1).
836 /// @param Offset Offset into Node.
837 void push(NodeRef Node, unsigned Offset) {
838 path.push_back(Entry(Node, Offset));
841 /// pop - Remove the last path entry.
846 /// setSize - Set the size of a node both in the path and in the tree.
847 /// @param Level 0..height. Note that setting the root size won't change
849 /// @param Size New node size.
850 void setSize(unsigned Level, unsigned Size) {
851 path[Level].size = Size;
853 subtree(Level - 1).setSize(Size);
856 /// setRoot - Clear the path and set a new root node.
857 /// @param Node New root node.
858 /// @param Size New root size.
859 /// @param Offset Offset into root node.
860 void setRoot(void *Node, unsigned Size, unsigned Offset) {
862 path.push_back(Entry(Node, Size, Offset));
865 /// replaceRoot - Replace the current root node with two new entries after the
866 /// tree height has increased.
867 /// @param Root The new root node.
868 /// @param Size Number of entries in the new root.
869 /// @param Offsets Offsets into the root and first branch nodes.
870 void replaceRoot(void *Root, unsigned Size, IdxPair Offsets);
872 /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
873 /// @param Level Get the sibling to node(Level).
874 /// @return Left sibling, or NodeRef().
875 NodeRef getLeftSibling(unsigned Level) const;
877 /// moveLeft - Move path to the left sibling at Level. Leave nodes below Level
879 /// @param Level Move node(Level).
880 void moveLeft(unsigned Level);
882 /// fillLeft - Grow path to Height by taking leftmost branches.
883 /// @param Height The target height.
884 void fillLeft(unsigned Height) {
885 while (height() < Height)
886 push(subtree(height()), 0);
889 /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
890 /// @param Level Get the sinbling to node(Level).
891 /// @return Left sibling, or NodeRef().
892 NodeRef getRightSibling(unsigned Level) const;
894 /// moveRight - Move path to the left sibling at Level. Leave nodes below
896 /// @param Level Move node(Level).
897 void moveRight(unsigned Level);
899 /// atBegin - Return true if path is at begin().
900 bool atBegin() const {
901 for (unsigned i = 0, e = path.size(); i != e; ++i)
902 if (path[i].offset != 0)
907 /// atLastBranch - Return true if the path is at the last branch of the node
909 /// @param Level Node to examine.
910 bool atLastBranch(unsigned Level) const {
911 return path[Level].offset == path[Level].size - 1;
914 /// legalizeForInsert - Prepare the path for an insertion at Level. When the
915 /// path is at end(), node(Level) may not be a legal node. legalizeForInsert
916 /// ensures that node(Level) is real by moving back to the last node at Level,
917 /// and setting offset(Level) to size(Level) if required.
918 /// @param Level The level where an insertion is about to take place.
919 void legalizeForInsert(unsigned Level) {
923 ++path[Level].offset;
928 for (unsigned l = 0, e = path.size(); l != e; ++l)
929 errs() << l << ": " << path[l].node << ' ' << path[l].size << ' '
930 << path[l].offset << '\n';
935 } // namespace IntervalMapImpl
938 //===----------------------------------------------------------------------===//
939 //--- IntervalMap ----//
940 //===----------------------------------------------------------------------===//
942 template <typename KeyT, typename ValT,
943 unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize,
944 typename Traits = IntervalMapInfo<KeyT> >
946 typedef IntervalMapImpl::NodeSizer<KeyT, ValT> Sizer;
947 typedef IntervalMapImpl::LeafNode<KeyT, ValT, Sizer::LeafSize, Traits> Leaf;
948 typedef IntervalMapImpl::BranchNode<KeyT, ValT, Sizer::BranchSize, Traits>
950 typedef IntervalMapImpl::LeafNode<KeyT, ValT, N, Traits> RootLeaf;
951 typedef IntervalMapImpl::IdxPair IdxPair;
953 // The RootLeaf capacity is given as a template parameter. We must compute the
954 // corresponding RootBranch capacity.
956 DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) /
957 (sizeof(KeyT) + sizeof(IntervalMapImpl::NodeRef)),
958 RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1
961 typedef IntervalMapImpl::BranchNode<KeyT, ValT, RootBranchCap, Traits>
964 // When branched, we store a global start key as well as the branch node.
965 struct RootBranchData {
971 RootDataSize = sizeof(RootBranchData) > sizeof(RootLeaf) ?
972 sizeof(RootBranchData) : sizeof(RootLeaf)
976 typedef typename Sizer::Allocator Allocator;
979 // The root data is either a RootLeaf or a RootBranchData instance.
980 // We can't put them in a union since C++03 doesn't allow non-trivial
981 // constructors in unions.
982 // Instead, we use a char array with pointer alignment. The alignment is
983 // ensured by the allocator member in the class, but still verified in the
984 // constructor. We don't support keys or values that are more aligned than a
986 char data[RootDataSize];
989 // 0: Leaves in root.
990 // 1: Root points to leaf.
991 // 2: root->branch->leaf ...
994 // Number of entries in the root node.
997 // Allocator used for creating external nodes.
998 Allocator &allocator;
1000 /// dataAs - Represent data as a node type without breaking aliasing rules.
1001 template <typename T>
1011 const RootLeaf &rootLeaf() const {
1012 assert(!branched() && "Cannot acces leaf data in branched root");
1013 return dataAs<RootLeaf>();
1015 RootLeaf &rootLeaf() {
1016 assert(!branched() && "Cannot acces leaf data in branched root");
1017 return dataAs<RootLeaf>();
1019 RootBranchData &rootBranchData() const {
1020 assert(branched() && "Cannot access branch data in non-branched root");
1021 return dataAs<RootBranchData>();
1023 RootBranchData &rootBranchData() {
1024 assert(branched() && "Cannot access branch data in non-branched root");
1025 return dataAs<RootBranchData>();
1027 const RootBranch &rootBranch() const { return rootBranchData().node; }
1028 RootBranch &rootBranch() { return rootBranchData().node; }
1029 KeyT rootBranchStart() const { return rootBranchData().start; }
1030 KeyT &rootBranchStart() { return rootBranchData().start; }
1032 template <typename NodeT> NodeT *newNode() {
1033 return new(allocator.template Allocate<NodeT>()) NodeT();
1036 template <typename NodeT> void deleteNode(NodeT *P) {
1038 allocator.Deallocate(P);
1041 IdxPair branchRoot(unsigned Position);
1042 IdxPair splitRoot(unsigned Position);
1044 void switchRootToBranch() {
1045 rootLeaf().~RootLeaf();
1047 new (&rootBranchData()) RootBranchData();
1050 void switchRootToLeaf() {
1051 rootBranchData().~RootBranchData();
1053 new(&rootLeaf()) RootLeaf();
1056 bool branched() const { return height > 0; }
1058 ValT treeSafeLookup(KeyT x, ValT NotFound) const;
1059 void visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef,
1061 void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level);
1064 explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) {
1065 assert((uintptr_t(data) & (alignOf<RootLeaf>() - 1)) == 0 &&
1066 "Insufficient alignment");
1067 new(&rootLeaf()) RootLeaf();
1072 rootLeaf().~RootLeaf();
1075 /// empty - Return true when no intervals are mapped.
1076 bool empty() const {
1077 return rootSize == 0;
1080 /// start - Return the smallest mapped key in a non-empty map.
1081 KeyT start() const {
1082 assert(!empty() && "Empty IntervalMap has no start");
1083 return !branched() ? rootLeaf().start(0) : rootBranchStart();
1086 /// stop - Return the largest mapped key in a non-empty map.
1088 assert(!empty() && "Empty IntervalMap has no stop");
1089 return !branched() ? rootLeaf().stop(rootSize - 1) :
1090 rootBranch().stop(rootSize - 1);
1093 /// lookup - Return the mapped value at x or NotFound.
1094 ValT lookup(KeyT x, ValT NotFound = ValT()) const {
1095 if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x))
1097 return branched() ? treeSafeLookup(x, NotFound) :
1098 rootLeaf().safeLookup(x, NotFound);
1101 /// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
1102 /// It is assumed that no key in the interval is mapped to another value, but
1103 /// overlapping intervals already mapped to y will be coalesced.
1104 void insert(KeyT a, KeyT b, ValT y) {
1105 if (branched() || rootSize == RootLeaf::Capacity)
1106 return find(a).insert(a, b, y);
1108 // Easy insert into root leaf.
1109 unsigned p = rootLeaf().findFrom(0, rootSize, a);
1110 rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y);
1113 /// clear - Remove all entries.
1116 class const_iterator;
1118 friend class const_iterator;
1119 friend class iterator;
1121 const_iterator begin() const {
1133 const_iterator end() const {
1145 /// find - Return an iterator pointing to the first interval ending at or
1146 /// after x, or end().
1147 const_iterator find(KeyT x) const {
1153 iterator find(KeyT x) {
1162 void dumpNode(IntervalMapImpl::NodeRef Node, unsigned Height);
1166 /// treeSafeLookup - Return the mapped value at x or NotFound, assuming a
1168 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1169 ValT IntervalMap<KeyT, ValT, N, Traits>::
1170 treeSafeLookup(KeyT x, ValT NotFound) const {
1171 assert(branched() && "treeLookup assumes a branched root");
1173 IntervalMapImpl::NodeRef NR = rootBranch().safeLookup(x);
1174 for (unsigned h = height-1; h; --h)
1175 NR = NR.get<Branch>().safeLookup(x);
1176 return NR.get<Leaf>().safeLookup(x, NotFound);
1180 // branchRoot - Switch from a leaf root to a branched root.
1181 // Return the new (root offset, node offset) corresponding to Position.
1182 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1183 IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
1184 branchRoot(unsigned Position) {
1185 using namespace IntervalMapImpl;
1186 // How many external leaf nodes to hold RootLeaf+1?
1187 const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1;
1189 // Compute element distribution among new nodes.
1190 unsigned size[Nodes];
1191 IdxPair NewOffset(0, Position);
1193 // Is is very common for the root node to be smaller than external nodes.
1197 NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, size,
1200 // Allocate new nodes.
1202 NodeRef node[Nodes];
1203 for (unsigned n = 0; n != Nodes; ++n) {
1204 Leaf *L = newNode<Leaf>();
1205 L->copy(rootLeaf(), pos, 0, size[n]);
1206 node[n] = NodeRef(L, size[n]);
1210 // Destroy the old leaf node, construct branch node instead.
1211 switchRootToBranch();
1212 for (unsigned n = 0; n != Nodes; ++n) {
1213 rootBranch().stop(n) = node[n].template get<Leaf>().stop(size[n]-1);
1214 rootBranch().subtree(n) = node[n];
1216 rootBranchStart() = node[0].template get<Leaf>().start(0);
1221 // splitRoot - Split the current BranchRoot into multiple Branch nodes.
1222 // Return the new (root offset, node offset) corresponding to Position.
1223 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1224 IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
1225 splitRoot(unsigned Position) {
1226 using namespace IntervalMapImpl;
1227 // How many external leaf nodes to hold RootBranch+1?
1228 const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1;
1230 // Compute element distribution among new nodes.
1231 unsigned Size[Nodes];
1232 IdxPair NewOffset(0, Position);
1234 // Is is very common for the root node to be smaller than external nodes.
1238 NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, Size,
1241 // Allocate new nodes.
1243 NodeRef Node[Nodes];
1244 for (unsigned n = 0; n != Nodes; ++n) {
1245 Branch *B = newNode<Branch>();
1246 B->copy(rootBranch(), Pos, 0, Size[n]);
1247 Node[n] = NodeRef(B, Size[n]);
1251 for (unsigned n = 0; n != Nodes; ++n) {
1252 rootBranch().stop(n) = Node[n].template get<Branch>().stop(Size[n]-1);
1253 rootBranch().subtree(n) = Node[n];
1260 /// visitNodes - Visit each external node.
1261 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1262 void IntervalMap<KeyT, ValT, N, Traits>::
1263 visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, unsigned Height)) {
1266 SmallVector<IntervalMapImpl::NodeRef, 4> Refs, NextRefs;
1268 // Collect level 0 nodes from the root.
1269 for (unsigned i = 0; i != rootSize; ++i)
1270 Refs.push_back(rootBranch().subtree(i));
1272 // Visit all branch nodes.
1273 for (unsigned h = height - 1; h; --h) {
1274 for (unsigned i = 0, e = Refs.size(); i != e; ++i) {
1275 for (unsigned j = 0, s = Refs[i].size(); j != s; ++j)
1276 NextRefs.push_back(Refs[i].subtree(j));
1277 (this->*f)(Refs[i], h);
1280 Refs.swap(NextRefs);
1283 // Visit all leaf nodes.
1284 for (unsigned i = 0, e = Refs.size(); i != e; ++i)
1285 (this->*f)(Refs[i], 0);
1288 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1289 void IntervalMap<KeyT, ValT, N, Traits>::
1290 deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) {
1292 deleteNode(&Node.get<Branch>());
1294 deleteNode(&Node.get<Leaf>());
1297 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1298 void IntervalMap<KeyT, ValT, N, Traits>::
1301 visitNodes(&IntervalMap::deleteNode);
1308 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1309 void IntervalMap<KeyT, ValT, N, Traits>::
1310 dumpNode(IntervalMapImpl::NodeRef Node, unsigned Height) {
1312 Node.get<Branch>().dump(*OS, Node.size());
1314 Node.get<Leaf>().dump(*OS, Node.size());
1317 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1318 void IntervalMap<KeyT, ValT, N, Traits>::
1321 raw_fd_ostream ofs("tree.dot", errors);
1323 ofs << "digraph {\n";
1325 rootBranch().dump(ofs, rootSize);
1327 rootLeaf().dump(ofs, rootSize);
1328 visitNodes(&IntervalMap::dumpNode);
1333 //===----------------------------------------------------------------------===//
1334 //--- IntervalMap::const_iterator ----//
1335 //===----------------------------------------------------------------------===//
1337 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1338 class IntervalMap<KeyT, ValT, N, Traits>::const_iterator :
1339 public std::iterator<std::bidirectional_iterator_tag, ValT> {
1341 friend class IntervalMap;
1343 // The map referred to.
1346 // We store a full path from the root to the current position.
1347 // The path may be partially filled, but never between iterator calls.
1348 IntervalMapImpl::Path path;
1350 explicit const_iterator(IntervalMap &map) : map(&map) {}
1352 bool branched() const {
1353 assert(map && "Invalid iterator");
1354 return map->branched();
1357 void setRoot(unsigned Offset) {
1359 path.setRoot(&map->rootBranch(), map->rootSize, Offset);
1361 path.setRoot(&map->rootLeaf(), map->rootSize, Offset);
1364 void pathFillFind(KeyT x);
1365 void treeFind(KeyT x);
1366 void treeAdvanceTo(KeyT x);
1369 /// const_iterator - Create an iterator that isn't pointing anywhere.
1370 const_iterator() : map(0) {}
1372 /// valid - Return true if the current position is valid, false for end().
1373 bool valid() const { return path.valid(); }
1375 /// start - Return the beginning of the current interval.
1376 const KeyT &start() const {
1377 assert(valid() && "Cannot access invalid iterator");
1378 return branched() ? path.leaf<Leaf>().start(path.leafOffset()) :
1379 path.leaf<RootLeaf>().start(path.leafOffset());
1382 /// stop - Return the end of the current interval.
1383 const KeyT &stop() const {
1384 assert(valid() && "Cannot access invalid iterator");
1385 return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) :
1386 path.leaf<RootLeaf>().stop(path.leafOffset());
1389 /// value - Return the mapped value at the current interval.
1390 const ValT &value() const {
1391 assert(valid() && "Cannot access invalid iterator");
1392 return branched() ? path.leaf<Leaf>().value(path.leafOffset()) :
1393 path.leaf<RootLeaf>().value(path.leafOffset());
1396 const ValT &operator*() const {
1400 bool operator==(const const_iterator &RHS) const {
1401 assert(map == RHS.map && "Cannot compare iterators from different maps");
1403 return !RHS.valid();
1404 if (path.leafOffset() != RHS.path.leafOffset())
1406 return &path.template leaf<Leaf>() == &RHS.path.template leaf<Leaf>();
1409 bool operator!=(const const_iterator &RHS) const {
1410 return !operator==(RHS);
1413 /// goToBegin - Move to the first interval in map.
1417 path.fillLeft(map->height);
1420 /// goToEnd - Move beyond the last interval in map.
1422 setRoot(map->rootSize);
1425 /// preincrement - move to the next interval.
1426 const_iterator &operator++() {
1427 assert(valid() && "Cannot increment end()");
1428 if (++path.leafOffset() == path.leafSize() && branched())
1429 path.moveRight(map->height);
1433 /// postincrement - Dont do that!
1434 const_iterator operator++(int) {
1435 const_iterator tmp = *this;
1440 /// predecrement - move to the previous interval.
1441 const_iterator &operator--() {
1442 if (path.leafOffset() && (valid() || !branched()))
1443 --path.leafOffset();
1445 path.moveLeft(map->height);
1449 /// postdecrement - Dont do that!
1450 const_iterator operator--(int) {
1451 const_iterator tmp = *this;
1456 /// find - Move to the first interval with stop >= x, or end().
1457 /// This is a full search from the root, the current position is ignored.
1462 setRoot(map->rootLeaf().findFrom(0, map->rootSize, x));
1465 /// advanceTo - Move to the first interval with stop >= x, or end().
1466 /// The search is started from the current position, and no earlier positions
1467 /// can be found. This is much faster than find() for small moves.
1468 void advanceTo(KeyT x) {
1473 map->rootLeaf().findFrom(path.leafOffset(), map->rootSize, x);
1478 /// pathFillFind - Complete path by searching for x.
1479 /// @param x Key to search for.
1480 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1481 void IntervalMap<KeyT, ValT, N, Traits>::
1482 const_iterator::pathFillFind(KeyT x) {
1483 IntervalMapImpl::NodeRef NR = path.subtree(path.height());
1484 for (unsigned i = map->height - path.height() - 1; i; --i) {
1485 unsigned p = NR.get<Branch>().safeFind(0, x);
1489 path.push(NR, NR.get<Leaf>().safeFind(0, x));
1492 /// treeFind - Find in a branched tree.
1493 /// @param x Key to search for.
1494 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1495 void IntervalMap<KeyT, ValT, N, Traits>::
1496 const_iterator::treeFind(KeyT x) {
1497 setRoot(map->rootBranch().findFrom(0, map->rootSize, x));
1502 /// treeAdvanceTo - Find position after the current one.
1503 /// @param x Key to search for.
1504 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1505 void IntervalMap<KeyT, ValT, N, Traits>::
1506 const_iterator::treeAdvanceTo(KeyT x) {
1507 // Can we stay on the same leaf node?
1508 if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) {
1509 path.leafOffset() = path.leaf<Leaf>().safeFind(path.leafOffset(), x);
1513 // Drop the current leaf.
1516 // Search towards the root for a usable subtree.
1517 if (path.height()) {
1518 for (unsigned l = path.height() - 1; l; --l) {
1519 if (!Traits::stopLess(path.node<Branch>(l).stop(path.offset(l)), x)) {
1520 // The branch node at l+1 is usable
1521 path.offset(l + 1) =
1522 path.node<Branch>(l + 1).safeFind(path.offset(l + 1), x);
1523 return pathFillFind(x);
1527 // Is the level-1 Branch usable?
1528 if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) {
1529 path.offset(1) = path.node<Branch>(1).safeFind(path.offset(1), x);
1530 return pathFillFind(x);
1534 // We reached the root.
1535 setRoot(map->rootBranch().findFrom(path.offset(0), map->rootSize, x));
1540 //===----------------------------------------------------------------------===//
1541 //--- IntervalMap::iterator ----//
1542 //===----------------------------------------------------------------------===//
1544 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1545 class IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator {
1546 friend class IntervalMap;
1547 typedef IntervalMapImpl::IdxPair IdxPair;
1549 explicit iterator(IntervalMap &map) : const_iterator(map) {}
1551 void setNodeStop(unsigned Level, KeyT Stop);
1552 bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop);
1553 template <typename NodeT> bool overflow(unsigned Level);
1554 void treeInsert(KeyT a, KeyT b, ValT y);
1555 void eraseNode(unsigned Level);
1556 void treeErase(bool UpdateRoot = true);
1558 /// iterator - Create null iterator.
1561 /// insert - Insert mapping [a;b] -> y before the current position.
1562 void insert(KeyT a, KeyT b, ValT y);
1564 /// erase - Erase the current interval.
1567 iterator &operator++() {
1568 const_iterator::operator++();
1572 iterator operator++(int) {
1573 iterator tmp = *this;
1578 iterator &operator--() {
1579 const_iterator::operator--();
1583 iterator operator--(int) {
1584 iterator tmp = *this;
1591 /// setNodeStop - Update the stop key of the current node at level and above.
1592 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1593 void IntervalMap<KeyT, ValT, N, Traits>::
1594 iterator::setNodeStop(unsigned Level, KeyT Stop) {
1595 // There are no references to the root node, so nothing to update.
1598 IntervalMapImpl::Path &P = this->path;
1599 // Update nodes pointing to the current node.
1601 P.node<Branch>(Level).stop(P.offset(Level)) = Stop;
1602 if (!P.atLastBranch(Level))
1605 // Update root separately since it has a different layout.
1606 P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop;
1609 /// insertNode - insert a node before the current path at level.
1610 /// Leave the current path pointing at the new node.
1611 /// @param Level path index of the node to be inserted.
1612 /// @param Node The node to be inserted.
1613 /// @param Stop The last index in the new node.
1614 /// @return True if the tree height was increased.
1615 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1616 bool IntervalMap<KeyT, ValT, N, Traits>::
1617 iterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) {
1618 assert(Level && "Cannot insert next to the root");
1619 bool SplitRoot = false;
1620 IntervalMap &IM = *this->map;
1621 IntervalMapImpl::Path &P = this->path;
1624 // Insert into the root branch node.
1625 if (IM.rootSize < RootBranch::Capacity) {
1626 IM.rootBranch().insert(P.offset(0), IM.rootSize, Node, Stop);
1627 P.setSize(0, ++IM.rootSize);
1632 // We need to split the root while keeping our position.
1634 IdxPair Offset = IM.splitRoot(P.offset(0));
1635 P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset);
1637 // Fall through to insert at the new higher level.
1641 // When inserting before end(), make sure we have a valid path.
1642 P.legalizeForInsert(--Level);
1644 // Insert into the branch node at Level-1.
1645 if (P.size(Level) == Branch::Capacity) {
1646 // Branch node is full, handle handle the overflow.
1647 assert(!SplitRoot && "Cannot overflow after splitting the root");
1648 SplitRoot = overflow<Branch>(Level);
1651 P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop);
1652 P.setSize(Level, P.size(Level) + 1);
1653 if (P.atLastBranch(Level))
1654 setNodeStop(Level, Stop);
1660 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1661 void IntervalMap<KeyT, ValT, N, Traits>::
1662 iterator::insert(KeyT a, KeyT b, ValT y) {
1663 if (this->branched())
1664 return treeInsert(a, b, y);
1665 IntervalMap &IM = *this->map;
1666 IntervalMapImpl::Path &P = this->path;
1668 // Try simple root leaf insert.
1669 unsigned Size = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y);
1671 // Was the root node insert successful?
1672 if (Size <= RootLeaf::Capacity) {
1673 P.setSize(0, IM.rootSize = Size);
1677 // Root leaf node is full, we must branch.
1678 IdxPair Offset = IM.branchRoot(P.leafOffset());
1679 P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset);
1681 // Now it fits in the new leaf.
1682 treeInsert(a, b, y);
1686 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1687 void IntervalMap<KeyT, ValT, N, Traits>::
1688 iterator::treeInsert(KeyT a, KeyT b, ValT y) {
1689 using namespace IntervalMapImpl;
1690 Path &P = this->path;
1693 P.legalizeForInsert(this->map->height);
1695 // Check if this insertion will extend the node to the left.
1696 if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<Leaf>().start(0))) {
1697 // Node is growing to the left, will it affect a left sibling node?
1698 if (NodeRef Sib = P.getLeftSibling(P.height())) {
1699 Leaf &SibLeaf = Sib.get<Leaf>();
1700 unsigned SibOfs = Sib.size() - 1;
1701 if (SibLeaf.value(SibOfs) == y &&
1702 Traits::adjacent(SibLeaf.stop(SibOfs), a)) {
1703 // This insertion will coalesce with the last entry in SibLeaf. We can
1704 // handle it in two ways:
1705 // 1. Extend SibLeaf.stop to b and be done, or
1706 // 2. Extend a to SibLeaf, erase the SibLeaf entry and continue.
1707 // We prefer 1., but need 2 when coalescing to the right as well.
1708 Leaf &CurLeaf = P.leaf<Leaf>();
1709 P.moveLeft(P.height());
1710 if (Traits::stopLess(b, CurLeaf.start(0)) &&
1711 (y != CurLeaf.value(0) || !Traits::adjacent(b, CurLeaf.start(0)))) {
1712 // Easy, just extend SibLeaf and we're done.
1713 setNodeStop(P.height(), SibLeaf.stop(SibOfs) = b);
1716 // We have both left and right coalescing. Erase the old SibLeaf entry
1717 // and continue inserting the larger interval.
1718 a = SibLeaf.start(SibOfs);
1719 treeErase(/* UpdateRoot= */false);
1723 // No left sibling means we are at begin(). Update cached bound.
1724 this->map->rootBranchStart() = a;
1728 // When we are inserting at the end of a leaf node, we must update stops.
1729 unsigned Size = P.leafSize();
1730 bool Grow = P.leafOffset() == Size;
1731 Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), Size, a, b, y);
1733 // Leaf insertion unsuccessful? Overflow and try again.
1734 if (Size > Leaf::Capacity) {
1735 overflow<Leaf>(P.height());
1736 Grow = P.leafOffset() == P.leafSize();
1737 Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y);
1738 assert(Size <= Leaf::Capacity && "overflow() didn't make room");
1741 // Inserted, update offset and leaf size.
1742 P.setSize(P.height(), Size);
1744 // Insert was the last node entry, update stops.
1746 setNodeStop(P.height(), b);
1749 /// erase - erase the current interval and move to the next position.
1750 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1751 void IntervalMap<KeyT, ValT, N, Traits>::
1753 IntervalMap &IM = *this->map;
1754 IntervalMapImpl::Path &P = this->path;
1755 assert(P.valid() && "Cannot erase end()");
1756 if (this->branched())
1758 IM.rootLeaf().erase(P.leafOffset(), IM.rootSize);
1759 P.setSize(0, --IM.rootSize);
1762 /// treeErase - erase() for a branched tree.
1763 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1764 void IntervalMap<KeyT, ValT, N, Traits>::
1765 iterator::treeErase(bool UpdateRoot) {
1766 IntervalMap &IM = *this->map;
1767 IntervalMapImpl::Path &P = this->path;
1768 Leaf &Node = P.leaf<Leaf>();
1770 // Nodes are not allowed to become empty.
1771 if (P.leafSize() == 1) {
1772 IM.deleteNode(&Node);
1773 eraseNode(IM.height);
1774 // Update rootBranchStart if we erased begin().
1775 if (UpdateRoot && IM.branched() && P.valid() && P.atBegin())
1776 IM.rootBranchStart() = P.leaf<Leaf>().start(0);
1780 // Erase current entry.
1781 Node.erase(P.leafOffset(), P.leafSize());
1782 unsigned NewSize = P.leafSize() - 1;
1783 P.setSize(IM.height, NewSize);
1784 // When we erase the last entry, update stop and move to a legal position.
1785 if (P.leafOffset() == NewSize) {
1786 setNodeStop(IM.height, Node.stop(NewSize - 1));
1787 P.moveRight(IM.height);
1788 } else if (UpdateRoot && P.atBegin())
1789 IM.rootBranchStart() = P.leaf<Leaf>().start(0);
1792 /// eraseNode - Erase the current node at Level from its parent and move path to
1793 /// the first entry of the next sibling node.
1794 /// The node must be deallocated by the caller.
1795 /// @param Level 1..height, the root node cannot be erased.
1796 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1797 void IntervalMap<KeyT, ValT, N, Traits>::
1798 iterator::eraseNode(unsigned Level) {
1799 assert(Level && "Cannot erase root node");
1800 IntervalMap &IM = *this->map;
1801 IntervalMapImpl::Path &P = this->path;
1804 IM.rootBranch().erase(P.offset(0), IM.rootSize);
1805 P.setSize(0, --IM.rootSize);
1806 // If this cleared the root, switch to height=0.
1808 IM.switchRootToLeaf();
1813 // Remove node ref from branch node at Level.
1814 Branch &Parent = P.node<Branch>(Level);
1815 if (P.size(Level) == 1) {
1816 // Branch node became empty, remove it recursively.
1817 IM.deleteNode(&Parent);
1820 // Branch node won't become empty.
1821 Parent.erase(P.offset(Level), P.size(Level));
1822 unsigned NewSize = P.size(Level) - 1;
1823 P.setSize(Level, NewSize);
1824 // If we removed the last branch, update stop and move to a legal pos.
1825 if (P.offset(Level) == NewSize) {
1826 setNodeStop(Level, Parent.stop(NewSize - 1));
1831 // Update path cache for the new right sibling position.
1834 P.offset(Level + 1) = 0;
1838 /// overflow - Distribute entries of the current node evenly among
1839 /// its siblings and ensure that the current node is not full.
1840 /// This may require allocating a new node.
1841 /// @param NodeT The type of node at Level (Leaf or Branch).
1842 /// @param Level path index of the overflowing node.
1843 /// @return True when the tree height was changed.
1844 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1845 template <typename NodeT>
1846 bool IntervalMap<KeyT, ValT, N, Traits>::
1847 iterator::overflow(unsigned Level) {
1848 using namespace IntervalMapImpl;
1849 Path &P = this->path;
1850 unsigned CurSize[4];
1853 unsigned Elements = 0;
1854 unsigned Offset = P.offset(Level);
1856 // Do we have a left sibling?
1857 NodeRef LeftSib = P.getLeftSibling(Level);
1859 Offset += Elements = CurSize[Nodes] = LeftSib.size();
1860 Node[Nodes++] = &LeftSib.get<NodeT>();
1864 Elements += CurSize[Nodes] = P.size(Level);
1865 Node[Nodes++] = &P.node<NodeT>(Level);
1867 // Do we have a right sibling?
1868 NodeRef RightSib = P.getRightSibling(Level);
1870 Elements += CurSize[Nodes] = RightSib.size();
1871 Node[Nodes++] = &RightSib.get<NodeT>();
1874 // Do we need to allocate a new node?
1875 unsigned NewNode = 0;
1876 if (Elements + 1 > Nodes * NodeT::Capacity) {
1877 // Insert NewNode at the penultimate position, or after a single node.
1878 NewNode = Nodes == 1 ? 1 : Nodes - 1;
1879 CurSize[Nodes] = CurSize[NewNode];
1880 Node[Nodes] = Node[NewNode];
1881 CurSize[NewNode] = 0;
1882 Node[NewNode] = this->map->newNode<NodeT>();
1886 // Compute the new element distribution.
1887 unsigned NewSize[4];
1888 IdxPair NewOffset = distribute(Nodes, Elements, NodeT::Capacity,
1889 CurSize, NewSize, Offset, true);
1890 adjustSiblingSizes(Node, Nodes, CurSize, NewSize);
1892 // Move current location to the leftmost node.
1896 // Elements have been rearranged, now update node sizes and stops.
1897 bool SplitRoot = false;
1900 KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1);
1901 if (NewNode && Pos == NewNode) {
1902 SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop);
1905 P.setSize(Level, NewSize[Pos]);
1906 setNodeStop(Level, Stop);
1908 if (Pos + 1 == Nodes)
1914 // Where was I? Find NewOffset.
1915 while(Pos != NewOffset.first) {
1919 P.offset(Level) = NewOffset.second;