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