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