org.helidb.backend.heap
Class HeapBackend<K,V>

java.lang.Object
  org.helidb.backend.AbstractDatabaseBackend<K,V,Long>
      org.helidb.backend.heap.HeapBackend<K,V>

Type Parameters:

K - The type of keys.

V - The type of values.

All Implemented Interfaces:

Iterable<Record<K,V>>, DatabaseBackend<K,V,Long>

public class HeapBackend<K,V>
extends AbstractDatabaseBackend<K,V,Long>

This backend implementation takes database records and puts them on a heap. The heap is a file where new records are appended, so inserts are very fast. To find a record, the entire heap is scanned from the beginning, which means that the average time to find a database record increases linearly with the number of records in the database (minus the effects of hard drive caching). If a record is deleted, the heap becomes fragmented and. It can then be defragmented by calling the compact() method.

Keys and values may be of variable size. If both keys and values are of constant size when serialized, use ConstantRecordSizeHeapBackend instead.

The maximum length of a database record (key and value) is Integer.MAX_VALUE - 4 bytes.

The format of the file where the data is stored is:

File ::= Record*
 Record ::= Record_header Key Value
 Record_header ::= 
 Deleted_flag
  &ndash 1 byte: 1 for deleted, 0 for active
 Record_size
  &ndash 4 bytes, big-endian integer, size of key + value
 Key_size
  &ndash 4 bytes, big-endian integer, size of key
 

The total size of a record is the Record_size plus the size of the header (nine bytes).

The backend uses a key and a value Serializer for serializing and interpreting keys and values. It is required that different keys never are serialized to the same byte array value and vice versa.

When iterating over a database using this backend using a Cursor, an iterator, a key iterator or a value iterator, the records are always returned in the order that they were inserted. If the database uses an index, the index implementation may modify that behavior. (See the documentation for the index implementation.)

Backwards iteration is not supported by this backend. The getLastPosition() and getPreviousPosition(Long) methods both throw UnsupportedOperationException:s. Adding an index to the database backend may change that.

This backend supports all search modes defined in SearchMode. Searching the database using SearchMode.CLOSEST_MATCH, SearchMode.CLOSEST_ABOVE or SearchMode.CLOSEST_BELOW and no custom Comparator requires that the keys in the backend are Comparable and it will cause the backend to iterate through all records to find the closest matching key (unless an exact match is found before the end of the data).

Since:

1.0

Author:

Karl Gustafsson

See Also:

ConstantRecordSizeHeapBackend, HeapBackendFactory

In_jar:

helidb-core

Field Summary

static int

DEFAULT_BUFFER_SIZE The default buffer size for internal buffers.

Constructor Summary

HeapBackend(RandomlyAccessibleFile dbFile, boolean readOnly, Serializer<K> keySerializer, Serializer<V> valueSerializer, LogAdapterHolder lah)
Create a new heap backend for read/write access with database data starting at position 0 in the supplied file and the buffer size set to 8192 bytes.

HeapBackend(RandomlyAccessibleFile dbFile, boolean readOnly, Serializer<K> keySerializer, Serializer<V> valueSerializer, long startPosOfDb, int bufferSize, LogAdapterHolder lah)
Create a new heap backend.

Method Summary

protected void	assertNotClosed() Subclasses implement this to throw an IllegalStateException if the database backend is closed.
void	clear() Wipe out the entire database.
void	close() Close this database backend and release all resources associated with it (close files and release locks, for instance).
boolean	compact() This compacts the database by removing holes left by deleted elements.
boolean	delete(K key) Delete the record with the supplied key, if it exists.
Long	find(K key) Find the position of the record with the supplied key in the database backend.
void	forEachKey(ForEachKeyCallback<K,Long> callback) For each key in the database, call the callback object.
Long	getFirstPosition() Get the position of the "first" record in the backend.
Set<K>	getKeys() Return an immutable Set containing all keys in the database.
Long	getLastPosition() This method throws an UnsupportedOperationException.
Long	getNextPosition(Long pos) Get the position of the "next" record in the backend, relative to the record at the supplied position.
Long	getPreviousPosition(Long pos) This method throws an UnsupportedOperationException.
Set<Record<K,V>>	getRecords() Return an immutable Set containing all database records (keys and values).
V	getValueFor(K key) Get the value for the record with the supplied key.
Collection<V>	getValues() Return an immutable Collection containing all values in the database.
Long	insert(K key, V value) Insert a new record in the database.
Long	insertCheckKeyUnique(K key, V value) Insert a new record in the database after verifying that the key is unique within the database.
boolean	insertOrUpdate(K key, V value) If a record with the supplied key exists, update its value.
Iterator<Record<K,V>>	iterator()
Iterator<K>	keyIterator() Get an iterator for all keys in the database.
K	readKeyAt(Long pos) Read the key at the supplied position.
Record<K,V>	readRecordAt(Long pos) Read the record (key and value) at the specified position.
V	readValueAt(Long pos) Read the value at the specified position.
V	remove(K key) Delete the record with the supplied key and return its value.
void	removeAt(Long pos, K key) Delete the record at the supplied position.
void	replaceContentsWith(RandomAccess ra, long dataSize) Replace the contents of the database with content read from the supplied RandomAccess.
Pair<Long>	update(K key, V value) Update an existing record with a new value.
Long	updateAt(Long pos, K key, V value) Update the record at the supplied position with the new value.
Iterator<V>	valueIterator() Get an iterator for all the values in the database.
long	writeContentsTo(RandomAccess ra) Write the contents of the entire database to the current position in the supplied RandomAccess.

