lib/Support/IntervalMap.cpp

   1 //===- lib/Support/IntervalMap.cpp - A sorted interval map ----------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements the few non-templated functions in IntervalMap.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/ADT/IntervalMap.h"
  14
  15 namespace llvm {
  16 namespace IntervalMapImpl {
  17
  18 void Path::replaceRoot(void *Root, unsigned Size, IdxPair Offsets) {
  19   assert(!path.empty() && "Can't replace missing root");
  20   path.front() = Entry(Root, Size, Offsets.first);
  21   path.insert(path.begin() + 1, Entry(subtree(0), Offsets.second));
  22 }
  23
  24 NodeRef Path::getLeftSibling(unsigned Level) const {
  25   // The root has no siblings.
  26   if (Level == 0)
  27     return NodeRef();
  28
  29   // Go up the tree until we can go left.
  30   unsigned l = Level - 1;
  31   while (l && path[l].offset == 0)
  32     --l;
  33
  34   // We can't go left.
  35   if (path[l].offset == 0)
  36     return NodeRef();
  37
  38   // NR is the subtree containing our left sibling.
  39   NodeRef NR = path[l].subtree(path[l].offset - 1);
  40
  41   // Keep right all the way down.
  42   for (++l; l != Level; ++l)
  43     NR = NR.subtree(NR.size() - 1);
  44   return NR;
  45 }
  46
  47 void Path::moveLeft(unsigned Level) {
  48   assert(Level != 0 && "Cannot move the root node");
  49
  50   // Go up the tree until we can go left.
  51   unsigned l = 0;
  52   if (valid()) {
  53     l = Level - 1;
  54     while (path[l].offset == 0) {
  55       assert(l != 0 && "Cannot move beyond begin()");
  56       --l;
  57     }
  58   } else if (height() < Level)
  59     // end() may have created a height=0 path.
  60     path.resize(Level + 1, Entry(nullptr, 0, 0));
  61
  62   // NR is the subtree containing our left sibling.
  63   --path[l].offset;
  64   NodeRef NR = subtree(l);
  65
  66   // Get the rightmost node in the subtree.
  67   for (++l; l != Level; ++l) {
  68     path[l] = Entry(NR, NR.size() - 1);
  69     NR = NR.subtree(NR.size() - 1);
  70   }
  71   path[l] = Entry(NR, NR.size() - 1);
  72 }
  73
  74 NodeRef Path::getRightSibling(unsigned Level) const {
  75   // The root has no siblings.
  76   if (Level == 0)
  77     return NodeRef();
  78
  79   // Go up the tree until we can go right.
  80   unsigned l = Level - 1;
  81   while (l && atLastEntry(l))
  82     --l;
  83
  84   // We can't go right.
  85   if (atLastEntry(l))
  86     return NodeRef();
  87
  88   // NR is the subtree containing our right sibling.
  89   NodeRef NR = path[l].subtree(path[l].offset + 1);
  90
  91   // Keep left all the way down.
  92   for (++l; l != Level; ++l)
  93     NR = NR.subtree(0);
  94   return NR;
  95 }
  96
  97 void Path::moveRight(unsigned Level) {
  98   assert(Level != 0 && "Cannot move the root node");
  99
 100   // Go up the tree until we can go right.
 101   unsigned l = Level - 1;
 102   while (l && atLastEntry(l))
 103     --l;
 104
 105   // NR is the subtree containing our right sibling. If we hit end(), we have
 106   // offset(0) == node(0).size().
 107   if (++path[l].offset == path[l].size)
 108     return;
 109   NodeRef NR = subtree(l);
 110
 111   for (++l; l != Level; ++l) {
 112     path[l] = Entry(NR, 0);
 113     NR = NR.subtree(0);
 114   }
 115   path[l] = Entry(NR, 0);
 116 }
 117
 118
 119 IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,
 120                    const unsigned *CurSize, unsigned NewSize[],
 121                    unsigned Position, bool Grow) {
 122   assert(Elements + Grow <= Nodes * Capacity && "Not enough room for elements");
 123   assert(Position <= Elements && "Invalid position");
 124   if (!Nodes)
 125     return IdxPair();
 126
 127   // Trivial algorithm: left-leaning even distribution.
 128   const unsigned PerNode = (Elements + Grow) / Nodes;
 129   const unsigned Extra = (Elements + Grow) % Nodes;
 130   IdxPair PosPair = IdxPair(Nodes, 0);
 131   unsigned Sum = 0;
 132   for (unsigned n = 0; n != Nodes; ++n) {
 133     Sum += NewSize[n] = PerNode + (n < Extra);
 134     if (PosPair.first == Nodes && Sum > Position)
 135       PosPair = IdxPair(n, Position - (Sum - NewSize[n]));
 136   }
 137   assert(Sum == Elements + Grow && "Bad distribution sum");
 138
 139   // Subtract the Grow element that was added.
 140   if (Grow) {
 141     assert(PosPair.first < Nodes && "Bad algebra");
 142     assert(NewSize[PosPair.first] && "Too few elements to need Grow");
 143     --NewSize[PosPair.first];
 144   }
 145
 146 #ifndef NDEBUG
 147   Sum = 0;
 148   for (unsigned n = 0; n != Nodes; ++n) {
 149     assert(NewSize[n] <= Capacity && "Overallocated node");
 150     Sum += NewSize[n];
 151   }
 152   assert(Sum == Elements && "Bad distribution sum");
 153 #endif
 154
 155   return PosPair;
 156 }
 157
 158 } // namespace IntervalMapImpl
 159 } // namespace llvm
 160