Revert "Add ADT/IntervalMap.", GCC doesn't like it.

This reverts r119772.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119773 91177308-0d34-0410-b5e6-96231b3b80d8

5 files changed, 0 insertions, 2114 deletions

diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h
deleted file mode 100644
index e38789b763..0000000000
--- a/include/llvm/ADT/IntervalMap.h
+++ /dev/null
@@ -1,1695 +0,0 @@
-//===- llvm/ADT/IntervalMap.h - A sorted interval map -----------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file implements a coalescing interval map for small objects.
-//
-// KeyT objects are mapped to ValT objects. Intervals of keys that map to the
-// same value are represented in a compressed form.
-//
-// Iterators provide ordered access to the compressed intervals rather than the
-// individual keys, and insert and erase operations use key intervals as well.
-//
-// Like SmallVector, IntervalMap will store the first N intervals in the map
-// object itself without any allocations. When space is exhausted it switches to
-// a B+-tree representation with very small overhead for small key and value
-// objects.
-//
-// A Traits class specifies how keys are compared. It also allows IntervalMap to
-// work with both closed and half-open intervals.
-//
-// Keys and values are not stored next to each other in a std::pair, so we don't
-// provide such a value_type. Dereferencing iterators only returns the mapped
-// value. The interval bounds are accessible through the start() and stop()
-// iterator methods.
-//
-// IntervalMap is optimized for small key and value objects, 4 or 8 bytes each
-// is the optimal size. For large objects use std::map instead.
-//
-//===----------------------------------------------------------------------===//
-//
-// Synopsis:
-//
-// template <typename KeyT, typename ValT, unsigned N, typename Traits>
-// class IntervalMap {
-// public:
-//   typedef KeyT key_type;
-//   typedef ValT mapped_type;
-//   typedef RecyclingAllocator<...> Allocator;
-//   class iterator;
-//   class const_iterator;
-//
-//   explicit IntervalMap(Allocator&);
-//   ~IntervalMap():
-//
-//   bool empty() const;
-//   KeyT start() const;
-//   KeyT stop() const;
-//   ValT lookup(KeyT x, Value NotFound = Value()) const;
-//
-//   const_iterator begin() const;
-//   const_iterator end() const;
-//   iterator begin();
-//   iterator end();
-//   const_iterator find(KeyT x) const;
-//   iterator find(KeyT x);
-//
-//   void insert(KeyT a, KeyT b, ValT y);
-//   void clear();
-// };
-//
-// template <typename KeyT, typename ValT, unsigned N, typename Traits>
-// class IntervalMap::const_iterator :
-//   public std::iterator<std::bidirectional_iterator_tag, ValT> {
-// public:
-//   bool operator==(const const_iterator &) const;
-//   bool operator!=(const const_iterator &) const;
-//   bool valid() const;
-//
-//   const KeyT &start() const;
-//   const KeyT &stop() const;
-//   const ValT &value() const;
-//   const ValT &operator*() const;
-//   const ValT *operator->() const;
-//
-//   const_iterator &operator++();
-//   const_iterator &operator++(int);
-//   const_iterator &operator--();
-//   const_iterator &operator--(int);
-//   void goToBegin();
-//   void goToEnd();
-//   void find(KeyT x);
-//   void advanceTo(KeyT x);
-// };
-//
-// template <typename KeyT, typename ValT, unsigned N, typename Traits>
-// class IntervalMap::iterator : public const_iterator {
-// public:
-//   void insert(KeyT a, KeyT b, Value y);
-//   void erase();
-// };
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ADT_INTERVALMAP_H
-#define LLVM_ADT_INTERVALMAP_H
-
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/PointerIntPair.h"
-#include "llvm/Support/Allocator.h"
-#include "llvm/Support/RecyclingAllocator.h"
-#include <limits>
-#include <iterator>
-
-// FIXME: Remove debugging code
-#ifndef NDEBUG
-#include "llvm/Support/raw_ostream.h"
-#endif
-
-namespace llvm {
-
-
-//===----------------------------------------------------------------------===//
-//---                              Key traits                              ---//
-//===----------------------------------------------------------------------===//
-//
-// The IntervalMap works with closed or half-open intervals.
-// Adjacent intervals that map to the same value are coalesced.
-//
-// The IntervalMapInfo traits class is used to determine if a key is contained
-// in an interval, and if two intervals are adjacent so they can be coalesced.
-// The provided implementation works for closed integer intervals, other keys
-// probably need a specialized version.
-//
-// The point x is contained in [a;b] when !startLess(x, a) && !stopLess(b, x).
-//
-// It is assumed that (a;b] half-open intervals are not used, only [a;b) is
-// allowed. This is so that stopLess(a, b) can be used to determine if two
-// intervals overlap.
-//
-//===----------------------------------------------------------------------===//
-
-template <typename T>
-struct IntervalMapInfo {
-
-  /// startLess - Return true if x is not in [a;b].
-  /// This is x < a both for closed intervals and for [a;b) half-open intervals.
-  static inline bool startLess(const T &x, const T &a) {
-    return x < a;
-  }
-
-  /// stopLess - Return true if x is not in [a;b].
-  /// This is b < x for a closed interval, b <= x for [a;b) half-open intervals.
-  static inline bool stopLess(const T &b, const T &x) {
-    return b < x;
-  }
-
-  /// adjacent - Return true when the intervals [x;a] and [b;y] can coalesce.
-  /// This is a+1 == b for closed intervals, a == b for half-open intervals.
-  static inline bool adjacent(const T &a, const T &b) {
-    return a+1 == b;
-  }
-
-};
-
-/// IntervalMapImpl - Namespace used for IntervalMap implementation details.
-/// It should be considered private to the implementation.
-namespace IntervalMapImpl {
-
-// Forward declarations.
-template <typename, typename, unsigned, typename> class Leaf;
-template <typename, typename, unsigned, typename> class Branch;
-
-typedef std::pair<unsigned,unsigned> IdxPair;
-
-
-//===----------------------------------------------------------------------===//
-//---                            Node Storage                              ---//
-//===----------------------------------------------------------------------===//
-//
-// Both leaf and branch nodes store vectors of (key,value) pairs.
-// Leaves store ((KeyT, KeyT), ValT) pairs, branches use (KeyT, NodeRef).
-//
-// Keys and values are stored in separate arrays to avoid padding caused by
-// different object alignments. This also helps improve locality of reference
-// when searching the keys.
-//
-// The nodes don't know how many elements they contain - that information is
-// stored elsewhere. Omitting the size field prevents padding and allows a node
-// to fill the allocated cache lines completely.
-//
-// These are typical key and value sizes, the node branching factor (N), and
-// wasted space when nodes are sized to fit in three cache lines (192 bytes):
-//
-//   KT  VT   N Waste  Used by
-//    4   4  24   0    Branch<4> (32-bit pointers)
-//    4   8  16   0    Branch<4>
-//    8   4  16   0    Leaf<4,4>
-//    8   8  12   0    Leaf<4,8>, Branch<8>
-//   16   4   9  12    Leaf<8,4>
-//   16   8   8   0    Leaf<8,8>
-//
-//===----------------------------------------------------------------------===//
-
-template <typename KT, typename VT, unsigned N>
-class NodeBase {
-public:
-  enum { Capacity = N };
-
-  KT key[N];
-  VT val[N];
-
-  /// copy - Copy elements from another node.
-  /// @param other Node elements are copied from.
-  /// @param i     Beginning of the source range in other.
-  /// @param j     Beginning of the destination range in this.
-  /// @param count Number of elements to copy.
-  template <unsigned M>
-  void copy(const NodeBase<KT, VT, M> &Other, unsigned i,
-            unsigned j, unsigned Count) {
-    assert(i + Count <= M && "Invalid source range");
-    assert(j + Count <= N && "Invalid dest range");
-    std::copy(Other.key + i, Other.key + i + Count, key + j);
-    std::copy(Other.val + i, Other.val + i + Count, val + j);
-  }
-
-  /// lmove - Move elements to the left.
-  /// @param i     Beginning of the source range.
-  /// @param j     Beginning of the destination range.
-  /// @param count Number of elements to copy.
-  void lmove(unsigned i, unsigned j, unsigned Count) {
-    assert(j <= i && "Use rmove shift elements right");
-    copy(*this, i, j, Count);
-  }
-
-  /// rmove - Move elements to the right.
-  /// @param i     Beginning of the source range.
-  /// @param j     Beginning of the destination range.
-  /// @param count Number of elements to copy.
-  void rmove(unsigned i, unsigned j, unsigned Count) {
-    assert(i <= j && "Use lmove shift elements left");
-    assert(j + Count <= N && "Invalid range");
-    std::copy_backward(key + i, key + i + Count, key + j + Count);
-    std::copy_backward(val + i, val + i + Count, val + j + Count);
-  }
-
-  /// erase - Erase elements [i;j).
-  /// @param i    Beginning of the range to erase.
-  /// @param j    End of the range. (Exclusive).
-  /// @param size Number of elements in node.
-  void erase(unsigned i, unsigned j, unsigned Size) {
-    lmove(j, i, Size - j);
-  }
-
-  /// shift - Shift elements [i;size) 1 position to the right.
-  /// @param i    Beginning of the range to move.
-  /// @param size Number of elements in node.
-  void shift(unsigned i, unsigned Size) {
-    rmove(i, i + 1, Size - i);
-  }
-
-  /// xferLeft - Transfer elements to a left sibling node.
-  /// @param size  Number of elements in this.
-  /// @param sib   Left sibling node.
-  /// @param ssize Number of elements in sib.
-  /// @param count Number of elements to transfer.
-  void xferLeft(unsigned Size, NodeBase &Sib, unsigned SSize, unsigned Count) {
-    Sib.copy(*this, 0, SSize, Count);
-    erase(0, Count, Size);
-  }
-
-  /// xferRight - Transfer elements to a right sibling node.
-  /// @param size  Number of elements in this.
-  /// @param sib   Right sibling node.
-  /// @param ssize Number of elements in sib.
-  /// @param count Number of elements to transfer.
-  void xferRight(unsigned Size, NodeBase &Sib, unsigned SSize, unsigned Count) {
-    Sib.rmove(0, Count, SSize);
-    Sib.copy(*this, Size-Count, 0, Count);
-  }
-
-  /// adjLeftSib - Adjust the number if elements in this node by moving
-  /// elements to or from a left sibling node.
-  /// @param size  Number of elements in this.
-  /// @param sib   Right sibling node.
-  /// @param ssize Number of elements in sib.
-  /// @param add   The number of elements to add to this node, possibly < 0.
-  /// @return      Number of elements added to this node, possibly negative.
-  int adjLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add) {
-    if (Add > 0) {
-      // We want to grow, copy from sib.
-      unsigned Count = std::min(std::min(unsigned(Add), SSize), N - Size);
-      Sib.xferRight(SSize, *this, Size, Count);
-      return Count;
-    } else {
-      // We want to shrink, copy to sib.
-      unsigned Count = std::min(std::min(unsigned(-Add), Size), N - SSize);
-      xferLeft(Size, Sib, SSize, Count);
-      return -Count;
-    }
-  }
-};
-
-
-//===----------------------------------------------------------------------===//
-//---                             NodeSizer                                ---//
-//===----------------------------------------------------------------------===//
-//
-// Compute node sizes from key and value types.
-//
-// The branching factors are chosen to make nodes fit in three cache lines.
-// This may not be possible if keys or values are very large. Such large objects
-// are handled correctly, but a std::map would probably give better performance.
-//
-//===----------------------------------------------------------------------===//
-
-template <typename KeyT, typename ValT>
-struct NodeSizer {
-  enum {
-    // Cache line size. Most architectures have 32 or 64 byte cache lines.
-    // We use 64 bytes here because it provides good branching factors.
-    Log2CacheLine = 6,
-    CacheLineBytes = 1 << Log2CacheLine,
-
-    // Compute the leaf node branching factor that makes a node fit in three
-    // cache lines. The branching factor must be at least 3, or some B+-tree
-    // balancing algorithms won't work.
-    // LeafSize can't be larger than CacheLineBytes. This is required by the
-    // PointerIntPair used by NodeRef.
-    DesiredNodeBytes = 3 * CacheLineBytes,
-    DesiredLeafSize = DesiredNodeBytes / (2*sizeof(KeyT)+sizeof(ValT)),
-    LeafSize = DesiredLeafSize > 3 ? DesiredLeafSize : 3,
-
-    // Now that we have the leaf branching factor, compute the actual allocation
-    // unit size by rounding up to a whole number of cache lines.
-    LeafBytes = sizeof(NodeBase<std::pair<KeyT, KeyT>, ValT, LeafSize>),
-    AllocBytes = (LeafBytes + CacheLineBytes-1) & ~(CacheLineBytes-1),
-
-    // Determine the branching factor for branch nodes, constrained to
-    // CacheLineBytes to please NodeRef.
-    DesiredBranchSize = AllocBytes / (sizeof(KeyT) + sizeof(void*)),
-    BranchSize = DesiredBranchSize < CacheLineBytes ?
-                 DesiredBranchSize : CacheLineBytes
-  };
-
-  /// Allocator - The recycling allocator used for both branch and leaf nodes.
-  /// This typedef is very likely to be identical for all IntervalMaps with
-  /// reasonably sized entries, so the same allocator can be shared among
-  /// different kinds of maps.
-  typedef RecyclingAllocator<BumpPtrAllocator, char,
-                             AllocBytes, CacheLineBytes> Allocator;
-
-};
-
-
-//===----------------------------------------------------------------------===//
-//---                              NodeRef                                 ---//
-//===----------------------------------------------------------------------===//
-//
-// B+-tree nodes can be leaves or branches, so we need a polymorphic node
-// pointer that can point to both kinds.
-//
-// All nodes are cache line aligned and the low 6 bits of a node pointer are
-// always 0. These bits are used to store the number of elements in the
-// referenced node. Besides saving space, placing node sizes in the parents
-// allow tree balancing algorithms to run without faulting cache lines for nodes
-// that may not need to be modified.
-//
-// A NodeRef doesn't know whether it references a leaf node or a branch node.
-// It is the responsibility of the caller to use the correct types.
-//
-// Nodes are never supposed to be empty, and it is invalid to store a node size
-// of 0 in a NodeRef. The valid range of sizes is 1-64.
-//
-//===----------------------------------------------------------------------===//
-
-template <typename KeyT, typename ValT, typename Traits>
-class NodeRef {
-
-public:
-  typedef NodeSizer<KeyT, ValT> NodeSizer;
-  typedef Leaf<KeyT, ValT, NodeSizer::LeafSize, Traits> Leaf;
-  typedef Branch<KeyT, ValT, NodeSizer::BranchSize, Traits> Branch;
-
-private:
-  struct CacheAlignedPointerTraits {
-    static inline void *getAsVoidPointer(void *P) { return P; }
-    static inline void *getFromVoidPointer(void *P) { return P; }
-    enum { NumLowBitsAvailable = NodeSizer::Log2CacheLine };
-  };
-
-  PointerIntPair<void*, NodeSizer::Log2CacheLine, unsigned,
-                 CacheAlignedPointerTraits> pip;
-
-public:
-  /// NodeRef - Create a null ref.
-  NodeRef() {}
-
-  /// operator bool - Detect a null ref.
-  operator bool() const { return pip.getOpaqueValue(); }
-
-  /// NodeRef - Create a reference to the leaf node p with n elements.
-  NodeRef(Leaf *p, unsigned n) : pip(p, n - 1) {}
-
-  /// NodeRef - Create a reference to the branch node p with n elements.
-  NodeRef(Branch *p, unsigned n) : pip(p, n - 1) {}
-
-  /// size - Return the number of elements in the referenced node.
-  unsigned size() const { return pip.getInt() + 1; }
-
-  /// setSize - Update the node size.
-  void setSize(unsigned n) { pip.setInt(n - 1); }
-
-  /// leaf - Return the referenced leaf node.
-  /// Note there are no dynamic type checks.
-  Leaf &leaf() const {
-    return *reinterpret_cast<Leaf*>(pip.getPointer());
-  }
-
-  /// branch - Return the referenced branch node.
-  /// Note there are no dynamic type checks.
-  Branch &branch() const {
-    return *reinterpret_cast<Branch*>(pip.getPointer());
-  }
-
-  bool operator==(const NodeRef &RHS) const {
-    if (pip == RHS.pip)
-      return true;
-    assert(pip.getPointer() != RHS.pip.getPointer() && "Inconsistent NodeRefs");
-    return false;
-  }
-
-  bool operator!=(const NodeRef &RHS) const {
-    return !operator==(RHS);
-  }
-};
-
-//===----------------------------------------------------------------------===//
-//---                            Leaf nodes                                ---//
-//===----------------------------------------------------------------------===//
-//
-// Leaf nodes store up to N disjoint intervals with corresponding values.
-//
-// The intervals are kept sorted and fully coalesced so there are no adjacent
-// intervals mapping to the same value.
-//
-// These constraints are always satisfied:
-//
-// - Traits::stopLess(key[i].start, key[i].stop) - Non-empty, sane intervals.
-//
-// - Traits::stopLess(key[i].stop, key[i + 1].start) - Sorted.
-//
-// - val[i] != val[i + 1] ||
-//     !Traits::adjacent(key[i].stop, key[i + 1].start) - Fully coalesced.
-//
-//===----------------------------------------------------------------------===//
-
-template <typename KeyT, typename ValT, unsigned N, typename Traits>
-class Leaf : public NodeBase<std::pair<KeyT, KeyT>, ValT, N> {
-public:
-  const KeyT &start(unsigned i) const { return this->key[i].first; }
-  const KeyT &stop(unsigned i) const { return this->key[i].second; }
-  const ValT &value(unsigned i) const { return this->val[i]; }
-
-  KeyT &start(unsigned i) { return this->key[i].first; }
-  KeyT &stop(unsigned i) { return this->key[i].second; }
-  ValT &value(unsigned i) { return this->val[i]; }
-
-  /// findFrom - Find the first interval after i that may contain x.
-  /// @param i    Starting index for the search.
-  /// @param size Number of elements in node.
-  /// @param x    Key to search for.
-  /// @return     First index with !stopLess(key[i].stop, x), or size.
-  ///             This is the first interval that can possibly contain x.
-  unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
-    assert(i <= Size && Size <= N && "Bad indices");
-    assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
-           "Index is past the needed point");
-    while (i != Size && Traits::stopLess(stop(i), x)) ++i;
-    return i;
-  }
-
-  /// safeFind - Find an interval that is known to exist. This is the same as
-  /// findFrom except is it assumed that x is at least within range of the last
-  /// interval.
-  /// @param i Starting index for the search.
-  /// @param x Key to search for.
-  /// @return  First index with !stopLess(key[i].stop, x), never size.
-  ///          This is the first interval that can possibly contain x.
-  unsigned safeFind(unsigned i, KeyT x) const {
-    assert(i < N && "Bad index");
-    assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
-           "Index is past the needed point");
-    while (Traits::stopLess(stop(i), x)) ++i;
-    assert(i < N && "Unsafe intervals");
-    return i;
-  }
-
-  /// safeLookup - Lookup mapped value for a safe key.
-  /// It is assumed that x is within range of the last entry.
-  /// @param x        Key to search for.
-  /// @param NotFound Value to return if x is not in any interval.
-  /// @return         The mapped value at x or NotFound.
-  ValT safeLookup(KeyT x, ValT NotFound) const {
-    unsigned i = safeFind(0, x);
-    return Traits::startLess(x, start(i)) ? NotFound : value(i);
-  }
-
-  IdxPair insertFrom(unsigned i, unsigned Size, KeyT a, KeyT b, ValT y);
-  unsigned extendStop(unsigned i, unsigned Size, KeyT b);
-
-#ifndef NDEBUG
-  void dump(unsigned Size) {
-    errs() << "  N" << this << " [shape=record label=\"{ " << Size << '/' << N;
-    for (unsigned i = 0; i != Size; ++i)
-      errs() << " | {" << start(i) << '-' << stop(i) << "|" << value(i) << '}';
-    errs() << "}\"];\n";
-  }
-#endif
-
-};
-
-/// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as
-/// possible. This may cause the node to grow by 1, or it may cause the node
-/// to shrink because of coalescing.
-/// @param i    Starting index = insertFrom(0, size, a)
-/// @param size Number of elements in node.
-/// @param a    Interval start.
-/// @param b    Interval stop.
-/// @param y    Value be mapped.
-/// @return     (insert position, new size), or (i, Capacity+1) on overflow.
-template <typename KeyT, typename ValT, unsigned N, typename Traits>
-IdxPair Leaf<KeyT, ValT, N, Traits>::
-insertFrom(unsigned i, unsigned Size, KeyT a, KeyT b, ValT y) {
-  assert(i <= Size && Size <= N && "Invalid index");
-  assert(!Traits::stopLess(b, a) && "Invalid interval");
-
-  // Verify the findFrom invariant.
-  assert((i == 0 || Traits::stopLess(stop(i - 1), a)));
-  assert((i == Size || !Traits::stopLess(stop(i), a)));
-
-  // Coalesce with previous interval.
-  if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a))
-    return IdxPair(i - 1, extendStop(i - 1, Size, b));
-
-  // Detect overflow.
-  if (i == N)
-    return IdxPair(i, N + 1);
-
-  // Add new interval at end.
-  if (i == Size) {
-    start(i) = a;
-    stop(i) = b;
-    value(i) = y;
-    return IdxPair(i, Size + 1);
-  }
-
-  // Overlapping intervals?
-  if (!Traits::stopLess(b, start(i))) {
-    assert(value(i) == y && "Inconsistent values in overlapping intervals");
-    if (Traits::startLess(a, start(i)))
-      start(i) = a;
-    return IdxPair(i, extendStop(i, Size, b));
-  }
-
-  // Try to coalesce with following interval.
-  if (value(i) == y && Traits::adjacent(b, start(i))) {
-    start(i) = a;
-    return IdxPair(i, Size);
-  }
-
-  // We must insert before i. Detect overflow.
-  if (Size == N)
-    return IdxPair(i, N + 1);
-
-  // Insert before i.
-  this->shift(i, Size);
-  start(i) = a;
-  stop(i) = b;
-  value(i) = y;
-  return IdxPair(i, Size + 1);
-}
-
-/// extendStop - Extend stop(i) to b, coalescing with following intervals.
-/// @param i    Interval to extend.
-/// @param size Number of elements in node.
-/// @param b    New interval end point.
-/// @return     New node size after coalescing.
-template <typename KeyT, typename ValT, unsigned N, typename Traits>
-unsigned Leaf<KeyT, ValT, N, Traits>::
-extendStop(unsigned i, unsigned Size, KeyT b) {
-  assert(i < Size && Size <= N && "Bad indices");
-
-  // Are we even extending the interval?
-  if (Traits::startLess(b, stop(i)))
-    return Size;
-
-  // Find the first interval that may be preserved.
-  unsigned j = findFrom(i + 1, Size, b);
-  if (j < Size) {
-    // Would key[i] overlap key[j] after the extension?
-    if (Traits::stopLess(b, start(j))) {
-      // Not overlapping. Perhaps adjacent and coalescable?
-      if (value(i) == value(j) && Traits::adjacent(b, start(j)))
-        b = stop(j++);
-    } else {
-      // Overlap. Include key[j] in the new interval.
-      assert(value(i) == value(j) && "Overlapping values");
-      b = stop(j++);
-    }
-  }
-  stop(i) =  b;
-
-  // Entries [i+1;j) were coalesced.
-  if (i + 1 < j && j < Size)
-    this->erase(i + 1, j, Size);
-  return Size - (j - (i + 1));
-}
-
-
-//===----------------------------------------------------------------------===//
-//---                             Branch nodes                             ---//
-//===----------------------------------------------------------------------===//
-//
-// A branch node stores references to 1--N subtrees all of the same height.
-//
-// The key array in a branch node holds the rightmost stop key of each subtree.
-// It is redundant to store the last stop key since it can be found in the
-// parent node, but doing so makes tree balancing a lot simpler.
-//
-// It is unusual for a branch node to only have one subtree, but it can happen
-// in the root node if it is smaller than the normal nodes.
-//
-// When all of the leaf nodes from all the subtrees are concatenated, they must
-// satisfy the same constraints as a single leaf node. They must be sorted,
-// sane, and fully coalesced.
-//
-//===----------------------------------------------------------------------===//
-
-template <typename KeyT, typename ValT, unsigned N, typename Traits>
-class Branch : public NodeBase<KeyT, NodeRef<KeyT, ValT, Traits>, N> {
-  typedef  NodeRef<KeyT, ValT, Traits> NodeRef;
-public:
-  const KeyT &stop(unsigned i) const { return this->key[i]; }
-  const NodeRef &subtree(unsigned i) const { return this->val[i]; }
-
-  KeyT &stop(unsigned i) { return this->key[i]; }
-  NodeRef &subtree(unsigned i) { return this->val[i]; }
-
-
-  /// findFrom - Find the first subtree after i that may contain x.
-  /// @param i    Starting index for the search.
-  /// @param size Number of elements in node.
-  /// @param x    Key to search for.
-  /// @return     First index with !stopLess(key[i], x), or size.
-  ///             This is the first subtree that can possibly contain x.
-  unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
-    assert(i <= Size && Size <= N && "Bad indices");
-    assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
-           "Index to findFrom is past the needed point");
-    while (i != Size && Traits::stopLess(stop(i), x)) ++i;
-    return i;
-  }
-
-  /// safeFind - Find a subtree that is known to exist. This is the same as
-  /// findFrom except is it assumed that x is in range.
-  /// @param i Starting index for the search.
-  /// @param x Key to search for.
-  /// @return  First index with !stopLess(key[i], x), never size.
-  ///          This is the first subtree that can possibly contain x.
-  unsigned safeFind(unsigned i, KeyT x) const {
-    assert(i < N && "Bad index");
-    assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
-           "Index is past the needed point");
-    while (Traits::stopLess(stop(i), x)) ++i;
-    assert(i < N && "Unsafe intervals");
-    return i;
-  }
-
-  /// safeLookup - Get the subtree containing x, Assuming that x is in range.
-  /// @param x Key to search for.
-  /// @return  Subtree containing x
-  NodeRef safeLookup(KeyT x) const {
-    return subtree(safeFind(0, x));
-  }
-
-  /// insert - Insert a new (subtree, stop) pair.
-  /// @param i    Insert position, following entries will be shifted.
-  /// @param size Number of elements in node.
-  /// @param node Subtree to insert.
-  /// @param stp  Last key in subtree.
-  void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop) {
-    assert(Size < N && "branch node overflow");
-    assert(i <= Size && "Bad insert position");
-    this->shift(i, Size);
-    subtree(i) = Node;
-    stop(i) = Stop;
-  }
-
-#ifndef NDEBUG
-  void dump(unsigned Size) {
-    errs() << "  N" << this << " [shape=record label=\"" << Size << '/' << N;
-    for (unsigned i = 0; i != Size; ++i)
-      errs() << " | <s" << i << "> " << stop(i);
-    errs() << "\"];\n";
-    for (unsigned i = 0; i != Size; ++i)
-      errs() << "  N" << this << ":s" << i << " -> N"
-             << &subtree(i).branch() << ";\n";
-  }
-#endif
-
-};
-
-} // namespace IntervalMapImpl
-
-
-//===----------------------------------------------------------------------===//
-//---                          IntervalMap                                ----//
-//===----------------------------------------------------------------------===//
-
-template <typename KeyT, typename ValT,
-          unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize,
-          typename Traits = IntervalMapInfo<KeyT> >
-class IntervalMap {
-  typedef IntervalMapImpl::NodeRef<KeyT, ValT, Traits> NodeRef;
-  typedef typename NodeRef::NodeSizer NodeSizer;
-  typedef typename NodeRef::Leaf Leaf;
-  typedef typename NodeRef::Branch Branch;
-  typedef IntervalMapImpl::Leaf<KeyT, ValT, N, Traits> RootLeaf;
-  typedef IntervalMapImpl::IdxPair IdxPair;
-
-  // The RootLeaf capacity is given as a template parameter. We must compute the
-  // corresponding RootBranch capacity.
-  enum {
-    DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) /
-      (sizeof(KeyT) + sizeof(NodeRef)),
-    RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1
-  };
-
-  typedef IntervalMapImpl::Branch<KeyT, ValT, RootBranchCap, Traits> RootBranch;
-
-  // When branched, we store a global start key as well as the branch node.
-  struct RootBranchData {
-    KeyT start;
-    RootBranch node;
-  };
-
-  enum {
-    RootDataSize = sizeof(RootBranchData) > sizeof(RootLeaf) ?
-                   sizeof(RootBranchData) : sizeof(RootLeaf)
-  };
-
-public:
-  typedef typename NodeSizer::Allocator Allocator;
-
-private:
-  // The root data is either a RootLeaf or a RootBranchData instance.
-  // We can't put them in a union since C++03 doesn't allow non-trivial
-  // constructors in unions.
-  // Instead, we use a char array with pointer alignment. The alignment is
-  // ensured by the allocator member in the class, but still verified in the
-  // constructor. We don't support keys or values that are more aligned than a
-  // pointer.
-  char data[RootDataSize];
-
-  // Tree height.
-  // 0: Leaves in root.
-  // 1: Root points to leaf.
-  // 2: root->branch->leaf ...
-  unsigned height;
-
-  // Number of entries in the root node.
-  unsigned rootSize;
-
-  // Allocator used for creating external nodes.
-  Allocator &allocator;
-
-  const RootLeaf &rootLeaf() const {
-    assert(!branched() && "Cannot acces leaf data in branched root");
-    return *reinterpret_cast<const RootLeaf*>(data);
-  }
-  RootLeaf &rootLeaf() {
-    assert(!branched() && "Cannot acces leaf data in branched root");
-    return *reinterpret_cast<RootLeaf*>(data);
-  }
-  const RootBranchData &rootBranchData() const {
-    assert(branched() && "Cannot access branch data in non-branched root");
-    return *reinterpret_cast<const RootBranchData*>(data);
-  }
-  RootBranchData &rootBranchData() {
-    assert(branched() && "Cannot access branch data in non-branched root");
-    return *reinterpret_cast<RootBranchData*>(data);
-  }
-  const RootBranch &rootBranch() const { return rootBranchData().node; }
-  RootBranch &rootBranch()             { return rootBranchData().node; }
-  KeyT rootBranchStart() const { return rootBranchData().start; }
-  KeyT &rootBranchStart()      { return rootBranchData().start; }
-
-  Leaf *allocLeaf()  {
-    return new(allocator.template Allocate<Leaf>()) Leaf();
-  }
-  void freeLeaf(Leaf *P) {
-    P->~Leaf();
-    allocator.Deallocate(P);
-  }
-
-  Branch *allocBranch() {
-    return new(allocator.template Allocate<Branch>()) Branch();
-  }
-  void freeBranch(Branch *P) {
-    P->~Branch();
-    allocator.Deallocate(P);
-  }
-
-
-  IdxPair branchRoot(unsigned Position);
-  IdxPair splitRoot(unsigned Position);
-
-  void switchRootToBranch() {
-    rootLeaf().~RootLeaf();
-    height = 1;
-    new (&rootBranchData()) RootBranchData();
-  }
-
-  void switchRootToLeaf() {
-    rootBranchData().~RootBranchData();
-    height = 0;
-    new(&rootLeaf()) RootLeaf();
-  }
-
-  bool branched() const { return height > 0; }
-
-  ValT treeSafeLookup(KeyT x, ValT NotFound) const;
-
-  void visitNodes(void (IntervalMap::*f)(NodeRef, unsigned Level));
-
-public:
-  explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) {
-    assert((uintptr_t(data) & (alignOf<RootLeaf>() - 1)) == 0 &&
-           "Insufficient alignment");
-    new(&rootLeaf()) RootLeaf();
-  }
-
-  /// empty -  Return true when no intervals are mapped.
-  bool empty() const {
-    return rootSize == 0;
-  }
-
-  /// start - Return the smallest mapped key in a non-empty map.
-  KeyT start() const {
-    assert(!empty() && "Empty IntervalMap has no start");
-    return !branched() ? rootLeaf().start(0) : rootBranchStart();
-  }
-
-  /// stop - Return the largest mapped key in a non-empty map.
-  KeyT stop() const {
-    assert(!empty() && "Empty IntervalMap has no stop");
-    return !branched() ? rootLeaf().stop(rootSize - 1) :
-                         rootBranch().stop(rootSize - 1);
-  }
-
-  /// lookup - Return the mapped value at x or NotFound.
-  ValT lookup(KeyT x, ValT NotFound = ValT()) const {
-    if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x))
-      return NotFound;
-    return branched() ? treeSafeLookup(x, NotFound) :
-                        rootLeaf().safeLookup(x, NotFound);
-  }
-
-  /// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
-  /// It is assumed that no key in the interval is mapped to another value, but
-  /// overlapping intervals already mapped to y will be coalesced.
-  void insert(KeyT a, KeyT b, ValT y) {
-    find(a).insert(a, b, y);
-  }
-
-  class const_iterator;
-  class iterator;
-  friend class const_iterator;
-  friend class iterator;
-
-  const_iterator begin() const {
-    iterator I(*this);
-    I.goToBegin();
-    return I;
-  }
-
-  iterator begin() {
-    iterator I(*this);
-    I.goToBegin();
-    return I;
-  }
-
-  const_iterator end() const {
-    iterator I(*this);
-    I.goToEnd();
-    return I;
-  }
-
-  iterator end() {
-    iterator I(*this);
-    I.goToEnd();
-    return I;
-  }
-
-  /// find - Return an iterator pointing to the first interval ending at or
-  /// after x, or end().
-  const_iterator find(KeyT x) const {
-    iterator I(*this);
-    I.find(x);
-    return I;
-  }
-
-  iterator find(KeyT x) {
-    iterator I(*this);
-    I.find(x);
-    return I;
-  }
-
-#ifndef NDEBUG
-  void dump();
-  void dumpNode(NodeRef Node, unsigned Height);
-#endif
-};
-
-/// treeSafeLookup - Return the mapped value at x or NotFound, assuming a
-/// branched root.
-template <typename KeyT, typename ValT, unsigned N, typename Traits>
-ValT IntervalMap<KeyT, ValT, N, Traits>::
-treeSafeLookup(KeyT x, ValT NotFound) const {
-  assert(branched() && "treeLookup assumes a branched root");
-
-  NodeRef NR = rootBranch().safeLookup(x);
-  for (unsigned h = height-1; h; --h)
-    NR = NR.branch().safeLookup(x);
-  return NR.leaf().safeLookup(x, NotFound);
-}
-