18dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===- lib/Support/IntervalMap.cpp - A sorted interval map ----------------===// 28dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 38dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The LLVM Compiler Infrastructure 48dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 58dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 68dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// License. See LICENSE.TXT for details. 78dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 88dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 98dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// This file implements the few non-templated functions in IntervalMap. 118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen#include "llvm/ADT/IntervalMap.h" 158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesennamespace llvm { 178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesennamespace IntervalMapImpl { 188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 19706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesenvoid Path::replaceRoot(void *Root, unsigned Size, IdxPair Offsets) { 20706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen assert(!path.empty() && "Can't replace missing root"); 21706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.front() = Entry(Root, Size, Offsets.first); 22706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.insert(path.begin() + 1, Entry(subtree(0), Offsets.second)); 23706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen} 24706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 25706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund OlesenNodeRef Path::getLeftSibling(unsigned Level) const { 26706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // The root has no siblings. 27706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (Level == 0) 28706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return NodeRef(); 29706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 30706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Go up the tree until we can go left. 31706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned l = Level - 1; 32706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen while (l && path[l].offset == 0) 33706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen --l; 34706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 35706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // We can't go left. 36706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (path[l].offset == 0) 37706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return NodeRef(); 38706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 39706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // NR is the subtree containing our left sibling. 40706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef NR = path[l].subtree(path[l].offset - 1); 41706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 42706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Keep right all the way down. 43706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen for (++l; l != Level; ++l) 44706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NR = NR.subtree(NR.size() - 1); 45706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return NR; 46706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen} 47706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 48706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesenvoid Path::moveLeft(unsigned Level) { 49706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen assert(Level != 0 && "Cannot move the root node"); 50706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 51706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Go up the tree until we can go left. 52706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned l = 0; 53706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (valid()) { 54706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen l = Level - 1; 55706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen while (path[l].offset == 0) { 56706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen assert(l != 0 && "Cannot move beyond begin()"); 57706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen --l; 58706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 59706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } else if (height() < Level) 60706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // end() may have created a height=0 path. 61dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines path.resize(Level + 1, Entry(nullptr, 0, 0)); 62706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 63706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // NR is the subtree containing our left sibling. 64706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen --path[l].offset; 65706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef NR = subtree(l); 66706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 67706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Get the rightmost node in the subtree. 68706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen for (++l; l != Level; ++l) { 69706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path[l] = Entry(NR, NR.size() - 1); 70706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NR = NR.subtree(NR.size() - 1); 71706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 72706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path[l] = Entry(NR, NR.size() - 1); 73706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen} 74706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 75706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund OlesenNodeRef Path::getRightSibling(unsigned Level) const { 76706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // The root has no siblings. 77706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (Level == 0) 78706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return NodeRef(); 79706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 80706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Go up the tree until we can go right. 81706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned l = Level - 1; 827a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen while (l && atLastEntry(l)) 83706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen --l; 84706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 85706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // We can't go right. 867a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (atLastEntry(l)) 87706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return NodeRef(); 88706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 89706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // NR is the subtree containing our right sibling. 90706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef NR = path[l].subtree(path[l].offset + 1); 91706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 92706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Keep left all the way down. 93706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen for (++l; l != Level; ++l) 94706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NR = NR.subtree(0); 95706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return NR; 96706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen} 97706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 98706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesenvoid Path::moveRight(unsigned Level) { 99706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen assert(Level != 0 && "Cannot move the root node"); 100706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 101706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Go up the tree until we can go right. 102706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned l = Level - 1; 1037a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen while (l && atLastEntry(l)) 104706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen --l; 105706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 106706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // NR is the subtree containing our right sibling. If we hit end(), we have 107706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // offset(0) == node(0).size(). 108706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (++path[l].offset == path[l].size) 109706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return; 110706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef NR = subtree(l); 111706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 112706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen for (++l; l != Level; ++l) { 113706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path[l] = Entry(NR, 0); 114706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NR = NR.subtree(0); 115706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 116706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path[l] = Entry(NR, 0); 117706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen} 118706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 119706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund OlesenIdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity, 1218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const unsigned *CurSize, unsigned NewSize[], 1228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Position, bool Grow) { 1238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(Elements + Grow <= Nodes * Capacity && "Not enough room for elements"); 1248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(Position <= Elements && "Invalid position"); 1258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (!Nodes) 1268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return IdxPair(); 1278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Trivial algorithm: left-leaning even distribution. 1298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const unsigned PerNode = (Elements + Grow) / Nodes; 1308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const unsigned Extra = (Elements + Grow) % Nodes; 1318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen IdxPair PosPair = IdxPair(Nodes, 0); 1328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Sum = 0; 1338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned n = 0; n != Nodes; ++n) { 1348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Sum += NewSize[n] = PerNode + (n < Extra); 1358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (PosPair.first == Nodes && Sum > Position) 1368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen PosPair = IdxPair(n, Position - (Sum - NewSize[n])); 1378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(Sum == Elements + Grow && "Bad distribution sum"); 1398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Subtract the Grow element that was added. 1418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (Grow) { 1428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(PosPair.first < Nodes && "Bad algebra"); 1438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(NewSize[PosPair.first] && "Too few elements to need Grow"); 1448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen --NewSize[PosPair.first]; 1458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen#ifndef NDEBUG 1488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Sum = 0; 1498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned n = 0; n != Nodes; ++n) { 1508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(NewSize[n] <= Capacity && "Overallocated node"); 1518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Sum += NewSize[n]; 1528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(Sum == Elements && "Bad distribution sum"); 1548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen#endif 1558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return PosPair; 1578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 1588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} // namespace IntervalMapImpl 160706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen} // namespace llvm 1618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 162