1//===- llvm/ADT/IntervalMap.h - A sorted interval map -----------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements a coalescing interval map for small objects.
11//
12// KeyT objects are mapped to ValT objects. Intervals of keys that map to the
13// same value are represented in a compressed form.
14//
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.
17//
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
21// objects.
22//
23// A Traits class specifies how keys are compared. It also allows IntervalMap to
24// work with both closed and half-open intervals.
25//
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()
29// iterator methods.
30//
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.
33//
34//===----------------------------------------------------------------------===//
35//
36// Synopsis:
37//
38// template <typename KeyT, typename ValT, unsigned N, typename Traits>
39// class IntervalMap {
40// public:
41//   typedef KeyT key_type;
42//   typedef ValT mapped_type;
43//   typedef RecyclingAllocator<...> Allocator;
44//   class iterator;
45//   class const_iterator;
46//
47//   explicit IntervalMap(Allocator&);
48//   ~IntervalMap():
49//
50//   bool empty() const;
51//   KeyT start() const;
52//   KeyT stop() const;
53//   ValT lookup(KeyT x, Value NotFound = Value()) const;
54//
55//   const_iterator begin() const;
56//   const_iterator end() const;
57//   iterator begin();
58//   iterator end();
59//   const_iterator find(KeyT x) const;
60//   iterator find(KeyT x);
61//
62//   void insert(KeyT a, KeyT b, ValT y);
63//   void clear();
64// };
65//
66// template <typename KeyT, typename ValT, unsigned N, typename Traits>
67// class IntervalMap::const_iterator :
68//   public std::iterator<std::bidirectional_iterator_tag, ValT> {
69// public:
70//   bool operator==(const const_iterator &) const;
71//   bool operator!=(const const_iterator &) const;
72//   bool valid() const;
73//
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;
79//
80//   const_iterator &operator++();
81//   const_iterator &operator++(int);
82//   const_iterator &operator--();
83//   const_iterator &operator--(int);
84//   void goToBegin();
85//   void goToEnd();
86//   void find(KeyT x);
87//   void advanceTo(KeyT x);
88// };
89//
90// template <typename KeyT, typename ValT, unsigned N, typename Traits>
91// class IntervalMap::iterator : public const_iterator {
92// public:
93//   void insert(KeyT a, KeyT b, Value y);
94//   void erase();
95// };
96//
97//===----------------------------------------------------------------------===//
98
99#ifndef LLVM_ADT_INTERVALMAP_H
100#define LLVM_ADT_INTERVALMAP_H
101
102#include "llvm/ADT/PointerIntPair.h"
103#include "llvm/ADT/SmallVector.h"
104#include "llvm/Support/Allocator.h"
105#include "llvm/Support/RecyclingAllocator.h"
106#include <iterator>
107
108namespace llvm {
109
110
111//===----------------------------------------------------------------------===//
112//---                              Key traits                              ---//
113//===----------------------------------------------------------------------===//
114//
115// The IntervalMap works with closed or half-open intervals.
116// Adjacent intervals that map to the same value are coalesced.
117//
118// The IntervalMapInfo traits class is used to determine if a key is contained
119// in an interval, and if two intervals are adjacent so they can be coalesced.
120// The provided implementation works for closed integer intervals, other keys
121// probably need a specialized version.
122//
123// The point x is contained in [a;b] when !startLess(x, a) && !stopLess(b, x).
124//
125// It is assumed that (a;b] half-open intervals are not used, only [a;b) is
126// allowed. This is so that stopLess(a, b) can be used to determine if two
127// intervals overlap.
128//
129//===----------------------------------------------------------------------===//
130
131template <typename T>
132struct IntervalMapInfo {
133
134  /// startLess - Return true if x is not in [a;b].
135  /// This is x < a both for closed intervals and for [a;b) half-open intervals.
136  static inline bool startLess(const T &x, const T &a) {
137    return x < a;
138  }
139
140  /// stopLess - Return true if x is not in [a;b].
141  /// This is b < x for a closed interval, b <= x for [a;b) half-open intervals.
142  static inline bool stopLess(const T &b, const T &x) {
143    return b < x;
144  }
145
146  /// adjacent - Return true when the intervals [x;a] and [b;y] can coalesce.
147  /// This is a+1 == b for closed intervals, a == b for half-open intervals.
148  static inline bool adjacent(const T &a, const T &b) {
149    return a+1 == b;
150  }
151
152};
153
154template <typename T>
155struct IntervalMapHalfOpenInfo {
156
157  /// startLess - Return true if x is not in [a;b).
158  static inline bool startLess(const T &x, const T &a) {
159    return x < a;
160  }
161
162  /// stopLess - Return true if x is not in [a;b).
163  static inline bool stopLess(const T &b, const T &x) {
164    return b <= x;
165  }
166
167  /// adjacent - Return true when the intervals [x;a) and [b;y) can coalesce.
168  static inline bool adjacent(const T &a, const T &b) {
169    return a == b;
170  }
171
172};
173
174/// IntervalMapImpl - Namespace used for IntervalMap implementation details.
175/// It should be considered private to the implementation.
176namespace IntervalMapImpl {
177
178// Forward declarations.
179template <typename, typename, unsigned, typename> class LeafNode;
180template <typename, typename, unsigned, typename> class BranchNode;
181
182typedef std::pair<unsigned,unsigned> IdxPair;
183
184
185//===----------------------------------------------------------------------===//
186//---                    IntervalMapImpl::NodeBase                         ---//
187//===----------------------------------------------------------------------===//
188//
189// Both leaf and branch nodes store vectors of pairs.
190// Leaves store ((KeyT, KeyT), ValT) pairs, branches use (NodeRef, KeyT).
191//
192// Keys and values are stored in separate arrays to avoid padding caused by
193// different object alignments. This also helps improve locality of reference
194// when searching the keys.
195//
196// The nodes don't know how many elements they contain - that information is
197// stored elsewhere. Omitting the size field prevents padding and allows a node
198// to fill the allocated cache lines completely.
199//
200// These are typical key and value sizes, the node branching factor (N), and
201// wasted space when nodes are sized to fit in three cache lines (192 bytes):
202//
203//   T1  T2   N Waste  Used by
204//    4   4  24   0    Branch<4> (32-bit pointers)
205//    8   4  16   0    Leaf<4,4>, Branch<4>
206//    8   8  12   0    Leaf<4,8>, Branch<8>
207//   16   4   9  12    Leaf<8,4>
208//   16   8   8   0    Leaf<8,8>
209//
210//===----------------------------------------------------------------------===//
211
212template <typename T1, typename T2, unsigned N>
213class NodeBase {
214public:
215  enum { Capacity = N };
216
217  T1 first[N];
218  T2 second[N];
219
220  /// copy - Copy elements from another node.
221  /// @param Other Node elements are copied from.
222  /// @param i     Beginning of the source range in other.
223  /// @param j     Beginning of the destination range in this.
224  /// @param Count Number of elements to copy.
225  template <unsigned M>
226  void copy(const NodeBase<T1, T2, M> &Other, unsigned i,
227            unsigned j, unsigned Count) {
228    assert(i + Count <= M && "Invalid source range");
229    assert(j + Count <= N && "Invalid dest range");
230    for (unsigned e = i + Count; i != e; ++i, ++j) {
231      first[j]  = Other.first[i];
232      second[j] = Other.second[i];
233    }
234  }
235
236  /// moveLeft - Move elements to the left.
237  /// @param i     Beginning of the source range.
238  /// @param j     Beginning of the destination range.
239  /// @param Count Number of elements to copy.
240  void moveLeft(unsigned i, unsigned j, unsigned Count) {
241    assert(j <= i && "Use moveRight shift elements right");
242    copy(*this, i, j, Count);
243  }
244
245  /// moveRight - Move elements to the right.
246  /// @param i     Beginning of the source range.
247  /// @param j     Beginning of the destination range.
248  /// @param Count Number of elements to copy.
249  void moveRight(unsigned i, unsigned j, unsigned Count) {
250    assert(i <= j && "Use moveLeft shift elements left");
251    assert(j + Count <= N && "Invalid range");
252    while (Count--) {
253      first[j + Count]  = first[i + Count];
254      second[j + Count] = second[i + Count];
255    }
256  }
257
258  /// erase - Erase elements [i;j).
259  /// @param i    Beginning of the range to erase.
260  /// @param j    End of the range. (Exclusive).
261  /// @param Size Number of elements in node.
262  void erase(unsigned i, unsigned j, unsigned Size) {
263    moveLeft(j, i, Size - j);
264  }
265
266  /// erase - Erase element at i.
267  /// @param i    Index of element to erase.
268  /// @param Size Number of elements in node.
269  void erase(unsigned i, unsigned Size) {
270    erase(i, i+1, Size);
271  }
272
273  /// shift - Shift elements [i;size) 1 position to the right.
274  /// @param i    Beginning of the range to move.
275  /// @param Size Number of elements in node.
276  void shift(unsigned i, unsigned Size) {
277    moveRight(i, i + 1, Size - i);
278  }
279
280  /// transferToLeftSib - Transfer elements to a left sibling node.
281  /// @param Size  Number of elements in this.
282  /// @param Sib   Left sibling node.
283  /// @param SSize Number of elements in sib.
284  /// @param Count Number of elements to transfer.
285  void transferToLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize,
286                         unsigned Count) {
287    Sib.copy(*this, 0, SSize, Count);
288    erase(0, Count, Size);
289  }
290
291  /// transferToRightSib - Transfer elements to a right sibling node.
292  /// @param Size  Number of elements in this.
293  /// @param Sib   Right sibling node.
294  /// @param SSize Number of elements in sib.
295  /// @param Count Number of elements to transfer.
296  void transferToRightSib(unsigned Size, NodeBase &Sib, unsigned SSize,
297                          unsigned Count) {
298    Sib.moveRight(0, Count, SSize);
299    Sib.copy(*this, Size-Count, 0, Count);
300  }
301
302  /// adjustFromLeftSib - Adjust the number if elements in this node by moving
303  /// elements to or from a left sibling node.
304  /// @param Size  Number of elements in this.
305  /// @param Sib   Right sibling node.
306  /// @param SSize Number of elements in sib.
307  /// @param Add   The number of elements to add to this node, possibly < 0.
308  /// @return      Number of elements added to this node, possibly negative.
309  int adjustFromLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add) {
310    if (Add > 0) {
311      // We want to grow, copy from sib.
312      unsigned Count = std::min(std::min(unsigned(Add), SSize), N - Size);
313      Sib.transferToRightSib(SSize, *this, Size, Count);
314      return Count;
315    } else {
316      // We want to shrink, copy to sib.
317      unsigned Count = std::min(std::min(unsigned(-Add), Size), N - SSize);
318      transferToLeftSib(Size, Sib, SSize, Count);
319      return -Count;
320    }
321  }
322};
323
324/// IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes.
325/// @param Node  Array of pointers to sibling nodes.
326/// @param Nodes Number of nodes.
327/// @param CurSize Array of current node sizes, will be overwritten.
328/// @param NewSize Array of desired node sizes.
329template <typename NodeT>
330void adjustSiblingSizes(NodeT *Node[], unsigned Nodes,
331                        unsigned CurSize[], const unsigned NewSize[]) {
332  // Move elements right.
333  for (int n = Nodes - 1; n; --n) {
334    if (CurSize[n] == NewSize[n])
335      continue;
336    for (int m = n - 1; m != -1; --m) {
337      int d = Node[n]->adjustFromLeftSib(CurSize[n], *Node[m], CurSize[m],
338                                         NewSize[n] - CurSize[n]);
339      CurSize[m] -= d;
340      CurSize[n] += d;
341      // Keep going if the current node was exhausted.
342      if (CurSize[n] >= NewSize[n])
343          break;
344    }
345  }
346
347  if (Nodes == 0)
348    return;
349
350  // Move elements left.
351  for (unsigned n = 0; n != Nodes - 1; ++n) {
352    if (CurSize[n] == NewSize[n])
353      continue;
354    for (unsigned m = n + 1; m != Nodes; ++m) {
355      int d = Node[m]->adjustFromLeftSib(CurSize[m], *Node[n], CurSize[n],
356                                        CurSize[n] -  NewSize[n]);
357      CurSize[m] += d;
358      CurSize[n] -= d;
359      // Keep going if the current node was exhausted.
360      if (CurSize[n] >= NewSize[n])
361          break;
362    }
363  }
364
365#ifndef NDEBUG
366  for (unsigned n = 0; n != Nodes; n++)
367    assert(CurSize[n] == NewSize[n] && "Insufficient element shuffle");
368#endif
369}
370
371/// IntervalMapImpl::distribute - Compute a new distribution of node elements
372/// after an overflow or underflow. Reserve space for a new element at Position,
373/// and compute the node that will hold Position after redistributing node
374/// elements.
375///
376/// It is required that
377///
378///   Elements == sum(CurSize), and
379///   Elements + Grow <= Nodes * Capacity.
380///
381/// NewSize[] will be filled in such that:
382///
383///   sum(NewSize) == Elements, and
384///   NewSize[i] <= Capacity.
385///
386/// The returned index is the node where Position will go, so:
387///
388///   sum(NewSize[0..idx-1]) <= Position
389///   sum(NewSize[0..idx])   >= Position
390///
391/// The last equality, sum(NewSize[0..idx]) == Position, can only happen when
392/// Grow is set and NewSize[idx] == Capacity-1. The index points to the node
393/// before the one holding the Position'th element where there is room for an
394/// insertion.
395///
396/// @param Nodes    The number of nodes.
397/// @param Elements Total elements in all nodes.
398/// @param Capacity The capacity of each node.
399/// @param CurSize  Array[Nodes] of current node sizes, or NULL.
400/// @param NewSize  Array[Nodes] to receive the new node sizes.
401/// @param Position Insert position.
402/// @param Grow     Reserve space for a new element at Position.
403/// @return         (node, offset) for Position.
404IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,
405                   const unsigned *CurSize, unsigned NewSize[],
406                   unsigned Position, bool Grow);
407
408
409//===----------------------------------------------------------------------===//
410//---                   IntervalMapImpl::NodeSizer                         ---//
411//===----------------------------------------------------------------------===//
412//
413// Compute node sizes from key and value types.
414//
415// The branching factors are chosen to make nodes fit in three cache lines.
416// This may not be possible if keys or values are very large. Such large objects
417// are handled correctly, but a std::map would probably give better performance.
418//
419//===----------------------------------------------------------------------===//
420
421enum {
422  // Cache line size. Most architectures have 32 or 64 byte cache lines.
423  // We use 64 bytes here because it provides good branching factors.
424  Log2CacheLine = 6,
425  CacheLineBytes = 1 << Log2CacheLine,
426  DesiredNodeBytes = 3 * CacheLineBytes
427};
428
429template <typename KeyT, typename ValT>
430struct NodeSizer {
431  enum {
432    // Compute the leaf node branching factor that makes a node fit in three
433    // cache lines. The branching factor must be at least 3, or some B+-tree
434    // balancing algorithms won't work.
435    // LeafSize can't be larger than CacheLineBytes. This is required by the
436    // PointerIntPair used by NodeRef.
437    DesiredLeafSize = DesiredNodeBytes /
438      static_cast<unsigned>(2*sizeof(KeyT)+sizeof(ValT)),
439    MinLeafSize = 3,
440    LeafSize = DesiredLeafSize > MinLeafSize ? DesiredLeafSize : MinLeafSize
441  };
442
443  typedef NodeBase<std::pair<KeyT, KeyT>, ValT, LeafSize> LeafBase;
444
445  enum {
446    // Now that we have the leaf branching factor, compute the actual allocation
447    // unit size by rounding up to a whole number of cache lines.
448    AllocBytes = (sizeof(LeafBase) + CacheLineBytes-1) & ~(CacheLineBytes-1),
449
450    // Determine the branching factor for branch nodes.
451    BranchSize = AllocBytes /
452      static_cast<unsigned>(sizeof(KeyT) + sizeof(void*))
453  };
454
455  /// Allocator - The recycling allocator used for both branch and leaf nodes.
456  /// This typedef is very likely to be identical for all IntervalMaps with
457  /// reasonably sized entries, so the same allocator can be shared among
458  /// different kinds of maps.
459  typedef RecyclingAllocator<BumpPtrAllocator, char,
460                             AllocBytes, CacheLineBytes> Allocator;
461
462};
463
464
465//===----------------------------------------------------------------------===//
466//---                     IntervalMapImpl::NodeRef                         ---//
467//===----------------------------------------------------------------------===//
468//
469// B+-tree nodes can be leaves or branches, so we need a polymorphic node
470// pointer that can point to both kinds.
471//
472// All nodes are cache line aligned and the low 6 bits of a node pointer are
473// always 0. These bits are used to store the number of elements in the
474// referenced node. Besides saving space, placing node sizes in the parents
475// allow tree balancing algorithms to run without faulting cache lines for nodes
476// that may not need to be modified.
477//
478// A NodeRef doesn't know whether it references a leaf node or a branch node.
479// It is the responsibility of the caller to use the correct types.
480//
481// Nodes are never supposed to be empty, and it is invalid to store a node size
482// of 0 in a NodeRef. The valid range of sizes is 1-64.
483//
484//===----------------------------------------------------------------------===//
485
486class NodeRef {
487  struct CacheAlignedPointerTraits {
488    static inline void *getAsVoidPointer(void *P) { return P; }
489    static inline void *getFromVoidPointer(void *P) { return P; }
490    enum { NumLowBitsAvailable = Log2CacheLine };
491  };
492  PointerIntPair<void*, Log2CacheLine, unsigned, CacheAlignedPointerTraits> pip;
493
494public:
495  /// NodeRef - Create a null ref.
496  NodeRef() {}
497
498  /// operator bool - Detect a null ref.
499  LLVM_EXPLICIT operator bool() const { return pip.getOpaqueValue(); }
500
501  /// NodeRef - Create a reference to the node p with n elements.
502  template <typename NodeT>
503  NodeRef(NodeT *p, unsigned n) : pip(p, n - 1) {
504    assert(n <= NodeT::Capacity && "Size too big for node");
505  }
506
507  /// size - Return the number of elements in the referenced node.
508  unsigned size() const { return pip.getInt() + 1; }
509
510  /// setSize - Update the node size.
511  void setSize(unsigned n) { pip.setInt(n - 1); }
512
513  /// subtree - Access the i'th subtree reference in a branch node.
514  /// This depends on branch nodes storing the NodeRef array as their first
515  /// member.
516  NodeRef &subtree(unsigned i) const {
517    return reinterpret_cast<NodeRef*>(pip.getPointer())[i];
518  }
519
520  /// get - Dereference as a NodeT reference.
521  template <typename NodeT>
522  NodeT &get() const {
523    return *reinterpret_cast<NodeT*>(pip.getPointer());
524  }
525
526  bool operator==(const NodeRef &RHS) const {
527    if (pip == RHS.pip)
528      return true;
529    assert(pip.getPointer() != RHS.pip.getPointer() && "Inconsistent NodeRefs");
530    return false;
531  }
532
533  bool operator!=(const NodeRef &RHS) const {
534    return !operator==(RHS);
535  }
536};
537
538//===----------------------------------------------------------------------===//
539//---                      IntervalMapImpl::LeafNode                       ---//
540//===----------------------------------------------------------------------===//
541//
542// Leaf nodes store up to N disjoint intervals with corresponding values.
543//
544// The intervals are kept sorted and fully coalesced so there are no adjacent
545// intervals mapping to the same value.
546//
547// These constraints are always satisfied:
548//
549// - Traits::stopLess(start(i), stop(i))    - Non-empty, sane intervals.
550//
551// - Traits::stopLess(stop(i), start(i + 1) - Sorted.
552//
553// - value(i) != value(i + 1) || !Traits::adjacent(stop(i), start(i + 1))
554//                                          - Fully coalesced.
555//
556//===----------------------------------------------------------------------===//
557
558template <typename KeyT, typename ValT, unsigned N, typename Traits>
559class LeafNode : public NodeBase<std::pair<KeyT, KeyT>, ValT, N> {
560public:
561  const KeyT &start(unsigned i) const { return this->first[i].first; }
562  const KeyT &stop(unsigned i) const { return this->first[i].second; }
563  const ValT &value(unsigned i) const { return this->second[i]; }
564
565  KeyT &start(unsigned i) { return this->first[i].first; }
566  KeyT &stop(unsigned i) { return this->first[i].second; }
567  ValT &value(unsigned i) { return this->second[i]; }
568
569  /// findFrom - Find the first interval after i that may contain x.
570  /// @param i    Starting index for the search.
571  /// @param Size Number of elements in node.
572  /// @param x    Key to search for.
573  /// @return     First index with !stopLess(key[i].stop, x), or size.
574  ///             This is the first interval that can possibly contain x.
575  unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
576    assert(i <= Size && Size <= N && "Bad indices");
577    assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
578           "Index is past the needed point");
579    while (i != Size && Traits::stopLess(stop(i), x)) ++i;
580    return i;
581  }
582
583  /// safeFind - Find an interval that is known to exist. This is the same as
584  /// findFrom except is it assumed that x is at least within range of the last
585  /// interval.
586  /// @param i Starting index for the search.
587  /// @param x Key to search for.
588  /// @return  First index with !stopLess(key[i].stop, x), never size.
589  ///          This is the first interval that can possibly contain x.
590  unsigned safeFind(unsigned i, KeyT x) const {
591    assert(i < N && "Bad index");
592    assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
593           "Index is past the needed point");
594    while (Traits::stopLess(stop(i), x)) ++i;
595    assert(i < N && "Unsafe intervals");
596    return i;
597  }
598
599  /// safeLookup - Lookup mapped value for a safe key.
600  /// It is assumed that x is within range of the last entry.
601  /// @param x        Key to search for.
602  /// @param NotFound Value to return if x is not in any interval.
603  /// @return         The mapped value at x or NotFound.
604  ValT safeLookup(KeyT x, ValT NotFound) const {
605    unsigned i = safeFind(0, x);
606    return Traits::startLess(x, start(i)) ? NotFound : value(i);
607  }
608
609  unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y);
610};
611
612/// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as
613/// possible. This may cause the node to grow by 1, or it may cause the node
614/// to shrink because of coalescing.
615/// @param Pos  Starting index = insertFrom(0, size, a)
616/// @param Size Number of elements in node.
617/// @param a    Interval start.
618/// @param b    Interval stop.
619/// @param y    Value be mapped.
620/// @return     (insert position, new size), or (i, Capacity+1) on overflow.
621template <typename KeyT, typename ValT, unsigned N, typename Traits>
622unsigned LeafNode<KeyT, ValT, N, Traits>::
623insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y) {
624  unsigned i = Pos;
625  assert(i <= Size && Size <= N && "Invalid index");
626  assert(!Traits::stopLess(b, a) && "Invalid interval");
627
628  // Verify the findFrom invariant.
629  assert((i == 0 || Traits::stopLess(stop(i - 1), a)));
630  assert((i == Size || !Traits::stopLess(stop(i), a)));
631  assert((i == Size || Traits::stopLess(b, start(i))) && "Overlapping insert");
632
633  // Coalesce with previous interval.
634  if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a)) {
635    Pos = i - 1;
636    // Also coalesce with next interval?
637    if (i != Size && value(i) == y && Traits::adjacent(b, start(i))) {
638      stop(i - 1) = stop(i);
639      this->erase(i, Size);
640      return Size - 1;
641    }
642    stop(i - 1) = b;
643    return Size;
644  }
645
646  // Detect overflow.
647  if (i == N)
648    return N + 1;
649
650  // Add new interval at end.
651  if (i == Size) {
652    start(i) = a;
653    stop(i) = b;
654    value(i) = y;
655    return Size + 1;
656  }
657
658  // Try to coalesce with following interval.
659  if (value(i) == y && Traits::adjacent(b, start(i))) {
660    start(i) = a;
661    return Size;
662  }
663
664  // We must insert before i. Detect overflow.
665  if (Size == N)
666    return N + 1;
667
668  // Insert before i.
669  this->shift(i, Size);
670  start(i) = a;
671  stop(i) = b;
672  value(i) = y;
673  return Size + 1;
674}
675
676
677//===----------------------------------------------------------------------===//
678//---                   IntervalMapImpl::BranchNode                        ---//
679//===----------------------------------------------------------------------===//
680//
681// A branch node stores references to 1--N subtrees all of the same height.
682//
683// The key array in a branch node holds the rightmost stop key of each subtree.
684// It is redundant to store the last stop key since it can be found in the
685// parent node, but doing so makes tree balancing a lot simpler.
686//
687// It is unusual for a branch node to only have one subtree, but it can happen
688// in the root node if it is smaller than the normal nodes.
689//
690// When all of the leaf nodes from all the subtrees are concatenated, they must
691// satisfy the same constraints as a single leaf node. They must be sorted,
692// sane, and fully coalesced.
693//
694//===----------------------------------------------------------------------===//
695
696template <typename KeyT, typename ValT, unsigned N, typename Traits>
697class BranchNode : public NodeBase<NodeRef, KeyT, N> {
698public:
699  const KeyT &stop(unsigned i) const { return this->second[i]; }
700  const NodeRef &subtree(unsigned i) const { return this->first[i]; }
701
702  KeyT &stop(unsigned i) { return this->second[i]; }
703  NodeRef &subtree(unsigned i) { return this->first[i]; }
704
705  /// findFrom - Find the first subtree after i that may contain x.
706  /// @param i    Starting index for the search.
707  /// @param Size Number of elements in node.
708  /// @param x    Key to search for.
709  /// @return     First index with !stopLess(key[i], x), or size.
710  ///             This is the first subtree that can possibly contain x.
711  unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
712    assert(i <= Size && Size <= N && "Bad indices");
713    assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
714           "Index to findFrom is past the needed point");
715    while (i != Size && Traits::stopLess(stop(i), x)) ++i;
716    return i;
717  }
718
719  /// safeFind - Find a subtree that is known to exist. This is the same as
720  /// findFrom except is it assumed that x is in range.
721  /// @param i Starting index for the search.
722  /// @param x Key to search for.
723  /// @return  First index with !stopLess(key[i], x), never size.
724  ///          This is the first subtree that can possibly contain x.
725  unsigned safeFind(unsigned i, KeyT x) const {
726    assert(i < N && "Bad index");
727    assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
728           "Index is past the needed point");
729    while (Traits::stopLess(stop(i), x)) ++i;
730    assert(i < N && "Unsafe intervals");
731    return i;
732  }
733
734  /// safeLookup - Get the subtree containing x, Assuming that x is in range.
735  /// @param x Key to search for.
736  /// @return  Subtree containing x
737  NodeRef safeLookup(KeyT x) const {
738    return subtree(safeFind(0, x));
739  }
740
741  /// insert - Insert a new (subtree, stop) pair.
742  /// @param i    Insert position, following entries will be shifted.
743  /// @param Size Number of elements in node.
744  /// @param Node Subtree to insert.
745  /// @param Stop Last key in subtree.
746  void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop) {
747    assert(Size < N && "branch node overflow");
748    assert(i <= Size && "Bad insert position");
749    this->shift(i, Size);
750    subtree(i) = Node;
751    stop(i) = Stop;
752  }
753};
754
755//===----------------------------------------------------------------------===//
756//---                         IntervalMapImpl::Path                        ---//
757//===----------------------------------------------------------------------===//
758//
759// A Path is used by iterators to represent a position in a B+-tree, and the
760// path to get there from the root.
761//
762// The Path class also contains the tree navigation code that doesn't have to
763// be templatized.
764//
765//===----------------------------------------------------------------------===//
766
767class Path {
768  /// Entry - Each step in the path is a node pointer and an offset into that
769  /// node.
770  struct Entry {
771    void *node;
772    unsigned size;
773    unsigned offset;
774
775    Entry(void *Node, unsigned Size, unsigned Offset)
776      : node(Node), size(Size), offset(Offset) {}
777
778    Entry(NodeRef Node, unsigned Offset)
779      : node(&Node.subtree(0)), size(Node.size()), offset(Offset) {}
780
781    NodeRef &subtree(unsigned i) const {
782      return reinterpret_cast<NodeRef*>(node)[i];
783    }
784  };
785
786  /// path - The path entries, path[0] is the root node, path.back() is a leaf.
787  SmallVector<Entry, 4> path;
788
789public:
790  // Node accessors.
791  template <typename NodeT> NodeT &node(unsigned Level) const {
792    return *reinterpret_cast<NodeT*>(path[Level].node);
793  }
794  unsigned size(unsigned Level) const { return path[Level].size; }
795  unsigned offset(unsigned Level) const { return path[Level].offset; }
796  unsigned &offset(unsigned Level) { return path[Level].offset; }
797
798  // Leaf accessors.
799  template <typename NodeT> NodeT &leaf() const {
800    return *reinterpret_cast<NodeT*>(path.back().node);
801  }
802  unsigned leafSize() const { return path.back().size; }
803  unsigned leafOffset() const { return path.back().offset; }
804  unsigned &leafOffset() { return path.back().offset; }
805
806  /// valid - Return true if path is at a valid node, not at end().
807  bool valid() const {
808    return !path.empty() && path.front().offset < path.front().size;
809  }
810
811  /// height - Return the height of the tree corresponding to this path.
812  /// This matches map->height in a full path.
813  unsigned height() const { return path.size() - 1; }
814
815  /// subtree - Get the subtree referenced from Level. When the path is
816  /// consistent, node(Level + 1) == subtree(Level).
817  /// @param Level 0..height-1. The leaves have no subtrees.
818  NodeRef &subtree(unsigned Level) const {
819    return path[Level].subtree(path[Level].offset);
820  }
821
822  /// reset - Reset cached information about node(Level) from subtree(Level -1).
823  /// @param Level 1..height. THe node to update after parent node changed.
824  void reset(unsigned Level) {
825    path[Level] = Entry(subtree(Level - 1), offset(Level));
826  }
827
828  /// push - Add entry to path.
829  /// @param Node Node to add, should be subtree(path.size()-1).
830  /// @param Offset Offset into Node.
831  void push(NodeRef Node, unsigned Offset) {
832    path.push_back(Entry(Node, Offset));
833  }
834
835  /// pop - Remove the last path entry.
836  void pop() {
837    path.pop_back();
838  }
839
840  /// setSize - Set the size of a node both in the path and in the tree.
841  /// @param Level 0..height. Note that setting the root size won't change
842  ///              map->rootSize.
843  /// @param Size New node size.
844  void setSize(unsigned Level, unsigned Size) {
845    path[Level].size = Size;
846    if (Level)
847      subtree(Level - 1).setSize(Size);
848  }
849
850  /// setRoot - Clear the path and set a new root node.
851  /// @param Node New root node.
852  /// @param Size New root size.
853  /// @param Offset Offset into root node.
854  void setRoot(void *Node, unsigned Size, unsigned Offset) {
855    path.clear();
856    path.push_back(Entry(Node, Size, Offset));
857  }
858
859  /// replaceRoot - Replace the current root node with two new entries after the
860  /// tree height has increased.
861  /// @param Root The new root node.
862  /// @param Size Number of entries in the new root.
863  /// @param Offsets Offsets into the root and first branch nodes.
864  void replaceRoot(void *Root, unsigned Size, IdxPair Offsets);
865
866  /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
867  /// @param Level Get the sibling to node(Level).
868  /// @return Left sibling, or NodeRef().
869  NodeRef getLeftSibling(unsigned Level) const;
870
871  /// moveLeft - Move path to the left sibling at Level. Leave nodes below Level
872  /// unaltered.
873  /// @param Level Move node(Level).
874  void moveLeft(unsigned Level);
875
876  /// fillLeft - Grow path to Height by taking leftmost branches.
877  /// @param Height The target height.
878  void fillLeft(unsigned Height) {
879    while (height() < Height)
880      push(subtree(height()), 0);
881  }
882
883  /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
884  /// @param Level Get the sinbling to node(Level).
885  /// @return Left sibling, or NodeRef().
886  NodeRef getRightSibling(unsigned Level) const;
887
888  /// moveRight - Move path to the left sibling at Level. Leave nodes below
889  /// Level unaltered.
890  /// @param Level Move node(Level).
891  void moveRight(unsigned Level);
892
893  /// atBegin - Return true if path is at begin().
894  bool atBegin() const {
895    for (unsigned i = 0, e = path.size(); i != e; ++i)
896      if (path[i].offset != 0)
897        return false;
898    return true;
899  }
900
901  /// atLastEntry - Return true if the path is at the last entry of the node at
902  /// Level.
903  /// @param Level Node to examine.
904  bool atLastEntry(unsigned Level) const {
905    return path[Level].offset == path[Level].size - 1;
906  }
907
908  /// legalizeForInsert - Prepare the path for an insertion at Level. When the
909  /// path is at end(), node(Level) may not be a legal node. legalizeForInsert
910  /// ensures that node(Level) is real by moving back to the last node at Level,
911  /// and setting offset(Level) to size(Level) if required.
912  /// @param Level The level where an insertion is about to take place.
913  void legalizeForInsert(unsigned Level) {
914    if (valid())
915      return;
916    moveLeft(Level);
917    ++path[Level].offset;
918  }
919};
920
921} // namespace IntervalMapImpl
922
923
924//===----------------------------------------------------------------------===//
925//---                          IntervalMap                                ----//
926//===----------------------------------------------------------------------===//
927
928template <typename KeyT, typename ValT,
929          unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize,
930          typename Traits = IntervalMapInfo<KeyT> >
931class IntervalMap {
932  typedef IntervalMapImpl::NodeSizer<KeyT, ValT> Sizer;
933  typedef IntervalMapImpl::LeafNode<KeyT, ValT, Sizer::LeafSize, Traits> Leaf;
934  typedef IntervalMapImpl::BranchNode<KeyT, ValT, Sizer::BranchSize, Traits>
935    Branch;
936  typedef IntervalMapImpl::LeafNode<KeyT, ValT, N, Traits> RootLeaf;
937  typedef IntervalMapImpl::IdxPair IdxPair;
938
939  // The RootLeaf capacity is given as a template parameter. We must compute the
940  // corresponding RootBranch capacity.
941  enum {
942    DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) /
943      (sizeof(KeyT) + sizeof(IntervalMapImpl::NodeRef)),
944    RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1
945  };
946
947  typedef IntervalMapImpl::BranchNode<KeyT, ValT, RootBranchCap, Traits>
948    RootBranch;
949
950  // When branched, we store a global start key as well as the branch node.
951  struct RootBranchData {
952    KeyT start;
953    RootBranch node;
954  };
955
956  enum {
957    RootDataSize = sizeof(RootBranchData) > sizeof(RootLeaf) ?
958                   sizeof(RootBranchData) : sizeof(RootLeaf)
959  };
960
961public:
962  typedef typename Sizer::Allocator Allocator;
963  typedef KeyT KeyType;
964  typedef ValT ValueType;
965  typedef Traits KeyTraits;
966
967private:
968  // The root data is either a RootLeaf or a RootBranchData instance.
969  // We can't put them in a union since C++03 doesn't allow non-trivial
970  // constructors in unions.
971  // Instead, we use a char array with pointer alignment. The alignment is
972  // ensured by the allocator member in the class, but still verified in the
973  // constructor. We don't support keys or values that are more aligned than a
974  // pointer.
975  char data[RootDataSize];
976
977  // Tree height.
978  // 0: Leaves in root.
979  // 1: Root points to leaf.
980  // 2: root->branch->leaf ...
981  unsigned height;
982
983  // Number of entries in the root node.
984  unsigned rootSize;
985
986  // Allocator used for creating external nodes.
987  Allocator &allocator;
988
989  /// dataAs - Represent data as a node type without breaking aliasing rules.
990  template <typename T>
991  T &dataAs() const {
992    union {
993      const char *d;
994      T *t;
995    } u;
996    u.d = data;
997    return *u.t;
998  }
999
1000  const RootLeaf &rootLeaf() const {
1001    assert(!branched() && "Cannot acces leaf data in branched root");
1002    return dataAs<RootLeaf>();
1003  }
1004  RootLeaf &rootLeaf() {
1005    assert(!branched() && "Cannot acces leaf data in branched root");
1006    return dataAs<RootLeaf>();
1007  }
1008  RootBranchData &rootBranchData() const {
1009    assert(branched() && "Cannot access branch data in non-branched root");
1010    return dataAs<RootBranchData>();
1011  }
1012  RootBranchData &rootBranchData() {
1013    assert(branched() && "Cannot access branch data in non-branched root");
1014    return dataAs<RootBranchData>();
1015  }
1016  const RootBranch &rootBranch() const { return rootBranchData().node; }
1017  RootBranch &rootBranch()             { return rootBranchData().node; }
1018  KeyT rootBranchStart() const { return rootBranchData().start; }
1019  KeyT &rootBranchStart()      { return rootBranchData().start; }
1020
1021  template <typename NodeT> NodeT *newNode() {
1022    return new(allocator.template Allocate<NodeT>()) NodeT();
1023  }
1024
1025  template <typename NodeT> void deleteNode(NodeT *P) {
1026    P->~NodeT();
1027    allocator.Deallocate(P);
1028  }
1029
1030  IdxPair branchRoot(unsigned Position);
1031  IdxPair splitRoot(unsigned Position);
1032
1033  void switchRootToBranch() {
1034    rootLeaf().~RootLeaf();
1035    height = 1;
1036    new (&rootBranchData()) RootBranchData();
1037  }
1038
1039  void switchRootToLeaf() {
1040    rootBranchData().~RootBranchData();
1041    height = 0;
1042    new(&rootLeaf()) RootLeaf();
1043  }
1044
1045  bool branched() const { return height > 0; }
1046
1047  ValT treeSafeLookup(KeyT x, ValT NotFound) const;
1048  void visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef,
1049                  unsigned Level));
1050  void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level);
1051
1052public:
1053  explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) {
1054    assert((uintptr_t(data) & (alignOf<RootLeaf>() - 1)) == 0 &&
1055           "Insufficient alignment");
1056    new(&rootLeaf()) RootLeaf();
1057  }
1058
1059  ~IntervalMap() {
1060    clear();
1061    rootLeaf().~RootLeaf();
1062  }
1063
1064  /// empty -  Return true when no intervals are mapped.
1065  bool empty() const {
1066    return rootSize == 0;
1067  }
1068
1069  /// start - Return the smallest mapped key in a non-empty map.
1070  KeyT start() const {
1071    assert(!empty() && "Empty IntervalMap has no start");
1072    return !branched() ? rootLeaf().start(0) : rootBranchStart();
1073  }
1074
1075  /// stop - Return the largest mapped key in a non-empty map.
1076  KeyT stop() const {
1077    assert(!empty() && "Empty IntervalMap has no stop");
1078    return !branched() ? rootLeaf().stop(rootSize - 1) :
1079                         rootBranch().stop(rootSize - 1);
1080  }
1081
1082  /// lookup - Return the mapped value at x or NotFound.
1083  ValT lookup(KeyT x, ValT NotFound = ValT()) const {
1084    if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x))
1085      return NotFound;
1086    return branched() ? treeSafeLookup(x, NotFound) :
1087                        rootLeaf().safeLookup(x, NotFound);
1088  }
1089
1090  /// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
1091  /// It is assumed that no key in the interval is mapped to another value, but
1092  /// overlapping intervals already mapped to y will be coalesced.
1093  void insert(KeyT a, KeyT b, ValT y) {
1094    if (branched() || rootSize == RootLeaf::Capacity)
1095      return find(a).insert(a, b, y);
1096
1097    // Easy insert into root leaf.
1098    unsigned p = rootLeaf().findFrom(0, rootSize, a);
1099    rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y);
1100  }
1101
1102  /// clear - Remove all entries.
1103  void clear();
1104
1105  class const_iterator;
1106  class iterator;
1107  friend class const_iterator;
1108  friend class iterator;
1109
1110  const_iterator begin() const {
1111    const_iterator I(*this);
1112    I.goToBegin();
1113    return I;
1114  }
1115
1116  iterator begin() {
1117    iterator I(*this);
1118    I.goToBegin();
1119    return I;
1120  }
1121
1122  const_iterator end() const {
1123    const_iterator I(*this);
1124    I.goToEnd();
1125    return I;
1126  }
1127
1128  iterator end() {
1129    iterator I(*this);
1130    I.goToEnd();
1131    return I;
1132  }
1133
1134  /// find - Return an iterator pointing to the first interval ending at or
1135  /// after x, or end().
1136  const_iterator find(KeyT x) const {
1137    const_iterator I(*this);
1138    I.find(x);
1139    return I;
1140  }
1141
1142  iterator find(KeyT x) {
1143    iterator I(*this);
1144    I.find(x);
1145    return I;
1146  }
1147};
1148
1149/// treeSafeLookup - Return the mapped value at x or NotFound, assuming a
1150/// branched root.
1151template <typename KeyT, typename ValT, unsigned N, typename Traits>
1152ValT IntervalMap<KeyT, ValT, N, Traits>::
1153treeSafeLookup(KeyT x, ValT NotFound) const {
1154  assert(branched() && "treeLookup assumes a branched root");
1155
1156  IntervalMapImpl::NodeRef NR = rootBranch().safeLookup(x);
1157  for (unsigned h = height-1; h; --h)
1158    NR = NR.get<Branch>().safeLookup(x);
1159  return NR.get<Leaf>().safeLookup(x, NotFound);
1160}
1161
1162
1163// branchRoot - Switch from a leaf root to a branched root.
1164// Return the new (root offset, node offset) corresponding to Position.
1165template <typename KeyT, typename ValT, unsigned N, typename Traits>
1166IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
1167branchRoot(unsigned Position) {
1168  using namespace IntervalMapImpl;
1169  // How many external leaf nodes to hold RootLeaf+1?
1170  const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1;
1171
1172  // Compute element distribution among new nodes.
1173  unsigned size[Nodes];
1174  IdxPair NewOffset(0, Position);
1175
1176  // Is is very common for the root node to be smaller than external nodes.
1177  if (Nodes == 1)
1178    size[0] = rootSize;
1179  else
1180    NewOffset = distribute(Nodes, rootSize, Leaf::Capacity,  nullptr, size,
1181                           Position, true);
1182
1183  // Allocate new nodes.
1184  unsigned pos = 0;
1185  NodeRef node[Nodes];
1186  for (unsigned n = 0; n != Nodes; ++n) {
1187    Leaf *L = newNode<Leaf>();
1188    L->copy(rootLeaf(), pos, 0, size[n]);
1189    node[n] = NodeRef(L, size[n]);
1190    pos += size[n];
1191  }
1192
1193  // Destroy the old leaf node, construct branch node instead.
1194  switchRootToBranch();
1195  for (unsigned n = 0; n != Nodes; ++n) {
1196    rootBranch().stop(n) = node[n].template get<Leaf>().stop(size[n]-1);
1197    rootBranch().subtree(n) = node[n];
1198  }
1199  rootBranchStart() = node[0].template get<Leaf>().start(0);
1200  rootSize = Nodes;
1201  return NewOffset;
1202}
1203
1204// splitRoot - Split the current BranchRoot into multiple Branch nodes.
1205// Return the new (root offset, node offset) corresponding to Position.
1206template <typename KeyT, typename ValT, unsigned N, typename Traits>
1207IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
1208splitRoot(unsigned Position) {
1209  using namespace IntervalMapImpl;
1210  // How many external leaf nodes to hold RootBranch+1?
1211  const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1;
1212
1213  // Compute element distribution among new nodes.
1214  unsigned Size[Nodes];
1215  IdxPair NewOffset(0, Position);
1216
1217  // Is is very common for the root node to be smaller than external nodes.
1218  if (Nodes == 1)
1219    Size[0] = rootSize;
1220  else
1221    NewOffset = distribute(Nodes, rootSize, Leaf::Capacity,  nullptr, Size,
1222                           Position, true);
1223
1224  // Allocate new nodes.
1225  unsigned Pos = 0;
1226  NodeRef Node[Nodes];
1227  for (unsigned n = 0; n != Nodes; ++n) {
1228    Branch *B = newNode<Branch>();
1229    B->copy(rootBranch(), Pos, 0, Size[n]);
1230    Node[n] = NodeRef(B, Size[n]);
1231    Pos += Size[n];
1232  }
1233
1234  for (unsigned n = 0; n != Nodes; ++n) {
1235    rootBranch().stop(n) = Node[n].template get<Branch>().stop(Size[n]-1);
1236    rootBranch().subtree(n) = Node[n];
1237  }
1238  rootSize = Nodes;
1239  ++height;
1240  return NewOffset;
1241}
1242
1243/// visitNodes - Visit each external node.
1244template <typename KeyT, typename ValT, unsigned N, typename Traits>
1245void IntervalMap<KeyT, ValT, N, Traits>::
1246visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, unsigned Height)) {
1247  if (!branched())
1248    return;
1249  SmallVector<IntervalMapImpl::NodeRef, 4> Refs, NextRefs;
1250
1251  // Collect level 0 nodes from the root.
1252  for (unsigned i = 0; i != rootSize; ++i)
1253    Refs.push_back(rootBranch().subtree(i));
1254
1255  // Visit all branch nodes.
1256  for (unsigned h = height - 1; h; --h) {
1257    for (unsigned i = 0, e = Refs.size(); i != e; ++i) {
1258      for (unsigned j = 0, s = Refs[i].size(); j != s; ++j)
1259        NextRefs.push_back(Refs[i].subtree(j));
1260      (this->*f)(Refs[i], h);
1261    }
1262    Refs.clear();
1263    Refs.swap(NextRefs);
1264  }
1265
1266  // Visit all leaf nodes.
1267  for (unsigned i = 0, e = Refs.size(); i != e; ++i)
1268    (this->*f)(Refs[i], 0);
1269}
1270
1271template <typename KeyT, typename ValT, unsigned N, typename Traits>
1272void IntervalMap<KeyT, ValT, N, Traits>::
1273deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) {
1274  if (Level)
1275    deleteNode(&Node.get<Branch>());
1276  else
1277    deleteNode(&Node.get<Leaf>());
1278}
1279
1280template <typename KeyT, typename ValT, unsigned N, typename Traits>
1281void IntervalMap<KeyT, ValT, N, Traits>::
1282clear() {
1283  if (branched()) {
1284    visitNodes(&IntervalMap::deleteNode);
1285    switchRootToLeaf();
1286  }
1287  rootSize = 0;
1288}
1289
1290//===----------------------------------------------------------------------===//
1291//---                   IntervalMap::const_iterator                       ----//
1292//===----------------------------------------------------------------------===//
1293
1294template <typename KeyT, typename ValT, unsigned N, typename Traits>
1295class IntervalMap<KeyT, ValT, N, Traits>::const_iterator :
1296  public std::iterator<std::bidirectional_iterator_tag, ValT> {
1297protected:
1298  friend class IntervalMap;
1299
1300  // The map referred to.
1301  IntervalMap *map;
1302
1303  // We store a full path from the root to the current position.
1304  // The path may be partially filled, but never between iterator calls.
1305  IntervalMapImpl::Path path;
1306
1307  explicit const_iterator(const IntervalMap &map) :
1308    map(const_cast<IntervalMap*>(&map)) {}
1309
1310  bool branched() const {
1311    assert(map && "Invalid iterator");
1312    return map->branched();
1313  }
1314
1315  void setRoot(unsigned Offset) {
1316    if (branched())
1317      path.setRoot(&map->rootBranch(), map->rootSize, Offset);
1318    else
1319      path.setRoot(&map->rootLeaf(), map->rootSize, Offset);
1320  }
1321
1322  void pathFillFind(KeyT x);
1323  void treeFind(KeyT x);
1324  void treeAdvanceTo(KeyT x);
1325
1326  /// unsafeStart - Writable access to start() for iterator.
1327  KeyT &unsafeStart() const {
1328    assert(valid() && "Cannot access invalid iterator");
1329    return branched() ? path.leaf<Leaf>().start(path.leafOffset()) :
1330                        path.leaf<RootLeaf>().start(path.leafOffset());
1331  }
1332
1333  /// unsafeStop - Writable access to stop() for iterator.
1334  KeyT &unsafeStop() const {
1335    assert(valid() && "Cannot access invalid iterator");
1336    return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) :
1337                        path.leaf<RootLeaf>().stop(path.leafOffset());
1338  }
1339
1340  /// unsafeValue - Writable access to value() for iterator.
1341  ValT &unsafeValue() const {
1342    assert(valid() && "Cannot access invalid iterator");
1343    return branched() ? path.leaf<Leaf>().value(path.leafOffset()) :
1344                        path.leaf<RootLeaf>().value(path.leafOffset());
1345  }
1346
1347public:
1348  /// const_iterator - Create an iterator that isn't pointing anywhere.
1349  const_iterator() : map(nullptr) {}
1350
1351  /// setMap - Change the map iterated over. This call must be followed by a
1352  /// call to goToBegin(), goToEnd(), or find()
1353  void setMap(const IntervalMap &m) { map = const_cast<IntervalMap*>(&m); }
1354
1355  /// valid - Return true if the current position is valid, false for end().
1356  bool valid() const { return path.valid(); }
1357
1358  /// atBegin - Return true if the current position is the first map entry.
1359  bool atBegin() const { return path.atBegin(); }
1360
1361  /// start - Return the beginning of the current interval.
1362  const KeyT &start() const { return unsafeStart(); }
1363
1364  /// stop - Return the end of the current interval.
1365  const KeyT &stop() const { return unsafeStop(); }
1366
1367  /// value - Return the mapped value at the current interval.
1368  const ValT &value() const { return unsafeValue(); }
1369
1370  const ValT &operator*() const { return value(); }
1371
1372  bool operator==(const const_iterator &RHS) const {
1373    assert(map == RHS.map && "Cannot compare iterators from different maps");
1374    if (!valid())
1375      return !RHS.valid();
1376    if (path.leafOffset() != RHS.path.leafOffset())
1377      return false;
1378    return &path.template leaf<Leaf>() == &RHS.path.template leaf<Leaf>();
1379  }
1380
1381  bool operator!=(const const_iterator &RHS) const {
1382    return !operator==(RHS);
1383  }
1384
1385  /// goToBegin - Move to the first interval in map.
1386  void goToBegin() {
1387    setRoot(0);
1388    if (branched())
1389      path.fillLeft(map->height);
1390  }
1391
1392  /// goToEnd - Move beyond the last interval in map.
1393  void goToEnd() {
1394    setRoot(map->rootSize);
1395  }
1396
1397  /// preincrement - move to the next interval.
1398  const_iterator &operator++() {
1399    assert(valid() && "Cannot increment end()");
1400    if (++path.leafOffset() == path.leafSize() && branched())
1401      path.moveRight(map->height);
1402    return *this;
1403  }
1404
1405  /// postincrement - Dont do that!
1406  const_iterator operator++(int) {
1407    const_iterator tmp = *this;
1408    operator++();
1409    return tmp;
1410  }
1411
1412  /// predecrement - move to the previous interval.
1413  const_iterator &operator--() {
1414    if (path.leafOffset() && (valid() || !branched()))
1415      --path.leafOffset();
1416    else
1417      path.moveLeft(map->height);
1418    return *this;
1419  }
1420
1421  /// postdecrement - Dont do that!
1422  const_iterator operator--(int) {
1423    const_iterator tmp = *this;
1424    operator--();
1425    return tmp;
1426  }
1427
1428  /// find - Move to the first interval with stop >= x, or end().
1429  /// This is a full search from the root, the current position is ignored.
1430  void find(KeyT x) {
1431    if (branched())
1432      treeFind(x);
1433    else
1434      setRoot(map->rootLeaf().findFrom(0, map->rootSize, x));
1435  }
1436
1437  /// advanceTo - Move to the first interval with stop >= x, or end().
1438  /// The search is started from the current position, and no earlier positions
1439  /// can be found. This is much faster than find() for small moves.
1440  void advanceTo(KeyT x) {
1441    if (!valid())
1442      return;
1443    if (branched())
1444      treeAdvanceTo(x);
1445    else
1446      path.leafOffset() =
1447        map->rootLeaf().findFrom(path.leafOffset(), map->rootSize, x);
1448  }
1449
1450};
1451
1452/// pathFillFind - Complete path by searching for x.
1453/// @param x Key to search for.
1454template <typename KeyT, typename ValT, unsigned N, typename Traits>
1455void IntervalMap<KeyT, ValT, N, Traits>::
1456const_iterator::pathFillFind(KeyT x) {
1457  IntervalMapImpl::NodeRef NR = path.subtree(path.height());
1458  for (unsigned i = map->height - path.height() - 1; i; --i) {
1459    unsigned p = NR.get<Branch>().safeFind(0, x);
1460    path.push(NR, p);
1461    NR = NR.subtree(p);
1462  }
1463  path.push(NR, NR.get<Leaf>().safeFind(0, x));
1464}
1465
1466/// treeFind - Find in a branched tree.
1467/// @param x Key to search for.
1468template <typename KeyT, typename ValT, unsigned N, typename Traits>
1469void IntervalMap<KeyT, ValT, N, Traits>::
1470const_iterator::treeFind(KeyT x) {
1471  setRoot(map->rootBranch().findFrom(0, map->rootSize, x));
1472  if (valid())
1473    pathFillFind(x);
1474}
1475
1476/// treeAdvanceTo - Find position after the current one.
1477/// @param x Key to search for.
1478template <typename KeyT, typename ValT, unsigned N, typename Traits>
1479void IntervalMap<KeyT, ValT, N, Traits>::
1480const_iterator::treeAdvanceTo(KeyT x) {
1481  // Can we stay on the same leaf node?
1482  if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) {
1483    path.leafOffset() = path.leaf<Leaf>().safeFind(path.leafOffset(), x);
1484    return;
1485  }
1486
1487  // Drop the current leaf.
1488  path.pop();
1489
1490  // Search towards the root for a usable subtree.
1491  if (path.height()) {
1492    for (unsigned l = path.height() - 1; l; --l) {
1493      if (!Traits::stopLess(path.node<Branch>(l).stop(path.offset(l)), x)) {
1494        // The branch node at l+1 is usable
1495        path.offset(l + 1) =
1496          path.node<Branch>(l + 1).safeFind(path.offset(l + 1), x);
1497        return pathFillFind(x);
1498      }
1499      path.pop();
1500    }
1501    // Is the level-1 Branch usable?
1502    if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) {
1503      path.offset(1) = path.node<Branch>(1).safeFind(path.offset(1), x);
1504      return pathFillFind(x);
1505    }
1506  }
1507
1508  // We reached the root.
1509  setRoot(map->rootBranch().findFrom(path.offset(0), map->rootSize, x));
1510  if (valid())
1511    pathFillFind(x);
1512}
1513
1514//===----------------------------------------------------------------------===//
1515//---                       IntervalMap::iterator                         ----//
1516//===----------------------------------------------------------------------===//
1517
1518template <typename KeyT, typename ValT, unsigned N, typename Traits>
1519class IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator {
1520  friend class IntervalMap;
1521  typedef IntervalMapImpl::IdxPair IdxPair;
1522
1523  explicit iterator(IntervalMap &map) : const_iterator(map) {}
1524
1525  void setNodeStop(unsigned Level, KeyT Stop);
1526  bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop);
1527  template <typename NodeT> bool overflow(unsigned Level);
1528  void treeInsert(KeyT a, KeyT b, ValT y);
1529  void eraseNode(unsigned Level);
1530  void treeErase(bool UpdateRoot = true);
1531  bool canCoalesceLeft(KeyT Start, ValT x);
1532  bool canCoalesceRight(KeyT Stop, ValT x);
1533
1534public:
1535  /// iterator - Create null iterator.
1536  iterator() {}
1537
1538  /// setStart - Move the start of the current interval.
1539  /// This may cause coalescing with the previous interval.
1540  /// @param a New start key, must not overlap the previous interval.
1541  void setStart(KeyT a);
1542
1543  /// setStop - Move the end of the current interval.
1544  /// This may cause coalescing with the following interval.
1545  /// @param b New stop key, must not overlap the following interval.
1546  void setStop(KeyT b);
1547
1548  /// setValue - Change the mapped value of the current interval.
1549  /// This may cause coalescing with the previous and following intervals.
1550  /// @param x New value.
1551  void setValue(ValT x);
1552
1553  /// setStartUnchecked - Move the start of the current interval without
1554  /// checking for coalescing or overlaps.
1555  /// This should only be used when it is known that coalescing is not required.
1556  /// @param a New start key.
1557  void setStartUnchecked(KeyT a) { this->unsafeStart() = a; }
1558
1559  /// setStopUnchecked - Move the end of the current interval without checking
1560  /// for coalescing or overlaps.
1561  /// This should only be used when it is known that coalescing is not required.
1562  /// @param b New stop key.
1563  void setStopUnchecked(KeyT b) {
1564    this->unsafeStop() = b;
1565    // Update keys in branch nodes as well.
1566    if (this->path.atLastEntry(this->path.height()))
1567      setNodeStop(this->path.height(), b);
1568  }
1569
1570  /// setValueUnchecked - Change the mapped value of the current interval
1571  /// without checking for coalescing.
1572  /// @param x New value.
1573  void setValueUnchecked(ValT x) { this->unsafeValue() = x; }
1574
1575  /// insert - Insert mapping [a;b] -> y before the current position.
1576  void insert(KeyT a, KeyT b, ValT y);
1577
1578  /// erase - Erase the current interval.
1579  void erase();
1580
1581  iterator &operator++() {
1582    const_iterator::operator++();
1583    return *this;
1584  }
1585
1586  iterator operator++(int) {
1587    iterator tmp = *this;
1588    operator++();
1589    return tmp;
1590  }
1591
1592  iterator &operator--() {
1593    const_iterator::operator--();
1594    return *this;
1595  }
1596
1597  iterator operator--(int) {
1598    iterator tmp = *this;
1599    operator--();
1600    return tmp;
1601  }
1602
1603};
1604
1605/// canCoalesceLeft - Can the current interval coalesce to the left after
1606/// changing start or value?
1607/// @param Start New start of current interval.
1608/// @param Value New value for current interval.
1609/// @return True when updating the current interval would enable coalescing.
1610template <typename KeyT, typename ValT, unsigned N, typename Traits>
1611bool IntervalMap<KeyT, ValT, N, Traits>::
1612iterator::canCoalesceLeft(KeyT Start, ValT Value) {
1613  using namespace IntervalMapImpl;
1614  Path &P = this->path;
1615  if (!this->branched()) {
1616    unsigned i = P.leafOffset();
1617    RootLeaf &Node = P.leaf<RootLeaf>();
1618    return i && Node.value(i-1) == Value &&
1619                Traits::adjacent(Node.stop(i-1), Start);
1620  }
1621  // Branched.
1622  if (unsigned i = P.leafOffset()) {
1623    Leaf &Node = P.leaf<Leaf>();
1624    return Node.value(i-1) == Value && Traits::adjacent(Node.stop(i-1), Start);
1625  } else if (NodeRef NR = P.getLeftSibling(P.height())) {
1626    unsigned i = NR.size() - 1;
1627    Leaf &Node = NR.get<Leaf>();
1628    return Node.value(i) == Value && Traits::adjacent(Node.stop(i), Start);
1629  }
1630  return false;
1631}
1632
1633/// canCoalesceRight - Can the current interval coalesce to the right after
1634/// changing stop or value?
1635/// @param Stop New stop of current interval.
1636/// @param Value New value for current interval.
1637/// @return True when updating the current interval would enable coalescing.
1638template <typename KeyT, typename ValT, unsigned N, typename Traits>
1639bool IntervalMap<KeyT, ValT, N, Traits>::
1640iterator::canCoalesceRight(KeyT Stop, ValT Value) {
1641  using namespace IntervalMapImpl;
1642  Path &P = this->path;
1643  unsigned i = P.leafOffset() + 1;
1644  if (!this->branched()) {
1645    if (i >= P.leafSize())
1646      return false;
1647    RootLeaf &Node = P.leaf<RootLeaf>();
1648    return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));
1649  }
1650  // Branched.
1651  if (i < P.leafSize()) {
1652    Leaf &Node = P.leaf<Leaf>();
1653    return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));
1654  } else if (NodeRef NR = P.getRightSibling(P.height())) {
1655    Leaf &Node = NR.get<Leaf>();
1656    return Node.value(0) == Value && Traits::adjacent(Stop, Node.start(0));
1657  }
1658  return false;
1659}
1660
1661/// setNodeStop - Update the stop key of the current node at level and above.
1662template <typename KeyT, typename ValT, unsigned N, typename Traits>
1663void IntervalMap<KeyT, ValT, N, Traits>::
1664iterator::setNodeStop(unsigned Level, KeyT Stop) {
1665  // There are no references to the root node, so nothing to update.
1666  if (!Level)
1667    return;
1668  IntervalMapImpl::Path &P = this->path;
1669  // Update nodes pointing to the current node.
1670  while (--Level) {
1671    P.node<Branch>(Level).stop(P.offset(Level)) = Stop;
1672    if (!P.atLastEntry(Level))
1673      return;
1674  }
1675  // Update root separately since it has a different layout.
1676  P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop;
1677}
1678
1679template <typename KeyT, typename ValT, unsigned N, typename Traits>
1680void IntervalMap<KeyT, ValT, N, Traits>::
1681iterator::setStart(KeyT a) {
1682  assert(Traits::stopLess(a, this->stop()) && "Cannot move start beyond stop");
1683  KeyT &CurStart = this->unsafeStart();
1684  if (!Traits::startLess(a, CurStart) || !canCoalesceLeft(a, this->value())) {
1685    CurStart = a;
1686    return;
1687  }
1688  // Coalesce with the interval to the left.
1689  --*this;
1690  a = this->start();
1691  erase();
1692  setStartUnchecked(a);
1693}
1694
1695template <typename KeyT, typename ValT, unsigned N, typename Traits>
1696void IntervalMap<KeyT, ValT, N, Traits>::
1697iterator::setStop(KeyT b) {
1698  assert(Traits::stopLess(this->start(), b) && "Cannot move stop beyond start");
1699  if (Traits::startLess(b, this->stop()) ||
1700      !canCoalesceRight(b, this->value())) {
1701    setStopUnchecked(b);
1702    return;
1703  }
1704  // Coalesce with interval to the right.
1705  KeyT a = this->start();
1706  erase();
1707  setStartUnchecked(a);
1708}
1709
1710template <typename KeyT, typename ValT, unsigned N, typename Traits>
1711void IntervalMap<KeyT, ValT, N, Traits>::
1712iterator::setValue(ValT x) {
1713  setValueUnchecked(x);
1714  if (canCoalesceRight(this->stop(), x)) {
1715    KeyT a = this->start();
1716    erase();
1717    setStartUnchecked(a);
1718  }
1719  if (canCoalesceLeft(this->start(), x)) {
1720    --*this;
1721    KeyT a = this->start();
1722    erase();
1723    setStartUnchecked(a);
1724  }
1725}
1726
1727/// insertNode - insert a node before the current path at level.
1728/// Leave the current path pointing at the new node.
1729/// @param Level path index of the node to be inserted.
1730/// @param Node The node to be inserted.
1731/// @param Stop The last index in the new node.
1732/// @return True if the tree height was increased.
1733template <typename KeyT, typename ValT, unsigned N, typename Traits>
1734bool IntervalMap<KeyT, ValT, N, Traits>::
1735iterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) {
1736  assert(Level && "Cannot insert next to the root");
1737  bool SplitRoot = false;
1738  IntervalMap &IM = *this->map;
1739  IntervalMapImpl::Path &P = this->path;
1740
1741  if (Level == 1) {
1742    // Insert into the root branch node.
1743    if (IM.rootSize < RootBranch::Capacity) {
1744      IM.rootBranch().insert(P.offset(0), IM.rootSize, Node, Stop);
1745      P.setSize(0, ++IM.rootSize);
1746      P.reset(Level);
1747      return SplitRoot;
1748    }
1749
1750    // We need to split the root while keeping our position.
1751    SplitRoot = true;
1752    IdxPair Offset = IM.splitRoot(P.offset(0));
1753    P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset);
1754
1755    // Fall through to insert at the new higher level.
1756    ++Level;
1757  }
1758
1759  // When inserting before end(), make sure we have a valid path.
1760  P.legalizeForInsert(--Level);
1761
1762  // Insert into the branch node at Level-1.
1763  if (P.size(Level) == Branch::Capacity) {
1764    // Branch node is full, handle handle the overflow.
1765    assert(!SplitRoot && "Cannot overflow after splitting the root");
1766    SplitRoot = overflow<Branch>(Level);
1767    Level += SplitRoot;
1768  }
1769  P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop);
1770  P.setSize(Level, P.size(Level) + 1);
1771  if (P.atLastEntry(Level))
1772    setNodeStop(Level, Stop);
1773  P.reset(Level + 1);
1774  return SplitRoot;
1775}
1776
1777// insert
1778template <typename KeyT, typename ValT, unsigned N, typename Traits>
1779void IntervalMap<KeyT, ValT, N, Traits>::
1780iterator::insert(KeyT a, KeyT b, ValT y) {
1781  if (this->branched())
1782    return treeInsert(a, b, y);
1783  IntervalMap &IM = *this->map;
1784  IntervalMapImpl::Path &P = this->path;
1785
1786  // Try simple root leaf insert.
1787  unsigned Size = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y);
1788
1789  // Was the root node insert successful?
1790  if (Size <= RootLeaf::Capacity) {
1791    P.setSize(0, IM.rootSize = Size);
1792    return;
1793  }
1794
1795  // Root leaf node is full, we must branch.
1796  IdxPair Offset = IM.branchRoot(P.leafOffset());
1797  P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset);
1798
1799  // Now it fits in the new leaf.
1800  treeInsert(a, b, y);
1801}
1802
1803
1804template <typename KeyT, typename ValT, unsigned N, typename Traits>
1805void IntervalMap<KeyT, ValT, N, Traits>::
1806iterator::treeInsert(KeyT a, KeyT b, ValT y) {
1807  using namespace IntervalMapImpl;
1808  Path &P = this->path;
1809
1810  if (!P.valid())
1811    P.legalizeForInsert(this->map->height);
1812
1813  // Check if this insertion will extend the node to the left.
1814  if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<Leaf>().start(0))) {
1815    // Node is growing to the left, will it affect a left sibling node?
1816    if (NodeRef Sib = P.getLeftSibling(P.height())) {
1817      Leaf &SibLeaf = Sib.get<Leaf>();
1818      unsigned SibOfs = Sib.size() - 1;
1819      if (SibLeaf.value(SibOfs) == y &&
1820          Traits::adjacent(SibLeaf.stop(SibOfs), a)) {
1821        // This insertion will coalesce with the last entry in SibLeaf. We can
1822        // handle it in two ways:
1823        //  1. Extend SibLeaf.stop to b and be done, or
1824        //  2. Extend a to SibLeaf, erase the SibLeaf entry and continue.
1825        // We prefer 1., but need 2 when coalescing to the right as well.
1826        Leaf &CurLeaf = P.leaf<Leaf>();
1827        P.moveLeft(P.height());
1828        if (Traits::stopLess(b, CurLeaf.start(0)) &&
1829            (y != CurLeaf.value(0) || !Traits::adjacent(b, CurLeaf.start(0)))) {
1830          // Easy, just extend SibLeaf and we're done.
1831          setNodeStop(P.height(), SibLeaf.stop(SibOfs) = b);
1832          return;
1833        } else {
1834          // We have both left and right coalescing. Erase the old SibLeaf entry
1835          // and continue inserting the larger interval.
1836          a = SibLeaf.start(SibOfs);
1837          treeErase(/* UpdateRoot= */false);
1838        }
1839      }
1840    } else {
1841      // No left sibling means we are at begin(). Update cached bound.
1842      this->map->rootBranchStart() = a;
1843    }
1844  }
1845
1846  // When we are inserting at the end of a leaf node, we must update stops.
1847  unsigned Size = P.leafSize();
1848  bool Grow = P.leafOffset() == Size;
1849  Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), Size, a, b, y);
1850
1851  // Leaf insertion unsuccessful? Overflow and try again.
1852  if (Size > Leaf::Capacity) {
1853    overflow<Leaf>(P.height());
1854    Grow = P.leafOffset() == P.leafSize();
1855    Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y);
1856    assert(Size <= Leaf::Capacity && "overflow() didn't make room");
1857  }
1858
1859  // Inserted, update offset and leaf size.
1860  P.setSize(P.height(), Size);
1861
1862  // Insert was the last node entry, update stops.
1863  if (Grow)
1864    setNodeStop(P.height(), b);
1865}
1866
1867/// erase - erase the current interval and move to the next position.
1868template <typename KeyT, typename ValT, unsigned N, typename Traits>
1869void IntervalMap<KeyT, ValT, N, Traits>::
1870iterator::erase() {
1871  IntervalMap &IM = *this->map;
1872  IntervalMapImpl::Path &P = this->path;
1873  assert(P.valid() && "Cannot erase end()");
1874  if (this->branched())
1875    return treeErase();
1876  IM.rootLeaf().erase(P.leafOffset(), IM.rootSize);
1877  P.setSize(0, --IM.rootSize);
1878}
1879
1880/// treeErase - erase() for a branched tree.
1881template <typename KeyT, typename ValT, unsigned N, typename Traits>
1882void IntervalMap<KeyT, ValT, N, Traits>::
1883iterator::treeErase(bool UpdateRoot) {
1884  IntervalMap &IM = *this->map;
1885  IntervalMapImpl::Path &P = this->path;
1886  Leaf &Node = P.leaf<Leaf>();
1887
1888  // Nodes are not allowed to become empty.
1889  if (P.leafSize() == 1) {
1890    IM.deleteNode(&Node);
1891    eraseNode(IM.height);
1892    // Update rootBranchStart if we erased begin().
1893    if (UpdateRoot && IM.branched() && P.valid() && P.atBegin())
1894      IM.rootBranchStart() = P.leaf<Leaf>().start(0);
1895    return;
1896  }
1897
1898  // Erase current entry.
1899  Node.erase(P.leafOffset(), P.leafSize());
1900  unsigned NewSize = P.leafSize() - 1;
1901  P.setSize(IM.height, NewSize);
1902  // When we erase the last entry, update stop and move to a legal position.
1903  if (P.leafOffset() == NewSize) {
1904    setNodeStop(IM.height, Node.stop(NewSize - 1));
1905    P.moveRight(IM.height);
1906  } else if (UpdateRoot && P.atBegin())
1907    IM.rootBranchStart() = P.leaf<Leaf>().start(0);
1908}
1909
1910/// eraseNode - Erase the current node at Level from its parent and move path to
1911/// the first entry of the next sibling node.
1912/// The node must be deallocated by the caller.
1913/// @param Level 1..height, the root node cannot be erased.
1914template <typename KeyT, typename ValT, unsigned N, typename Traits>
1915void IntervalMap<KeyT, ValT, N, Traits>::
1916iterator::eraseNode(unsigned Level) {
1917  assert(Level && "Cannot erase root node");
1918  IntervalMap &IM = *this->map;
1919  IntervalMapImpl::Path &P = this->path;
1920
1921  if (--Level == 0) {
1922    IM.rootBranch().erase(P.offset(0), IM.rootSize);
1923    P.setSize(0, --IM.rootSize);
1924    // If this cleared the root, switch to height=0.
1925    if (IM.empty()) {
1926      IM.switchRootToLeaf();
1927      this->setRoot(0);
1928      return;
1929    }
1930  } else {
1931    // Remove node ref from branch node at Level.
1932    Branch &Parent = P.node<Branch>(Level);
1933    if (P.size(Level) == 1) {
1934      // Branch node became empty, remove it recursively.
1935      IM.deleteNode(&Parent);
1936      eraseNode(Level);
1937    } else {
1938      // Branch node won't become empty.
1939      Parent.erase(P.offset(Level), P.size(Level));
1940      unsigned NewSize = P.size(Level) - 1;
1941      P.setSize(Level, NewSize);
1942      // If we removed the last branch, update stop and move to a legal pos.
1943      if (P.offset(Level) == NewSize) {
1944        setNodeStop(Level, Parent.stop(NewSize - 1));
1945        P.moveRight(Level);
1946      }
1947    }
1948  }
1949  // Update path cache for the new right sibling position.
1950  if (P.valid()) {
1951    P.reset(Level + 1);
1952    P.offset(Level + 1) = 0;
1953  }
1954}
1955
1956/// overflow - Distribute entries of the current node evenly among
1957/// its siblings and ensure that the current node is not full.
1958/// This may require allocating a new node.
1959/// @tparam NodeT The type of node at Level (Leaf or Branch).
1960/// @param Level path index of the overflowing node.
1961/// @return True when the tree height was changed.
1962template <typename KeyT, typename ValT, unsigned N, typename Traits>
1963template <typename NodeT>
1964bool IntervalMap<KeyT, ValT, N, Traits>::
1965iterator::overflow(unsigned Level) {
1966  using namespace IntervalMapImpl;
1967  Path &P = this->path;
1968  unsigned CurSize[4];
1969  NodeT *Node[4];
1970  unsigned Nodes = 0;
1971  unsigned Elements = 0;
1972  unsigned Offset = P.offset(Level);
1973
1974  // Do we have a left sibling?
1975  NodeRef LeftSib = P.getLeftSibling(Level);
1976  if (LeftSib) {
1977    Offset += Elements = CurSize[Nodes] = LeftSib.size();
1978    Node[Nodes++] = &LeftSib.get<NodeT>();
1979  }
1980
1981  // Current node.
1982  Elements += CurSize[Nodes] = P.size(Level);
1983  Node[Nodes++] = &P.node<NodeT>(Level);
1984
1985  // Do we have a right sibling?
1986  NodeRef RightSib = P.getRightSibling(Level);
1987  if (RightSib) {
1988    Elements += CurSize[Nodes] = RightSib.size();
1989    Node[Nodes++] = &RightSib.get<NodeT>();
1990  }
1991
1992  // Do we need to allocate a new node?
1993  unsigned NewNode = 0;
1994  if (Elements + 1 > Nodes * NodeT::Capacity) {
1995    // Insert NewNode at the penultimate position, or after a single node.
1996    NewNode = Nodes == 1 ? 1 : Nodes - 1;
1997    CurSize[Nodes] = CurSize[NewNode];
1998    Node[Nodes] = Node[NewNode];
1999    CurSize[NewNode] = 0;
2000    Node[NewNode] = this->map->template newNode<NodeT>();
2001    ++Nodes;
2002  }
2003
2004  // Compute the new element distribution.
2005  unsigned NewSize[4];
2006  IdxPair NewOffset = distribute(Nodes, Elements, NodeT::Capacity,
2007                                 CurSize, NewSize, Offset, true);
2008  adjustSiblingSizes(Node, Nodes, CurSize, NewSize);
2009
2010  // Move current location to the leftmost node.
2011  if (LeftSib)
2012    P.moveLeft(Level);
2013
2014  // Elements have been rearranged, now update node sizes and stops.
2015  bool SplitRoot = false;
2016  unsigned Pos = 0;
2017  for (;;) {
2018    KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1);
2019    if (NewNode && Pos == NewNode) {
2020      SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop);
2021      Level += SplitRoot;
2022    } else {
2023      P.setSize(Level, NewSize[Pos]);
2024      setNodeStop(Level, Stop);
2025    }
2026    if (Pos + 1 == Nodes)
2027      break;
2028    P.moveRight(Level);
2029    ++Pos;
2030  }
2031
2032  // Where was I? Find NewOffset.
2033  while(Pos != NewOffset.first) {
2034    P.moveLeft(Level);
2035    --Pos;
2036  }
2037  P.offset(Level) = NewOffset.second;
2038  return SplitRoot;
2039}
2040
2041//===----------------------------------------------------------------------===//
2042//---                       IntervalMapOverlaps                           ----//
2043//===----------------------------------------------------------------------===//
2044
2045/// IntervalMapOverlaps - Iterate over the overlaps of mapped intervals in two
2046/// IntervalMaps. The maps may be different, but the KeyT and Traits types
2047/// should be the same.
2048///
2049/// Typical uses:
2050///
2051/// 1. Test for overlap:
2052///    bool overlap = IntervalMapOverlaps(a, b).valid();
2053///
2054/// 2. Enumerate overlaps:
2055///    for (IntervalMapOverlaps I(a, b); I.valid() ; ++I) { ... }
2056///
2057template <typename MapA, typename MapB>
2058class IntervalMapOverlaps {
2059  typedef typename MapA::KeyType KeyType;
2060  typedef typename MapA::KeyTraits Traits;
2061  typename MapA::const_iterator posA;
2062  typename MapB::const_iterator posB;
2063
2064  /// advance - Move posA and posB forward until reaching an overlap, or until
2065  /// either meets end.
2066  /// Don't move the iterators if they are already overlapping.
2067  void advance() {
2068    if (!valid())
2069      return;
2070
2071    if (Traits::stopLess(posA.stop(), posB.start())) {
2072      // A ends before B begins. Catch up.
2073      posA.advanceTo(posB.start());
2074      if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
2075        return;
2076    } else if (Traits::stopLess(posB.stop(), posA.start())) {
2077      // B ends before A begins. Catch up.
2078      posB.advanceTo(posA.start());
2079      if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
2080        return;
2081    } else
2082      // Already overlapping.
2083      return;
2084
2085    for (;;) {
2086      // Make a.end > b.start.
2087      posA.advanceTo(posB.start());
2088      if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
2089        return;
2090      // Make b.end > a.start.
2091      posB.advanceTo(posA.start());
2092      if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
2093        return;
2094    }
2095  }
2096
2097public:
2098  /// IntervalMapOverlaps - Create an iterator for the overlaps of a and b.
2099  IntervalMapOverlaps(const MapA &a, const MapB &b)
2100    : posA(b.empty() ? a.end() : a.find(b.start())),
2101      posB(posA.valid() ? b.find(posA.start()) : b.end()) { advance(); }
2102
2103  /// valid - Return true if iterator is at an overlap.
2104  bool valid() const {
2105    return posA.valid() && posB.valid();
2106  }
2107
2108  /// a - access the left hand side in the overlap.
2109  const typename MapA::const_iterator &a() const { return posA; }
2110
2111  /// b - access the right hand side in the overlap.
2112  const typename MapB::const_iterator &b() const { return posB; }
2113
2114  /// start - Beginning of the overlapping interval.
2115  KeyType start() const {
2116    KeyType ak = a().start();
2117    KeyType bk = b().start();
2118    return Traits::startLess(ak, bk) ? bk : ak;
2119  }
2120
2121  /// stop - End of the overlapping interval.
2122  KeyType stop() const {
2123    KeyType ak = a().stop();
2124    KeyType bk = b().stop();
2125    return Traits::startLess(ak, bk) ? ak : bk;
2126  }
2127
2128  /// skipA - Move to the next overlap that doesn't involve a().
2129  void skipA() {
2130    ++posA;
2131    advance();
2132  }
2133
2134  /// skipB - Move to the next overlap that doesn't involve b().
2135  void skipB() {
2136    ++posB;
2137    advance();
2138  }
2139
2140  /// Preincrement - Move to the next overlap.
2141  IntervalMapOverlaps &operator++() {
2142    // Bump the iterator that ends first. The other one may have more overlaps.
2143    if (Traits::startLess(posB.stop(), posA.stop()))
2144      skipB();
2145    else
2146      skipA();
2147    return *this;
2148  }
2149
2150  /// advanceTo - Move to the first overlapping interval with
2151  /// stopLess(x, stop()).
2152  void advanceTo(KeyType x) {
2153    if (!valid())
2154      return;
2155    // Make sure advanceTo sees monotonic keys.
2156    if (Traits::stopLess(posA.stop(), x))
2157      posA.advanceTo(x);
2158    if (Traits::stopLess(posB.stop(), x))
2159      posB.advanceTo(x);
2160    advance();
2161  }
2162};
2163
2164} // namespace llvm
2165
2166#endif
2167