IntervalMap.h revision 33fa490c5011b610ccf7b1206bbabb85d9a8cbaa
1//===- llvm/ADT/IntervalMap.h - A sorted interval map -----------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements a coalescing interval map for small objects.
11//
12// KeyT objects are mapped to ValT objects. Intervals of keys that map to the
13// same value are represented in a compressed form.
14//
15// Iterators provide ordered access to the compressed intervals rather than the
16// individual keys, and insert and erase operations use key intervals as well.
17//
18// Like SmallVector, IntervalMap will store the first N intervals in the map
19// object itself without any allocations. When space is exhausted it switches to
20// a B+-tree representation with very small overhead for small key and value
21// objects.
22//
23// A Traits class specifies how keys are compared. It also allows IntervalMap to
24// work with both closed and half-open intervals.
25//
26// Keys and values are not stored next to each other in a std::pair, so we don't
27// provide such a value_type. Dereferencing iterators only returns the mapped
28// value. The interval bounds are accessible through the start() and stop()
29// iterator methods.
30//
31// IntervalMap is optimized for small key and value objects, 4 or 8 bytes each
32// is the optimal size. For large objects use std::map instead.
33//
34//===----------------------------------------------------------------------===//
35//
36// Synopsis:
37//
38// template <typename KeyT, typename ValT, unsigned N, typename Traits>
39// class IntervalMap {
40// public:
41//   typedef KeyT key_type;
42//   typedef ValT mapped_type;
43//   typedef RecyclingAllocator<...> Allocator;
44//   class iterator;
45//   class const_iterator;
46//
47//   explicit IntervalMap(Allocator&);
48//   ~IntervalMap():
49//
50//   bool empty() const;
51//   KeyT start() const;
52//   KeyT stop() const;
53//   ValT lookup(KeyT x, Value NotFound = Value()) const;
54//
55//   const_iterator begin() const;
56//   const_iterator end() const;
57//   iterator begin();
58//   iterator end();
59//   const_iterator find(KeyT x) const;
60//   iterator find(KeyT x);
61//
62//   void insert(KeyT a, KeyT b, ValT y);
63//   void clear();
64// };
65//
66// template <typename KeyT, typename ValT, unsigned N, typename Traits>
67// class IntervalMap::const_iterator :
68//   public std::iterator<std::bidirectional_iterator_tag, ValT> {
69// public:
70//   bool operator==(const const_iterator &) const;
71//   bool operator!=(const const_iterator &) const;
72//   bool valid() const;
73//
74//   const KeyT &start() const;
75//   const KeyT &stop() const;
76//   const ValT &value() const;
77//   const ValT &operator*() const;
78//   const ValT *operator->() const;
79//
80//   const_iterator &operator++();
81//   const_iterator &operator++(int);
82//   const_iterator &operator--();
83//   const_iterator &operator--(int);
84//   void goToBegin();
85//   void goToEnd();
86//   void find(KeyT x);
87//   void advanceTo(KeyT x);
88// };
89//
90// template <typename KeyT, typename ValT, unsigned N, typename Traits>
91// class IntervalMap::iterator : public const_iterator {
92// public:
93//   void insert(KeyT a, KeyT b, Value y);
94//   void erase();
95// };
96//
97//===----------------------------------------------------------------------===//
98
99#ifndef LLVM_ADT_INTERVALMAP_H
100#define LLVM_ADT_INTERVALMAP_H
101
102#include "llvm/ADT/SmallVector.h"
103#include "llvm/ADT/PointerIntPair.h"
104#include "llvm/Support/Allocator.h"
105#include "llvm/Support/RecyclingAllocator.h"
106#include <limits>
107#include <iterator>
108
109// FIXME: Remove debugging code.
110#include "llvm/Support/raw_ostream.h"
111
112namespace llvm {
113
114
115//===----------------------------------------------------------------------===//
116//---                              Key traits                              ---//
117//===----------------------------------------------------------------------===//
118//
119// The IntervalMap works with closed or half-open intervals.
120// Adjacent intervals that map to the same value are coalesced.
121//
122// The IntervalMapInfo traits class is used to determine if a key is contained
123// in an interval, and if two intervals are adjacent so they can be coalesced.
124// The provided implementation works for closed integer intervals, other keys
125// probably need a specialized version.
126//
127// The point x is contained in [a;b] when !startLess(x, a) && !stopLess(b, x).
128//
129// It is assumed that (a;b] half-open intervals are not used, only [a;b) is
130// allowed. This is so that stopLess(a, b) can be used to determine if two
131// intervals overlap.
132//
133//===----------------------------------------------------------------------===//
134
135template <typename T>
136struct IntervalMapInfo {
137
138  /// startLess - Return true if x is not in [a;b].
139  /// This is x < a both for closed intervals and for [a;b) half-open intervals.
140  static inline bool startLess(const T &x, const T &a) {
141    return x < a;
142  }
143
144  /// stopLess - Return true if x is not in [a;b].
145  /// This is b < x for a closed interval, b <= x for [a;b) half-open intervals.
146  static inline bool stopLess(const T &b, const T &x) {
147    return b < x;
148  }
149
150  /// adjacent - Return true when the intervals [x;a] and [b;y] can coalesce.
151  /// This is a+1 == b for closed intervals, a == b for half-open intervals.
152  static inline bool adjacent(const T &a, const T &b) {
153    return a+1 == b;
154  }
155
156};
157
158/// IntervalMapImpl - Namespace used for IntervalMap implementation details.
159/// It should be considered private to the implementation.
160namespace IntervalMapImpl {
161
162// Forward declarations.
163template <typename, typename, unsigned, typename> class LeafNode;
164template <typename, typename, unsigned, typename> class BranchNode;
165
166typedef std::pair<unsigned,unsigned> IdxPair;
167
168
169//===----------------------------------------------------------------------===//
170//---                            Node Storage                              ---//
171//===----------------------------------------------------------------------===//
172//
173// Both leaf and branch nodes store vectors of (key,value) pairs.
174// Leaves store ((KeyT, KeyT), ValT) pairs, branches use (KeyT, NodeRef).
175//
176// Keys and values are stored in separate arrays to avoid padding caused by
177// different object alignments. This also helps improve locality of reference
178// when searching the keys.
179//
180// The nodes don't know how many elements they contain - that information is
181// stored elsewhere. Omitting the size field prevents padding and allows a node
182// to fill the allocated cache lines completely.
183//
184// These are typical key and value sizes, the node branching factor (N), and
185// wasted space when nodes are sized to fit in three cache lines (192 bytes):
186//
187//   KT  VT   N Waste  Used by
188//    4   4  24   0    Branch<4> (32-bit pointers)
189//    4   8  16   0    Branch<4>
190//    8   4  16   0    Leaf<4,4>
191//    8   8  12   0    Leaf<4,8>, Branch<8>
192//   16   4   9  12    Leaf<8,4>
193//   16   8   8   0    Leaf<8,8>
194//
195//===----------------------------------------------------------------------===//
196
197template <typename KT, typename VT, unsigned N>
198class NodeBase {
199public:
200  enum { Capacity = N };
201
202  KT key[N];
203  VT val[N];
204
205  /// copy - Copy elements from another node.
206  /// @param Other Node elements are copied from.
207  /// @param i     Beginning of the source range in other.
208  /// @param j     Beginning of the destination range in this.
209  /// @param Count Number of elements to copy.
210  template <unsigned M>
211  void copy(const NodeBase<KT, VT, M> &Other, unsigned i,
212            unsigned j, unsigned Count) {
213    assert(i + Count <= M && "Invalid source range");
214    assert(j + Count <= N && "Invalid dest range");
215    std::copy(Other.key + i, Other.key + i + Count, key + j);
216    std::copy(Other.val + i, Other.val + i + Count, val + j);
217  }
218
219  /// moveLeft - Move elements to the left.
220  /// @param i     Beginning of the source range.
221  /// @param j     Beginning of the destination range.
222  /// @param Count Number of elements to copy.
223  void moveLeft(unsigned i, unsigned j, unsigned Count) {
224    assert(j <= i && "Use moveRight shift elements right");
225    copy(*this, i, j, Count);
226  }
227
228  /// moveRight - Move elements to the right.
229  /// @param i     Beginning of the source range.
230  /// @param j     Beginning of the destination range.
231  /// @param Count Number of elements to copy.
232  void moveRight(unsigned i, unsigned j, unsigned Count) {
233    assert(i <= j && "Use moveLeft shift elements left");
234    assert(j + Count <= N && "Invalid range");
235    std::copy_backward(key + i, key + i + Count, key + j + Count);
236    std::copy_backward(val + i, val + i + Count, val + j + Count);
237  }
238
239  /// erase - Erase elements [i;j).
240  /// @param i    Beginning of the range to erase.
241  /// @param j    End of the range. (Exclusive).
242  /// @param Size Number of elements in node.
243  void erase(unsigned i, unsigned j, unsigned Size) {
244    moveLeft(j, i, Size - j);
245  }
246
247  /// shift - Shift elements [i;size) 1 position to the right.
248  /// @param i    Beginning of the range to move.
249  /// @param Size Number of elements in node.
250  void shift(unsigned i, unsigned Size) {
251    moveRight(i, i + 1, Size - i);
252  }
253
254  /// transferToLeftSib - Transfer elements to a left sibling node.
255  /// @param Size  Number of elements in this.
256  /// @param Sib   Left sibling node.
257  /// @param SSize Number of elements in sib.
258  /// @param Count Number of elements to transfer.
259  void transferToLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize,
260                         unsigned Count) {
261    Sib.copy(*this, 0, SSize, Count);
262    erase(0, Count, Size);
263  }
264
265  /// transferToRightSib - Transfer elements to a right sibling node.
266  /// @param Size  Number of elements in this.
267  /// @param Sib   Right sibling node.
268  /// @param SSize Number of elements in sib.
269  /// @param Count Number of elements to transfer.
270  void transferToRightSib(unsigned Size, NodeBase &Sib, unsigned SSize,
271                          unsigned Count) {
272    Sib.moveRight(0, Count, SSize);
273    Sib.copy(*this, Size-Count, 0, Count);
274  }
275
276  /// adjustFromLeftSib - Adjust the number if elements in this node by moving
277  /// elements to or from a left sibling node.
278  /// @param Size  Number of elements in this.
279  /// @param Sib   Right sibling node.
280  /// @param SSize Number of elements in sib.
281  /// @param Add   The number of elements to add to this node, possibly < 0.
282  /// @return      Number of elements added to this node, possibly negative.
283  int adjustFromLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add) {
284    if (Add > 0) {
285      // We want to grow, copy from sib.
286      unsigned Count = std::min(std::min(unsigned(Add), SSize), N - Size);
287      Sib.transferToRightSib(SSize, *this, Size, Count);
288      return Count;
289    } else {
290      // We want to shrink, copy to sib.
291      unsigned Count = std::min(std::min(unsigned(-Add), Size), N - SSize);
292      transferToLeftSib(Size, Sib, SSize, Count);
293      return -Count;
294    }
295  }
296};
297
298
299//===----------------------------------------------------------------------===//
300//---                             NodeSizer                                ---//
301//===----------------------------------------------------------------------===//
302//
303// Compute node sizes from key and value types.
304//
305// The branching factors are chosen to make nodes fit in three cache lines.
306// This may not be possible if keys or values are very large. Such large objects
307// are handled correctly, but a std::map would probably give better performance.
308//
309//===----------------------------------------------------------------------===//
310
311enum {
312  // Cache line size. Most architectures have 32 or 64 byte cache lines.
313  // We use 64 bytes here because it provides good branching factors.
314  Log2CacheLine = 6,
315  CacheLineBytes = 1 << Log2CacheLine,
316  DesiredNodeBytes = 3 * CacheLineBytes
317};
318
319template <typename KeyT, typename ValT>
320struct NodeSizer {
321  enum {
322    // Compute the leaf node branching factor that makes a node fit in three
323    // cache lines. The branching factor must be at least 3, or some B+-tree
324    // balancing algorithms won't work.
325    // LeafSize can't be larger than CacheLineBytes. This is required by the
326    // PointerIntPair used by NodeRef.
327    DesiredLeafSize = DesiredNodeBytes /
328      static_cast<unsigned>(2*sizeof(KeyT)+sizeof(ValT)),
329    MinLeafSize = 3,
330    LeafSize = DesiredLeafSize > MinLeafSize ? DesiredLeafSize : MinLeafSize
331  };
332
333  typedef NodeBase<std::pair<KeyT, KeyT>, ValT, LeafSize> LeafBase;
334
335  enum {
336    // Now that we have the leaf branching factor, compute the actual allocation
337    // unit size by rounding up to a whole number of cache lines.
338    AllocBytes = (sizeof(LeafBase) + CacheLineBytes-1) & ~(CacheLineBytes-1),
339
340    // Determine the branching factor for branch nodes.
341    BranchSize = AllocBytes /
342      static_cast<unsigned>(sizeof(KeyT) + sizeof(void*))
343  };
344
345  /// Allocator - The recycling allocator used for both branch and leaf nodes.
346  /// This typedef is very likely to be identical for all IntervalMaps with
347  /// reasonably sized entries, so the same allocator can be shared among
348  /// different kinds of maps.
349  typedef RecyclingAllocator<BumpPtrAllocator, char,
350                             AllocBytes, CacheLineBytes> Allocator;
351
352};
353
354
355//===----------------------------------------------------------------------===//
356//---                              NodeRef                                 ---//
357//===----------------------------------------------------------------------===//
358//
359// B+-tree nodes can be leaves or branches, so we need a polymorphic node
360// pointer that can point to both kinds.
361//
362// All nodes are cache line aligned and the low 6 bits of a node pointer are
363// always 0. These bits are used to store the number of elements in the
364// referenced node. Besides saving space, placing node sizes in the parents
365// allow tree balancing algorithms to run without faulting cache lines for nodes
366// that may not need to be modified.
367//
368// A NodeRef doesn't know whether it references a leaf node or a branch node.
369// It is the responsibility of the caller to use the correct types.
370//
371// Nodes are never supposed to be empty, and it is invalid to store a node size
372// of 0 in a NodeRef. The valid range of sizes is 1-64.
373//
374//===----------------------------------------------------------------------===//
375
376struct CacheAlignedPointerTraits {
377  static inline void *getAsVoidPointer(void *P) { return P; }
378  static inline void *getFromVoidPointer(void *P) { return P; }
379  enum { NumLowBitsAvailable = Log2CacheLine };
380};
381
382template <typename KeyT, typename ValT, typename Traits>
383class NodeRef {
384public:
385  typedef LeafNode<KeyT, ValT, NodeSizer<KeyT, ValT>::LeafSize, Traits> Leaf;
386  typedef BranchNode<KeyT, ValT, NodeSizer<KeyT, ValT>::BranchSize,
387                     Traits> Branch;
388
389private:
390  PointerIntPair<void*, Log2CacheLine, unsigned, CacheAlignedPointerTraits> pip;
391
392public:
393  /// NodeRef - Create a null ref.
394  NodeRef() {}
395
396  /// operator bool - Detect a null ref.
397  operator bool() const { return pip.getOpaqueValue(); }
398
399  /// NodeRef - Create a reference to the leaf node p with n elements.
400  NodeRef(Leaf *p, unsigned n) : pip(p, n - 1) {}
401
402  /// NodeRef - Create a reference to the branch node p with n elements.
403  NodeRef(Branch *p, unsigned n) : pip(p, n - 1) {}
404
405  /// size - Return the number of elements in the referenced node.
406  unsigned size() const { return pip.getInt() + 1; }
407
408  /// setSize - Update the node size.
409  void setSize(unsigned n) { pip.setInt(n - 1); }
410
411  /// leaf - Return the referenced leaf node.
412  /// Note there are no dynamic type checks.
413  Leaf &leaf() const {
414    return *reinterpret_cast<Leaf*>(pip.getPointer());
415  }
416
417  /// branch - Return the referenced branch node.
418  /// Note there are no dynamic type checks.
419  Branch &branch() const {
420    return *reinterpret_cast<Branch*>(pip.getPointer());
421  }
422
423  bool operator==(const NodeRef &RHS) const {
424    if (pip == RHS.pip)
425      return true;
426    assert(pip.getPointer() != RHS.pip.getPointer() && "Inconsistent NodeRefs");
427    return false;
428  }
429
430  bool operator!=(const NodeRef &RHS) const {
431    return !operator==(RHS);
432  }
433};
434
435//===----------------------------------------------------------------------===//
436//---                            Leaf nodes                                ---//
437//===----------------------------------------------------------------------===//
438//
439// Leaf nodes store up to N disjoint intervals with corresponding values.
440//
441// The intervals are kept sorted and fully coalesced so there are no adjacent
442// intervals mapping to the same value.
443//
444// These constraints are always satisfied:
445//
446// - Traits::stopLess(key[i].start, key[i].stop) - Non-empty, sane intervals.
447//
448// - Traits::stopLess(key[i].stop, key[i + 1].start) - Sorted.
449//
450// - val[i] != val[i + 1] ||
451//     !Traits::adjacent(key[i].stop, key[i + 1].start) - Fully coalesced.
452//
453//===----------------------------------------------------------------------===//
454
455template <typename KeyT, typename ValT, unsigned N, typename Traits>
456class LeafNode : public NodeBase<std::pair<KeyT, KeyT>, ValT, N> {
457public:
458  const KeyT &start(unsigned i) const { return this->key[i].first; }
459  const KeyT &stop(unsigned i) const { return this->key[i].second; }
460  const ValT &value(unsigned i) const { return this->val[i]; }
461
462  KeyT &start(unsigned i) { return this->key[i].first; }
463  KeyT &stop(unsigned i) { return this->key[i].second; }
464  ValT &value(unsigned i) { return this->val[i]; }
465
466  /// findFrom - Find the first interval after i that may contain x.
467  /// @param i    Starting index for the search.
468  /// @param Size Number of elements in node.
469  /// @param x    Key to search for.
470  /// @return     First index with !stopLess(key[i].stop, x), or size.
471  ///             This is the first interval that can possibly contain x.
472  unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
473    assert(i <= Size && Size <= N && "Bad indices");
474    assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
475           "Index is past the needed point");
476    while (i != Size && Traits::stopLess(stop(i), x)) ++i;
477    return i;
478  }
479
480  /// safeFind - Find an interval that is known to exist. This is the same as
481  /// findFrom except is it assumed that x is at least within range of the last
482  /// interval.
483  /// @param i Starting index for the search.
484  /// @param x Key to search for.
485  /// @return  First index with !stopLess(key[i].stop, x), never size.
486  ///          This is the first interval that can possibly contain x.
487  unsigned safeFind(unsigned i, KeyT x) const {
488    assert(i < N && "Bad index");
489    assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
490           "Index is past the needed point");
491    while (Traits::stopLess(stop(i), x)) ++i;
492    assert(i < N && "Unsafe intervals");
493    return i;
494  }
495
496  /// safeLookup - Lookup mapped value for a safe key.
497  /// It is assumed that x is within range of the last entry.
498  /// @param x        Key to search for.
499  /// @param NotFound Value to return if x is not in any interval.
500  /// @return         The mapped value at x or NotFound.
501  ValT safeLookup(KeyT x, ValT NotFound) const {
502    unsigned i = safeFind(0, x);
503    return Traits::startLess(x, start(i)) ? NotFound : value(i);
504  }
505
506  IdxPair insertFrom(unsigned i, unsigned Size, KeyT a, KeyT b, ValT y);
507  unsigned extendStop(unsigned i, unsigned Size, KeyT b);
508
509#ifndef NDEBUG
510  void dump(unsigned Size) {
511    errs() << "  N" << this << " [shape=record label=\"{ " << Size << '/' << N;
512    for (unsigned i = 0; i != Size; ++i)
513      errs() << " | {" << start(i) << '-' << stop(i) << "|" << value(i) << '}';
514    errs() << "}\"];\n";
515  }
516#endif
517
518};
519
520/// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as
521/// possible. This may cause the node to grow by 1, or it may cause the node
522/// to shrink because of coalescing.
523/// @param i    Starting index = insertFrom(0, size, a)
524/// @param Size Number of elements in node.
525/// @param a    Interval start.
526/// @param b    Interval stop.
527/// @param y    Value be mapped.
528/// @return     (insert position, new size), or (i, Capacity+1) on overflow.
529template <typename KeyT, typename ValT, unsigned N, typename Traits>
530IdxPair LeafNode<KeyT, ValT, N, Traits>::
531insertFrom(unsigned i, unsigned Size, KeyT a, KeyT b, ValT y) {
532  assert(i <= Size && Size <= N && "Invalid index");
533  assert(!Traits::stopLess(b, a) && "Invalid interval");
534
535  // Verify the findFrom invariant.
536  assert((i == 0 || Traits::stopLess(stop(i - 1), a)));
537  assert((i == Size || !Traits::stopLess(stop(i), a)));
538
539  // Coalesce with previous interval.
540  if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a))
541    return IdxPair(i - 1, extendStop(i - 1, Size, b));
542
543  // Detect overflow.
544  if (i == N)
545    return IdxPair(i, N + 1);
546
547  // Add new interval at end.
548  if (i == Size) {
549    start(i) = a;
550    stop(i) = b;
551    value(i) = y;
552    return IdxPair(i, Size + 1);
553  }
554
555  // Overlapping intervals?
556  if (!Traits::stopLess(b, start(i))) {
557    assert(value(i) == y && "Inconsistent values in overlapping intervals");
558    if (Traits::startLess(a, start(i)))
559      start(i) = a;
560    return IdxPair(i, extendStop(i, Size, b));
561  }
562
563  // Try to coalesce with following interval.
564  if (value(i) == y && Traits::adjacent(b, start(i))) {
565    start(i) = a;
566    return IdxPair(i, Size);
567  }
568
569  // We must insert before i. Detect overflow.
570  if (Size == N)
571    return IdxPair(i, N + 1);
572
573  // Insert before i.
574  this->shift(i, Size);
575  start(i) = a;
576  stop(i) = b;
577  value(i) = y;
578  return IdxPair(i, Size + 1);
579}
580
581/// extendStop - Extend stop(i) to b, coalescing with following intervals.
582/// @param i    Interval to extend.
583/// @param Size Number of elements in node.
584/// @param b    New interval end point.
585/// @return     New node size after coalescing.
586template <typename KeyT, typename ValT, unsigned N, typename Traits>
587unsigned LeafNode<KeyT, ValT, N, Traits>::
588extendStop(unsigned i, unsigned Size, KeyT b) {
589  assert(i < Size && Size <= N && "Bad indices");
590
591  // Are we even extending the interval?
592  if (Traits::startLess(b, stop(i)))
593    return Size;
594
595  // Find the first interval that may be preserved.
596  unsigned j = findFrom(i + 1, Size, b);
597  if (j < Size) {
598    // Would key[i] overlap key[j] after the extension?
599    if (Traits::stopLess(b, start(j))) {
600      // Not overlapping. Perhaps adjacent and coalescable?
601      if (value(i) == value(j) && Traits::adjacent(b, start(j)))
602        b = stop(j++);
603    } else {
604      // Overlap. Include key[j] in the new interval.
605      assert(value(i) == value(j) && "Overlapping values");
606      b = stop(j++);
607    }
608  }
609  stop(i) =  b;
610
611  // Entries [i+1;j) were coalesced.
612  if (i + 1 < j && j < Size)
613    this->erase(i + 1, j, Size);
614  return Size - (j - (i + 1));
615}
616
617
618//===----------------------------------------------------------------------===//
619//---                             Branch nodes                             ---//
620//===----------------------------------------------------------------------===//
621//
622// A branch node stores references to 1--N subtrees all of the same height.
623//
624// The key array in a branch node holds the rightmost stop key of each subtree.
625// It is redundant to store the last stop key since it can be found in the
626// parent node, but doing so makes tree balancing a lot simpler.
627//
628// It is unusual for a branch node to only have one subtree, but it can happen
629// in the root node if it is smaller than the normal nodes.
630//
631// When all of the leaf nodes from all the subtrees are concatenated, they must
632// satisfy the same constraints as a single leaf node. They must be sorted,
633// sane, and fully coalesced.
634//
635//===----------------------------------------------------------------------===//
636
637template <typename KeyT, typename ValT, unsigned N, typename Traits>
638class BranchNode : public NodeBase<KeyT, NodeRef<KeyT, ValT, Traits>, N> {
639  typedef  NodeRef<KeyT, ValT, Traits> NodeRefT;
640public:
641  const KeyT &stop(unsigned i) const { return this->key[i]; }
642  const NodeRefT &subtree(unsigned i) const { return this->val[i]; }
643
644  KeyT &stop(unsigned i) { return this->key[i]; }
645  NodeRefT &subtree(unsigned i) { return this->val[i]; }
646
647  /// findFrom - Find the first subtree after i that may contain x.
648  /// @param i    Starting index for the search.
649  /// @param Size Number of elements in node.
650  /// @param x    Key to search for.
651  /// @return     First index with !stopLess(key[i], x), or size.
652  ///             This is the first subtree that can possibly contain x.
653  unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
654    assert(i <= Size && Size <= N && "Bad indices");
655    assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
656           "Index to findFrom is past the needed point");
657    while (i != Size && Traits::stopLess(stop(i), x)) ++i;
658    return i;
659  }
660
661  /// safeFind - Find a subtree that is known to exist. This is the same as
662  /// findFrom except is it assumed that x is in range.
663  /// @param i Starting index for the search.
664  /// @param x Key to search for.
665  /// @return  First index with !stopLess(key[i], x), never size.
666  ///          This is the first subtree that can possibly contain x.
667  unsigned safeFind(unsigned i, KeyT x) const {
668    assert(i < N && "Bad index");
669    assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
670           "Index is past the needed point");
671    while (Traits::stopLess(stop(i), x)) ++i;
672    assert(i < N && "Unsafe intervals");
673    return i;
674  }
675
676  /// safeLookup - Get the subtree containing x, Assuming that x is in range.
677  /// @param x Key to search for.
678  /// @return  Subtree containing x
679  NodeRefT safeLookup(KeyT x) const {
680    return subtree(safeFind(0, x));
681  }
682
683  /// insert - Insert a new (subtree, stop) pair.
684  /// @param i    Insert position, following entries will be shifted.
685  /// @param Size Number of elements in node.
686  /// @param Node Subtree to insert.
687  /// @param Stop Last key in subtree.
688  void insert(unsigned i, unsigned Size, NodeRefT Node, KeyT Stop) {
689    assert(Size < N && "branch node overflow");
690    assert(i <= Size && "Bad insert position");
691    this->shift(i, Size);
692    subtree(i) = Node;
693    stop(i) = Stop;
694  }
695
696#ifndef NDEBUG
697  void dump(unsigned Size) {
698    errs() << "  N" << this << " [shape=record label=\"" << Size << '/' << N;
699    for (unsigned i = 0; i != Size; ++i)
700      errs() << " | <s" << i << "> " << stop(i);
701    errs() << "\"];\n";
702    for (unsigned i = 0; i != Size; ++i)
703      errs() << "  N" << this << ":s" << i << " -> N"
704             << &subtree(i).branch() << ";\n";
705  }
706#endif
707
708};
709
710} // namespace IntervalMapImpl
711
712
713//===----------------------------------------------------------------------===//
714//---                          IntervalMap                                ----//
715//===----------------------------------------------------------------------===//
716
717template <typename KeyT, typename ValT,
718          unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize,
719          typename Traits = IntervalMapInfo<KeyT> >
720class IntervalMap {
721  typedef IntervalMapImpl::NodeRef<KeyT, ValT, Traits> NodeRef;
722  typedef IntervalMapImpl::NodeSizer<KeyT, ValT> NodeSizer;
723  typedef typename NodeRef::Leaf Leaf;
724  typedef typename NodeRef::Branch Branch;
725  typedef IntervalMapImpl::LeafNode<KeyT, ValT, N, Traits> RootLeaf;
726  typedef IntervalMapImpl::IdxPair IdxPair;
727
728  // The RootLeaf capacity is given as a template parameter. We must compute the
729  // corresponding RootBranch capacity.
730  enum {
731    DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) /
732      (sizeof(KeyT) + sizeof(NodeRef)),
733    RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1
734  };
735
736  typedef IntervalMapImpl::BranchNode<KeyT, ValT, RootBranchCap, Traits> RootBranch;
737
738  // When branched, we store a global start key as well as the branch node.
739  struct RootBranchData {
740    KeyT start;
741    RootBranch node;
742  };
743
744  enum {
745    RootDataSize = sizeof(RootBranchData) > sizeof(RootLeaf) ?
746                   sizeof(RootBranchData) : sizeof(RootLeaf)
747  };
748
749public:
750  typedef typename NodeSizer::Allocator Allocator;
751
752private:
753  // The root data is either a RootLeaf or a RootBranchData instance.
754  // We can't put them in a union since C++03 doesn't allow non-trivial
755  // constructors in unions.
756  // Instead, we use a char array with pointer alignment. The alignment is
757  // ensured by the allocator member in the class, but still verified in the
758  // constructor. We don't support keys or values that are more aligned than a
759  // pointer.
760  char data[RootDataSize];
761
762  // Tree height.
763  // 0: Leaves in root.
764  // 1: Root points to leaf.
765  // 2: root->branch->leaf ...
766  unsigned height;
767
768  // Number of entries in the root node.
769  unsigned rootSize;
770
771  // Allocator used for creating external nodes.
772  Allocator &allocator;
773
774  /// dataAs - Represent data as a node type without breaking aliasing rules.
775  template <typename T>
776  T &dataAs() const {
777    union {
778      const char *d;
779      T *t;
780    } u;
781    u.d = data;
782    return *u.t;
783  }
784
785  const RootLeaf &rootLeaf() const {
786    assert(!branched() && "Cannot acces leaf data in branched root");
787    return dataAs<RootLeaf>();
788  }
789  RootLeaf &rootLeaf() {
790    assert(!branched() && "Cannot acces leaf data in branched root");
791    return dataAs<RootLeaf>();
792  }
793  RootBranchData &rootBranchData() const {
794    assert(branched() && "Cannot access branch data in non-branched root");
795    return dataAs<RootBranchData>();
796  }
797  RootBranchData &rootBranchData() {
798    assert(branched() && "Cannot access branch data in non-branched root");
799    return dataAs<RootBranchData>();
800  }
801  const RootBranch &rootBranch() const { return rootBranchData().node; }
802  RootBranch &rootBranch()             { return rootBranchData().node; }
803  KeyT rootBranchStart() const { return rootBranchData().start; }
804  KeyT &rootBranchStart()      { return rootBranchData().start; }
805
806  Leaf *allocLeaf()  {
807    return new(allocator.template Allocate<Leaf>()) Leaf();
808  }
809  void freeLeaf(Leaf *P) {
810    P->~Leaf();
811    allocator.Deallocate(P);
812  }
813
814  Branch *allocBranch() {
815    return new(allocator.template Allocate<Branch>()) Branch();
816  }
817  void freeBranch(Branch *P) {
818    P->~Branch();
819    allocator.Deallocate(P);
820  }
821
822
823  IdxPair branchRoot(unsigned Position);
824  IdxPair splitRoot(unsigned Position);
825
826  void switchRootToBranch() {
827    rootLeaf().~RootLeaf();
828    height = 1;
829    new (&rootBranchData()) RootBranchData();
830  }
831
832  void switchRootToLeaf() {
833    rootBranchData().~RootBranchData();
834    height = 0;
835    new(&rootLeaf()) RootLeaf();
836  }
837
838  bool branched() const { return height > 0; }
839
840  ValT treeSafeLookup(KeyT x, ValT NotFound) const;
841
842  void visitNodes(void (IntervalMap::*f)(NodeRef, unsigned Level));
843
844public:
845  explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) {
846    assert((uintptr_t(data) & (alignOf<RootLeaf>() - 1)) == 0 &&
847           "Insufficient alignment");
848    new(&rootLeaf()) RootLeaf();
849  }
850
851  /// empty -  Return true when no intervals are mapped.
852  bool empty() const {
853    return rootSize == 0;
854  }
855
856  /// start - Return the smallest mapped key in a non-empty map.
857  KeyT start() const {
858    assert(!empty() && "Empty IntervalMap has no start");
859    return !branched() ? rootLeaf().start(0) : rootBranchStart();
860  }
861
862  /// stop - Return the largest mapped key in a non-empty map.
863  KeyT stop() const {
864    assert(!empty() && "Empty IntervalMap has no stop");
865    return !branched() ? rootLeaf().stop(rootSize - 1) :
866                         rootBranch().stop(rootSize - 1);
867  }
868
869  /// lookup - Return the mapped value at x or NotFound.
870  ValT lookup(KeyT x, ValT NotFound = ValT()) const {
871    if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x))
872      return NotFound;
873    return branched() ? treeSafeLookup(x, NotFound) :
874                        rootLeaf().safeLookup(x, NotFound);
875  }
876
877  /// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
878  /// It is assumed that no key in the interval is mapped to another value, but
879  /// overlapping intervals already mapped to y will be coalesced.
880  void insert(KeyT a, KeyT b, ValT y) {
881    find(a).insert(a, b, y);
882  }
883
884  class const_iterator;
885  class iterator;
886  friend class const_iterator;
887  friend class iterator;
888
889  const_iterator begin() const {
890    iterator I(*this);
891    I.goToBegin();
892    return I;
893  }
894
895  iterator begin() {
896    iterator I(*this);
897    I.goToBegin();
898    return I;
899  }
900
901  const_iterator end() const {
902    iterator I(*this);
903    I.goToEnd();
904    return I;
905  }
906
907  iterator end() {
908    iterator I(*this);
909    I.goToEnd();
910    return I;
911  }
912
913  /// find - Return an iterator pointing to the first interval ending at or
914  /// after x, or end().
915  const_iterator find(KeyT x) const {
916    iterator I(*this);
917    I.find(x);
918    return I;
919  }
920
921  iterator find(KeyT x) {
922    iterator I(*this);
923    I.find(x);
924    return I;
925  }
926
927#ifndef NDEBUG
928  void dump();
929  void dumpNode(NodeRef Node, unsigned Height);
930#endif
931};
932
933/// treeSafeLookup - Return the mapped value at x or NotFound, assuming a
934/// branched root.
935template <typename KeyT, typename ValT, unsigned N, typename Traits>
936ValT IntervalMap<KeyT, ValT, N, Traits>::
937treeSafeLookup(KeyT x, ValT NotFound) const {
938  assert(branched() && "treeLookup assumes a branched root");
939
940  NodeRef NR = rootBranch().safeLookup(x);
941  for (unsigned h = height-1; h; --h)
942    NR = NR.branch().safeLookup(x);
943  return NR.leaf().safeLookup(x, NotFound);
944}
945
946
947// branchRoot - Switch from a leaf root to a branched root.
948// Return the new (root offset, node offset) corresponding to Position.
949template <typename KeyT, typename ValT, unsigned N, typename Traits>
950IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
951branchRoot(unsigned Position) {
952  // How many external leaf nodes to hold RootLeaf+1?
953  const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1;
954
955  // Compute element distribution among new nodes.
956  unsigned size[Nodes];
957  IdxPair NewOffset(0, Position);
958
959  // Is is very common for the root node to be smaller than external nodes.
960  if (Nodes == 1)
961    size[0] = rootSize;
962  else
963    NewOffset = distribute(Nodes, rootSize, Leaf::Capacity,  NULL, size,
964                           Position, true);
965
966  // Allocate new nodes.
967  unsigned pos = 0;
968  NodeRef node[Nodes];
969  for (unsigned n = 0; n != Nodes; ++n) {
970    node[n] = NodeRef(allocLeaf(), size[n]);
971    node[n].leaf().copy(rootLeaf(), pos, 0, size[n]);
972    pos += size[n];
973  }
974
975  // Destroy the old leaf node, construct branch node instead.
976  switchRootToBranch();
977  for (unsigned n = 0; n != Nodes; ++n) {
978    rootBranch().stop(n) = node[n].leaf().stop(size[n]-1);
979    rootBranch().subtree(n) = node[n];
980  }
981  rootBranchStart() = node[0].leaf().start(0);
982  rootSize = Nodes;
983  return NewOffset;
984}
985
986// splitRoot - Split the current BranchRoot into multiple Branch nodes.
987// Return the new (root offset, node offset) corresponding to Position.
988template <typename KeyT, typename ValT, unsigned N, typename Traits>
989IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
990splitRoot(unsigned Position) {
991  // How many external leaf nodes to hold RootBranch+1?
992  const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1;
993
994  // Compute element distribution among new nodes.
995  unsigned Size[Nodes];
996  IdxPair NewOffset(0, Position);
997
998  // Is is very common for the root node to be smaller than external nodes.
999  if (Nodes == 1)
1000    Size[0] = rootSize;
1001  else
1002    NewOffset = distribute(Nodes, rootSize, Leaf::Capacity,  NULL, Size,
1003                           Position, true);
1004
1005  // Allocate new nodes.
1006  unsigned Pos = 0;
1007  NodeRef Node[Nodes];
1008  for (unsigned n = 0; n != Nodes; ++n) {
1009    Node[n] = NodeRef(allocBranch(), Size[n]);
1010    Node[n].branch().copy(rootBranch(), Pos, 0, Size[n]);
1011    Pos += Size[n];
1012  }
1013
1014  for (unsigned n = 0; n != Nodes; ++n) {
1015    rootBranch().stop(n) = Node[n].branch().stop(Size[n]-1);
1016    rootBranch().subtree(n) = Node[n];
1017  }
1018  rootSize = Nodes;
1019  return NewOffset;
1020}
1021
1022/// visitNodes - Visit each external node.
1023template <typename KeyT, typename ValT, unsigned N, typename Traits>
1024void IntervalMap<KeyT, ValT, N, Traits>::
1025visitNodes(void (IntervalMap::*f)(NodeRef, unsigned Height)) {
1026  if (!branched())
1027    return;
1028  SmallVector<NodeRef, 4> Refs, NextRefs;
1029
1030  // Collect level 0 nodes from the root.
1031  for (unsigned i = 0; i != rootSize; ++i)
1032    Refs.push_back(rootBranch().subtree(i));
1033
1034  // Visit all branch nodes.
1035  for (unsigned h = height - 1; h; --h) {
1036    for (unsigned i = 0, e = Refs.size(); i != e; ++i) {
1037      Branch &B = Refs[i].branch();
1038      for (unsigned j = 0, s = Refs[i].size(); j != s; ++j)
1039        NextRefs.push_back(B.subtree(j));
1040      (this->*f)(Refs[i], h);
1041    }
1042    Refs.clear();
1043    Refs.swap(NextRefs);
1044  }
1045
1046  // Visit all leaf nodes.
1047  for (unsigned i = 0, e = Refs.size(); i != e; ++i)
1048    (this->*f)(Refs[i], 0);
1049}
1050
1051#ifndef NDEBUG
1052template <typename KeyT, typename ValT, unsigned N, typename Traits>
1053void IntervalMap<KeyT, ValT, N, Traits>::
1054dumpNode(NodeRef Node, unsigned Height) {
1055  if (Height)
1056    Node.branch().dump(Node.size());
1057  else
1058    Node.leaf().dump(Node.size());
1059}
1060
1061template <typename KeyT, typename ValT, unsigned N, typename Traits>
1062void IntervalMap<KeyT, ValT, N, Traits>::
1063dump() {
1064  errs() << "digraph {\n";
1065  if (branched())
1066    rootBranch().dump(rootSize);
1067  else
1068    rootLeaf().dump(rootSize);
1069  visitNodes(&IntervalMap::dumpNode);
1070  errs() << "}\n";
1071}
1072#endif
1073
1074//===----------------------------------------------------------------------===//
1075//---                             const_iterator                          ----//
1076//===----------------------------------------------------------------------===//
1077
1078template <typename KeyT, typename ValT, unsigned N, typename Traits>
1079class IntervalMap<KeyT, ValT, N, Traits>::const_iterator :
1080  public std::iterator<std::bidirectional_iterator_tag, ValT> {
1081protected:
1082  friend class IntervalMap;
1083  typedef std::pair<NodeRef, unsigned> PathEntry;
1084  typedef SmallVector<PathEntry, 4> Path;
1085
1086  // The map referred to.
1087  IntervalMap *map;
1088
1089  // The offset into map's root node.
1090  unsigned rootOffset;
1091
1092  // We store a full path from the root to the current position.
1093  //
1094  // When rootOffset == map->rootSize, we are at end() and path() is empty.
1095  // Otherwise, when branched these conditions hold:
1096  //
1097  // 1. path.front().first == rootBranch().subtree(rootOffset)
1098  // 2. path[i].first == path[i-1].first.branch().subtree(path[i-1].second)
1099  // 3. path.size() == map->height.
1100  //
1101  // Thus, path.back() always refers to the current leaf node unless the root is
1102  // unbranched.
1103  //
1104  // The path may be partially filled, but never between iterator calls.
1105  Path path;
1106
1107  explicit const_iterator(IntervalMap &map)
1108    : map(&map), rootOffset(map.rootSize) {}
1109
1110  bool branched() const {
1111    assert(map && "Invalid iterator");
1112    return map->branched();
1113  }
1114
1115  NodeRef   pathNode(unsigned h)   const { return path[h].first; }
1116  NodeRef  &pathNode(unsigned h)         { return path[h].first; }
1117  unsigned  pathOffset(unsigned h) const { return path[h].second; }
1118  unsigned &pathOffset(unsigned h)       { return path[h].second; }
1119
1120  Leaf &treeLeaf() const {
1121    assert(branched() && path.size() == map->height);
1122    return path.back().first.leaf();
1123  }
1124  unsigned treeLeafSize() const {
1125    assert(branched() && path.size() == map->height);
1126    return path.back().first.size();
1127  }
1128  unsigned &treeLeafOffset() {
1129    assert(branched() && path.size() == map->height);
1130    return path.back().second;
1131  }
1132  unsigned treeLeafOffset() const {
1133    assert(branched() && path.size() == map->height);
1134    return path.back().second;
1135  }
1136
1137  // Get the next node ptr for an incomplete path.
1138  NodeRef pathNextDown() {
1139    assert(path.size() < map->height && "Path is already complete");
1140
1141    if (path.empty())
1142      return map->rootBranch().subtree(rootOffset);
1143    else
1144      return path.back().first.branch().subtree(path.back().second);
1145  }
1146
1147  void pathFillLeft();
1148  void pathFillFind(KeyT x);
1149  void pathFillRight();
1150
1151  NodeRef leftSibling(unsigned level) const;
1152  NodeRef rightSibling(unsigned level) const;
1153
1154  void treeIncrement();
1155  void treeDecrement();
1156  void treeFind(KeyT x);
1157
1158public:
1159  /// valid - Return true if the current position is valid, false for end().
1160  bool valid() const {
1161    assert(map && "Invalid iterator");
1162    return rootOffset < map->rootSize;
1163  }
1164
1165  /// start - Return the beginning of the current interval.
1166  const KeyT &start() const {
1167    assert(valid() && "Cannot access invalid iterator");
1168    return branched() ? treeLeaf().start(treeLeafOffset()) :
1169                        map->rootLeaf().start(rootOffset);
1170  }
1171
1172  /// stop - Return the end of the current interval.
1173  const KeyT &stop() const {
1174    assert(valid() && "Cannot access invalid iterator");
1175    return branched() ? treeLeaf().stop(treeLeafOffset()) :
1176                        map->rootLeaf().stop(rootOffset);
1177  }
1178
1179  /// value - Return the mapped value at the current interval.
1180  const ValT &value() const {
1181    assert(valid() && "Cannot access invalid iterator");
1182    return branched() ? treeLeaf().value(treeLeafOffset()) :
1183                        map->rootLeaf().value(rootOffset);
1184  }
1185
1186  const ValT &operator*() const {
1187    return value();
1188  }
1189
1190  bool operator==(const const_iterator &RHS) const {
1191    assert(map == RHS.map && "Cannot compare iterators from different maps");
1192    return rootOffset == RHS.rootOffset &&
1193             (!valid() || !branched() || path.back() == RHS.path.back());
1194  }
1195
1196  bool operator!=(const const_iterator &RHS) const {
1197    return !operator==(RHS);
1198  }
1199
1200  /// goToBegin - Move to the first interval in map.
1201  void goToBegin() {
1202    rootOffset = 0;
1203    path.clear();
1204    if (branched())
1205      pathFillLeft();
1206  }
1207
1208  /// goToEnd - Move beyond the last interval in map.
1209  void goToEnd() {
1210    rootOffset = map->rootSize;
1211    path.clear();
1212  }
1213
1214  /// preincrement - move to the next interval.
1215  const_iterator &operator++() {
1216    assert(valid() && "Cannot increment end()");
1217    if (!branched())
1218      ++rootOffset;
1219    else if (treeLeafOffset() != treeLeafSize() - 1)
1220      ++treeLeafOffset();
1221    else
1222      treeIncrement();
1223    return *this;
1224  }
1225
1226  /// postincrement - Dont do that!
1227  const_iterator operator++(int) {
1228    const_iterator tmp = *this;
1229    operator++();
1230    return tmp;
1231  }
1232
1233  /// predecrement - move to the previous interval.
1234  const_iterator &operator--() {
1235    if (!branched()) {
1236      assert(rootOffset && "Cannot decrement begin()");
1237      --rootOffset;
1238    } else if (treeLeafOffset())
1239      --treeLeafOffset();
1240    else
1241      treeDecrement();
1242    return *this;
1243  }
1244
1245  /// postdecrement - Dont do that!
1246  const_iterator operator--(int) {
1247    const_iterator tmp = *this;
1248    operator--();
1249    return tmp;
1250  }
1251
1252  /// find - Move to the first interval with stop >= x, or end().
1253  /// This is a full search from the root, the current position is ignored.
1254  void find(KeyT x) {
1255    if (branched())
1256      treeFind(x);
1257    else
1258      rootOffset = map->rootLeaf().findFrom(0, map->rootSize, x);
1259  }
1260
1261  /// advanceTo - Move to the first interval with stop >= x, or end().
1262  /// The search is started from the current position, and no earlier positions
1263  /// can be found. This is much faster than find() for small moves.
1264  void advanceTo(KeyT x) {
1265    if (branched())
1266      treeAdvanceTo(x);
1267    else
1268      rootOffset = map->rootLeaf().findFrom(rootOffset, map->rootSize, x);
1269  }
1270
1271};
1272
1273// pathFillLeft - Complete path by following left-most branches.
1274template <typename KeyT, typename ValT, unsigned N, typename Traits>
1275void IntervalMap<KeyT, ValT, N, Traits>::
1276const_iterator::pathFillLeft() {
1277  NodeRef NR = pathNextDown();
1278  for (unsigned i = map->height - path.size() - 1; i; --i) {
1279    path.push_back(PathEntry(NR, 0));
1280    NR = NR.branch().subtree(0);
1281  }
1282  path.push_back(PathEntry(NR, 0));
1283}
1284
1285// pathFillFind - Complete path by searching for x.
1286template <typename KeyT, typename ValT, unsigned N, typename Traits>
1287void IntervalMap<KeyT, ValT, N, Traits>::
1288const_iterator::pathFillFind(KeyT x) {
1289  NodeRef NR = pathNextDown();
1290  for (unsigned i = map->height - path.size() - 1; i; --i) {
1291    unsigned p = NR.branch().safeFind(0, x);
1292    path.push_back(PathEntry(NR, p));
1293    NR = NR.branch().subtree(p);
1294  }
1295  path.push_back(PathEntry(NR, NR.leaf().safeFind(0, x)));
1296}
1297
1298// pathFillRight - Complete path by adding rightmost entries.
1299template <typename KeyT, typename ValT, unsigned N, typename Traits>
1300void IntervalMap<KeyT, ValT, N, Traits>::
1301const_iterator::pathFillRight() {
1302  NodeRef NR = pathNextDown();
1303  for (unsigned i = map->height - path.size() - 1; i; --i) {
1304    unsigned p = NR.size() - 1;
1305    path.push_back(PathEntry(NR, p));
1306    NR = NR.branch().subtree(p);
1307  }
1308  path.push_back(PathEntry(NR, NR.size() - 1));
1309}
1310
1311/// leftSibling - find the left sibling node to path[level].
1312/// @param level 0 is just below the root, map->height - 1 for the leaves.
1313/// @return The left sibling NodeRef, or NULL.
1314template <typename KeyT, typename ValT, unsigned N, typename Traits>
1315typename IntervalMap<KeyT, ValT, N, Traits>::NodeRef
1316IntervalMap<KeyT, ValT, N, Traits>::
1317const_iterator::leftSibling(unsigned level) const {
1318  assert(branched() && "Not at a branched node");
1319  assert(level <= path.size() && "Bad level");
1320
1321  // Go up the tree until we can go left.
1322  unsigned h = level;
1323  while (h && pathOffset(h - 1) == 0)
1324    --h;
1325
1326  // We are at the first leaf node, no left sibling.
1327  if (!h && rootOffset == 0)
1328    return NodeRef();
1329
1330  // NR is the subtree containing our left sibling.
1331  NodeRef NR = h ?
1332    pathNode(h - 1).branch().subtree(pathOffset(h - 1) - 1) :
1333    map->rootBranch().subtree(rootOffset - 1);
1334
1335  // Keep right all the way down.
1336  for (; h != level; ++h)
1337    NR = NR.branch().subtree(NR.size() - 1);
1338  return NR;
1339}
1340
1341/// rightSibling - find the right sibling node to path[level].
1342/// @param level 0 is just below the root, map->height - 1 for the leaves.
1343/// @return The right sibling NodeRef, or NULL.
1344template <typename KeyT, typename ValT, unsigned N, typename Traits>
1345typename IntervalMap<KeyT, ValT, N, Traits>::NodeRef
1346IntervalMap<KeyT, ValT, N, Traits>::
1347const_iterator::rightSibling(unsigned level) const {
1348  assert(branched() && "Not at a branched node");
1349  assert(level <= this->path.size() && "Bad level");
1350
1351  // Go up the tree until we can go right.
1352  unsigned h = level;
1353  while (h && pathOffset(h - 1) == pathNode(h - 1).size() - 1)
1354    --h;
1355
1356  // We are at the last leaf node, no right sibling.
1357  if (!h && rootOffset == map->rootSize - 1)
1358    return NodeRef();
1359
1360  // NR is the subtree containing our right sibling.
1361  NodeRef NR = h ?
1362    pathNode(h - 1).branch().subtree(pathOffset(h - 1) + 1) :
1363    map->rootBranch().subtree(rootOffset + 1);
1364
1365  // Keep left all the way down.
1366  for (; h != level; ++h)
1367    NR = NR.branch().subtree(0);
1368  return NR;
1369}
1370
1371// treeIncrement - Move to the beginning of the next leaf node.
1372template <typename KeyT, typename ValT, unsigned N, typename Traits>
1373void IntervalMap<KeyT, ValT, N, Traits>::
1374const_iterator::treeIncrement() {
1375  assert(branched() && "treeIncrement is not for small maps");
1376  assert(path.size() == map->height && "inconsistent iterator");
1377  do path.pop_back();
1378  while (!path.empty() && path.back().second == path.back().first.size() - 1);
1379  if (path.empty()) {
1380    ++rootOffset;
1381    if (!valid())
1382      return;
1383  } else
1384    ++path.back().second;
1385  pathFillLeft();
1386}
1387
1388// treeDecrement - Move to the end of the previous leaf node.
1389template <typename KeyT, typename ValT, unsigned N, typename Traits>
1390void IntervalMap<KeyT, ValT, N, Traits>::
1391const_iterator::treeDecrement() {
1392  assert(branched() && "treeDecrement is not for small maps");
1393  if (valid()) {
1394    assert(path.size() == map->height && "inconsistent iterator");
1395    do path.pop_back();
1396    while (!path.empty() && path.back().second == 0);
1397  }
1398  if (path.empty()) {
1399    assert(rootOffset && "cannot treeDecrement() on begin()");
1400    --rootOffset;
1401  } else
1402    --path.back().second;
1403  pathFillRight();
1404}
1405
1406// treeFind - Find in a branched tree.
1407template <typename KeyT, typename ValT, unsigned N, typename Traits>
1408void IntervalMap<KeyT, ValT, N, Traits>::
1409const_iterator::treeFind(KeyT x) {
1410  path.clear();
1411  rootOffset = map->rootBranch().findFrom(0, map->rootSize, x);
1412  if (valid())
1413    pathFillFind(x);
1414}
1415
1416
1417//===----------------------------------------------------------------------===//
1418//---                                iterator                             ----//
1419//===----------------------------------------------------------------------===//
1420
1421namespace IntervalMapImpl {
1422
1423  /// distribute - Compute a new distribution of node elements after an overflow
1424  /// or underflow. Reserve space for a new element at Position, and compute the
1425  /// node that will hold Position after redistributing node elements.
1426  ///
1427  /// It is required that
1428  ///
1429  ///   Elements == sum(CurSize), and
1430  ///   Elements + Grow <= Nodes * Capacity.
1431  ///
1432  /// NewSize[] will be filled in such that:
1433  ///
1434  ///   sum(NewSize) == Elements, and
1435  ///   NewSize[i] <= Capacity.
1436  ///
1437  /// The returned index is the node where Position will go, so:
1438  ///
1439  ///   sum(NewSize[0..idx-1]) <= Position
1440  ///   sum(NewSize[0..idx])   >= Position
1441  ///
1442  /// The last equality, sum(NewSize[0..idx]) == Position, can only happen when
1443  /// Grow is set and NewSize[idx] == Capacity-1. The index points to the node
1444  /// before the one holding the Position'th element where there is room for an
1445  /// insertion.
1446  ///
1447  /// @param Nodes    The number of nodes.
1448  /// @param Elements Total elements in all nodes.
1449  /// @param Capacity The capacity of each node.
1450  /// @param CurSize  Array[Nodes] of current node sizes, or NULL.
1451  /// @param NewSize  Array[Nodes] to receive the new node sizes.
1452  /// @param Position Insert position.
1453  /// @param Grow     Reserve space for a new element at Position.
1454  /// @return         (node, offset) for Position.
1455  IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,
1456                     const unsigned *CurSize, unsigned NewSize[],
1457                     unsigned Position, bool Grow);
1458
1459}
1460
1461template <typename KeyT, typename ValT, unsigned N, typename Traits>
1462class IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator {
1463  friend class IntervalMap;
1464  typedef IntervalMapImpl::IdxPair IdxPair;
1465
1466  explicit iterator(IntervalMap &map) : const_iterator(map) {}
1467
1468  void setNodeSize(unsigned Level, unsigned Size);
1469  void setNodeStop(unsigned Level, KeyT Stop);
1470  void insertNode(unsigned Level, NodeRef Node, KeyT Stop);
1471  void overflowLeaf();
1472  void treeInsert(KeyT a, KeyT b, ValT y);
1473
1474public:
1475  /// insert - Insert mapping [a;b] -> y before the current position.
1476  void insert(KeyT a, KeyT b, ValT y);
1477
1478};
1479
1480/// setNodeSize - Set the size of the node at path[level], updating both path
1481/// and the real tree.
1482/// @param level 0 is just below the root, map->height - 1 for the leaves.
1483/// @param size  New node size.
1484template <typename KeyT, typename ValT, unsigned N, typename Traits>
1485void IntervalMap<KeyT, ValT, N, Traits>::
1486iterator::setNodeSize(unsigned Level, unsigned Size) {
1487  this->pathNode(Level).setSize(Size);
1488  if (Level)
1489    this->pathNode(Level-1).branch()
1490      .subtree(this->pathOffset(Level-1)).setSize(Size);
1491  else
1492    this->map->rootBranch().subtree(this->rootOffset).setSize(Size);
1493}
1494
1495/// setNodeStop - Update the stop key of the current node at level and above.
1496template <typename KeyT, typename ValT, unsigned N, typename Traits>
1497void IntervalMap<KeyT, ValT, N, Traits>::
1498iterator::setNodeStop(unsigned Level, KeyT Stop) {
1499  while (Level--) {
1500    this->pathNode(Level).branch().stop(this->pathOffset(Level)) = Stop;
1501    if (this->pathOffset(Level) != this->pathNode(Level).size() - 1)
1502      return;
1503  }
1504  this->map->rootBranch().stop(this->rootOffset) = Stop;
1505}
1506
1507/// insertNode - insert a node before the current path at level.
1508/// Leave the current path pointing at the new node.
1509template <typename KeyT, typename ValT, unsigned N, typename Traits>
1510void IntervalMap<KeyT, ValT, N, Traits>::
1511iterator::insertNode(unsigned Level, NodeRef Node, KeyT Stop) {
1512  if (!Level) {
1513    // Insert into the root branch node.
1514    IntervalMap &IM = *this->map;
1515    if (IM.rootSize < RootBranch::Capacity) {
1516      IM.rootBranch().insert(this->rootOffset, IM.rootSize, Node, Stop);
1517      ++IM.rootSize;
1518      return;
1519    }
1520
1521    // We need to split the root while keeping our position.
1522    IdxPair Offset = IM.splitRoot(this->rootOffset);
1523    this->rootOffset = Offset.first;
1524    this->path.insert(this->path.begin(),std::make_pair(
1525      this->map->rootBranch().subtree(Offset.first), Offset.second));
1526    Level = 1;
1527  }
1528
1529  // When inserting before end(), make sure we have a valid path.
1530  if (!this->valid()) {
1531    this->treeDecrement();
1532    ++this->pathOffset(Level-1);
1533  }
1534
1535  // Insert into the branch node at level-1.
1536  NodeRef NR = this->pathNode(Level-1);
1537  unsigned Offset = this->pathOffset(Level-1);
1538  assert(NR.size() < Branch::Capacity && "Branch overflow");
1539  NR.branch().insert(Offset, NR.size(), Node, Stop);
1540  setNodeSize(Level - 1, NR.size() + 1);
1541}
1542
1543// insert
1544template <typename KeyT, typename ValT, unsigned N, typename Traits>
1545void IntervalMap<KeyT, ValT, N, Traits>::
1546iterator::insert(KeyT a, KeyT b, ValT y) {
1547  if (this->branched())
1548    return treeInsert(a, b, y);
1549  IdxPair IP = this->map->rootLeaf().insertFrom(this->rootOffset,
1550                                                this->map->rootSize,
1551                                                a, b, y);
1552  if (IP.second <= RootLeaf::Capacity) {
1553    this->rootOffset = IP.first;
1554    this->map->rootSize = IP.second;
1555    return;
1556  }
1557  IdxPair Offset = this->map->branchRoot(this->rootOffset);
1558  this->rootOffset = Offset.first;
1559  this->path.push_back(std::make_pair(
1560    this->map->rootBranch().subtree(Offset.first), Offset.second));
1561  treeInsert(a, b, y);
1562}
1563
1564
1565template <typename KeyT, typename ValT, unsigned N, typename Traits>
1566void IntervalMap<KeyT, ValT, N, Traits>::
1567iterator::treeInsert(KeyT a, KeyT b, ValT y) {
1568  if (!this->valid()) {
1569    // end() has an empty path. Go back to the last leaf node and use an
1570    // invalid offset instead.
1571    this->treeDecrement();
1572    ++this->treeLeafOffset();
1573  }
1574  IdxPair IP = this->treeLeaf().insertFrom(this->treeLeafOffset(),
1575                                           this->treeLeafSize(), a, b, y);
1576  this->treeLeafOffset() = IP.first;
1577  if (IP.second <= Leaf::Capacity) {
1578    setNodeSize(this->map->height - 1, IP.second);
1579    if (IP.first == IP.second - 1)
1580      setNodeStop(this->map->height - 1, this->treeLeaf().stop(IP.first));
1581    return;
1582  }
1583  // Leaf node has no space.
1584  overflowLeaf();
1585  IP = this->treeLeaf().insertFrom(this->treeLeafOffset(),
1586                                   this->treeLeafSize(), a, b, y);
1587  this->treeLeafOffset() = IP.first;
1588  setNodeSize(this->map->height-1, IP.second);
1589  if (IP.first == IP.second - 1)
1590    setNodeStop(this->map->height - 1, this->treeLeaf().stop(IP.first));
1591
1592  // FIXME: Handle cross-node coalescing.
1593}
1594
1595// overflowLeaf - Distribute entries of the current leaf node evenly among
1596// its siblings and ensure that the current node is not full.
1597// This may require allocating a new node.
1598template <typename KeyT, typename ValT, unsigned N, typename Traits>
1599void IntervalMap<KeyT, ValT, N, Traits>::
1600iterator::overflowLeaf() {
1601  unsigned CurSize[4];
1602  Leaf *Node[4];
1603  unsigned Nodes = 0;
1604  unsigned Elements = 0;
1605  unsigned Offset = this->treeLeafOffset();
1606
1607  // Do we have a left sibling?
1608  NodeRef LeftSib = this->leftSibling(this->map->height-1);
1609  if (LeftSib) {
1610    Offset += Elements = CurSize[Nodes] = LeftSib.size();
1611    Node[Nodes++] = &LeftSib.leaf();
1612  }
1613
1614  // Current leaf node.
1615  Elements += CurSize[Nodes] = this->treeLeafSize();
1616  Node[Nodes++] = &this->treeLeaf();
1617
1618  // Do we have a right sibling?
1619  NodeRef RightSib = this->rightSibling(this->map->height-1);
1620  if (RightSib) {
1621    Offset += Elements = CurSize[Nodes] = RightSib.size();
1622    Node[Nodes++] = &RightSib.leaf();
1623  }
1624
1625  // Do we need to allocate a new node?
1626  unsigned NewNode = 0;
1627  if (Elements + 1 > Nodes * Leaf::Capacity) {
1628    // Insert NewNode at the penultimate position, or after a single node.
1629    NewNode = Nodes == 1 ? 1 : Nodes - 1;
1630    CurSize[Nodes] = CurSize[NewNode];
1631    Node[Nodes] = Node[NewNode];
1632    CurSize[NewNode] = 0;
1633    Node[NewNode] = this->map->allocLeaf();
1634    ++Nodes;
1635  }
1636
1637  // Compute the new element distribution.
1638  unsigned NewSize[4];
1639  IdxPair NewOffset =
1640    IntervalMapImpl::distribute(Nodes, Elements, Leaf::Capacity,
1641                                CurSize, NewSize, Offset, true);
1642
1643  // Move current location to the leftmost node.
1644  if (LeftSib)
1645    this->treeDecrement();
1646
1647  // Move elements right.
1648  for (int n = Nodes - 1; n; --n) {
1649    if (CurSize[n] == NewSize[n])
1650      continue;
1651    for (int m = n - 1; m != -1; --m) {
1652      int d = Node[n]->adjustFromLeftSib(CurSize[n], *Node[m], CurSize[m],
1653                                        NewSize[n] - CurSize[n]);
1654      CurSize[m] -= d;
1655      CurSize[n] += d;
1656      // Keep going if the current node was exhausted.
1657      if (CurSize[n] >= NewSize[n])
1658          break;
1659    }
1660  }
1661
1662  // Move elements left.
1663  for (unsigned n = 0; n != Nodes - 1; ++n) {
1664    if (CurSize[n] == NewSize[n])
1665      continue;
1666    for (unsigned m = n + 1; m != Nodes; ++m) {
1667      int d = Node[m]->adjustFromLeftSib(CurSize[m], *Node[n], CurSize[n],
1668                                        CurSize[n] -  NewSize[n]);
1669      CurSize[m] += d;
1670      CurSize[n] -= d;
1671      // Keep going if the current node was exhausted.
1672      if (CurSize[n] >= NewSize[n])
1673          break;
1674    }
1675  }
1676
1677#ifndef NDEBUG
1678  for (unsigned n = 0; n != Nodes; n++)
1679    assert(CurSize[n] == NewSize[n] && "Insufficient element shuffle");
1680#endif
1681
1682  // Elements have been rearranged, now update node sizes and stops.
1683  unsigned Pos = 0;
1684  for (;;) {
1685    KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1);
1686    if (NewNode && Pos == NewNode)
1687      insertNode(this->map->height - 1, NodeRef(Node[Pos], NewSize[Pos]), Stop);
1688    else {
1689      setNodeSize(this->map->height - 1, NewSize[Pos]);
1690      setNodeStop(this->map->height - 1, Stop);
1691    }
1692    if (Pos + 1 == Nodes)
1693      break;
1694    this->treeIncrement();
1695    ++Pos;
1696  }
1697
1698  // Where was I? Find NewOffset.
1699  while(Pos != NewOffset.first) {
1700    this->treeDecrement();
1701    --Pos;
1702  }
1703  this->treeLeafOffset() = NewOffset.second;
1704}
1705
1706} // namespace llvm
1707
1708#endif
1709