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