1 //===- lib/Support/IntervalMap.cpp - A sorted interval map ----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the few non-templated functions in IntervalMap.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/ADT/IntervalMap.h"
17 namespace IntervalMapImpl {
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");
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);
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]));
37 assert(Sum == Elements + Grow && "Bad distribution sum");
39 // Subtract the Grow element that was added.
41 assert(PosPair.first < Nodes && "Bad algebra");
42 assert(NewSize[PosPair.first] && "Too few elements to need Grow");
43 --NewSize[PosPair.first];
48 for (unsigned n = 0; n != Nodes; ++n) {
49 assert(NewSize[n] <= Capacity && "Overallocated node");
52 assert(Sum == Elements && "Bad distribution sum");
58 } // namespace IntervalMapImpl