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 Details

    • MAGIC

      private static final long MAGIC
      Written first in a persisted level, so a wrong file is recognised
      See Also:

    • HEADER_LEN

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

    • levelPage

      public final int levelPage
      Page number of this level

    • spanPage

      public final int spanPage
      Page number of the associated span

    • bf

      public final BlockFile bf
      Reference to the BlockFile

    • bsl

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

    • isKilled

      private boolean isKilled
      Whether this level has been killed

    • lps

      private final int[] lps
      The level pages, passed from the constructor to initializeLevels()

  • Constructor Details

    • 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(BlockFile, int, int, int) was previously called.
      Parameters:
      bf - the BlockFile that owns the page this level is read from
      levelPage - the page number of this level
      bsl - the BSkipList this level is registered in, for its levelHash and spanHash caches
      Throws:
      IOException - if an I/O error occurs

  • Method Details

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

    • initializeLevels

      private void initializeLevels(List<BSkipLevels<K,V>> nextInit)
      Non-recursive initializer. MUST be called after constructor.
      Parameters:
      nextInit - out parameter, next levels to initialize

    • 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 that the page is allocated from
      page - the page number
      spanPage - the span page number
      maxHeight - the maximum height
      Throws:
      IOException - if an I/O error occurs

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

    • 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 whose page this level is built above
      sl - the SkipList that owns this level
      Returns:
      a new BSkipLevels instance

    • 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

    • blvlfix

      private boolean blvlfix()
      Fix the levels. Only call from the first level. Primarily to fix nulls in levels caused by previous SkipLevels bug. This should handle dups and loops and out-of-order levels too, but those may cause problems before this in the constructor. This is fast enough to call every time the skiplist is opened.
      Returns:
      true if the levels were modified.

    • getAllLevels

      private void getAllLevels(SkipLevels<K,V> l, Set<SkipLevels<K,V>> lvlSet)
      Breadth-first, sortof We assume everything is findable from the root level
      Parameters:
      l - non-null
      lvlSet - out parameter, the result

    • 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

    • toString

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