Home | History | Annotate | Download | only in Support 
      1 //===- lib/Support/IntervalMap.cpp - A sorted interval map ----------------===//
      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 the few non-templated functions in IntervalMap.
     11 //
     12 //===----------------------------------------------------------------------===//
     13 
     14 #include "llvm/ADT/IntervalMap.h"
     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(0, 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 
    162