net.metanotion.io.block.index

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

java.lang.Object

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

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

Type Parameters:

K - the type of keys maintained by this skip level structure

V - the type of mapped values

All Implemented Interfaces:

Flushable

public class BSkipLevels<K extends Comparable<? super K>,V>
extends SkipLevels<K,V>

SkipList level management for multi-level indexing.

Manages hierarchical structure of SkipList levels to provide efficient search paths through data structure.

On-disk format:

    Magic number (long)
    max height (unsigned short)
    non-null height (unsigned short)
    span page (unsigned int)
    height number of level pages (unsigned ints)
 

Always fits on one page.

Field Summary

Fields

Modifier and Type	Field and Description
BlockFile	bf Reference to the BlockFile
(package private) static int	HEADER_LEN Fixed header length in bytes
int	levelPage Page number of this level
int	spanPage Page number of the associated span

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

bottom, levels, MAX_SIZE

Constructor Summary

Constructors

Constructor and Description
BSkipLevels(BlockFile bf, int levelPage, BSkipList<K,V> bsl) Create a BSkipLevels and load it from disk.

Method Summary

Modifier and Type	Method and Description
boolean	blvlck(boolean fix) Run an integrity check on this level.
boolean	blvlck(boolean fix, int width, SkipLevels<K,V>[] prevLevels) Run an integrity check on this level with additional parameters.
void	flush() Flush this level to disk.
static void	init(BlockFile bf, int page, int spanPage, int maxHeight) Initialize a new BSkipLevels page on disk.
void	initializeLevels() Non-recursive initializer.
void	killInstance() Mark this level as killed and free its resources.
SkipLevels<K,V>	newInstance(int levels, SkipSpan<K,V> ss, SkipList<K,V> sl) Create a new instance of this level type.
String	toString() Get a string representation of this level.

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

get, getEnd, getSpan, key, print, printAll, put, remove

Methods inherited from class java.lang.Object

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

Field Detail

bf

public final BlockFile bf

Reference to the BlockFile

HEADER_LEN

static final int HEADER_LEN

Fixed header length in bytes

See Also:

Constant Field Values

levelPage

public final int levelPage

Page number of this level

spanPage

public final int spanPage

Page number of the associated span

Constructor Detail

BSkipLevels

public BSkipLevels(BlockFile bf,
                   int levelPage,
                   BSkipList<K,V> bsl)
            throws IOException

Create a BSkipLevels and load it from disk. Non-recursive initializer initializeLevels() MUST be called on the first BSkipLevel in the skiplist after the constructor, unless it's a new empty level and init() was previously called.

Parameters:

bf - the BlockFile

levelPage - the page number of this level

bsl - the BSkipList

Throws:

IOException - if an I/O error occurs

Method Detail

blvlck

public boolean blvlck(boolean fix)

Run an integrity check on this level.

Overrides:

blvlck in class SkipLevels<K extends Comparable<? super K>,V>

Parameters:

fix - if true, attempt to fix corruption

Returns:

true if the levels were modified

blvlck

public boolean blvlck(boolean fix,
                      int width,
                      SkipLevels<K,V>[] prevLevels)

Run an integrity check on this level with additional parameters.

Overrides:

blvlck in class SkipLevels<K extends Comparable<? super K>,V>

Parameters:

fix - if true, attempt to fix corruption

width - the current width

prevLevels - previous levels to check

Returns:

true if corruption was found

flush

public void flush()

Flush this level to disk.

Specified by:

flush in interface Flushable

Overrides:

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

init

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

Initialize a new BSkipLevels page on disk.

Parameters:

bf - the BlockFile

page - the page number

spanPage - the span page number

maxHeight - the maximum height

Throws:

IOException - if an I/O error occurs

initializeLevels

public void initializeLevels()

Non-recursive initializer. MUST be called on the first BSkipLevel in the skiplist after the constructor, unless it's a new empty level and init() was previously called. Only call on the first skiplevel in the list!

killInstance

public void killInstance()

Mark this level as killed and free its resources.

Overrides:

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

newInstance

public SkipLevels<K,V> newInstance(int levels,
                                   SkipSpan<K,V> ss,
                                   SkipList<K,V> sl)

Create a new instance of this level type.

Overrides:

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

Parameters:

levels - the number of levels

ss - the SkipSpan

sl - the SkipList

Returns:

a new BSkipLevels instance

toString

public String toString()

Get a string representation of this level.

Overrides:

toString in class Object

Returns:

a string representation