net.metanotion.io.block.index

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

java.lang.Object

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

net.metanotion.io.block.index.BSkipSpan<K,V>

Type Parameters:

K - type of keys maintained by this skip span

V - type of values stored in this skip span

All Implemented Interfaces:

Flushable

Direct Known Subclasses:

IBSkipSpan

public class BSkipSpan<K extends Comparable<? super K>,V>
extends SkipSpan<K,V>

SkipList span implementation with in-memory key-value storage.

Stores all keys and values in memory for fast access while maintaining disk persistence. Supports overflow to additional pages when capacity is exceeded.

On-disk format:

   First Page:
     Magic number (int)
     overflow page (unsigned int)
     previous page (unsigned int)
     next page (unsigned int)
     max keys (unsigned short)
     number of keys (unsigned short)
     for each key:
         key length (unsigned short)
         value length (unsigned short)
         key data
         value data

   Overflow pages:
     Magic number (int)
     next overflow page (unsigned int)
 

Field Summary

Fields

Modifier and Type	Field and Description
protected BlockFile	bf Reference to the BlockFile
static int	CONT_HEADER_LEN Continuation page header length in bytes
protected static int	HEADER_LEN Fixed header length in bytes
protected boolean	isKilled Whether this span has been killed/deleted
protected Serializer<K>	keySer Key serializer
protected static int	MAGIC Magic number for span pages ("Span")
protected int	nextPage Next page number
protected int	overflowPage Overflow page number
protected int	page Page number of this span
protected int	prevPage Previous page number
protected int	spanSize Number of keys this span can hold
protected Serializer<V>	valSer Value serializer

Fields inherited from class net.metanotion.util.skiplist.SkipSpan

keys, MAX_SIZE, next, nKeys, prev, vals

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	BSkipSpan(BlockFile bf, BSkipList<K,V> bsl) Create a new BSkipSpan with the given BlockFile and BSkipList.
	BSkipSpan(BlockFile bf, BSkipList<K,V> bsl, int spanPage, Serializer<K> key, Serializer<V> val) Create a BSkipSpan and load its data from disk.

Method Summary

Modifier and Type	Method and Description
void	flush() Flush this span to disk.
static void	init(BlockFile bf, int page, int spanSize) Initialize a new span page on disk.
void	killInstance() Mark this span instance as killed and free its resources.
protected void	loadData() Load the span's keys and values into memory (second half of load()).
protected void	loadData(boolean flushOnError) Load the span's keys and values into memory.
protected static <X extends Comparable<? super X>,Y> void	loadInit(BSkipSpan<X,Y> bss, BlockFile bf, BSkipList<X,Y> bsl, int spanPage, Serializer<X> key, Serializer<Y> val) Load the span headers from disk (first half of load()).
protected void	lostEntries(int firstBadEntry, int lastGoodPage) Attempt to recover from corrupt data in this span.
SkipSpan<K,V>	newInstance(SkipList<K,V> sl) Create a new instance of this span type.
String	toString() Get a string representation of this span.

Methods inherited from class net.metanotion.util.skiplist.SkipSpan

firstKey, get, getEnd, getSpan, print, put, remove

Methods inherited from class java.lang.Object

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

Field Detail

bf

protected final BlockFile bf

Reference to the BlockFile

CONT_HEADER_LEN

public static final int CONT_HEADER_LEN

Continuation page header length in bytes

See Also:

Constant Field Values

HEADER_LEN

protected static final int HEADER_LEN

Fixed header length in bytes

See Also:

Constant Field Values

isKilled

protected boolean isKilled

Whether this span has been killed/deleted

keySer

protected Serializer<K extends Comparable<? super K>> keySer

Key serializer

MAGIC

protected static final int MAGIC

Magic number for span pages ("Span")

See Also:

Constant Field Values

nextPage

protected int nextPage

Next page number

overflowPage

protected int overflowPage

Overflow page number

page

protected int page

Page number of this span

prevPage

protected int prevPage

Previous page number

spanSize

protected int spanSize

Number of keys this span can hold

valSer

protected Serializer<V> valSer

Value serializer

Constructor Detail

BSkipSpan

protected BSkipSpan(BlockFile bf,
                    BSkipList<K,V> bsl)

Create a new BSkipSpan with the given BlockFile and BSkipList.

Parameters:

bf - the BlockFile

bsl - the BSkipList

BSkipSpan

public BSkipSpan(BlockFile bf,
                 BSkipList<K,V> bsl,
                 int spanPage,
                 Serializer<K> key,
                 Serializer<V> val)
          throws IOException

Create a BSkipSpan and load its data from disk.

Parameters:

bf - the BlockFile

bsl - the BSkipList

spanPage - the page number of this span

key - the key serializer

val - the value serializer

Throws:

IOException - if an I/O error occurs

Method Detail

flush

public void flush()

Flush this span to disk.

Specified by:

flush in interface Flushable

Overrides:

flush in class SkipSpan<K extends Comparable<? super K>,V>

init

public static void init(BlockFile bf,
                        int page,
                        int spanSize)
                 throws IOException

Initialize a new span page on disk.

Parameters:

bf - the BlockFile to write to

page - the page number to initialize

spanSize - the size of the span

Throws:

IOException - if an I/O error occurs

killInstance

public void killInstance()

Mark this span instance as killed and free its resources.

Overrides:

killInstance in class SkipSpan<K extends Comparable<? super K>,V>

loadData

protected void loadData()
                 throws IOException

Load the span's keys and values into memory (second half of load()).

Throws:

IOException - if an I/O error occurs

loadData

protected void loadData(boolean flushOnError)
                 throws IOException

Load the span's keys and values into memory.

Parameters:

flushOnError - set to false if you are going to flush anyway

Throws:

IOException - if an I/O error occurs

loadInit

protected static <X extends Comparable<? super X>,Y> void loadInit(BSkipSpan<X,Y> bss,
                                                                   BlockFile bf,
                                                                   BSkipList<X,Y> bsl,
                                                                   int spanPage,
                                                                   Serializer<X> key,
                                                                   Serializer<Y> val)
                                                            throws IOException

Load the span headers from disk (first half of load()). Only reads the span headers.

Type Parameters:

X - the key type

Y - the value type

Parameters:

bss - the BSkipSpan to load into

bf - the BlockFile

bsl - the BSkipList

spanPage - the page number

key - the key serializer

val - the value serializer

Throws:

IOException - if an I/O error occurs

lostEntries

protected void lostEntries(int firstBadEntry,
                           int lastGoodPage)

Attempt to recover from corrupt data in this span. All entries starting with firstBadEntry are lost. Zero out the overflow page on lastGoodPage, and correct the number of entries in the first page. We don't attempt to free the lost continuation pages.

Parameters:

firstBadEntry - the first entry index that is corrupted

lastGoodPage - the last good page number

newInstance

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

Create a new instance of this span type.

Overrides:

newInstance in class SkipSpan<K extends Comparable<? super K>,V>

Parameters:

sl - the SkipList to create the span for

Returns:

a new SkipSpan instance

toString

public String toString()

Get a string representation of this span.

Overrides:

toString in class Object

Returns:

a string representation