org.apache.directory.mavibot.btree

Class InMemoryLeaf<K,V>

java.lang.Object

org.apache.directory.mavibot.btree.AbstractPage<K,V>

org.apache.directory.mavibot.btree.InMemoryLeaf<K,V>

Type Parameters:

K - The type for the Key

V - The type for the stored value

All Implemented Interfaces:

Page<K,V>

class InMemoryLeaf<K,V>
extends AbstractPage<K,V>

A MVCC Leaf. It stores the keys and values. It does not have any children.

Field Summary

Fields

Modifier and Type	Field and Description
protected ValueHolder<V>[]	values Values associated with keys

Fields inherited from class org.apache.directory.mavibot.btree.AbstractPage

btree, children, keys, lastOffset, nbElems, offset, revision

Constructor Summary

Constructors

Constructor and Description
InMemoryLeaf(BTree<K,V> btree) Constructor used to create a new Leaf when we read it from a file.
InMemoryLeaf(BTree<K,V> btree, long revision, int nbElems) Internal constructor used to create Page instance used when a page is being copied or overflow

Method Summary

Modifier and Type	Method and Description
private InsertResult<K,V>	addAndSplit(long revision, K key, V value, int pos) Split a full page into two new pages, a left, a right and a pivot element.
private Page<K,V>	addElement(long revision, K key, V value, int pos) Adds a new into a copy of the current page at a given position.
private DeleteResult<K,V>	borrowFromLeft(Tuple<K,V> removedElement, long revision, InMemoryLeaf<K,V> sibling, int pos) Borrows an element from the left sibling, creating a new sibling with one less element and creating a new page where the element to remove has been deleted and the borrowed element added on the left.
private DeleteResult<K,V>	borrowFromRight(Tuple<K,V> removedElement, long revision, InMemoryLeaf<K,V> sibling, int pos) Borrows an element from the right sibling, creating a new sibling with one less element and creating a new page where the element to remove has been deleted and the borrowed element added on the right.
TupleCursor<K,V>	browse(K key, ReadTransaction<K,V> transaction, ParentPos<K,V>[] stack, int depth) Browses the tree, looking for the given key, and creates a Cursor on top of the found result.
TupleCursor<K,V>	browse(ReadTransaction<K,V> transaction, ParentPos<K,V>[] stack, int depth) Browses the whole tree, and creates a Cursor on top of it.
KeyCursor<K>	browseKeys(ReadTransaction<K,K> transaction, ParentPos<K,K>[] stack, int depth) Browses the keys of whole tree, and creates a Cursor on top of it.
boolean	contains(K key, V value) Checks if the page contains the given key with the given value.
private Page<K,V>	copy(long revision, int nbElems) Copy the current page and all of the keys, values and children, if it's not a leaf.
private void	copyAfterRemovingElement(boolean keyRemoved, InMemoryLeaf<K,V> newLeaf, int pos) Copies the elements of the current page to a new page
(package private) DeleteResult<K,V>	delete(K key, V value, long revision, Page<K,V> parent, int parentPos) The real delete implementation.
java.lang.String	dumpPage(java.lang.String tabs) Pretty-prints the tree with tabs
Tuple<K,V>	findLeftMost() Finds the leftmost element in this page.
Tuple<K,V>	findRightMost() Finds the rightmost element in this page.
V	get(K key) Gets the value associated with the given key, if any.
(package private) ValueHolder<V>	getValue(int pos)
ValueCursor<V>	getValues(K key) Gets the values associated with the given key, if any.
boolean	hasKey(K key) Checks if the given key exists.
InsertResult<K,V>	insert(K key, V value, long revision)
boolean	isLeaf()
boolean	isNode()
private DeleteResult<K,V>	mergeWithSibling(Tuple<K,V> removedElement, long revision, InMemoryLeaf<K,V> sibling, boolean isLeft, int pos) Merges the sibling with the current leaf, after having removed the element in the page.
private InsertResult<K,V>	replaceElement(long revision, K key, V value, int pos) Copy the current page if needed, and replace the value at the position we have found the key.
(package private) void	setValue(int pos, ValueHolder<V> value) Sets the value at a give position
java.lang.String	toString()

Methods inherited from class org.apache.directory.mavibot.btree.AbstractPage

compare, delete, findPos, getBtree, getKey, getKeys, getLastOffset, getLeftMostKey, getNbElems, getOffset, getPage, getReference, getRevision, getRightMostKey, selectSibling, setKey, setKeys, setLastOffset, setNbElems, setOffset, setPageHolder, setRevision

Methods inherited from class java.lang.Object

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

Field Detail

values

protected ValueHolder<V>[] values

Values associated with keys

Constructor Detail

InMemoryLeaf

InMemoryLeaf(BTree<K,V> btree)

Constructor used to create a new Leaf when we read it from a file.

Parameters:

btree - The BTree this page belongs to.

InMemoryLeaf

InMemoryLeaf(BTree<K,V> btree,
             long revision,
             int nbElems)

