IntervalMap.cpp revision 360660
1247738Sbapt//===- lib/Support/IntervalMap.cpp - A sorted interval map ----------------===// 2247738Sbapt// 3247738Sbapt// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4247738Sbapt// See https://llvm.org/LICENSE.txt for license information. 5247738Sbapt// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6247738Sbapt// 7247738Sbapt//===----------------------------------------------------------------------===// 8247738Sbapt// 9247738Sbapt// This file implements the few non-templated functions in IntervalMap. 10247738Sbapt// 11247738Sbapt//===----------------------------------------------------------------------===// 12247738Sbapt 13247738Sbapt#include "llvm/ADT/IntervalMap.h" 14247738Sbapt 15247738Sbaptnamespace llvm { 16247738Sbaptnamespace IntervalMapImpl { 17247738Sbapt 18247738Sbaptvoid Path::replaceRoot(void *Root, unsigned Size, IdxPair Offsets) { 19247738Sbapt assert(!path.empty() && "Can't replace missing root"); 20247738Sbapt path.front() = Entry(Root, Size, Offsets.first); 21247738Sbapt path.insert(path.begin() + 1, Entry(subtree(0), Offsets.second)); 22247738Sbapt} 23247738Sbapt 24247738SbaptNodeRef Path::getLeftSibling(unsigned Level) const { 25247738Sbapt // The root has no siblings. 26247738Sbapt if (Level == 0) 27247738Sbapt return NodeRef(); 28247738Sbapt 29247738Sbapt // Go up the tree until we can go left. 30247738Sbapt unsigned l = Level - 1; 31247738Sbapt while (l && path[l].offset == 0) 32247738Sbapt --l; 33247738Sbapt 34247738Sbapt // We can't go left. 35247738Sbapt if (path[l].offset == 0) 36247738Sbapt return NodeRef(); 37247738Sbapt 38247738Sbapt // NR is the subtree containing our left sibling. 39247738Sbapt NodeRef NR = path[l].subtree(path[l].offset - 1); 40247738Sbapt 41247738Sbapt // Keep right all the way down. 42247738Sbapt for (++l; l != Level; ++l) 43247738Sbapt NR = NR.subtree(NR.size() - 1); 44247738Sbapt return NR; 45247738Sbapt} 46247738Sbapt 47247738Sbaptvoid Path::moveLeft(unsigned Level) { 48247738Sbapt assert(Level != 0 && "Cannot move the root node"); 49247738Sbapt 50247738Sbapt // Go up the tree until we can go left. 51247738Sbapt unsigned l = 0; 52247738Sbapt if (valid()) { 53247738Sbapt l = Level - 1; 54247738Sbapt while (path[l].offset == 0) { 55247738Sbapt assert(l != 0 && "Cannot move beyond begin()"); 56247738Sbapt --l; 57247738Sbapt } 58247738Sbapt } else if (height() < Level) 59247738Sbapt // end() may have created a height=0 path. 60247738Sbapt path.resize(Level + 1, Entry(nullptr, 0, 0)); 61247738Sbapt 62247738Sbapt // NR is the subtree containing our left sibling. 63247738Sbapt --path[l].offset; 64247738Sbapt NodeRef NR = subtree(l); 65247738Sbapt 66247738Sbapt // Get the rightmost node in the subtree. 67247738Sbapt for (++l; l != Level; ++l) { 68247738Sbapt path[l] = Entry(NR, NR.size() - 1); 69247738Sbapt NR = NR.subtree(NR.size() - 1); 70247738Sbapt } 71247738Sbapt path[l] = Entry(NR, NR.size() - 1); 72247738Sbapt} 73247738Sbapt 74247738SbaptNodeRef Path::getRightSibling(unsigned Level) const { 75247738Sbapt // The root has no siblings. 76247738Sbapt if (Level == 0) 77247738Sbapt return NodeRef(); 78247738Sbapt 79247738Sbapt // Go up the tree until we can go right. 80247738Sbapt unsigned l = Level - 1; 81247738Sbapt while (l && atLastEntry(l)) 82247738Sbapt --l; 83247738Sbapt 84247738Sbapt // We can't go right. 85247738Sbapt if (atLastEntry(l)) 86247738Sbapt return NodeRef(); 87247738Sbapt 88247738Sbapt // NR is the subtree containing our right sibling. 89247738Sbapt NodeRef NR = path[l].subtree(path[l].offset + 1); 90247738Sbapt 91247738Sbapt // Keep left all the way down. 92247738Sbapt for (++l; l != Level; ++l) 93247738Sbapt NR = NR.subtree(0); 94247738Sbapt return NR; 95247738Sbapt} 96247738Sbapt 97247738Sbaptvoid Path::moveRight(unsigned Level) { 98247738Sbapt assert(Level != 0 && "Cannot move the root node"); 99247738Sbapt 100247738Sbapt // Go up the tree until we can go right. 101247738Sbapt unsigned l = Level - 1; 102247738Sbapt while (l && atLastEntry(l)) 103247738Sbapt --l; 104247738Sbapt 105247738Sbapt // NR is the subtree containing our right sibling. If we hit end(), we have 106247738Sbapt // offset(0) == node(0).size(). 107247738Sbapt if (++path[l].offset == path[l].size) 108247738Sbapt return; 109247738Sbapt NodeRef NR = subtree(l); 110247738Sbapt 111247738Sbapt for (++l; l != Level; ++l) { 112247738Sbapt path[l] = Entry(NR, 0); 113247738Sbapt NR = NR.subtree(0); 114247738Sbapt } 115247738Sbapt path[l] = Entry(NR, 0); 116247738Sbapt} 117247738Sbapt 118247738Sbapt 119247738SbaptIdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity, 120247738Sbapt const unsigned *CurSize, unsigned NewSize[], 121247738Sbapt unsigned Position, bool Grow) { 122247738Sbapt assert(Elements + Grow <= Nodes * Capacity && "Not enough room for elements"); 123247738Sbapt assert(Position <= Elements && "Invalid position"); 124247738Sbapt if (!Nodes) 125247738Sbapt return IdxPair(); 126247738Sbapt 127247738Sbapt // Trivial algorithm: left-leaning even distribution. 128247738Sbapt const unsigned PerNode = (Elements + Grow) / Nodes; 129247738Sbapt const unsigned Extra = (Elements + Grow) % Nodes; 130247738Sbapt IdxPair PosPair = IdxPair(Nodes, 0); 131247738Sbapt unsigned Sum = 0; 132247738Sbapt for (unsigned n = 0; n != Nodes; ++n) { 133247738Sbapt Sum += NewSize[n] = PerNode + (n < Extra); 134247738Sbapt if (PosPair.first == Nodes && Sum > Position) 135247738Sbapt PosPair = IdxPair(n, Position - (Sum - NewSize[n])); 136247738Sbapt } 137247738Sbapt assert(Sum == Elements + Grow && "Bad distribution sum"); 138247738Sbapt 139247738Sbapt // Subtract the Grow element that was added. 140247738Sbapt if (Grow) { 141247738Sbapt assert(PosPair.first < Nodes && "Bad algebra"); 142247738Sbapt assert(NewSize[PosPair.first] && "Too few elements to need Grow"); 143247738Sbapt --NewSize[PosPair.first]; 144247738Sbapt } 145247738Sbapt 146247738Sbapt#ifndef NDEBUG 147247738Sbapt Sum = 0; 148247738Sbapt for (unsigned n = 0; n != Nodes; ++n) { 149247738Sbapt assert(NewSize[n] <= Capacity && "Overallocated node"); 150247738Sbapt Sum += NewSize[n]; 151247738Sbapt } 152247738Sbapt assert(Sum == Elements && "Bad distribution sum"); 153247738Sbapt#endif 154247738Sbapt 155247738Sbapt return PosPair; 156247738Sbapt} 157247738Sbapt 158247738Sbapt} // namespace IntervalMapImpl 159247738Sbapt} // namespace llvm 160247738Sbapt 161247738Sbapt