net.metanotion.util.skiplist

Class SkipSpan<K extends Comparable<? super K>,V>

java.lang.Object

net.metanotion.util.skiplist.SkipSpan<K,V>

Type Parameters:

K - type of keys, must be comparable

V - type of values

All Implemented Interfaces:

Flushable

Direct Known Subclasses:

BSkipSpan

public class SkipSpan<K extends Comparable<? super K>,V>
extends Object
implements Flushable

Represents a span or node in a skip list data structure. Contains arrays of keys and values at a specific level in the skip list.

Field Summary

Fields

Modifier and Type	Field and Description
K[]	keys Array of keys
static int	MAX_SIZE Maximum number of entries in a span (limited by BlockFile.spanSize)
SkipSpan<K,V>	next Next and previous spans
int	nKeys Number of keys in this span
SkipSpan<K,V>	prev Next and previous spans
V[]	vals Array of values

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	SkipSpan() Protected constructor for subclasses.
	SkipSpan(int size) Create a new SkipSpan with the specified capacity.

Method Summary

Modifier and Type	Method and Description
K	firstKey() Get the first key in this span.
void	flush() Flush this span to disk.
V	get(K key) Get the value associated with the given key.
SkipSpan<K,V>	getEnd() Get the end span of this chain.
SkipSpan<K,V>	getSpan(K key, int[] search) Get the span containing the given key.
void	killInstance() Mark this instance as killed.
SkipSpan<K,V>	newInstance(SkipList<K,V> sl) Create a new instance of this span type.
String	print() Dump all data from this span to the end.
SkipSpan<K,V>	put(K key, V val, SkipList<K,V> sl) Put a key-value pair into this span.
Object[]	remove(K key, SkipList<K,V> sl) Remove a key-value pair from this span.

Methods inherited from class java.lang.Object

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

Field Detail

keys

public K extends Comparable<? super K>[] keys

Array of keys

MAX_SIZE

public static final int MAX_SIZE

Maximum number of entries in a span (limited by BlockFile.spanSize)

See Also:

Constant Field Values

next

public SkipSpan<K extends Comparable<? super K>,V> next

Next and previous spans

nKeys

public int nKeys

Number of keys in this span

prev

public SkipSpan<K extends Comparable<? super K>,V> prev

Next and previous spans

vals

public V[] vals

Array of values

Constructor Detail

SkipSpan

protected SkipSpan()

Protected constructor for subclasses.

SkipSpan

public SkipSpan(int size)

Create a new SkipSpan with the specified capacity.

Parameters:

size - the maximum number of key-value pairs

Throws:

IllegalArgumentException - if size too big or too small

Method Detail

firstKey

public K firstKey()

Get the first key in this span.

Returns:

the first key, or null if empty

flush

public void flush()

Flush this span to disk.

Specified by:

flush in interface Flushable

get

public V get(K key)

Get the value associated with the given key.

Parameters:

key - the key to search for

Returns:

the value, or null if not found

getEnd

public SkipSpan<K,V> getEnd()

Get the end span of this chain.

Returns:

the last SkipSpan in the chain

getSpan

public SkipSpan<K,V> getSpan(K key,
                             int[] search)

Get the span containing the given key.

Parameters:

key - the key to search for

search - search parameters and results

Returns:

the SkipSpan containing the key

killInstance

public void killInstance()

Mark this instance as killed.

newInstance

public SkipSpan<K,V> newInstance(SkipList<K,V> sl)

Create a new instance of this span type.

Parameters:

sl - the SkipList to create the span for

Returns:

a new SkipSpan instance

print

public String print()

Dump all data from this span to the end.

Returns:

a string representation of this span and all following spans

put

public SkipSpan<K,V> put(K key,
                         V val,
                         SkipList<K,V> sl)

Put a key-value pair into this span.

Parameters:

key - the key

val - the value

sl - the SkipList

Returns:

the new span if it caused a split, else null if it went in this span

remove

public Object[] remove(K key,
                       SkipList<K,V> sl)

Remove a key-value pair from this span.

Parameters:

key - the key to remove

sl - the SkipList

Returns:

An array of two objects or null. rv[0] is the removed object. rv[1] is the deleted SkipSpan if the removed object was the last in the SkipSpan. rv is null if no object was removed.