Package net.metanotion.io.block.index

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

java.lang.Object

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

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

All Implemented Interfaces:

Closeable, Flushable, AutoCloseable, Iterable<V>

public class BSkipList<K extends Comparable<? super K>,V>
extends SkipList<K,V>
implements Closeable

On-disk format:

    Magic number (long)
    first span page (unsigned int)
    first level page (unsigned int)
    size (unsigned int)
    spans (unsigned int)
    levels (unsigned int)

Always fits on one page.

Field Summary

Fields

Modifier and Type	Field	Description
final BlockFile	bf
int	firstLevelPage
int	firstSpanPage
(package private) final HashMap<Integer,SkipLevels<K,V>>	levelHash
int	skipPage
(package private) final HashMap<Integer,BSkipSpan<K,V>>	spanHash

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

first, P, rng, size, stack

Constructor Summary

Constructors

Constructor	Description
BSkipList(int spanSize, BlockFile bf, int skipPage, Serializer<K> key, Serializer<V> val)
BSkipList(int spanSize, BlockFile bf, int skipPage, Serializer<K> key, Serializer<V> val, boolean fileOnly)

Method Summary

Modifier and Type	Method	Description
boolean	bslck(boolean fix, boolean isMeta)	Run an integrity check on the skiplist and all the levels in it
void	close()
void	delete()	must be open (do not call close() first)
SkipIterator<K,V>	find(K key)	find
void	flush()
static void	init(BlockFile bf, int page, int spanSize)
SkipIterator<K,V>	iterator()
int	maxLevels()
String	toString()

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

addItem, balance, delItem, generateColHeight, get, print, printSL, put, remove, size

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Details

firstSpanPage

public int firstSpanPage

firstLevelPage

public int firstLevelPage

skipPage

public int skipPage

bf

public final BlockFile bf

spanHash

final HashMap<Integer,BSkipSpan<K extends Comparable<? super K>,V>> spanHash

levelHash

final HashMap<Integer,SkipLevels<K extends Comparable<? super K>,V>> levelHash

Constructor Details

BSkipList

public BSkipList(int spanSize,
 BlockFile bf,
 int skipPage,
 Serializer<K> key,
 Serializer<V> val)
          throws IOException

Throws:

IOException

BSkipList

public BSkipList(int spanSize,
 BlockFile bf,
 int skipPage,
 Serializer<K> key,
 Serializer<V> val,
 boolean fileOnly)
          throws IOException

Throws:

IOException

Method Details

close

public void close()

Specified by:

close in interface AutoCloseable

Specified by:

close in interface Closeable

flush

public void flush()

Specified by:

flush in interface Flushable

Overrides:

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

delete

public void delete()
            throws IOException

must be open (do not call close() first)

Throws:

IOException

init

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

Throws:

IOException

maxLevels

public int maxLevels()

Overrides:

maxLevels in class SkipList<K extends Comparable<? super K>,V>

Returns:

log2(span count), minimum 4

iterator

public SkipIterator<K,V> iterator()

Specified by:

iterator in interface Iterable<K extends Comparable<? super K>>

Overrides:

iterator in class SkipList<K extends Comparable<? super K>,V>

find

public SkipIterator<K,V> find(K key)

find

Overrides:

find in class SkipList<K extends Comparable<? super K>,V>

Returns:

an iterator where nextKey() is the first one greater than or equal to 'key'

bslck

public boolean bslck(boolean fix,
 boolean isMeta)

Run an integrity check on the skiplist and all the levels in it

Returns:

true if the levels were modified.

toString

public String toString()

Overrides:

toString in class Object