Methods inherited from class org.helidb.backend.AbstractDatabaseBackend

addRecordMoveListener, find, find, getContentsVersion, hasRecordMoveListeners, notifyRecordMoveListeners, removeRecordMoveListener, updateContentsVersion

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_BUFFER_SIZE

public static final int DEFAULT_BUFFER_SIZE

The default buffer size for internal buffers.

See Also:

Constant Field Values

Constructor Detail

HeapBackend

public HeapBackend(RandomlyAccessibleFile dbFile,
                   boolean readOnly,
                   Serializer<K> keySerializer,
                   Serializer<V> valueSerializer,
                   LogAdapterHolder lah)

Create a new heap backend for read/write access with database data starting at position 0 in the supplied file and the buffer size set to 8192 bytes. The buffer size is used when creating internal temporary buffers used when compacting the database, etc.

The HeapBackendBuilder may be more convenient to use than this constructor.

Parameters:

dbFile - The file containing the database data.

readOnly - Should the database only be read from?

keySerializer - Serializer for keys.

valueSerializer - Serializer for values.

lah - A log adapter holder.

See Also:

HeapBackend(RandomlyAccessibleFile, boolean, Serializer, Serializer, long, int, LogAdapterHolder)

HeapBackend

public HeapBackend(RandomlyAccessibleFile dbFile,
                   boolean readOnly,
                   Serializer<K> keySerializer,
                   Serializer<V> valueSerializer,
                   long startPosOfDb,
                   int bufferSize,
                   LogAdapterHolder lah)
            throws IllegalArgumentException

Create a new heap backend.

The HeapBackendBuilder may be more convenient to use than this constructor.

Parameters:

dbFile - The file containing the database data.

readOnly - Should the database be read only?

keySerializer - Serializer for keys.

valueSerializer - Serializer for values.

startPosOfDb - The start position of the database in the database file. The database file may contain a header that this backend does not care about. In this case, set this value to the size of that header.

bufferSize - The size of internal buffers used when compacting the database. 8192 may be appropriate. If the database has large records, a higher value speeds up compact() a bit at the expense of more memory usage.

lah - A log adapter holder.

Throws:

IllegalArgumentException - If the buffer size is negative.

See Also:

HeapBackend(RandomlyAccessibleFile, boolean, Serializer, Serializer, LogAdapterHolder)

Method Detail

assertNotClosed

protected void assertNotClosed()
                        throws IllegalStateException

Description copied from class: AbstractDatabaseBackend

Subclasses implement this to throw an IllegalStateException if the database backend is closed.

Specified by:

assertNotClosed in class AbstractDatabaseBackend<K,V,Long>

Throws:

IllegalStateException - Thrown if the database backend is closed.

insert

public Long insert(K key,
                   V value)

Description copied from interface: DatabaseBackend

Insert a new record in the database.

Parameters:

key - The key. It is not verified that this key is unique. Inserting duplicate keys will result in unspecified behavior from the backend.

value - The value.

Returns:

The position of the new record.

insertCheckKeyUnique

public Long insertCheckKeyUnique(K key,
                                 V value)

Description copied from interface: DatabaseBackend

Insert a new record in the database after verifying that the key is unique within the database.

Parameters:

key - The key.

value - The value.

Returns:

The position of the new record.

insertOrUpdate

public boolean insertOrUpdate(K key,
                              V value)

Description copied from interface: DatabaseBackend

If a record with the supplied key exists, update its value. If not, insert a new record.

Parameters:

key - The key.

value - The value.

Returns:

true if an existing record was updated, false if a new record was inserted.

updateAt

public Long updateAt(Long pos,
                     K key,
                     V value)

