Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- llvm/ADT/IntervalMap.h - A sorted interval map -----------*- C++ -*-===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

///

/// \file

/// 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:

//   using iterator_category = std::bidirectional_iterator_tag;

//   using value_type = ValT;

//   using difference_type = std::ptrdiff_t;

//   using pointer = value_type *;

//   using reference = value_type &;

//

//   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/PointerIntPair.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/Support/Allocator.h"

#include "llvm/Support/RecyclingAllocator.h"

#include <algorithm>

#include <cassert>

#include <iterator>

#include <new>

#include <utility>

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;

  }

  /// nonEmpty - Return true if [a;b] is non-empty.

  /// This is a <= b for a closed interval, a < b for [a;b) half-open intervals.

  static inline bool nonEmpty(const T &a, const T &b) {

    return a <= b;

  }

};

template <typename T>

struct IntervalMapHalfOpenInfo {

  /// startLess - Return true if x is not in [a;b).

  static inline bool startLess(const T &x, const T &a) {

    return x < a;

  }

  /// stopLess - Return true if x is not in [a;b).

  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.

  static inline bool adjacent(const T &a, const T &b) {

    return a == b;

  }

  /// nonEmpty - Return true if [a;b) is non-empty.

  static inline bool nonEmpty(const T &a, const T &b) {

    return a < b;

  }

};

/// IntervalMapImpl - Namespace used for IntervalMap implementation details.

/// It should be considered private to the implementation.

namespace IntervalMapImpl {

using IdxPair = std::pair<unsigned,unsigned>;

//===----------------------------------------------------------------------===//

//---                    IntervalMapImpl::NodeBase                         ---//

//===----------------------------------------------------------------------===//

//

// Both leaf and branch nodes store vectors of pairs.

// Leaves store ((KeyT, KeyT), ValT) pairs, branches use (NodeRef, KeyT).

//

// 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):

//

//   T1  T2   N Waste  Used by

//    4   4  24   0    Branch<4> (32-bit pointers)

//    8   4  16   0    Leaf<4,4>, Branch<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 T1, typename T2, unsigned N>

class NodeBase {

public:

  enum { Capacity = N };

  T1 first[N];

  T2 second[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<T1, T2, M> &Other, unsigned i,

            unsigned j, unsigned Count) {

    assert(i + Count <= M && "Invalid source range");

    assert(j + Count <= N && "Invalid dest range");

    for (unsigned e = i + Count; i != e; ++i, ++j) {

      first[j]  = Other.first[i];

      second[j] = Other.second[i];

    }

  }

  /// moveLeft - 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 moveLeft(unsigned i, unsigned j, unsigned Count) {

    assert(j <= i && "Use moveRight shift elements right");

    copy(*this, i, j, Count);

  }

  /// moveRight - 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 moveRight(unsigned i, unsigned j, unsigned Count) {

    assert(i <= j && "Use moveLeft shift elements left");

    assert(j + Count <= N && "Invalid range");

    while (Count--) {

      first[j + Count]  = first[i + Count];

      second[j + Count] = second[i + 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) {

    moveLeft(j, i, Size - j);

  }

  /// erase - Erase element at i.

  /// @param i    Index of element to erase.

  /// @param Size Number of elements in node.

  void erase(unsigned i, unsigned Size) {

    erase(i, i+1, Size);

  }

  /// 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) {

    moveRight(i, i + 1, Size - i);

  }

  /// transferToLeftSib - 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 transferToLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize,

                         unsigned Count) {

    Sib.copy(*this, 0, SSize, Count);

    erase(0, Count, Size);

  }

  /// transferToRightSib - 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 transferToRightSib(unsigned Size, NodeBase &Sib, unsigned SSize,

                          unsigned Count) {

    Sib.moveRight(0, Count, SSize);

    Sib.copy(*this, Size-Count, 0, Count);

  }

  /// adjustFromLeftSib - 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 adjustFromLeftSib(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.transferToRightSib(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);

      transferToLeftSib(Size, Sib, SSize, Count);

      return -Count;

    }

  }

};

/// IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes.

/// @param Node  Array of pointers to sibling nodes.

/// @param Nodes Number of nodes.

/// @param CurSize Array of current node sizes, will be overwritten.

/// @param NewSize Array of desired node sizes.

template <typename NodeT>

