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