lib/Support/IntervalMap.cpp

   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 IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,
  20                    const unsigned *CurSize, unsigned NewSize[],
  21                    unsigned Position, bool Grow) {
  22   assert(Elements + Grow <= Nodes * Capacity && "Not enough room for elements");
  23   assert(Position <= Elements && "Invalid position");
  24   if (!Nodes)
  25     return IdxPair();
  26
  27   // Trivial algorithm: left-leaning even distribution.
  28   const unsigned PerNode = (Elements + Grow) / Nodes;
  29   const unsigned Extra = (Elements + Grow) % Nodes;
  30   IdxPair PosPair = IdxPair(Nodes, 0);
  31   unsigned Sum = 0;
  32   for (unsigned n = 0; n != Nodes; ++n) {
  33     Sum += NewSize[n] = PerNode + (n < Extra);
  34     if (PosPair.first == Nodes && Sum > Position)
  35       PosPair = IdxPair(n, Position - (Sum - NewSize[n]));
  36   }
  37   assert(Sum == Elements + Grow && "Bad distribution sum");
  38
  39   // Subtract the Grow element that was added.
  40   if (Grow) {
  41     assert(PosPair.first < Nodes && "Bad algebra");
  42     assert(NewSize[PosPair.first] && "Too few elements to need Grow");
  43     --NewSize[PosPair.first];
  44   }
  45
  46 #ifndef NDEBUG
  47   Sum = 0;
  48   for (unsigned n = 0; n != Nodes; ++n) {
  49     assert(NewSize[n] <= Capacity && "Overallocated node");
  50     Sum += NewSize[n];
  51   }
  52   assert(Sum == Elements && "Bad distribution sum");
  53 #endif
  54
  55   return PosPair;
  56 }
  57
  58 } // namespace IntervalMapImpl
  59 } // namespace llvm
  60