rebalanceAfterRemove "unsplits" n and its ancestors if they are deficient (contain fewer segments than required by B-tree invariants), as required for removal, and returns an updated iterator to the position represented by gap. Precondition: n is the only node in the tree that may currently violate
(gap GapIterator)
| 1243 | // Precondition: n is the only node in the tree that may currently violate a |
| 1244 | // B-tree invariant. |
| 1245 | func (n *node) rebalanceAfterRemove(gap GapIterator) GapIterator { |
| 1246 | for { |
| 1247 | if n.nrSegments >= minDegree-1 { |
| 1248 | return gap |
| 1249 | } |
| 1250 | if n.parent == nil { |
| 1251 | // Root is allowed to be deficient. |
| 1252 | return gap |
| 1253 | } |
| 1254 | // There's one other thing we can do before resorting to unsplitting. |
| 1255 | // If either sibling node has at least minDegree segments, rotate that |
| 1256 | // sibling's closest segment through the segment in the parent that |
| 1257 | // separates us. That is, given: |
| 1258 | // |
| 1259 | // ... D ... |
| 1260 | // / \ |
| 1261 | // ... B C] [E ... |
| 1262 | // |
| 1263 | // where the node containing E is deficient, end up with: |
| 1264 | // |
| 1265 | // ... C ... |
| 1266 | // / \ |
| 1267 | // ... B] [D E ... |
| 1268 | // |
| 1269 | // As in Set.Remove, prefer rotating from the end of the sibling to the |
| 1270 | // left: by precondition, n.node has fewer segments (to memcpy) than |
| 1271 | // the sibling does. |
| 1272 | if sibling := n.prevSibling(); sibling != nil && sibling.nrSegments >= minDegree { |
| 1273 | copy(n.keys[1:], n.keys[:n.nrSegments]) |
| 1274 | copy(n.values[1:], n.values[:n.nrSegments]) |
| 1275 | n.keys[0] = n.parent.keys[n.parentIndex-1] |
| 1276 | n.values[0] = n.parent.values[n.parentIndex-1] |
| 1277 | n.parent.keys[n.parentIndex-1] = sibling.keys[sibling.nrSegments-1] |
| 1278 | n.parent.values[n.parentIndex-1] = sibling.values[sibling.nrSegments-1] |
| 1279 | Functions{}.ClearValue(&sibling.values[sibling.nrSegments-1]) |
| 1280 | if n.hasChildren { |
| 1281 | copy(n.children[1:], n.children[:n.nrSegments+1]) |
| 1282 | n.children[0] = sibling.children[sibling.nrSegments] |
| 1283 | sibling.children[sibling.nrSegments] = nil |
| 1284 | n.children[0].parent = n |
| 1285 | n.children[0].parentIndex = 0 |
| 1286 | for i := 1; i < n.nrSegments+2; i++ { |
| 1287 | n.children[i].parentIndex = i |
| 1288 | } |
| 1289 | } |
| 1290 | n.nrSegments++ |
| 1291 | sibling.nrSegments-- |
| 1292 | // n's parent's maxGap does not need to be updated as its content is unmodified. |
| 1293 | // n and its sibling must be updated with (new) maxGap because of the shift of keys. |
| 1294 | if trackGaps != 0 { |
| 1295 | n.updateMaxGapLocal() |
| 1296 | sibling.updateMaxGapLocal() |
| 1297 | } |
| 1298 | if gap.node == sibling && gap.index == sibling.nrSegments { |
| 1299 | return GapIterator{n, 0} |
| 1300 | } |
| 1301 | if gap.node == n { |
| 1302 | return GapIterator{n, gap.index + 1} |
no test coverage detected