Package org.apache.cassandra.utils.btree

Class BTree

java.lang.Object

org.apache.cassandra.utils.btree.BTree

public class BTree
extends java.lang.Object

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	BTree.Builder<V>
static class	BTree.Dir	Represents the direction of iteration.
static class	BTree.FastBuilder<V>	A pooled builder for constructing a tree in-order, and without needing any reconciliation.

Field Summary

Fields

Modifier and Type	Field	Description
static 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.
static int	MAX_KEYS
static int	MIN_KEYS

Constructor Summary

Constructors

Constructor	Description
BTree()

Method Summary

Modifier and Type	Method	Description
static <V,A> long	accumulate(java.lang.Object[] btree, BiLongAccumulator<A,V> accumulator, A arg, long initialValue)
static <V,A> long	accumulate(java.lang.Object[] btree, BiLongAccumulator<A,V> accumulator, A arg, java.util.Comparator<V> comparator, V from, long initialValue)	Walk the btree and accumulate a long value using the supplied accumulator function.
static <V> long	accumulate(java.lang.Object[] btree, LongAccumulator<V> accumulator, long initialValue)
static <V> long	accumulate(java.lang.Object[] btree, LongAccumulator<V> accumulator, java.util.Comparator<V> comparator, V from, long initialValue)
static <V,A> void	apply(java.lang.Object[] btree, java.util.function.BiConsumer<A,V> function, A argument)	Simple method to walk the btree forwards and apply a function till a stop condition is reached
static <V> void	apply(java.lang.Object[] btree, java.util.function.Consumer<V> function)	Simple method to walk the btree forwards and apply a function till a stop condition is reached
static <V,A> void	applyLeaf(java.lang.Object[] btree, java.util.function.BiConsumer<A,V> function, A argument)
static <C,K extends C,V extends C> java.lang.Object[]	build(java.util.Collection<K> source)	Deprecated.
static <C,K extends C,V extends C> java.lang.Object[]	build(java.util.Collection<K> source, UpdateFunction<K,V> updateF)	Deprecated.
static <C,I extends C,O extends C> java.lang.Object[]	build(BulkIterator<I> source, int size, UpdateFunction<I,O> updateF)
static <V> BTree.Builder<V>	builder(java.util.Comparator<? super V> comparator)
static <V> BTree.Builder<V>	builder(java.util.Comparator<? super V> comparator, int initialCapacity)
static <V> V	ceil(java.lang.Object[] btree, java.util.Comparator<? super V> comparator, V find)
static <V> int	ceilIndex(java.lang.Object[] btree, java.util.Comparator<? super V> comparator, V find)
static int	depth(java.lang.Object[] tree)
static java.lang.Object[]	empty()	Returns an empty BTree
static boolean	equals(java.lang.Object[] a, java.lang.Object[] b)
static <V> BTree.FastBuilder<V>	fastBuilder()	Build a tree of unknown size, in order.
static <V> V	find(java.lang.Object[] node, java.util.Comparator<? super V> comparator, V find)
static <V> V	findByIndex(java.lang.Object[] tree, int index)
static <V> int	findIndex(java.lang.Object[] node, java.util.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
static <V> V	floor(java.lang.Object[] btree, java.util.Comparator<? super V> comparator, V find)
static <V> int	floorIndex(java.lang.Object[] btree, java.util.Comparator<? super V> comparator, V find)
static int	hashCode(java.lang.Object[] btree)
static int	height(java.lang.Object[] tree)
static <V> V	higher(java.lang.Object[] btree, java.util.Comparator<? super V> comparator, V find)
static <V> int	higherIndex(java.lang.Object[] btree, java.util.Comparator<? super V> comparator, V find)
static boolean	isEmpty(java.lang.Object[] tree)
static boolean	isLeaf(java.lang.Object[] node)	Checks is the node is a leaf.
static boolean	isWellFormed(java.lang.Object[] btree, java.util.Comparator<?> cmp)
static <V> java.lang.Iterable<V>	iterable(java.lang.Object[] btree)
static <V> java.lang.Iterable<V>	iterable(java.lang.Object[] btree, int lb, int ub, BTree.Dir dir)
static <V> java.lang.Iterable<V>	iterable(java.lang.Object[] btree, BTree.Dir dir)
static <V> java.util.Iterator<V>	iterator(java.lang.Object[] btree)
static <V> java.util.Iterator<V>	iterator(java.lang.Object[] btree, int lb, int ub, BTree.Dir dir)
static <V> java.util.Iterator<V>	iterator(java.lang.Object[] btree, BTree.Dir dir)
static <V> V	lower(java.lang.Object[] btree, java.util.Comparator<? super V> comparator, V find)
static <V> int	lowerIndex(java.lang.Object[] btree, java.util.Comparator<? super V> comparator, V find)
static <V> void	replaceInSitu(java.lang.Object[] tree, int index, V replace)	Modifies the provided btree directly.
static <V> void	replaceInSitu(java.lang.Object[] node, java.util.Comparator<? super V> comparator, V find, V replace)	Modifies the provided btree directly.
static void	reverseInSitu(java.lang.Object[] tree)
static java.lang.Object[]	singleton(java.lang.Object value)	Create a BTree containing only the specified object
static int	size(java.lang.Object[] tree)
static long	sizeOfStructureOnHeap(java.lang.Object[] tree)
static long	sizeOnHeapOf(java.lang.Object[] tree)
static <K,V extends K> BTreeSearchIterator<K,V>	slice(java.lang.Object[] btree, java.util.Comparator<? super K> comparator, int startIndex, int endIndex, BTree.Dir dir)
static <K,V extends K> BTreeSearchIterator<K,V>	slice(java.lang.Object[] btree, java.util.Comparator<? super K> comparator, K start, boolean startInclusive, K end, boolean endInclusive, BTree.Dir dir)
static <K,V extends K> BTreeSearchIterator<K,V>	slice(java.lang.Object[] btree, java.util.Comparator<? super K> comparator, K start, K end, BTree.Dir dir)
static <K,V> BTreeSearchIterator<K,V>	slice(java.lang.Object[] btree, java.util.Comparator<? super K> comparator, BTree.Dir dir)	Returns an Iterator over the entire tree
static int	toArray(java.lang.Object[] tree, int treeStart, int treeEnd, java.lang.Object[] target, int targetOffset)
static int	toArray(java.lang.Object[] tree, java.lang.Object[] target, int targetOffset)	Fill the target array with the contents of the provided subtree, in ascending order, starting at targetOffset
static java.lang.String	toString(java.lang.Object[] btree)
static <I,O> java.lang.Object[]	transform(java.lang.Object[] tree, java.util.function.Function<? super I,? extends O> function)	Takes a tree and transforms it using the provided function.
static <I,I2,O> java.lang.Object[]	transformAndFilter(java.lang.Object[] tree, java.util.function.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.
static <I,O> java.lang.Object[]	transformAndFilter(java.lang.Object[] tree, java.util.function.Function<? super I,? extends O> apply)	Takes a tree and transforms it using the provided function, filtering out any null results.
static int	treeIndexOfBranchKey(java.lang.Object[] root, int keyIndex)
static int	treeIndexOffsetOfChild(java.lang.Object[] root, int childIndex)
static int	treeIndexOfKey(java.lang.Object[] root, int keyIndex)	tree index => index of key wrt all items in the tree laid out serially
static int	treeIndexOfLeafKey(int keyIndex)
static <Compare> java.lang.Object[]	update(java.lang.Object[] toUpdate, java.lang.Object[] insert, java.util.Comparator<? super Compare> comparator)
static <Compare,Existing extends Compare,Insert extends Compare> java.lang.Object[]	update(java.lang.Object[] toUpdate, java.lang.Object[] insert, java.util.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.
static <Compare,Existing extends Compare,Insert extends Compare> java.lang.Object[]	updateLeaves(java.lang.Object[] unode, java.lang.Object[] inode, java.util.Comparator<? super Compare> comparator, UpdateFunction<Insert,Existing> updateF)	A fast tight-loop variant of updating one btree with another, when both are leaves.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

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

Constructor Detail

BTree

public BTree()

Method Detail

empty

public static java.lang.Object[] empty()

Returns an empty BTree

Returns:

an empty BTree

singleton

public static java.lang.Object[] singleton(java.lang.Object value)

Create a BTree containing only the specified object

Returns:

an new BTree containing only the specified object

build

@Deprecated
public static <C,K extends C,V extends C> java.lang.Object[] build(java.util.Collection<K> source)

Deprecated.

build

@Deprecated
public static <C,K extends C,V extends C> java.lang.Object[] build(java.util.Collection<K> source,
                                                                               UpdateFunction<K,V> updateF)

Deprecated.

build

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

update

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

update

public static <Compare,Existing extends Compare,Insert extends Compare> java.lang.Object[] update(java.lang.Object[] toUpdate,
                                                                                                              java.lang.Object[] insert,
                                                                                                              java.util.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> java.lang.Object[] updateLeaves(java.lang.Object[] unode,
                                                                                                                    java.lang.Object[] inode,
                                                                                                                    java.util.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(java.lang.Object[] tree)

iterator

public static <V> java.util.Iterator<V> iterator(java.lang.Object[] btree)

iterator

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

iterator

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

iterable

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

iterable

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

iterable

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

slice

public static <K,V> BTreeSearchIterator<K,V> slice(java.lang.Object[] btree,
                                                               java.util.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(java.lang.Object[] btree,
                                                                         java.util.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(java.lang.Object[] btree,
                                                                         java.util.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(java.lang.Object[] btree,
                                                                         java.util.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(java.lang.Object[] node,
                         java.util.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(java.lang.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(java.lang.Object[] node,
                                     java.util.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(java.lang.Object[] node,
                                java.util.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(java.lang.Object[] tree,
                                int index)

Returns:

the value at the index'th position in the tree, in tree order

lowerIndex

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

lower

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

floorIndex

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

floor

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

higherIndex

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

higher

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

ceilIndex

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

ceil

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

size

public static int size(java.lang.Object[] tree)

sizeOfStructureOnHeap

public static long sizeOfStructureOnHeap(java.lang.Object[] tree)

isLeaf

public static boolean isLeaf(java.lang.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(java.lang.Object[] tree)

depth

public static int depth(java.lang.Object[] tree)

toArray

public static int toArray(java.lang.Object[] tree,
                          java.lang.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(java.lang.Object[] tree,
                          int treeStart,
                          int treeEnd,
                          java.lang.Object[] target,
                          int targetOffset)

transformAndFilter

public static <I,I2,O> java.lang.Object[] transformAndFilter(java.lang.Object[] tree,
                                                                         java.util.function.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> java.lang.Object[] transformAndFilter(java.lang.Object[] tree,
                                                                java.util.function.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> java.lang.Object[] transform(java.lang.Object[] tree,
                                                       java.util.function.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(java.lang.Object[] a,
                             java.lang.Object[] b)

hashCode

public static int hashCode(java.lang.Object[] btree)

toString

public static java.lang.String toString(java.lang.Object[] btree)

treeIndexOfKey

public static int treeIndexOfKey(java.lang.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(java.lang.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(java.lang.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(java.util.Comparator<? super V> comparator)

builder

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

applyLeaf

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

apply

public static <V,A> void apply(java.lang.Object[] btree,
                                     java.util.function.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(java.lang.Object[] btree,
                             java.util.function.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(java.lang.Object[] btree,
                                          BiLongAccumulator<A,V> accumulator,
                                          A arg,
                                          java.util.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 values Long.MIN_VALUE or Long.MAX_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(java.lang.Object[] btree,
                                  LongAccumulator<V> accumulator,
                                  java.util.Comparator<V> comparator,
                                  V from,
                                  long initialValue)

accumulate

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

accumulate

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

height

public static int height(java.lang.Object[] tree)

Returns:

the actual height of tree

sizeOnHeapOf

public static long sizeOnHeapOf(java.lang.Object[] tree)

isWellFormed

public static boolean isWellFormed(java.lang.Object[] btree,
                                   java.util.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.