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