org.apache.directory.mavibot.btree

Class AbstractPage<K,V>

java.lang.Object

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

Type Parameters:

K - The type for the Key

V - The type for the stored value

All Implemented Interfaces:

Page<K,V>

Direct Known Subclasses:

InMemoryLeaf, InMemoryNode, PersistedLeaf, PersistedNode

abstract class AbstractPage<K,V>
extends java.lang.Object
implements Page<K,V>

A MVCC abstract Page. It stores the field and the methods shared by the Node and Leaf classes.

Field Summary

Fields

Modifier and Type	Field and Description
protected BTree<K,V>	btree Parent B+Tree.
protected PageHolder<K,V>[]	children Children pages associated with keys.
protected KeyHolder<K>[]	keys Keys of children nodes
protected long	lastOffset The last PageIO storing the serialized Page on disk
protected int	nbElems The number of current values in the Page
protected long	offset The first PageIO storing the serialized Page on disk
protected long	revision This BPage's revision

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	AbstractPage(BTree<K,V> btree) Creates a default empty AbstractPage
protected	AbstractPage(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
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.
protected int	compare(K key1, K key2) Compares two keys
boolean	contains(K key, V value) Checks if the page contains the given key with the given value.
DeleteResult<K,V>	delete(K key, V value, long revision) Deletes the value from an entry associated with the given key in this page.
(package private) abstract 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.
int	findPos(K key) Finds the position of the given key in the 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.
BTree<K,V>	getBtree()
K	getKey(int pos) Returns the key at a given position
(package private) KeyHolder<K>[]	getKeys()
(package private) long	getLastOffset()
K	getLeftMostKey() Finds the leftmost key in this page.
int	getNbElems()
(package private) long	getOffset()
(package private) Page<K,V>	getPage(int pos)
(package private) Page<K,V>	getReference(int pos)
long	getRevision()
K	getRightMostKey() Finds the rightmost key in this page.
(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.
protected int	selectSibling(Page<K,V> parent, int parentPos) Selects the sibling (the previous or next page with the same parent) which has the more element assuming it's above N/2
(package private) void	setKey(int pos, KeyHolder<K> key) Sets the key at a give position
(package private) void	setKeys(KeyHolder<K>[] keys)
(package private) void	setLastOffset(long lastOffset)
(package private) void	setNbElems(int nbElems) Sets the number of element in this page
(package private) void	setOffset(long offset)
(package private) void	setPageHolder(int pos, PageHolder<K,V> pageHolder) Inject a pageHolder into the node, at a given position
(package private) void	setRevision(long revision)
(package private) void	setValue(int pos, ValueHolder<V> value) Sets the value at a give position
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.apache.directory.mavibot.btree.Page

insert, isLeaf, isNode

Field Detail

btree

protected transient BTree<K,V> btree

Parent B+Tree.

keys

protected KeyHolder<K>[] keys

Keys of children nodes

children

protected PageHolder<K,V>[] children

Children pages associated with keys.

nbElems

protected int nbElems

The number of current values in the Page

revision

protected long revision

This BPage's revision

offset

protected long offset

The first PageIO storing the serialized Page on disk

lastOffset

protected long lastOffset

The last PageIO storing the serialized Page on disk

Constructor Detail

AbstractPage

protected AbstractPage(BTree<K,V> btree)

Creates a default empty AbstractPage

Parameters:

btree - The associated BTree

AbstractPage

protected AbstractPage(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 Detail

getNbElems

public int getNbElems()

Specified by:

getNbElems in interface Page<K,V>

Returns:

The number of keys present in this page

setNbElems

void setNbElems(int nbElems)

Sets the number of element in this page

Parameters:

nbElems - The number of elements

getKey

public K getKey(int pos)

Returns the key at a given position

Specified by:

getKey in interface Page<K,V>

Parameters:

pos - The position of the key we want to retrieve

Returns:

The key found at the given position

hasKey

public boolean hasKey(K key)
               throws java.io.IOException

Checks if the given key exists.

Specified by:

hasKey in interface Page<K,V>

Parameters:

key - The key we are looking at

Returns:

true if the key is present, false otherwise

Throws:

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

getReference

Page<K,V> getReference(int pos)
                throws java.io.IOException

Throws:

java.io.IOException

browse

public TupleCursor<K,V> browse(K key,
                               ReadTransaction<K,V> transaction,
                               ParentPos<K,V>[] stack,
                               int depth)
                        throws java.io.IOException

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>

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

Throws:

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

contains

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

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

Specified by:

contains in interface Page<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

delete

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

Deletes the value from an entry associated with the given key in this page. We first find the place were to remove the into the tree, by recursively browsing the pages. If the value is present, it will be deleted first, later if there are no other values associated with this key(which can happen when duplicates are enabled), we will remove the key from the tree.

Specified by:

delete in interface Page<K,V>

Parameters:

key - The key to delete

value - The value to delete (can be null)

revision - The new revision for the modified pages

Returns:

Either a modified Page if the key has been removed from the page, or a NotPresentResult.

Throws:

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

delete

abstract 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.

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

get

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

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>

Parameters:

key - The key we are looking for

Returns:

The associated value, which can be null

Throws:

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

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

getPage

Page<K,V> getPage(int pos)

setPageHolder

void setPageHolder(int pos,
                   PageHolder<K,V> pageHolder)

Inject a pageHolder into the node, at a given position

Parameters:

pos - The position of the added pageHolder

pageHolder - The pageHolder to add

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>

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

setValue

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

Sets the value at a give position

Parameters:

pos - The position in the values array

value - the value to inject

browse

public TupleCursor<K,V> browse(ReadTransaction<K,V> transaction,
                               ParentPos<K,V>[] stack,
                               int depth)
                        throws java.io.IOException

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

Specified by:

browse in interface Page<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

Throws:

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

browseKeys

public KeyCursor<K> browseKeys(ReadTransaction<K,K> transaction,
                               ParentPos<K,K>[] stack,
                               int depth)
                        throws java.io.IOException

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

Specified by:

browseKeys in interface Page<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

Throws:

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

selectSibling

protected int selectSibling(Page<K,V> parent,
                            int parentPos)
                     throws java.io.IOException

Selects the sibling (the previous or next page with the same parent) which has the more element assuming it's above N/2

Parameters:

parent - The parent of the current page

The - position of the current page reference in its parent

Returns:

The position of the sibling, or -1 if we have'nt found any sibling

Throws:

java.io.IOException - If we have an error while trying to access the 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>

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>

Returns:

The rightmost key in the tree

getOffset

long getOffset()

Returns:

the offset of the first PageIO which stores the Page on disk.

setOffset

void setOffset(long offset)

Parameters:

offset - the offset to set

getLastOffset

long getLastOffset()

Returns:

the offset of the last PageIO which stores the Page on disk.

setLastOffset

void setLastOffset(long lastOffset)

getKeys

KeyHolder<K>[] getKeys()

Returns:

the keys

setKey

void setKey(int pos,
            KeyHolder<K> key)

Sets the key at a give position

Parameters:

pos - The position in the keys array

key - the key to inject

setKeys

void setKeys(KeyHolder<K>[] keys)

Parameters:

revision - the keys to set

getValue

ValueHolder<V> getValue(int pos)

getRevision

public long getRevision()

Specified by:

getRevision in interface Page<K,V>

Returns:

the revision

setRevision

void setRevision(long revision)

Parameters:

revision - the revision to set

compare

protected final int compare(K key1,
                            K key2)

Compares two keys

Parameters:

key1 - The first key

key2 - The second key

Returns:

-1 if the first key is above the second one, 1 if it's below, and 0 if the two keys are equal

findPos

public int findPos(K key)

Finds the position of the given key in the page. If we have found the key, we will return its position as a negative value.

Assuming that the array is zero-indexed, the returned value will be :
position = - ( position + 1)
So for the following table of keys :

 +---+---+---+---+
 | b | d | f | h |
 +---+---+---+---+
   0   1   2   3
 

looking for 'b' will return -1 (-(0+1)) and looking for 'f' will return -3 (-(2+1)).
Computing the real position is just a matter to get -(position++).

If we don't find the key in the table, we will return the position of the key immediately above the key we are looking for.
For instance, looking for :

• 'a' will return 0
• 'b' will return -1
• 'c' will return 1
• 'd' will return -2
• 'e' will return 2
• 'f' will return -3
• 'g' will return 3
• 'h' will return -4
• 'i' will return 4

Specified by:

findPos in interface Page<K,V>

Parameters:

key - The key to find

Returns:

The position in the page.

findLeftMost

public Tuple<K,V> findLeftMost()
                        throws EndOfFileExceededException,
                               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>

Returns:

The leftmost element in the tree

Throws:

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

EndOfFileExceededException

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>

Returns:

The rightmost element in the tree

Throws:

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

EndOfFileExceededException

getBtree

public BTree<K,V> getBtree()

Returns:

the btree

dumpPage

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

Pretty-prints the tree with tabs

Specified by:

dumpPage in interface Page<K,V>

Parameters:

tabs - The tabs to add in front of each node

Returns:

A pretty-print dump of the tree

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

See Also:

Object.toString()