Internal constructor used to create Page instance used when a page is being copied or overflow

Parameters:

btree - The BTree this page belongs to.

revision - The page revision

nbElems - The number of elements this page will contain

Method Detail

insert

public InsertResult<K,V> insert(K key,
                                V value,
                                long revision)
                         throws java.io.IOException

Throws:

java.io.IOException

delete

DeleteResult<K,V> delete(K key,
                         V value,
                         long revision,
                         Page<K,V> parent,
                         int parentPos)
                  throws java.io.IOException

The real delete implementation. It can be used for internal deletion in the B-tree.

Specified by:

delete in class AbstractPage<K,V>

Parameters:

key - The key to delete

value - The value to delete

revision - The revision for which we want to delete a tuple

parent - The parent page

parentPos - The position of this page in the parent page

Returns:

The result

Throws:

java.io.IOException - If we had an issue while processing the deletion

mergeWithSibling

private DeleteResult<K,V> mergeWithSibling(Tuple<K,V> removedElement,
                                           long revision,
                                           InMemoryLeaf<K,V> sibling,
                                           boolean isLeft,
                                           int pos)
                                    throws EndOfFileExceededException,
                                           java.io.IOException

Merges the sibling with the current leaf, after having removed the element in the page.

Parameters:

revision - The new revision

sibling - The sibling we will merge with

isLeft - Tells if the sibling is on the left or on the right

pos - The position of the removed element

Returns:

The new created leaf containing the sibling and the old page.

Throws:

java.io.IOException - If we have an error while trying to access the page

EndOfFileExceededException

borrowFromLeft

private DeleteResult<K,V> borrowFromLeft(Tuple<K,V> removedElement,
                                         long revision,
                                         InMemoryLeaf<K,V> sibling,
                                         int pos)
                                  throws java.io.IOException

Borrows an element from the left sibling, creating a new sibling with one less element and creating a new page where the element to remove has been deleted and the borrowed element added on the left.

Parameters:

revision - The new revision for all the pages

sibling - The left sibling

pos - The position of the element to remove

Returns:

The resulting pages

Throws:

java.io.IOException - If we have an error while trying to access the page

borrowFromRight

private DeleteResult<K,V> borrowFromRight(Tuple<K,V> removedElement,
                                          long revision,
                                          InMemoryLeaf<K,V> sibling,
                                          int pos)
                                   throws java.io.IOException

Borrows an element from the right sibling, creating a new sibling with one less element and creating a new page where the element to remove has been deleted and the borrowed element added on the right.

Parameters:

revision - The new revision for all the pages

sibling - The right sibling

pos - The position of the element to remove

Returns:

The resulting pages

Throws:

java.io.IOException - If we have an error while trying to access the page

copyAfterRemovingElement

private void copyAfterRemovingElement(boolean keyRemoved,
                                      InMemoryLeaf<K,V> newLeaf,
                                      int pos)
                               throws java.io.IOException

Copies the elements of the current page to a new page

Parameters:

keyRemoved - a flag stating if the key was removed

newLeaf - The new page into which the remaining keys and values will be copied

pos - The position into the page of the element to remove

Throws:

java.io.IOException - If we have an error while trying to access the page

get

public V get(K key)
      throws KeyNotFoundException,
             java.io.IOException

Gets the value associated with the given key, if any. If we don't have one, this method will throw a KeyNotFoundException.
Note that we may get back null if a null value has been associated with the key.

Specified by:

get in interface Page<K,V>

Overrides:

get in class AbstractPage<K,V>

Parameters:

key - The key we are looking for

Returns:

The associated value, which can be null

Throws:

KeyNotFoundException - If no entry with the given key can be found

java.io.IOException - If we have an error while trying to access the page

getValues

public ValueCursor<V> getValues(K key)
                         throws KeyNotFoundException,
                                java.io.IOException,
                                java.lang.IllegalArgumentException

Gets the values associated with the given key, if any. If we don't have the key, this method will throw a KeyNotFoundException.
Note that we may get back null if a null value has been associated with the key.

Specified by:

getValues in interface Page<K,V>

Overrides:

getValues in class AbstractPage<K,V>

Parameters:

key - The key we are looking for

Returns:

The associated value, which can be null

Throws:

KeyNotFoundException - If no entry with the given key can be found

java.io.IOException - If we have an error while trying to access the page

java.lang.IllegalArgumentException - If duplicates are not enabled

hasKey

public boolean hasKey(K key)

Checks if the given key exists.

Specified by:

hasKey in interface Page<K,V>

Overrides:

hasKey in class AbstractPage<K,V>

Parameters:

key - The key we are looking at

Returns:

true if the key is present, false otherwise

contains

public boolean contains(K key,
                        V value)
                 throws java.io.IOException

Description copied from class: AbstractPage

Checks if the page contains the given key with the given value.

Specified by:

contains in interface Page<K,V>

Overrides:

contains in class AbstractPage<K,V>

Parameters:

key - The key we are looking for

