LLVM  16.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 = 0;
979 
980  // Number of entries in the root node.
981  unsigned rootSize = 0;
982 
983  // Allocator used for creating external nodes.
984  Allocator *allocator = nullptr;
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) : allocator(&a) {
1042  new (&rootLeaf()) RootLeaf();
1043  }
1044 
1045  ///@{
1046  /// NOTE: The moved-from or copied-from object's allocator needs to have a
1047  /// lifetime equal to or exceeding the moved-to or copied-to object to avoid
1048  /// undefined behaviour.
1050  // Future-proofing assertion: this function assumes the IntervalMap
1051  // constructor doesn't add any nodes.
1052  assert(empty() && "Expected emptry tree");
1053  *this = RHS;
1054  }
1056  clear();
1057  allocator = RHS.allocator;
1058  for (auto It = RHS.begin(), End = RHS.end(); It != End; ++It)
1059  insert(It.start(), It.stop(), It.value());
1060  return *this;
1061  }
1062 
1064  // Future-proofing assertion: this function assumes the IntervalMap
1065  // constructor doesn't add any nodes.
1066  assert(empty() && "Expected emptry tree");
1067  *this = std::move(RHS);
1068  }
1070  // Calling clear deallocates memory and switches to rootLeaf.
1071  clear();
1072  // Destroy the new rootLeaf.
1073  rootLeaf().~RootLeaf();
1074 
1075  height = RHS.height;
1076  rootSize = RHS.rootSize;
1077  allocator = RHS.allocator;
1078 
1079  // rootLeaf and rootBranch are both uninitialized. Move RHS data into
1080  // appropriate field.
1081  if (RHS.branched()) {
1082  rootBranch() = std::move(RHS.rootBranch());
1083  // Prevent RHS deallocating memory LHS now owns by replacing RHS
1084  // rootBranch with a new rootLeaf.
1085  RHS.rootBranch().~RootBranch();
1086  RHS.height = 0;
1087  new (&RHS.rootLeaf()) RootLeaf();
1088  } else {
1089  rootLeaf() = std::move(RHS.rootLeaf());
1090  }
1091  return *this;
1092  }
1093  ///@}
1094 
1096  clear();
1097  rootLeaf().~RootLeaf();
1098  }
1099 
1100  /// empty - Return true when no intervals are mapped.
1101  bool empty() const {
1102  return rootSize == 0;
1103  }
1104 
1105  /// start - Return the smallest mapped key in a non-empty map.
1106  KeyT start() const {
1107  assert(!empty() && "Empty IntervalMap has no start");
1108  return !branched() ? rootLeaf().start(0) : rootBranchStart();
1109  }
1110 
1111  /// stop - Return the largest mapped key in a non-empty map.
1112  KeyT stop() const {
1113  assert(!empty() && "Empty IntervalMap has no stop");
1114  return !branched() ? rootLeaf().stop(rootSize - 1) :
1115  rootBranch().stop(rootSize - 1);
1116  }
1117 
1118  /// lookup - Return the mapped value at x or NotFound.
1120  if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x))
1121  return NotFound;
1122  return branched() ? treeSafeLookup(x, NotFound) :
1123  rootLeaf().safeLookup(x, NotFound);
1124  }
1125 
1126  /// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
1127  /// It is assumed that no key in the interval is mapped to another value, but
1128  /// overlapping intervals already mapped to y will be coalesced.
1129  void insert(KeyT a, KeyT b, ValT y) {
1130  if (branched() || rootSize == RootLeaf::Capacity)
1131  return find(a).insert(a, b, y);
1132 
1133  // Easy insert into root leaf.
1134  unsigned p = rootLeaf().findFrom(0, rootSize, a);
1135  rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y);
1136  }
1137 
1138  /// clear - Remove all entries.
1139  void clear();
1140 
1141  class const_iterator;
1142  class iterator;
1143  friend class const_iterator;
1144  friend class iterator;
1145 
1147  const_iterator I(*this);
1148  I.goToBegin();
1149  return I;
1150  }
1151 
1153  iterator I(*this);
1154  I.goToBegin();
1155  return I;
1156  }
1157 
1159  const_iterator I(*this);
1160  I.goToEnd();
1161  return I;
1162  }
1163 
1165  iterator I(*this);
1166  I.goToEnd();
1167  return I;
1168  }
1169 
1170  /// find - Return an iterator pointing to the first interval ending at or
1171  /// after x, or end().
1173  const_iterator I(*this);
1174  I.find(x);
1175  return I;
1176  }
1177 
1179  iterator I(*this);
1180  I.find(x);
1181  return I;
1182  }
1183 
1184  /// overlaps(a, b) - Return true if the intervals in this map overlap with the
1185  /// interval [a;b].
1186  bool overlaps(KeyT a, KeyT b) const {
1187  assert(Traits::nonEmpty(a, b));
1188  const_iterator I = find(a);
1189  if (!I.valid())
1190  return false;
1191  // [a;b] and [x;y] overlap iff x<=b and a<=y. The find() call guarantees the
1192  // second part (y = find(a).stop()), so it is sufficient to check the first
1193  // one.
1194  return !Traits::stopLess(b, I.start());
1195  }
1196 };
1197 
1198 /// treeSafeLookup - Return the mapped value at x or NotFound, assuming a
1199 /// branched root.
1200 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1201 ValT IntervalMap<KeyT, ValT, N, Traits>::
1202 treeSafeLookup(KeyT x, ValT NotFound) const {
1203  assert(branched() && "treeLookup assumes a branched root");
1204 
1205  IntervalMapImpl::NodeRef NR = rootBranch().safeLookup(x);
1206  for (unsigned h = height-1; h; --h)
1207  NR = NR.get<Branch>().safeLookup(x);
1208  return NR.get<Leaf>().safeLookup(x, NotFound);
1209 }
1210 
1211 // branchRoot - Switch from a leaf root to a branched root.
1212 // Return the new (root offset, node offset) corresponding to Position.
1213 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1214 IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
1215 branchRoot(unsigned Position) {
1216  using namespace IntervalMapImpl;
1217  // How many external leaf nodes to hold RootLeaf+1?
1218  const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1;
1219 
1220  // Compute element distribution among new nodes.
1221  unsigned size[Nodes];
1222  IdxPair NewOffset(0, Position);
1223 
1224  // Is is very common for the root node to be smaller than external nodes.
1225  if (Nodes == 1)
1226  size[0] = rootSize;
1227  else
1228  NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, nullptr, size,
1229  Position, true);
1230 
1231  // Allocate new nodes.
1232  unsigned pos = 0;
1233  NodeRef node[Nodes];
1234  for (unsigned n = 0; n != Nodes; ++n) {
1235  Leaf *L = newNode<Leaf>();
1236  L->copy(rootLeaf(), pos, 0, size[n]);
1237  node[n] = NodeRef(L, size[n]);
1238  pos += size[n];
1239  }
1240 
1241  // Destroy the old leaf node, construct branch node instead.
1242  switchRootToBranch();
1243  for (unsigned n = 0; n != Nodes; ++n) {
1244  rootBranch().stop(n) = node[n].template get<Leaf>().stop(size[n]-1);
1245  rootBranch().subtree(n) = node[n];
1246  }
1247  rootBranchStart() = node[0].template get<Leaf>().start(0);
1248  rootSize = Nodes;
1249  return NewOffset;
1250 }
1251 
1252 // splitRoot - Split the current BranchRoot into multiple Branch nodes.
1253 // Return the new (root offset, node offset) corresponding to Position.
1254 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1255 IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
1256 splitRoot(unsigned Position) {
1257  using namespace IntervalMapImpl;
1258  // How many external leaf nodes to hold RootBranch+1?
1259  const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1;
1260 
1261  // Compute element distribution among new nodes.
1262  unsigned Size[Nodes];
1263  IdxPair NewOffset(0, Position);
1264 
1265  // Is is very common for the root node to be smaller than external nodes.
1266  if (Nodes == 1)
1267  Size[0] = rootSize;
1268  else
1269  NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, nullptr, Size,
1270  Position, true);
1271 
1272  // Allocate new nodes.
1273  unsigned Pos = 0;
1274  NodeRef Node[Nodes];
1275  for (unsigned n = 0; n != Nodes; ++n) {
1276  Branch *B = newNode<Branch>();
1277  B->copy(rootBranch(), Pos, 0, Size[n]);
1278  Node[n] = NodeRef(B, Size[n]);
1279  Pos += Size[n];
1280  }
1281 
1282  for (unsigned n = 0; n != Nodes; ++n) {
1283  rootBranch().stop(n) = Node[n].template get<Branch>().stop(Size[n]-1);
1284  rootBranch().subtree(n) = Node[n];
1285  }
1286  rootSize = Nodes;
1287  ++height;
1288  return NewOffset;
1289 }
1290 
1291 /// visitNodes - Visit each external node.
1292 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1293 void IntervalMap<KeyT, ValT, N, Traits>::
1294 visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, unsigned Height)) {
1295  if (!branched())
1296  return;
1297  SmallVector<IntervalMapImpl::NodeRef, 4> Refs, NextRefs;
1298 
1299  // Collect level 0 nodes from the root.
1300  for (unsigned i = 0; i != rootSize; ++i)
1301  Refs.push_back(rootBranch().subtree(i));
1302 
1303  // Visit all branch nodes.
1304  for (unsigned h = height - 1; h; --h) {
1305  for (unsigned i = 0, e = Refs.size(); i != e; ++i) {
1306  for (unsigned j = 0, s = Refs[i].size(); j != s; ++j)
1307  NextRefs.push_back(Refs[i].subtree(j));
1308  (this->*f)(Refs[i], h);
1309  }
1310  Refs.clear();
1311  Refs.swap(NextRefs);
1312  }
1313 
1314  // Visit all leaf nodes.
1315  for (unsigned i = 0, e = Refs.size(); i != e; ++i)
1316  (this->*f)(Refs[i], 0);
1317 }
1318 
1319 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1320 void IntervalMap<KeyT, ValT, N, Traits>::
1321 deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) {
1322  if (Level)
1323  deleteNode(&Node.get<Branch>());
1324  else
1325  deleteNode(&Node.get<Leaf>());
1326 }
1327 
1328 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1331  if (branched()) {
1332  visitNodes(&IntervalMap::deleteNode);
1333  switchRootToLeaf();
1334  }
1335  rootSize = 0;
1336 }
1337 
1338 //===----------------------------------------------------------------------===//
1339 //--- IntervalMap::const_iterator ----//
1340 //===----------------------------------------------------------------------===//
1341 
1342 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1343 class IntervalMap<KeyT, ValT, N, Traits>::const_iterator {
1344  friend class IntervalMap;
1345 
1346 public:
1347  using iterator_category = std::bidirectional_iterator_tag;
1348  using value_type = ValT;
1349  using difference_type = std::ptrdiff_t;
1350  using pointer = value_type *;
1352 
1353 protected:
1354  // The map referred to.
1355  IntervalMap *map = nullptr;
1356 
1357  // We store a full path from the root to the current position.
1358  // The path may be partially filled, but never between iterator calls.
1360 
1361  explicit const_iterator(const IntervalMap &map) :
1362  map(const_cast<IntervalMap*>(&map)) {}
1363 
1364  bool branched() const {
1365  assert(map && "Invalid iterator");
1366  return map->branched();
1367  }
1368 
1369  void setRoot(unsigned Offset) {
1370  if (branched())
1371  path.setRoot(&map->rootBranch(), map->rootSize, Offset);
1372  else
1373  path.setRoot(&map->rootLeaf(), map->rootSize, Offset);
1374  }
1375 
1376  void pathFillFind(KeyT x);
1377  void treeFind(KeyT x);
1378  void treeAdvanceTo(KeyT x);
1379 
1380  /// unsafeStart - Writable access to start() for iterator.
1381  KeyT &unsafeStart() const {
1382  assert(valid() && "Cannot access invalid iterator");
1383  return branched() ? path.leaf<Leaf>().start(path.leafOffset()) :
1384  path.leaf<RootLeaf>().start(path.leafOffset());
1385  }
1386 
1387  /// unsafeStop - Writable access to stop() for iterator.
1388  KeyT &unsafeStop() const {
1389  assert(valid() && "Cannot access invalid iterator");
1390  return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) :
1391  path.leaf<RootLeaf>().stop(path.leafOffset());
1392  }
1393 
1394  /// unsafeValue - Writable access to value() for iterator.
1395  ValT &unsafeValue() const {
1396  assert(valid() && "Cannot access invalid iterator");
1397  return branched() ? path.leaf<Leaf>().value(path.leafOffset()) :
1398  path.leaf<RootLeaf>().value(path.leafOffset());
1399  }
1400 
1401 public:
1402  /// const_iterator - Create an iterator that isn't pointing anywhere.
1403  const_iterator() = default;
1404 
1405  /// setMap - Change the map iterated over. This call must be followed by a
1406  /// call to goToBegin(), goToEnd(), or find()
1407  void setMap(const IntervalMap &m) { map = const_cast<IntervalMap*>(&m); }
1408 
1409  /// valid - Return true if the current position is valid, false for end().
1410  bool valid() const { return path.valid(); }
1411 
1412  /// atBegin - Return true if the current position is the first map entry.
1413  bool atBegin() const { return path.atBegin(); }
1414 
1415  /// start - Return the beginning of the current interval.
1416  const KeyT &start() const { return unsafeStart(); }
1417 
1418  /// stop - Return the end of the current interval.
1419  const KeyT &stop() const { return unsafeStop(); }
1420 
1421  /// value - Return the mapped value at the current interval.
1422  const ValT &value() const { return unsafeValue(); }
1423 
1424  const ValT &operator*() const { return value(); }
1425 
1426  bool operator==(const const_iterator &RHS) const {
1427  assert(map == RHS.map && "Cannot compare iterators from different maps");
1428  if (!valid())
1429  return !RHS.valid();
1430  if (path.leafOffset() != RHS.path.leafOffset())
1431  return false;
1432  return &path.template leaf<Leaf>() == &RHS.path.template leaf<Leaf>();
1433  }
1434 
1435  bool operator!=(const const_iterator &RHS) const {
1436  return !operator==(RHS);
1437  }
1438 
1439  /// goToBegin - Move to the first interval in map.
1440  void goToBegin() {
1441  setRoot(0);
1442  if (branched())
1443  path.fillLeft(map->height);
1444  }
1445 
1446  /// goToEnd - Move beyond the last interval in map.
1447  void goToEnd() {
1448  setRoot(map->rootSize);
1449  }
1450 
1451  /// preincrement - Move to the next interval.
1453  assert(valid() && "Cannot increment end()");
1454  if (++path.leafOffset() == path.leafSize() && branched())
1455  path.moveRight(map->height);
1456  return *this;
1457  }
1458 
1459  /// postincrement - Don't do that!
1461  const_iterator tmp = *this;
1462  operator++();
1463  return tmp;
1464  }
1465 
1466  /// predecrement - Move to the previous interval.
1468  if (path.leafOffset() && (valid() || !branched()))
1469  --path.leafOffset();
1470  else
1471  path.moveLeft(map->height);
1472  return *this;
1473  }
1474 
1475  /// postdecrement - Don't do that!
1477  const_iterator tmp = *this;
1478  operator--();
1479  return tmp;
1480  }
1481 
1482  /// find - Move to the first interval with stop >= x, or end().
1483  /// This is a full search from the root, the current position is ignored.
1484  void find(KeyT x) {
1485  if (branched())
1486  treeFind(x);
1487  else
1488  setRoot(map->rootLeaf().findFrom(0, map->rootSize, x));
1489  }
1490 
1491  /// advanceTo - Move to the first interval with stop >= x, or end().
1492  /// The search is started from the current position, and no earlier positions
1493  /// can be found. This is much faster than find() for small moves.
1494  void advanceTo(KeyT x) {
1495  if (!valid())
1496  return;
1497  if (branched())
1498  treeAdvanceTo(x);
1499  else
1500  path.leafOffset() =
1501  map->rootLeaf().findFrom(path.leafOffset(), map->rootSize, x);
1502  }
1503 };
1504 
1505 /// pathFillFind - Complete path by searching for x.
1506 /// @param x Key to search for.
1507 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1510  IntervalMapImpl::NodeRef NR = path.subtree(path.height());
1511  for (unsigned i = map->height - path.height() - 1; i; --i) {
1512  unsigned p = NR.get<Branch>().safeFind(0, x);
1513  path.push(NR, p);
1514  NR = NR.subtree(p);
1515  }
1516  path.push(NR, NR.get<Leaf>().safeFind(0, x));
1517 }
1518 
1519 /// treeFind - Find in a branched tree.
1520 /// @param x Key to search for.
1521 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1524  setRoot(map->rootBranch().findFrom(0, map->rootSize, x));
1525  if (valid())
1526  pathFillFind(x);
1527 }
1528 
1529 /// treeAdvanceTo - Find position after the current one.
1530 /// @param x Key to search for.
1531 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1534  // Can we stay on the same leaf node?
1535  if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) {
1536  path.leafOffset() = path.leaf<Leaf>().safeFind(path.leafOffset(), x);
1537  return;
1538  }
1539 
1540  // Drop the current leaf.
1541  path.pop();
1542 
1543  // Search towards the root for a usable subtree.
1544  if (path.height()) {
1545  for (unsigned l = path.height() - 1; l; --l) {
1546  if (!Traits::stopLess(path.node<Branch>(l).stop(path.offset(l)), x)) {
1547  // The branch node at l+1 is usable
1548  path.offset(l + 1) =
1549  path.node<Branch>(l + 1).safeFind(path.offset(l + 1), x);
1550  return pathFillFind(x);
1551  }
1552  path.pop();
1553  }
1554  // Is the level-1 Branch usable?
1555  if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) {
1556  path.offset(1) = path.node<Branch>(1).safeFind(path.offset(1), x);
1557  return pathFillFind(x);
1558  }
1559  }
1560 
1561  // We reached the root.
1562  setRoot(map->rootBranch().findFrom(path.offset(0), map->rootSize, x));
1563  if (valid())
1564  pathFillFind(x);
1565 }
1566 
1567 //===----------------------------------------------------------------------===//
1568 //--- IntervalMap::iterator ----//
1569 //===----------------------------------------------------------------------===//
1570 
1571 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1572 class IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator {
1573  friend class IntervalMap;
1574 
1575  using IdxPair = IntervalMapImpl::IdxPair;
1576 
1577  explicit iterator(IntervalMap &map) : const_iterator(map) {}
1578 
1579  void setNodeStop(unsigned Level, KeyT Stop);
1580  bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop);
1581  template <typename NodeT> bool overflow(unsigned Level);
1582  void treeInsert(KeyT a, KeyT b, ValT y);
1583  void eraseNode(unsigned Level);
1584  void treeErase(bool UpdateRoot = true);
1585  bool canCoalesceLeft(KeyT Start, ValT x);
1586  bool canCoalesceRight(KeyT Stop, ValT x);
1587 
1588 public:
1589  /// iterator - Create null iterator.
1590  iterator() = default;
1591 
1592  /// setStart - Move the start of the current interval.
1593  /// This may cause coalescing with the previous interval.
1594  /// @param a New start key, must not overlap the previous interval.
1595  void setStart(KeyT a);
1596 
1597  /// setStop - Move the end of the current interval.
1598  /// This may cause coalescing with the following interval.
1599  /// @param b New stop key, must not overlap the following interval.
1600  void setStop(KeyT b);
1601 
1602  /// setValue - Change the mapped value of the current interval.
1603  /// This may cause coalescing with the previous and following intervals.
1604  /// @param x New value.
1605  void setValue(ValT x);
1606 
1607  /// setStartUnchecked - Move the start of the current interval without
1608  /// checking for coalescing or overlaps.
1609  /// This should only be used when it is known that coalescing is not required.
1610  /// @param a New start key.
1611  void setStartUnchecked(KeyT a) { this->unsafeStart() = a; }
1612 
1613  /// setStopUnchecked - Move the end of the current interval without checking
1614  /// for coalescing or overlaps.
1615  /// This should only be used when it is known that coalescing is not required.
1616  /// @param b New stop key.
1618  this->unsafeStop() = b;
1619  // Update keys in branch nodes as well.
1620  if (this->path.atLastEntry(this->path.height()))
1621  setNodeStop(this->path.height(), b);
1622  }
1623 
1624  /// setValueUnchecked - Change the mapped value of the current interval
1625  /// without checking for coalescing.
1626  /// @param x New value.
1627  void setValueUnchecked(ValT x) { this->unsafeValue() = x; }
1628 
1629  /// insert - Insert mapping [a;b] -> y before the current position.
1630  void insert(KeyT a, KeyT b, ValT y);
1631 
1632  /// erase - Erase the current interval.
1633  void erase();
1634 
1637  return *this;
1638  }
1639 
1641  iterator tmp = *this;
1642  operator++();
1643  return tmp;
1644  }
1645 
1648  return *this;
1649  }
1650 
1652  iterator tmp = *this;
1653  operator--();
1654  return tmp;
1655  }
1656 };
1657 
1658 /// canCoalesceLeft - Can the current interval coalesce to the left after
1659 /// changing start or value?
1660 /// @param Start New start of current interval.
1661 /// @param Value New value for current interval.
1662 /// @return True when updating the current interval would enable coalescing.
1663 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1665 iterator::canCoalesceLeft(KeyT Start, ValT Value) {
1666  using namespace IntervalMapImpl;
1667  Path &P = this->path;
1668  if (!this->branched()) {
1669  unsigned i = P.leafOffset();
1670  RootLeaf &Node = P.leaf<RootLeaf>();
1671  return i && Node.value(i-1) == Value &&
1672  Traits::adjacent(Node.stop(i-1), Start);
1673  }
1674  // Branched.
1675  if (unsigned i = P.leafOffset()) {
1676  Leaf &Node = P.leaf<Leaf>();
1677  return Node.value(i-1) == Value && Traits::adjacent(Node.stop(i-1), Start);
1678  } else if (NodeRef NR = P.getLeftSibling(P.height())) {
1679  unsigned i = NR.size() - 1;
1680  Leaf &Node = NR.get<Leaf>();
1681  return Node.value(i) == Value && Traits::adjacent(Node.stop(i), Start);
1682  }
1683  return false;
1684 }
1685 
1686 /// canCoalesceRight - Can the current interval coalesce to the right after
1687 /// changing stop or value?
1688 /// @param Stop New stop of current interval.
1689 /// @param Value New value for current interval.
1690 /// @return True when updating the current interval would enable coalescing.
1691 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1692 bool IntervalMap<KeyT, ValT, N, Traits>::
1693 iterator::canCoalesceRight(KeyT Stop, ValT Value) {
1694  using namespace IntervalMapImpl;
1695  Path &P = this->path;
1696  unsigned i = P.leafOffset() + 1;
1697  if (!this->branched()) {
1698  if (i >= P.leafSize())
1699  return false;
1700  RootLeaf &Node = P.leaf<RootLeaf>();
1701  return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));
1702  }
1703  // Branched.
1704  if (i < P.leafSize()) {
1705  Leaf &Node = P.leaf<Leaf>();
1706  return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));
1707  } else if (NodeRef NR = P.getRightSibling(P.height())) {
1708  Leaf &Node = NR.get<Leaf>();
1709  return Node.value(0) == Value && Traits::adjacent(Stop, Node.start(0));
1710  }
1711  return false;
1712 }
1713 
1714 /// setNodeStop - Update the stop key of the current node at level and above.
1715 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1716 void IntervalMap<KeyT, ValT, N, Traits>::
1717 iterator::setNodeStop(unsigned Level, KeyT Stop) {
1718  // There are no references to the root node, so nothing to update.
1719  if (!Level)
1720  return;
1721  IntervalMapImpl::Path &P = this->path;
1722  // Update nodes pointing to the current node.
1723  while (--Level) {
1724  P.node<Branch>(Level).stop(P.offset(Level)) = Stop;
1725  if (!P.atLastEntry(Level))
1726  return;
1727  }
1728  // Update root separately since it has a different layout.
1729  P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop;
1730 }
1731 
1732 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1735  assert(Traits::nonEmpty(a, this->stop()) && "Cannot move start beyond stop");
1736  KeyT &CurStart = this->unsafeStart();
1737  if (!Traits::startLess(a, CurStart) || !canCoalesceLeft(a, this->value())) {
1738  CurStart = a;
1739  return;
1740  }
1741  // Coalesce with the interval to the left.
1742  --*this;
1743  a = this->start();
1744  erase();
1745  setStartUnchecked(a);
1746 }
1747 
1748 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1751  assert(Traits::nonEmpty(this->start(), b) && "Cannot move stop beyond start");
1752  if (Traits::startLess(b, this->stop()) ||
1753  !canCoalesceRight(b, this->value())) {
1754  setStopUnchecked(b);
1755  return;
1756  }
1757  // Coalesce with interval to the right.
1758  KeyT a = this->start();
1759  erase();
1760  setStartUnchecked(a);
1761 }
1762 
1763 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1767  if (canCoalesceRight(this->stop(), x)) {
1768  KeyT a = this->start();
1769  erase();
1770  setStartUnchecked(a);
1771  }
1772  if (canCoalesceLeft(this->start(), x)) {
1773  --*this;
1774  KeyT a = this->start();
1775  erase();
1776  setStartUnchecked(a);
1777  }
1778 }
1779 
1780 /// insertNode - insert a node before the current path at level.
1781 /// Leave the current path pointing at the new node.
1782 /// @param Level path index of the node to be inserted.
1783 /// @param Node The node to be inserted.
1784 /// @param Stop The last index in the new node.
1785 /// @return True if the tree height was increased.
1786 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1789  assert(Level && "Cannot insert next to the root");
1790  bool SplitRoot = false;
1791  IntervalMap &IM = *this->map;
1792  IntervalMapImpl::Path &P = this->path;
1793 
1794  if (Level == 1) {
1795  // Insert into the root branch node.
1796  if (IM.rootSize < RootBranch::Capacity) {
1797  IM.rootBranch().insert(P.offset(0), IM.rootSize, Node, Stop);
1798  P.setSize(0, ++IM.rootSize);
1799  P.reset(Level);
1800  return SplitRoot;
1801  }
1802 
1803  // We need to split the root while keeping our position.
1804  SplitRoot = true;
1805  IdxPair Offset = IM.splitRoot(P.offset(0));
1806  P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset);
1807 
1808  // Fall through to insert at the new higher level.
1809  ++Level;
1810  }
1811 
1812  // When inserting before end(), make sure we have a valid path.
1813  P.legalizeForInsert(--Level);
1814 
1815  // Insert into the branch node at Level-1.
1816  if (P.size(Level) == Branch::Capacity) {
1817  // Branch node is full, handle handle the overflow.
1818  assert(!SplitRoot && "Cannot overflow after splitting the root");
1819  SplitRoot = overflow<Branch>(Level);
1820  Level += SplitRoot;
1821  }
1822  P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop);
1823  P.setSize(Level, P.size(Level) + 1);
1824  if (P.atLastEntry(Level))
1825  setNodeStop(Level, Stop);
1826  P.reset(Level + 1);
1827  return SplitRoot;
1828 }
1829 
1830 // insert
1831 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1834  if (this->branched())
1835  return treeInsert(a, b, y);
1836  IntervalMap &IM = *this->map;
1837  IntervalMapImpl::Path &P = this->path;
1838 
1839  // Try simple root leaf insert.
1840  unsigned Size = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y);
1841 
1842  // Was the root node insert successful?
1843  if (Size <= RootLeaf::Capacity) {
1844  P.setSize(0, IM.rootSize = Size);
1845  return;
1846  }
1847 
1848  // Root leaf node is full, we must branch.
1849  IdxPair Offset = IM.branchRoot(P.leafOffset());
1850  P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset);
1851 
1852  // Now it fits in the new leaf.
1853  treeInsert(a, b, y);
1854 }
1855 
1856 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1859  using namespace IntervalMapImpl;
1860  Path &P = this->path;
1861 
1862  if (!P.valid())
1863  P.legalizeForInsert(this->map->height);
1864 
1865  // Check if this insertion will extend the node to the left.
1866  if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<Leaf>().start(0))) {
1867  // Node is growing to the left, will it affect a left sibling node?
1868  if (NodeRef Sib = P.getLeftSibling(P.height())) {
1869  Leaf &SibLeaf = Sib.get<Leaf>();
1870  unsigned SibOfs = Sib.size() - 1;
1871  if (SibLeaf.value(SibOfs) == y &&
1872  Traits::adjacent(SibLeaf.stop(SibOfs), a)) {
1873  // This insertion will coalesce with the last entry in SibLeaf. We can
1874  // handle it in two ways:
1875  // 1. Extend SibLeaf.stop to b and be done, or
1876  // 2. Extend a to SibLeaf, erase the SibLeaf entry and continue.
1877  // We prefer 1., but need 2 when coalescing to the right as well.
1878  Leaf &CurLeaf = P.leaf<Leaf>();
1879  P.moveLeft(P.height());
1880  if (Traits::stopLess(b, CurLeaf.start(0)) &&
1881  (y != CurLeaf.value(0) || !Traits::adjacent(b, CurLeaf.start(0)))) {
1882  // Easy, just extend SibLeaf and we're done.
1883  setNodeStop(P.height(), SibLeaf.stop(SibOfs) = b);
1884  return;
1885  } else {
1886  // We have both left and right coalescing. Erase the old SibLeaf entry
1887  // and continue inserting the larger interval.
1888  a = SibLeaf.start(SibOfs);
1889  treeErase(/* UpdateRoot= */false);
1890  }
1891  }
1892  } else {
1893  // No left sibling means we are at begin(). Update cached bound.
1894  this->map->rootBranchStart() = a;
1895  }
1896  }
1897 
1898  // When we are inserting at the end of a leaf node, we must update stops.
1899  unsigned Size = P.leafSize();
1900  bool Grow = P.leafOffset() == Size;
1901  Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), Size, a, b, y);
1902 
1903  // Leaf insertion unsuccessful? Overflow and try again.
1904  if (Size > Leaf::Capacity) {
1905  overflow<Leaf>(P.height());
1906  Grow = P.leafOffset() == P.leafSize();
1907  Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y);
1908  assert(Size <= Leaf::Capacity && "overflow() didn't make room");
1909  }
1910 
1911  // Inserted, update offset and leaf size.
1912  P.setSize(P.height(), Size);
1913 
1914  // Insert was the last node entry, update stops.
1915  if (Grow)
1916  setNodeStop(P.height(), b);
1917 }
1918 
1919 /// erase - erase the current interval and move to the next position.
1920 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1923  IntervalMap &IM = *this->map;
1924  IntervalMapImpl::Path &P = this->path;
1925  assert(P.valid() && "Cannot erase end()");
1926  if (this->branched())
1927  return treeErase();
1928  IM.rootLeaf().erase(P.leafOffset(), IM.rootSize);
1929  P.setSize(0, --IM.rootSize);
1930 }
1931 
1932 /// treeErase - erase() for a branched tree.
1933 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1935 iterator::treeErase(bool UpdateRoot) {
1936  IntervalMap &IM = *this->map;
1937  IntervalMapImpl::Path &P = this->path;
1938  Leaf &Node = P.leaf<Leaf>();
1939 
1940  // Nodes are not allowed to become empty.
1941  if (P.leafSize() == 1) {
1942  IM.deleteNode(&Node);
1943  eraseNode(IM.height);
1944  // Update rootBranchStart if we erased begin().
1945  if (UpdateRoot && IM.branched() && P.valid() && P.atBegin())
1946  IM.rootBranchStart() = P.leaf<Leaf>().start(0);
1947  return;
1948  }
1949 
1950  // Erase current entry.
1951  Node.erase(P.leafOffset(), P.leafSize());
1952  unsigned NewSize = P.leafSize() - 1;
1953  P.setSize(IM.height, NewSize);
1954  // When we erase the last entry, update stop and move to a legal position.
1955  if (P.leafOffset() == NewSize) {
1956  setNodeStop(IM.height, Node.stop(NewSize - 1));
1957  P.moveRight(IM.height);
1958  } else if (UpdateRoot && P.atBegin())
1959  IM.rootBranchStart() = P.leaf<Leaf>().start(0);
1960 }
1961 
1962 /// eraseNode - Erase the current node at Level from its parent and move path to
1963 /// the first entry of the next sibling node.
1964 /// The node must be deallocated by the caller.
1965 /// @param Level 1..height, the root node cannot be erased.
1966 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1967 void IntervalMap<KeyT, ValT, N, Traits>::
1968 iterator::eraseNode(unsigned Level) {
1969  assert(Level && "Cannot erase root node");
1970  IntervalMap &IM = *this->map;
1971  IntervalMapImpl::Path &P = this->path;
1972 
1973  if (--Level == 0) {
1974  IM.rootBranch().erase(P.offset(0), IM.rootSize);
1975  P.setSize(0, --IM.rootSize);
1976  // If this cleared the root, switch to height=0.
1977  if (IM.empty()) {
1978  IM.switchRootToLeaf();
1979  this->setRoot(0);
1980  return;
1981  }
1982  } else {
1983  // Remove node ref from branch node at Level.
1984  Branch &Parent = P.node<Branch>(Level);
1985  if (P.size(Level) == 1) {
1986  // Branch node became empty, remove it recursively.
1987  IM.deleteNode(&Parent);
1988  eraseNode(Level);
1989  } else {
1990  // Branch node won't become empty.
1991  Parent.erase(P.offset(Level), P.size(Level));
1992  unsigned NewSize = P.size(Level) - 1;
1993  P.setSize(Level, NewSize);
1994  // If we removed the last branch, update stop and move to a legal pos.
1995  if (P.offset(Level) == NewSize) {
1996  setNodeStop(Level, Parent.stop(NewSize - 1));
1997  P.moveRight(Level);
1998  }
1999  }
2000  }
2001  // Update path cache for the new right sibling position.
2002  if (P.valid()) {
2003  P.reset(Level + 1);
2004  P.offset(Level + 1) = 0;
2005  }
2006 }
2007 
2008 /// overflow - Distribute entries of the current node evenly among
2009 /// its siblings and ensure that the current node is not full.
2010 /// This may require allocating a new node.
2011 /// @tparam NodeT The type of node at Level (Leaf or Branch).
2012 /// @param Level path index of the overflowing node.
2013 /// @return True when the tree height was changed.
2014 template <typename KeyT, typename ValT, unsigned N, typename Traits>
2015 template <typename NodeT>
2016 bool IntervalMap<KeyT, ValT, N, Traits>::
2017 iterator::overflow(unsigned Level) {
2018  using namespace IntervalMapImpl;
2019  Path &P = this->path;
2020  unsigned CurSize[4];
2021  NodeT *Node[4];
2022  unsigned Nodes = 0;
2023  unsigned Elements = 0;
2024  unsigned Offset = P.offset(Level);
2025 
2026  // Do we have a left sibling?
2027  NodeRef LeftSib = P.getLeftSibling(Level);
2028  if (LeftSib) {
2029  Offset += Elements = CurSize[Nodes] = LeftSib.size();
2030  Node[Nodes++] = &LeftSib.get<NodeT>();
2031  }
2032 
2033  // Current node.
2034  Elements += CurSize[Nodes] = P.size(Level);
2035  Node[Nodes++] = &P.node<NodeT>(Level);
2036 
2037  // Do we have a right sibling?
2038  NodeRef RightSib = P.getRightSibling(Level);
2039  if (RightSib) {
2040  Elements += CurSize[Nodes] = RightSib.size();
2041  Node[Nodes++] = &RightSib.get<NodeT>();
2042  }
2043 
2044  // Do we need to allocate a new node?
2045  unsigned NewNode = 0;
2046  if (Elements + 1 > Nodes * NodeT::Capacity) {
2047  // Insert NewNode at the penultimate position, or after a single node.
2048  NewNode = Nodes == 1 ? 1 : Nodes - 1;
2049  CurSize[Nodes] = CurSize[NewNode];
2050  Node[Nodes] = Node[NewNode];
2051  CurSize[NewNode] = 0;
2052  Node[NewNode] = this->map->template newNode<NodeT>();
2053  ++Nodes;
2054  }
2055 
2056  // Compute the new element distribution.
2057  unsigned NewSize[4];
2058  IdxPair NewOffset = distribute(Nodes, Elements, NodeT::Capacity,
2059  CurSize, NewSize, Offset, true);
2060  adjustSiblingSizes(Node, Nodes, CurSize, NewSize);
2061 
2062  // Move current location to the leftmost node.
2063  if (LeftSib)
2064  P.moveLeft(Level);
2065 
2066  // Elements have been rearranged, now update node sizes and stops.
2067  bool SplitRoot = false;
2068  unsigned Pos = 0;
2069  while (true) {
2070  KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1);
2071  if (NewNode && Pos == NewNode) {
2072  SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop);
2073  Level += SplitRoot;
2074  } else {
2075  P.setSize(Level, NewSize[Pos]);
2076  setNodeStop(Level, Stop);
2077  }
2078  if (Pos + 1 == Nodes)
2079  break;
2080  P.moveRight(Level);
2081  ++Pos;
2082  }
2083 
2084  // Where was I? Find NewOffset.
2085  while(Pos != NewOffset.first) {
2086  P.moveLeft(Level);
2087  --Pos;
2088  }
2089  P.offset(Level) = NewOffset.second;
2090  return SplitRoot;
2091 }
2092 
2093 //===----------------------------------------------------------------------===//
2094 //--- IntervalMapOverlaps ----//
2095 //===----------------------------------------------------------------------===//
2096 
2097 /// IntervalMapOverlaps - Iterate over the overlaps of mapped intervals in two
2098 /// IntervalMaps. The maps may be different, but the KeyT and Traits types
2099 /// should be the same.
2100 ///
2101 /// Typical uses:
2102 ///
2103 /// 1. Test for overlap:
2104 /// bool overlap = IntervalMapOverlaps(a, b).valid();
2105 ///
2106 /// 2. Enumerate overlaps:
2107 /// for (IntervalMapOverlaps I(a, b); I.valid() ; ++I) { ... }
2108 ///
2109 template <typename MapA, typename MapB>
2111  using KeyType = typename MapA::KeyType;
2112  using Traits = typename MapA::KeyTraits;
2113 
2114  typename MapA::const_iterator posA;
2115  typename MapB::const_iterator posB;
2116 
2117  /// advance - Move posA and posB forward until reaching an overlap, or until
2118  /// either meets end.
2119  /// Don't move the iterators if they are already overlapping.
2120  void advance() {
2121  if (!valid())
2122  return;
2123 
2124  if (Traits::stopLess(posA.stop(), posB.start())) {
2125  // A ends before B begins. Catch up.
2126  posA.advanceTo(posB.start());
2127  if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
2128  return;
2129  } else if (Traits::stopLess(posB.stop(), posA.start())) {
2130  // B ends before A begins. Catch up.
2131  posB.advanceTo(posA.start());
2132  if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
2133  return;
2134  } else
2135  // Already overlapping.
2136  return;
2137 
2138  while (true) {
2139  // Make a.end > b.start.
2140  posA.advanceTo(posB.start());
2141  if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
2142  return;
2143  // Make b.end > a.start.
2144  posB.advanceTo(posA.start());
2145  if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
2146  return;
2147  }
2148  }
2149 
2150 public:
2151  /// IntervalMapOverlaps - Create an iterator for the overlaps of a and b.
2152  IntervalMapOverlaps(const MapA &a, const MapB &b)
2153  : posA(b.empty() ? a.end() : a.find(b.start())),
2154  posB(posA.valid() ? b.find(posA.start()) : b.end()) { advance(); }
2155 
2156  /// valid - Return true if iterator is at an overlap.
2157  bool valid() const {
2158  return posA.valid() && posB.valid();
2159  }
2160 
2161  /// a - access the left hand side in the overlap.
2162  const typename MapA::const_iterator &a() const { return posA; }
2163 
2164  /// b - access the right hand side in the overlap.
2165  const typename MapB::const_iterator &b() const { return posB; }
2166 
2167  /// start - Beginning of the overlapping interval.
2168  KeyType start() const {
2169  KeyType ak = a().start();
2170  KeyType bk = b().start();
2171  return Traits::startLess(ak, bk) ? bk : ak;
2172  }
2173 
2174  /// stop - End of the overlapping interval.
2175  KeyType stop() const {
2176  KeyType ak = a().stop();
2177  KeyType bk = b().stop();
2178  return Traits::startLess(ak, bk) ? ak : bk;
2179  }
2180 
2181  /// skipA - Move to the next overlap that doesn't involve a().
2182  void skipA() {
2183  ++posA;
2184  advance();
2185  }
2186 
2187  /// skipB - Move to the next overlap that doesn't involve b().
2188  void skipB() {
2189  ++posB;
2190  advance();
2191  }
2192 
2193  /// Preincrement - Move to the next overlap.
2195  // Bump the iterator that ends first. The other one may have more overlaps.
2196  if (Traits::startLess(posB.stop(), posA.stop()))
2197  skipB();
2198  else
2199  skipA();
2200  return *this;
2201  }
2202 
2203  /// advanceTo - Move to the first overlapping interval with
2204  /// stopLess(x, stop()).
2205  void advanceTo(KeyType x) {
2206  if (!valid())
2207  return;
2208  // Make sure advanceTo sees monotonic keys.
2209  if (Traits::stopLess(posA.stop(), x))
2210  posA.advanceTo(x);
2211  if (Traits::stopLess(posB.stop(), x))
2212  posB.advanceTo(x);
2213  advance();
2214  }
2215 };
2216 
2217 } // end namespace llvm
2218 
2219 #endif // LLVM_ADT_INTERVALMAP_H
llvm::IntervalMap::find
iterator find(KeyT x)
Definition: IntervalMap.h:1178
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:1369
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:1186
llvm::IntervalMap::end
iterator end()
Definition: IntervalMap.h:1164
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:1330
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:1129
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:1635
llvm::IntervalMap::const_iterator::stop
const KeyT & stop() const
stop - Return the end of the current interval.
Definition: IntervalMap.h:1419
llvm::PointerIntPair::setInt
void setInt(IntType IntVal) &
Definition: PointerIntPair.h:68
llvm::IntervalMap::~IntervalMap
~IntervalMap()
Definition: IntervalMap.h:1095
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:1424
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
llvm::IntervalMap::operator=
IntervalMap & operator=(IntervalMap &&RHS)
Definition: IntervalMap.h:1069
llvm::IntervalMap::IntervalMap
IntervalMap(IntervalMap &&RHS)
Definition: IntervalMap.h:1063
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:1572
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::AArch64::operator--
ArchKind & operator--(ArchKind &Kind)
Definition: AArch64TargetParser.h:147
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:1152
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:1101
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:1361
llvm::IntervalMap::const_iterator
Definition: IntervalMap.h:1343
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:1533
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::IntervalMap::operator=
IntervalMap & operator=(IntervalMap const &RHS)
Definition: IntervalMap.h:1055
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:1440
llvm::IntervalMap::const_iterator::unsafeValue
ValT & unsafeValue() const
unsafeValue - Writable access to value() for iterator.
Definition: IntervalMap.h:1395
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:1416
llvm::IntervalMap::const_iterator::operator++
const_iterator & operator++()
preincrement - Move to the next interval.
Definition: IntervalMap.h:1452
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::IntervalMap::IntervalMap
IntervalMap(IntervalMap const &RHS)
Definition: IntervalMap.h:1049
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:2157
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:1734
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:1611
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:1106
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:1460
llvm::IntervalMap::leaf
RootLeaf leaf
Definition: IntervalMap.h:970
llvm::IntervalMap::iterator::operator++
iterator operator++(int)
Definition: IntervalMap.h:1640
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:1627
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:1144
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:1447
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:2205
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:1410
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:1407
llvm::IntervalMap::const_iterator::path
IntervalMapImpl::Path path
Definition: IntervalMap.h:1359
llvm::IntervalMap::const_iterator::advanceTo
void advanceTo(KeyT x)
advanceTo - Move to the first interval with stop >= x, or end().
Definition: IntervalMap.h:1494
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::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:1381
uint64_t
llvm::IntervalMapOverlaps::start
KeyType start() const
start - Beginning of the overlapping interval.
Definition: IntervalMap.h:2168
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:1426
llvm::IntervalMap::branchData
RootBranchData branchData
Definition: IntervalMap.h:971
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::IntervalMap::const_iterator::value
const ValT & value() const
value - Return the mapped value at the current interval.
Definition: IntervalMap.h:1422
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
llvm::logicalview::LVPrintKind::Elements
@ Elements
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:1347
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:1119
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:1172
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:2010
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:2152
llvm::IntervalMap::const_iterator::atBegin
bool atBegin() const
atBegin - Return true if the current position is the first map entry.
Definition: IntervalMap.h:1413
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:1690
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:1833
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:1158
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:1467
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:1765
Node
Definition: ItaniumDemangle.h:156
llvm::IntervalMapOverlaps::stop
KeyType stop() const
stop - End of the overlapping interval.
Definition: IntervalMap.h:2175
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:1573
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:2110
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:2182
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:2162
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::IntervalMap::const_iterator::map
IntervalMap * map
Definition: IntervalMap.h:1355
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:2165
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:1484
RecyclingAllocator.h
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:614
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:1651
llvm::IntervalMap::const_iterator::difference_type
std::ptrdiff_t difference_type
Definition: IntervalMap.h:1349
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:1617
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:2188
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:2194
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:1146
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:1142
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:1646
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:1476
llvm::IntervalMap::const_iterator::pathFillFind
void pathFillFind(KeyT x)
pathFillFind - Complete path by searching for x.
Definition: IntervalMap.h:1509
InlinePriorityMode::Size
@ Size
ValT
llvm::SI::KernelInputOffsets::Offsets
Offsets
Offsets in bytes from the start of the input buffer.
Definition: SIInstrInfo.h:1314
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:1388
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:1435
llvm::IntervalMap::iterator::erase
void erase()
erase - Erase the current interval.
Definition: IntervalMap.h:1922
llvm::IntervalMap::const_iterator::treeFind
void treeFind(KeyT x)
treeFind - Find in a branched tree.
Definition: IntervalMap.h:1523
llvm::IntervalMap::const_iterator::branched
bool branched() const
Definition: IntervalMap.h:1364
llvm::IntervalMap::iterator::setStop
void setStop(KeyT b)
setStop - Move the end of the current interval.
Definition: IntervalMap.h:1750
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:1251
llvm::IntervalMap::stop
KeyT stop() const
stop - Return the largest mapped key in a non-empty map.
Definition: IntervalMap.h:1112