alluxio.client.keyvalue

Class LinearProbingIndex

java.lang.Object

alluxio.client.keyvalue.LinearProbingIndex

All Implemented Interfaces:

Index

@NotThreadSafe
public final class LinearProbingIndex
extends Object
implements Index

Index structure using linear probing. It keeps a collection of buckets. Each bucket stores a fingerprint (a byte) and an offset (an int) indicating where to find the key and the value in the payload.

The index hash table looks like: ===================================== | fingerprint (byte) | offset (int) | ===================================== | fingerprint (byte) | offset (int) | ===================================== | ... | If fingerprint is zero, it indicates the bucket is empty.

The overall byte array of the index looks like: | key count (int) | the above hash table |

Field Summary

Fields

Modifier and Type	Field and Description
static int	MAX_PROBES Max number of probes for linear probing.

Method Summary

Modifier and Type	Method and Description
int	byteCount()
static LinearProbingIndex	createEmptyIndex()
byte	fingerprintHash(byte[] key) Hashes a key in byte array into a non-zero, one byte fingerprint.
byte	fingerprintHash(ByteBuffer key) Hashes a key in ByteBuffer into a non-zero, one byte fingerprint.
ByteBuffer	get(ByteBuffer key, PayloadReader reader) Gets the bytes of value given the key and payload storage reader.
byte[]	getBytes()
int	indexHash(byte[] key) Hashes a key in byte array to a bucket index in non-negative integer value.
int	indexHash(ByteBuffer key) Hashes a key in ByteBuffer to a bucket index in non-negative integer value.
int	keyCount()
Iterator<ByteBuffer>	keyIterator(PayloadReader reader) Gets an iterator to iterate over all keys.
static LinearProbingIndex	loadFromByteArray(ByteBuffer buffer) Creates an instance of linear probing index by loading its content from a buffer.
ByteBuffer	nextKey(ByteBuffer currentKey, PayloadReader reader) Gets the next key relative to the current provided key.
boolean	put(byte[] key, byte[] value, PayloadWriter writer) Puts a key into the index and stores key and value data into payload storage.

Methods inherited from class java.lang.Object

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

Field Detail

MAX_PROBES

public static final int MAX_PROBES

Max number of probes for linear probing.

See Also:

Constant Field Values

Method Detail

createEmptyIndex

public static LinearProbingIndex createEmptyIndex()

Returns:

an instance of linear probing index, with no key added

loadFromByteArray

public static LinearProbingIndex loadFromByteArray(ByteBuffer buffer)

Creates an instance of linear probing index by loading its content from a buffer. The Buffer.position must be at the beginning of index.

Parameters:

buffer - intput buffer storing the index

Returns:

an instance of linear probing index

byteCount

public int byteCount()

Specified by:

byteCount in interface Index

Returns:

size of this index in bytes

keyCount

public int keyCount()

Specified by:

keyCount in interface Index

Returns:

the number of keys inserted

put

public boolean put(byte[] key,
                   byte[] value,
                   PayloadWriter writer)
            throws IOException

Description copied from interface: Index

Puts a key into the index and stores key and value data into payload storage.

Specified by:

put in interface Index

Parameters:

key - bytes of key

value - bytes of value

writer - writer to store key-value payload

Returns:

true on success, false otherwise (e.g., unresolvable hash collision)

Throws:

IOException

get

public ByteBuffer get(ByteBuffer key,
                      PayloadReader reader)

Description copied from interface: Index

Gets the bytes of value given the key and payload storage reader.

Specified by:

get in interface Index

Parameters:

key - bytes of key

reader - reader to access key-value payload

Returns:

ByteBuffer of value, or null if not found

getBytes

public byte[] getBytes()

Specified by:

getBytes in interface Index

Returns:

byte array which contains raw bytes of this index

indexHash

public int indexHash(byte[] key)

Hashes a key in byte array to a bucket index in non-negative integer value.

Parameters:

key - key in byte array

Returns:

bucket index of key

indexHash

public int indexHash(ByteBuffer key)

Hashes a key in ByteBuffer to a bucket index in non-negative integer value.

Parameters:

key - key in byte array

Returns:

bucket index of key

fingerprintHash

public byte fingerprintHash(byte[] key)

Hashes a key in byte array into a non-zero, one byte fingerprint.

Parameters:

key - key in byte array

Returns:

value of fingerprint in byte which is never zero

fingerprintHash

public byte fingerprintHash(ByteBuffer key)

Hashes a key in ByteBuffer into a non-zero, one byte fingerprint.

Parameters:

key - key in byte array

Returns:

value of fingerprint in byte which is never zero

nextKey

public ByteBuffer nextKey(ByteBuffer currentKey,
                          PayloadReader reader)

Description copied from interface: Index

Gets the next key relative to the current provided key.

This could be more efficient than iterating over Index.keyIterator(PayloadReader) to find the next key.

Specified by:

nextKey in interface Index

Parameters:

currentKey - the current key, or null if there is no initial key known yet

reader - reader to access key-value payload

Returns:

the next key, or null if there are no remaining keys

keyIterator

public Iterator<ByteBuffer> keyIterator(PayloadReader reader)

Description copied from interface: Index

Gets an iterator to iterate over all keys.

This could be more efficient than repeatedly calling Index.nextKey(ByteBuffer, PayloadReader).

Specified by:

keyIterator in interface Index

Parameters:

reader - reader to access key-value payload

Returns:

an iterator of keys, the iterator does not support remove