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