value - The value associated with the given key

Returns:

true if the key and value are associated with each other, false otherwise

Throws:

java.io.IOException

getValue

ValueHolder<V> getValue(int pos)

Overrides:

getValue in class AbstractPage<K,V>

setValue

void setValue(int pos,
              ValueHolder<V> value)

Sets the value at a give position

Overrides:

setValue in class AbstractPage<K,V>

Parameters:

pos - The position in the values array

value - the value to inject

browse

public TupleCursor<K,V> browse(K key,
                               ReadTransaction<K,V> transaction,
                               ParentPos<K,V>[] stack,
                               int depth)

Browses the tree, looking for the given key, and creates a Cursor on top of the found result.

Specified by:

browse in interface Page<K,V>

Overrides:

browse in class AbstractPage<K,V>

Parameters:

key - The key we are looking for.

transaction - The started transaction for this operation

stack - The stack of parents we go through to get to this page

Returns:

A Cursor to browse the next elements

browse

public TupleCursor<K,V> browse(ReadTransaction<K,V> transaction,
                               ParentPos<K,V>[] stack,
                               int depth)

Browses the whole tree, and creates a Cursor on top of it.

Specified by:

browse in interface Page<K,V>

Overrides:

browse in class AbstractPage<K,V>

Parameters:

transaction - The started transaction for this operation

stack - The stack of parents we go through to get to this page

Returns:

A Cursor to browse the next elements

browseKeys

public KeyCursor<K> browseKeys(ReadTransaction<K,K> transaction,
                               ParentPos<K,K>[] stack,
                               int depth)

Browses the keys of whole tree, and creates a Cursor on top of it.

Specified by:

browseKeys in interface Page<K,V>

Overrides:

browseKeys in class AbstractPage<K,V>

Parameters:

transaction - The started transaction for this operation

stack - The stack of parents we go through to get to this page

Returns:

A Cursor to browse the keys

copy

private Page<K,V> copy(long revision,
                       int nbElems)

Copy the current page and all of the keys, values and children, if it's not a leaf.

Parameters:

revision - The new revision

nbElems - The number of elements to copy

Returns:

The copied page

replaceElement

private InsertResult<K,V> replaceElement(long revision,
                                         K key,
                                         V value,
                                         int pos)
                                  throws java.io.IOException

Copy the current page if needed, and replace the value at the position we have found the key.

Parameters:

revision - The new page revision

key - The new key

value - the new value

pos - The position of the key in the page

Returns:

The copied page

Throws:

java.io.IOException - If we have an error while trying to access the page

addElement

private Page<K,V> addElement(long revision,
                             K key,
                             V value,
                             int pos)

Adds a new into a copy of the current page at a given position. We return the modified page. The new page will have one more element than the current page.

Parameters:

revision - The revision of the modified page

key - The key to insert

value - The value to insert

pos - The position into the page

Returns:

The modified page with the element added

addAndSplit

private InsertResult<K,V> addAndSplit(long revision,
                                      K key,
                                      V value,
                                      int pos)

Split a full page into two new pages, a left, a right and a pivot element. The new pages will each contains half of the original elements.
The pivot will be computed, depending on the place we will inject the newly added element.
If the newly added element is in the middle, we will use it as a pivot. Otherwise, we will use either the last element in the left page if the element is added on the left, or the first element in the right page if it's added on the right.

Parameters:

revision - The new revision for all the created pages

key - The key to add

value - The value to add

pos - The position of the insertion of the new element

Returns:

An OverflowPage containing the pivot, and the new left and right pages

findLeftMost

public Tuple<K,V> findLeftMost()
                        throws java.io.IOException

Finds the leftmost element in this page. If the page is a node, it will go down in the leftmost children to recursively find the leftmost element.

Specified by:

findLeftMost in interface Page<K,V>

Overrides:

findLeftMost in class AbstractPage<K,V>

Returns:

The leftmost element in the tree

Throws:

java.io.IOException - If we have an error while trying to access the page

findRightMost

public Tuple<K,V> findRightMost()
                         throws EndOfFileExceededException,
                                java.io.IOException

Finds the rightmost element in this page. If the page is a node, it will go down in the rightmost children to recursively find the rightmost element.

Specified by:

findRightMost in interface Page<K,V>

Overrides:

findRightMost in class AbstractPage<K,V>

Returns:

The rightmost element in the tree

Throws:

java.io.IOException - If we have an error while trying to access the page

EndOfFileExceededException

isLeaf

public boolean isLeaf()

isNode

public boolean isNode()

toString

public java.lang.String toString()

Overrides:

toString in class AbstractPage<K,V>

See Also:

Object.toString()

dumpPage

public java.lang.String dumpPage(java.lang.String tabs)

Pretty-prints the tree with tabs

Specified by:

dumpPage in interface Page<K,V>

Overrides:

dumpPage in class AbstractPage<K,V>

Parameters:

tabs - The tabs to add in front of each node

Returns:

A pretty-print dump of the tree