void adjustSiblingSizes(NodeT *Node[], unsigned Nodes,

                        unsigned CurSize[], const unsigned NewSize[]) {

  // Move elements right.

  for (int n = Nodes - 1; n; --n) {

    if (CurSize[n] == NewSize[n])

      continue;

    for (int m = n - 1; m != -1; --m) {

      int d = Node[n]->adjustFromLeftSib(CurSize[n], *Node[m], CurSize[m],

                                         NewSize[n] - CurSize[n]);

      CurSize[m] -= d;

      CurSize[n] += d;

      // Keep going if the current node was exhausted.

      if (CurSize[n] >= NewSize[n])

          break;

    }

  }

  if (Nodes == 0)

    return;

  // Move elements left.

  for (unsigned n = 0; n != Nodes - 1; ++n) {

    if (CurSize[n] == NewSize[n])

      continue;

    for (unsigned m = n + 1; m != Nodes; ++m) {

      int d = Node[m]->adjustFromLeftSib(CurSize[m], *Node[n], CurSize[n],

                                        CurSize[n] -  NewSize[n]);

      CurSize[m] += d;

      CurSize[n] -= d;

      // Keep going if the current node was exhausted.

      if (CurSize[n] >= NewSize[n])

          break;

    }

  }

#ifndef NDEBUG

  for (unsigned n = 0; n != Nodes; n++)

    assert(CurSize[n] == NewSize[n] && "Insufficient element shuffle");

#endif

}

/// IntervalMapImpl::distribute - Compute a new distribution of node elements

/// after an overflow or underflow. Reserve space for a new element at Position,

/// and compute the node that will hold Position after redistributing node

/// elements.

///

/// It is required that

///

///   Elements == sum(CurSize), and

///   Elements + Grow <= Nodes * Capacity.

///

/// NewSize[] will be filled in such that:

///

///   sum(NewSize) == Elements, and

///   NewSize[i] <= Capacity.

///

/// The returned index is the node where Position will go, so:

///

///   sum(NewSize[0..idx-1]) <= Position

///   sum(NewSize[0..idx])   >= Position

///

/// The last equality, sum(NewSize[0..idx]) == Position, can only happen when

/// Grow is set and NewSize[idx] == Capacity-1. The index points to the node

/// before the one holding the Position'th element where there is room for an

/// insertion.

///

/// @param Nodes    The number of nodes.

/// @param Elements Total elements in all nodes.

/// @param Capacity The capacity of each node.

/// @param CurSize  Array[Nodes] of current node sizes, or NULL.

/// @param NewSize  Array[Nodes] to receive the new node sizes.

/// @param Position Insert position.

/// @param Grow     Reserve space for a new element at Position.

/// @return         (node, offset) for Position.

IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,

                   const unsigned *CurSize, unsigned NewSize[],

                   unsigned Position, bool Grow);

//===----------------------------------------------------------------------===//

//---                   IntervalMapImpl::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.

//

//===----------------------------------------------------------------------===//

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,

  DesiredNodeBytes = 3 * CacheLineBytes

};

template <typename KeyT, typename ValT>

struct NodeSizer {

  enum {

    // 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.

    DesiredLeafSize = DesiredNodeBytes /

      static_cast<unsigned>(2*sizeof(KeyT)+sizeof(ValT)),

    MinLeafSize = 3,

    LeafSize = DesiredLeafSize > MinLeafSize ? DesiredLeafSize : MinLeafSize

  };

  using LeafBase = NodeBase<std::pair<KeyT, KeyT>, ValT, LeafSize>;

  enum {

    // Now that we have the leaf branching factor, compute the actual allocation

    // unit size by rounding up to a whole number of cache lines.

    AllocBytes = (sizeof(LeafBase) + CacheLineBytes-1) & ~(CacheLineBytes-1),

    // Determine the branching factor for branch nodes.

    BranchSize = AllocBytes /

      static_cast<unsigned>(sizeof(KeyT) + sizeof(void*))

  };

  /// 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.

  using Allocator =

      RecyclingAllocator<BumpPtrAllocator, char, AllocBytes, CacheLineBytes>;

};

//===----------------------------------------------------------------------===//

//---                     IntervalMapImpl::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.

//

//===----------------------------------------------------------------------===//

class NodeRef {

  struct CacheAlignedPointerTraits {

    static inline void *getAsVoidPointer(void *P) { return P; }

    static inline void *getFromVoidPointer(void *P) { return P; }

    static constexpr int NumLowBitsAvailable = Log2CacheLine;

  };

  PointerIntPair<void*, Log2CacheLine, unsigned, CacheAlignedPointerTraits> pip;

public:

  /// NodeRef - Create a null ref.

  NodeRef() = default;

  /// operator bool - Detect a null ref.

  explicit operator bool() const { return pip.getOpaqueValue(); }

  /// NodeRef - Create a reference to the node p with n elements.

  template <typename NodeT>

  NodeRef(NodeT *p, unsigned n) : pip(p, n - 1) {

    assert(n <= NodeT::Capacity && "Size too big for node");

  }

  /// 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); }

  /// subtree - Access the i'th subtree reference in a branch node.

  /// This depends on branch nodes storing the NodeRef array as their first

  /// member.

  NodeRef &subtree(unsigned i) const {

    return reinterpret_cast<NodeRef*>(pip.getPointer())[i];

  }

  /// get - Dereference as a NodeT reference.

