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 Details

    • MAGIC

      protected static final int MAGIC
      Magic number for span pages ("Span")
      See Also:

    • HEADER_LEN

      protected static final int HEADER_LEN
      Fixed header length in bytes
      See Also:

    • CONT_HEADER_LEN

      public static final int CONT_HEADER_LEN
      Continuation page header length in bytes
      See Also:

    • bf

      protected final BlockFile bf
      Reference to the BlockFile

    • bsl

      private final BSkipList<K extends Comparable<? super K>, V> bsl
      Reference to the BSkipList

    • page

      protected int page
      Page number of this span

    • overflowPage

      protected int overflowPage
      Overflow page number

    • prevPage

      protected int prevPage
      Previous page number

    • nextPage

      protected int nextPage
      Next page number

    • keySer

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

    • valSer

      protected Serializer<V> valSer
      Value serializer

    • spanSize

      protected int spanSize
      Number of keys this span can hold

    • isKilled

      protected boolean isKilled
      Whether this span has been killed/deleted

  • Constructor Details

    • BSkipSpan

      protected BSkipSpan(BlockFile bf, BSkipList<K,V> bsl)
      Create a new BSkipSpan with the given BlockFile and BSkipList.
      Parameters:
      bf - the BlockFile this span is stored in
      bsl - the BSkipList this span belongs to

    • 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 this span is stored in
      bsl - the BSkipList this span belongs to
      spanPage - the page number of this span
      key - the key serializer
      val - the value serializer
      Throws:
      IOException - if an I/O error occurs

  • Method Details

    • 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

    • 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

    • 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>

    • freeContinuationPages

      private int freeContinuationPages(int curPage) throws IOException
      Free a chain of continuation pages
      Parameters:
      curPage - the first page to be freed, if 0 this does nothing.
      Returns:
      the number of pages freed
      Throws:
      IOException - if a page read or free fails, or a continuation page has a bad magic number

    • 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>

    • fflush

      private void fflush()
      I2P - avoid super.flush()

    • load

      private static <X extends Comparable<? super X>, Y>void load(BSkipSpan<X,Y> bss, BlockFile bf, BSkipList<X,Y> bsl, int spanPage, Serializer<X> key, Serializer<Y> val) throws IOException
      Load a BSkipSpan from disk.
      Type Parameters:
      X - the key type
      Y - the value type
      Parameters:
      bss - the BSkipSpan to load into
      bf - the BlockFile this span is stored in
      bsl - the BSkipList this span belongs to
      spanPage - the page number
      key - the key serializer
      val - the value serializer
      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 this span is stored in
      bsl - the BSkipList this span belongs to
      spanPage - the page number
      key - the key serializer
      val - the value serializer
      Throws:
      IOException - if an I/O error occurs

    • 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

    • 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

    • toString

      public String toString()
      Get a string representation of this span.
      Overrides:
      toString in class Object
      Returns:
      a string representation