LCOV - code coverage report
Current view: top level - lib/Support - IntervalMap.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 60 63 95.2 %
Date: 2018-06-17 00:07:59 Functions: 6 6 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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       32017 : void Path::replaceRoot(void *Root, unsigned Size, IdxPair Offsets) {
      20             :   assert(!path.empty() && "Can't replace missing root");
      21       32017 :   path.front() = Entry(Root, Size, Offsets.first);
      22       64034 :   path.insert(path.begin() + 1, Entry(subtree(0), Offsets.second));
      23       32017 : }
      24             : 
      25      362864 : NodeRef Path::getLeftSibling(unsigned Level) const {
      26             :   // The root has no siblings.
      27      362864 :   if (Level == 0)
      28           0 :     return NodeRef();
      29             : 
      30             :   // Go up the tree until we can go left.
      31      362864 :   unsigned l = Level - 1;
      32      514980 :   while (l && path[l].offset == 0)
      33       10059 :     --l;
      34             : 
      35             :   // We can't go left.
      36      725728 :   if (path[l].offset == 0)
      37       43122 :     return NodeRef();
      38             : 
      39             :   // NR is the subtree containing our left sibling.
      40      639484 :   NodeRef NR = path[l].subtree(path[l].offset - 1);
      41             : 
      42             :   // Keep right all the way down.
      43      324303 :   for (++l; l != Level; ++l)
      44        4561 :     NR = NR.subtree(NR.size() - 1);
      45      319742 :   return NR;
      46             : }
      47             : 
      48      765799 : 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      472862 :     l = Level - 1;
      55      970900 :     while (path[l].offset == 0) {
      56             :       assert(l != 0 && "Cannot move beyond begin()");
      57        8392 :       --l;
      58             :     }
      59      292937 :   } else if (height() < Level)
      60             :     // end() may have created a height=0 path.
      61      581854 :     path.resize(Level + 1, Entry(nullptr, 0, 0));
      62             : 
      63             :   // NR is the subtree containing our left sibling.
      64     1531598 :   --path[l].offset;
      65      765799 :   NodeRef NR = subtree(l);
      66             : 
      67             :   // Get the rightmost node in the subtree.
      68      871192 :   for (++l; l != Level; ++l) {
      69      210786 :     path[l] = Entry(NR, NR.size() - 1);
      70      105393 :     NR = NR.subtree(NR.size() - 1);
      71             :   }
      72     1531598 :   path[l] = Entry(NR, NR.size() - 1);
      73      765799 : }
      74             : 
      75      286174 : NodeRef Path::getRightSibling(unsigned Level) const {
      76             :   // The root has no siblings.
      77      286174 :   if (Level == 0)
      78           0 :     return NodeRef();
      79             : 
      80             :   // Go up the tree until we can go right.
      81      286174 :   unsigned l = Level - 1;
      82      500665 :   while (l && atLastEntry(l))
      83       53007 :     --l;
      84             : 
      85             :   // We can't go right.
      86      286174 :   if (atLastEntry(l))
      87      166330 :     return NodeRef();
      88             : 
      89             :   // NR is the subtree containing our right sibling.
      90      239688 :   NodeRef NR = path[l].subtree(path[l].offset + 1);
      91             : 
      92             :   // Keep left all the way down.
      93      122768 :   for (++l; l != Level; ++l)
      94        2924 :     NR = NR.subtree(0);
      95      119844 :   return NR;
      96             : }
      97             : 
      98     1213247 : 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     1213247 :   unsigned l = Level - 1;
     103     2004232 :   while (l && atLastEntry(l))
     104       61629 :     --l;
     105             : 
     106             :   // NR is the subtree containing our right sibling. If we hit end(), we have
     107             :   // offset(0) == node(0).size().
     108     2426494 :   if (++path[l].offset == path[l].size)
     109             :     return;
     110     1098631 :   NodeRef NR = subtree(l);
     111             : 
     112     1139189 :   for (++l; l != Level; ++l) {
     113       81116 :     path[l] = Entry(NR, 0);
     114       40558 :     NR = NR.subtree(0);
     115             :   }
     116     2197262 :   path[l] = Entry(NR, 0);
     117             : }
     118             : 
     119             : 
     120      315049 : 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      315049 :   if (!Nodes)
     126           0 :     return IdxPair();
     127             : 
     128             :   // Trivial algorithm: left-leaning even distribution.
     129      315049 :   const unsigned PerNode = (Elements + Grow) / Nodes;
     130      315049 :   const unsigned Extra = (Elements + Grow) % Nodes;
     131             :   IdxPair PosPair = IdxPair(Nodes, 0);
     132             :   unsigned Sum = 0;
     133     1969363 :   for (unsigned n = 0; n != Nodes; ++n) {
     134      827157 :     Sum += NewSize[n] = PerNode + (n < Extra);
     135      827157 :     if (PosPair.first == Nodes && Sum > Position)
     136      315049 :       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      315049 :   if (Grow) {
     142             :     assert(PosPair.first < Nodes && "Bad algebra");
     143             :     assert(NewSize[PosPair.first] && "Too few elements to need Grow");
     144      315049 :     --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      315049 :   return PosPair;
     157             : }
     158             : 
     159             : } // namespace IntervalMapImpl
     160             : } // namespace llvm
     161             : 

Generated by: LCOV version 1.13