162 lines · cpp
1//===- lib/Support/IntervalMap.cpp - A sorted interval map ----------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the few non-templated functions in IntervalMap.10//11//===----------------------------------------------------------------------===//12 13#include "llvm/ADT/IntervalMap.h"14#include <cassert>15 16namespace llvm {17namespace IntervalMapImpl {18 19void Path::replaceRoot(void *Root, unsigned Size, IdxPair Offsets) {20 assert(!path.empty() && "Can't replace missing root");21 path.front() = Entry(Root, Size, Offsets.first);22 path.insert(path.begin() + 1, Entry(subtree(0), Offsets.second));23}24 25NodeRef Path::getLeftSibling(unsigned Level) const {26 // The root has no siblings.27 if (Level == 0)28 return NodeRef();29 30 // Go up the tree until we can go left.31 unsigned l = Level - 1;32 while (l && path[l].offset == 0)33 --l;34 35 // We can't go left.36 if (path[l].offset == 0)37 return NodeRef();38 39 // NR is the subtree containing our left sibling.40 NodeRef NR = path[l].subtree(path[l].offset - 1);41 42 // Keep right all the way down.43 for (++l; l != Level; ++l)44 NR = NR.subtree(NR.size() - 1);45 return NR;46}47 48void Path::moveLeft(unsigned Level) {49 assert(Level != 0 && "Cannot move the root node");50 51 // Go up the tree until we can go left.52 unsigned l = 0;53 if (valid()) {54 l = Level - 1;55 while (path[l].offset == 0) {56 assert(l != 0 && "Cannot move beyond begin()");57 --l;58 }59 } else if (height() < Level)60 // end() may have created a height=0 path.61 path.resize(Level + 1, Entry(nullptr, 0, 0));62 63 // NR is the subtree containing our left sibling.64 --path[l].offset;65 NodeRef NR = subtree(l);66 67 // Get the rightmost node in the subtree.68 for (++l; l != Level; ++l) {69 path[l] = Entry(NR, NR.size() - 1);70 NR = NR.subtree(NR.size() - 1);71 }72 path[l] = Entry(NR, NR.size() - 1);73}74 75NodeRef Path::getRightSibling(unsigned Level) const {76 // The root has no siblings.77 if (Level == 0)78 return NodeRef();79 80 // Go up the tree until we can go right.81 unsigned l = Level - 1;82 while (l && atLastEntry(l))83 --l;84 85 // We can't go right.86 if (atLastEntry(l))87 return NodeRef();88 89 // NR is the subtree containing our right sibling.90 NodeRef NR = path[l].subtree(path[l].offset + 1);91 92 // Keep left all the way down.93 for (++l; l != Level; ++l)94 NR = NR.subtree(0);95 return NR;96}97 98void Path::moveRight(unsigned Level) {99 assert(Level != 0 && "Cannot move the root node");100 101 // Go up the tree until we can go right.102 unsigned l = Level - 1;103 while (l && atLastEntry(l))104 --l;105 106 // NR is the subtree containing our right sibling. If we hit end(), we have107 // offset(0) == node(0).size().108 if (++path[l].offset == path[l].size)109 return;110 NodeRef NR = subtree(l);111 112 for (++l; l != Level; ++l) {113 path[l] = Entry(NR, 0);114 NR = NR.subtree(0);115 }116 path[l] = Entry(NR, 0);117}118 119 120IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,121 const unsigned *CurSize, unsigned NewSize[],122 unsigned Position, bool Grow) {123 assert(Elements + Grow <= Nodes * Capacity && "Not enough room for elements");124 assert(Position <= Elements && "Invalid position");125 if (!Nodes)126 return IdxPair();127 128 // Trivial algorithm: left-leaning even distribution.129 const unsigned PerNode = (Elements + Grow) / Nodes;130 const unsigned Extra = (Elements + Grow) % Nodes;131 IdxPair PosPair = IdxPair(Nodes, 0);132 unsigned Sum = 0;133 for (unsigned n = 0; n != Nodes; ++n) {134 Sum += NewSize[n] = PerNode + (n < Extra);135 if (PosPair.first == Nodes && Sum > Position)136 PosPair = IdxPair(n, Position - (Sum - NewSize[n]));137 }138 assert(Sum == Elements + Grow && "Bad distribution sum");139 140 // Subtract the Grow element that was added.141 if (Grow) {142 assert(PosPair.first < Nodes && "Bad algebra");143 assert(NewSize[PosPair.first] && "Too few elements to need Grow");144 --NewSize[PosPair.first];145 }146 147#ifndef NDEBUG148 Sum = 0;149 for (unsigned n = 0; n != Nodes; ++n) {150 assert(NewSize[n] <= Capacity && "Overallocated node");151 Sum += NewSize[n];152 }153 assert(Sum == Elements && "Bad distribution sum");154#endif155 156 return PosPair;157}158 159} // namespace IntervalMapImpl160} // namespace llvm161 162