org.apache.directory.mavibot.btree

Class AbstractBTree<K,V>

java.lang.Object

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

Type Parameters:

K - The Key type

V - The Value type

All Implemented Interfaces:

BTree<K,V>

Direct Known Subclasses:

InMemoryBTree, PersistedBTree

abstract class AbstractBTree<K,V>
extends java.lang.Object
implements BTree<K,V>

A BTree abstract class containing the methods shared by the PersistedBTree or the InMemoryBTree implementations.

Field Summary

Fields

Modifier and Type	Field and Description
protected boolean	allowDuplicates Flag to enable duplicate key support
protected java.util.Map<java.lang.Long,BTreeHeader<K,V>>	btreeRevisions The map of all the used BtreeHeaders
protected BTreeTypeEnum	btreeType The BTree type : either in-memory, disk backed or persisted
protected BTreeHeader<K,V>	currentBtreeHeader The current Header for a managed BTree
protected java.util.concurrent.atomic.AtomicLong	currentRevision The current revision
protected ElementSerializer<K>	keySerializer The Key serializer used for this tree.
protected java.lang.String	keySerializerFQCN The FQCN of the Key serializer
protected java.lang.String	name The BTree name
protected int	pageSize The number of elements in a page for this B-tree
protected long	readTimeOut The read transaction timeout
protected java.util.concurrent.ConcurrentLinkedQueue<ReadTransaction<K,V>>	readTransactions The list of read transactions being executed
protected java.lang.Thread	readTransactionsThread The thread responsible for the cleanup of timed out reads
protected TransactionManager	transactionManager The TransactionManager used for this BTree
protected java.util.concurrent.atomic.AtomicBoolean	transactionStarted The current transaction
protected ElementSerializer<V>	valueSerializer The Value serializer used for this tree.
protected java.lang.String	valueSerializerFQCN The FQCN of the Value serializer
protected int	writeBufferSize The size of the buffer used to write data in disk

Fields inherited from interface org.apache.directory.mavibot.btree.BTree

ALLOW_DUPLICATES, DEFAULT_PAGE_SIZE, DEFAULT_READ_TIMEOUT, DEFAULT_WRITE_BUFFER_SIZE, FORBID_DUPLICATES

Constructor Summary

Constructors

Constructor and Description
AbstractBTree()

Method Summary

Modifier and Type	Method and Description
protected abstract ReadTransaction<K,V>	beginReadTransaction() Starts a Read Only transaction.
protected abstract ReadTransaction<K,V>	beginReadTransaction(long revision) Starts a Read Only transaction.
TupleCursor<K,V>	browse() Creates a cursor starting at the beginning of the tree
TupleCursor<K,V>	browse(long revision) Creates a cursor starting at the beginning of the tree, for a given revision
TupleCursor<K,V>	browseFrom(K key) Creates a cursor starting on the given key
TupleCursor<K,V>	browseFrom(long revision, K key) Creates a cursor starting on the given key at the given revision
KeyCursor<K>	browseKeys() Creates a cursor starting at the beginning of the tree
boolean	contains(K key, V value) Checks if the B-tree contains the given key with the given value.
boolean	contains(long revision, K key, V value) Checks if the B-tree contains the given key with the given value for a given revision
(package private) void	createTransactionManager() Create a thread that is responsible of cleaning the transactions when they hit the timeout
Tuple<K,V>	delete(K key) Delete the entry which key is given as a parameter.
(package private) Tuple<K,V>	delete(K key, long revision) Delete the entry which key is given as a parameter.
Tuple<K,V>	delete(K key, V value) Delete the value from an entry associated with the given key.
(package private) abstract Tuple<K,V>	delete(K key, V value, long revision)
void	flush() Flush the latest revision to disk.
V	get(K key) Find a value in the tree, given its key.
V	get(long revision, K key) Find a value in the tree, given its key, at a specific revision.
protected BTreeHeader<K,V>	getBtreeHeader()
protected BTreeHeader<K,V>	getBtreeHeader(long revision)
java.util.Comparator<K>	getKeyComparator()
ElementSerializer<K>	getKeySerializer()
java.lang.String	getKeySerializerFQCN()
java.lang.String	getName()
long	getNbElems()
int	getPageSize()
private int	getPowerOf2(int size) Gets the number which is a power of 2 immediately above the given positive number.
long	getReadTimeOut()
long	getRevision()
abstract Page<K,V>	getRootPage() Get the current rootPage
BTreeTypeEnum	getType()
java.util.Comparator<V>	getValueComparator()
ValueCursor<V>	getValues(K key)
ElementSerializer<V>	getValueSerializer()
java.lang.String	getValueSerializerFQCN()
int	getWriteBufferSize()
boolean	hasKey(K key) Checks if the given key exists.
boolean	hasKey(long revision, K key) Checks if the given key exists for a given revision.
V	insert(K key, V value) Insert an entry in the B-tree.
(package private) abstract InsertResult<K,V>	insert(K key, V value, long revision)
boolean	isAllowDuplicates()
void	setAllowDuplicates(boolean allowDuplicates)
void	setKeySerializer(ElementSerializer<K> keySerializer)
void	setName(java.lang.String name)
(package private) void	setNbElems(long nbElems)
void	setPageSize(int pageSize) Set the maximum number of elements we can store in a page.
void	setReadTimeOut(long readTimeOut)
(package private) void	setRevision(long revision)
(package private) abstract void	setRootPage(Page<K,V> root)
void	setType(BTreeTypeEnum type)
void	setValueSerializer(ElementSerializer<V> valueSerializer)
void	setWriteBufferSize(int writeBufferSize)
protected void	storeRevision(BTreeHeader<K,V> btreeHeader) Store the new revision in the map of btrees, increment the current revision
protected void	storeRevision(BTreeHeader<K,V> btreeHeader, boolean keepRevisions) Store the new revision in the map of btrees, increment the current revision

