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-10-20 13:21:21 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       46982 : void Path::replaceRoot(void *Root, unsigned Size, IdxPair Offsets) {
      20             :   assert(!path.empty() && "Can't replace missing root");
      21       46982 :   path.front() = Entry(Root, Size, Offsets.first);
      22       93964 :   path.insert(path.begin() + 1, Entry(subtree(0), Offsets.second));
      23       46982 : }
      24             : 
      25      612193 : NodeRef Path::getLeftSibling(unsigned Level) const {
      26             :   // The root has no siblings.
      27      612193 :   if (Level == 0)
      28           0 :     return NodeRef();
      29             : 
      30             :   // Go up the tree until we can go left.
      31      612193 :   unsigned l = Level - 1;
      32      640300 :   while (l && path[l].offset == 0)
      33       28107 :     --l;
      34             : 
      35             :   // We can't go left.
      36     1224386 :   if (path[l].offset == 0)
      37       82207 :     return NodeRef();
      38             : 
      39             :   // NR is the subtree containing our left sibling.
      40      529986 :   NodeRef NR = path[l].subtree(path[l].offset - 1);
      41             : 
      42             :   // Keep right all the way down.
      43      544265 :   for (++l; l != Level; ++l)
      44       14279 :     NR = NR.subtree(NR.size() - 1);
      45      529986 :   return NR;
      46             : }
      47             : 
      48     1029768 : 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      846344 :     l = Level - 1;
      55     1740406 :     while (path[l].offset == 0) {
      56             :       assert(l != 0 && "Cannot move beyond begin()");
      57       23859 :       --l;
      58             :     }
      59      183424 :   } else if (height() < Level)
      60             :     // end() may have created a height=0 path.
      61      361872 :     path.resize(Level + 1, Entry(nullptr, 0, 0));
      62             : 
      63             :   // NR is the subtree containing our left sibling.
      64     2059536 :   --path[l].offset;
      65     1029768 :   NodeRef NR = subtree(l);
      66             : 
      67             :   // Get the rightmost node in the subtree.
      68     1090271 :   for (++l; l != Level; ++l) {
      69      121006 :     path[l] = Entry(NR, NR.size() - 1);
      70       60503 :     NR = NR.subtree(NR.size() - 1);
      71             :   }
      72     2059536 :   path[l] = Entry(NR, NR.size() - 1);
      73     1029768 : }
      74             : 
      75      478657 : NodeRef Path::getRightSibling(unsigned Level) const {
      76             :   // The root has no siblings.
      77      478657 :   if (Level == 0)
      78           0 :     return NodeRef();
      79             : 
      80             :   // Go up the tree until we can go right.
      81      478657 :   unsigned l = Level - 1;
      82      524094 :   while (l && atLastEntry(l))
      83       45437 :     --l;
      84             : 
      85             :   // We can't go right.
      86      478657 :   if (atLastEntry(l))
      87      180579 :     return NodeRef();
      88             : 
      89             :   // NR is the subtree containing our right sibling.
      90      298078 :   NodeRef NR = path[l].subtree(path[l].offset + 1);
      91             : 
      92             :   // Keep left all the way down.
      93      308819 :   for (++l; l != Level; ++l)
      94       10741 :     NR = NR.subtree(0);
      95      298078 :   return NR;
      96             : }
      97             : 
      98     1687687 : 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     1687687 :   unsigned l = Level - 1;
     103     1766933 :   while (l && atLastEntry(l))
     104       79246 :     --l;
     105             : 
     106             :   // NR is the subtree containing our right sibling. If we hit end(), we have
     107             :   // offset(0) == node(0).size().
     108     3375374 :   if (++path[l].offset == path[l].size)
     109             :     return;
     110     1572202 :   NodeRef NR = subtree(l);
     111             : 
     112     1634209 :   for (++l; l != Level; ++l) {
     113       62007 :     path[l] = Entry(NR, 0);
     114       62007 :     NR = NR.subtree(0);
     115             :   }
     116     3144404 :   path[l] = Entry(NR, 0);
     117             : }
     118             : 
     119             : 
     120      519644 : 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      519644 :   if (!Nodes)
     126           0 :     return IdxPair();
     127             : 
     128             :   // Trivial algorithm: left-leaning even distribution.
     129      519644 :   const unsigned PerNode = (Elements + Grow) / Nodes;
     130      519644 :   const unsigned Extra = (Elements + Grow) % Nodes;
     131             :   IdxPair PosPair = IdxPair(Nodes, 0);
     132             :   unsigned Sum = 0;
     133     1961096 :   for (unsigned n = 0; n != Nodes; ++n) {
     134     1441452 :     Sum += NewSize[n] = PerNode + (n < Extra);
     135     1441452 :     if (PosPair.first == Nodes && Sum > Position)
     136      519644 :       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      519644 :   if (Grow) {
     142             :     assert(PosPair.first < Nodes && "Bad algebra");
     143             :     assert(NewSize[PosPair.first] && "Too few elements to need Grow");
     144      519644 :     --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      519644 :   return PosPair;
     157             : }
     158             : 
     159             : } // namespace IntervalMapImpl
     160             : } // namespace llvm
     161             : 

Generated by: LCOV version 1.13