1249423Sdim//===- llvm/ADT/IntervalMap.h - A sorted interval map -----------*- C++ -*-===//
2212795Sdim//
3212795Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4212795Sdim// See https://llvm.org/LICENSE.txt for license information.
5212795Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6212795Sdim//
7212795Sdim//===----------------------------------------------------------------------===//
8212795Sdim///
9212795Sdim/// \file
10212795Sdim/// This file implements a coalescing interval map for small objects.
11212795Sdim///
12212795Sdim/// KeyT objects are mapped to ValT objects. Intervals of keys that map to the
13212795Sdim/// same value are represented in a compressed form.
14212795Sdim///
15212795Sdim/// Iterators provide ordered access to the compressed intervals rather than the
16226633Sdim/// individual keys, and insert and erase operations use key intervals as well.
17212795Sdim///
18212795Sdim/// Like SmallVector, IntervalMap will store the first N intervals in the map
19212795Sdim/// object itself without any allocations. When space is exhausted it switches
20212795Sdim/// to a B+-tree representation with very small overhead for small key and
21212795Sdim/// value objects.
22221345Sdim///
23212795Sdim/// A Traits class specifies how keys are compared. It also allows IntervalMap
24212795Sdim/// to work with both closed and half-open intervals.
25249423Sdim///
26212795Sdim/// Keys and values are not stored next to each other in a std::pair, so we
27212795Sdim/// don't provide such a value_type. Dereferencing iterators only returns the
28212795Sdim/// mapped value. The interval bounds are accessible through the start() and
29243830Sdim/// stop() iterator methods.
30212795Sdim///
31221345Sdim/// IntervalMap is optimized for small key and value objects, 4 or 8 bytes
32249423Sdim/// each is the optimal size. For large objects use std::map instead.
33249423Sdim//
34249423Sdim//===----------------------------------------------------------------------===//
35249423Sdim//
36249423Sdim// Synopsis:
37249423Sdim//
38249423Sdim// template <typename KeyT, typename ValT, unsigned N, typename Traits>
39249423Sdim// class IntervalMap {
40249423Sdim// public:
41249423Sdim//   typedef KeyT key_type;
42249423Sdim//   typedef ValT mapped_type;
43249423Sdim//   typedef RecyclingAllocator<...> Allocator;
44249423Sdim//   class iterator;
45212795Sdim//   class const_iterator;
46212795Sdim//
47212795Sdim//   explicit IntervalMap(Allocator&);
48218893Sdim//   ~IntervalMap():
49249423Sdim//
50218893Sdim//   bool empty() const;
51234982Sdim//   KeyT start() const;
52218893Sdim//   KeyT stop() const;
53212795Sdim//   ValT lookup(KeyT x, Value NotFound = Value()) const;
54249423Sdim//
55212795Sdim//   const_iterator begin() const;
56218893Sdim//   const_iterator end() const;
57212795Sdim//   iterator begin();
58212795Sdim//   iterator end();
59226633Sdim//   const_iterator find(KeyT x) const;
60249423Sdim//   iterator find(KeyT x);
61212795Sdim//
62212795Sdim//   void insert(KeyT a, KeyT b, ValT y);
63212795Sdim//   void clear();
64212795Sdim// };
65212795Sdim//
66212795Sdim// template <typename KeyT, typename ValT, unsigned N, typename Traits>
67212795Sdim// class IntervalMap::const_iterator {
68243830Sdim// public:
69243830Sdim//   using iterator_category = std::bidirectional_iterator_tag;
70243830Sdim//   using value_type = ValT;
71243830Sdim//   using difference_type = std::ptrdiff_t;
72243830Sdim//   using pointer = value_type *;
73243830Sdim//   using reference = value_type &;
74243830Sdim//
75243830Sdim//   bool operator==(const const_iterator &) const;
76243830Sdim//   bool operator!=(const const_iterator &) const;
77243830Sdim//   bool valid() const;
78243830Sdim//
79243830Sdim//   const KeyT &start() const;
80243830Sdim//   const KeyT &stop() const;
81243830Sdim//   const ValT &value() const;
82243830Sdim//   const ValT &operator*() const;
83243830Sdim//   const ValT *operator->() const;
84243830Sdim//
85243830Sdim//   const_iterator &operator++();
86243830Sdim//   const_iterator &operator++(int);
87243830Sdim//   const_iterator &operator--();
88243830Sdim//   const_iterator &operator--(int);
89243830Sdim//   void goToBegin();
90226633Sdim//   void goToEnd();
91212795Sdim//   void find(KeyT x);
92212795Sdim//   void advanceTo(KeyT x);
93243830Sdim// };
94243830Sdim//
95243830Sdim// template <typename KeyT, typename ValT, unsigned N, typename Traits>
96243830Sdim// class IntervalMap::iterator : public const_iterator {
97243830Sdim// public:
98243830Sdim//   void insert(KeyT a, KeyT b, Value y);
99212795Sdim//   void erase();
100212795Sdim// };
101226633Sdim//
102226633Sdim//===----------------------------------------------------------------------===//
103226633Sdim
104239462Sdim#ifndef LLVM_ADT_INTERVALMAP_H
105243830Sdim#define LLVM_ADT_INTERVALMAP_H
106243830Sdim
107243830Sdim#include "llvm/ADT/PointerIntPair.h"
108239462Sdim#include "llvm/ADT/SmallVector.h"
109239462Sdim#include "llvm/Support/Allocator.h"
110239462Sdim#include "llvm/Support/RecyclingAllocator.h"
111243830Sdim#include <algorithm>
112249423Sdim#include <cassert>
113249423Sdim#include <iterator>
114249423Sdim#include <new>
115249423Sdim#include <utility>
116249423Sdim
117249423Sdimnamespace llvm {
118249423Sdim
119249423Sdim//===----------------------------------------------------------------------===//
120212795Sdim//---                              Key traits                              ---//
121212795Sdim//===----------------------------------------------------------------------===//
122212795Sdim//
123243830Sdim// The IntervalMap works with closed or half-open intervals.
124243830Sdim// Adjacent intervals that map to the same value are coalesced.
125243830Sdim//
126243830Sdim// The IntervalMapInfo traits class is used to determine if a key is contained
127243830Sdim// in an interval, and if two intervals are adjacent so they can be coalesced.
128243830Sdim// The provided implementation works for closed integer intervals, other keys
129243830Sdim// probably need a specialized version.
130243830Sdim//
131243830Sdim// The point x is contained in [a;b] when !startLess(x, a) && !stopLess(b, x).
132243830Sdim//
133243830Sdim// It is assumed that (a;b] half-open intervals are not used, only [a;b) is
134243830Sdim// allowed. This is so that stopLess(a, b) can be used to determine if two
135243830Sdim// intervals overlap.
136243830Sdim//
137243830Sdim//===----------------------------------------------------------------------===//
138243830Sdim
139212795Sdimtemplate <typename T>
140243830Sdimstruct IntervalMapInfo {
141243830Sdim  /// startLess - Return true if x is not in [a;b].
142243830Sdim  /// This is x < a both for closed intervals and for [a;b) half-open intervals.
143243830Sdim  static inline bool startLess(const T &x, const T &a) {
144243830Sdim    return x < a;
145243830Sdim  }
146212795Sdim
147243830Sdim  /// stopLess - Return true if x is not in [a;b].
148243830Sdim  /// This is b < x for a closed interval, b <= x for [a;b) half-open intervals.
149243830Sdim  static inline bool stopLess(const T &b, const T &x) {
150243830Sdim    return b < x;
151243830Sdim  }
152243830Sdim
153243830Sdim  /// adjacent - Return true when the intervals [x;a] and [b;y] can coalesce.
154243830Sdim  /// This is a+1 == b for closed intervals, a == b for half-open intervals.
155212795Sdim  static inline bool adjacent(const T &a, const T &b) {
156243830Sdim    return a+1 == b;
157243830Sdim  }
158243830Sdim
159243830Sdim  /// nonEmpty - Return true if [a;b] is non-empty.
160243830Sdim  /// This is a <= b for a closed interval, a < b for [a;b) half-open intervals.
161243830Sdim  static inline bool nonEmpty(const T &a, const T &b) {
162243830Sdim    return a <= b;
163243830Sdim  }
164212795Sdim};
165243830Sdim
166243830Sdimtemplate <typename T>
167243830Sdimstruct IntervalMapHalfOpenInfo {
168243830Sdim  /// startLess - Return true if x is not in [a;b).
169243830Sdim  static inline bool startLess(const T &x, const T &a) {
170243830Sdim    return x < a;
171212795Sdim  }
172243830Sdim
173243830Sdim  /// stopLess - Return true if x is not in [a;b).
174243830Sdim  static inline bool stopLess(const T &b, const T &x) {
175243830Sdim    return b <= x;
176212795Sdim  }
177212795Sdim
178243830Sdim  /// adjacent - Return true when the intervals [x;a) and [b;y) can coalesce.
179243830Sdim  static inline bool adjacent(const T &a, const T &b) {
180243830Sdim    return a == b;
181243830Sdim  }
182243830Sdim
183212795Sdim  /// nonEmpty - Return true if [a;b) is non-empty.
184212795Sdim  static inline bool nonEmpty(const T &a, const T &b) {
185243830Sdim    return a < b;
186243830Sdim  }
187243830Sdim};
188243830Sdim
189212795Sdim/// IntervalMapImpl - Namespace used for IntervalMap implementation details.
190212795Sdim/// It should be considered private to the implementation.
191212795Sdimnamespace IntervalMapImpl {
192243830Sdim
193243830Sdimusing IdxPair = std::pair<unsigned,unsigned>;
194212795Sdim
195243830Sdim//===----------------------------------------------------------------------===//
196243830Sdim//---                    IntervalMapImpl::NodeBase                         ---//
197243830Sdim//===----------------------------------------------------------------------===//
198243830Sdim//
199243830Sdim// Both leaf and branch nodes store vectors of pairs.
200243830Sdim// Leaves store ((KeyT, KeyT), ValT) pairs, branches use (NodeRef, KeyT).
201243830Sdim//
202212795Sdim// Keys and values are stored in separate arrays to avoid padding caused by
203243830Sdim// different object alignments. This also helps improve locality of reference
204243830Sdim// when searching the keys.
205243830Sdim//
206243830Sdim// The nodes don't know how many elements they contain - that information is
207243830Sdim// stored elsewhere. Omitting the size field prevents padding and allows a node
208243830Sdim// to fill the allocated cache lines completely.
209212795Sdim//
210243830Sdim// These are typical key and value sizes, the node branching factor (N), and
211243830Sdim// wasted space when nodes are sized to fit in three cache lines (192 bytes):
212243830Sdim//
213263508Sdim//   T1  T2   N Waste  Used by
214263508Sdim//    4   4  24   0    Branch<4> (32-bit pointers)
215243830Sdim//    8   4  16   0    Leaf<4,4>, Branch<4>
216212795Sdim//    8   8  12   0    Leaf<4,8>, Branch<8>
217243830Sdim//   16   4   9  12    Leaf<8,4>
218243830Sdim//   16   8   8   0    Leaf<8,8>
219243830Sdim//
220243830Sdim//===----------------------------------------------------------------------===//
221243830Sdim
222243830Sdimtemplate <typename T1, typename T2, unsigned N>
223243830Sdimclass NodeBase {
224243830Sdimpublic:
225218893Sdim  enum { Capacity = N };
226243830Sdim
227243830Sdim  T1 first[N];
228243830Sdim  T2 second[N];
229218893Sdim
230243830Sdim  /// copy - Copy elements from another node.
231243830Sdim  /// @param Other Node elements are copied from.
232243830Sdim  /// @param i     Beginning of the source range in other.
233243830Sdim  /// @param j     Beginning of the destination range in this.
234218893Sdim  /// @param Count Number of elements to copy.
235243830Sdim  template <unsigned M>
236218893Sdim  void copy(const NodeBase<T1, T2, M> &Other, unsigned i,
237218893Sdim            unsigned j, unsigned Count) {
238243830Sdim    assert(i + Count <= M && "Invalid source range");
239243830Sdim    assert(j + Count <= N && "Invalid dest range");
240243830Sdim    for (unsigned e = i + Count; i != e; ++i, ++j) {
241243830Sdim      first[j]  = Other.first[i];
242243830Sdim      second[j] = Other.second[i];
243243830Sdim    }
244243830Sdim  }
245243830Sdim
246212795Sdim  /// moveLeft - Move elements to the left.
247212795Sdim  /// @param i     Beginning of the source range.
248243830Sdim  /// @param j     Beginning of the destination range.
249243830Sdim  /// @param Count Number of elements to copy.
250243830Sdim  void moveLeft(unsigned i, unsigned j, unsigned Count) {
251243830Sdim    assert(j <= i && "Use moveRight shift elements right");
252243830Sdim    copy(*this, i, j, Count);
253243830Sdim  }
254243830Sdim
255243830Sdim  /// moveRight - Move elements to the right.
256243830Sdim  /// @param i     Beginning of the source range.
257243830Sdim  /// @param j     Beginning of the destination range.
258243830Sdim  /// @param Count Number of elements to copy.
259243830Sdim  void moveRight(unsigned i, unsigned j, unsigned Count) {
260243830Sdim    assert(i <= j && "Use moveLeft shift elements left");
261243830Sdim    assert(j + Count <= N && "Invalid range");
262251662Sdim    while (Count--) {
263251662Sdim      first[j + Count]  = first[i + Count];
264243830Sdim      second[j + Count] = second[i + Count];
265243830Sdim    }
266243830Sdim  }
267243830Sdim
268243830Sdim  /// erase - Erase elements [i;j).
269243830Sdim  /// @param i    Beginning of the range to erase.
270212795Sdim  /// @param j    End of the range. (Exclusive).
271243830Sdim  /// @param Size Number of elements in node.
272243830Sdim  void erase(unsigned i, unsigned j, unsigned Size) {
273243830Sdim    moveLeft(j, i, Size - j);
274243830Sdim  }
275212795Sdim
276243830Sdim  /// erase - Erase element at i.
277243830Sdim  /// @param i    Index of element to erase.
278243830Sdim  /// @param Size Number of elements in node.
279243830Sdim  void erase(unsigned i, unsigned Size) {
280243830Sdim    erase(i, i+1, Size);
281243830Sdim  }
282243830Sdim
283212795Sdim  /// shift - Shift elements [i;size) 1 position to the right.
284243830Sdim  /// @param i    Beginning of the range to move.
285243830Sdim  /// @param Size Number of elements in node.
286243830Sdim  void shift(unsigned i, unsigned Size) {
287243830Sdim    moveRight(i, i + 1, Size - i);
288243830Sdim  }
289243830Sdim
290243830Sdim  /// transferToLeftSib - Transfer elements to a left sibling node.
291243830Sdim  /// @param Size  Number of elements in this.
292243830Sdim  /// @param Sib   Left sibling node.
293243830Sdim  /// @param SSize Number of elements in sib.
294243830Sdim  /// @param Count Number of elements to transfer.
295243830Sdim  void transferToLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize,
296212795Sdim                         unsigned Count) {
297212795Sdim    Sib.copy(*this, 0, SSize, Count);
298243830Sdim    erase(0, Count, Size);
299243830Sdim  }
300243830Sdim
301243830Sdim  /// transferToRightSib - Transfer elements to a right sibling node.
302243830Sdim  /// @param Size  Number of elements in this.
303243830Sdim  /// @param Sib   Right sibling node.
304243830Sdim  /// @param SSize Number of elements in sib.
305243830Sdim  /// @param Count Number of elements to transfer.
306243830Sdim  void transferToRightSib(unsigned Size, NodeBase &Sib, unsigned SSize,
307212795Sdim                          unsigned Count) {
308243830Sdim    Sib.moveRight(0, Count, SSize);
309243830Sdim    Sib.copy(*this, Size-Count, 0, Count);
310243830Sdim  }
311212795Sdim
312212795Sdim  /// adjustFromLeftSib - Adjust the number if elements in this node by moving
313243830Sdim  /// elements to or from a left sibling node.
314243830Sdim  /// @param Size  Number of elements in this.
315243830Sdim  /// @param Sib   Right sibling node.
316243830Sdim  /// @param SSize Number of elements in sib.
317212795Sdim  /// @param Add   The number of elements to add to this node, possibly < 0.
318243830Sdim  /// @return      Number of elements added to this node, possibly negative.
319212795Sdim  int adjustFromLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add) {
320212795Sdim    if (Add > 0) {
321243830Sdim      // We want to grow, copy from sib.
322243830Sdim      unsigned Count = std::min(std::min(unsigned(Add), SSize), N - Size);
323243830Sdim      Sib.transferToRightSib(SSize, *this, Size, Count);
324243830Sdim      return Count;
325243830Sdim    } else {
326212795Sdim      // We want to shrink, copy to sib.
327243830Sdim      unsigned Count = std::min(std::min(unsigned(-Add), Size), N - SSize);
328212795Sdim      transferToLeftSib(Size, Sib, SSize, Count);
329251662Sdim      return -Count;
330251662Sdim    }
331251662Sdim  }
332251662Sdim};
333251662Sdim
334251662Sdim/// IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes.
335251662Sdim/// @param Node  Array of pointers to sibling nodes.
336251662Sdim/// @param Nodes Number of nodes.
337251662Sdim/// @param CurSize Array of current node sizes, will be overwritten.
338243830Sdim/// @param NewSize Array of desired node sizes.
339243830Sdimtemplate <typename NodeT>
340243830Sdimvoid adjustSiblingSizes(NodeT *Node[], unsigned Nodes,
341243830Sdim                        unsigned CurSize[], const unsigned NewSize[]) {
342243830Sdim  // Move elements right.
343212795Sdim  for (int n = Nodes - 1; n; --n) {
344243830Sdim    if (CurSize[n] == NewSize[n])
345243830Sdim      continue;
346243830Sdim    for (int m = n - 1; m != -1; --m) {
347212795Sdim      int d = Node[n]->adjustFromLeftSib(CurSize[n], *Node[m], CurSize[m],
348243830Sdim                                         NewSize[n] - CurSize[n]);
349243830Sdim      CurSize[m] -= d;
350243830Sdim      CurSize[n] += d;
351243830Sdim      // Keep going if the current node was exhausted.
352243830Sdim      if (CurSize[n] >= NewSize[n])
353212795Sdim          break;
354243830Sdim    }
355243830Sdim  }
356243830Sdim
357243830Sdim  if (Nodes == 0)
358243830Sdim    return;
359243830Sdim
360243830Sdim  // Move elements left.
361243830Sdim  for (unsigned n = 0; n != Nodes - 1; ++n) {
362243830Sdim    if (CurSize[n] == NewSize[n])
363243830Sdim      continue;
364243830Sdim    for (unsigned m = n + 1; m != Nodes; ++m) {
365212795Sdim      int d = Node[m]->adjustFromLeftSib(CurSize[m], *Node[n], CurSize[n],
366212795Sdim                                        CurSize[n] -  NewSize[n]);
367212795Sdim      CurSize[m] += d;
368212795Sdim      CurSize[n] -= d;
369212795Sdim      // Keep going if the current node was exhausted.
370243830Sdim      if (CurSize[n] >= NewSize[n])
371243830Sdim          break;
372243830Sdim    }
373243830Sdim  }
374243830Sdim
375243830Sdim#ifndef NDEBUG
376243830Sdim  for (unsigned n = 0; n != Nodes; n++)
377243830Sdim    assert(CurSize[n] == NewSize[n] && "Insufficient element shuffle");
378251662Sdim#endif
379251662Sdim}
380243830Sdim
381243830Sdim/// IntervalMapImpl::distribute - Compute a new distribution of node elements
382243830Sdim/// after an overflow or underflow. Reserve space for a new element at Position,
383212795Sdim/// and compute the node that will hold Position after redistributing node
384212795Sdim/// elements.
385212795Sdim///
386212795Sdim/// It is required that
387212795Sdim///
388212795Sdim///   Elements == sum(CurSize), and
389212795Sdim///   Elements + Grow <= Nodes * Capacity.
390212795Sdim///
391212795Sdim/// NewSize[] will be filled in such that:
392212795Sdim///
393212795Sdim///   sum(NewSize) == Elements, and
394212795Sdim///   NewSize[i] <= Capacity.
395212795Sdim///
396212795Sdim/// The returned index is the node where Position will go, so:
397226633Sdim///
398226633Sdim///   sum(NewSize[0..idx-1]) <= Position
399226633Sdim///   sum(NewSize[0..idx])   >= Position
400212795Sdim///
401212795Sdim/// The last equality, sum(NewSize[0..idx]) == Position, can only happen when
402226633Sdim/// Grow is set and NewSize[idx] == Capacity-1. The index points to the node
403226633Sdim/// before the one holding the Position'th element where there is room for an
404226633Sdim/// insertion.
405226633Sdim///
406226633Sdim/// @param Nodes    The number of nodes.
407226633Sdim/// @param Elements Total elements in all nodes.
408226633Sdim/// @param Capacity The capacity of each node.
409212795Sdim/// @param CurSize  Array[Nodes] of current node sizes, or NULL.
410226633Sdim/// @param NewSize  Array[Nodes] to receive the new node sizes.
411226633Sdim/// @param Position Insert position.
412226633Sdim/// @param Grow     Reserve space for a new element at Position.
413226633Sdim/// @return         (node, offset) for Position.
414226633SdimIdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,
415226633Sdim                   const unsigned *CurSize, unsigned NewSize[],
416226633Sdim                   unsigned Position, bool Grow);
417226633Sdim
418226633Sdim//===----------------------------------------------------------------------===//
419226633Sdim//---                   IntervalMapImpl::NodeSizer                         ---//
420226633Sdim//===----------------------------------------------------------------------===//
421212795Sdim//
422226633Sdim// Compute node sizes from key and value types.
423226633Sdim//
424226633Sdim// The branching factors are chosen to make nodes fit in three cache lines.
425226633Sdim// This may not be possible if keys or values are very large. Such large objects
426212795Sdim// are handled correctly, but a std::map would probably give better performance.
427226633Sdim//
428226633Sdim//===----------------------------------------------------------------------===//
429212795Sdim
430226633Sdimenum {
431226633Sdim  // Cache line size. Most architectures have 32 or 64 byte cache lines.
432226633Sdim  // We use 64 bytes here because it provides good branching factors.
433226633Sdim  Log2CacheLine = 6,
434212795Sdim  CacheLineBytes = 1 << Log2CacheLine,
435226633Sdim  DesiredNodeBytes = 3 * CacheLineBytes
436212795Sdim};
437226633Sdim
438251662Sdimtemplate <typename KeyT, typename ValT>
439251662Sdimstruct NodeSizer {
440251662Sdim  enum {
441251662Sdim    // Compute the leaf node branching factor that makes a node fit in three
442251662Sdim    // cache lines. The branching factor must be at least 3, or some B+-tree
443251662Sdim    // balancing algorithms won't work.
444212795Sdim    // LeafSize can't be larger than CacheLineBytes. This is required by the
445226633Sdim    // PointerIntPair used by NodeRef.
446226633Sdim    DesiredLeafSize = DesiredNodeBytes /
447226633Sdim      static_cast<unsigned>(2*sizeof(KeyT)+sizeof(ValT)),
448226633Sdim    MinLeafSize = 3,
449226633Sdim    LeafSize = DesiredLeafSize > MinLeafSize ? DesiredLeafSize : MinLeafSize
450212795Sdim  };
451212795Sdim
452226633Sdim  using LeafBase = NodeBase<std::pair<KeyT, KeyT>, ValT, LeafSize>;
453226633Sdim
454226633Sdim  enum {
455226633Sdim    // Now that we have the leaf branching factor, compute the actual allocation
456226633Sdim    // unit size by rounding up to a whole number of cache lines.
457212795Sdim    AllocBytes = (sizeof(LeafBase) + CacheLineBytes-1) & ~(CacheLineBytes-1),
458212795Sdim
459226633Sdim    // Determine the branching factor for branch nodes.
460226633Sdim    BranchSize = AllocBytes /
461212795Sdim      static_cast<unsigned>(sizeof(KeyT) + sizeof(void*))
462249423Sdim  };
463249423Sdim
464226633Sdim  /// Allocator - The recycling allocator used for both branch and leaf nodes.
465212795Sdim  /// This typedef is very likely to be identical for all IntervalMaps with
466226633Sdim  /// reasonably sized entries, so the same allocator can be shared among
467249423Sdim  /// different kinds of maps.
468226633Sdim  using Allocator =
469226633Sdim      RecyclingAllocator<BumpPtrAllocator, char, AllocBytes, CacheLineBytes>;
470226633Sdim};
471226633Sdim
472226633Sdim//===----------------------------------------------------------------------===//
473212795Sdim//---                     IntervalMapImpl::NodeRef                         ---//
474249423Sdim//===----------------------------------------------------------------------===//
475249423Sdim//
476226633Sdim// B+-tree nodes can be leaves or branches, so we need a polymorphic node
477249423Sdim// pointer that can point to both kinds.
478226633Sdim//
479212795Sdim// All nodes are cache line aligned and the low 6 bits of a node pointer are
480249423Sdim// always 0. These bits are used to store the number of elements in the
481249423Sdim// referenced node. Besides saving space, placing node sizes in the parents
482249423Sdim// allow tree balancing algorithms to run without faulting cache lines for nodes
483249423Sdim// that may not need to be modified.
484249423Sdim//
485249423Sdim// A NodeRef doesn't know whether it references a leaf node or a branch node.
486249423Sdim// It is the responsibility of the caller to use the correct types.
487249423Sdim//
488249423Sdim// Nodes are never supposed to be empty, and it is invalid to store a node size
489249423Sdim// of 0 in a NodeRef. The valid range of sizes is 1-64.
490226633Sdim//
491226633Sdim//===----------------------------------------------------------------------===//
492226633Sdim
493226633Sdimclass NodeRef {
494226633Sdim  struct CacheAlignedPointerTraits {
495226633Sdim    static inline void *getAsVoidPointer(void *P) { return P; }
496212795Sdim    static inline void *getFromVoidPointer(void *P) { return P; }
497226633Sdim    static constexpr int NumLowBitsAvailable = Log2CacheLine;
498226633Sdim  };
499212795Sdim  PointerIntPair<void*, Log2CacheLine, unsigned, CacheAlignedPointerTraits> pip;
500226633Sdim
501226633Sdimpublic:
502226633Sdim  /// NodeRef - Create a null ref.
503226633Sdim  NodeRef() = default;
504212795Sdim
505234353Sdim  /// operator bool - Detect a null ref.
506249423Sdim  explicit operator bool() const { return pip.getOpaqueValue(); }
507234353Sdim
508234353Sdim  /// NodeRef - Create a reference to the node p with n elements.
509212795Sdim  template <typename NodeT>
510249423Sdim  NodeRef(NodeT *p, unsigned n) : pip(p, n - 1) {
511249423Sdim    assert(n <= NodeT::Capacity && "Size too big for node");
512249423Sdim  }
513249423Sdim
514249423Sdim  /// size - Return the number of elements in the referenced node.
515249423Sdim  unsigned size() const { return pip.getInt() + 1; }
516249423Sdim
517212795Sdim  /// setSize - Update the node size.
518212795Sdim  void setSize(unsigned n) { pip.setInt(n - 1); }
519212795Sdim
520243830Sdim  /// subtree - Access the i'th subtree reference in a branch node.
521226633Sdim  /// This depends on branch nodes storing the NodeRef array as their first
522226633Sdim  /// member.
523226633Sdim  NodeRef &subtree(unsigned i) const {
524226633Sdim    return reinterpret_cast<NodeRef*>(pip.getPointer())[i];
525226633Sdim  }
526226633Sdim
527226633Sdim  /// get - Dereference as a NodeT reference.
528226633Sdim  template <typename NodeT>
529226633Sdim  NodeT &get() const {
530249423Sdim    return *reinterpret_cast<NodeT*>(pip.getPointer());
531249423Sdim  }
532243830Sdim
533226633Sdim  bool operator==(const NodeRef &RHS) const {
534212795Sdim    if (pip == RHS.pip)
535226633Sdim      return true;
536243830Sdim    assert(pip.getPointer() != RHS.pip.getPointer() && "Inconsistent NodeRefs");
537212795Sdim    return false;
538226633Sdim  }
539226633Sdim
540226633Sdim  bool operator!=(const NodeRef &RHS) const {
541234353Sdim    return !operator==(RHS);
542249423Sdim  }
543234353Sdim};
544234353Sdim
545234353Sdim//===----------------------------------------------------------------------===//
546249423Sdim//---                      IntervalMapImpl::LeafNode                       ---//
547249423Sdim//===----------------------------------------------------------------------===//
548249423Sdim//
549249423Sdim// Leaf nodes store up to N disjoint intervals with corresponding values.
550249423Sdim//
551249423Sdim// The intervals are kept sorted and fully coalesced so there are no adjacent
552212795Sdim// intervals mapping to the same value.
553226633Sdim//
554226633Sdim// These constraints are always satisfied:
555249423Sdim//
556226633Sdim// - Traits::stopLess(start(i), stop(i))    - Non-empty, sane intervals.
557226633Sdim//
558226633Sdim// - Traits::stopLess(stop(i), start(i + 1) - Sorted.
559226633Sdim//
560226633Sdim// - value(i) != value(i + 1) || !Traits::adjacent(stop(i), start(i + 1))
561226633Sdim//                                          - Fully coalesced.
562226633Sdim//
563226633Sdim//===----------------------------------------------------------------------===//
564226633Sdim
565226633Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
566212795Sdimclass LeafNode : public NodeBase<std::pair<KeyT, KeyT>, ValT, N> {
567226633Sdimpublic:
568226633Sdim  const KeyT &start(unsigned i) const { return this->first[i].first; }
569243830Sdim  const KeyT &stop(unsigned i) const { return this->first[i].second; }
570249423Sdim  const ValT &value(unsigned i) const { return this->second[i]; }
571249423Sdim
572249423Sdim  KeyT &start(unsigned i) { return this->first[i].first; }
573249423Sdim  KeyT &stop(unsigned i) { return this->first[i].second; }
574249423Sdim  ValT &value(unsigned i) { return this->second[i]; }
575249423Sdim
576249423Sdim  /// findFrom - Find the first interval after i that may contain x.
577249423Sdim  /// @param i    Starting index for the search.
578243830Sdim  /// @param Size Number of elements in node.
579234353Sdim  /// @param x    Key to search for.
580249423Sdim  /// @return     First index with !stopLess(key[i].stop, x), or size.
581249423Sdim  ///             This is the first interval that can possibly contain x.
582249423Sdim  unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
583249423Sdim    assert(i <= Size && Size <= N && "Bad indices");
584249423Sdim    assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
585249423Sdim           "Index is past the needed point");
586249423Sdim    while (i != Size && Traits::stopLess(stop(i), x)) ++i;
587249423Sdim    return i;
588249423Sdim  }
589249423Sdim
590226633Sdim  /// safeFind - Find an interval that is known to exist. This is the same as
591212795Sdim  /// findFrom except is it assumed that x is at least within range of the last
592234353Sdim  /// interval.
593234353Sdim  /// @param i Starting index for the search.
594226633Sdim  /// @param x Key to search for.
595226633Sdim  /// @return  First index with !stopLess(key[i].stop, x), never size.
596226633Sdim  ///          This is the first interval that can possibly contain x.
597226633Sdim  unsigned safeFind(unsigned i, KeyT x) const {
598226633Sdim    assert(i < N && "Bad index");
599226633Sdim    assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
600226633Sdim           "Index is past the needed point");
601212795Sdim    while (Traits::stopLess(stop(i), x)) ++i;
602212795Sdim    assert(i < N && "Unsafe intervals");
603226633Sdim    return i;
604226633Sdim  }
605212795Sdim
606226633Sdim  /// safeLookup - Lookup mapped value for a safe key.
607226633Sdim  /// It is assumed that x is within range of the last entry.
608226633Sdim  /// @param x        Key to search for.
609226633Sdim  /// @param NotFound Value to return if x is not in any interval.
610212795Sdim  /// @return         The mapped value at x or NotFound.
611226633Sdim  ValT safeLookup(KeyT x, ValT NotFound) const {
612226633Sdim    unsigned i = safeFind(0, x);
613226633Sdim    return Traits::startLess(x, start(i)) ? NotFound : value(i);
614226633Sdim  }
615226633Sdim
616226633Sdim  unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y);
617226633Sdim};
618226633Sdim
619226633Sdim/// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as
620226633Sdim/// possible. This may cause the node to grow by 1, or it may cause the node
621226633Sdim/// to shrink because of coalescing.
622226633Sdim/// @param Pos  Starting index = insertFrom(0, size, a)
623226633Sdim/// @param Size Number of elements in node.
624226633Sdim/// @param a    Interval start.
625226633Sdim/// @param b    Interval stop.
626226633Sdim/// @param y    Value be mapped.
627226633Sdim/// @return     (insert position, new size), or (i, Capacity+1) on overflow.
628226633Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
629212795Sdimunsigned LeafNode<KeyT, ValT, N, Traits>::
630212795SdiminsertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y) {
631226633Sdim  unsigned i = Pos;
632226633Sdim  assert(i <= Size && Size <= N && "Invalid index");
633218893Sdim  assert(!Traits::stopLess(b, a) && "Invalid interval");
634226633Sdim
635226633Sdim  // Verify the findFrom invariant.
636226633Sdim  assert((i == 0 || Traits::stopLess(stop(i - 1), a)));
637226633Sdim  assert((i == Size || !Traits::stopLess(stop(i), a)));
638226633Sdim  assert((i == Size || Traits::stopLess(b, start(i))) && "Overlapping insert");
639226633Sdim
640226633Sdim  // Coalesce with previous interval.
641226633Sdim  if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a)) {
642226633Sdim    Pos = i - 1;
643226633Sdim    // Also coalesce with next interval?
644226633Sdim    if (i != Size && value(i) == y && Traits::adjacent(b, start(i))) {
645226633Sdim      stop(i - 1) = stop(i);
646226633Sdim      this->erase(i, Size);
647226633Sdim      return Size - 1;
648226633Sdim    }
649226633Sdim    stop(i - 1) = b;
650226633Sdim    return Size;
651226633Sdim  }
652226633Sdim
653226633Sdim  // Detect overflow.
654226633Sdim  if (i == N)
655226633Sdim    return N + 1;
656226633Sdim
657226633Sdim  // Add new interval at end.
658226633Sdim  if (i == Size) {
659226633Sdim    start(i) = a;
660212795Sdim    stop(i) = b;
661212795Sdim    value(i) = y;
662226633Sdim    return Size + 1;
663226633Sdim  }
664212795Sdim
665226633Sdim  // Try to coalesce with following interval.
666226633Sdim  if (value(i) == y && Traits::adjacent(b, start(i))) {
667226633Sdim    start(i) = a;
668226633Sdim    return Size;
669226633Sdim  }
670226633Sdim
671226633Sdim  // We must insert before i. Detect overflow.
672212795Sdim  if (Size == N)
673226633Sdim    return N + 1;
674226633Sdim
675226633Sdim  // Insert before i.
676218893Sdim  this->shift(i, Size);
677226633Sdim  start(i) = a;
678226633Sdim  stop(i) = b;
679226633Sdim  value(i) = y;
680226633Sdim  return Size + 1;
681226633Sdim}
682226633Sdim
683226633Sdim//===----------------------------------------------------------------------===//
684226633Sdim//---                   IntervalMapImpl::BranchNode                        ---//
685226633Sdim//===----------------------------------------------------------------------===//
686226633Sdim//
687226633Sdim// A branch node stores references to 1--N subtrees all of the same height.
688226633Sdim//
689226633Sdim// The key array in a branch node holds the rightmost stop key of each subtree.
690226633Sdim// It is redundant to store the last stop key since it can be found in the
691226633Sdim// parent node, but doing so makes tree balancing a lot simpler.
692226633Sdim//
693226633Sdim// It is unusual for a branch node to only have one subtree, but it can happen
694226633Sdim// in the root node if it is smaller than the normal nodes.
695226633Sdim//
696226633Sdim// When all of the leaf nodes from all the subtrees are concatenated, they must
697226633Sdim// satisfy the same constraints as a single leaf node. They must be sorted,
698226633Sdim// sane, and fully coalesced.
699226633Sdim//
700226633Sdim//===----------------------------------------------------------------------===//
701226633Sdim
702212795Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
703212795Sdimclass BranchNode : public NodeBase<NodeRef, KeyT, N> {
704226633Sdimpublic:
705226633Sdim  const KeyT &stop(unsigned i) const { return this->second[i]; }
706212795Sdim  const NodeRef &subtree(unsigned i) const { return this->first[i]; }
707226633Sdim
708226633Sdim  KeyT &stop(unsigned i) { return this->second[i]; }
709226633Sdim  NodeRef &subtree(unsigned i) { return this->first[i]; }
710234982Sdim
711226633Sdim  /// findFrom - Find the first subtree after i that may contain x.
712226633Sdim  /// @param i    Starting index for the search.
713249423Sdim  /// @param Size Number of elements in node.
714249423Sdim  /// @param x    Key to search for.
715226633Sdim  /// @return     First index with !stopLess(key[i], x), or size.
716226633Sdim  ///             This is the first subtree that can possibly contain x.
717212795Sdim  unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
718234353Sdim    assert(i <= Size && Size <= N && "Bad indices");
719249423Sdim    assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
720212795Sdim           "Index to findFrom is past the needed point");
721212795Sdim    while (i != Size && Traits::stopLess(stop(i), x)) ++i;
722212795Sdim    return i;
723212795Sdim  }
724212795Sdim
725212795Sdim  /// safeFind - Find a subtree that is known to exist. This is the same as
726212795Sdim  /// findFrom except is it assumed that x is in range.
727212795Sdim  /// @param i Starting index for the search.
728249423Sdim  /// @param x Key to search for.
729212795Sdim  /// @return  First index with !stopLess(key[i], x), never size.
730249423Sdim  ///          This is the first subtree that can possibly contain x.
731212795Sdim  unsigned safeFind(unsigned i, KeyT x) const {
732212795Sdim    assert(i < N && "Bad index");
733212795Sdim    assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
734212795Sdim           "Index is past the needed point");
735212795Sdim    while (Traits::stopLess(stop(i), x)) ++i;
736249423Sdim    assert(i < N && "Unsafe intervals");
737249423Sdim    return i;
738212795Sdim  }
739212795Sdim
740212795Sdim  /// safeLookup - Get the subtree containing x, Assuming that x is in range.
741212795Sdim  /// @param x Key to search for.
742212795Sdim  /// @return  Subtree containing x
743212795Sdim  NodeRef safeLookup(KeyT x) const {
744212795Sdim    return subtree(safeFind(0, x));
745249423Sdim  }
746212795Sdim
747249423Sdim  /// insert - Insert a new (subtree, stop) pair.
748212795Sdim  /// @param i    Insert position, following entries will be shifted.
749212795Sdim  /// @param Size Number of elements in node.
750212795Sdim  /// @param Node Subtree to insert.
751212795Sdim  /// @param Stop Last key in subtree.
752212795Sdim  void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop) {
753212795Sdim    assert(Size < N && "branch node overflow");
754249423Sdim    assert(i <= Size && "Bad insert position");
755249423Sdim    this->shift(i, Size);
756226633Sdim    subtree(i) = Node;
757212795Sdim    stop(i) = Stop;
758212795Sdim  }
759212795Sdim};
760212795Sdim
761212795Sdim//===----------------------------------------------------------------------===//
762226633Sdim//---                         IntervalMapImpl::Path                        ---//
763221345Sdim//===----------------------------------------------------------------------===//
764263508Sdim//
765263508Sdim// A Path is used by iterators to represent a position in a B+-tree, and the
766263508Sdim// path to get there from the root.
767263508Sdim//
768212795Sdim// The Path class also contains the tree navigation code that doesn't have to
769212795Sdim// be templatized.
770221345Sdim//
771226633Sdim//===----------------------------------------------------------------------===//
772221345Sdim
773221345Sdimclass Path {
774221345Sdim  /// Entry - Each step in the path is a node pointer and an offset into that
775221345Sdim  /// node.
776221345Sdim  struct Entry {
777221345Sdim    void *node;
778212795Sdim    unsigned size;
779212795Sdim    unsigned offset;
780212795Sdim
781212795Sdim    Entry(void *Node, unsigned Size, unsigned Offset)
782212795Sdim      : node(Node), size(Size), offset(Offset) {}
783218893Sdim
784234353Sdim    Entry(NodeRef Node, unsigned Offset)
785226633Sdim      : node(&Node.subtree(0)), size(Node.size()), offset(Offset) {}
786212795Sdim
787212795Sdim    NodeRef &subtree(unsigned i) const {
788212795Sdim      return reinterpret_cast<NodeRef*>(node)[i];
789212795Sdim    }
790212795Sdim  };
791212795Sdim
792212795Sdim  /// path - The path entries, path[0] is the root node, path.back() is a leaf.
793212795Sdim  SmallVector<Entry, 4> path;
794212795Sdim
795212795Sdimpublic:
796243830Sdim  // Node accessors.
797224145Sdim  template <typename NodeT> NodeT &node(unsigned Level) const {
798212795Sdim    return *reinterpret_cast<NodeT*>(path[Level].node);
799212795Sdim  }
800212795Sdim  unsigned size(unsigned Level) const { return path[Level].size; }
801212795Sdim  unsigned offset(unsigned Level) const { return path[Level].offset; }
802212795Sdim  unsigned &offset(unsigned Level) { return path[Level].offset; }
803212795Sdim
804226633Sdim  // Leaf accessors.
805226633Sdim  template <typename NodeT> NodeT &leaf() const {
806226633Sdim    return *reinterpret_cast<NodeT*>(path.back().node);
807212795Sdim  }
808212795Sdim  unsigned leafSize() const { return path.back().size; }
809212795Sdim  unsigned leafOffset() const { return path.back().offset; }
810212795Sdim  unsigned &leafOffset() { return path.back().offset; }
811212795Sdim
812212795Sdim  /// valid - Return true if path is at a valid node, not at end().
813212795Sdim  bool valid() const {
814212795Sdim    return !path.empty() && path.front().offset < path.front().size;
815212795Sdim  }
816212795Sdim
817212795Sdim  /// height - Return the height of the tree corresponding to this path.
818212795Sdim  /// This matches map->height in a full path.
819212795Sdim  unsigned height() const { return path.size() - 1; }
820212795Sdim
821212795Sdim  /// subtree - Get the subtree referenced from Level. When the path is
822212795Sdim  /// consistent, node(Level + 1) == subtree(Level).
823239462Sdim  /// @param Level 0..height-1. The leaves have no subtrees.
824212795Sdim  NodeRef &subtree(unsigned Level) const {
825212795Sdim    return path[Level].subtree(path[Level].offset);
826212795Sdim  }
827212795Sdim
828212795Sdim  /// reset - Reset cached information about node(Level) from subtree(Level -1).
829212795Sdim  /// @param Level 1..height. The node to update after parent node changed.
830243830Sdim  void reset(unsigned Level) {
831212795Sdim    path[Level] = Entry(subtree(Level - 1), offset(Level));
832212795Sdim  }
833249423Sdim
834212795Sdim  /// push - Add entry to path.
835212795Sdim  /// @param Node Node to add, should be subtree(path.size()-1).
836212795Sdim  /// @param Offset Offset into Node.
837212795Sdim  void push(NodeRef Node, unsigned Offset) {
838212795Sdim    path.push_back(Entry(Node, Offset));
839212795Sdim  }
840212795Sdim
841212795Sdim  /// pop - Remove the last path entry.
842212795Sdim  void pop() {
843212795Sdim    path.pop_back();
844243830Sdim  }
845212795Sdim
846212795Sdim  /// setSize - Set the size of a node both in the path and in the tree.
847212795Sdim  /// @param Level 0..height. Note that setting the root size won't change
848212795Sdim  ///              map->rootSize.
849212795Sdim  /// @param Size New node size.
850243830Sdim  void setSize(unsigned Level, unsigned Size) {
851212795Sdim    path[Level].size = Size;
852212795Sdim    if (Level)
853212795Sdim      subtree(Level - 1).setSize(Size);
854212795Sdim  }
855249423Sdim
856249423Sdim  /// setRoot - Clear the path and set a new root node.
857249423Sdim  /// @param Node New root node.
858249423Sdim  /// @param Size New root size.
859249423Sdim  /// @param Offset Offset into root node.
860249423Sdim  void setRoot(void *Node, unsigned Size, unsigned Offset) {
861249423Sdim    path.clear();
862249423Sdim    path.push_back(Entry(Node, Size, Offset));
863243830Sdim  }
864249423Sdim
865249423Sdim  /// replaceRoot - Replace the current root node with two new entries after the
866249423Sdim  /// tree height has increased.
867212795Sdim  /// @param Root The new root node.
868249423Sdim  /// @param Size Number of entries in the new root.
869212795Sdim  /// @param Offsets Offsets into the root and first branch nodes.
870212795Sdim  void replaceRoot(void *Root, unsigned Size, IdxPair Offsets);
871249423Sdim
872249423Sdim  /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
873212795Sdim  /// @param Level Get the sibling to node(Level).
874212795Sdim  /// @return Left sibling, or NodeRef().
875212795Sdim  NodeRef getLeftSibling(unsigned Level) const;
876212795Sdim
877212795Sdim  /// moveLeft - Move path to the left sibling at Level. Leave nodes below Level
878224145Sdim  /// unaltered.
879212795Sdim  /// @param Level Move node(Level).
880243830Sdim  void moveLeft(unsigned Level);
881212795Sdim
882212795Sdim  /// fillLeft - Grow path to Height by taking leftmost branches.
883212795Sdim  /// @param Height The target height.
884212795Sdim  void fillLeft(unsigned Height) {
885218893Sdim    while (height() < Height)
886218893Sdim      push(subtree(height()), 0);
887218893Sdim  }
888218893Sdim
889218893Sdim  /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
890218893Sdim  /// @param Level Get the sibling to node(Level).
891218893Sdim  /// @return Left sibling, or NodeRef().
892218893Sdim  NodeRef getRightSibling(unsigned Level) const;
893218893Sdim
894218893Sdim  /// moveRight - Move path to the left sibling at Level. Leave nodes below
895218893Sdim  /// Level unaltered.
896234353Sdim  /// @param Level Move node(Level).
897218893Sdim  void moveRight(unsigned Level);
898218893Sdim
899234353Sdim  /// atBegin - Return true if path is at begin().
900218893Sdim  bool atBegin() const {
901218893Sdim    for (unsigned i = 0, e = path.size(); i != e; ++i)
902218893Sdim      if (path[i].offset != 0)
903218893Sdim        return false;
904218893Sdim    return true;
905218893Sdim  }
906218893Sdim
907218893Sdim  /// atLastEntry - Return true if the path is at the last entry of the node at
908218893Sdim  /// Level.
909218893Sdim  /// @param Level Node to examine.
910218893Sdim  bool atLastEntry(unsigned Level) const {
911218893Sdim    return path[Level].offset == path[Level].size - 1;
912218893Sdim  }
913218893Sdim
914218893Sdim  /// legalizeForInsert - Prepare the path for an insertion at Level. When the
915218893Sdim  /// path is at end(), node(Level) may not be a legal node. legalizeForInsert
916218893Sdim  /// ensures that node(Level) is real by moving back to the last node at Level,
917218893Sdim  /// and setting offset(Level) to size(Level) if required.
918243830Sdim  /// @param Level The level where an insertion is about to take place.
919212795Sdim  void legalizeForInsert(unsigned Level) {
920243830Sdim    if (valid())
921212795Sdim      return;
922226633Sdim    moveLeft(Level);
923212795Sdim    ++path[Level].offset;
924243830Sdim  }
925212795Sdim};
926212795Sdim
927234353Sdim} // end namespace IntervalMapImpl
928226633Sdim
929249423Sdim//===----------------------------------------------------------------------===//
930226633Sdim//---                          IntervalMap                                ----//
931212795Sdim//===----------------------------------------------------------------------===//
932212795Sdim
933249423Sdimtemplate <typename KeyT, typename ValT,
934249423Sdim          unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize,
935212795Sdim          typename Traits = IntervalMapInfo<KeyT>>
936243830Sdimclass IntervalMap {
937212795Sdim  using Sizer = IntervalMapImpl::NodeSizer<KeyT, ValT>;
938249423Sdim  using Leaf = IntervalMapImpl::LeafNode<KeyT, ValT, Sizer::LeafSize, Traits>;
939212795Sdim  using Branch =
940249423Sdim      IntervalMapImpl::BranchNode<KeyT, ValT, Sizer::BranchSize, Traits>;
941249423Sdim  using RootLeaf = IntervalMapImpl::LeafNode<KeyT, ValT, N, Traits>;
942212795Sdim  using IdxPair = IntervalMapImpl::IdxPair;
943212795Sdim
944243830Sdim  // The RootLeaf capacity is given as a template parameter. We must compute the
945212795Sdim  // corresponding RootBranch capacity.
946212795Sdim  enum {
947234353Sdim    DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) /
948234353Sdim      (sizeof(KeyT) + sizeof(IntervalMapImpl::NodeRef)),
949243830Sdim    RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1
950243830Sdim  };
951249423Sdim
952249423Sdim  using RootBranch =
953234353Sdim      IntervalMapImpl::BranchNode<KeyT, ValT, RootBranchCap, Traits>;
954249423Sdim
955249423Sdim  // When branched, we store a global start key as well as the branch node.
956249423Sdim  struct RootBranchData {
957249423Sdim    KeyT start;
958243830Sdim    RootBranch node;
959212795Sdim  };
960226633Sdim
961226633Sdimpublic:
962226633Sdim  using Allocator = typename Sizer::Allocator;
963226633Sdim  using KeyType = KeyT;
964226633Sdim  using ValueType = ValT;
965239462Sdim  using KeyTraits = Traits;
966239462Sdim
967239462Sdimprivate:
968226633Sdim  // The root data is either a RootLeaf or a RootBranchData instance.
969226633Sdim  union {
970226633Sdim    RootLeaf leaf;
971243830Sdim    RootBranchData branchData;
972212795Sdim  };
973226633Sdim
974234353Sdim  // Tree height.
975243830Sdim  // 0: Leaves in root.
976243830Sdim  // 1: Root points to leaf.
977234353Sdim  // 2: root->branch->leaf ...
978234353Sdim  unsigned height = 0;
979234353Sdim
980234353Sdim  // Number of entries in the root node.
981234353Sdim  unsigned rootSize = 0;
982218893Sdim
983234353Sdim  // Allocator used for creating external nodes.
984239462Sdim  Allocator *allocator = nullptr;
985239462Sdim
986234353Sdim  const RootLeaf &rootLeaf() const {
987234353Sdim    assert(!branched() && "Cannot acces leaf data in branched root");
988234353Sdim    return leaf;
989234353Sdim  }
990249423Sdim  RootLeaf &rootLeaf() {
991234353Sdim    assert(!branched() && "Cannot acces leaf data in branched root");
992234353Sdim    return leaf;
993234353Sdim  }
994243830Sdim
995234353Sdim  const RootBranchData &rootBranchData() const {
996234353Sdim    assert(branched() && "Cannot access branch data in non-branched root");
997234353Sdim    return branchData;
998249423Sdim  }
999234353Sdim  RootBranchData &rootBranchData() {
1000234353Sdim    assert(branched() && "Cannot access branch data in non-branched root");
1001234353Sdim    return branchData;
1002212795Sdim  }
1003212795Sdim
1004212795Sdim  const RootBranch &rootBranch() const { return rootBranchData().node; }
1005212795Sdim  RootBranch &rootBranch()             { return rootBranchData().node; }
1006249423Sdim  KeyT rootBranchStart() const { return rootBranchData().start; }
1007212795Sdim  KeyT &rootBranchStart()      { return rootBranchData().start; }
1008243830Sdim
1009243830Sdim  template <typename NodeT> NodeT *newNode() {
1010243830Sdim    return new (allocator->template Allocate<NodeT>()) NodeT();
1011249423Sdim  }
1012249423Sdim
1013249423Sdim  template <typename NodeT> void deleteNode(NodeT *P) {
1014212795Sdim    P->~NodeT();
1015212795Sdim    allocator->Deallocate(P);
1016212795Sdim  }
1017249423Sdim
1018212795Sdim  IdxPair branchRoot(unsigned Position);
1019212795Sdim  IdxPair splitRoot(unsigned Position);
1020212795Sdim
1021243830Sdim  void switchRootToBranch() {
1022212795Sdim    rootLeaf().~RootLeaf();
1023212795Sdim    height = 1;
1024212795Sdim    new (&rootBranchData()) RootBranchData();
1025249423Sdim  }
1026243830Sdim
1027243830Sdim  void switchRootToLeaf() {
1028212795Sdim    rootBranchData().~RootBranchData();
1029212795Sdim    height = 0;
1030212795Sdim    new(&rootLeaf()) RootLeaf();
1031224145Sdim  }
1032218893Sdim
1033226633Sdim  bool branched() const { return height > 0; }
1034218893Sdim
1035218893Sdim  ValT treeSafeLookup(KeyT x, ValT NotFound) const;
1036212795Sdim  void visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef,
1037212795Sdim                  unsigned Level));
1038226633Sdim  void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level);
1039212795Sdim
1040212795Sdimpublic:
1041212795Sdim  explicit IntervalMap(Allocator &a) : allocator(&a) {
1042212795Sdim    new (&rootLeaf()) RootLeaf();
1043243830Sdim  }
1044212795Sdim
1045212795Sdim  ///@{
1046249423Sdim  /// NOTE: The moved-from or copied-from object's allocator needs to have a
1047249423Sdim  /// lifetime equal to or exceeding the moved-to or copied-to object to avoid
1048249423Sdim  /// undefined behaviour.
1049249423Sdim  IntervalMap(IntervalMap const &RHS) : IntervalMap(*RHS.allocator) {
1050249423Sdim    // Future-proofing assertion: this function assumes the IntervalMap
1051249423Sdim    // constructor doesn't add any nodes.
1052249423Sdim    assert(empty() && "Expected emptry tree");
1053249423Sdim    *this = RHS;
1054249423Sdim  }
1055249423Sdim  IntervalMap &operator=(IntervalMap const &RHS) {
1056249423Sdim    clear();
1057249423Sdim    allocator = RHS.allocator;
1058249423Sdim    for (auto It = RHS.begin(), End = RHS.end(); It != End; ++It)
1059249423Sdim      insert(It.start(), It.stop(), It.value());
1060249423Sdim    return *this;
1061249423Sdim  }
1062249423Sdim
1063249423Sdim  IntervalMap(IntervalMap &&RHS) : IntervalMap(*RHS.allocator) {
1064249423Sdim    // Future-proofing assertion: this function assumes the IntervalMap
1065226633Sdim    // constructor doesn't add any nodes.
1066234353Sdim    assert(empty() && "Expected emptry tree");
1067226633Sdim    *this = std::move(RHS);
1068226633Sdim  }
1069226633Sdim  IntervalMap &operator=(IntervalMap &&RHS) {
1070226633Sdim    // Calling clear deallocates memory and switches to rootLeaf.
1071226633Sdim    clear();
1072226633Sdim    // Destroy the new rootLeaf.
1073226633Sdim    rootLeaf().~RootLeaf();
1074226633Sdim
1075226633Sdim    height = RHS.height;
1076226633Sdim    rootSize = RHS.rootSize;
1077226633Sdim    allocator = RHS.allocator;
1078226633Sdim
1079226633Sdim    // rootLeaf and rootBranch are both uninitialized. Move RHS data into
1080226633Sdim    // appropriate field.
1081226633Sdim    if (RHS.branched()) {
1082226633Sdim      rootBranch() = std::move(RHS.rootBranch());
1083226633Sdim      // Prevent RHS deallocating memory LHS now owns by replacing RHS
1084212795Sdim      // rootBranch with a new rootLeaf.
1085212795Sdim      RHS.rootBranch().~RootBranch();
1086212795Sdim      RHS.height = 0;
1087249423Sdim      new (&RHS.rootLeaf()) RootLeaf();
1088212795Sdim    } else {
1089212795Sdim      rootLeaf() = std::move(RHS.rootLeaf());
1090212795Sdim    }
1091212795Sdim    return *this;
1092212795Sdim  }
1093212795Sdim  ///@}
1094218893Sdim
1095212795Sdim  ~IntervalMap() {
1096212795Sdim    clear();
1097212795Sdim    rootLeaf().~RootLeaf();
1098218893Sdim  }
1099218893Sdim
1100212795Sdim  /// empty -  Return true when no intervals are mapped.
1101218893Sdim  bool empty() const {
1102212795Sdim    return rootSize == 0;
1103212795Sdim  }
1104212795Sdim
1105212795Sdim  /// start - Return the smallest mapped key in a non-empty map.
1106263508Sdim  KeyT start() const {
1107251662Sdim    assert(!empty() && "Empty IntervalMap has no start");
1108251662Sdim    return !branched() ? rootLeaf().start(0) : rootBranchStart();
1109251662Sdim  }
1110251662Sdim
1111251662Sdim  /// stop - Return the largest mapped key in a non-empty map.
1112251662Sdim  KeyT stop() const {
1113251662Sdim    assert(!empty() && "Empty IntervalMap has no stop");
1114251662Sdim    return !branched() ? rootLeaf().stop(rootSize - 1) :
1115251662Sdim                         rootBranch().stop(rootSize - 1);
1116251662Sdim  }
1117251662Sdim
1118251662Sdim  /// lookup - Return the mapped value at x or NotFound.
1119249423Sdim  ValT lookup(KeyT x, ValT NotFound = ValT()) const {
1120249423Sdim    if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x))
1121212795Sdim      return NotFound;
1122212795Sdim    return branched() ? treeSafeLookup(x, NotFound) :
1123212795Sdim                        rootLeaf().safeLookup(x, NotFound);
1124212795Sdim  }
1125212795Sdim
1126212795Sdim  /// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
1127212795Sdim  /// It is assumed that no key in the interval is mapped to another value, but
1128226633Sdim  /// overlapping intervals already mapped to y will be coalesced.
1129212795Sdim  void insert(KeyT a, KeyT b, ValT y) {
1130212795Sdim    if (branched() || rootSize == RootLeaf::Capacity)
1131212795Sdim      return find(a).insert(a, b, y);
1132249423Sdim
1133249423Sdim    // Easy insert into root leaf.
1134249423Sdim    unsigned p = rootLeaf().findFrom(0, rootSize, a);
1135249423Sdim    rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y);
1136249423Sdim  }
1137249423Sdim
1138249423Sdim  /// clear - Remove all entries.
1139249423Sdim  void clear();
1140249423Sdim
1141249423Sdim  class const_iterator;
1142249423Sdim  class iterator;
1143249423Sdim  friend class const_iterator;
1144249423Sdim  friend class iterator;
1145249423Sdim
1146249423Sdim  const_iterator begin() const {
1147249423Sdim    const_iterator I(*this);
1148212795Sdim    I.goToBegin();
1149212795Sdim    return I;
1150212795Sdim  }
1151212795Sdim
1152212795Sdim  iterator begin() {
1153249423Sdim    iterator I(*this);
1154212795Sdim    I.goToBegin();
1155249423Sdim    return I;
1156249423Sdim  }
1157249423Sdim
1158212795Sdim  const_iterator end() const {
1159212795Sdim    const_iterator I(*this);
1160212795Sdim    I.goToEnd();
1161212795Sdim    return I;
1162212795Sdim  }
1163212795Sdim
1164249423Sdim  iterator end() {
1165212795Sdim    iterator I(*this);
1166249423Sdim    I.goToEnd();
1167249423Sdim    return I;
1168243830Sdim  }
1169249423Sdim
1170249423Sdim  /// find - Return an iterator pointing to the first interval ending at or
1171243830Sdim  /// after x, or end().
1172212795Sdim  const_iterator find(KeyT x) const {
1173212795Sdim    const_iterator I(*this);
1174212795Sdim    I.find(x);
1175226633Sdim    return I;
1176226633Sdim  }
1177249423Sdim
1178212795Sdim  iterator find(KeyT x) {
1179226633Sdim    iterator I(*this);
1180212795Sdim    I.find(x);
1181226633Sdim    return I;
1182212795Sdim  }
1183212795Sdim
1184212795Sdim  /// overlaps(a, b) - Return true if the intervals in this map overlap with the
1185212795Sdim  /// interval [a;b].
1186212795Sdim  bool overlaps(KeyT a, KeyT b) const {
1187249423Sdim    assert(Traits::nonEmpty(a, b));
1188212795Sdim    const_iterator I = find(a);
1189226633Sdim    if (!I.valid())
1190212795Sdim      return false;
1191212795Sdim    // [a;b] and [x;y] overlap iff x<=b and a<=y. The find() call guarantees the
1192212795Sdim    // second part (y = find(a).stop()), so it is sufficient to check the first
1193212795Sdim    // one.
1194212795Sdim    return !Traits::stopLess(b, I.start());
1195218893Sdim  }
1196226633Sdim};
1197226633Sdim
1198226633Sdim/// treeSafeLookup - Return the mapped value at x or NotFound, assuming a
1199226633Sdim/// branched root.
1200226633Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1201226633SdimValT IntervalMap<KeyT, ValT, N, Traits>::
1202249423SdimtreeSafeLookup(KeyT x, ValT NotFound) const {
1203249423Sdim  assert(branched() && "treeLookup assumes a branched root");
1204249423Sdim
1205249423Sdim  IntervalMapImpl::NodeRef NR = rootBranch().safeLookup(x);
1206249423Sdim  for (unsigned h = height-1; h; --h)
1207249423Sdim    NR = NR.get<Branch>().safeLookup(x);
1208212795Sdim  return NR.get<Leaf>().safeLookup(x, NotFound);
1209218893Sdim}
1210212795Sdim
1211212795Sdim// branchRoot - Switch from a leaf root to a branched root.
1212212795Sdim// Return the new (root offset, node offset) corresponding to Position.
1213212795Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1214212795SdimIntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
1215212795SdimbranchRoot(unsigned Position) {
1216212795Sdim  using namespace IntervalMapImpl;
1217212795Sdim  // How many external leaf nodes to hold RootLeaf+1?
1218212795Sdim  const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1;
1219251662Sdim
1220251662Sdim  // Compute element distribution among new nodes.
1221212795Sdim  unsigned size[Nodes];
1222212795Sdim  IdxPair NewOffset(0, Position);
1223212795Sdim
1224234353Sdim  // Is is very common for the root node to be smaller than external nodes.
1225218893Sdim  if (Nodes == 1)
1226218893Sdim    size[0] = rootSize;
1227212795Sdim  else
1228226633Sdim    NewOffset = distribute(Nodes, rootSize, Leaf::Capacity,  nullptr, size,
1229234353Sdim                           Position, true);
1230226633Sdim
1231226633Sdim  // Allocate new nodes.
1232226633Sdim  unsigned pos = 0;
1233226633Sdim  NodeRef node[Nodes];
1234226633Sdim  for (unsigned n = 0; n != Nodes; ++n) {
1235226633Sdim    Leaf *L = newNode<Leaf>();
1236226633Sdim    L->copy(rootLeaf(), pos, 0, size[n]);
1237212795Sdim    node[n] = NodeRef(L, size[n]);
1238249423Sdim    pos += size[n];
1239249423Sdim  }
1240226633Sdim
1241218893Sdim  // Destroy the old leaf node, construct branch node instead.
1242226633Sdim  switchRootToBranch();
1243249423Sdim  for (unsigned n = 0; n != Nodes; ++n) {
1244249423Sdim    rootBranch().stop(n) = node[n].template get<Leaf>().stop(size[n]-1);
1245249423Sdim    rootBranch().subtree(n) = node[n];
1246249423Sdim  }
1247249423Sdim  rootBranchStart() = node[0].template get<Leaf>().start(0);
1248218893Sdim  rootSize = Nodes;
1249249423Sdim  return NewOffset;
1250249423Sdim}
1251249423Sdim
1252249423Sdim// splitRoot - Split the current BranchRoot into multiple Branch nodes.
1253249423Sdim// Return the new (root offset, node offset) corresponding to Position.
1254226633Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1255226633SdimIntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
1256234353SdimsplitRoot(unsigned Position) {
1257249423Sdim  using namespace IntervalMapImpl;
1258249423Sdim  // How many external leaf nodes to hold RootBranch+1?
1259249423Sdim  const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1;
1260249423Sdim
1261226633Sdim  // Compute element distribution among new nodes.
1262218893Sdim  unsigned Size[Nodes];
1263226633Sdim  IdxPair NewOffset(0, Position);
1264226633Sdim
1265226633Sdim  // Is is very common for the root node to be smaller than external nodes.
1266226633Sdim  if (Nodes == 1)
1267249423Sdim    Size[0] = rootSize;
1268226633Sdim  else
1269249423Sdim    NewOffset = distribute(Nodes, rootSize, Leaf::Capacity,  nullptr, Size,
1270249423Sdim                           Position, true);
1271249423Sdim
1272249423Sdim  // Allocate new nodes.
1273249423Sdim  unsigned Pos = 0;
1274249423Sdim  NodeRef Node[Nodes];
1275249423Sdim  for (unsigned n = 0; n != Nodes; ++n) {
1276249423Sdim    Branch *B = newNode<Branch>();
1277249423Sdim    B->copy(rootBranch(), Pos, 0, Size[n]);
1278249423Sdim    Node[n] = NodeRef(B, Size[n]);
1279226633Sdim    Pos += Size[n];
1280249423Sdim  }
1281226633Sdim
1282226633Sdim  for (unsigned n = 0; n != Nodes; ++n) {
1283226633Sdim    rootBranch().stop(n) = Node[n].template get<Branch>().stop(Size[n]-1);
1284226633Sdim    rootBranch().subtree(n) = Node[n];
1285226633Sdim  }
1286263508Sdim  rootSize = Nodes;
1287263508Sdim  ++height;
1288226633Sdim  return NewOffset;
1289226633Sdim}
1290226633Sdim
1291226633Sdim/// visitNodes - Visit each external node.
1292226633Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1293226633Sdimvoid IntervalMap<KeyT, ValT, N, Traits>::
1294234353SdimvisitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, unsigned Height)) {
1295234353Sdim  if (!branched())
1296226633Sdim    return;
1297226633Sdim  SmallVector<IntervalMapImpl::NodeRef, 4> Refs, NextRefs;
1298226633Sdim
1299226633Sdim  // Collect level 0 nodes from the root.
1300226633Sdim  for (unsigned i = 0; i != rootSize; ++i)
1301212795Sdim    Refs.push_back(rootBranch().subtree(i));
1302218893Sdim
1303249423Sdim  // Visit all branch nodes.
1304249423Sdim  for (unsigned h = height - 1; h; --h) {
1305249423Sdim    for (unsigned i = 0, e = Refs.size(); i != e; ++i) {
1306249423Sdim      for (unsigned j = 0, s = Refs[i].size(); j != s; ++j)
1307249423Sdim        NextRefs.push_back(Refs[i].subtree(j));
1308249423Sdim      (this->*f)(Refs[i], h);
1309249423Sdim    }
1310249423Sdim    Refs.clear();
1311249423Sdim    Refs.swap(NextRefs);
1312249423Sdim  }
1313249423Sdim
1314263508Sdim  // Visit all leaf nodes.
1315249423Sdim  for (unsigned i = 0, e = Refs.size(); i != e; ++i)
1316249423Sdim    (this->*f)(Refs[i], 0);
1317249423Sdim}
1318226633Sdim
1319226633Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1320218893Sdimvoid IntervalMap<KeyT, ValT, N, Traits>::
1321226633SdimdeleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) {
1322226633Sdim  if (Level)
1323226633Sdim    deleteNode(&Node.get<Branch>());
1324218893Sdim  else
1325218893Sdim    deleteNode(&Node.get<Leaf>());
1326249423Sdim}
1327249423Sdim
1328249423Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1329249423Sdimvoid IntervalMap<KeyT, ValT, N, Traits>::
1330243830Sdimclear() {
1331249423Sdim  if (branched()) {
1332218893Sdim    visitNodes(&IntervalMap::deleteNode);
1333218893Sdim    switchRootToLeaf();
1334249423Sdim  }
1335249423Sdim  rootSize = 0;
1336249423Sdim}
1337249423Sdim
1338249423Sdim//===----------------------------------------------------------------------===//
1339249423Sdim//---                   IntervalMap::const_iterator                       ----//
1340249423Sdim//===----------------------------------------------------------------------===//
1341212795Sdim
1342243830Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1343243830Sdimclass IntervalMap<KeyT, ValT, N, Traits>::const_iterator {
1344243830Sdim  friend class IntervalMap;
1345226633Sdim
1346226633Sdimpublic:
1347249423Sdim  using iterator_category = std::bidirectional_iterator_tag;
1348212795Sdim  using value_type = ValT;
1349212795Sdim  using difference_type = std::ptrdiff_t;
1350212795Sdim  using pointer = value_type *;
1351212795Sdim  using reference = value_type &;
1352212795Sdim
1353249423Sdimprotected:
1354226633Sdim  // The map referred to.
1355212795Sdim  IntervalMap *map = nullptr;
1356212795Sdim
1357212795Sdim  // We store a full path from the root to the current position.
1358249423Sdim  // The path may be partially filled, but never between iterator calls.
1359249423Sdim  IntervalMapImpl::Path path;
1360249423Sdim
1361249423Sdim  explicit const_iterator(const IntervalMap &map) :
1362249423Sdim    map(const_cast<IntervalMap*>(&map)) {}
1363249423Sdim
1364249423Sdim  bool branched() const {
1365249423Sdim    assert(map && "Invalid iterator");
1366249423Sdim    return map->branched();
1367249423Sdim  }
1368249423Sdim
1369249423Sdim  void setRoot(unsigned Offset) {
1370249423Sdim    if (branched())
1371249423Sdim      path.setRoot(&map->rootBranch(), map->rootSize, Offset);
1372249423Sdim    else
1373249423Sdim      path.setRoot(&map->rootLeaf(), map->rootSize, Offset);
1374249423Sdim  }
1375249423Sdim
1376249423Sdim  void pathFillFind(KeyT x);
1377249423Sdim  void treeFind(KeyT x);
1378249423Sdim  void treeAdvanceTo(KeyT x);
1379249423Sdim
1380249423Sdim  /// unsafeStart - Writable access to start() for iterator.
1381249423Sdim  KeyT &unsafeStart() const {
1382212795Sdim    assert(valid() && "Cannot access invalid iterator");
1383212795Sdim    return branched() ? path.leaf<Leaf>().start(path.leafOffset()) :
1384212795Sdim                        path.leaf<RootLeaf>().start(path.leafOffset());
1385212795Sdim  }
1386249423Sdim
1387212795Sdim  /// unsafeStop - Writable access to stop() for iterator.
1388212795Sdim  KeyT &unsafeStop() const {
1389212795Sdim    assert(valid() && "Cannot access invalid iterator");
1390234353Sdim    return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) :
1391234353Sdim                        path.leaf<RootLeaf>().stop(path.leafOffset());
1392234353Sdim  }
1393234353Sdim
1394234353Sdim  /// unsafeValue - Writable access to value() for iterator.
1395249423Sdim  ValT &unsafeValue() const {
1396249423Sdim    assert(valid() && "Cannot access invalid iterator");
1397234353Sdim    return branched() ? path.leaf<Leaf>().value(path.leafOffset()) :
1398249423Sdim                        path.leaf<RootLeaf>().value(path.leafOffset());
1399234353Sdim  }
1400249423Sdim
1401249423Sdimpublic:
1402249423Sdim  /// const_iterator - Create an iterator that isn't pointing anywhere.
1403249423Sdim  const_iterator() = default;
1404249423Sdim
1405249423Sdim  /// setMap - Change the map iterated over. This call must be followed by a
1406249423Sdim  /// call to goToBegin(), goToEnd(), or find()
1407249423Sdim  void setMap(const IntervalMap &m) { map = const_cast<IntervalMap*>(&m); }
1408249423Sdim
1409234353Sdim  /// valid - Return true if the current position is valid, false for end().
1410234353Sdim  bool valid() const { return path.valid(); }
1411234353Sdim
1412234353Sdim  /// atBegin - Return true if the current position is the first map entry.
1413234353Sdim  bool atBegin() const { return path.atBegin(); }
1414234353Sdim
1415234353Sdim  /// start - Return the beginning of the current interval.
1416234353Sdim  const KeyT &start() const { return unsafeStart(); }
1417249423Sdim
1418234353Sdim  /// stop - Return the end of the current interval.
1419234353Sdim  const KeyT &stop() const { return unsafeStop(); }
1420234353Sdim
1421234353Sdim  /// value - Return the mapped value at the current interval.
1422234353Sdim  const ValT &value() const { return unsafeValue(); }
1423234353Sdim
1424234353Sdim  const ValT &operator*() const { return value(); }
1425249423Sdim
1426249423Sdim  bool operator==(const const_iterator &RHS) const {
1427234353Sdim    assert(map == RHS.map && "Cannot compare iterators from different maps");
1428234353Sdim    if (!valid())
1429234353Sdim      return !RHS.valid();
1430234353Sdim    if (path.leafOffset() != RHS.path.leafOffset())
1431234353Sdim      return false;
1432234353Sdim    return &path.template leaf<Leaf>() == &RHS.path.template leaf<Leaf>();
1433249423Sdim  }
1434234353Sdim
1435234353Sdim  bool operator!=(const const_iterator &RHS) const {
1436234353Sdim    return !operator==(RHS);
1437234353Sdim  }
1438234353Sdim
1439234353Sdim  /// goToBegin - Move to the first interval in map.
1440234353Sdim  void goToBegin() {
1441234353Sdim    setRoot(0);
1442234353Sdim    if (branched())
1443234353Sdim      path.fillLeft(map->height);
1444234353Sdim  }
1445243830Sdim
1446243830Sdim  /// goToEnd - Move beyond the last interval in map.
1447243830Sdim  void goToEnd() {
1448234353Sdim    setRoot(map->rootSize);
1449234353Sdim  }
1450234353Sdim
1451249423Sdim  /// preincrement - Move to the next interval.
1452249423Sdim  const_iterator &operator++() {
1453249423Sdim    assert(valid() && "Cannot increment end()");
1454249423Sdim    if (++path.leafOffset() == path.leafSize() && branched())
1455249423Sdim      path.moveRight(map->height);
1456249423Sdim    return *this;
1457249423Sdim  }
1458249423Sdim
1459249423Sdim  /// postincrement - Don't do that!
1460249423Sdim  const_iterator operator++(int) {
1461249423Sdim    const_iterator tmp = *this;
1462249423Sdim    operator++();
1463249423Sdim    return tmp;
1464249423Sdim  }
1465249423Sdim
1466234353Sdim  /// predecrement - Move to the previous interval.
1467234353Sdim  const_iterator &operator--() {
1468234353Sdim    if (path.leafOffset() && (valid() || !branched()))
1469234353Sdim      --path.leafOffset();
1470234353Sdim    else
1471234353Sdim      path.moveLeft(map->height);
1472234353Sdim    return *this;
1473234353Sdim  }
1474234353Sdim
1475234353Sdim  /// postdecrement - Don't do that!
1476234353Sdim  const_iterator operator--(int) {
1477234353Sdim    const_iterator tmp = *this;
1478234353Sdim    operator--();
1479234353Sdim    return tmp;
1480249423Sdim  }
1481249423Sdim
1482249423Sdim  /// find - Move to the first interval with stop >= x, or end().
1483249423Sdim  /// This is a full search from the root, the current position is ignored.
1484249423Sdim  void find(KeyT x) {
1485249423Sdim    if (branched())
1486249423Sdim      treeFind(x);
1487249423Sdim    else
1488249423Sdim      setRoot(map->rootLeaf().findFrom(0, map->rootSize, x));
1489249423Sdim  }
1490249423Sdim
1491249423Sdim  /// advanceTo - Move to the first interval with stop >= x, or end().
1492249423Sdim  /// The search is started from the current position, and no earlier positions
1493249423Sdim  /// can be found. This is much faster than find() for small moves.
1494249423Sdim  void advanceTo(KeyT x) {
1495249423Sdim    if (!valid())
1496249423Sdim      return;
1497249423Sdim    if (branched())
1498249423Sdim      treeAdvanceTo(x);
1499249423Sdim    else
1500249423Sdim      path.leafOffset() =
1501249423Sdim        map->rootLeaf().findFrom(path.leafOffset(), map->rootSize, x);
1502249423Sdim  }
1503249423Sdim};
1504249423Sdim
1505249423Sdim/// pathFillFind - Complete path by searching for x.
1506249423Sdim/// @param x Key to search for.
1507249423Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1508249423Sdimvoid IntervalMap<KeyT, ValT, N, Traits>::
1509249423Sdimconst_iterator::pathFillFind(KeyT x) {
1510249423Sdim  IntervalMapImpl::NodeRef NR = path.subtree(path.height());
1511249423Sdim  for (unsigned i = map->height - path.height() - 1; i; --i) {
1512249423Sdim    unsigned p = NR.get<Branch>().safeFind(0, x);
1513249423Sdim    path.push(NR, p);
1514249423Sdim    NR = NR.subtree(p);
1515249423Sdim  }
1516249423Sdim  path.push(NR, NR.get<Leaf>().safeFind(0, x));
1517249423Sdim}
1518249423Sdim
1519249423Sdim/// treeFind - Find in a branched tree.
1520249423Sdim/// @param x Key to search for.
1521249423Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1522249423Sdimvoid IntervalMap<KeyT, ValT, N, Traits>::
1523249423Sdimconst_iterator::treeFind(KeyT x) {
1524249423Sdim  setRoot(map->rootBranch().findFrom(0, map->rootSize, x));
1525249423Sdim  if (valid())
1526249423Sdim    pathFillFind(x);
1527249423Sdim}
1528249423Sdim
1529249423Sdim/// treeAdvanceTo - Find position after the current one.
1530249423Sdim/// @param x Key to search for.
1531249423Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1532249423Sdimvoid IntervalMap<KeyT, ValT, N, Traits>::
1533249423Sdimconst_iterator::treeAdvanceTo(KeyT x) {
1534249423Sdim  // Can we stay on the same leaf node?
1535249423Sdim  if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) {
1536249423Sdim    path.leafOffset() = path.leaf<Leaf>().safeFind(path.leafOffset(), x);
1537249423Sdim    return;
1538249423Sdim  }
1539249423Sdim
1540249423Sdim  // Drop the current leaf.
1541249423Sdim  path.pop();
1542249423Sdim
1543249423Sdim  // Search towards the root for a usable subtree.
1544249423Sdim  if (path.height()) {
1545249423Sdim    for (unsigned l = path.height() - 1; l; --l) {
1546249423Sdim      if (!Traits::stopLess(path.node<Branch>(l).stop(path.offset(l)), x)) {
1547249423Sdim        // The branch node at l+1 is usable
1548249423Sdim        path.offset(l + 1) =
1549249423Sdim          path.node<Branch>(l + 1).safeFind(path.offset(l + 1), x);
1550249423Sdim        return pathFillFind(x);
1551249423Sdim      }
1552249423Sdim      path.pop();
1553249423Sdim    }
1554249423Sdim    // Is the level-1 Branch usable?
1555249423Sdim    if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) {
1556249423Sdim      path.offset(1) = path.node<Branch>(1).safeFind(path.offset(1), x);
1557249423Sdim      return pathFillFind(x);
1558249423Sdim    }
1559249423Sdim  }
1560249423Sdim
1561249423Sdim  // We reached the root.
1562249423Sdim  setRoot(map->rootBranch().findFrom(path.offset(0), map->rootSize, x));
1563249423Sdim  if (valid())
1564249423Sdim    pathFillFind(x);
1565249423Sdim}
1566249423Sdim
1567249423Sdim//===----------------------------------------------------------------------===//
1568249423Sdim//---                       IntervalMap::iterator                         ----//
1569249423Sdim//===----------------------------------------------------------------------===//
1570249423Sdim
1571249423Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1572249423Sdimclass IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator {
1573249423Sdim  friend class IntervalMap;
1574249423Sdim
1575249423Sdim  using IdxPair = IntervalMapImpl::IdxPair;
1576249423Sdim
1577249423Sdim  explicit iterator(IntervalMap &map) : const_iterator(map) {}
1578249423Sdim
1579249423Sdim  void setNodeStop(unsigned Level, KeyT Stop);
1580249423Sdim  bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop);
1581249423Sdim  template <typename NodeT> bool overflow(unsigned Level);
1582249423Sdim  void treeInsert(KeyT a, KeyT b, ValT y);
1583249423Sdim  void eraseNode(unsigned Level);
1584249423Sdim  void treeErase(bool UpdateRoot = true);
1585249423Sdim  bool canCoalesceLeft(KeyT Start, ValT x);
1586249423Sdim  bool canCoalesceRight(KeyT Stop, ValT x);
1587249423Sdim
1588249423Sdimpublic:
1589249423Sdim  /// iterator - Create null iterator.
1590251662Sdim  iterator() = default;
1591251662Sdim
1592263508Sdim  /// setStart - Move the start of the current interval.
1593249423Sdim  /// This may cause coalescing with the previous interval.
1594249423Sdim  /// @param a New start key, must not overlap the previous interval.
1595249423Sdim  void setStart(KeyT a);
1596249423Sdim
1597263508Sdim  /// setStop - Move the end of the current interval.
1598263508Sdim  /// This may cause coalescing with the following interval.
1599263508Sdim  /// @param b New stop key, must not overlap the following interval.
1600263508Sdim  void setStop(KeyT b);
1601263508Sdim
1602263508Sdim  /// setValue - Change the mapped value of the current interval.
1603263508Sdim  /// This may cause coalescing with the previous and following intervals.
1604263508Sdim  /// @param x New value.
1605249423Sdim  void setValue(ValT x);
1606263508Sdim
1607249423Sdim  /// setStartUnchecked - Move the start of the current interval without
1608249423Sdim  /// checking for coalescing or overlaps.
1609249423Sdim  /// This should only be used when it is known that coalescing is not required.
1610249423Sdim  /// @param a New start key.
1611249423Sdim  void setStartUnchecked(KeyT a) { this->unsafeStart() = a; }
1612249423Sdim
1613249423Sdim  /// setStopUnchecked - Move the end of the current interval without checking
1614249423Sdim  /// for coalescing or overlaps.
1615249423Sdim  /// This should only be used when it is known that coalescing is not required.
1616249423Sdim  /// @param b New stop key.
1617249423Sdim  void setStopUnchecked(KeyT b) {
1618249423Sdim    this->unsafeStop() = b;
1619249423Sdim    // Update keys in branch nodes as well.
1620249423Sdim    if (this->path.atLastEntry(this->path.height()))
1621249423Sdim      setNodeStop(this->path.height(), b);
1622251662Sdim  }
1623251662Sdim
1624251662Sdim  /// setValueUnchecked - Change the mapped value of the current interval
1625249423Sdim  /// without checking for coalescing.
1626249423Sdim  /// @param x New value.
1627251662Sdim  void setValueUnchecked(ValT x) { this->unsafeValue() = x; }
1628249423Sdim
1629249423Sdim  /// insert - Insert mapping [a;b] -> y before the current position.
1630249423Sdim  void insert(KeyT a, KeyT b, ValT y);
1631249423Sdim
1632249423Sdim  /// erase - Erase the current interval.
1633249423Sdim  void erase();
1634249423Sdim
1635249423Sdim  iterator &operator++() {
1636249423Sdim    const_iterator::operator++();
1637249423Sdim    return *this;
1638243830Sdim  }
1639243830Sdim
1640243830Sdim  iterator operator++(int) {
1641243830Sdim    iterator tmp = *this;
1642243830Sdim    operator++();
1643249423Sdim    return tmp;
1644243830Sdim  }
1645243830Sdim
1646243830Sdim  iterator &operator--() {
1647249423Sdim    const_iterator::operator--();
1648243830Sdim    return *this;
1649243830Sdim  }
1650243830Sdim
1651243830Sdim  iterator operator--(int) {
1652243830Sdim    iterator tmp = *this;
1653249423Sdim    operator--();
1654249423Sdim    return tmp;
1655243830Sdim  }
1656243830Sdim};
1657243830Sdim
1658243830Sdim/// canCoalesceLeft - Can the current interval coalesce to the left after
1659243830Sdim/// changing start or value?
1660243830Sdim/// @param Start New start of current interval.
1661243830Sdim/// @param Value New value for current interval.
1662243830Sdim/// @return True when updating the current interval would enable coalescing.
1663243830Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1664249423Sdimbool IntervalMap<KeyT, ValT, N, Traits>::
1665243830Sdimiterator::canCoalesceLeft(KeyT Start, ValT Value) {
1666243830Sdim  using namespace IntervalMapImpl;
1667243830Sdim  Path &P = this->path;
1668243830Sdim  if (!this->branched()) {
1669243830Sdim    unsigned i = P.leafOffset();
1670243830Sdim    RootLeaf &Node = P.leaf<RootLeaf>();
1671243830Sdim    return i && Node.value(i-1) == Value &&
1672243830Sdim                Traits::adjacent(Node.stop(i-1), Start);
1673243830Sdim  }
1674243830Sdim  // Branched.
1675243830Sdim  if (unsigned i = P.leafOffset()) {
1676243830Sdim    Leaf &Node = P.leaf<Leaf>();
1677243830Sdim    return Node.value(i-1) == Value && Traits::adjacent(Node.stop(i-1), Start);
1678243830Sdim  } else if (NodeRef NR = P.getLeftSibling(P.height())) {
1679243830Sdim    unsigned i = NR.size() - 1;
1680243830Sdim    Leaf &Node = NR.get<Leaf>();
1681243830Sdim    return Node.value(i) == Value && Traits::adjacent(Node.stop(i), Start);
1682243830Sdim  }
1683243830Sdim  return false;
1684243830Sdim}
1685243830Sdim
1686243830Sdim/// canCoalesceRight - Can the current interval coalesce to the right after
1687243830Sdim/// changing stop or value?
1688243830Sdim/// @param Stop New stop of current interval.
1689243830Sdim/// @param Value New value for current interval.
1690243830Sdim/// @return True when updating the current interval would enable coalescing.
1691243830Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1692243830Sdimbool IntervalMap<KeyT, ValT, N, Traits>::
1693243830Sdimiterator::canCoalesceRight(KeyT Stop, ValT Value) {
1694243830Sdim  using namespace IntervalMapImpl;
1695243830Sdim  Path &P = this->path;
1696243830Sdim  unsigned i = P.leafOffset() + 1;
1697249423Sdim  if (!this->branched()) {
1698243830Sdim    if (i >= P.leafSize())
1699243830Sdim      return false;
1700243830Sdim    RootLeaf &Node = P.leaf<RootLeaf>();
1701243830Sdim    return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));
1702243830Sdim  }
1703243830Sdim  // Branched.
1704249423Sdim  if (i < P.leafSize()) {
1705249423Sdim    Leaf &Node = P.leaf<Leaf>();
1706243830Sdim    return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));
1707243830Sdim  } else if (NodeRef NR = P.getRightSibling(P.height())) {
1708243830Sdim    Leaf &Node = NR.get<Leaf>();
1709243830Sdim    return Node.value(0) == Value && Traits::adjacent(Stop, Node.start(0));
1710243830Sdim  }
1711243830Sdim  return false;
1712243830Sdim}
1713243830Sdim
1714243830Sdim/// setNodeStop - Update the stop key of the current node at level and above.
1715243830Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1716249423Sdimvoid IntervalMap<KeyT, ValT, N, Traits>::
1717249423Sdimiterator::setNodeStop(unsigned Level, KeyT Stop) {
1718243830Sdim  // There are no references to the root node, so nothing to update.
1719249423Sdim  if (!Level)
1720243830Sdim    return;
1721243830Sdim  IntervalMapImpl::Path &P = this->path;
1722243830Sdim  // Update nodes pointing to the current node.
1723243830Sdim  while (--Level) {
1724249423Sdim    P.node<Branch>(Level).stop(P.offset(Level)) = Stop;
1725243830Sdim    if (!P.atLastEntry(Level))
1726243830Sdim      return;
1727249423Sdim  }
1728249423Sdim  // Update root separately since it has a different layout.
1729263508Sdim  P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop;
1730263508Sdim}
1731263508Sdim
1732263508Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1733249423Sdimvoid IntervalMap<KeyT, ValT, N, Traits>::
1734249423Sdimiterator::setStart(KeyT a) {
1735249423Sdim  assert(Traits::nonEmpty(a, this->stop()) && "Cannot move start beyond stop");
1736243830Sdim  KeyT &CurStart = this->unsafeStart();
1737243830Sdim  if (!Traits::startLess(a, CurStart) || !canCoalesceLeft(a, this->value())) {
1738249423Sdim    CurStart = a;
1739249423Sdim    return;
1740249423Sdim  }
1741249423Sdim  // Coalesce with the interval to the left.
1742249423Sdim  --*this;
1743243830Sdim  a = this->start();
1744243830Sdim  erase();
1745243830Sdim  setStartUnchecked(a);
1746243830Sdim}
1747243830Sdim
1748243830Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1749226633Sdimvoid IntervalMap<KeyT, ValT, N, Traits>::
1750243830Sdimiterator::setStop(KeyT b) {
1751223017Sdim  assert(Traits::nonEmpty(this->start(), b) && "Cannot move stop beyond start");
1752243830Sdim  if (Traits::startLess(b, this->stop()) ||
1753223017Sdim      !canCoalesceRight(b, this->value())) {
1754243830Sdim    setStopUnchecked(b);
1755243830Sdim    return;
1756223017Sdim  }
1757243830Sdim  // Coalesce with interval to the right.
1758223017Sdim  KeyT a = this->start();
1759223017Sdim  erase();
1760223017Sdim  setStartUnchecked(a);
1761223017Sdim}
1762223017Sdim
1763223017Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1764223017Sdimvoid IntervalMap<KeyT, ValT, N, Traits>::
1765223017Sdimiterator::setValue(ValT x) {
1766212795Sdim  setValueUnchecked(x);
1767212795Sdim  if (canCoalesceRight(this->stop(), x)) {
1768212795Sdim    KeyT a = this->start();
1769243830Sdim    erase();
1770243830Sdim    setStartUnchecked(a);
1771212795Sdim  }
1772243830Sdim  if (canCoalesceLeft(this->start(), x)) {
1773212795Sdim    --*this;
1774212795Sdim    KeyT a = this->start();
1775218893Sdim    erase();
1776212795Sdim    setStartUnchecked(a);
1777212795Sdim  }
1778226633Sdim}
1779212795Sdim
1780212795Sdim/// insertNode - insert a node before the current path at level.
1781212795Sdim/// Leave the current path pointing at the new node.
1782212795Sdim/// @param Level path index of the node to be inserted.
1783212795Sdim/// @param Node The node to be inserted.
1784226633Sdim/// @param Stop The last index in the new node.
1785212795Sdim/// @return True if the tree height was increased.
1786212795Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1787212795Sdimbool IntervalMap<KeyT, ValT, N, Traits>::
1788226633Sdimiterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) {
1789212795Sdim  assert(Level && "Cannot insert next to the root");
1790212795Sdim  bool SplitRoot = false;
1791212795Sdim  IntervalMap &IM = *this->map;
1792243830Sdim  IntervalMapImpl::Path &P = this->path;
1793249423Sdim
1794243830Sdim  if (Level == 1) {
1795249423Sdim    // Insert into the root branch node.
1796212795Sdim    if (IM.rootSize < RootBranch::Capacity) {
1797243830Sdim      IM.rootBranch().insert(P.offset(0), IM.rootSize, Node, Stop);
1798212795Sdim      P.setSize(0, ++IM.rootSize);
1799212795Sdim      P.reset(Level);
1800212795Sdim      return SplitRoot;
1801212795Sdim    }
1802243830Sdim
1803212795Sdim    // We need to split the root while keeping our position.
1804249423Sdim    SplitRoot = true;
1805249423Sdim    IdxPair Offset = IM.splitRoot(P.offset(0));
1806249423Sdim    P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset);
1807249423Sdim
1808249423Sdim    // Fall through to insert at the new higher level.
1809249423Sdim    ++Level;
1810249423Sdim  }
1811249423Sdim
1812249423Sdim  // When inserting before end(), make sure we have a valid path.
1813243830Sdim  P.legalizeForInsert(--Level);
1814243830Sdim
1815249423Sdim  // Insert into the branch node at Level-1.
1816249423Sdim  if (P.size(Level) == Branch::Capacity) {
1817249423Sdim    // Branch node is full, handle handle the overflow.
1818249423Sdim    assert(!SplitRoot && "Cannot overflow after splitting the root");
1819249423Sdim    SplitRoot = overflow<Branch>(Level);
1820243830Sdim    Level += SplitRoot;
1821249423Sdim  }
1822243830Sdim  P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop);
1823212795Sdim  P.setSize(Level, P.size(Level) + 1);
1824249423Sdim  if (P.atLastEntry(Level))
1825249423Sdim    setNodeStop(Level, Stop);
1826249423Sdim  P.reset(Level + 1);
1827243830Sdim  return SplitRoot;
1828243830Sdim}
1829243830Sdim
1830243830Sdim// insert
1831243830Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1832243830Sdimvoid IntervalMap<KeyT, ValT, N, Traits>::
1833243830Sdimiterator::insert(KeyT a, KeyT b, ValT y) {
1834243830Sdim  if (this->branched())
1835243830Sdim    return treeInsert(a, b, y);
1836249423Sdim  IntervalMap &IM = *this->map;
1837243830Sdim  IntervalMapImpl::Path &P = this->path;
1838249423Sdim
1839249423Sdim  // Try simple root leaf insert.
1840249423Sdim  unsigned Size = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y);
1841249423Sdim
1842249423Sdim  // Was the root node insert successful?
1843243830Sdim  if (Size <= RootLeaf::Capacity) {
1844249423Sdim    P.setSize(0, IM.rootSize = Size);
1845249423Sdim    return;
1846249423Sdim  }
1847249423Sdim
1848243830Sdim  // Root leaf node is full, we must branch.
1849243830Sdim  IdxPair Offset = IM.branchRoot(P.leafOffset());
1850243830Sdim  P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset);
1851243830Sdim
1852249423Sdim  // Now it fits in the new leaf.
1853249423Sdim  treeInsert(a, b, y);
1854243830Sdim}
1855243830Sdim
1856243830Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1857243830Sdimvoid IntervalMap<KeyT, ValT, N, Traits>::
1858243830Sdimiterator::treeInsert(KeyT a, KeyT b, ValT y) {
1859243830Sdim  using namespace IntervalMapImpl;
1860243830Sdim  Path &P = this->path;
1861243830Sdim
1862243830Sdim  if (!P.valid())
1863243830Sdim    P.legalizeForInsert(this->map->height);
1864243830Sdim
1865243830Sdim  // Check if this insertion will extend the node to the left.
1866243830Sdim  if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<Leaf>().start(0))) {
1867243830Sdim    // Node is growing to the left, will it affect a left sibling node?
1868243830Sdim    if (NodeRef Sib = P.getLeftSibling(P.height())) {
1869243830Sdim      Leaf &SibLeaf = Sib.get<Leaf>();
1870243830Sdim      unsigned SibOfs = Sib.size() - 1;
1871249423Sdim      if (SibLeaf.value(SibOfs) == y &&
1872243830Sdim          Traits::adjacent(SibLeaf.stop(SibOfs), a)) {
1873243830Sdim        // This insertion will coalesce with the last entry in SibLeaf. We can
1874243830Sdim        // handle it in two ways:
1875243830Sdim        //  1. Extend SibLeaf.stop to b and be done, or
1876243830Sdim        //  2. Extend a to SibLeaf, erase the SibLeaf entry and continue.
1877243830Sdim        // We prefer 1., but need 2 when coalescing to the right as well.
1878243830Sdim        Leaf &CurLeaf = P.leaf<Leaf>();
1879243830Sdim        P.moveLeft(P.height());
1880243830Sdim        if (Traits::stopLess(b, CurLeaf.start(0)) &&
1881243830Sdim            (y != CurLeaf.value(0) || !Traits::adjacent(b, CurLeaf.start(0)))) {
1882243830Sdim          // Easy, just extend SibLeaf and we're done.
1883243830Sdim          setNodeStop(P.height(), SibLeaf.stop(SibOfs) = b);
1884243830Sdim          return;
1885243830Sdim        } else {
1886249423Sdim          // We have both left and right coalescing. Erase the old SibLeaf entry
1887249423Sdim          // and continue inserting the larger interval.
1888249423Sdim          a = SibLeaf.start(SibOfs);
1889249423Sdim          treeErase(/* UpdateRoot= */false);
1890249423Sdim        }
1891249423Sdim      }
1892249423Sdim    } else {
1893243830Sdim      // No left sibling means we are at begin(). Update cached bound.
1894243830Sdim      this->map->rootBranchStart() = a;
1895243830Sdim    }
1896243830Sdim  }
1897243830Sdim
1898243830Sdim  // When we are inserting at the end of a leaf node, we must update stops.
1899249423Sdim  unsigned Size = P.leafSize();
1900249423Sdim  bool Grow = P.leafOffset() == Size;
1901243830Sdim  Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), Size, a, b, y);
1902243830Sdim
1903243830Sdim  // Leaf insertion unsuccessful? Overflow and try again.
1904249423Sdim  if (Size > Leaf::Capacity) {
1905243830Sdim    overflow<Leaf>(P.height());
1906243830Sdim    Grow = P.leafOffset() == P.leafSize();
1907243830Sdim    Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y);
1908243830Sdim    assert(Size <= Leaf::Capacity && "overflow() didn't make room");
1909243830Sdim  }
1910243830Sdim
1911243830Sdim  // Inserted, update offset and leaf size.
1912243830Sdim  P.setSize(P.height(), Size);
1913243830Sdim
1914243830Sdim  // Insert was the last node entry, update stops.
1915243830Sdim  if (Grow)
1916243830Sdim    setNodeStop(P.height(), b);
1917243830Sdim}
1918243830Sdim
1919243830Sdim/// erase - erase the current interval and move to the next position.
1920243830Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1921243830Sdimvoid IntervalMap<KeyT, ValT, N, Traits>::
1922243830Sdimiterator::erase() {
1923243830Sdim  IntervalMap &IM = *this->map;
1924243830Sdim  IntervalMapImpl::Path &P = this->path;
1925243830Sdim  assert(P.valid() && "Cannot erase end()");
1926243830Sdim  if (this->branched())
1927243830Sdim    return treeErase();
1928243830Sdim  IM.rootLeaf().erase(P.leafOffset(), IM.rootSize);
1929243830Sdim  P.setSize(0, --IM.rootSize);
1930243830Sdim}
1931243830Sdim
1932243830Sdim/// treeErase - erase() for a branched tree.
1933243830Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1934243830Sdimvoid IntervalMap<KeyT, ValT, N, Traits>::
1935243830Sdimiterator::treeErase(bool UpdateRoot) {
1936243830Sdim  IntervalMap &IM = *this->map;
1937243830Sdim  IntervalMapImpl::Path &P = this->path;
1938243830Sdim  Leaf &Node = P.leaf<Leaf>();
1939243830Sdim
1940243830Sdim  // Nodes are not allowed to become empty.
1941243830Sdim  if (P.leafSize() == 1) {
1942243830Sdim    IM.deleteNode(&Node);
1943243830Sdim    eraseNode(IM.height);
1944243830Sdim    // Update rootBranchStart if we erased begin().
1945243830Sdim    if (UpdateRoot && IM.branched() && P.valid() && P.atBegin())
1946243830Sdim      IM.rootBranchStart() = P.leaf<Leaf>().start(0);
1947243830Sdim    return;
1948243830Sdim  }
1949243830Sdim
1950243830Sdim  // Erase current entry.
1951243830Sdim  Node.erase(P.leafOffset(), P.leafSize());
1952243830Sdim  unsigned NewSize = P.leafSize() - 1;
1953243830Sdim  P.setSize(IM.height, NewSize);
1954243830Sdim  // When we erase the last entry, update stop and move to a legal position.
1955243830Sdim  if (P.leafOffset() == NewSize) {
1956243830Sdim    setNodeStop(IM.height, Node.stop(NewSize - 1));
1957243830Sdim    P.moveRight(IM.height);
1958243830Sdim  } else if (UpdateRoot && P.atBegin())
1959243830Sdim    IM.rootBranchStart() = P.leaf<Leaf>().start(0);
1960243830Sdim}
1961243830Sdim
1962243830Sdim/// eraseNode - Erase the current node at Level from its parent and move path to
1963243830Sdim/// the first entry of the next sibling node.
1964243830Sdim/// The node must be deallocated by the caller.
1965243830Sdim/// @param Level 1..height, the root node cannot be erased.
1966243830Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
1967243830Sdimvoid IntervalMap<KeyT, ValT, N, Traits>::
1968243830Sdimiterator::eraseNode(unsigned Level) {
1969243830Sdim  assert(Level && "Cannot erase root node");
1970243830Sdim  IntervalMap &IM = *this->map;
1971243830Sdim  IntervalMapImpl::Path &P = this->path;
1972249423Sdim
1973243830Sdim  if (--Level == 0) {
1974243830Sdim    IM.rootBranch().erase(P.offset(0), IM.rootSize);
1975243830Sdim    P.setSize(0, --IM.rootSize);
1976243830Sdim    // If this cleared the root, switch to height=0.
1977249423Sdim    if (IM.empty()) {
1978249423Sdim      IM.switchRootToLeaf();
1979249423Sdim      this->setRoot(0);
1980249423Sdim      return;
1981243830Sdim    }
1982249423Sdim  } else {
1983243830Sdim    // Remove node ref from branch node at Level.
1984243830Sdim    Branch &Parent = P.node<Branch>(Level);
1985243830Sdim    if (P.size(Level) == 1) {
1986249423Sdim      // Branch node became empty, remove it recursively.
1987243830Sdim      IM.deleteNode(&Parent);
1988243830Sdim      eraseNode(Level);
1989243830Sdim    } else {
1990243830Sdim      // Branch node won't become empty.
1991243830Sdim      Parent.erase(P.offset(Level), P.size(Level));
1992243830Sdim      unsigned NewSize = P.size(Level) - 1;
1993243830Sdim      P.setSize(Level, NewSize);
1994249423Sdim      // If we removed the last branch, update stop and move to a legal pos.
1995243830Sdim      if (P.offset(Level) == NewSize) {
1996243830Sdim        setNodeStop(Level, Parent.stop(NewSize - 1));
1997243830Sdim        P.moveRight(Level);
1998243830Sdim      }
1999243830Sdim    }
2000243830Sdim  }
2001243830Sdim  // Update path cache for the new right sibling position.
2002243830Sdim  if (P.valid()) {
2003249423Sdim    P.reset(Level + 1);
2004249423Sdim    P.offset(Level + 1) = 0;
2005249423Sdim  }
2006249423Sdim}
2007249423Sdim
2008249423Sdim/// overflow - Distribute entries of the current node evenly among
2009249423Sdim/// its siblings and ensure that the current node is not full.
2010249423Sdim/// This may require allocating a new node.
2011249423Sdim/// @tparam NodeT The type of node at Level (Leaf or Branch).
2012249423Sdim/// @param Level path index of the overflowing node.
2013249423Sdim/// @return True when the tree height was changed.
2014249423Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits>
2015249423Sdimtemplate <typename NodeT>
2016243830Sdimbool IntervalMap<KeyT, ValT, N, Traits>::
2017249423Sdimiterator::overflow(unsigned Level) {
2018249423Sdim  using namespace IntervalMapImpl;
2019243830Sdim  Path &P = this->path;
2020249423Sdim  unsigned CurSize[4];
2021243830Sdim  NodeT *Node[4];
2022243830Sdim  unsigned Nodes = 0;
2023249423Sdim  unsigned Elements = 0;
2024249423Sdim  unsigned Offset = P.offset(Level);
2025212795Sdim
2026212795Sdim  // Do we have a left sibling?
2027212795Sdim  NodeRef LeftSib = P.getLeftSibling(Level);
2028212795Sdim  if (LeftSib) {
2029212795Sdim    Offset += Elements = CurSize[Nodes] = LeftSib.size();
2030212795Sdim    Node[Nodes++] = &LeftSib.get<NodeT>();
2031212795Sdim  }
2032212795Sdim
2033212795Sdim  // Current node.
2034212795Sdim  Elements += CurSize[Nodes] = P.size(Level);
2035243830Sdim  Node[Nodes++] = &P.node<NodeT>(Level);
2036212795Sdim
2037212795Sdim  // Do we have a right sibling?
2038249423Sdim  NodeRef RightSib = P.getRightSibling(Level);
2039218893Sdim  if (RightSib) {
2040218893Sdim    Elements += CurSize[Nodes] = RightSib.size();
2041218893Sdim    Node[Nodes++] = &RightSib.get<NodeT>();
2042243830Sdim  }
2043218893Sdim
2044218893Sdim  // Do we need to allocate a new node?
2045249423Sdim  unsigned NewNode = 0;
2046212795Sdim  if (Elements + 1 > Nodes * NodeT::Capacity) {
2047212795Sdim    // Insert NewNode at the penultimate position, or after a single node.
2048226633Sdim    NewNode = Nodes == 1 ? 1 : Nodes - 1;
2049226633Sdim    CurSize[Nodes] = CurSize[NewNode];
2050249423Sdim    Node[Nodes] = Node[NewNode];
2051218893Sdim    CurSize[NewNode] = 0;
2052218893Sdim    Node[NewNode] = this->map->template newNode<NodeT>();
2053212795Sdim    ++Nodes;
2054243830Sdim  }
2055212795Sdim
2056218893Sdim  // Compute the new element distribution.
2057212795Sdim  unsigned NewSize[4];
2058249423Sdim  IdxPair NewOffset = distribute(Nodes, Elements, NodeT::Capacity,
2059218893Sdim                                 CurSize, NewSize, Offset, true);
2060218893Sdim  adjustSiblingSizes(Node, Nodes, CurSize, NewSize);
2061218893Sdim
2062249423Sdim  // Move current location to the leftmost node.
2063218893Sdim  if (LeftSib)
2064249423Sdim    P.moveLeft(Level);
2065249423Sdim
2066249423Sdim  // Elements have been rearranged, now update node sizes and stops.
2067218893Sdim  bool SplitRoot = false;
2068249423Sdim  unsigned Pos = 0;
2069249423Sdim  while (true) {
2070226633Sdim    KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1);
2071249423Sdim    if (NewNode && Pos == NewNode) {
2072226633Sdim      SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop);
2073226633Sdim      Level += SplitRoot;
2074218893Sdim    } else {
2075218893Sdim      P.setSize(Level, NewSize[Pos]);
2076212795Sdim      setNodeStop(Level, Stop);
2077243830Sdim    }
2078243830Sdim    if (Pos + 1 == Nodes)
2079212795Sdim      break;
2080249423Sdim    P.moveRight(Level);
2081234353Sdim    ++Pos;
2082243830Sdim  }
2083243830Sdim
2084234353Sdim  // Where was I? Find NewOffset.
2085249423Sdim  while(Pos != NewOffset.first) {
2086239462Sdim    P.moveLeft(Level);
2087249423Sdim    --Pos;
2088239462Sdim  }
2089239462Sdim  P.offset(Level) = NewOffset.second;
2090239462Sdim  return SplitRoot;
2091243830Sdim}
2092239462Sdim
2093239462Sdim//===----------------------------------------------------------------------===//
2094239462Sdim//---                       IntervalMapOverlaps                           ----//
2095239462Sdim//===----------------------------------------------------------------------===//
2096249423Sdim
2097234353Sdim/// IntervalMapOverlaps - Iterate over the overlaps of mapped intervals in two
2098249423Sdim/// IntervalMaps. The maps may be different, but the KeyT and Traits types
2099249423Sdim/// should be the same.
2100249423Sdim///
2101249423Sdim/// Typical uses:
2102249423Sdim///
2103212795Sdim/// 1. Test for overlap:
2104212795Sdim///    bool overlap = IntervalMapOverlaps(a, b).valid();
2105249423Sdim///
2106249423Sdim/// 2. Enumerate overlaps:
2107249423Sdim///    for (IntervalMapOverlaps I(a, b); I.valid() ; ++I) { ... }
2108249423Sdim///
2109212795Sdimtemplate <typename MapA, typename MapB>
2110212795Sdimclass IntervalMapOverlaps {
2111212795Sdim  using KeyType = typename MapA::KeyType;
2112212795Sdim  using Traits = typename MapA::KeyTraits;
2113249423Sdim
2114249423Sdim  typename MapA::const_iterator posA;
2115212795Sdim  typename MapB::const_iterator posB;
2116212795Sdim
2117212795Sdim  /// advance - Move posA and posB forward until reaching an overlap, or until
2118226633Sdim  /// either meets end.
2119212795Sdim  /// Don't move the iterators if they are already overlapping.
2120212795Sdim  void advance() {
2121243830Sdim    if (!valid())
2122212795Sdim      return;
2123249423Sdim
2124212795Sdim    if (Traits::stopLess(posA.stop(), posB.start())) {
2125226633Sdim      // A ends before B begins. Catch up.
2126226633Sdim      posA.advanceTo(posB.start());
2127226633Sdim      if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
2128226633Sdim        return;
2129226633Sdim    } else if (Traits::stopLess(posB.stop(), posA.start())) {
2130226633Sdim      // B ends before A begins. Catch up.
2131226633Sdim      posB.advanceTo(posA.start());
2132226633Sdim      if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
2133234353Sdim        return;
2134234353Sdim    } else
2135234353Sdim      // Already overlapping.
2136226633Sdim      return;
2137226633Sdim
2138226633Sdim    while (true) {
2139212795Sdim      // Make a.end > b.start.
2140226633Sdim      posA.advanceTo(posB.start());
2141226633Sdim      if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
2142226633Sdim        return;
2143212795Sdim      // Make b.end > a.start.
2144212795Sdim      posB.advanceTo(posA.start());
2145243830Sdim      if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
2146212795Sdim        return;
2147249423Sdim    }
2148212795Sdim  }
2149226633Sdim
2150226633Sdimpublic:
2151226633Sdim  /// IntervalMapOverlaps - Create an iterator for the overlaps of a and b.
2152226633Sdim  IntervalMapOverlaps(const MapA &a, const MapB &b)
2153226633Sdim    : posA(b.empty() ? a.end() : a.find(b.start())),
2154226633Sdim      posB(posA.valid() ? b.find(posA.start()) : b.end()) { advance(); }
2155226633Sdim
2156226633Sdim  /// valid - Return true if iterator is at an overlap.
2157226633Sdim  bool valid() const {
2158226633Sdim    return posA.valid() && posB.valid();
2159226633Sdim  }
2160234353Sdim
2161234353Sdim  /// a - access the left hand side in the overlap.
2162226633Sdim  const typename MapA::const_iterator &a() const { return posA; }
2163234353Sdim
2164234353Sdim  /// b - access the right hand side in the overlap.
2165234353Sdim  const typename MapB::const_iterator &b() const { return posB; }
2166234353Sdim
2167226633Sdim  /// start - Beginning of the overlapping interval.
2168226633Sdim  KeyType start() const {
2169212795Sdim    KeyType ak = a().start();
2170226633Sdim    KeyType bk = b().start();
2171226633Sdim    return Traits::startLess(ak, bk) ? bk : ak;
2172212795Sdim  }
2173226633Sdim
2174226633Sdim  /// stop - End of the overlapping interval.
2175249423Sdim  KeyType stop() const {
2176226633Sdim    KeyType ak = a().stop();
2177249423Sdim    KeyType bk = b().stop();
2178226633Sdim    return Traits::startLess(ak, bk) ? ak : bk;
2179212795Sdim  }
2180212795Sdim
2181212795Sdim  /// skipA - Move to the next overlap that doesn't involve a().
2182212795Sdim  void skipA() {
2183226633Sdim    ++posA;
2184226633Sdim    advance();
2185234982Sdim  }
2186234982Sdim
2187249423Sdim  /// skipB - Move to the next overlap that doesn't involve b().
2188249423Sdim  void skipB() {
2189226633Sdim    ++posB;
2190226633Sdim    advance();
2191226633Sdim  }
2192226633Sdim
2193226633Sdim  /// Preincrement - Move to the next overlap.
2194212795Sdim  IntervalMapOverlaps &operator++() {
2195226633Sdim    // Bump the iterator that ends first. The other one may have more overlaps.
2196212795Sdim    if (Traits::startLess(posB.stop(), posA.stop()))
2197212795Sdim      skipB();
2198212795Sdim    else
2199212795Sdim      skipA();
2200249423Sdim    return *this;
2201212795Sdim  }
2202212795Sdim
2203212795Sdim  /// advanceTo - Move to the first overlapping interval with
2204212795Sdim  /// stopLess(x, stop()).
2205212795Sdim  void advanceTo(KeyType x) {
2206218893Sdim    if (!valid())
2207226633Sdim      return;
2208226633Sdim    // Make sure advanceTo sees monotonic keys.
2209212795Sdim    if (Traits::stopLess(posA.stop(), x))
2210212795Sdim      posA.advanceTo(x);
2211212795Sdim    if (Traits::stopLess(posB.stop(), x))
2212226633Sdim      posB.advanceTo(x);
2213212795Sdim    advance();
2214212795Sdim  }
2215243830Sdim};
2216212795Sdim
2217249423Sdim} // end namespace llvm
2218212795Sdim
2219226633Sdim#endif // LLVM_ADT_INTERVALMAP_H
2220226633Sdim