LCOV - code coverage report
Current view: top level - lib/Support - IntervalMap.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 64 67 95.5 %
Date: 2017-09-14 15:23:50 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       23512 : void Path::replaceRoot(void *Root, unsigned Size, IdxPair Offsets) {
      20             :   assert(!path.empty() && "Can't replace missing root");
      21       47024 :   path.front() = Entry(Root, Size, Offsets.first);
      22       70536 :   path.insert(path.begin() + 1, Entry(subtree(0), Offsets.second));
      23       23512 : }
      24             : 
      25      280435 : NodeRef Path::getLeftSibling(unsigned Level) const {
      26             :   // The root has no siblings.
      27      280435 :   if (Level == 0)
      28           0 :     return NodeRef();
      29             : 
      30             :   // Go up the tree until we can go left.
      31      280435 :   unsigned l = Level - 1;
      32      403637 :   while (l && path[l].offset == 0)
      33        7374 :     --l;
      34             : 
      35             :   // We can't go left.
      36      560870 :   if (path[l].offset == 0)
      37       61002 :     return NodeRef();
      38             : 
      39             :   // NR is the subtree containing our left sibling.
      40      999736 :   NodeRef NR = path[l].subtree(path[l].offset - 1);
      41             : 
      42             :   // Keep right all the way down.
      43      253123 :   for (++l; l != Level; ++l)
      44        6378 :     NR = NR.subtree(NR.size() - 1);
      45      249934 :   return NR;
      46             : }
      47             : 
      48      628715 : 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      628715 :   unsigned l = 0;
      53      359373 :   if (valid()) {
      54      359373 :     l = Level - 1;
      55      736491 :     while (path[l].offset == 0) {
      56             :       assert(l != 0 && "Cannot move beyond begin()");
      57        5915 :       --l;
      58             :     }
      59      269342 :   } else if (height() < Level)
      60             :     // end() may have created a height=0 path.
      61      538362 :     path.resize(Level + 1, Entry(nullptr, 0, 0));
      62             : 
      63             :   // NR is the subtree containing our left sibling.
      64     1257430 :   --path[l].offset;
      65      628715 :   NodeRef NR = subtree(l);
      66             : 
      67             :   // Get the rightmost node in the subtree.
      68      776658 :   for (++l; l != Level; ++l) {
      69      443829 :     path[l] = Entry(NR, NR.size() - 1);
      70      295886 :     NR = NR.subtree(NR.size() - 1);
      71             :   }
      72     1886145 :   path[l] = Entry(NR, NR.size() - 1);
      73      628715 : }
      74             : 
      75      224551 : NodeRef Path::getRightSibling(unsigned Level) const {
      76             :   // The root has no siblings.
      77      224551 :   if (Level == 0)
      78           0 :     return NodeRef();
      79             : 
      80             :   // Go up the tree until we can go right.
      81      224551 :   unsigned l = Level - 1;
      82      447685 :   while (l && atLastEntry(l))
      83       61624 :     --l;
      84             : 
      85             :   // We can't go right.
      86      224551 :   if (atLastEntry(l))
      87      276104 :     return NodeRef();
      88             : 
      89             :   // NR is the subtree containing our right sibling.
      90      345996 :   NodeRef NR = path[l].subtree(path[l].offset + 1);
      91             : 
      92             :   // Keep left all the way down.
      93       88505 :   for (++l; l != Level; ++l)
      94        2006 :     NR = NR.subtree(0);
      95       86499 :   return NR;
      96             : }
      97             : 
      98      706212 : 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      706212 :   unsigned l = Level - 1;
     103     1033929 :   while (l && atLastEntry(l))
     104       27123 :     --l;
     105             : 
     106             :   // NR is the subtree containing our right sibling. If we hit end(), we have
     107             :   // offset(0) == node(0).size().
     108     2118636 :   if (++path[l].offset == path[l].size)
     109             :     return;
     110      616303 :   NodeRef NR = subtree(l);
     111             : 
     112      627097 :   for (++l; l != Level; ++l) {
     113       21588 :     path[l] = Entry(NR, 0);
     114       10794 :     NR = NR.subtree(0);
     115             :   }
     116     1232606 :   path[l] = Entry(NR, 0);
     117             : }
     118             : 
     119             : 
     120      246023 : 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      246023 :   if (!Nodes)
     126           0 :     return IdxPair();
     127             : 
     128             :   // Trivial algorithm: left-leaning even distribution.
     129      246023 :   const unsigned PerNode = (Elements + Grow) / Nodes;
     130      246023 :   const unsigned Extra = (Elements + Grow) % Nodes;
     131      492046 :   IdxPair PosPair = IdxPair(Nodes, 0);
     132      246023 :   unsigned Sum = 0;
     133      888665 :   for (unsigned n = 0; n != Nodes; ++n) {
     134      642642 :     Sum += NewSize[n] = PerNode + (n < Extra);
     135      642642 :     if (PosPair.first == Nodes && Sum > Position)
     136      738069 :       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      246023 :   if (Grow) {
     142             :     assert(PosPair.first < Nodes && "Bad algebra");
     143             :     assert(NewSize[PosPair.first] && "Too few elements to need Grow");
     144      246023 :     --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      246023 :   return PosPair;
     157             : }
     158             : 
     159             : } // namespace IntervalMapImpl
     160             : } // namespace llvm
     161             : 

Generated by: LCOV version 1.13