com.bigdata.btree.raba
Class MutableKeyBuffer

java.lang.Object
  com.bigdata.btree.raba.AbstractKeyBuffer
      com.bigdata.btree.raba.MutableKeyBuffer

All Implemented Interfaces:

IRaba, Iterable<byte[]>

public class MutableKeyBuffer
extends AbstractKeyBuffer

A flyweight mutable implementation exposing the backing byte[][] and supporting search.

Version:

$Id: MutableKeyBuffer.java 2265 2009-10-26 12:51:06Z thompsonbry $

Author:

Bryan Thompson

Field Summary

byte[][]	keys An array containing the keys.
int	nkeys The #of defined keys.

Constructor Summary

MutableKeyBuffer(int capacity)
Allocate a mutable key buffer capable of storing capacity keys.

MutableKeyBuffer(int nkeys, byte[][] keys)
Constructor wraps an existing byte[][].

MutableKeyBuffer(int capacity, IRaba src)
Builds a mutable key buffer.

MutableKeyBuffer(MutableKeyBuffer src)
Creates a new instance using a new array of keys but sharing the key references with the provided MutableKeyBuffer.

Method Summary

protected int	_binarySearch(int searchKeyOffset, byte[] searchKey) Binary search.
protected int	_linearSearch(int searchKeyOffset, byte[] searchKey) Linear search.
protected int	_prefixMatchLength(int prefixLength, byte[] searchKey) Test the search key against the leading prefix shared by all bytes in the key buffer.
int	add(byte[] key) Append a byte[] value to the end of the logical byte[][] (optional operation).
int	add(byte[] key, int off, int len) Append a byte[] value to the end of the logical byte[][] (optional operation).
int	add(DataInput in, int len) Append a byte[] value to the end of the logical byte[][] (optional operation).
void	assertKeysMonotonic() Verifies that the keys are in sort order and that undefined keys are [null].
int	capacity() The maximum #of keys that may be held in the buffer (its capacity).
int	copy(int index, OutputStream out) Copy the value at the specified index onto the output stream.
byte[]	get(int index) Returns a reference to the key at that index.
byte[]	getPrefix() Computes the #of leading bytes shared by all keys and returns a new byte[] containing those bytes.
int	getPrefixLength() Computes the length of the prefix by computed by counting the #of leading bytes that match for the first and last key in the buffer.
int	insert(int index, byte[] key) Insert a key into the buffer at the specified index, incrementing the #of keys in the buffer by one and moving down all keys from that index on down by one (towards the end of the array).
boolean	isEmpty() True iff the logical byte[][] is empty.
boolean	isFull() True iff the key buffer can not contain another key.
boolean	isKeys() Instances are searchable and do not allow nulls.
boolean	isNull(int index) Return true iff the byte[] at that index is null.
boolean	isReadOnly() Mutable.
int	length(int index) The length of the byte[] at that index.
int	remove(int index) Remove a key in the buffer at the specified index, decrementing the #of keys in the buffer by one and moving up all keys from that index on down by one (towards the start of the array).
int	search(byte[] searchKey) Search for the given searchKey in the key buffer (optional operation).
void	set(int index, byte[] key) Set the key at the specified index.
int	size() The #of entries in the logical byte[][].
String	toString()

Methods inherited from class com.bigdata.btree.raba.AbstractKeyBuffer

iterator

Methods inherited from class java.lang.Object

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

Field Detail

nkeys

public int nkeys

The #of defined keys.

keys

public final byte[][] keys

An array containing the keys. The size of the array is the maximum capacity of the key buffer.

Constructor Detail

MutableKeyBuffer

public MutableKeyBuffer(int capacity)

Allocate a mutable key buffer capable of storing capacity keys.

Parameters:

capacity - The capacity of the key buffer.

MutableKeyBuffer

public MutableKeyBuffer(int nkeys,
                        byte[][] keys)

Constructor wraps an existing byte[][].

Parameters:

nkeys - The #of defined keys in the array.

keys - The array of keys.

MutableKeyBuffer

public MutableKeyBuffer(MutableKeyBuffer src)

Creates a new instance using a new array of keys but sharing the key references with the provided MutableKeyBuffer.

Parameters:

src - An existing instance.

MutableKeyBuffer

public MutableKeyBuffer(int capacity,
                        IRaba src)

Builds a mutable key buffer.

Parameters:

capacity - The capacity of the new instance (this is based on the branching factor for the B+Tree).

src - The source data.

Throws:

IllegalArgumentException - if the capacity is LT the IRaba.size() of the src.

IllegalArgumentException - if the source is null.

Method Detail

get

public final byte[] get(int index)

Returns a reference to the key at that index.

Parameters:

index - The index in [0:IRaba.size()-1].

Returns:

The byte[] value at that index and null if a null value was stored at that index.

length

public final int length(int index)

Description copied from interface: IRaba

The length of the byte[] at that index.

Parameters:

index - The index in [0:IRaba.size()-1].

Returns:

The length of the byte[] at that index.

copy

public final int copy(int index,
                      OutputStream out)

Description copied from interface: IRaba

Copy the value at the specified index onto the output stream. This is often used with an ByteArrayBuffer so that the same backing byte[] can be overwritten by each visited key.

