org.apache.directory.mavibot.btree

Class InMemoryNode<K,V>

java.lang.Object

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

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

Type Parameters:

K - The type for the Key

V - The type for the stored value

All Implemented Interfaces:

Page<K,V>

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

A MVCC Node. It stores the keys and references to its children page. It does not contain any value.

Field Summary

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

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

Constructor Summary

Constructors

Constructor and Description
InMemoryNode(BTree<K,V> btree, long revision, int nbElems) Creates a new Node which will contain only one key, with references to a left and right page.
InMemoryNode(BTree<K,V> btree, long revision, K key, Page<K,V> leftPage, Page<K,V> rightPage) Creates a new Node which will contain only one key, with references to a left and right page.

Method Summary

Modifier and Type	Method and Description
private InsertResult<K,V>	addAndSplit(java.util.List<Page<K,V>> copiedPages, long revision, K pivot, Page<K,V> leftPage, Page<K,V> rightPage, int pos) Splits a full page into two new pages, a left, a right and a pivot element.
private DeleteResult<K,V>	borrowFromLeft(long revision, MergedWithSiblingResult<K,V> mergedResult, InMemoryNode<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(long revision, MergedWithSiblingResult<K,V> mergedResult, InMemoryNode<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.
protected InMemoryNode<K,V>	copy(long revision) Copies the current page and all its keys, with a new revision.
(package private) DeleteResult<K,V>	delete(K key, V value, long revision, Page<K,V> parent, int parentPos) The real delete implementation.
K	getLeftMostKey() Finds the leftmost key in this page.
K	getRightMostKey() Finds the rightmost key in this page.
private RemoveResult<K,V>	handleBorrowedResult(BorrowedFromSiblingResult<K,V> borrowedResult, int pos) The deletion in a children has moved an element from one of its sibling.
private RemoveResult<K,V>	handleRemoveResult(RemoveResult<K,V> removeResult, int index, int pos, boolean found) Modifies the current node after a remove has been done in one of its children.
private RemoveResult<K,V>	handleRootRemove(MergedWithSiblingResult<K,V> mergedResult, int pos, boolean found) Handles the removal of an element from the root page, when two of its children have been merged.
InsertResult<K,V>	insert(K key, V value, long revision)
private InsertResult<K,V>	insertChild(java.util.List<Page<K,V>> copiedPages, long revision, K key, Page<K,V> leftPage, Page<K,V> rightPage, int pos) Adds a new key into a copy of the current page at a given position.
boolean	isLeaf()
boolean	isNode()
private DeleteResult<K,V>	mergeWithSibling(long revision, MergedWithSiblingResult<K,V> mergedResult, InMemoryNode<K,V> sibling, boolean isLeft, int pos) We have to merge the node with its sibling, both have N/2 elements before the element removal.
private RemoveResult<K,V>	removeKey(MergedWithSiblingResult<K,V> mergedResult, long revision, int pos) Remove the key at a given position.
private InsertResult<K,V>	replaceChild(long revision, ModifyResult<K,V> result, int pos) This method is used when we have to replace a child in a page when we have found the key in the tree (the value will be changed, so we have made copies of the existing pages).
(package private) void	setValue(int pos, Page<K,V> value) Set the value at a give position
java.lang.String	toString()

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

browse, browse, browseKeys, compare, contains, delete, dumpPage, findLeftMost, findPos, findRightMost, get, getBtree, getKey, getKeys, getLastOffset, getNbElems, getOffset, getPage, getReference, getRevision, getValue, getValues, hasKey, selectSibling, setKey, setKeys, setLastOffset, setNbElems, setOffset, setPageHolder, setRevision, setValue

Methods inherited from class java.lang.Object

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

Constructor Detail

InMemoryNode

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

Creates a new Node which will contain only one key, with references to a left and right page. This is a specific constructor used by the btree when the root was full when we added a new value.

Parameters:

btree - the parent BTree

revision - the Node revision

nbElems - The number of elements in this Node

InMemoryNode

InMemoryNode(BTree<K,V> btree,
             long revision,
             K key,
             Page<K,V> leftPage,
             Page<K,V> rightPage)

Creates a new Node which will contain only one key, with references to a left and right page. This is a specific constructor used by the btree when the root was full when we added a new value.

Parameters:

btree - the parent BTree

revision - the Node revision

key - The new key

leftPage - The left page

rightPage - The right page

Method Detail

insert

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

Throws:

java.io.IOException

handleRemoveResult

private RemoveResult<K,V> handleRemoveResult(RemoveResult<K,V> removeResult,
                                             int index,
                                             int pos,
                                             boolean found)
                                      throws java.io.IOException

Modifies the current node after a remove has been done in one of its children. The node won't be merged with another node.

Parameters:

removeResult - The result of a remove operation

index - the position of the key, not transformed

pos - The position of the key, as a positive value

found - If the key has been found in the page

Returns:

The new result

Throws:

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

handleRootRemove

private RemoveResult<K,V> handleRootRemove(MergedWithSiblingResult<K,V> mergedResult,
                                           int pos,
                                           boolean found)
                                    throws java.io.IOException

Handles the removal of an element from the root page, when two of its children have been merged.

Parameters:

mergedResult - The merge result

pos - The position in the current root

found - Tells if the removed key is present in the root page

Returns:

The resulting root page

Throws:

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

borrowFromRight

private DeleteResult<K,V> borrowFromRight(long revision,
                                          MergedWithSiblingResult<K,V> mergedResult,
                                          InMemoryNode<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

borrowFromLeft

private DeleteResult<K,V> borrowFromLeft(long revision,
                                         MergedWithSiblingResult<K,V> mergedResult,
                                         InMemoryNode<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

mergeWithSibling

private DeleteResult<K,V> mergeWithSibling(long revision,
                                           MergedWithSiblingResult<K,V> mergedResult,
                                           InMemoryNode<K,V> sibling,
                                           boolean isLeft,
                                           int pos)
                                    throws java.io.IOException

We have to merge the node with its sibling, both have N/2 elements before the element removal.

Parameters:

revision - The revision

mergedResult - The result of the merge

sibling - The Page we will merge the current page with

isLeft - Tells if the sibling is on the left

pos - The position of the key that has been removed

Returns:

The page resulting of the merge

Throws:

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

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

handleBorrowedResult

private RemoveResult<K,V> handleBorrowedResult(BorrowedFromSiblingResult<K,V> borrowedResult,
                                               int pos)
                                        throws java.io.IOException

The deletion in a children has moved an element from one of its sibling. The key is present in the current node.

Parameters:

borrowedResult - The result of the deletion from the children

pos - The position the key was found in the current node

Returns:

The result

Throws:

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

removeKey

private RemoveResult<K,V> removeKey(MergedWithSiblingResult<K,V> mergedResult,
                                    long revision,
                                    int pos)
                             throws java.io.IOException

Remove the key at a given position.

Parameters:

mergedResult - The page we will remove a key from

revision - The revision of the modified page

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

Returns:

The modified page with the element added

Throws:

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

setValue

void setValue(int pos,
              Page<K,V> value)

Set the value at a give position

Parameters:

pos - The position in the values array

value - the value to inject

replaceChild

private InsertResult<K,V> replaceChild(long revision,
                                       ModifyResult<K,V> result,
                                       int pos)
                                throws java.io.IOException

This method is used when we have to replace a child in a page when we have found the key in the tree (the value will be changed, so we have made copies of the existing pages).

Parameters:

revision - The current revision

result - The modified page

pos - The position of the found key

Returns:

A modified page

Throws:

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

insertChild

private InsertResult<K,V> insertChild(java.util.List<Page<K,V>> copiedPages,
                                      long revision,
                                      K key,
                                      Page<K,V> leftPage,
                                      Page<K,V> rightPage,
                                      int pos)
                               throws java.io.IOException

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

Parameters:

copiedPages - the list of copied pages

revision - The revision of the modified page

key - The key to insert

leftPage - The left child

rightPage - The right child

pos - The position into the page

Returns:

The modified page with the element added

Throws:

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

addAndSplit

private InsertResult<K,V> addAndSplit(java.util.List<Page<K,V>> copiedPages,
                                      long revision,
                                      K pivot,
                                      Page<K,V> leftPage,
                                      Page<K,V> rightPage,
                                      int pos)
                               throws java.io.IOException

Splits 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:

copiedPages - the list of copied pages

revision - The new revision for all the created pages

pivot - The key that will be move up after the split

leftPage - The left child

rightPage - The right child

pos - The position of the insertion of the new element

Returns:

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

Throws:

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

copy

protected InMemoryNode<K,V> copy(long revision)

Copies the current page and all its keys, with a new revision.

Parameters:

revision - The new revision

Returns:

The copied page

getLeftMostKey

public K getLeftMostKey()

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

Specified by:

getLeftMostKey in interface Page<K,V>

Overrides:

getLeftMostKey in class AbstractPage<K,V>

Returns:

The leftmost key in the tree

getRightMostKey

public K getRightMostKey()

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

Specified by:

getRightMostKey in interface Page<K,V>

Overrides:

getRightMostKey in class AbstractPage<K,V>

Returns:

The rightmost key in the tree

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()