Package org.apache.cassandra.utils.btree

Class BTree

java.lang.Object
org.apache.cassandra.utils.btree.BTree
public class BTree extends Object

  • Field Details

    • BRANCH_SHIFT

      public static final int BRANCH_SHIFT
      The BRANCH_FACTOR is defined as the maximum number of children of each branch, with between BRANCH_FACTOR/2-1 and BRANCH_FACTOR-1 keys being stored in every node. This yields a minimum tree size of (BRANCH_FACTOR/2)^height - 1 and a maximum tree size of BRANCH_FACTOR^height - 1.

      Branches differ from leaves only in that they contain a suffix region containing the child nodes that occur either side of the keys, and a sizeMap in the last position, permitting seeking by index within the tree. Nodes are disambiguated by the length of the array that represents them: an even number is a branch, odd a leaf.

      Leaf Nodes are represented by an odd-length array of keys, with the final element possibly null, i.e. Object[V1, V2, ...,null?]

      Branch nodes: Object[V1, V2, ..., child[<V1.key], child[<V2.key], ..., child[< Inf], sizeMap] Each child is either a branch or leaf, i.e., always an Object[]. The key elements in a branch node occupy the first half of the array (minus one)

      BTrees are immutable; updating one returns a new tree that reuses unmodified nodes.

      There are no references back to a parent node from its children (this would make it impossible to re-use subtrees when modifying the tree, since the modified tree would need new parent references). Instead, we store these references in a Path as needed when navigating the tree.

    • MIN_KEYS

      public static final int MIN_KEYS

    • MAX_KEYS

      public static final int MAX_KEYS

    • STOP_SENTINEL_VALUE

      public static final long STOP_SENTINEL_VALUE
      See Also:

  • Constructor Details

    • BTree

      public BTree()

  • Method Details

    • empty

      public static Object[] empty()
      Returns an empty BTree
      Returns:
      an empty BTree

    • singleton

      public static Object[] singleton(Object value)
      Create a BTree containing only the specified object
      Returns:
      an new BTree containing only the specified object

    • build

      @Deprecated(since="4.0") public static <C, K extends C, V extends C> Object[] build(Collection<K> source)
      Deprecated.
      See CASSANDRA-15510

    • build

      @Deprecated(since="4.0") public static <C, K extends C, V extends C> Object[] build(Collection<K> source, UpdateFunction<K,V> updateF)
      Deprecated.
      See CASSANDRA-15510

    • build

      public static <C, I extends C, O extends C> Object[] build(BulkIterator<I> source, int size, UpdateFunction<I,O> updateF)

    • update

      public static <Compare> Object[] update(Object[] toUpdate, Object[] insert, Comparator<? super Compare> comparator)

    • update

      public static <Compare, Existing extends Compare, Insert extends Compare> Object[] update(Object[] toUpdate, Object[] insert, Comparator<? super Compare> comparator, UpdateFunction<Insert,Existing> updateF)
      Inserts insert into update, applying updateF to each new item in insert, as well as any matched items in update.

      Note that UpdateFunction.noOp is assumed to indicate a lack of interest in which value survives.

    • updateLeaves

      public static <Compare, Existing extends Compare, Insert extends Compare> Object[] updateLeaves(Object[] unode, Object[] inode, Comparator<? super Compare> comparator, UpdateFunction<Insert,Existing> updateF)
      A fast tight-loop variant of updating one btree with another, when both are leaves.

    • reverseInSitu

      public static void reverseInSitu(Object[] tree)

    • iterator

      public static <V> Iterator<V> iterator(Object[] btree)

    • iterator

      public static <V> Iterator<V> iterator(Object[] btree, BTree.Dir dir)

    • iterator

      public static <V> Iterator<V> iterator(Object[] btree, int lb, int ub, BTree.Dir dir)

    • iterable

      public static <V> Iterable<V> iterable(Object[] btree)

    • iterable

      public static <V> Iterable<V> iterable(Object[] btree, BTree.Dir dir)

    • iterable

      public static <V> Iterable<V> iterable(Object[] btree, int lb, int ub, BTree.Dir dir)

    • slice

      public static <K, V> BTreeSearchIterator<K,V> slice(Object[] btree, Comparator<? super K> comparator, BTree.Dir dir)
      Returns an Iterator over the entire tree
      Type Parameters:
      V -
      Parameters:
      btree - the tree to iterate over
      dir - direction of iteration
      Returns:

    • slice

      public static <K, V extends K> BTreeSearchIterator<K,V> slice(Object[] btree, Comparator<? super K> comparator, K start, K end, BTree.Dir dir)
      Parameters:
      btree - the tree to iterate over
      comparator - the comparator that defines the ordering over the items in the tree
      start - the beginning of the range to return, inclusive (in ascending order)
      end - the end of the range to return, exclusive (in ascending order)
      dir - if false, the iterator will start at the last item and move backwards
      Returns:
      an Iterator over the defined sub-range of the tree

    • slice

      public static <K, V extends K> BTreeSearchIterator<K,V> slice(Object[] btree, Comparator<? super K> comparator, int startIndex, int endIndex, BTree.Dir dir)
      Parameters:
      btree - the tree to iterate over
      comparator - the comparator that defines the ordering over the items in the tree
      startIndex - the start index of the range to return, inclusive
      endIndex - the end index of the range to return, inclusive
      dir - if false, the iterator will start at the last item and move backwards
      Returns:
      an Iterator over the defined sub-range of the tree

    • slice

      public static <K, V extends K> BTreeSearchIterator<K,V> slice(Object[] btree, Comparator<? super K> comparator, K start, boolean startInclusive, K end, boolean endInclusive, BTree.Dir dir)
      Parameters:
      btree - the tree to iterate over
      comparator - the comparator that defines the ordering over the items in the tree
      start - low bound of the range
      startInclusive - inclusivity of lower bound
      end - high bound of the range
      endInclusive - inclusivity of higher bound
      dir - direction of iteration
      Returns:
      an Iterator over the defined sub-range of the tree

    • find

      public static <V> V find(Object[] node, Comparator<? super V> comparator, V find)
      Returns:
      the item in the tree that sorts as equal to the search argument, or null if no such item

    • replaceInSitu

      public static <V> void replaceInSitu(Object[] tree, int index, V replace)
      Modifies the provided btree directly. THIS SHOULD NOT BE USED WITHOUT EXTREME CARE as BTrees are meant to be immutable. Finds and replaces the item provided by index in the tree.

    • replaceInSitu

      public static <V> void replaceInSitu(Object[] node, Comparator<? super V> comparator, V find, V replace)
      Modifies the provided btree directly. THIS SHOULD NOT BE USED WITHOUT EXTREME CARE as BTrees are meant to be immutable. Finds and replaces the provided item in the tree. Both should sort as equal to each other (although this is not enforced)

    • findIndex

      public static <V> int findIndex(Object[] node, Comparator<? super V> comparator, V find)
      Honours result semantics of Arrays.binarySearch(long[], long), as though it were performed on the tree flattened into an array
      Returns:
      index of item in tree, or (-(insertion point) - 1) if not present

    • findByIndex

      public static <V> V findByIndex(Object[] tree, int index)
      Returns:
      the value at the index'th position in the tree, in tree order

    • lowerIndex

      public static <V> int lowerIndex(Object[] btree, Comparator<? super V> comparator, V find)

    • lower

      public static <V> V lower(Object[] btree, Comparator<? super V> comparator, V find)

    • floorIndex

      public static <V> int floorIndex(Object[] btree, Comparator<? super V> comparator, V find)

    • floor

      public static <V> V floor(Object[] btree, Comparator<? super V> comparator, V find)

    • higherIndex

      public static <V> int higherIndex(Object[] btree, Comparator<? super V> comparator, V find)

    • higher

      public static <V> V higher(Object[] btree, Comparator<? super V> comparator, V find)

    • ceilIndex

      public static <V> int ceilIndex(Object[] btree, Comparator<? super V> comparator, V find)

    • ceil

      public static <V> V ceil(Object[] btree, Comparator<? super V> comparator, V find)

    • size

      public static int size(Object[] tree)

    • sizeOfStructureOnHeap

      public static long sizeOfStructureOnHeap(Object[] tree)

    • isLeaf

      public static boolean isLeaf(Object[] node)
      Checks is the node is a leaf.
      Returns:
      true if the provided node is a leaf, false if it is a branch.

    • isEmpty

      public static boolean isEmpty(Object[] tree)

    • depth

      public static int depth(Object[] tree)

    • toArray

      public static int toArray(Object[] tree, Object[] target, int targetOffset)
      Fill the target array with the contents of the provided subtree, in ascending order, starting at targetOffset
      Parameters:
      tree - source
      target - array
      targetOffset - offset in target array
      Returns:
      number of items copied (size of tree)

    • toArray

      public static int toArray(Object[] tree, int treeStart, int treeEnd, Object[] target, int targetOffset)

    • transformAndFilter

      public static <I, I2, O> Object[] transformAndFilter(Object[] tree, BiFunction<? super I,? super I2,? extends O> apply, I2 param)
      Takes a tree and transforms it using the provided function, filtering out any null results. The result of any transformation must sort identically as their originals, wrt other results.

      If no modifications are made, the original is returned. NOTE: codewise *identical* to transformAndFilter(Object[], Function)

    • transformAndFilter

      public static <I, O> Object[] transformAndFilter(Object[] tree, Function<? super I,? extends O> apply)
      Takes a tree and transforms it using the provided function, filtering out any null results. The result of any transformation must sort identically as their originals, wrt other results.

      If no modifications are made, the original is returned.

      An efficient transformAndFilter implementation suitable for a tree consisting of a single leaf root NOTE: codewise *identical* to transformAndFilter(Object[], BiFunction, Object)

    • transform

      public static <I, O> Object[] transform(Object[] tree, Function<? super I,? extends O> function)
      Takes a tree and transforms it using the provided function. The result of any transformation must sort identically as their originals, wrt other results.

      If no modifications are made, the original is returned.

    • equals

      public static boolean equals(Object[] a, Object[] b)

    • hashCode

      public static int hashCode(Object[] btree)

    • toString

      public static String toString(Object[] btree)

    • treeIndexOfKey

      public static int treeIndexOfKey(Object[] root, int keyIndex)
      tree index => index of key wrt all items in the tree laid out serially

      This version of the method permits requesting out-of-bounds indexes, -1 and size

      Parameters:
      root - to calculate tree index within
      keyIndex - root-local index of key to calculate tree-index
      Returns:
      the number of items preceding the key in the whole tree of root

    • treeIndexOfLeafKey

      public static int treeIndexOfLeafKey(int keyIndex)
      Parameters:
      keyIndex - node-local index of the key to calculate index of
      Returns:
      keyIndex; this method is here only for symmetry and clarity

    • treeIndexOfBranchKey

      public static int treeIndexOfBranchKey(Object[] root, int keyIndex)
      Parameters:
      root - to calculate tree-index within
      keyIndex - root-local index of key to calculate tree-index of
      Returns:
      the number of items preceding the key in the whole tree of root

    • treeIndexOffsetOfChild

      public static int treeIndexOffsetOfChild(Object[] root, int childIndex)
      Parameters:
      root - to calculate tree-index within
      childIndex - root-local index of *child* to calculate tree-index of
      Returns:
      the number of items preceding the child in the whole tree of root

    • builder

      public static <V> BTree.Builder<V> builder(Comparator<? super V> comparator)

    • builder

      public static <V> BTree.Builder<V> builder(Comparator<? super V> comparator, int initialCapacity)

    • applyLeaf

      public static <V, A> void applyLeaf(Object[] btree, BiConsumer<A,V> function, A argument)

    • apply

      public static <V, A> void apply(Object[] btree, BiConsumer<A,V> function, A argument)
      Simple method to walk the btree forwards and apply a function till a stop condition is reached

      Private method

      Parameters:
      btree -
      function -

    • apply

      public static <V> void apply(Object[] btree, Consumer<V> function)
      Simple method to walk the btree forwards and apply a function till a stop condition is reached

      Private method

      Parameters:
      btree -
      function -

    • accumulate

      public static <V, A> long accumulate(Object[] btree, BiLongAccumulator<A,V> accumulator, A arg, Comparator<V> comparator, V from, long initialValue)
      Walk the btree and accumulate a long value using the supplied accumulator function. Iteration will stop if the accumulator function returns the sentinel value STOP_SENTINEL_VALUE

      If the optional from argument is not null, iteration will start from that value (or the one after it's insertion point if an exact match isn't found)

    • accumulate

      public static <V> long accumulate(Object[] btree, LongAccumulator<V> accumulator, Comparator<V> comparator, V from, long initialValue)

    • accumulate

      public static <V> long accumulate(Object[] btree, LongAccumulator<V> accumulator, long initialValue)

    • accumulate

      public static <V, A> long accumulate(Object[] btree, BiLongAccumulator<A,V> accumulator, A arg, long initialValue)

    • height

      public static int height(Object[] tree)
      Returns:
      the actual height of tree

    • sizeOnHeapOf

      public static long sizeOnHeapOf(Object[] tree)

    • isWellFormed

      public static boolean isWellFormed(Object[] btree, Comparator<?> cmp)

    • fastBuilder

      public static <V> BTree.FastBuilder<V> fastBuilder()
      Build a tree of unknown size, in order.

      Can be used with reverseInSitu(java.lang.Object[]) to build a tree in reverse.