Parameters:

index - The index in [0:IRaba.size()-1].

Returns:

The #of bytes copied.

isNull

public final boolean isNull(int index)

Description copied from interface: IRaba

Return true iff the byte[] at that index is null. If IRaba.isKeys() would return true then this method MUST return false since nulls are not permitted for B+Tree keys.

Parameters:

index - The index in [0:IRaba.size()-1].

isEmpty

public final boolean isEmpty()

Description copied from interface: IRaba

True iff the logical byte[][] is empty.

size

public final int size()

Description copied from interface: IRaba

The #of entries in the logical byte[][].

capacity

public final int capacity()

The maximum #of keys that may be held in the buffer (its capacity).

isFull

public final boolean isFull()

True iff the key buffer can not contain another key.

isReadOnly

public final boolean isReadOnly()

Mutable.

isKeys

public final boolean isKeys()

Instances are searchable and do not allow nulls.

Returns:

true if the IRaba represents B+Tree keys and false if it represents B+Tree values.

set

public final void set(int index,
                      byte[] key)

Set the key at the specified index.

Parameters:

index - The index in [0:nkeys-1].

key - The key (non-null).

TODO:

Who uses this? Track prefixLength?

add

public final int add(byte[] key)

Description copied from interface: IRaba

Append a byte[] value to the end of the logical byte[][] (optional operation).

Parameters:

key - A value.

Returns:

The #of values in the logical byte[][] (postcondition).

add

public final int add(byte[] key,
                     int off,
                     int len)

Description copied from interface: IRaba

Append a byte[] value to the end of the logical byte[][] (optional operation).

Parameters:

key - A value

off - The offset of the first byte to be copied.

len - The #of bytes to be copied.

Returns:

The #of values in the logical byte[][] (postcondition).

add

public int add(DataInput in,
               int len)
        throws IOException

Description copied from interface: IRaba

Append a byte[] value to the end of the logical byte[][] (optional operation).

Parameters:

in - The input stream from which the byte[] will be read.

len - The #of bytes to be read.

Returns:

The #of values in the logical byte[][] (postcondition).

Throws:

IOException

insert

public final int insert(int index,
                        byte[] key)

Insert a key into the buffer at the specified index, incrementing the #of keys in the buffer by one and moving down all keys from that index on down by one (towards the end of the array).

Parameters:

index - The index in [0:nkeys] (you are allowed to append using this method).

key - The key.

Returns:

The #of keys in the buffer.

TODO:

if index==0 || index==nkeys-1 then update prefixLength, lazily compute prefix.

remove

public final int remove(int index)

Remove a key in the buffer at the specified index, decrementing the #of keys in the buffer by one and moving up all keys from that index on down by one (towards the start of the array).

Parameters:

index - The index in [0:nkeys-1].

key - The key.

Returns:

The #of keys in the buffer.

TODO:

if index==0 || index==nkeys-1 then update prefixLength, lazily compute prefix (requires that the application never directly modifies keys).

toString

public String toString()

Overrides:

toString in class Object

search

public final int search(byte[] searchKey)

Description copied from interface: IRaba

Search for the given searchKey in the key buffer (optional operation). Whether or not search is supported depends on whether the logical byte[][] is ordered. However, the efficiency of search, where supported, depends on the implementation. Some implementations support binary search of the coded byte[] values. Others may require a mixture of binary and linear search, etc.

 entryIndex = -entryIndex - 1
 

or just

 entryIndex = -entryIndex
 

if you are looking for the first key after the searchKey.

Parameters:

searchKey - The search key.

Returns:

index of the search key, if it is found; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

_prefixMatchLength

protected final int _prefixMatchLength(int prefixLength,
                                       byte[] searchKey)

Description copied from class: AbstractKeyBuffer

Test the search key against the leading prefix shared by all bytes in the key buffer.

Specified by:

_prefixMatchLength in class AbstractKeyBuffer

Parameters:

prefixLength - The length of the prefix shared by all keys in the buffer.

searchKey - The search key.

Returns:

Zero iff all bytes match and otherwise the insert position for the search key in the buffer. The insert position will be before the first key iff the search key is less than the prefix (-1) and will be after the last key iff the search key is greater than the prefix (-(nkeys)-1).

_linearSearch

protected final int _linearSearch(int searchKeyOffset,
                                  byte[] searchKey)

Description copied from class: AbstractKeyBuffer

Linear search.

Specified by:

_linearSearch in class AbstractKeyBuffer

_binarySearch

protected final int _binarySearch(int searchKeyOffset,
                                  byte[] searchKey)

Description copied from class: AbstractKeyBuffer

Binary search.

Specified by:

_binarySearch in class AbstractKeyBuffer

assertKeysMonotonic

public final void assertKeysMonotonic()

Verifies that the keys are in sort order and that undefined keys are [null].

getPrefixLength

public int getPrefixLength()

Computes the length of the prefix by computed by counting the #of leading bytes that match for the first and last key in the buffer.

Specified by:

getPrefixLength in class AbstractKeyBuffer

getPrefix

public byte[] getPrefix()

Computes the #of leading bytes shared by all keys and returns a new byte[] containing those bytes.

Specified by:

getPrefix in class AbstractKeyBuffer