IntervalMap.cpp revision 259065
11541Srgrimes//===- lib/Support/IntervalMap.cpp - A sorted interval map ----------------===// 21541Srgrimes// 31541Srgrimes// The LLVM Compiler Infrastructure 41541Srgrimes// 52124Sdg// This file is distributed under the University of Illinois Open Source 61541Srgrimes// License. See LICENSE.TXT for details. 71541Srgrimes// 81541Srgrimes//===----------------------------------------------------------------------===// 91541Srgrimes// 101541Srgrimes// This file implements the few non-templated functions in IntervalMap. 111541Srgrimes// 121541Srgrimes//===----------------------------------------------------------------------===// 131541Srgrimes 141541Srgrimes#include "llvm/ADT/IntervalMap.h" 151541Srgrimes 161541Srgrimesnamespace llvm { 171541Srgrimesnamespace IntervalMapImpl { 181541Srgrimes 191541Srgrimesvoid Path::replaceRoot(void *Root, unsigned Size, IdxPair Offsets) { 201541Srgrimes assert(!path.empty() && "Can't replace missing root"); 211541Srgrimes path.front() = Entry(Root, Size, Offsets.first); 221541Srgrimes path.insert(path.begin() + 1, Entry(subtree(0), Offsets.second)); 231541Srgrimes} 241541Srgrimes 251541SrgrimesNodeRef Path::getLeftSibling(unsigned Level) const { 261541Srgrimes // The root has no siblings. 271541Srgrimes if (Level == 0) 281541Srgrimes return NodeRef(); 291541Srgrimes 301541Srgrimes // Go up the tree until we can go left. 311541Srgrimes unsigned l = Level - 1; 321541Srgrimes while (l && path[l].offset == 0) 331541Srgrimes --l; 341541Srgrimes 351541Srgrimes // We can't go left. 361541Srgrimes if (path[l].offset == 0) 371541Srgrimes return NodeRef(); 381541Srgrimes 391541Srgrimes // NR is the subtree containing our left sibling. 401541Srgrimes NodeRef NR = path[l].subtree(path[l].offset - 1); 411541Srgrimes 421541Srgrimes // Keep right all the way down. 431541Srgrimes for (++l; l != Level; ++l) 441541Srgrimes NR = NR.subtree(NR.size() - 1); 451541Srgrimes return NR; 461541Srgrimes} 471541Srgrimes 481541Srgrimesvoid Path::moveLeft(unsigned Level) { 491541Srgrimes assert(Level != 0 && "Cannot move the root node"); 501541Srgrimes 511541Srgrimes // Go up the tree until we can go left. 521541Srgrimes unsigned l = 0; 531541Srgrimes if (valid()) { 541541Srgrimes l = Level - 1; 551541Srgrimes while (path[l].offset == 0) { 561541Srgrimes assert(l != 0 && "Cannot move beyond begin()"); 571541Srgrimes --l; 581541Srgrimes } 591541Srgrimes } else if (height() < Level) 601541Srgrimes // end() may have created a height=0 path. 611541Srgrimes path.resize(Level + 1, Entry(0, 0, 0)); 621541Srgrimes 631541Srgrimes // NR is the subtree containing our left sibling. 641541Srgrimes --path[l].offset; 651541Srgrimes NodeRef NR = subtree(l); 661541Srgrimes 671541Srgrimes // Get the rightmost node in the subtree. 681541Srgrimes for (++l; l != Level; ++l) { 691541Srgrimes path[l] = Entry(NR, NR.size() - 1); 701541Srgrimes NR = NR.subtree(NR.size() - 1); 711541Srgrimes } 721541Srgrimes path[l] = Entry(NR, NR.size() - 1); 731541Srgrimes} 741541Srgrimes 751541SrgrimesNodeRef Path::getRightSibling(unsigned Level) const { 761541Srgrimes // The root has no siblings. 771541Srgrimes if (Level == 0) 781541Srgrimes return NodeRef(); 791541Srgrimes 801541Srgrimes // Go up the tree until we can go right. 811541Srgrimes unsigned l = Level - 1; 821541Srgrimes while (l && atLastEntry(l)) 831541Srgrimes --l; 841541Srgrimes 851541Srgrimes // We can't go right. 861541Srgrimes if (atLastEntry(l)) 871541Srgrimes return NodeRef(); 881541Srgrimes 891541Srgrimes // NR is the subtree containing our right sibling. 901541Srgrimes NodeRef NR = path[l].subtree(path[l].offset + 1); 911541Srgrimes 921541Srgrimes // Keep left all the way down. 931541Srgrimes for (++l; l != Level; ++l) 941541Srgrimes NR = NR.subtree(0); 951541Srgrimes return NR; 961541Srgrimes} 971541Srgrimes 981541Srgrimesvoid Path::moveRight(unsigned Level) { 991541Srgrimes assert(Level != 0 && "Cannot move the root node"); 1001541Srgrimes 1011541Srgrimes // Go up the tree until we can go right. 1021541Srgrimes unsigned l = Level - 1; 1031541Srgrimes while (l && atLastEntry(l)) 1041541Srgrimes --l; 1051541Srgrimes 1061541Srgrimes // NR is the subtree containing our right sibling. If we hit end(), we have 1071541Srgrimes // offset(0) == node(0).size(). 1081541Srgrimes if (++path[l].offset == path[l].size) 1091541Srgrimes return; 1101541Srgrimes NodeRef NR = subtree(l); 1111541Srgrimes 1121541Srgrimes for (++l; l != Level; ++l) { 1131541Srgrimes path[l] = Entry(NR, 0); 1141541Srgrimes NR = NR.subtree(0); 1151541Srgrimes } 1161541Srgrimes path[l] = Entry(NR, 0); 1171541Srgrimes} 1181541Srgrimes 1191541Srgrimes 1201541SrgrimesIdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity, 1211541Srgrimes const unsigned *CurSize, unsigned NewSize[], 1221541Srgrimes unsigned Position, bool Grow) { 1231541Srgrimes assert(Elements + Grow <= Nodes * Capacity && "Not enough room for elements"); 1241541Srgrimes assert(Position <= Elements && "Invalid position"); 1251541Srgrimes if (!Nodes) 1261541Srgrimes return IdxPair(); 1271541Srgrimes 1281541Srgrimes // Trivial algorithm: left-leaning even distribution. 1291541Srgrimes const unsigned PerNode = (Elements + Grow) / Nodes; 1301541Srgrimes const unsigned Extra = (Elements + Grow) % Nodes; 1311541Srgrimes IdxPair PosPair = IdxPair(Nodes, 0); 1321541Srgrimes unsigned Sum = 0; 1331541Srgrimes for (unsigned n = 0; n != Nodes; ++n) { 1341541Srgrimes Sum += NewSize[n] = PerNode + (n < Extra); 1351541Srgrimes if (PosPair.first == Nodes && Sum > Position) 1361541Srgrimes PosPair = IdxPair(n, Position - (Sum - NewSize[n])); 1371541Srgrimes } 1381541Srgrimes assert(Sum == Elements + Grow && "Bad distribution sum"); 1391541Srgrimes 1401541Srgrimes // Subtract the Grow element that was added. 1411541Srgrimes if (Grow) { 1421541Srgrimes assert(PosPair.first < Nodes && "Bad algebra"); 1431541Srgrimes assert(NewSize[PosPair.first] && "Too few elements to need Grow"); 1441541Srgrimes --NewSize[PosPair.first]; 1451541Srgrimes } 1461541Srgrimes 1471541Srgrimes#ifndef NDEBUG 1481541Srgrimes Sum = 0; 1491541Srgrimes for (unsigned n = 0; n != Nodes; ++n) { 1501541Srgrimes assert(NewSize[n] <= Capacity && "Overallocated node"); 1511541Srgrimes Sum += NewSize[n]; 1521541Srgrimes } 1531541Srgrimes assert(Sum == Elements && "Bad distribution sum"); 1541541Srgrimes#endif 1551541Srgrimes 1561541Srgrimes return PosPair; 1571541Srgrimes} 1581541Srgrimes 1591541Srgrimes} // namespace IntervalMapImpl 1601541Srgrimes} // namespace llvm 1611541Srgrimes 1621541Srgrimes