/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */
package org.apache.cassandra.utils.btree;

import org.apache.cassandra.utils.ObjectSizes;

import java.util.Arrays;
import java.util.Comparator;

import static org.apache.cassandra.utils.btree.BTree.*;

Represents a level / stack item of in progress modifications to a BTree.
/** * Represents a level / stack item of in progress modifications to a BTree. */
final class NodeBuilder { private static final int MAX_KEYS = 1 + (FAN_FACTOR * 2); // parent stack private NodeBuilder parent, child; // buffer for building new nodes private Object[] buildKeys = new Object[MAX_KEYS]; // buffers keys for branches and leaves private Object[] buildChildren = new Object[1 + MAX_KEYS]; // buffers children for branches only private int buildKeyPosition; private int buildChildPosition; // we null out the contents of buildKeys/buildChildren when clear()ing them for re-use; this is where // we track how much we actually have to null out private int maxBuildKeyPosition; // current node of the btree we're modifying/copying from private Object[] copyFrom; // the index of the first key in copyFrom that has not yet been copied into the build arrays private int copyFromKeyPosition; // the index of the first child node in copyFrom that has not yet been copied into the build arrays private int copyFromChildPosition; private UpdateFunction updateFunction; private Comparator comparator; // upper bound of range owned by this level; lets us know if we need to ascend back up the tree // for the next key we update when bsearch gives an insertion point past the end of the values // in the current node private Object upperBound; // ensure we aren't referencing any garbage void clear() { NodeBuilder current = this; while (current != null && current.upperBound != null) { current.clearSelf(); current = current.child; } current = parent; while (current != null && current.upperBound != null) { current.clearSelf(); current = current.parent; } } void clearSelf() { reset(null, null, null, null); Arrays.fill(buildKeys, 0, maxBuildKeyPosition, null); Arrays.fill(buildChildren, 0, maxBuildKeyPosition + 1, null); maxBuildKeyPosition = 0; } // reset counters/setup to copy from provided node void reset(Object[] copyFrom, Object upperBound, UpdateFunction updateFunction, Comparator comparator) { this.copyFrom = copyFrom; this.upperBound = upperBound; this.updateFunction = updateFunction; this.comparator = comparator; maxBuildKeyPosition = Math.max(maxBuildKeyPosition, buildKeyPosition); buildKeyPosition = 0; buildChildPosition = 0; copyFromKeyPosition = 0; copyFromChildPosition = 0; } NodeBuilder finish() { assert copyFrom != null; int copyFromKeyEnd = getKeyEnd(copyFrom); if (buildKeyPosition + buildChildPosition > 0) { // only want to copy if we've already changed something, otherwise we'll return the original copyKeys(copyFromKeyEnd); if (!isLeaf(copyFrom)) copyChildren(copyFromKeyEnd + 1); } return isRoot() ? null : ascend(); }
Inserts or replaces the provided key, copying all not-yet-visited keys prior to it into our buffer.
Params:
  • key – key we are inserting/replacing
Returns:the NodeBuilder to retry the update against (a child if we own the range being updated, a parent if we do not -- we got here from an earlier key -- and we need to ascend back up), or null if we finished the update in this node.
/** * Inserts or replaces the provided key, copying all not-yet-visited keys prior to it into our buffer. * * @param key key we are inserting/replacing * @return the NodeBuilder to retry the update against (a child if we own the range being updated, * a parent if we do not -- we got here from an earlier key -- and we need to ascend back up), * or null if we finished the update in this node. */
NodeBuilder update(Object key) { assert copyFrom != null; int copyFromKeyEnd = getKeyEnd(copyFrom); int i = copyFromKeyPosition; boolean found; // exact key match? boolean owns = true; // true if this node (or a child) should contain the key if (i == copyFromKeyEnd) { found = false; } else { // this optimisation is for the common scenario of updating an existing row with the same columns/keys // and simply avoids performing a binary search until we've checked the proceeding key; // possibly we should disable this check if we determine that it fails more than a handful of times // during any given builder use to get the best of both worlds int c = -comparator.compare(key, copyFrom[i]); if (c >= 0) { found = c == 0; } else { i = Arrays.binarySearch(copyFrom, i + 1, copyFromKeyEnd, key, comparator); found = i >= 0; if (!found) i = -i - 1; } } if (found) { Object prev = copyFrom[i]; Object next = updateFunction.apply(prev, key); // we aren't actually replacing anything, so leave our state intact and continue if (prev == next) return null; key = next; } else if (i == copyFromKeyEnd && compareUpperBound(comparator, key, upperBound) >= 0) owns = false; if (isLeaf(copyFrom)) { if (owns) { // copy keys from the original node up to prior to the found index copyKeys(i); if (found) { // if found, we've applied updateFunction already replaceNextKey(key); } else { // if not found, we need to apply updateFunction still, which is handled in addNewKey addNewKey(key); } // done, so return null return null; } else { // we don't want to copy anything if we're ascending and haven't copied anything previously, // as in this case we can return the original node. Leaving buildKeyPosition as 0 indicates // to buildFromRange that it should return the original instead of building a new node if (buildKeyPosition > 0) copyKeys(i); } // if we don't own it, all we need to do is ensure we've copied everything in this node // (which we have done, since not owning means pos >= keyEnd), ascend, and let Modifier.update // retry against the parent node. The if/ascend after the else branch takes care of that. } else { // branch if (found) { copyKeys(i); replaceNextKey(key); copyChildren(i + 1); return null; } else if (owns) { copyKeys(i); copyChildren(i); // belongs to the range owned by this node, but not equal to any key in the node // so descend into the owning child Object newUpperBound = i < copyFromKeyEnd ? copyFrom[i] : upperBound; Object[] descendInto = (Object[]) copyFrom[copyFromKeyEnd + i]; ensureChild().reset(descendInto, newUpperBound, updateFunction, comparator); return child; } else if (buildKeyPosition > 0 || buildChildPosition > 0) { // ensure we've copied all keys and children, but only if we've already copied something. // otherwise we want to return the original node copyKeys(copyFromKeyEnd); copyChildren(copyFromKeyEnd + 1); // since we know that there are exactly 1 more child nodes, than keys } } return ascend(); } private static <V> int compareUpperBound(Comparator<V> comparator, Object value, Object upperBound) { return upperBound == POSITIVE_INFINITY ? -1 : comparator.compare((V)value, (V)upperBound); } // UTILITY METHODS FOR IMPLEMENTATION OF UPDATE/BUILD/DELETE boolean isRoot() { // if parent == null, or parent.upperBound == null, then we have not initialised a parent builder, // so we are the top level builder holding modifications; if we have more than FAN_FACTOR items, though, // we are not a valid root so we would need to spill-up to create a new root return (parent == null || parent.upperBound == null) && buildKeyPosition <= FAN_FACTOR; } // ascend to the root node, splitting into proper node sizes as we go; useful for building // where we work only on the newest child node, which may construct many spill-over parents as it goes NodeBuilder ascendToRoot() { NodeBuilder current = this; while (!current.isRoot()) current = current.ascend(); return current; } // builds a new root BTree node - must be called on root of operation Object[] toNode() { // we permit building empty trees as some constructions do not know in advance how many items they will contain assert buildKeyPosition <= FAN_FACTOR : buildKeyPosition; return buildFromRange(0, buildKeyPosition, isLeaf(copyFrom), false); } // finish up this level and pass any constructed children up to our parent, ensuring a parent exists private NodeBuilder ascend() { ensureParent(); boolean isLeaf = isLeaf(copyFrom); if (buildKeyPosition > FAN_FACTOR) { // split current node and move the midpoint into parent, with the two halves as children int mid = buildKeyPosition / 2; parent.addExtraChild(buildFromRange(0, mid, isLeaf, true), buildKeys[mid]); parent.finishChild(buildFromRange(mid + 1, buildKeyPosition - (mid + 1), isLeaf, false)); } else { parent.finishChild(buildFromRange(0, buildKeyPosition, isLeaf, false)); } return parent; } // copy keys from copyf to the builder, up to the provided index in copyf (exclusive) private void copyKeys(int upToKeyPosition) { if (copyFromKeyPosition >= upToKeyPosition) return; int len = upToKeyPosition - copyFromKeyPosition; assert len <= FAN_FACTOR : upToKeyPosition + "," + copyFromKeyPosition; ensureRoom(buildKeyPosition + len); if (len > 0) { System.arraycopy(copyFrom, copyFromKeyPosition, buildKeys, buildKeyPosition, len); copyFromKeyPosition = upToKeyPosition; buildKeyPosition += len; } } // skips the next key in copyf, and puts the provided key in the builder instead private void replaceNextKey(Object with) { // (this first part differs from addNewKey in that we pass the replaced object to replaceF as well) ensureRoom(buildKeyPosition + 1); buildKeys[buildKeyPosition++] = with; copyFromKeyPosition++; } // applies the updateFunction // puts the resulting key into the builder // splits the parent if necessary via ensureRoom void addNewKey(Object key) { ensureRoom(buildKeyPosition + 1); buildKeys[buildKeyPosition++] = updateFunction.apply(key); } // copies children from copyf to the builder, up to the provided index in copyf (exclusive) private void copyChildren(int upToChildPosition) { // (ensureRoom isn't called here, as we should always be at/behind key additions) if (copyFromChildPosition >= upToChildPosition) return; int len = upToChildPosition - copyFromChildPosition; if (len > 0) { System.arraycopy(copyFrom, getKeyEnd(copyFrom) + copyFromChildPosition, buildChildren, buildChildPosition, len); copyFromChildPosition = upToChildPosition; buildChildPosition += len; } } // adds a new and unexpected child to the builder - called by children that overflow private void addExtraChild(Object[] child, Object upperBound) { ensureRoom(buildKeyPosition + 1); buildKeys[buildKeyPosition++] = upperBound; buildChildren[buildChildPosition++] = child; } // adds a replacement expected child to the builder - called by children prior to ascending private void finishChild(Object[] child) { buildChildren[buildChildPosition++] = child; copyFromChildPosition++; } // checks if we can add the requested keys+children to the builder, and if not we spill-over into our parent private void ensureRoom(int nextBuildKeyPosition) { if (nextBuildKeyPosition < MAX_KEYS) return; // flush even number of items so we don't waste leaf space repeatedly Object[] flushUp = buildFromRange(0, FAN_FACTOR, isLeaf(copyFrom), true); ensureParent().addExtraChild(flushUp, buildKeys[FAN_FACTOR]); int size = FAN_FACTOR + 1; assert size <= buildKeyPosition : buildKeyPosition + "," + nextBuildKeyPosition; System.arraycopy(buildKeys, size, buildKeys, 0, buildKeyPosition - size); buildKeyPosition -= size; maxBuildKeyPosition = buildKeys.length; if (buildChildPosition > 0) { System.arraycopy(buildChildren, size, buildChildren, 0, buildChildPosition - size); buildChildPosition -= size; } } // builds and returns a node from the buffered objects in the given range private Object[] buildFromRange(int offset, int keyLength, boolean isLeaf, boolean isExtra) { // if keyLength is 0, we didn't copy anything from the original, which means we didn't // modify any of the range owned by it, so can simply return it as is if (keyLength == 0) return copyFrom; Object[] a; if (isLeaf) { a = new Object[keyLength | 1]; System.arraycopy(buildKeys, offset, a, 0, keyLength); } else { a = new Object[2 + (keyLength * 2)]; System.arraycopy(buildKeys, offset, a, 0, keyLength); System.arraycopy(buildChildren, offset, a, keyLength, keyLength + 1); // calculate the indexOffsets of each key in this node, within the sub-tree rooted at this node int[] indexOffsets = new int[keyLength + 1]; int size = BTree.size((Object[]) a[keyLength]); for (int i = 0 ; i < keyLength ; i++) { indexOffsets[i] = size; size += 1 + BTree.size((Object[]) a[keyLength + 1 + i]); } indexOffsets[keyLength] = size; a[a.length - 1] = indexOffsets; } if (isExtra) updateFunction.allocated(ObjectSizes.sizeOfArray(a)); else if (a.length != copyFrom.length) updateFunction.allocated(ObjectSizes.sizeOfArray(a) - (copyFrom.length == 0 ? 0 : ObjectSizes.sizeOfArray(copyFrom))); return a; } // checks if there is an initialised parent, and if not creates/initialises one and returns it. // different to ensureChild, as we initialise here instead of caller, as parents in general should // already be initialised, and only aren't in the case where we are overflowing the original root node private NodeBuilder ensureParent() { if (parent == null) { parent = new NodeBuilder(); parent.child = this; } if (parent.upperBound == null) parent.reset(EMPTY_BRANCH, upperBound, updateFunction, comparator); return parent; } // ensures a child level exists and returns it NodeBuilder ensureChild() { if (child == null) { child = new NodeBuilder(); child.parent = this; } return child; } }