1 //===- llvm/ADT/IntervalMap.h - A sorted interval map -----------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a coalescing interval map for small objects.
12 // KeyT objects are mapped to ValT objects. Intervals of keys that map to the
13 // same value are represented in a compressed form.
15 // Iterators provide ordered access to the compressed intervals rather than the
16 // individual keys, and insert and erase operations use key intervals as well.
18 // Like SmallVector, IntervalMap will store the first N intervals in the map
19 // object itself without any allocations. When space is exhausted it switches to
20 // a B+-tree representation with very small overhead for small key and value
23 // A Traits class specifies how keys are compared. It also allows IntervalMap to
24 // work with both closed and half-open intervals.
26 // Keys and values are not stored next to each other in a std::pair, so we don't
27 // provide such a value_type. Dereferencing iterators only returns the mapped
28 // value. The interval bounds are accessible through the start() and stop()
31 // IntervalMap is optimized for small key and value objects, 4 or 8 bytes each
32 // is the optimal size. For large objects use std::map instead.
34 //===----------------------------------------------------------------------===//
38 // template <typename KeyT, typename ValT, unsigned N, typename Traits>
39 // class IntervalMap {
41 // typedef KeyT key_type;
42 // typedef ValT mapped_type;
43 // typedef RecyclingAllocator<...> Allocator;
45 // class const_iterator;
47 // explicit IntervalMap(Allocator&);
50 // bool empty() const;
51 // KeyT start() const;
53 // ValT lookup(KeyT x, Value NotFound = Value()) const;
55 // const_iterator begin() const;
56 // const_iterator end() const;
59 // const_iterator find(KeyT x) const;
60 // iterator find(KeyT x);
62 // void insert(KeyT a, KeyT b, ValT y);
66 // template <typename KeyT, typename ValT, unsigned N, typename Traits>
67 // class IntervalMap::const_iterator :
68 // public std::iterator<std::bidirectional_iterator_tag, ValT> {
70 // bool operator==(const const_iterator &) const;
71 // bool operator!=(const const_iterator &) const;
72 // bool valid() const;
74 // const KeyT &start() const;
75 // const KeyT &stop() const;
76 // const ValT &value() const;
77 // const ValT &operator*() const;
78 // const ValT *operator->() const;
80 // const_iterator &operator++();
81 // const_iterator &operator++(int);
82 // const_iterator &operator--();
83 // const_iterator &operator--(int);
87 // void advanceTo(KeyT x);
90 // template <typename KeyT, typename ValT, unsigned N, typename Traits>
91 // class IntervalMap::iterator : public const_iterator {
93 // void insert(KeyT a, KeyT b, Value y);
97 //===----------------------------------------------------------------------===//
99 #ifndef LLVM_ADT_INTERVALMAP_H
100 #define LLVM_ADT_INTERVALMAP_H
102 #include "llvm/ADT/SmallVector.h"
103 #include "llvm/ADT/PointerIntPair.h"
104 #include "llvm/Support/Allocator.h"
105 #include "llvm/Support/RecyclingAllocator.h"
109 // FIXME: Remove debugging code
111 #include "llvm/Support/raw_ostream.h"
117 //===----------------------------------------------------------------------===//
118 //--- Key traits ---//
119 //===----------------------------------------------------------------------===//
121 // The IntervalMap works with closed or half-open intervals.
122 // Adjacent intervals that map to the same value are coalesced.
124 // The IntervalMapInfo traits class is used to determine if a key is contained
125 // in an interval, and if two intervals are adjacent so they can be coalesced.
126 // The provided implementation works for closed integer intervals, other keys
127 // probably need a specialized version.
129 // The point x is contained in [a;b] when !startLess(x, a) && !stopLess(b, x).
131 // It is assumed that (a;b] half-open intervals are not used, only [a;b) is
132 // allowed. This is so that stopLess(a, b) can be used to determine if two
133 // intervals overlap.
135 //===----------------------------------------------------------------------===//
137 template <typename T>
138 struct IntervalMapInfo {
140 /// startLess - Return true if x is not in [a;b].
141 /// This is x < a both for closed intervals and for [a;b) half-open intervals.
142 static inline bool startLess(const T &x, const T &a) {
146 /// stopLess - Return true if x is not in [a;b].
147 /// This is b < x for a closed interval, b <= x for [a;b) half-open intervals.
148 static inline bool stopLess(const T &b, const T &x) {
152 /// adjacent - Return true when the intervals [x;a] and [b;y] can coalesce.
153 /// This is a+1 == b for closed intervals, a == b for half-open intervals.
154 static inline bool adjacent(const T &a, const T &b) {
160 /// IntervalMapImpl - Namespace used for IntervalMap implementation details.
161 /// It should be considered private to the implementation.
162 namespace IntervalMapImpl {
164 // Forward declarations.
165 template <typename, typename, unsigned, typename> class Leaf;
166 template <typename, typename, unsigned, typename> class Branch;
168 typedef std::pair<unsigned,unsigned> IdxPair;
171 //===----------------------------------------------------------------------===//
172 //--- Node Storage ---//
173 //===----------------------------------------------------------------------===//
175 // Both leaf and branch nodes store vectors of (key,value) pairs.
176 // Leaves store ((KeyT, KeyT), ValT) pairs, branches use (KeyT, NodeRef).
178 // Keys and values are stored in separate arrays to avoid padding caused by
179 // different object alignments. This also helps improve locality of reference
180 // when searching the keys.
182 // The nodes don't know how many elements they contain - that information is
183 // stored elsewhere. Omitting the size field prevents padding and allows a node
184 // to fill the allocated cache lines completely.
186 // These are typical key and value sizes, the node branching factor (N), and
187 // wasted space when nodes are sized to fit in three cache lines (192 bytes):
189 // KT VT N Waste Used by
190 // 4 4 24 0 Branch<4> (32-bit pointers)
191 // 4 8 16 0 Branch<4>
192 // 8 4 16 0 Leaf<4,4>
193 // 8 8 12 0 Leaf<4,8>, Branch<8>
194 // 16 4 9 12 Leaf<8,4>
195 // 16 8 8 0 Leaf<8,8>
197 //===----------------------------------------------------------------------===//
199 template <typename KT, typename VT, unsigned N>
202 enum { Capacity = N };
207 /// copy - Copy elements from another node.
208 /// @param other Node elements are copied from.
209 /// @param i Beginning of the source range in other.
210 /// @param j Beginning of the destination range in this.
211 /// @param count Number of elements to copy.
212 template <unsigned M>
213 void copy(const NodeBase<KT, VT, M> &Other, unsigned i,
214 unsigned j, unsigned Count) {
215 assert(i + Count <= M && "Invalid source range");
216 assert(j + Count <= N && "Invalid dest range");
217 std::copy(Other.key + i, Other.key + i + Count, key + j);
218 std::copy(Other.val + i, Other.val + i + Count, val + j);
221 /// lmove - Move elements to the left.
222 /// @param i Beginning of the source range.
223 /// @param j Beginning of the destination range.
224 /// @param count Number of elements to copy.
225 void lmove(unsigned i, unsigned j, unsigned Count) {
226 assert(j <= i && "Use rmove shift elements right");
227 copy(*this, i, j, Count);
230 /// rmove - Move elements to the right.
231 /// @param i Beginning of the source range.
232 /// @param j Beginning of the destination range.
233 /// @param count Number of elements to copy.
234 void rmove(unsigned i, unsigned j, unsigned Count) {
235 assert(i <= j && "Use lmove shift elements left");
236 assert(j + Count <= N && "Invalid range");
237 std::copy_backward(key + i, key + i + Count, key + j + Count);
238 std::copy_backward(val + i, val + i + Count, val + j + 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 lmove(j, i, Size - j);
249 /// shift - Shift elements [i;size) 1 position to the right.
250 /// @param i Beginning of the range to move.
251 /// @param size Number of elements in node.
252 void shift(unsigned i, unsigned Size) {
253 rmove(i, i + 1, Size - i);
256 /// xferLeft - Transfer elements to a left sibling node.
257 /// @param size Number of elements in this.
258 /// @param sib Left sibling node.
259 /// @param ssize Number of elements in sib.
260 /// @param count Number of elements to transfer.
261 void xferLeft(unsigned Size, NodeBase &Sib, unsigned SSize, unsigned Count) {
262 Sib.copy(*this, 0, SSize, Count);
263 erase(0, Count, Size);
266 /// xferRight - Transfer elements to a right sibling node.
267 /// @param size Number of elements in this.
268 /// @param sib Right sibling node.
269 /// @param ssize Number of elements in sib.
270 /// @param count Number of elements to transfer.
271 void xferRight(unsigned Size, NodeBase &Sib, unsigned SSize, unsigned Count) {
272 Sib.rmove(0, Count, SSize);
273 Sib.copy(*this, Size-Count, 0, Count);
276 /// adjLeftSib - Adjust the number if elements in this node by moving
277 /// elements to or from a left sibling node.
278 /// @param size Number of elements in this.
279 /// @param sib Right sibling node.
280 /// @param ssize Number of elements in sib.
281 /// @param add The number of elements to add to this node, possibly < 0.
282 /// @return Number of elements added to this node, possibly negative.
283 int adjLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add) {
285 // We want to grow, copy from sib.
286 unsigned Count = std::min(std::min(unsigned(Add), SSize), N - Size);
287 Sib.xferRight(SSize, *this, Size, Count);
290 // We want to shrink, copy to sib.
291 unsigned Count = std::min(std::min(unsigned(-Add), Size), N - SSize);
292 xferLeft(Size, Sib, SSize, Count);
299 //===----------------------------------------------------------------------===//
300 //--- NodeSizer ---//
301 //===----------------------------------------------------------------------===//
303 // Compute node sizes from key and value types.
305 // The branching factors are chosen to make nodes fit in three cache lines.
306 // This may not be possible if keys or values are very large. Such large objects
307 // are handled correctly, but a std::map would probably give better performance.
309 //===----------------------------------------------------------------------===//
311 template <typename KeyT, typename ValT>
314 // Cache line size. Most architectures have 32 or 64 byte cache lines.
315 // We use 64 bytes here because it provides good branching factors.
317 CacheLineBytes = 1 << Log2CacheLine,
319 // Compute the leaf node branching factor that makes a node fit in three
320 // cache lines. The branching factor must be at least 3, or some B+-tree
321 // balancing algorithms won't work.
322 // LeafSize can't be larger than CacheLineBytes. This is required by the
323 // PointerIntPair used by NodeRef.
324 DesiredNodeBytes = 3 * CacheLineBytes,
325 DesiredLeafSize = DesiredNodeBytes / (2*sizeof(KeyT)+sizeof(ValT)),
326 LeafSize = DesiredLeafSize > 3 ? DesiredLeafSize : 3,
328 // Now that we have the leaf branching factor, compute the actual allocation
329 // unit size by rounding up to a whole number of cache lines.
330 LeafBytes = sizeof(NodeBase<std::pair<KeyT, KeyT>, ValT, LeafSize>),
331 AllocBytes = (LeafBytes + CacheLineBytes-1) & ~(CacheLineBytes-1),
333 // Determine the branching factor for branch nodes, constrained to
334 // CacheLineBytes to please NodeRef.
335 DesiredBranchSize = AllocBytes / (sizeof(KeyT) + sizeof(void*)),
336 BranchSize = DesiredBranchSize < CacheLineBytes ?
337 DesiredBranchSize : CacheLineBytes
340 /// Allocator - The recycling allocator used for both branch and leaf nodes.
341 /// This typedef is very likely to be identical for all IntervalMaps with
342 /// reasonably sized entries, so the same allocator can be shared among
343 /// different kinds of maps.
344 typedef RecyclingAllocator<BumpPtrAllocator, char,
345 AllocBytes, CacheLineBytes> Allocator;
350 //===----------------------------------------------------------------------===//
352 //===----------------------------------------------------------------------===//
354 // B+-tree nodes can be leaves or branches, so we need a polymorphic node
355 // pointer that can point to both kinds.
357 // All nodes are cache line aligned and the low 6 bits of a node pointer are
358 // always 0. These bits are used to store the number of elements in the
359 // referenced node. Besides saving space, placing node sizes in the parents
360 // allow tree balancing algorithms to run without faulting cache lines for nodes
361 // that may not need to be modified.
363 // A NodeRef doesn't know whether it references a leaf node or a branch node.
364 // It is the responsibility of the caller to use the correct types.
366 // Nodes are never supposed to be empty, and it is invalid to store a node size
367 // of 0 in a NodeRef. The valid range of sizes is 1-64.
369 //===----------------------------------------------------------------------===//
371 template <typename KeyT, typename ValT, typename Traits>
375 typedef NodeSizer<KeyT, ValT> NodeSizer;
376 typedef Leaf<KeyT, ValT, NodeSizer::LeafSize, Traits> Leaf;
377 typedef Branch<KeyT, ValT, NodeSizer::BranchSize, Traits> Branch;
380 struct CacheAlignedPointerTraits {
381 static inline void *getAsVoidPointer(void *P) { return P; }
382 static inline void *getFromVoidPointer(void *P) { return P; }
383 enum { NumLowBitsAvailable = NodeSizer::Log2CacheLine };
386 PointerIntPair<void*, NodeSizer::Log2CacheLine, unsigned,
387 CacheAlignedPointerTraits> pip;
390 /// NodeRef - Create a null ref.
393 /// operator bool - Detect a null ref.
394 operator bool() const { return pip.getOpaqueValue(); }
396 /// NodeRef - Create a reference to the leaf node p with n elements.
397 NodeRef(Leaf *p, unsigned n) : pip(p, n - 1) {}
399 /// NodeRef - Create a reference to the branch node p with n elements.
400 NodeRef(Branch *p, unsigned n) : pip(p, n - 1) {}
402 /// size - Return the number of elements in the referenced node.
403 unsigned size() const { return pip.getInt() + 1; }
405 /// setSize - Update the node size.
406 void setSize(unsigned n) { pip.setInt(n - 1); }
408 /// leaf - Return the referenced leaf node.
409 /// Note there are no dynamic type checks.
411 return *reinterpret_cast<Leaf*>(pip.getPointer());
414 /// branch - Return the referenced branch node.
415 /// Note there are no dynamic type checks.
416 Branch &branch() const {
417 return *reinterpret_cast<Branch*>(pip.getPointer());
420 bool operator==(const NodeRef &RHS) const {
423 assert(pip.getPointer() != RHS.pip.getPointer() && "Inconsistent NodeRefs");
427 bool operator!=(const NodeRef &RHS) const {
428 return !operator==(RHS);
432 //===----------------------------------------------------------------------===//
433 //--- Leaf nodes ---//
434 //===----------------------------------------------------------------------===//
436 // Leaf nodes store up to N disjoint intervals with corresponding values.
438 // The intervals are kept sorted and fully coalesced so there are no adjacent
439 // intervals mapping to the same value.
441 // These constraints are always satisfied:
443 // - Traits::stopLess(key[i].start, key[i].stop) - Non-empty, sane intervals.
445 // - Traits::stopLess(key[i].stop, key[i + 1].start) - Sorted.
447 // - val[i] != val[i + 1] ||
448 // !Traits::adjacent(key[i].stop, key[i + 1].start) - Fully coalesced.
450 //===----------------------------------------------------------------------===//
452 template <typename KeyT, typename ValT, unsigned N, typename Traits>
453 class Leaf : public NodeBase<std::pair<KeyT, KeyT>, ValT, N> {
455 const KeyT &start(unsigned i) const { return this->key[i].first; }
456 const KeyT &stop(unsigned i) const { return this->key[i].second; }
457 const ValT &value(unsigned i) const { return this->val[i]; }
459 KeyT &start(unsigned i) { return this->key[i].first; }
460 KeyT &stop(unsigned i) { return this->key[i].second; }
461 ValT &value(unsigned i) { return this->val[i]; }
463 /// findFrom - Find the first interval after i that may contain x.
464 /// @param i Starting index for the search.
465 /// @param size Number of elements in node.
466 /// @param x Key to search for.
467 /// @return First index with !stopLess(key[i].stop, x), or size.
468 /// This is the first interval that can possibly contain x.
469 unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
470 assert(i <= Size && Size <= N && "Bad indices");
471 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
472 "Index is past the needed point");
473 while (i != Size && Traits::stopLess(stop(i), x)) ++i;
477 /// safeFind - Find an interval that is known to exist. This is the same as
478 /// findFrom except is it assumed that x is at least within range of the last
480 /// @param i Starting index for the search.
481 /// @param x Key to search for.
482 /// @return First index with !stopLess(key[i].stop, x), never size.
483 /// This is the first interval that can possibly contain x.
484 unsigned safeFind(unsigned i, KeyT x) const {
485 assert(i < N && "Bad index");
486 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
487 "Index is past the needed point");
488 while (Traits::stopLess(stop(i), x)) ++i;
489 assert(i < N && "Unsafe intervals");
493 /// safeLookup - Lookup mapped value for a safe key.
494 /// It is assumed that x is within range of the last entry.
495 /// @param x Key to search for.
496 /// @param NotFound Value to return if x is not in any interval.
497 /// @return The mapped value at x or NotFound.
498 ValT safeLookup(KeyT x, ValT NotFound) const {
499 unsigned i = safeFind(0, x);
500 return Traits::startLess(x, start(i)) ? NotFound : value(i);
503 IdxPair insertFrom(unsigned i, unsigned Size, KeyT a, KeyT b, ValT y);
504 unsigned extendStop(unsigned i, unsigned Size, KeyT b);
507 void dump(unsigned Size) {
508 errs() << " N" << this << " [shape=record label=\"{ " << Size << '/' << N;
509 for (unsigned i = 0; i != Size; ++i)
510 errs() << " | {" << start(i) << '-' << stop(i) << "|" << value(i) << '}';
517 /// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as
518 /// possible. This may cause the node to grow by 1, or it may cause the node
519 /// to shrink because of coalescing.
520 /// @param i Starting index = insertFrom(0, size, a)
521 /// @param size Number of elements in node.
522 /// @param a Interval start.
523 /// @param b Interval stop.
524 /// @param y Value be mapped.
525 /// @return (insert position, new size), or (i, Capacity+1) on overflow.
526 template <typename KeyT, typename ValT, unsigned N, typename Traits>
527 IdxPair Leaf<KeyT, ValT, N, Traits>::
528 insertFrom(unsigned i, unsigned Size, KeyT a, KeyT b, ValT y) {
529 assert(i <= Size && Size <= N && "Invalid index");
530 assert(!Traits::stopLess(b, a) && "Invalid interval");
532 // Verify the findFrom invariant.
533 assert((i == 0 || Traits::stopLess(stop(i - 1), a)));
534 assert((i == Size || !Traits::stopLess(stop(i), a)));
536 // Coalesce with previous interval.
537 if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a))
538 return IdxPair(i - 1, extendStop(i - 1, Size, b));
542 return IdxPair(i, N + 1);
544 // Add new interval at end.
549 return IdxPair(i, Size + 1);
552 // Overlapping intervals?
553 if (!Traits::stopLess(b, start(i))) {
554 assert(value(i) == y && "Inconsistent values in overlapping intervals");
555 if (Traits::startLess(a, start(i)))
557 return IdxPair(i, extendStop(i, Size, b));
560 // Try to coalesce with following interval.
561 if (value(i) == y && Traits::adjacent(b, start(i))) {
563 return IdxPair(i, Size);
566 // We must insert before i. Detect overflow.
568 return IdxPair(i, N + 1);
571 this->shift(i, Size);
575 return IdxPair(i, Size + 1);
578 /// extendStop - Extend stop(i) to b, coalescing with following intervals.
579 /// @param i Interval to extend.
580 /// @param size Number of elements in node.
581 /// @param b New interval end point.
582 /// @return New node size after coalescing.
583 template <typename KeyT, typename ValT, unsigned N, typename Traits>
584 unsigned Leaf<KeyT, ValT, N, Traits>::
585 extendStop(unsigned i, unsigned Size, KeyT b) {
586 assert(i < Size && Size <= N && "Bad indices");
588 // Are we even extending the interval?
589 if (Traits::startLess(b, stop(i)))
592 // Find the first interval that may be preserved.
593 unsigned j = findFrom(i + 1, Size, b);
595 // Would key[i] overlap key[j] after the extension?
596 if (Traits::stopLess(b, start(j))) {
597 // Not overlapping. Perhaps adjacent and coalescable?
598 if (value(i) == value(j) && Traits::adjacent(b, start(j)))
601 // Overlap. Include key[j] in the new interval.
602 assert(value(i) == value(j) && "Overlapping values");
608 // Entries [i+1;j) were coalesced.
609 if (i + 1 < j && j < Size)
610 this->erase(i + 1, j, Size);
611 return Size - (j - (i + 1));
615 //===----------------------------------------------------------------------===//
616 //--- Branch nodes ---//
617 //===----------------------------------------------------------------------===//
619 // A branch node stores references to 1--N subtrees all of the same height.
621 // The key array in a branch node holds the rightmost stop key of each subtree.
622 // It is redundant to store the last stop key since it can be found in the
623 // parent node, but doing so makes tree balancing a lot simpler.
625 // It is unusual for a branch node to only have one subtree, but it can happen
626 // in the root node if it is smaller than the normal nodes.
628 // When all of the leaf nodes from all the subtrees are concatenated, they must
629 // satisfy the same constraints as a single leaf node. They must be sorted,
630 // sane, and fully coalesced.
632 //===----------------------------------------------------------------------===//
634 template <typename KeyT, typename ValT, unsigned N, typename Traits>
635 class Branch : public NodeBase<KeyT, NodeRef<KeyT, ValT, Traits>, N> {
636 typedef NodeRef<KeyT, ValT, Traits> NodeRef;
638 const KeyT &stop(unsigned i) const { return this->key[i]; }
639 const NodeRef &subtree(unsigned i) const { return this->val[i]; }
641 KeyT &stop(unsigned i) { return this->key[i]; }
642 NodeRef &subtree(unsigned i) { return this->val[i]; }
645 /// findFrom - Find the first subtree after i that may contain x.
646 /// @param i Starting index for the search.
647 /// @param size Number of elements in node.
648 /// @param x Key to search for.
649 /// @return First index with !stopLess(key[i], x), or size.
650 /// This is the first subtree that can possibly contain x.
651 unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
652 assert(i <= Size && Size <= N && "Bad indices");
653 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
654 "Index to findFrom is past the needed point");
655 while (i != Size && Traits::stopLess(stop(i), x)) ++i;
659 /// safeFind - Find a subtree that is known to exist. This is the same as
660 /// findFrom except is it assumed that x is in range.
661 /// @param i Starting index for the search.
662 /// @param x Key to search for.
663 /// @return First index with !stopLess(key[i], x), never size.
664 /// This is the first subtree that can possibly contain x.
665 unsigned safeFind(unsigned i, KeyT x) const {
666 assert(i < N && "Bad index");
667 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
668 "Index is past the needed point");
669 while (Traits::stopLess(stop(i), x)) ++i;
670 assert(i < N && "Unsafe intervals");
674 /// safeLookup - Get the subtree containing x, Assuming that x is in range.
675 /// @param x Key to search for.
676 /// @return Subtree containing x
677 NodeRef safeLookup(KeyT x) const {
678 return subtree(safeFind(0, x));
681 /// insert - Insert a new (subtree, stop) pair.
682 /// @param i Insert position, following entries will be shifted.
683 /// @param size Number of elements in node.
684 /// @param node Subtree to insert.
685 /// @param stp Last key in subtree.
686 void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop) {
687 assert(Size < N && "branch node overflow");
688 assert(i <= Size && "Bad insert position");
689 this->shift(i, Size);
695 void dump(unsigned Size) {
696 errs() << " N" << this << " [shape=record label=\"" << Size << '/' << N;
697 for (unsigned i = 0; i != Size; ++i)
698 errs() << " | <s" << i << "> " << stop(i);
700 for (unsigned i = 0; i != Size; ++i)
701 errs() << " N" << this << ":s" << i << " -> N"
702 << &subtree(i).branch() << ";\n";
708 } // namespace IntervalMapImpl
711 //===----------------------------------------------------------------------===//
712 //--- IntervalMap ----//
713 //===----------------------------------------------------------------------===//
715 template <typename KeyT, typename ValT,
716 unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize,
717 typename Traits = IntervalMapInfo<KeyT> >
719 typedef IntervalMapImpl::NodeRef<KeyT, ValT, Traits> NodeRef;
720 typedef typename NodeRef::NodeSizer NodeSizer;
721 typedef typename NodeRef::Leaf Leaf;
722 typedef typename NodeRef::Branch Branch;
723 typedef IntervalMapImpl::Leaf<KeyT, ValT, N, Traits> RootLeaf;
724 typedef IntervalMapImpl::IdxPair IdxPair;
726 // The RootLeaf capacity is given as a template parameter. We must compute the
727 // corresponding RootBranch capacity.
729 DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) /
730 (sizeof(KeyT) + sizeof(NodeRef)),
731 RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1
734 typedef IntervalMapImpl::Branch<KeyT, ValT, RootBranchCap, Traits> RootBranch;
736 // When branched, we store a global start key as well as the branch node.
737 struct RootBranchData {
743 RootDataSize = sizeof(RootBranchData) > sizeof(RootLeaf) ?
744 sizeof(RootBranchData) : sizeof(RootLeaf)
748 typedef typename NodeSizer::Allocator Allocator;
751 // The root data is either a RootLeaf or a RootBranchData instance.
752 // We can't put them in a union since C++03 doesn't allow non-trivial
753 // constructors in unions.
754 // Instead, we use a char array with pointer alignment. The alignment is
755 // ensured by the allocator member in the class, but still verified in the
756 // constructor. We don't support keys or values that are more aligned than a
758 char data[RootDataSize];
761 // 0: Leaves in root.
762 // 1: Root points to leaf.
763 // 2: root->branch->leaf ...
766 // Number of entries in the root node.
769 // Allocator used for creating external nodes.
770 Allocator &allocator;
772 const RootLeaf &rootLeaf() const {
773 assert(!branched() && "Cannot acces leaf data in branched root");
774 return *reinterpret_cast<const RootLeaf*>(data);
776 RootLeaf &rootLeaf() {
777 assert(!branched() && "Cannot acces leaf data in branched root");
778 return *reinterpret_cast<RootLeaf*>(data);
780 const RootBranchData &rootBranchData() const {
781 assert(branched() && "Cannot access branch data in non-branched root");
782 return *reinterpret_cast<const RootBranchData*>(data);
784 RootBranchData &rootBranchData() {
785 assert(branched() && "Cannot access branch data in non-branched root");
786 return *reinterpret_cast<RootBranchData*>(data);
788 const RootBranch &rootBranch() const { return rootBranchData().node; }
789 RootBranch &rootBranch() { return rootBranchData().node; }
790 KeyT rootBranchStart() const { return rootBranchData().start; }
791 KeyT &rootBranchStart() { return rootBranchData().start; }
794 return new(allocator.template Allocate<Leaf>()) Leaf();
796 void freeLeaf(Leaf *P) {
798 allocator.Deallocate(P);
801 Branch *allocBranch() {
802 return new(allocator.template Allocate<Branch>()) Branch();
804 void freeBranch(Branch *P) {
806 allocator.Deallocate(P);
810 IdxPair branchRoot(unsigned Position);
811 IdxPair splitRoot(unsigned Position);
813 void switchRootToBranch() {
814 rootLeaf().~RootLeaf();
816 new (&rootBranchData()) RootBranchData();
819 void switchRootToLeaf() {
820 rootBranchData().~RootBranchData();
822 new(&rootLeaf()) RootLeaf();
825 bool branched() const { return height > 0; }
827 ValT treeSafeLookup(KeyT x, ValT NotFound) const;
829 void visitNodes(void (IntervalMap::*f)(NodeRef, unsigned Level));
832 explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) {
833 assert((uintptr_t(data) & (alignOf<RootLeaf>() - 1)) == 0 &&
834 "Insufficient alignment");
835 new(&rootLeaf()) RootLeaf();
838 /// empty - Return true when no intervals are mapped.
840 return rootSize == 0;
843 /// start - Return the smallest mapped key in a non-empty map.
845 assert(!empty() && "Empty IntervalMap has no start");
846 return !branched() ? rootLeaf().start(0) : rootBranchStart();
849 /// stop - Return the largest mapped key in a non-empty map.
851 assert(!empty() && "Empty IntervalMap has no stop");
852 return !branched() ? rootLeaf().stop(rootSize - 1) :
853 rootBranch().stop(rootSize - 1);
856 /// lookup - Return the mapped value at x or NotFound.
857 ValT lookup(KeyT x, ValT NotFound = ValT()) const {
858 if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x))
860 return branched() ? treeSafeLookup(x, NotFound) :
861 rootLeaf().safeLookup(x, NotFound);
864 /// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
865 /// It is assumed that no key in the interval is mapped to another value, but
866 /// overlapping intervals already mapped to y will be coalesced.
867 void insert(KeyT a, KeyT b, ValT y) {
868 find(a).insert(a, b, y);
871 class const_iterator;
873 friend class const_iterator;
874 friend class iterator;
876 const_iterator begin() const {
888 const_iterator end() const {
900 /// find - Return an iterator pointing to the first interval ending at or
901 /// after x, or end().
902 const_iterator find(KeyT x) const {
908 iterator find(KeyT x) {
916 void dumpNode(NodeRef Node, unsigned Height);
920 /// treeSafeLookup - Return the mapped value at x or NotFound, assuming a
922 template <typename KeyT, typename ValT, unsigned N, typename Traits>
923 ValT IntervalMap<KeyT, ValT, N, Traits>::
924 treeSafeLookup(KeyT x, ValT NotFound) const {
925 assert(branched() && "treeLookup assumes a branched root");
927 NodeRef NR = rootBranch().safeLookup(x);
928 for (unsigned h = height-1; h; --h)
929 NR = NR.branch().safeLookup(x);
930 return NR.leaf().safeLookup(x, NotFound);
934 // branchRoot - Switch from a leaf root to a branched root.
935 // Return the new (root offset, node offset) corresponding to Position.
936 template <typename KeyT, typename ValT, unsigned N, typename Traits>
937 IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
938 branchRoot(unsigned Position) {
939 // How many external leaf nodes to hold RootLeaf+1?
940 const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1;
942 // Compute element distribution among new nodes.
943 unsigned size[Nodes];
944 IdxPair NewOffset(0, Position);
946 // Is is very common for the root node to be smaller than external nodes.
950 NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, size,
953 // Allocate new nodes.
956 for (unsigned n = 0; n != Nodes; ++n) {
957 node[n] = NodeRef(allocLeaf(), size[n]);
958 node[n].leaf().copy(rootLeaf(), pos, 0, size[n]);
962 // Destroy the old leaf node, construct branch node instead.
963 switchRootToBranch();
964 for (unsigned n = 0; n != Nodes; ++n) {
965 rootBranch().stop(n) = node[n].leaf().stop(size[n]-1);
966 rootBranch().subtree(n) = node[n];
968 rootBranchStart() = node[0].leaf().start(0);
973 // splitRoot - Split the current BranchRoot into multiple Branch nodes.
974 // Return the new (root offset, node offset) corresponding to Position.
975 template <typename KeyT, typename ValT, unsigned N, typename Traits>
976 IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
977 splitRoot(unsigned Position) {
978 // How many external leaf nodes to hold RootBranch+1?
979 const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1;
981 // Compute element distribution among new nodes.
982 unsigned Size[Nodes];
983 IdxPair NewOffset(0, Position);
985 // Is is very common for the root node to be smaller than external nodes.
989 NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, Size,
992 // Allocate new nodes.
995 for (unsigned n = 0; n != Nodes; ++n) {
996 Node[n] = NodeRef(allocBranch(), Size[n]);
997 Node[n].branch().copy(rootBranch(), Pos, 0, Size[n]);
1001 for (unsigned n = 0; n != Nodes; ++n) {
1002 rootBranch().stop(n) = Node[n].branch().stop(Size[n]-1);
1003 rootBranch().subtree(n) = Node[n];
1009 /// visitNodes - Visit each external node.
1010 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1011 void IntervalMap<KeyT, ValT, N, Traits>::
1012 visitNodes(void (IntervalMap::*f)(NodeRef, unsigned Height)) {
1015 SmallVector<NodeRef, 4> Refs, NextRefs;
1017 // Collect level 0 nodes from the root.
1018 for (unsigned i = 0; i != rootSize; ++i)
1019 Refs.push_back(rootBranch().subtree(i));
1021 // Visit all branch nodes.
1022 for (unsigned h = height - 1; h; --h) {
1023 for (unsigned i = 0, e = Refs.size(); i != e; ++i) {
1024 Branch &B = Refs[i].branch();
1025 for (unsigned j = 0, s = Refs[i].size(); j != s; ++j)
1026 NextRefs.push_back(B.subtree(j));
1027 (this->*f)(Refs[i], h);
1030 Refs.swap(NextRefs);
1033 // Visit all leaf nodes.
1034 for (unsigned i = 0, e = Refs.size(); i != e; ++i)
1035 (this->*f)(Refs[i], 0);
1039 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1040 void IntervalMap<KeyT, ValT, N, Traits>::
1041 dumpNode(NodeRef Node, unsigned Height) {
1043 Node.branch().dump(Node.size());
1045 Node.leaf().dump(Node.size());
1048 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1049 void IntervalMap<KeyT, ValT, N, Traits>::
1051 errs() << "digraph {\n";
1053 rootBranch().dump(rootSize);
1055 rootLeaf().dump(rootSize);
1056 visitNodes(&IntervalMap::dumpNode);
1061 //===----------------------------------------------------------------------===//
1062 //--- const_iterator ----//
1063 //===----------------------------------------------------------------------===//
1065 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1066 class IntervalMap<KeyT, ValT, N, Traits>::const_iterator :
1067 public std::iterator<std::bidirectional_iterator_tag, ValT> {
1069 friend class IntervalMap;
1070 typedef std::pair<NodeRef, unsigned> PathEntry;
1071 typedef SmallVector<PathEntry, 4> Path;
1073 // The map referred to.
1076 // The offset into map's root node.
1077 unsigned rootOffset;
1079 // We store a full path from the root to the current position.
1081 // When rootOffset == map->rootSize, we are at end() and path() is empty.
1082 // Otherwise, when branched these conditions hold:
1084 // 1. path.front().first == rootBranch().subtree(rootOffset)
1085 // 2. path[i].first == path[i-1].first.branch().subtree(path[i-1].second)
1086 // 3. path.size() == map->height.
1088 // Thus, path.back() always refers to the current leaf node unless the root is
1091 // The path may be partially filled, but never between iterator calls.
1094 explicit const_iterator(IntervalMap &map)
1095 : map(&map), rootOffset(map.rootSize) {}
1097 bool branched() const {
1098 assert(map && "Invalid iterator");
1099 return map->branched();
1102 NodeRef pathNode(unsigned h) const { return path[h].first; }
1103 NodeRef &pathNode(unsigned h) { return path[h].first; }
1104 unsigned pathOffset(unsigned h) const { return path[h].second; }
1105 unsigned &pathOffset(unsigned h) { return path[h].second; }
1107 Leaf &treeLeaf() const {
1108 assert(branched() && path.size() == map->height);
1109 return path.back().first.leaf();
1111 unsigned treeLeafSize() const {
1112 assert(branched() && path.size() == map->height);
1113 return path.back().first.size();
1115 unsigned &treeLeafOffset() {
1116 assert(branched() && path.size() == map->height);
1117 return path.back().second;
1119 unsigned treeLeafOffset() const {
1120 assert(branched() && path.size() == map->height);
1121 return path.back().second;
1124 // Get the next node ptr for an incomplete path.
1125 NodeRef pathNextDown() {
1126 assert(path.size() < map->height && "Path is already complete");
1129 return map->rootBranch().subtree(rootOffset);
1131 return path.back().first.branch().subtree(path.back().second);
1134 void pathFillLeft();
1135 void pathFillFind(KeyT x);
1136 void pathFillRight();
1138 NodeRef leftSibling(unsigned level) const;
1139 NodeRef rightSibling(unsigned level) const;
1141 void treeIncrement();
1142 void treeDecrement();
1143 void treeFind(KeyT x);
1146 /// valid - Return true if the current position is valid, false for end().
1147 bool valid() const {
1148 assert(map && "Invalid iterator");
1149 return rootOffset < map->rootSize;
1152 /// start - Return the beginning of the current interval.
1153 const KeyT &start() const {
1154 assert(valid() && "Cannot access invalid iterator");
1155 return branched() ? treeLeaf().start(treeLeafOffset()) :
1156 map->rootLeaf().start(rootOffset);
1159 /// stop - Return the end of the current interval.
1160 const KeyT &stop() const {
1161 assert(valid() && "Cannot access invalid iterator");
1162 return branched() ? treeLeaf().stop(treeLeafOffset()) :
1163 map->rootLeaf().stop(rootOffset);
1166 /// value - Return the mapped value at the current interval.
1167 const ValT &value() const {
1168 assert(valid() && "Cannot access invalid iterator");
1169 return branched() ? treeLeaf().value(treeLeafOffset()) :
1170 map->rootLeaf().value(rootOffset);
1173 const ValT &operator*() const {
1177 bool operator==(const const_iterator &RHS) const {
1178 assert(map == RHS.map && "Cannot compare iterators from different maps");
1179 return rootOffset == RHS.rootOffset &&
1180 (!valid() || !branched() || path.back() == RHS.path.back());
1183 bool operator!=(const const_iterator &RHS) const {
1184 return !operator==(RHS);
1187 /// goToBegin - Move to the first interval in map.
1195 /// goToEnd - Move beyond the last interval in map.
1197 rootOffset = map->rootSize;
1201 /// preincrement - move to the next interval.
1202 const_iterator &operator++() {
1203 assert(valid() && "Cannot increment end()");
1206 else if (treeLeafOffset() != treeLeafSize() - 1)
1213 /// postincrement - Dont do that!
1214 const_iterator operator++(int) {
1215 const_iterator tmp = *this;
1220 /// predecrement - move to the previous interval.
1221 const_iterator &operator--() {
1223 assert(rootOffset && "Cannot decrement begin()");
1225 } else if (treeLeafOffset())
1232 /// postdecrement - Dont do that!
1233 const_iterator operator--(int) {
1234 const_iterator tmp = *this;
1239 /// find - Move to the first interval with stop >= x, or end().
1240 /// This is a full search from the root, the current position is ignored.
1245 rootOffset = map->rootLeaf().findFrom(0, map->rootSize, x);
1248 /// advanceTo - Move to the first interval with stop >= x, or end().
1249 /// The search is started from the current position, and no earlier positions
1250 /// can be found. This is much faster than find() for small moves.
1251 void advanceTo(KeyT x) {
1255 rootOffset = map->rootLeaf().findFrom(rootOffset, map->rootSize, x);
1260 // pathFillLeft - Complete path by following left-most branches.
1261 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1262 void IntervalMap<KeyT, ValT, N, Traits>::
1263 const_iterator::pathFillLeft() {
1264 NodeRef NR = pathNextDown();
1265 for (unsigned i = map->height - path.size() - 1; i; --i) {
1266 path.push_back(PathEntry(NR, 0));
1267 NR = NR.branch().subtree(0);
1269 path.push_back(PathEntry(NR, 0));
1272 // pathFillFind - Complete path by searching for x.
1273 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1274 void IntervalMap<KeyT, ValT, N, Traits>::
1275 const_iterator::pathFillFind(KeyT x) {
1276 NodeRef NR = pathNextDown();
1277 for (unsigned i = map->height - path.size() - 1; i; --i) {
1278 unsigned p = NR.branch().safeFind(0, x);
1279 path.push_back(PathEntry(NR, p));
1280 NR = NR.branch().subtree(p);
1282 path.push_back(PathEntry(NR, NR.leaf().safeFind(0, x)));
1285 // pathFillRight - Complete path by adding rightmost entries.
1286 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1287 void IntervalMap<KeyT, ValT, N, Traits>::
1288 const_iterator::pathFillRight() {
1289 NodeRef NR = pathNextDown();
1290 for (unsigned i = map->height - path.size() - 1; i; --i) {
1291 unsigned p = NR.size() - 1;
1292 path.push_back(PathEntry(NR, p));
1293 NR = NR.branch().subtree(p);
1295 path.push_back(PathEntry(NR, NR.size() - 1));
1298 /// leftSibling - find the left sibling node to path[level].
1299 /// @param level 0 is just below the root, map->height - 1 for the leaves.
1300 /// @return The left sibling NodeRef, or NULL.
1301 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1302 typename IntervalMap<KeyT, ValT, N, Traits>::NodeRef
1303 IntervalMap<KeyT, ValT, N, Traits>::
1304 const_iterator::leftSibling(unsigned level) const {
1305 assert(branched() && "Not at a branched node");
1306 assert(level <= path.size() && "Bad level");
1308 // Go up the tree until we can go left.
1310 while (h && pathOffset(h - 1) == 0)
1313 // We are at the first leaf node, no left sibling.
1314 if (!h && rootOffset == 0)
1317 // NR is the subtree containing our left sibling.
1319 pathNode(h - 1).branch().subtree(pathOffset(h - 1) - 1) :
1320 map->rootBranch().subtree(rootOffset - 1);
1322 // Keep right all the way down.
1323 for (; h != level; ++h)
1324 NR = NR.branch().subtree(NR.size() - 1);
1328 /// rightSibling - find the right sibling node to path[level].
1329 /// @param level 0 is just below the root, map->height - 1 for the leaves.
1330 /// @return The right sibling NodeRef, or NULL.
1331 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1332 typename IntervalMap<KeyT, ValT, N, Traits>::NodeRef
1333 IntervalMap<KeyT, ValT, N, Traits>::
1334 const_iterator::rightSibling(unsigned level) const {
1335 assert(branched() && "Not at a branched node");
1336 assert(level <= this->path.size() && "Bad level");
1338 // Go up the tree until we can go right.
1340 while (h && pathOffset(h - 1) == pathNode(h - 1).size() - 1)
1343 // We are at the last leaf node, no right sibling.
1344 if (!h && rootOffset == map->rootSize - 1)
1347 // NR is the subtree containing our right sibling.
1349 pathNode(h - 1).branch().subtree(pathOffset(h - 1) + 1) :
1350 map->rootBranch().subtree(rootOffset + 1);
1352 // Keep left all the way down.
1353 for (; h != level; ++h)
1354 NR = NR.branch().subtree(0);
1358 // treeIncrement - Move to the beginning of the next leaf node.
1359 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1360 void IntervalMap<KeyT, ValT, N, Traits>::
1361 const_iterator::treeIncrement() {
1362 assert(branched() && "treeIncrement is not for small maps");
1363 assert(path.size() == map->height && "inconsistent iterator");
1365 while (!path.empty() && path.back().second == path.back().first.size() - 1);
1371 ++path.back().second;
1375 // treeDecrement - Move to the end of the previous leaf node.
1376 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1377 void IntervalMap<KeyT, ValT, N, Traits>::
1378 const_iterator::treeDecrement() {
1379 assert(branched() && "treeDecrement is not for small maps");
1381 assert(path.size() == map->height && "inconsistent iterator");
1383 while (!path.empty() && path.back().second == 0);
1386 assert(rootOffset && "cannot treeDecrement() on begin()");
1389 --path.back().second;
1393 // treeFind - Find in a branched tree.
1394 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1395 void IntervalMap<KeyT, ValT, N, Traits>::
1396 const_iterator::treeFind(KeyT x) {
1398 rootOffset = map->rootBranch().findFrom(0, map->rootSize, x);
1404 //===----------------------------------------------------------------------===//
1405 //--- iterator ----//
1406 //===----------------------------------------------------------------------===//
1408 namespace IntervalMapImpl {
1410 /// distribute - Compute a new distribution of node elements after an overflow
1411 /// or underflow. Reserve space for a new element at Position, and compute the
1412 /// node that will hold Position after redistributing node elements.
1414 /// It is required that
1416 /// Elements == sum(CurSize), and
1417 /// Elements + Grow <= Nodes * Capacity.
1419 /// NewSize[] will be filled in such that:
1421 /// sum(NewSize) == Elements, and
1422 /// NewSize[i] <= Capacity.
1424 /// The returned index is the node where Position will go, so:
1426 /// sum(NewSize[0..idx-1]) <= Position
1427 /// sum(NewSize[0..idx]) >= Position
1429 /// The last equality, sum(NewSize[0..idx]) == Position, can only happen when
1430 /// Grow is set and NewSize[idx] == Capacity-1. The index points to the node
1431 /// before the one holding the Position'th element where there is room for an
1434 /// @param Nodes The number of nodes.
1435 /// @param Elements Total elements in all nodes.
1436 /// @param Capacity The capacity of each node.
1437 /// @param CurSize Array[Nodes] of current node sizes, or NULL.
1438 /// @param NewSize Array[Nodes] to receive the new node sizes.
1439 /// @param Position Insert position.
1440 /// @param Grow Reserve space for a new element at Position.
1441 /// @return (node, offset) for Position.
1442 IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,
1443 const unsigned *CurSize, unsigned NewSize[],
1444 unsigned Position, bool Grow);
1448 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1449 class IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator {
1450 friend class IntervalMap;
1451 typedef IntervalMapImpl::IdxPair IdxPair;
1453 explicit iterator(IntervalMap &map) : const_iterator(map) {}
1455 void setNodeSize(unsigned Level, unsigned Size);
1456 void setNodeStop(unsigned Level, KeyT Stop);
1457 void insertNode(unsigned Level, NodeRef Node, KeyT Stop);
1458 void overflowLeaf();
1459 void treeInsert(KeyT a, KeyT b, ValT y);
1462 /// insert - Insert mapping [a;b] -> y before the current position.
1463 void insert(KeyT a, KeyT b, ValT y);
1467 /// setNodeSize - Set the size of the node at path[level], updating both path
1468 /// and the real tree.
1469 /// @param level 0 is just below the root, map->height - 1 for the leaves.
1470 /// @param size New node size.
1471 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1472 void IntervalMap<KeyT, ValT, N, Traits>::
1473 iterator::setNodeSize(unsigned Level, unsigned Size) {
1474 this->pathNode(Level).setSize(Size);
1476 this->pathNode(Level-1).branch()
1477 .subtree(this->pathOffset(Level-1)).setSize(Size);
1479 this->map->rootBranch().subtree(this->rootOffset).setSize(Size);
1482 /// setNodeStop - Update the stop key of the current node at level and above.
1483 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1484 void IntervalMap<KeyT, ValT, N, Traits>::
1485 iterator::setNodeStop(unsigned Level, KeyT Stop) {
1487 this->pathNode(Level).branch().stop(this->pathOffset(Level)) = Stop;
1488 if (this->pathOffset(Level) != this->pathNode(Level).size() - 1)
1491 this->map->rootBranch().stop(this->rootOffset) = Stop;
1494 /// insertNode - insert a node before the current path at level.
1495 /// Leave the current path pointing at the new node.
1496 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1497 void IntervalMap<KeyT, ValT, N, Traits>::
1498 iterator::insertNode(unsigned Level, NodeRef Node, KeyT Stop) {
1500 // Insert into the root branch node.
1501 IntervalMap &IM = *this->map;
1502 if (IM.rootSize < RootBranch::Capacity) {
1503 IM.rootBranch().insert(this->rootOffset, IM.rootSize, Node, Stop);
1508 // We need to split the root while keeping our position.
1509 IdxPair Offset = IM.splitRoot(this->rootOffset);
1510 this->rootOffset = Offset.first;
1511 this->path.insert(this->path.begin(),std::make_pair(
1512 this->map->rootBranch().subtree(Offset.first), Offset.second));
1516 // When inserting before end(), make sure we have a valid path.
1517 if (!this->valid()) {
1518 this->treeDecrement();
1519 ++this->pathOffset(Level-1);
1522 // Insert into the branch node at level-1.
1523 NodeRef NR = this->pathNode(Level-1);
1524 unsigned Offset = this->pathOffset(Level-1);
1525 assert(NR.size() < Branch::Capacity && "Branch overflow");
1526 NR.branch().insert(Offset, NR.size(), Node, Stop);
1527 setNodeSize(Level - 1, NR.size() + 1);
1531 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1532 void IntervalMap<KeyT, ValT, N, Traits>::
1533 iterator::insert(KeyT a, KeyT b, ValT y) {
1534 if (this->branched())
1535 return treeInsert(a, b, y);
1536 IdxPair IP = this->map->rootLeaf().insertFrom(this->rootOffset,
1537 this->map->rootSize,
1539 if (IP.second <= RootLeaf::Capacity) {
1540 this->rootOffset = IP.first;
1541 this->map->rootSize = IP.second;
1544 IdxPair Offset = this->map->branchRoot(this->rootOffset);
1545 this->rootOffset = Offset.first;
1546 this->path.push_back(std::make_pair(
1547 this->map->rootBranch().subtree(Offset.first), Offset.second));
1548 treeInsert(a, b, y);
1552 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1553 void IntervalMap<KeyT, ValT, N, Traits>::
1554 iterator::treeInsert(KeyT a, KeyT b, ValT y) {
1555 if (!this->valid()) {
1556 // end() has an empty path. Go back to the last leaf node and use an
1557 // invalid offset instead.
1558 this->treeDecrement();
1559 ++this->treeLeafOffset();
1561 IdxPair IP = this->treeLeaf().insertFrom(this->treeLeafOffset(),
1562 this->treeLeafSize(), a, b, y);
1563 this->treeLeafOffset() = IP.first;
1564 if (IP.second <= Leaf::Capacity) {
1565 setNodeSize(this->map->height - 1, IP.second);
1566 if (IP.first == IP.second - 1)
1567 setNodeStop(this->map->height - 1, this->treeLeaf().stop(IP.first));
1570 // Leaf node has no space.
1572 IP = this->treeLeaf().insertFrom(this->treeLeafOffset(),
1573 this->treeLeafSize(), a, b, y);
1574 this->treeLeafOffset() = IP.first;
1575 setNodeSize(this->map->height-1, IP.second);
1576 if (IP.first == IP.second - 1)
1577 setNodeStop(this->map->height - 1, this->treeLeaf().stop(IP.first));
1579 // FIXME: Handle cross-node coalescing.
1582 // overflowLeaf - Distribute entries of the current leaf node evenly among
1583 // its siblings and ensure that the current node is not full.
1584 // This may require allocating a new node.
1585 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1586 void IntervalMap<KeyT, ValT, N, Traits>::
1587 iterator::overflowLeaf() {
1588 unsigned CurSize[4];
1591 unsigned Elements = 0;
1592 unsigned Offset = this->treeLeafOffset();
1594 // Do we have a left sibling?
1595 NodeRef LeftSib = this->leftSibling(this->map->height-1);
1597 Offset += Elements = CurSize[Nodes] = LeftSib.size();
1598 Node[Nodes++] = &LeftSib.leaf();
1601 // Current leaf node.
1602 Elements += CurSize[Nodes] = this->treeLeafSize();
1603 Node[Nodes++] = &this->treeLeaf();
1605 // Do we have a right sibling?
1606 NodeRef RightSib = this->rightSibling(this->map->height-1);
1608 Offset += Elements = CurSize[Nodes] = RightSib.size();
1609 Node[Nodes++] = &RightSib.leaf();
1612 // Do we need to allocate a new node?
1613 unsigned NewNode = 0;
1614 if (Elements + 1 > Nodes * Leaf::Capacity) {
1615 // Insert NewNode at the penultimate position, or after a single node.
1616 NewNode = Nodes == 1 ? 1 : Nodes - 1;
1617 CurSize[Nodes] = CurSize[NewNode];
1618 Node[Nodes] = Node[NewNode];
1619 CurSize[NewNode] = 0;
1620 Node[NewNode] = this->map->allocLeaf();
1624 // Compute the new element distribution.
1625 unsigned NewSize[4];
1627 IntervalMapImpl::distribute(Nodes, Elements, Leaf::Capacity,
1628 CurSize, NewSize, Offset, true);
1630 // Move current location to the leftmost node.
1632 this->treeDecrement();
1634 // Move elements right.
1635 for (int n = Nodes - 1; n; --n) {
1636 if (CurSize[n] == NewSize[n])
1638 for (int m = n - 1; m != -1; --m) {
1639 int d = Node[n]->adjLeftSib(CurSize[n], *Node[m], CurSize[m],
1640 NewSize[n] - CurSize[n]);
1643 // Keep going if the current node was exhausted.
1644 if (CurSize[n] >= NewSize[n])
1649 // Move elements left.
1650 for (unsigned n = 0; n != Nodes - 1; ++n) {
1651 if (CurSize[n] == NewSize[n])
1653 for (unsigned m = n + 1; m != Nodes; ++m) {
1654 int d = Node[m]->adjLeftSib(CurSize[m], *Node[n], CurSize[n],
1655 CurSize[n] - NewSize[n]);
1658 // Keep going if the current node was exhausted.
1659 if (CurSize[n] >= NewSize[n])
1665 for (unsigned n = 0; n != Nodes; n++)
1666 assert(CurSize[n] == NewSize[n] && "Insufficient element shuffle");
1669 // Elements have been rearranged, now update node sizes and stops.
1672 KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1);
1673 if (NewNode && Pos == NewNode)
1674 insertNode(this->map->height - 1, NodeRef(Node[Pos], NewSize[Pos]), Stop);
1676 setNodeSize(this->map->height - 1, NewSize[Pos]);
1677 setNodeStop(this->map->height - 1, Stop);
1679 if (Pos + 1 == Nodes)
1681 this->treeIncrement();
1685 // Where was I? Find NewOffset.
1686 while(Pos != NewOffset.first) {
1687 this->treeDecrement();
1690 this->treeLeafOffset() = NewOffset.second;