Methods inherited from class java.lang.Object

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

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

close, getRootPage

Field Detail

readTimeOut

protected long readTimeOut

The read transaction timeout

currentBtreeHeader

protected BTreeHeader<K,V> currentBtreeHeader

The current Header for a managed BTree

keySerializer

protected ElementSerializer<K> keySerializer

The Key serializer used for this tree.

valueSerializer

protected ElementSerializer<V> valueSerializer

The Value serializer used for this tree.

readTransactions

protected java.util.concurrent.ConcurrentLinkedQueue<ReadTransaction<K,V>> readTransactions

The list of read transactions being executed

writeBufferSize

protected int writeBufferSize

The size of the buffer used to write data in disk

allowDuplicates

protected boolean allowDuplicates

Flag to enable duplicate key support

pageSize

protected int pageSize

The number of elements in a page for this B-tree

name

protected java.lang.String name

The BTree name

keySerializerFQCN

protected java.lang.String keySerializerFQCN

The FQCN of the Key serializer

valueSerializerFQCN

protected java.lang.String valueSerializerFQCN

The FQCN of the Value serializer

readTransactionsThread

protected java.lang.Thread readTransactionsThread

The thread responsible for the cleanup of timed out reads

btreeType

protected BTreeTypeEnum btreeType

The BTree type : either in-memory, disk backed or persisted

transactionStarted

protected java.util.concurrent.atomic.AtomicBoolean transactionStarted

The current transaction

btreeRevisions

protected java.util.Map<java.lang.Long,BTreeHeader<K,V>> btreeRevisions

The map of all the used BtreeHeaders

currentRevision

protected java.util.concurrent.atomic.AtomicLong currentRevision

The current revision

transactionManager

protected TransactionManager transactionManager

The TransactionManager used for this BTree

Constructor Detail

AbstractBTree

AbstractBTree()

Method Detail

beginReadTransaction

protected abstract ReadTransaction<K,V> beginReadTransaction()

Starts a Read Only transaction. If the transaction is not closed, it will be automatically closed after the timeout

Returns:

The created transaction

beginReadTransaction

protected abstract ReadTransaction<K,V> beginReadTransaction(long revision)

Starts a Read Only transaction. If the transaction is not closed, it will be automatically closed after the timeout

Returns:

The created transaction

browse

public TupleCursor<K,V> browse()
                        throws java.io.IOException,
                               KeyNotFoundException

Creates a cursor starting at the beginning of the tree

Specified by:

browse in interface BTree<K,V>

Returns:

A cursor on the B-tree

Throws:

java.io.IOException

KeyNotFoundException

browse

public TupleCursor<K,V> browse(long revision)
                        throws java.io.IOException,
                               KeyNotFoundException

Creates a cursor starting at the beginning of the tree, for a given revision

Specified by:

browse in interface BTree<K,V>

Parameters:

revision - The revision we would like to browse

Returns:

A cursor on the B-tree

Throws:

java.io.IOException - If we had an issue while fetching data from the disk

KeyNotFoundException - If the key is not found in the B-tree

browseFrom

public TupleCursor<K,V> browseFrom(K key)
                            throws java.io.IOException

Creates a cursor starting on the given key

Specified by:

browseFrom in interface BTree<K,V>

Parameters:

key - The key which is the starting point. If the key is not found, then the cursor will always return null.

Returns:

A cursor on the B-tree

Throws:

java.io.IOException

browseFrom

public TupleCursor<K,V> browseFrom(long revision,
                                   K key)
                            throws java.io.IOException,
                                   KeyNotFoundException

Creates a cursor starting on the given key at the given revision

Specified by:

browseFrom in interface BTree<K,V>

key - The key which is the starting point. If the key is not found, then the cursor will always return null.

Returns:

A cursor on the B-tree

Throws:

java.io.IOException - If wxe had an issue reading the B-tree from disk

KeyNotFoundException - If we can't find a rootPage for this revision

contains

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

Checks if the B-tree contains the given key with the given value.

Specified by:

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

contains

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

Checks if the B-tree contains the given key with the given value for a given revision

Specified by:

contains in interface BTree<K,V>

Parameters:

revision - The revision we would like to browse

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:

KeyNotFoundException - If the key is not found in the B-tree

java.io.IOException

delete

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

Delete the entry which key is given as a parameter. If the entry exists, it will be removed from the tree, the old tuple will be returned. Otherwise, null is returned.

Specified by:

delete in interface BTree<K,V>

Parameters:

key - The key for the entry we try to remove

Returns:

A Tuple containing the removed entry, or null if it's not found.

Throws:

java.io.IOException

delete

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

Delete the value from an entry associated with the given key. If the value 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 BTree<K,V>

Parameters:

key - The key for the entry we try to remove

value - The value to delete (can be null)

Returns:

A Tuple containing the removed entry, or null if it's not found.

Throws:

java.io.IOException

delete

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

Delete the entry which key is given as a parameter. If the entry exists, it will be removed from the tree, the old tuple will be returned. Otherwise, null is returned.

Parameters:

key - The key for the entry we try to remove

Returns:

A Tuple containing the removed entry, or null if it's not found.

Throws:

java.io.IOException

delete

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

Throws:

java.io.IOException

insert

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

Insert an entry in the B-tree.

We will replace the value if the provided key already exists in the B-tree.

Specified by:

insert in interface BTree<K,V>

Parameters:

key - Inserted key

value - Inserted value

Returns:

Existing value, if any.

Throws:

java.io.IOException - TODO

insert

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

Throws:

java.io.IOException

flush

public void flush()
           throws java.io.IOException

Flush the latest revision to disk. We will replace the current file by the new one, as we flush in a temporary file.

Specified by:

flush in interface BTree<K,V>

Throws:

java.io.IOException

get

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

Find a value in the tree, given its key. If the key is not found, it will throw a KeyNotFoundException.
Note that we can get a null value stored, or many values.

Specified by:

get in interface BTree<K,V>

Parameters:

key - The key we are looking at

Returns:

The found value, or null if the key is not present in the tree

Throws:

java.io.IOException - TODO

KeyNotFoundException - If the key is not found in the B-tree

get

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

Find a value in the tree, given its key, at a specific revision. If the key is not found, it will throw a KeyNotFoundException.
Note that we can get a null value stored, or many values.

Specified by:

get in interface BTree<K,V>

Parameters:

revision - The revision for which we want to find a key

key - The key we are looking at

Returns:

The found value, or null if the key is not present in the tree

Throws:

java.io.IOException - If there was an issue while fetching data from the disk

KeyNotFoundException - If the key is not found in the B-tree

getRootPage

public abstract Page<K,V> getRootPage()

Get the current rootPage

Specified by:

getRootPage in interface BTree<K,V>

Returns:

The current rootPage

setRootPage

abstract void setRootPage(Page<K,V> root)

getValues

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

Specified by:

getValues in interface BTree<K,V>

Throws:

java.io.IOException

KeyNotFoundException

See Also:

Page.getValues(Object)

hasKey

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

Checks if the given key exists.

Specified by:

hasKey in interface BTree<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

KeyNotFoundException - If the key is not found in the B-tree

hasKey

public boolean hasKey(long revision,
                      K key)
               throws java.io.IOException,
                      KeyNotFoundException

Checks if the given key exists for a given revision.

Specified by:

hasKey in interface BTree<K,V>

Parameters:

revision - The revision for which we want to find a key

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

KeyNotFoundException - If the key is not found in the B-tree

getKeySerializer

public ElementSerializer<K> getKeySerializer()

Specified by:

getKeySerializer in interface BTree<K,V>

Returns:

the keySerializer

setKeySerializer

public void setKeySerializer(ElementSerializer<K> keySerializer)

Specified by:

setKeySerializer in interface BTree<K,V>

Parameters:

keySerializer - the Key serializer to set

getKeySerializerFQCN