Description copied from interface: DatabaseBackend

Update the record at the supplied position with the new value. The new key is always the same as the previous key.

It is up to the implementation to decide exactly how this is done. It is not required that the record should be located at the same position in the backend after the update. One strategy for implementing this method is to delete the old record and insert a new record with the updated values.

Parameters:

pos - The position of the record to update.

key - The record's key. The key is not modified by the update.

value - The new value.

Returns:

The new position of the record.

update

public Pair<Long> update(K key,
                         V value)

Description copied from interface: DatabaseBackend

Update an existing record with a new value.

It is up to the implementation to decide exactly how this is done. It is not required that the record should be located at the same position in the backend after the update. One strategy for implementing this method is to delete the old record and insert a new record with the updated values.

Parameters:

key - The record's key.

value - The record's new value.

Returns:

The record's old position (the first object in the pair) and the new position (the second object in the pair).

getFirstPosition

public Long getFirstPosition()
                      throws WrappedIOException,
                             IllegalStateException

Description copied from interface: DatabaseBackend

Get the position of the "first" record in the backend. The meaning of "first" is specified by the backend implementation. If the backend sorts the keys, this method returns the position of the first key in the sorted set of keys.

Returns:

The position of the first record in the backend, or null if the backend is empty.

Throws:

WrappedIOException - On I/O errors.

IllegalStateException - If the database backend has been closed.

See Also:

DatabaseBackend.getLastPosition(), DatabaseBackend.getNextPosition(Object), DatabaseBackend.getPreviousPosition(Object)

getLastPosition

public Long getLastPosition()
                     throws IllegalStateException,
                            UnsupportedOperationException

This method throws an UnsupportedOperationException.

Returns:

The position of the last record in the backend, or null if the backend is empty.

Throws:

UnsupportedOperationException - Backwards iteration is not supported by the heap backend.

IllegalStateException - If the database backend has been closed.

See Also:

DatabaseBackend.getFirstPosition(), DatabaseBackend.getNextPosition(Object), DatabaseBackend.getPreviousPosition(Object)

getNextPosition

public Long getNextPosition(Long pos)
                     throws WrappedIOException,
                            IllegalStateException

Description copied from interface: DatabaseBackend

Get the position of the "next" record in the backend, relative to the record at the supplied position. The meaning of "next" is specified by the backend implementation. If the backend sorts the keys, this method returns the position of the next key, relative to the key at the supplied position.

Parameters:

pos - The position to search from. This must be the position of a record in the backend. If it is not, the behavior of this method is unspecified.

Returns:

The position of the next key in the database backend, or null if the supplied position references the last record in the backend (the position returned from DatabaseBackend.getLastPosition()).

Throws:

WrappedIOException - On I/O errors.

IllegalStateException - If the database backend has been closed.

See Also:

DatabaseBackend.getFirstPosition(), DatabaseBackend.getLastPosition(), DatabaseBackend.getPreviousPosition(Object)

getPreviousPosition

public Long getPreviousPosition(Long pos)
                         throws WrappedIOException,
                                IllegalStateException,
                                UnsupportedOperationException

This method throws an UnsupportedOperationException.

Parameters:

pos - The position to search from. This must be the position of a record in the backend. If it is not, the behavior of this method is unspecified.

Returns:

The position of the previous key in the database backend, or null if the supplied position references the first record in the backend (the position returned from DatabaseBackend.getFirstPosition()).

Throws:

UnsupportedOperationException - Backwards iteration is not supported by the heap backend.

WrappedIOException - On I/O errors.

IllegalStateException - If the database backend has been closed.

See Also:

DatabaseBackend.getFirstPosition(), DatabaseBackend.getLastPosition(), DatabaseBackend.getNextPosition(Object)

iterator

public Iterator<Record<K,V>> iterator()

keyIterator

public Iterator<K> keyIterator()

Description copied from interface: DatabaseBackend

Get an iterator for all keys in the database. The iterator may or may not return the keys in a specific order. See the backend implementation documentation.

If the database is modified after calling this method, the methods of the Iterator returned will throw ConcurrentModificationException

Returns:

An Iterator over the database's keys.

valueIterator

public Iterator<V> valueIterator()

Description copied from interface: DatabaseBackend

Get an iterator for all the values in the database.

If the database is modified after calling this method, the methods of the Iterator returned will throw ConcurrentModificationException

Returns:

An Iterator over the database's values.

clear

public void clear()

Description copied from interface: DatabaseBackend

Wipe out the entire database.

find

public Long find(K key)

Description copied from interface: DatabaseBackend

