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 61