public java.lang.String getKeySerializerFQCN()

Specified by:

getKeySerializerFQCN in interface BTree<K,V>

Returns:

the keySerializer FQCN

getValueSerializer

public ElementSerializer<V> getValueSerializer()

Specified by:

getValueSerializer in interface BTree<K,V>

Returns:

the valueSerializer

setValueSerializer

public void setValueSerializer(ElementSerializer<V> valueSerializer)

Specified by:

setValueSerializer in interface BTree<K,V>

Parameters:

valueSerializer - the Value serializer to set

getValueSerializerFQCN

public java.lang.String getValueSerializerFQCN()

Specified by:

getValueSerializerFQCN in interface BTree<K,V>

Returns:

the valueSerializer FQCN

getRevision

public long getRevision()

Specified by:

getRevision in interface BTree<K,V>

Returns:

The current B-tree revision

setRevision

void setRevision(long revision)

storeRevision

protected void storeRevision(BTreeHeader<K,V> btreeHeader,
                             boolean keepRevisions)

Store the new revision in the map of btrees, increment the current revision

storeRevision

protected void storeRevision(BTreeHeader<K,V> btreeHeader)

Store the new revision in the map of btrees, increment the current revision

getReadTimeOut

public long getReadTimeOut()

Specified by:

getReadTimeOut in interface BTree<K,V>

Returns:

the readTimeOut

setReadTimeOut

public void setReadTimeOut(long readTimeOut)

Specified by:

setReadTimeOut in interface BTree<K,V>

Parameters:

readTimeOut - the readTimeOut to set

getNbElems

public long getNbElems()

Specified by:

getNbElems in interface BTree<K,V>

Returns:

The current number of elements in the B-tree

setNbElems

void setNbElems(long nbElems)

getPageSize

public int getPageSize()

Specified by:

getPageSize in interface BTree<K,V>

Returns:

the number of elements per page

setPageSize

public void setPageSize(int pageSize)

Set the maximum number of elements we can store in a page. This must be a number greater than 1, and a power of 2. The default page size is 16.
If the provided size is below 2, we will default to DEFAULT_PAGE_SIZE.
If the provided size is not a power of 2, we will select the closest power of 2 higher than the given number

Specified by:

setPageSize in interface BTree<K,V>

Parameters:

pageSize - The requested page size

getName

public java.lang.String getName()

Specified by:

getName in interface BTree<K,V>

Returns:

the name

setName

public void setName(java.lang.String name)

Specified by:

setName in interface BTree<K,V>

Parameters:

name - the name to set

getKeyComparator

public java.util.Comparator<K> getKeyComparator()

Specified by:

getKeyComparator in interface BTree<K,V>

Returns:

the key comparator

getValueComparator

public java.util.Comparator<V> getValueComparator()

Specified by:

getValueComparator in interface BTree<K,V>

Returns:

the value comparator

getWriteBufferSize

public int getWriteBufferSize()

Specified by:

getWriteBufferSize in interface BTree<K,V>

Returns:

the writeBufferSize

setWriteBufferSize

public void setWriteBufferSize(int writeBufferSize)

Specified by:

setWriteBufferSize in interface BTree<K,V>

Parameters:

writeBufferSize - the writeBufferSize to set

isAllowDuplicates

public boolean isAllowDuplicates()

Specified by:

isAllowDuplicates in interface BTree<K,V>

Returns:

true if this B-tree allow duplicate values

setAllowDuplicates

public void setAllowDuplicates(boolean allowDuplicates)

Specified by:

setAllowDuplicates in interface BTree<K,V>

Parameters:

allowDuplicates - True if the B-tree will allow duplicate values

getType

public BTreeTypeEnum getType()

Specified by:

getType in interface BTree<K,V>

Returns:

the type

setType

public void setType(BTreeTypeEnum type)

Parameters:

type - the type to set

getPowerOf2

private int getPowerOf2(int size)

Gets the number which is a power of 2 immediately above the given positive number.

getBtreeHeader

protected BTreeHeader<K,V> getBtreeHeader()

Returns:

The current BtreeHeader

getBtreeHeader

protected BTreeHeader<K,V> getBtreeHeader(long revision)

Returns:

The current BtreeHeader

browseKeys

public KeyCursor<K> browseKeys()
                        throws java.io.IOException,
                               KeyNotFoundException

Creates a cursor starting at the beginning of the tree

Specified by:

browseKeys in interface BTree<K,V>

Returns:

A cursor on the B-tree keys

Throws:

java.io.IOException

KeyNotFoundException

createTransactionManager

void createTransactionManager()

Create a thread that is responsible of cleaning the transactions when they hit the timeout