1218885Sdim//===- lib/Support/IntervalMap.cpp - A sorted interval map ----------------===// 2218885Sdim// 3218885Sdim// The LLVM Compiler Infrastructure 4218885Sdim// 5218885Sdim// This file is distributed under the University of Illinois Open Source 6218885Sdim// License. See LICENSE.TXT for details. 7218885Sdim// 8218885Sdim//===----------------------------------------------------------------------===// 9218885Sdim// 10218885Sdim// This file implements the few non-templated functions in IntervalMap. 11218885Sdim// 12218885Sdim//===----------------------------------------------------------------------===// 13218885Sdim 14218885Sdim#include "llvm/ADT/IntervalMap.h" 15218885Sdim 16218885Sdimnamespace llvm { 17218885Sdimnamespace IntervalMapImpl { 18218885Sdim 19218885Sdimvoid Path::replaceRoot(void *Root, unsigned Size, IdxPair Offsets) { 20218885Sdim assert(!path.empty() && "Can't replace missing root"); 21218885Sdim path.front() = Entry(Root, Size, Offsets.first); 22218885Sdim path.insert(path.begin() + 1, Entry(subtree(0), Offsets.second)); 23218885Sdim} 24218885Sdim 25218885SdimNodeRef Path::getLeftSibling(unsigned Level) const { 26218885Sdim // The root has no siblings. 27218885Sdim if (Level == 0) 28218885Sdim return NodeRef(); 29218885Sdim 30218885Sdim // Go up the tree until we can go left. 31218885Sdim unsigned l = Level - 1; 32218885Sdim while (l && path[l].offset == 0) 33218885Sdim --l; 34218885Sdim 35218885Sdim // We can't go left. 36218885Sdim if (path[l].offset == 0) 37218885Sdim return NodeRef(); 38218885Sdim 39218885Sdim // NR is the subtree containing our left sibling. 40218885Sdim NodeRef NR = path[l].subtree(path[l].offset - 1); 41218885Sdim 42218885Sdim // Keep right all the way down. 43218885Sdim for (++l; l != Level; ++l) 44218885Sdim NR = NR.subtree(NR.size() - 1); 45218885Sdim return NR; 46218885Sdim} 47218885Sdim 48218885Sdimvoid Path::moveLeft(unsigned Level) { 49218885Sdim assert(Level != 0 && "Cannot move the root node"); 50218885Sdim 51218885Sdim // Go up the tree until we can go left. 52218885Sdim unsigned l = 0; 53218885Sdim if (valid()) { 54218885Sdim l = Level - 1; 55218885Sdim while (path[l].offset == 0) { 56218885Sdim assert(l != 0 && "Cannot move beyond begin()"); 57218885Sdim --l; 58218885Sdim } 59218885Sdim } else if (height() < Level) 60218885Sdim // end() may have created a height=0 path. 61218885Sdim path.resize(Level + 1, Entry(0, 0, 0)); 62218885Sdim 63218885Sdim // NR is the subtree containing our left sibling. 64218885Sdim --path[l].offset; 65218885Sdim NodeRef NR = subtree(l); 66218885Sdim 67218885Sdim // Get the rightmost node in the subtree. 68218885Sdim for (++l; l != Level; ++l) { 69218885Sdim path[l] = Entry(NR, NR.size() - 1); 70218885Sdim NR = NR.subtree(NR.size() - 1); 71218885Sdim } 72218885Sdim path[l] = Entry(NR, NR.size() - 1); 73218885Sdim} 74218885Sdim 75218885SdimNodeRef Path::getRightSibling(unsigned Level) const { 76218885Sdim // The root has no siblings. 77218885Sdim if (Level == 0) 78218885Sdim return NodeRef(); 79218885Sdim 80218885Sdim // Go up the tree until we can go right. 81218885Sdim unsigned l = Level - 1; 82218885Sdim while (l && atLastEntry(l)) 83218885Sdim --l; 84218885Sdim 85218885Sdim // We can't go right. 86218885Sdim if (atLastEntry(l)) 87218885Sdim return NodeRef(); 88218885Sdim 89218885Sdim // NR is the subtree containing our right sibling. 90218885Sdim NodeRef NR = path[l].subtree(path[l].offset + 1); 91218885Sdim 92218885Sdim // Keep left all the way down. 93218885Sdim for (++l; l != Level; ++l) 94218885Sdim NR = NR.subtree(0); 95218885Sdim return NR; 96218885Sdim} 97218885Sdim 98218885Sdimvoid Path::moveRight(unsigned Level) { 99218885Sdim assert(Level != 0 && "Cannot move the root node"); 100218885Sdim 101218885Sdim // Go up the tree until we can go right. 102218885Sdim unsigned l = Level - 1; 103218885Sdim while (l && atLastEntry(l)) 104218885Sdim --l; 105218885Sdim 106218885Sdim // NR is the subtree containing our right sibling. If we hit end(), we have 107218885Sdim // offset(0) == node(0).size(). 108218885Sdim if (++path[l].offset == path[l].size) 109218885Sdim return; 110218885Sdim NodeRef NR = subtree(l); 111218885Sdim 112218885Sdim for (++l; l != Level; ++l) { 113218885Sdim path[l] = Entry(NR, 0); 114218885Sdim NR = NR.subtree(0); 115218885Sdim } 116218885Sdim path[l] = Entry(NR, 0); 117218885Sdim} 118218885Sdim 119218885Sdim 120218885SdimIdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity, 121218885Sdim const unsigned *CurSize, unsigned NewSize[], 122218885Sdim unsigned Position, bool Grow) { 123218885Sdim assert(Elements + Grow <= Nodes * Capacity && "Not enough room for elements"); 124218885Sdim assert(Position <= Elements && "Invalid position"); 125218885Sdim if (!Nodes) 126218885Sdim return IdxPair(); 127218885Sdim 128218885Sdim // Trivial algorithm: left-leaning even distribution. 129218885Sdim const unsigned PerNode = (Elements + Grow) / Nodes; 130218885Sdim const unsigned Extra = (Elements + Grow) % Nodes; 131218885Sdim IdxPair PosPair = IdxPair(Nodes, 0); 132218885Sdim unsigned Sum = 0; 133218885Sdim for (unsigned n = 0; n != Nodes; ++n) { 134218885Sdim Sum += NewSize[n] = PerNode + (n < Extra); 135218885Sdim if (PosPair.first == Nodes && Sum > Position) 136218885Sdim PosPair = IdxPair(n, Position - (Sum - NewSize[n])); 137218885Sdim } 138218885Sdim assert(Sum == Elements + Grow && "Bad distribution sum"); 139218885Sdim 140218885Sdim // Subtract the Grow element that was added. 141218885Sdim if (Grow) { 142218885Sdim assert(PosPair.first < Nodes && "Bad algebra"); 143218885Sdim assert(NewSize[PosPair.first] && "Too few elements to need Grow"); 144218885Sdim --NewSize[PosPair.first]; 145218885Sdim } 146218885Sdim 147218885Sdim#ifndef NDEBUG 148218885Sdim Sum = 0; 149218885Sdim for (unsigned n = 0; n != Nodes; ++n) { 150218885Sdim assert(NewSize[n] <= Capacity && "Overallocated node"); 151218885Sdim Sum += NewSize[n]; 152218885Sdim } 153218885Sdim assert(Sum == Elements && "Bad distribution sum"); 154218885Sdim#endif 155218885Sdim 156218885Sdim return PosPair; 157218885Sdim} 158218885Sdim 159218885Sdim} // namespace IntervalMapImpl 160218885Sdim} // namespace llvm 161218885Sdim 162