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/PointerIntPair.h"
103 #include "llvm/ADT/SmallVector.h"
104 #include "llvm/Support/AlignOf.h"
105 #include "llvm/Support/Allocator.h"
106 #include "llvm/Support/RecyclingAllocator.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 {
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) {
155 /// nonEmpty - Return true if [a;b] is non-empty.
156 /// This is a <= b for a closed interval, a < b for [a;b) half-open intervals.
157 static inline bool nonEmpty(const T &a, const T &b) {
162 template <typename T>
163 struct IntervalMapHalfOpenInfo {
164 /// startLess - Return true if x is not in [a;b).
165 static inline bool startLess(const T &x, const T &a) {
169 /// stopLess - Return true if x is not in [a;b).
170 static inline bool stopLess(const T &b, const T &x) {
174 /// adjacent - Return true when the intervals [x;a) and [b;y) can coalesce.
175 static inline bool adjacent(const T &a, const T &b) {
179 /// nonEmpty - Return true if [a;b) is non-empty.
180 static inline bool nonEmpty(const T &a, const T &b) {
185 /// IntervalMapImpl - Namespace used for IntervalMap implementation details.
186 /// It should be considered private to the implementation.
187 namespace IntervalMapImpl {
189 typedef std::pair<unsigned,unsigned> IdxPair;
191 //===----------------------------------------------------------------------===//
192 //--- IntervalMapImpl::NodeBase ---//
193 //===----------------------------------------------------------------------===//
195 // Both leaf and branch nodes store vectors of pairs.
196 // Leaves store ((KeyT, KeyT), ValT) pairs, branches use (NodeRef, KeyT).
198 // Keys and values are stored in separate arrays to avoid padding caused by
199 // different object alignments. This also helps improve locality of reference
200 // when searching the keys.
202 // The nodes don't know how many elements they contain - that information is
203 // stored elsewhere. Omitting the size field prevents padding and allows a node
204 // to fill the allocated cache lines completely.
206 // These are typical key and value sizes, the node branching factor (N), and
207 // wasted space when nodes are sized to fit in three cache lines (192 bytes):
209 // T1 T2 N Waste Used by
210 // 4 4 24 0 Branch<4> (32-bit pointers)
211 // 8 4 16 0 Leaf<4,4>, Branch<4>
212 // 8 8 12 0 Leaf<4,8>, Branch<8>
213 // 16 4 9 12 Leaf<8,4>
214 // 16 8 8 0 Leaf<8,8>
216 //===----------------------------------------------------------------------===//
218 template <typename T1, typename T2, unsigned N>
221 enum { Capacity = N };
226 /// copy - Copy elements from another node.
227 /// @param Other Node elements are copied from.
228 /// @param i Beginning of the source range in other.
229 /// @param j Beginning of the destination range in this.
230 /// @param Count Number of elements to copy.
231 template <unsigned M>
232 void copy(const NodeBase<T1, T2, M> &Other, unsigned i,
233 unsigned j, unsigned Count) {
234 assert(i + Count <= M && "Invalid source range");
235 assert(j + Count <= N && "Invalid dest range");
236 for (unsigned e = i + Count; i != e; ++i, ++j) {
237 first[j] = Other.first[i];
238 second[j] = Other.second[i];
242 /// moveLeft - Move elements to the left.
243 /// @param i Beginning of the source range.
244 /// @param j Beginning of the destination range.
245 /// @param Count Number of elements to copy.
246 void moveLeft(unsigned i, unsigned j, unsigned Count) {
247 assert(j <= i && "Use moveRight shift elements right");
248 copy(*this, i, j, Count);
251 /// moveRight - Move elements to the right.
252 /// @param i Beginning of the source range.
253 /// @param j Beginning of the destination range.
254 /// @param Count Number of elements to copy.
255 void moveRight(unsigned i, unsigned j, unsigned Count) {
256 assert(i <= j && "Use moveLeft shift elements left");
257 assert(j + Count <= N && "Invalid range");
259 first[j + Count] = first[i + Count];
260 second[j + Count] = second[i + Count];
264 /// erase - Erase elements [i;j).
265 /// @param i Beginning of the range to erase.
266 /// @param j End of the range. (Exclusive).
267 /// @param Size Number of elements in node.
268 void erase(unsigned i, unsigned j, unsigned Size) {
269 moveLeft(j, i, Size - j);
272 /// erase - Erase element at i.
273 /// @param i Index of element to erase.
274 /// @param Size Number of elements in node.
275 void erase(unsigned i, unsigned Size) {
279 /// shift - Shift elements [i;size) 1 position to the right.
280 /// @param i Beginning of the range to move.
281 /// @param Size Number of elements in node.
282 void shift(unsigned i, unsigned Size) {
283 moveRight(i, i + 1, Size - i);
286 /// transferToLeftSib - Transfer elements to a left sibling node.
287 /// @param Size Number of elements in this.
288 /// @param Sib Left sibling node.
289 /// @param SSize Number of elements in sib.
290 /// @param Count Number of elements to transfer.
291 void transferToLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize,
293 Sib.copy(*this, 0, SSize, Count);
294 erase(0, Count, Size);
297 /// transferToRightSib - Transfer elements to a right sibling node.
298 /// @param Size Number of elements in this.
299 /// @param Sib Right sibling node.
300 /// @param SSize Number of elements in sib.
301 /// @param Count Number of elements to transfer.
302 void transferToRightSib(unsigned Size, NodeBase &Sib, unsigned SSize,
304 Sib.moveRight(0, Count, SSize);
305 Sib.copy(*this, Size-Count, 0, Count);
308 /// adjustFromLeftSib - Adjust the number if elements in this node by moving
309 /// elements to or from a left sibling node.
310 /// @param Size Number of elements in this.
311 /// @param Sib Right sibling node.
312 /// @param SSize Number of elements in sib.
313 /// @param Add The number of elements to add to this node, possibly < 0.
314 /// @return Number of elements added to this node, possibly negative.
315 int adjustFromLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add) {
317 // We want to grow, copy from sib.
318 unsigned Count = std::min(std::min(unsigned(Add), SSize), N - Size);
319 Sib.transferToRightSib(SSize, *this, Size, Count);
322 // We want to shrink, copy to sib.
323 unsigned Count = std::min(std::min(unsigned(-Add), Size), N - SSize);
324 transferToLeftSib(Size, Sib, SSize, Count);
330 /// IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes.
331 /// @param Node Array of pointers to sibling nodes.
332 /// @param Nodes Number of nodes.
333 /// @param CurSize Array of current node sizes, will be overwritten.
334 /// @param NewSize Array of desired node sizes.
335 template <typename NodeT>
336 void adjustSiblingSizes(NodeT *Node[], unsigned Nodes,
337 unsigned CurSize[], const unsigned NewSize[]) {
338 // Move elements right.
339 for (int n = Nodes - 1; n; --n) {
340 if (CurSize[n] == NewSize[n])
342 for (int m = n - 1; m != -1; --m) {
343 int d = Node[n]->adjustFromLeftSib(CurSize[n], *Node[m], CurSize[m],
344 NewSize[n] - CurSize[n]);
347 // Keep going if the current node was exhausted.
348 if (CurSize[n] >= NewSize[n])
356 // Move elements left.
357 for (unsigned n = 0; n != Nodes - 1; ++n) {
358 if (CurSize[n] == NewSize[n])
360 for (unsigned m = n + 1; m != Nodes; ++m) {
361 int d = Node[m]->adjustFromLeftSib(CurSize[m], *Node[n], CurSize[n],
362 CurSize[n] - NewSize[n]);
365 // Keep going if the current node was exhausted.
366 if (CurSize[n] >= NewSize[n])
372 for (unsigned n = 0; n != Nodes; n++)
373 assert(CurSize[n] == NewSize[n] && "Insufficient element shuffle");
377 /// IntervalMapImpl::distribute - Compute a new distribution of node elements
378 /// after an overflow or underflow. Reserve space for a new element at Position,
379 /// and compute the node that will hold Position after redistributing node
382 /// It is required that
384 /// Elements == sum(CurSize), and
385 /// Elements + Grow <= Nodes * Capacity.
387 /// NewSize[] will be filled in such that:
389 /// sum(NewSize) == Elements, and
390 /// NewSize[i] <= Capacity.
392 /// The returned index is the node where Position will go, so:
394 /// sum(NewSize[0..idx-1]) <= Position
395 /// sum(NewSize[0..idx]) >= Position
397 /// The last equality, sum(NewSize[0..idx]) == Position, can only happen when
398 /// Grow is set and NewSize[idx] == Capacity-1. The index points to the node
399 /// before the one holding the Position'th element where there is room for an
402 /// @param Nodes The number of nodes.
403 /// @param Elements Total elements in all nodes.
404 /// @param Capacity The capacity of each node.
405 /// @param CurSize Array[Nodes] of current node sizes, or NULL.
406 /// @param NewSize Array[Nodes] to receive the new node sizes.
407 /// @param Position Insert position.
408 /// @param Grow Reserve space for a new element at Position.
409 /// @return (node, offset) for Position.
410 IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,
411 const unsigned *CurSize, unsigned NewSize[],
412 unsigned Position, bool Grow);
414 //===----------------------------------------------------------------------===//
415 //--- IntervalMapImpl::NodeSizer ---//
416 //===----------------------------------------------------------------------===//
418 // Compute node sizes from key and value types.
420 // The branching factors are chosen to make nodes fit in three cache lines.
421 // This may not be possible if keys or values are very large. Such large objects
422 // are handled correctly, but a std::map would probably give better performance.
424 //===----------------------------------------------------------------------===//
427 // Cache line size. Most architectures have 32 or 64 byte cache lines.
428 // We use 64 bytes here because it provides good branching factors.
430 CacheLineBytes = 1 << Log2CacheLine,
431 DesiredNodeBytes = 3 * CacheLineBytes
434 template <typename KeyT, typename ValT>
437 // Compute the leaf node branching factor that makes a node fit in three
438 // cache lines. The branching factor must be at least 3, or some B+-tree
439 // balancing algorithms won't work.
440 // LeafSize can't be larger than CacheLineBytes. This is required by the
441 // PointerIntPair used by NodeRef.
442 DesiredLeafSize = DesiredNodeBytes /
443 static_cast<unsigned>(2*sizeof(KeyT)+sizeof(ValT)),
445 LeafSize = DesiredLeafSize > MinLeafSize ? DesiredLeafSize : MinLeafSize
448 typedef NodeBase<std::pair<KeyT, KeyT>, ValT, LeafSize> LeafBase;
451 // Now that we have the leaf branching factor, compute the actual allocation
452 // unit size by rounding up to a whole number of cache lines.
453 AllocBytes = (sizeof(LeafBase) + CacheLineBytes-1) & ~(CacheLineBytes-1),
455 // Determine the branching factor for branch nodes.
456 BranchSize = AllocBytes /
457 static_cast<unsigned>(sizeof(KeyT) + sizeof(void*))
460 /// Allocator - The recycling allocator used for both branch and leaf nodes.
461 /// This typedef is very likely to be identical for all IntervalMaps with
462 /// reasonably sized entries, so the same allocator can be shared among
463 /// different kinds of maps.
464 typedef RecyclingAllocator<BumpPtrAllocator, char,
465 AllocBytes, CacheLineBytes> Allocator;
468 //===----------------------------------------------------------------------===//
469 //--- IntervalMapImpl::NodeRef ---//
470 //===----------------------------------------------------------------------===//
472 // B+-tree nodes can be leaves or branches, so we need a polymorphic node
473 // pointer that can point to both kinds.
475 // All nodes are cache line aligned and the low 6 bits of a node pointer are
476 // always 0. These bits are used to store the number of elements in the
477 // referenced node. Besides saving space, placing node sizes in the parents
478 // allow tree balancing algorithms to run without faulting cache lines for nodes
479 // that may not need to be modified.
481 // A NodeRef doesn't know whether it references a leaf node or a branch node.
482 // It is the responsibility of the caller to use the correct types.
484 // Nodes are never supposed to be empty, and it is invalid to store a node size
485 // of 0 in a NodeRef. The valid range of sizes is 1-64.
487 //===----------------------------------------------------------------------===//
490 struct CacheAlignedPointerTraits {
491 static inline void *getAsVoidPointer(void *P) { return P; }
492 static inline void *getFromVoidPointer(void *P) { return P; }
493 enum { NumLowBitsAvailable = Log2CacheLine };
495 PointerIntPair<void*, Log2CacheLine, unsigned, CacheAlignedPointerTraits> pip;
498 /// NodeRef - Create a null ref.
501 /// operator bool - Detect a null ref.
502 explicit operator bool() const { return pip.getOpaqueValue(); }
504 /// NodeRef - Create a reference to the node p with n elements.
505 template <typename NodeT>
506 NodeRef(NodeT *p, unsigned n) : pip(p, n - 1) {
507 assert(n <= NodeT::Capacity && "Size too big for node");
510 /// size - Return the number of elements in the referenced node.
511 unsigned size() const { return pip.getInt() + 1; }
513 /// setSize - Update the node size.
514 void setSize(unsigned n) { pip.setInt(n - 1); }
516 /// subtree - Access the i'th subtree reference in a branch node.
517 /// This depends on branch nodes storing the NodeRef array as their first
519 NodeRef &subtree(unsigned i) const {
520 return reinterpret_cast<NodeRef*>(pip.getPointer())[i];
523 /// get - Dereference as a NodeT reference.
524 template <typename NodeT>
526 return *reinterpret_cast<NodeT*>(pip.getPointer());
529 bool operator==(const NodeRef &RHS) const {
532 assert(pip.getPointer() != RHS.pip.getPointer() && "Inconsistent NodeRefs");
536 bool operator!=(const NodeRef &RHS) const {
537 return !operator==(RHS);
541 //===----------------------------------------------------------------------===//
542 //--- IntervalMapImpl::LeafNode ---//
543 //===----------------------------------------------------------------------===//
545 // Leaf nodes store up to N disjoint intervals with corresponding values.
547 // The intervals are kept sorted and fully coalesced so there are no adjacent
548 // intervals mapping to the same value.
550 // These constraints are always satisfied:
552 // - Traits::stopLess(start(i), stop(i)) - Non-empty, sane intervals.
554 // - Traits::stopLess(stop(i), start(i + 1) - Sorted.
556 // - value(i) != value(i + 1) || !Traits::adjacent(stop(i), start(i + 1))
557 // - Fully coalesced.
559 //===----------------------------------------------------------------------===//
561 template <typename KeyT, typename ValT, unsigned N, typename Traits>
562 class LeafNode : public NodeBase<std::pair<KeyT, KeyT>, ValT, N> {
564 const KeyT &start(unsigned i) const { return this->first[i].first; }
565 const KeyT &stop(unsigned i) const { return this->first[i].second; }
566 const ValT &value(unsigned i) const { return this->second[i]; }
568 KeyT &start(unsigned i) { return this->first[i].first; }
569 KeyT &stop(unsigned i) { return this->first[i].second; }
570 ValT &value(unsigned i) { return this->second[i]; }
572 /// findFrom - Find the first interval after i that may contain x.
573 /// @param i Starting index for the search.
574 /// @param Size Number of elements in node.
575 /// @param x Key to search for.
576 /// @return First index with !stopLess(key[i].stop, x), or size.
577 /// This is the first interval that can possibly contain x.
578 unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
579 assert(i <= Size && Size <= N && "Bad indices");
580 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
581 "Index is past the needed point");
582 while (i != Size && Traits::stopLess(stop(i), x)) ++i;
586 /// safeFind - Find an interval that is known to exist. This is the same as
587 /// findFrom except is it assumed that x is at least within range of the last
589 /// @param i Starting index for the search.
590 /// @param x Key to search for.
591 /// @return First index with !stopLess(key[i].stop, x), never size.
592 /// This is the first interval that can possibly contain x.
593 unsigned safeFind(unsigned i, KeyT x) const {
594 assert(i < N && "Bad index");
595 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
596 "Index is past the needed point");
597 while (Traits::stopLess(stop(i), x)) ++i;
598 assert(i < N && "Unsafe intervals");
602 /// safeLookup - Lookup mapped value for a safe key.
603 /// It is assumed that x is within range of the last entry.
604 /// @param x Key to search for.
605 /// @param NotFound Value to return if x is not in any interval.
606 /// @return The mapped value at x or NotFound.
607 ValT safeLookup(KeyT x, ValT NotFound) const {
608 unsigned i = safeFind(0, x);
609 return Traits::startLess(x, start(i)) ? NotFound : value(i);
612 unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y);
615 /// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as
616 /// possible. This may cause the node to grow by 1, or it may cause the node
617 /// to shrink because of coalescing.
618 /// @param Pos Starting index = insertFrom(0, size, a)
619 /// @param Size Number of elements in node.
620 /// @param a Interval start.
621 /// @param b Interval stop.
622 /// @param y Value be mapped.
623 /// @return (insert position, new size), or (i, Capacity+1) on overflow.
624 template <typename KeyT, typename ValT, unsigned N, typename Traits>
625 unsigned LeafNode<KeyT, ValT, N, Traits>::
626 insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y) {
628 assert(i <= Size && Size <= N && "Invalid index");
629 assert(!Traits::stopLess(b, a) && "Invalid interval");
631 // Verify the findFrom invariant.
632 assert((i == 0 || Traits::stopLess(stop(i - 1), a)));
633 assert((i == Size || !Traits::stopLess(stop(i), a)));
634 assert((i == Size || Traits::stopLess(b, start(i))) && "Overlapping insert");
636 // Coalesce with previous interval.
637 if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a)) {
639 // Also coalesce with next interval?
640 if (i != Size && value(i) == y && Traits::adjacent(b, start(i))) {
641 stop(i - 1) = stop(i);
642 this->erase(i, Size);
653 // Add new interval at end.
661 // Try to coalesce with following interval.
662 if (value(i) == y && Traits::adjacent(b, start(i))) {
667 // We must insert before i. Detect overflow.
672 this->shift(i, Size);
679 //===----------------------------------------------------------------------===//
680 //--- IntervalMapImpl::BranchNode ---//
681 //===----------------------------------------------------------------------===//
683 // A branch node stores references to 1--N subtrees all of the same height.
685 // The key array in a branch node holds the rightmost stop key of each subtree.
686 // It is redundant to store the last stop key since it can be found in the
687 // parent node, but doing so makes tree balancing a lot simpler.
689 // It is unusual for a branch node to only have one subtree, but it can happen
690 // in the root node if it is smaller than the normal nodes.
692 // When all of the leaf nodes from all the subtrees are concatenated, they must
693 // satisfy the same constraints as a single leaf node. They must be sorted,
694 // sane, and fully coalesced.
696 //===----------------------------------------------------------------------===//
698 template <typename KeyT, typename ValT, unsigned N, typename Traits>
699 class BranchNode : public NodeBase<NodeRef, KeyT, N> {
701 const KeyT &stop(unsigned i) const { return this->second[i]; }
702 const NodeRef &subtree(unsigned i) const { return this->first[i]; }
704 KeyT &stop(unsigned i) { return this->second[i]; }
705 NodeRef &subtree(unsigned i) { return this->first[i]; }
707 /// findFrom - Find the first subtree after i that may contain x.
708 /// @param i Starting index for the search.
709 /// @param Size Number of elements in node.
710 /// @param x Key to search for.
711 /// @return First index with !stopLess(key[i], x), or size.
712 /// This is the first subtree that can possibly contain x.
713 unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
714 assert(i <= Size && Size <= N && "Bad indices");
715 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
716 "Index to findFrom is past the needed point");
717 while (i != Size && Traits::stopLess(stop(i), x)) ++i;
721 /// safeFind - Find a subtree that is known to exist. This is the same as
722 /// findFrom except is it assumed that x is in range.
723 /// @param i Starting index for the search.
724 /// @param x Key to search for.
725 /// @return First index with !stopLess(key[i], x), never size.
726 /// This is the first subtree that can possibly contain x.
727 unsigned safeFind(unsigned i, KeyT x) const {
728 assert(i < N && "Bad index");
729 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
730 "Index is past the needed point");
731 while (Traits::stopLess(stop(i), x)) ++i;
732 assert(i < N && "Unsafe intervals");
736 /// safeLookup - Get the subtree containing x, Assuming that x is in range.
737 /// @param x Key to search for.
738 /// @return Subtree containing x
739 NodeRef safeLookup(KeyT x) const {
740 return subtree(safeFind(0, x));
743 /// insert - Insert a new (subtree, stop) pair.
744 /// @param i Insert position, following entries will be shifted.
745 /// @param Size Number of elements in node.
746 /// @param Node Subtree to insert.
747 /// @param Stop Last key in subtree.
748 void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop) {
749 assert(Size < N && "branch node overflow");
750 assert(i <= Size && "Bad insert position");
751 this->shift(i, Size);
757 //===----------------------------------------------------------------------===//
758 //--- IntervalMapImpl::Path ---//
759 //===----------------------------------------------------------------------===//
761 // A Path is used by iterators to represent a position in a B+-tree, and the
762 // path to get there from the root.
764 // The Path class also contains the tree navigation code that doesn't have to
767 //===----------------------------------------------------------------------===//
770 /// Entry - Each step in the path is a node pointer and an offset into that
777 Entry(void *Node, unsigned Size, unsigned Offset)
778 : node(Node), size(Size), offset(Offset) {}
780 Entry(NodeRef Node, unsigned Offset)
781 : node(&Node.subtree(0)), size(Node.size()), offset(Offset) {}
783 NodeRef &subtree(unsigned i) const {
784 return reinterpret_cast<NodeRef*>(node)[i];
788 /// path - The path entries, path[0] is the root node, path.back() is a leaf.
789 SmallVector<Entry, 4> path;
793 template <typename NodeT> NodeT &node(unsigned Level) const {
794 return *reinterpret_cast<NodeT*>(path[Level].node);
796 unsigned size(unsigned Level) const { return path[Level].size; }
797 unsigned offset(unsigned Level) const { return path[Level].offset; }
798 unsigned &offset(unsigned Level) { return path[Level].offset; }
801 template <typename NodeT> NodeT &leaf() const {
802 return *reinterpret_cast<NodeT*>(path.back().node);
804 unsigned leafSize() const { return path.back().size; }
805 unsigned leafOffset() const { return path.back().offset; }
806 unsigned &leafOffset() { return path.back().offset; }
808 /// valid - Return true if path is at a valid node, not at end().
810 return !path.empty() && path.front().offset < path.front().size;
813 /// height - Return the height of the tree corresponding to this path.
814 /// This matches map->height in a full path.
815 unsigned height() const { return path.size() - 1; }
817 /// subtree - Get the subtree referenced from Level. When the path is
818 /// consistent, node(Level + 1) == subtree(Level).
819 /// @param Level 0..height-1. The leaves have no subtrees.
820 NodeRef &subtree(unsigned Level) const {
821 return path[Level].subtree(path[Level].offset);
824 /// reset - Reset cached information about node(Level) from subtree(Level -1).
825 /// @param Level 1..height. THe node to update after parent node changed.
826 void reset(unsigned Level) {
827 path[Level] = Entry(subtree(Level - 1), offset(Level));
830 /// push - Add entry to path.
831 /// @param Node Node to add, should be subtree(path.size()-1).
832 /// @param Offset Offset into Node.
833 void push(NodeRef Node, unsigned Offset) {
834 path.push_back(Entry(Node, Offset));
837 /// pop - Remove the last path entry.
842 /// setSize - Set the size of a node both in the path and in the tree.
843 /// @param Level 0..height. Note that setting the root size won't change
845 /// @param Size New node size.
846 void setSize(unsigned Level, unsigned Size) {
847 path[Level].size = Size;
849 subtree(Level - 1).setSize(Size);
852 /// setRoot - Clear the path and set a new root node.
853 /// @param Node New root node.
854 /// @param Size New root size.
855 /// @param Offset Offset into root node.
856 void setRoot(void *Node, unsigned Size, unsigned Offset) {
858 path.push_back(Entry(Node, Size, Offset));
861 /// replaceRoot - Replace the current root node with two new entries after the
862 /// tree height has increased.
863 /// @param Root The new root node.
864 /// @param Size Number of entries in the new root.
865 /// @param Offsets Offsets into the root and first branch nodes.
866 void replaceRoot(void *Root, unsigned Size, IdxPair Offsets);
868 /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
869 /// @param Level Get the sibling to node(Level).
870 /// @return Left sibling, or NodeRef().
871 NodeRef getLeftSibling(unsigned Level) const;
873 /// moveLeft - Move path to the left sibling at Level. Leave nodes below Level
875 /// @param Level Move node(Level).
876 void moveLeft(unsigned Level);
878 /// fillLeft - Grow path to Height by taking leftmost branches.
879 /// @param Height The target height.
880 void fillLeft(unsigned Height) {
881 while (height() < Height)
882 push(subtree(height()), 0);
885 /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
886 /// @param Level Get the sinbling to node(Level).
887 /// @return Left sibling, or NodeRef().
888 NodeRef getRightSibling(unsigned Level) const;
890 /// moveRight - Move path to the left sibling at Level. Leave nodes below
892 /// @param Level Move node(Level).
893 void moveRight(unsigned Level);
895 /// atBegin - Return true if path is at begin().
896 bool atBegin() const {
897 for (unsigned i = 0, e = path.size(); i != e; ++i)
898 if (path[i].offset != 0)
903 /// atLastEntry - Return true if the path is at the last entry of the node at
905 /// @param Level Node to examine.
906 bool atLastEntry(unsigned Level) const {
907 return path[Level].offset == path[Level].size - 1;
910 /// legalizeForInsert - Prepare the path for an insertion at Level. When the
911 /// path is at end(), node(Level) may not be a legal node. legalizeForInsert
912 /// ensures that node(Level) is real by moving back to the last node at Level,
913 /// and setting offset(Level) to size(Level) if required.
914 /// @param Level The level where an insertion is about to take place.
915 void legalizeForInsert(unsigned Level) {
919 ++path[Level].offset;
923 } // end namespace IntervalMapImpl
925 //===----------------------------------------------------------------------===//
926 //--- IntervalMap ----//
927 //===----------------------------------------------------------------------===//
929 template <typename KeyT, typename ValT,
930 unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize,
931 typename Traits = IntervalMapInfo<KeyT>>
933 typedef IntervalMapImpl::NodeSizer<KeyT, ValT> Sizer;
934 typedef IntervalMapImpl::LeafNode<KeyT, ValT, Sizer::LeafSize, Traits> Leaf;
935 typedef IntervalMapImpl::BranchNode<KeyT, ValT, Sizer::BranchSize, Traits>
937 typedef IntervalMapImpl::LeafNode<KeyT, ValT, N, Traits> RootLeaf;
938 typedef IntervalMapImpl::IdxPair IdxPair;
940 // The RootLeaf capacity is given as a template parameter. We must compute the
941 // corresponding RootBranch capacity.
943 DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) /
944 (sizeof(KeyT) + sizeof(IntervalMapImpl::NodeRef)),
945 RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1
948 typedef IntervalMapImpl::BranchNode<KeyT, ValT, RootBranchCap, Traits>
951 // When branched, we store a global start key as well as the branch node.
952 struct RootBranchData {
958 typedef typename Sizer::Allocator Allocator;
959 typedef KeyT KeyType;
960 typedef ValT ValueType;
961 typedef Traits KeyTraits;
964 // The root data is either a RootLeaf or a RootBranchData instance.
965 AlignedCharArrayUnion<RootLeaf, RootBranchData> data;
968 // 0: Leaves in root.
969 // 1: Root points to leaf.
970 // 2: root->branch->leaf ...
973 // Number of entries in the root node.
976 // Allocator used for creating external nodes.
977 Allocator &allocator;
979 /// dataAs - Represent data as a node type without breaking aliasing rules.
980 template <typename T>
990 const RootLeaf &rootLeaf() const {
991 assert(!branched() && "Cannot acces leaf data in branched root");
992 return dataAs<RootLeaf>();
994 RootLeaf &rootLeaf() {
995 assert(!branched() && "Cannot acces leaf data in branched root");
996 return dataAs<RootLeaf>();
999 RootBranchData &rootBranchData() const {
1000 assert(branched() && "Cannot access branch data in non-branched root");
1001 return dataAs<RootBranchData>();
1003 RootBranchData &rootBranchData() {
1004 assert(branched() && "Cannot access branch data in non-branched root");
1005 return dataAs<RootBranchData>();
1008 const RootBranch &rootBranch() const { return rootBranchData().node; }
1009 RootBranch &rootBranch() { return rootBranchData().node; }
1010 KeyT rootBranchStart() const { return rootBranchData().start; }
1011 KeyT &rootBranchStart() { return rootBranchData().start; }
1013 template <typename NodeT> NodeT *newNode() {
1014 return new(allocator.template Allocate<NodeT>()) NodeT();
1017 template <typename NodeT> void deleteNode(NodeT *P) {
1019 allocator.Deallocate(P);
1022 IdxPair branchRoot(unsigned Position);
1023 IdxPair splitRoot(unsigned Position);
1025 void switchRootToBranch() {
1026 rootLeaf().~RootLeaf();
1028 new (&rootBranchData()) RootBranchData();
1031 void switchRootToLeaf() {
1032 rootBranchData().~RootBranchData();
1034 new(&rootLeaf()) RootLeaf();
1037 bool branched() const { return height > 0; }
1039 ValT treeSafeLookup(KeyT x, ValT NotFound) const;
1040 void visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef,
1042 void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level);
1045 explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) {
1046 assert((uintptr_t(data.buffer) & (alignof(RootLeaf) - 1)) == 0 &&
1047 "Insufficient alignment");
1048 new(&rootLeaf()) RootLeaf();
1053 rootLeaf().~RootLeaf();
1056 /// empty - Return true when no intervals are mapped.
1057 bool empty() const {
1058 return rootSize == 0;
1061 /// start - Return the smallest mapped key in a non-empty map.
1062 KeyT start() const {
1063 assert(!empty() && "Empty IntervalMap has no start");
1064 return !branched() ? rootLeaf().start(0) : rootBranchStart();
1067 /// stop - Return the largest mapped key in a non-empty map.
1069 assert(!empty() && "Empty IntervalMap has no stop");
1070 return !branched() ? rootLeaf().stop(rootSize - 1) :
1071 rootBranch().stop(rootSize - 1);
1074 /// lookup - Return the mapped value at x or NotFound.
1075 ValT lookup(KeyT x, ValT NotFound = ValT()) const {
1076 if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x))
1078 return branched() ? treeSafeLookup(x, NotFound) :
1079 rootLeaf().safeLookup(x, NotFound);
1082 /// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
1083 /// It is assumed that no key in the interval is mapped to another value, but
1084 /// overlapping intervals already mapped to y will be coalesced.
1085 void insert(KeyT a, KeyT b, ValT y) {
1086 if (branched() || rootSize == RootLeaf::Capacity)
1087 return find(a).insert(a, b, y);
1089 // Easy insert into root leaf.
1090 unsigned p = rootLeaf().findFrom(0, rootSize, a);
1091 rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y);
1094 /// clear - Remove all entries.
1097 class const_iterator;
1099 friend class const_iterator;
1100 friend class iterator;
1102 const_iterator begin() const {
1103 const_iterator I(*this);
1114 const_iterator end() const {
1115 const_iterator I(*this);
1126 /// find - Return an iterator pointing to the first interval ending at or
1127 /// after x, or end().
1128 const_iterator find(KeyT x) const {
1129 const_iterator I(*this);
1134 iterator find(KeyT x) {
1141 /// treeSafeLookup - Return the mapped value at x or NotFound, assuming a
1143 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1144 ValT IntervalMap<KeyT, ValT, N, Traits>::
1145 treeSafeLookup(KeyT x, ValT NotFound) const {
1146 assert(branched() && "treeLookup assumes a branched root");
1148 IntervalMapImpl::NodeRef NR = rootBranch().safeLookup(x);
1149 for (unsigned h = height-1; h; --h)
1150 NR = NR.get<Branch>().safeLookup(x);
1151 return NR.get<Leaf>().safeLookup(x, NotFound);
1154 // branchRoot - Switch from a leaf root to a branched root.
1155 // Return the new (root offset, node offset) corresponding to Position.
1156 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1157 IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
1158 branchRoot(unsigned Position) {
1159 using namespace IntervalMapImpl;
1160 // How many external leaf nodes to hold RootLeaf+1?
1161 const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1;
1163 // Compute element distribution among new nodes.
1164 unsigned size[Nodes];
1165 IdxPair NewOffset(0, Position);
1167 // Is is very common for the root node to be smaller than external nodes.
1171 NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, nullptr, size,
1174 // Allocate new nodes.
1176 NodeRef node[Nodes];
1177 for (unsigned n = 0; n != Nodes; ++n) {
1178 Leaf *L = newNode<Leaf>();
1179 L->copy(rootLeaf(), pos, 0, size[n]);
1180 node[n] = NodeRef(L, size[n]);
1184 // Destroy the old leaf node, construct branch node instead.
1185 switchRootToBranch();
1186 for (unsigned n = 0; n != Nodes; ++n) {
1187 rootBranch().stop(n) = node[n].template get<Leaf>().stop(size[n]-1);
1188 rootBranch().subtree(n) = node[n];
1190 rootBranchStart() = node[0].template get<Leaf>().start(0);
1195 // splitRoot - Split the current BranchRoot into multiple Branch nodes.
1196 // Return the new (root offset, node offset) corresponding to Position.
1197 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1198 IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
1199 splitRoot(unsigned Position) {
1200 using namespace IntervalMapImpl;
1201 // How many external leaf nodes to hold RootBranch+1?
1202 const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1;
1204 // Compute element distribution among new nodes.
1205 unsigned Size[Nodes];
1206 IdxPair NewOffset(0, Position);
1208 // Is is very common for the root node to be smaller than external nodes.
1212 NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, nullptr, Size,
1215 // Allocate new nodes.
1217 NodeRef Node[Nodes];
1218 for (unsigned n = 0; n != Nodes; ++n) {
1219 Branch *B = newNode<Branch>();
1220 B->copy(rootBranch(), Pos, 0, Size[n]);
1221 Node[n] = NodeRef(B, Size[n]);
1225 for (unsigned n = 0; n != Nodes; ++n) {
1226 rootBranch().stop(n) = Node[n].template get<Branch>().stop(Size[n]-1);
1227 rootBranch().subtree(n) = Node[n];
1234 /// visitNodes - Visit each external node.
1235 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1236 void IntervalMap<KeyT, ValT, N, Traits>::
1237 visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, unsigned Height)) {
1240 SmallVector<IntervalMapImpl::NodeRef, 4> Refs, NextRefs;
1242 // Collect level 0 nodes from the root.
1243 for (unsigned i = 0; i != rootSize; ++i)
1244 Refs.push_back(rootBranch().subtree(i));
1246 // Visit all branch nodes.
1247 for (unsigned h = height - 1; h; --h) {
1248 for (unsigned i = 0, e = Refs.size(); i != e; ++i) {
1249 for (unsigned j = 0, s = Refs[i].size(); j != s; ++j)
1250 NextRefs.push_back(Refs[i].subtree(j));
1251 (this->*f)(Refs[i], h);
1254 Refs.swap(NextRefs);
1257 // Visit all leaf nodes.
1258 for (unsigned i = 0, e = Refs.size(); i != e; ++i)
1259 (this->*f)(Refs[i], 0);
1262 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1263 void IntervalMap<KeyT, ValT, N, Traits>::
1264 deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) {
1266 deleteNode(&Node.get<Branch>());
1268 deleteNode(&Node.get<Leaf>());
1271 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1272 void IntervalMap<KeyT, ValT, N, Traits>::
1275 visitNodes(&IntervalMap::deleteNode);
1281 //===----------------------------------------------------------------------===//
1282 //--- IntervalMap::const_iterator ----//
1283 //===----------------------------------------------------------------------===//
1285 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1286 class IntervalMap<KeyT, ValT, N, Traits>::const_iterator :
1287 public std::iterator<std::bidirectional_iterator_tag, ValT> {
1290 friend class IntervalMap;
1292 // The map referred to.
1295 // We store a full path from the root to the current position.
1296 // The path may be partially filled, but never between iterator calls.
1297 IntervalMapImpl::Path path;
1299 explicit const_iterator(const IntervalMap &map) :
1300 map(const_cast<IntervalMap*>(&map)) {}
1302 bool branched() const {
1303 assert(map && "Invalid iterator");
1304 return map->branched();
1307 void setRoot(unsigned Offset) {
1309 path.setRoot(&map->rootBranch(), map->rootSize, Offset);
1311 path.setRoot(&map->rootLeaf(), map->rootSize, Offset);
1314 void pathFillFind(KeyT x);
1315 void treeFind(KeyT x);
1316 void treeAdvanceTo(KeyT x);
1318 /// unsafeStart - Writable access to start() for iterator.
1319 KeyT &unsafeStart() const {
1320 assert(valid() && "Cannot access invalid iterator");
1321 return branched() ? path.leaf<Leaf>().start(path.leafOffset()) :
1322 path.leaf<RootLeaf>().start(path.leafOffset());
1325 /// unsafeStop - Writable access to stop() for iterator.
1326 KeyT &unsafeStop() const {
1327 assert(valid() && "Cannot access invalid iterator");
1328 return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) :
1329 path.leaf<RootLeaf>().stop(path.leafOffset());
1332 /// unsafeValue - Writable access to value() for iterator.
1333 ValT &unsafeValue() const {
1334 assert(valid() && "Cannot access invalid iterator");
1335 return branched() ? path.leaf<Leaf>().value(path.leafOffset()) :
1336 path.leaf<RootLeaf>().value(path.leafOffset());
1340 /// const_iterator - Create an iterator that isn't pointing anywhere.
1341 const_iterator() : map(nullptr) {}
1343 /// setMap - Change the map iterated over. This call must be followed by a
1344 /// call to goToBegin(), goToEnd(), or find()
1345 void setMap(const IntervalMap &m) { map = const_cast<IntervalMap*>(&m); }
1347 /// valid - Return true if the current position is valid, false for end().
1348 bool valid() const { return path.valid(); }
1350 /// atBegin - Return true if the current position is the first map entry.
1351 bool atBegin() const { return path.atBegin(); }
1353 /// start - Return the beginning of the current interval.
1354 const KeyT &start() const { return unsafeStart(); }
1356 /// stop - Return the end of the current interval.
1357 const KeyT &stop() const { return unsafeStop(); }
1359 /// value - Return the mapped value at the current interval.
1360 const ValT &value() const { return unsafeValue(); }
1362 const ValT &operator*() const { return value(); }
1364 bool operator==(const const_iterator &RHS) const {
1365 assert(map == RHS.map && "Cannot compare iterators from different maps");
1367 return !RHS.valid();
1368 if (path.leafOffset() != RHS.path.leafOffset())
1370 return &path.template leaf<Leaf>() == &RHS.path.template leaf<Leaf>();
1373 bool operator!=(const const_iterator &RHS) const {
1374 return !operator==(RHS);
1377 /// goToBegin - Move to the first interval in map.
1381 path.fillLeft(map->height);
1384 /// goToEnd - Move beyond the last interval in map.
1386 setRoot(map->rootSize);
1389 /// preincrement - move to the next interval.
1390 const_iterator &operator++() {
1391 assert(valid() && "Cannot increment end()");
1392 if (++path.leafOffset() == path.leafSize() && branched())
1393 path.moveRight(map->height);
1397 /// postincrement - Dont do that!
1398 const_iterator operator++(int) {
1399 const_iterator tmp = *this;
1404 /// predecrement - move to the previous interval.
1405 const_iterator &operator--() {
1406 if (path.leafOffset() && (valid() || !branched()))
1407 --path.leafOffset();
1409 path.moveLeft(map->height);
1413 /// postdecrement - Dont do that!
1414 const_iterator operator--(int) {
1415 const_iterator tmp = *this;
1420 /// find - Move to the first interval with stop >= x, or end().
1421 /// This is a full search from the root, the current position is ignored.
1426 setRoot(map->rootLeaf().findFrom(0, map->rootSize, x));
1429 /// advanceTo - Move to the first interval with stop >= x, or end().
1430 /// The search is started from the current position, and no earlier positions
1431 /// can be found. This is much faster than find() for small moves.
1432 void advanceTo(KeyT x) {
1439 map->rootLeaf().findFrom(path.leafOffset(), map->rootSize, x);
1443 /// pathFillFind - Complete path by searching for x.
1444 /// @param x Key to search for.
1445 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1446 void IntervalMap<KeyT, ValT, N, Traits>::
1447 const_iterator::pathFillFind(KeyT x) {
1448 IntervalMapImpl::NodeRef NR = path.subtree(path.height());
1449 for (unsigned i = map->height - path.height() - 1; i; --i) {
1450 unsigned p = NR.get<Branch>().safeFind(0, x);
1454 path.push(NR, NR.get<Leaf>().safeFind(0, x));
1457 /// treeFind - Find in a branched tree.
1458 /// @param x Key to search for.
1459 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1460 void IntervalMap<KeyT, ValT, N, Traits>::
1461 const_iterator::treeFind(KeyT x) {
1462 setRoot(map->rootBranch().findFrom(0, map->rootSize, x));
1467 /// treeAdvanceTo - Find position after the current one.
1468 /// @param x Key to search for.
1469 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1470 void IntervalMap<KeyT, ValT, N, Traits>::
1471 const_iterator::treeAdvanceTo(KeyT x) {
1472 // Can we stay on the same leaf node?
1473 if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) {
1474 path.leafOffset() = path.leaf<Leaf>().safeFind(path.leafOffset(), x);
1478 // Drop the current leaf.
1481 // Search towards the root for a usable subtree.
1482 if (path.height()) {
1483 for (unsigned l = path.height() - 1; l; --l) {
1484 if (!Traits::stopLess(path.node<Branch>(l).stop(path.offset(l)), x)) {
1485 // The branch node at l+1 is usable
1486 path.offset(l + 1) =
1487 path.node<Branch>(l + 1).safeFind(path.offset(l + 1), x);
1488 return pathFillFind(x);
1492 // Is the level-1 Branch usable?
1493 if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) {
1494 path.offset(1) = path.node<Branch>(1).safeFind(path.offset(1), x);
1495 return pathFillFind(x);
1499 // We reached the root.
1500 setRoot(map->rootBranch().findFrom(path.offset(0), map->rootSize, x));
1505 //===----------------------------------------------------------------------===//
1506 //--- IntervalMap::iterator ----//
1507 //===----------------------------------------------------------------------===//
1509 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1510 class IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator {
1511 friend class IntervalMap;
1512 typedef IntervalMapImpl::IdxPair IdxPair;
1514 explicit iterator(IntervalMap &map) : const_iterator(map) {}
1516 void setNodeStop(unsigned Level, KeyT Stop);
1517 bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop);
1518 template <typename NodeT> bool overflow(unsigned Level);
1519 void treeInsert(KeyT a, KeyT b, ValT y);
1520 void eraseNode(unsigned Level);
1521 void treeErase(bool UpdateRoot = true);
1522 bool canCoalesceLeft(KeyT Start, ValT x);
1523 bool canCoalesceRight(KeyT Stop, ValT x);
1526 /// iterator - Create null iterator.
1527 iterator() = default;
1529 /// setStart - Move the start of the current interval.
1530 /// This may cause coalescing with the previous interval.
1531 /// @param a New start key, must not overlap the previous interval.
1532 void setStart(KeyT a);
1534 /// setStop - Move the end of the current interval.
1535 /// This may cause coalescing with the following interval.
1536 /// @param b New stop key, must not overlap the following interval.
1537 void setStop(KeyT b);
1539 /// setValue - Change the mapped value of the current interval.
1540 /// This may cause coalescing with the previous and following intervals.
1541 /// @param x New value.
1542 void setValue(ValT x);
1544 /// setStartUnchecked - Move the start of the current interval without
1545 /// checking for coalescing or overlaps.
1546 /// This should only be used when it is known that coalescing is not required.
1547 /// @param a New start key.
1548 void setStartUnchecked(KeyT a) { this->unsafeStart() = a; }
1550 /// setStopUnchecked - Move the end of the current interval without checking
1551 /// for coalescing or overlaps.
1552 /// This should only be used when it is known that coalescing is not required.
1553 /// @param b New stop key.
1554 void setStopUnchecked(KeyT b) {
1555 this->unsafeStop() = b;
1556 // Update keys in branch nodes as well.
1557 if (this->path.atLastEntry(this->path.height()))
1558 setNodeStop(this->path.height(), b);
1561 /// setValueUnchecked - Change the mapped value of the current interval
1562 /// without checking for coalescing.
1563 /// @param x New value.
1564 void setValueUnchecked(ValT x) { this->unsafeValue() = x; }
1566 /// insert - Insert mapping [a;b] -> y before the current position.
1567 void insert(KeyT a, KeyT b, ValT y);
1569 /// erase - Erase the current interval.
1572 iterator &operator++() {
1573 const_iterator::operator++();
1577 iterator operator++(int) {
1578 iterator tmp = *this;
1583 iterator &operator--() {
1584 const_iterator::operator--();
1588 iterator operator--(int) {
1589 iterator tmp = *this;
1595 /// canCoalesceLeft - Can the current interval coalesce to the left after
1596 /// changing start or value?
1597 /// @param Start New start of current interval.
1598 /// @param Value New value for current interval.
1599 /// @return True when updating the current interval would enable coalescing.
1600 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1601 bool IntervalMap<KeyT, ValT, N, Traits>::
1602 iterator::canCoalesceLeft(KeyT Start, ValT Value) {
1603 using namespace IntervalMapImpl;
1604 Path &P = this->path;
1605 if (!this->branched()) {
1606 unsigned i = P.leafOffset();
1607 RootLeaf &Node = P.leaf<RootLeaf>();
1608 return i && Node.value(i-1) == Value &&
1609 Traits::adjacent(Node.stop(i-1), Start);
1612 if (unsigned i = P.leafOffset()) {
1613 Leaf &Node = P.leaf<Leaf>();
1614 return Node.value(i-1) == Value && Traits::adjacent(Node.stop(i-1), Start);
1615 } else if (NodeRef NR = P.getLeftSibling(P.height())) {
1616 unsigned i = NR.size() - 1;
1617 Leaf &Node = NR.get<Leaf>();
1618 return Node.value(i) == Value && Traits::adjacent(Node.stop(i), Start);
1623 /// canCoalesceRight - Can the current interval coalesce to the right after
1624 /// changing stop or value?
1625 /// @param Stop New stop of current interval.
1626 /// @param Value New value for current interval.
1627 /// @return True when updating the current interval would enable coalescing.
1628 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1629 bool IntervalMap<KeyT, ValT, N, Traits>::
1630 iterator::canCoalesceRight(KeyT Stop, ValT Value) {
1631 using namespace IntervalMapImpl;
1632 Path &P = this->path;
1633 unsigned i = P.leafOffset() + 1;
1634 if (!this->branched()) {
1635 if (i >= P.leafSize())
1637 RootLeaf &Node = P.leaf<RootLeaf>();
1638 return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));
1641 if (i < P.leafSize()) {
1642 Leaf &Node = P.leaf<Leaf>();
1643 return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));
1644 } else if (NodeRef NR = P.getRightSibling(P.height())) {
1645 Leaf &Node = NR.get<Leaf>();
1646 return Node.value(0) == Value && Traits::adjacent(Stop, Node.start(0));
1651 /// setNodeStop - Update the stop key of the current node at level and above.
1652 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1653 void IntervalMap<KeyT, ValT, N, Traits>::
1654 iterator::setNodeStop(unsigned Level, KeyT Stop) {
1655 // There are no references to the root node, so nothing to update.
1658 IntervalMapImpl::Path &P = this->path;
1659 // Update nodes pointing to the current node.
1661 P.node<Branch>(Level).stop(P.offset(Level)) = Stop;
1662 if (!P.atLastEntry(Level))
1665 // Update root separately since it has a different layout.
1666 P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop;
1669 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1670 void IntervalMap<KeyT, ValT, N, Traits>::
1671 iterator::setStart(KeyT a) {
1672 assert(Traits::nonEmpty(a, this->stop()) && "Cannot move start beyond stop");
1673 KeyT &CurStart = this->unsafeStart();
1674 if (!Traits::startLess(a, CurStart) || !canCoalesceLeft(a, this->value())) {
1678 // Coalesce with the interval to the left.
1682 setStartUnchecked(a);
1685 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1686 void IntervalMap<KeyT, ValT, N, Traits>::
1687 iterator::setStop(KeyT b) {
1688 assert(Traits::nonEmpty(this->start(), b) && "Cannot move stop beyond start");
1689 if (Traits::startLess(b, this->stop()) ||
1690 !canCoalesceRight(b, this->value())) {
1691 setStopUnchecked(b);
1694 // Coalesce with interval to the right.
1695 KeyT a = this->start();
1697 setStartUnchecked(a);
1700 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1701 void IntervalMap<KeyT, ValT, N, Traits>::
1702 iterator::setValue(ValT x) {
1703 setValueUnchecked(x);
1704 if (canCoalesceRight(this->stop(), x)) {
1705 KeyT a = this->start();
1707 setStartUnchecked(a);
1709 if (canCoalesceLeft(this->start(), x)) {
1711 KeyT a = this->start();
1713 setStartUnchecked(a);
1717 /// insertNode - insert a node before the current path at level.
1718 /// Leave the current path pointing at the new node.
1719 /// @param Level path index of the node to be inserted.
1720 /// @param Node The node to be inserted.
1721 /// @param Stop The last index in the new node.
1722 /// @return True if the tree height was increased.
1723 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1724 bool IntervalMap<KeyT, ValT, N, Traits>::
1725 iterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) {
1726 assert(Level && "Cannot insert next to the root");
1727 bool SplitRoot = false;
1728 IntervalMap &IM = *this->map;
1729 IntervalMapImpl::Path &P = this->path;
1732 // Insert into the root branch node.
1733 if (IM.rootSize < RootBranch::Capacity) {
1734 IM.rootBranch().insert(P.offset(0), IM.rootSize, Node, Stop);
1735 P.setSize(0, ++IM.rootSize);
1740 // We need to split the root while keeping our position.
1742 IdxPair Offset = IM.splitRoot(P.offset(0));
1743 P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset);
1745 // Fall through to insert at the new higher level.
1749 // When inserting before end(), make sure we have a valid path.
1750 P.legalizeForInsert(--Level);
1752 // Insert into the branch node at Level-1.
1753 if (P.size(Level) == Branch::Capacity) {
1754 // Branch node is full, handle handle the overflow.
1755 assert(!SplitRoot && "Cannot overflow after splitting the root");
1756 SplitRoot = overflow<Branch>(Level);
1759 P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop);
1760 P.setSize(Level, P.size(Level) + 1);
1761 if (P.atLastEntry(Level))
1762 setNodeStop(Level, Stop);
1768 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1769 void IntervalMap<KeyT, ValT, N, Traits>::
1770 iterator::insert(KeyT a, KeyT b, ValT y) {
1771 if (this->branched())
1772 return treeInsert(a, b, y);
1773 IntervalMap &IM = *this->map;
1774 IntervalMapImpl::Path &P = this->path;
1776 // Try simple root leaf insert.
1777 unsigned Size = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y);
1779 // Was the root node insert successful?
1780 if (Size <= RootLeaf::Capacity) {
1781 P.setSize(0, IM.rootSize = Size);
1785 // Root leaf node is full, we must branch.
1786 IdxPair Offset = IM.branchRoot(P.leafOffset());
1787 P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset);
1789 // Now it fits in the new leaf.
1790 treeInsert(a, b, y);
1793 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1794 void IntervalMap<KeyT, ValT, N, Traits>::
1795 iterator::treeInsert(KeyT a, KeyT b, ValT y) {
1796 using namespace IntervalMapImpl;
1797 Path &P = this->path;
1800 P.legalizeForInsert(this->map->height);
1802 // Check if this insertion will extend the node to the left.
1803 if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<Leaf>().start(0))) {
1804 // Node is growing to the left, will it affect a left sibling node?
1805 if (NodeRef Sib = P.getLeftSibling(P.height())) {
1806 Leaf &SibLeaf = Sib.get<Leaf>();
1807 unsigned SibOfs = Sib.size() - 1;
1808 if (SibLeaf.value(SibOfs) == y &&
1809 Traits::adjacent(SibLeaf.stop(SibOfs), a)) {
1810 // This insertion will coalesce with the last entry in SibLeaf. We can
1811 // handle it in two ways:
1812 // 1. Extend SibLeaf.stop to b and be done, or
1813 // 2. Extend a to SibLeaf, erase the SibLeaf entry and continue.
1814 // We prefer 1., but need 2 when coalescing to the right as well.
1815 Leaf &CurLeaf = P.leaf<Leaf>();
1816 P.moveLeft(P.height());
1817 if (Traits::stopLess(b, CurLeaf.start(0)) &&
1818 (y != CurLeaf.value(0) || !Traits::adjacent(b, CurLeaf.start(0)))) {
1819 // Easy, just extend SibLeaf and we're done.
1820 setNodeStop(P.height(), SibLeaf.stop(SibOfs) = b);
1823 // We have both left and right coalescing. Erase the old SibLeaf entry
1824 // and continue inserting the larger interval.
1825 a = SibLeaf.start(SibOfs);
1826 treeErase(/* UpdateRoot= */false);
1830 // No left sibling means we are at begin(). Update cached bound.
1831 this->map->rootBranchStart() = a;
1835 // When we are inserting at the end of a leaf node, we must update stops.
1836 unsigned Size = P.leafSize();
1837 bool Grow = P.leafOffset() == Size;
1838 Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), Size, a, b, y);
1840 // Leaf insertion unsuccessful? Overflow and try again.
1841 if (Size > Leaf::Capacity) {
1842 overflow<Leaf>(P.height());
1843 Grow = P.leafOffset() == P.leafSize();
1844 Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y);
1845 assert(Size <= Leaf::Capacity && "overflow() didn't make room");
1848 // Inserted, update offset and leaf size.
1849 P.setSize(P.height(), Size);
1851 // Insert was the last node entry, update stops.
1853 setNodeStop(P.height(), b);
1856 /// erase - erase the current interval and move to the next position.
1857 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1858 void IntervalMap<KeyT, ValT, N, Traits>::
1860 IntervalMap &IM = *this->map;
1861 IntervalMapImpl::Path &P = this->path;
1862 assert(P.valid() && "Cannot erase end()");
1863 if (this->branched())
1865 IM.rootLeaf().erase(P.leafOffset(), IM.rootSize);
1866 P.setSize(0, --IM.rootSize);
1869 /// treeErase - erase() for a branched tree.
1870 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1871 void IntervalMap<KeyT, ValT, N, Traits>::
1872 iterator::treeErase(bool UpdateRoot) {
1873 IntervalMap &IM = *this->map;
1874 IntervalMapImpl::Path &P = this->path;
1875 Leaf &Node = P.leaf<Leaf>();
1877 // Nodes are not allowed to become empty.
1878 if (P.leafSize() == 1) {
1879 IM.deleteNode(&Node);
1880 eraseNode(IM.height);
1881 // Update rootBranchStart if we erased begin().
1882 if (UpdateRoot && IM.branched() && P.valid() && P.atBegin())
1883 IM.rootBranchStart() = P.leaf<Leaf>().start(0);
1887 // Erase current entry.
1888 Node.erase(P.leafOffset(), P.leafSize());
1889 unsigned NewSize = P.leafSize() - 1;
1890 P.setSize(IM.height, NewSize);
1891 // When we erase the last entry, update stop and move to a legal position.
1892 if (P.leafOffset() == NewSize) {
1893 setNodeStop(IM.height, Node.stop(NewSize - 1));
1894 P.moveRight(IM.height);
1895 } else if (UpdateRoot && P.atBegin())
1896 IM.rootBranchStart() = P.leaf<Leaf>().start(0);
1899 /// eraseNode - Erase the current node at Level from its parent and move path to
1900 /// the first entry of the next sibling node.
1901 /// The node must be deallocated by the caller.
1902 /// @param Level 1..height, the root node cannot be erased.
1903 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1904 void IntervalMap<KeyT, ValT, N, Traits>::
1905 iterator::eraseNode(unsigned Level) {
1906 assert(Level && "Cannot erase root node");
1907 IntervalMap &IM = *this->map;
1908 IntervalMapImpl::Path &P = this->path;
1911 IM.rootBranch().erase(P.offset(0), IM.rootSize);
1912 P.setSize(0, --IM.rootSize);
1913 // If this cleared the root, switch to height=0.
1915 IM.switchRootToLeaf();
1920 // Remove node ref from branch node at Level.
1921 Branch &Parent = P.node<Branch>(Level);
1922 if (P.size(Level) == 1) {
1923 // Branch node became empty, remove it recursively.
1924 IM.deleteNode(&Parent);
1927 // Branch node won't become empty.
1928 Parent.erase(P.offset(Level), P.size(Level));
1929 unsigned NewSize = P.size(Level) - 1;
1930 P.setSize(Level, NewSize);
1931 // If we removed the last branch, update stop and move to a legal pos.
1932 if (P.offset(Level) == NewSize) {
1933 setNodeStop(Level, Parent.stop(NewSize - 1));
1938 // Update path cache for the new right sibling position.
1941 P.offset(Level + 1) = 0;
1945 /// overflow - Distribute entries of the current node evenly among
1946 /// its siblings and ensure that the current node is not full.
1947 /// This may require allocating a new node.
1948 /// @tparam NodeT The type of node at Level (Leaf or Branch).
1949 /// @param Level path index of the overflowing node.
1950 /// @return True when the tree height was changed.
1951 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1952 template <typename NodeT>
1953 bool IntervalMap<KeyT, ValT, N, Traits>::
1954 iterator::overflow(unsigned Level) {
1955 using namespace IntervalMapImpl;
1956 Path &P = this->path;
1957 unsigned CurSize[4];
1960 unsigned Elements = 0;
1961 unsigned Offset = P.offset(Level);
1963 // Do we have a left sibling?
1964 NodeRef LeftSib = P.getLeftSibling(Level);
1966 Offset += Elements = CurSize[Nodes] = LeftSib.size();
1967 Node[Nodes++] = &LeftSib.get<NodeT>();
1971 Elements += CurSize[Nodes] = P.size(Level);
1972 Node[Nodes++] = &P.node<NodeT>(Level);
1974 // Do we have a right sibling?
1975 NodeRef RightSib = P.getRightSibling(Level);
1977 Elements += CurSize[Nodes] = RightSib.size();
1978 Node[Nodes++] = &RightSib.get<NodeT>();
1981 // Do we need to allocate a new node?
1982 unsigned NewNode = 0;
1983 if (Elements + 1 > Nodes * NodeT::Capacity) {
1984 // Insert NewNode at the penultimate position, or after a single node.
1985 NewNode = Nodes == 1 ? 1 : Nodes - 1;
1986 CurSize[Nodes] = CurSize[NewNode];
1987 Node[Nodes] = Node[NewNode];
1988 CurSize[NewNode] = 0;
1989 Node[NewNode] = this->map->template newNode<NodeT>();
1993 // Compute the new element distribution.
1994 unsigned NewSize[4];
1995 IdxPair NewOffset = distribute(Nodes, Elements, NodeT::Capacity,
1996 CurSize, NewSize, Offset, true);
1997 adjustSiblingSizes(Node, Nodes, CurSize, NewSize);
1999 // Move current location to the leftmost node.
2003 // Elements have been rearranged, now update node sizes and stops.
2004 bool SplitRoot = false;
2007 KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1);
2008 if (NewNode && Pos == NewNode) {
2009 SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop);
2012 P.setSize(Level, NewSize[Pos]);
2013 setNodeStop(Level, Stop);
2015 if (Pos + 1 == Nodes)
2021 // Where was I? Find NewOffset.
2022 while(Pos != NewOffset.first) {
2026 P.offset(Level) = NewOffset.second;
2030 //===----------------------------------------------------------------------===//
2031 //--- IntervalMapOverlaps ----//
2032 //===----------------------------------------------------------------------===//
2034 /// IntervalMapOverlaps - Iterate over the overlaps of mapped intervals in two
2035 /// IntervalMaps. The maps may be different, but the KeyT and Traits types
2036 /// should be the same.
2040 /// 1. Test for overlap:
2041 /// bool overlap = IntervalMapOverlaps(a, b).valid();
2043 /// 2. Enumerate overlaps:
2044 /// for (IntervalMapOverlaps I(a, b); I.valid() ; ++I) { ... }
2046 template <typename MapA, typename MapB>
2047 class IntervalMapOverlaps {
2048 typedef typename MapA::KeyType KeyType;
2049 typedef typename MapA::KeyTraits Traits;
2050 typename MapA::const_iterator posA;
2051 typename MapB::const_iterator posB;
2053 /// advance - Move posA and posB forward until reaching an overlap, or until
2054 /// either meets end.
2055 /// Don't move the iterators if they are already overlapping.
2060 if (Traits::stopLess(posA.stop(), posB.start())) {
2061 // A ends before B begins. Catch up.
2062 posA.advanceTo(posB.start());
2063 if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
2065 } else if (Traits::stopLess(posB.stop(), posA.start())) {
2066 // B ends before A begins. Catch up.
2067 posB.advanceTo(posA.start());
2068 if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
2071 // Already overlapping.
2075 // Make a.end > b.start.
2076 posA.advanceTo(posB.start());
2077 if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
2079 // Make b.end > a.start.
2080 posB.advanceTo(posA.start());
2081 if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
2087 /// IntervalMapOverlaps - Create an iterator for the overlaps of a and b.
2088 IntervalMapOverlaps(const MapA &a, const MapB &b)
2089 : posA(b.empty() ? a.end() : a.find(b.start())),
2090 posB(posA.valid() ? b.find(posA.start()) : b.end()) { advance(); }
2092 /// valid - Return true if iterator is at an overlap.
2093 bool valid() const {
2094 return posA.valid() && posB.valid();
2097 /// a - access the left hand side in the overlap.
2098 const typename MapA::const_iterator &a() const { return posA; }
2100 /// b - access the right hand side in the overlap.
2101 const typename MapB::const_iterator &b() const { return posB; }
2103 /// start - Beginning of the overlapping interval.
2104 KeyType start() const {
2105 KeyType ak = a().start();
2106 KeyType bk = b().start();
2107 return Traits::startLess(ak, bk) ? bk : ak;
2110 /// stop - End of the overlapping interval.
2111 KeyType stop() const {
2112 KeyType ak = a().stop();
2113 KeyType bk = b().stop();
2114 return Traits::startLess(ak, bk) ? ak : bk;
2117 /// skipA - Move to the next overlap that doesn't involve a().
2123 /// skipB - Move to the next overlap that doesn't involve b().
2129 /// Preincrement - Move to the next overlap.
2130 IntervalMapOverlaps &operator++() {
2131 // Bump the iterator that ends first. The other one may have more overlaps.
2132 if (Traits::startLess(posB.stop(), posA.stop()))
2139 /// advanceTo - Move to the first overlapping interval with
2140 /// stopLess(x, stop()).
2141 void advanceTo(KeyType x) {
2144 // Make sure advanceTo sees monotonic keys.
2145 if (Traits::stopLess(posA.stop(), x))
2147 if (Traits::stopLess(posB.stop(), x))
2153 } // end namespace llvm
2155 #endif // LLVM_ADT_INTERVALMAP_H