LCOV - code coverage report
Current view: top level - include/llvm/ADT - IntervalMap.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 586 588 99.7 %
Date: 2017-09-14 15:23:50 Functions: 156 203 76.8 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13