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-exception 6 // 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 16 namespace llvm { 17 namespace IntervalMapImpl { 18 19 void 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 25 NodeRef 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 48 void 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 75 NodeRef 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 98 void 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 have 107 // 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 120 IdxPair 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 NDEBUG 148 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 #endif 155 156 return PosPair; 157 } 158 159 } // namespace IntervalMapImpl 160 } // namespace llvm 161 162