Find the position of the record with the supplied key in the database backend.

Parameters:

key - The key to find.

Returns:

The position of the key, or null if not found.

See Also:

DatabaseBackend.find(Comparable, SearchMode), DatabaseBackend.find(Object, SearchMode, Comparator)

getValueFor

public V getValueFor(K key)

Description copied from interface: DatabaseBackend

Get the value for the record with the supplied key.

Parameters:

key - The record's key.

Returns:

The record's value or null if no record in the database has the supplied key.

getKeys

public Set<K> getKeys()

Description copied from interface: DatabaseBackend

Return an immutable Set containing all keys in the database.

Returns:

An immutable Set containing all keys in the database. If the database is empty, this method returns an empty Set.

getValues

public Collection<V> getValues()

Description copied from interface: DatabaseBackend

Return an immutable Collection containing all values in the database.

Returns:

An immutable Collection containing all values in the database. If the database is empty, this method returns an empty Collection.

getRecords

public Set<Record<K,V>> getRecords()

Description copied from interface: DatabaseBackend

Return an immutable Set containing all database records (keys and values).

Returns:

An immutable Set containing all database records. If the database is empty, this method returns an empty Set.

readKeyAt

public K readKeyAt(Long pos)
            throws WrappedIOException,
                   IllegalStateException

Description copied from interface: DatabaseBackend

Read the key at the supplied position.

Parameters:

pos - The position of the record containing the key. This must be a valid position in the backend. It it is not, the behavior of this method is unspecified.

Returns:

The key.

Throws:

WrappedIOException - On I/O errors.

IllegalStateException - If the database backend has been closed.

See Also:

DatabaseBackend.readValueAt(Object), DatabaseBackend.readRecordAt(Object)

readValueAt

public V readValueAt(Long pos)

Description copied from interface: DatabaseBackend

Read the value at the specified position.

Parameters:

pos - The position of the record containing the value. This must be a valid position in the backend. If it is not, the behavior of this method is unspecified.

Returns:

The value.

See Also:

DatabaseBackend.readKeyAt(Object), DatabaseBackend.readRecordAt(Object)

readRecordAt

public Record<K,V> readRecordAt(Long pos)
                         throws WrappedIOException,
                                IllegalStateException

Description copied from interface: DatabaseBackend

Read the record (key and value) at the specified position.

Parameters:

pos - The position of the record. This must be a valid position in the backend. If it is not, the behavior of this method is unspecified.

Returns:

The record.

Throws:

WrappedIOException - On I/O errors.

IllegalStateException - If the database backend has been closed.

See Also:

DatabaseBackend.readKeyAt(Object), DatabaseBackend.readValueAt(Object)

removeAt

public void removeAt(Long pos,
                     K key)

Description copied from interface: DatabaseBackend

Delete the record at the supplied position.

Parameters:

pos - The position of the record to delete.

key - The key for the record to remove.

delete

public boolean delete(K key)

Description copied from interface: DatabaseBackend

Delete the record with the supplied key, if it exists.

Parameters:

key - The record's key.

Returns:

true if a record was deleted.

remove

public V remove(K key)

Description copied from interface: DatabaseBackend

Delete the record with the supplied key and return its value.

Parameters:

key - The record's key.

Returns:

The record's value or null if no record in the database has the supplied key.

forEachKey

public void forEachKey(ForEachKeyCallback<K,Long> callback)

Description copied from interface: DatabaseBackend

For each key in the database, call the callback object.

This can for instance be used for building indices for the database.

Parameters:

callback - The callback object to call for each key.

compact

public boolean compact()

This compacts the database by removing holes left by deleted elements. Each record after the first hole is moved a distance backwards in the file that is equal to the combined sizes of all holes up to that record.

Returns:

true if the backend was modified, false if not.

writeContentsTo

public long writeContentsTo(RandomAccess ra)

Description copied from interface: DatabaseBackend

Write the contents of the entire database to the current position in the supplied RandomAccess.

After writing, the current position of the RandomAccess should be at the end of the written data.

Parameters:

ra - The RandomAccess to write to. It is not closed after writing.

Returns:

The size of the contents in bytes.

replaceContentsWith

public void replaceContentsWith(RandomAccess ra,
                                long dataSize)

Description copied from interface: DatabaseBackend

Replace the contents of the database with content read from the supplied RandomAccess. The database contents start at the RandomAccess' current position.

Parameters:

ra - The RandomAccess to read data from. It should not be closed after reading.

dataSize - The total size of the database data in bytes.

close

public void close()

Description copied from interface: DatabaseBackend

Close this database backend and release all resources associated with it (close files and release locks, for instance).