  template <typename NodeT>

  NodeT &get() const {

    return *reinterpret_cast<NodeT*>(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);

  }

};

//===----------------------------------------------------------------------===//

//---                      IntervalMapImpl::LeafNode                       ---//

//===----------------------------------------------------------------------===//

//

// 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(start(i), stop(i))    - Non-empty, sane intervals.

//

// - Traits::stopLess(stop(i), start(i + 1) - Sorted.

//

// - value(i) != value(i + 1) || !Traits::adjacent(stop(i), start(i + 1))

//                                          - Fully coalesced.

//

//===----------------------------------------------------------------------===//

template <typename KeyT, typename ValT, unsigned N, typename Traits>

class LeafNode : public NodeBase<std::pair<KeyT, KeyT>, ValT, N> {

public:

  const KeyT &start(unsigned i) const { return this->first[i].first; }

  const KeyT &stop(unsigned i) const { return this->first[i].second; }

  const ValT &value(unsigned i) const { return this->second[i]; }

  KeyT &start(unsigned i) { return this->first[i].first; }

  KeyT &stop(unsigned i) { return this->first[i].second; }

  ValT &value(unsigned i) { return this->second[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);

  }

  unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y);

};

/// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as

/// possible. This may cause the node to grow by 1, or it may cause the node

/// to shrink because of coalescing.

/// @param Pos  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>

unsigned LeafNode<KeyT, ValT, N, Traits>::

insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y) {

  unsigned i = Pos;

  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)));

  assert((i == Size || Traits::stopLess(b, start(i))) && "Overlapping insert");

  // Coalesce with previous interval.

  if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a)) {

    Pos = i - 1;

    // Also coalesce with next interval?

    if (i != Size && value(i) == y && Traits::adjacent(b, start(i))) {

      stop(i - 1) = stop(i);

      this->erase(i, Size);

      return Size - 1;

    }

    stop(i - 1) = b;

    return Size;

  }

  // Detect overflow.

  if (i == N)

    return N + 1;

  // Add new interval at end.

  if (i == Size) {

    start(i) = a;

    stop(i) = b;

    value(i) = y;

    return Size + 1;

  }

  // Try to coalesce with following interval.

  if (value(i) == y && Traits::adjacent(b, start(i))) {

    start(i) = a;

    return Size;

  }

  // We must insert before i. Detect overflow.

  if (Size == N)

    return N + 1;

  // Insert before i.

  this->shift(i, Size);

  start(i) = a;

  stop(i) = b;

  value(i) = y;

  return Size + 1;

}

//===----------------------------------------------------------------------===//

//---                   IntervalMapImpl::BranchNode                        ---//

//===----------------------------------------------------------------------===//

//

// 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 BranchNode : public NodeBase<NodeRef, KeyT, N> {

public:

  const KeyT &stop(unsigned i) const { return this->second[i]; }

  const NodeRef &subtree(unsigned i) const { return this->first[i]; }

  KeyT &stop(unsigned i) { return this->second[i]; }

  NodeRef &subtree(unsigned i) { return this->first[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 Stop 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;

  }

};

//===----------------------------------------------------------------------===//

//---                         IntervalMapImpl::Path                        ---//

//===----------------------------------------------------------------------===//

//

// A Path is used by iterators to represent a position in a B+-tree, and the

// path to get there from the root.

//

// The Path class also contains the tree navigation code that doesn't have to

// be templatized.

//

//===----------------------------------------------------------------------===//

class Path {

  /// Entry - Each step in the path is a node pointer and an offset into that

  /// node.

  struct Entry {

    void *node;

    unsigned size;

    unsigned offset;

    Entry(void *Node, unsigned Size, unsigned Offset)

      : node(Node), size(Size), offset(Offset) {}

    Entry(NodeRef Node, unsigned Offset)

      : node(&Node.subtree(0)), size(Node.size()), offset(Offset) {}

    NodeRef &subtree(unsigned i) const {

      return reinterpret_cast<NodeRef*>(node)[i];

    }

  };

  /// path - The path entries, path[0] is the root node, path.back() is a leaf.

  SmallVector<Entry, 4> path;

public:

  // Node accessors.

  template <typename NodeT> NodeT &node(unsigned Level) const {

    return *reinterpret_cast<NodeT*>(path[Level].node);

  }

  unsigned size(unsigned Level) const { return path[Level].size; }

  unsigned offset(unsigned Level) const { return path[Level].offset; }

  unsigned &offset(unsigned Level) { return path[Level].offset; }

  // Leaf accessors.

  template <typename NodeT> NodeT &leaf() const {

    return *reinterpret_cast<NodeT*>(path.back().node);

  }

  unsigned leafSize() const { return path.back().size; }

  unsigned leafOffset() const { return path.back().offset; }

  unsigned &leafOffset() { return path.back().offset; }