java.lang.Object
net.metanotion.util.skiplist.SkipLevels<K,V>
Type Parameters:
K - type of keys, must be comparable
V - type of values
All Implemented Interfaces:
Flushable
Direct Known Subclasses:
BSkipLevels
public class SkipLevels<K extends Comparable<? super K>, V>extends Object implements Flushable
Manages the level structure for a skip list data structure. Maintains pointers to different levels in the skip list hierarchy.

  • Field Details

    • MAX_SIZE

      public static final int MAX_SIZE
      Maximum number of levels in a skip list
      See Also:

    • levels

      public SkipLevels<K extends Comparable<? super K>, V>[] levels
      Array of level pointers at each height

    • bottom

      public SkipSpan<K extends Comparable<? super K>, V> bottom
      Bottom level pointer to the actual SkipSpan

    • _log

      private final Log _log
      Logger for this instance

  • Constructor Details

    • SkipLevels

      protected SkipLevels()
      Protected constructor for subclasses.

    • SkipLevels

      public SkipLevels(int size, SkipSpan<K,V> span)
      Create a new SkipLevels with the specified size.
      Parameters:
      size - the number of levels
      span - the bottom SkipSpan
      Throws:
      IllegalArgumentException - if size too big or too small

  • Method Details

    • newInstance

      public SkipLevels<K,V> newInstance(int levels, SkipSpan<K,V> ss, SkipList<K,V> sl)
      Create a new instance of this SkipLevels.
      Parameters:
      levels - the number of levels to create
      ss - the SkipSpan to use
      sl - accepted for signature compatibility with the other levels, unused
      Returns:
      a new SkipLevels instance

    • killInstance

      public void killInstance()
      Mark this instance as killed.

    • flush

      public void flush()
      Flush this level to disk.
      Specified by:
      flush in interface Flushable

    • print

      public String print()
      Print this level and all levels below it.
      Returns:
      a string representation of this level

    • printAll

      public String printAll()
      Print this level and all levels below it, recursively.
      Returns:
      a string representation of all levels

    • getEnd

      public SkipSpan<K,V> getEnd()
      Get the end span of this level.
      Returns:
      the last SkipSpan in this chain

    • getSpan

      public SkipSpan<K,V> getSpan(int start, K key, int[] search)
      Get the span containing or following the given key.
      Parameters:
      start - the starting level
      key - the key to locate, compared with compareTo() against each level's key
      search - search parameters and results
      Returns:
      the SkipSpan containing the key

    • key

      public K key()
      Get the key at the bottom of this level.
      Returns:
      the first key

    • get

      public V get(int start, K key)
      Get the value associated with the given key.
      Parameters:
      start - the starting level
      key - the key whose associated value is wanted
      Returns:
      the value, or null if not found

    • remove

      public Object[] remove(int start, K key, SkipList<K,V> sl)
      Remove a key-value pair from the skip list.
      Parameters:
      start - the starting level
      key - the key of the entry to remove
      sl - the owning SkipList, passed down and used for the head pointer
      Returns:
      An array of two objects or null. rv[0] is the removed object. rv[1] is the deleted SkipLevels if the removed object was the last in the SkipLevels, and the deleted SkipLevels is taller than this SkipLevels. rv is null if no object was removed.

    • put

      public SkipLevels<K,V> put(int start, K key, V val, SkipList<K,V> sl)
      Put a key-value pair into the skip list.
      Parameters:
      start - the starting level
      key - the key to map to the value, replacing any existing entry
      val - the value
      sl - the owning SkipList, which supplies the random column height
      Returns:
      the new level if it caused a split and we made a new level, and the new level is taller than our level; else null if it went in an existing level or the new level is our height or less.

    • blvlck

      public boolean blvlck(boolean fix)
      Run an integrity check on this level.
      Parameters:
      fix - if true, attempt to fix corruption
      Returns:
      true if corruption was found

    • blvlck

      public boolean blvlck(boolean fix, int width, SkipLevels<K,V>[] prevLevels)
      Run an integrity check on this level with additional parameters.
      Parameters:
      fix - if true, attempt to fix corruption
      width - the current width
      prevLevels - previous levels to check
      Returns:
      true if corruption was found