java.lang.Object
net.metanotion.util.skiplist.SkipSpan<K,V>
Type Parameters:
K - type of keys, must be comparable
V - type of values
All Implemented Interfaces:
Flushable
Direct Known Subclasses:
BSkipSpan
public class SkipSpan<K extends Comparable<? super K>, V>extends Object implements Flushable
Represents a span or node in a skip list data structure. Contains arrays of keys and values at a specific level in the skip list.

  • Field Details

    • MAX_SIZE

      public static final int MAX_SIZE
      Maximum number of entries in a span (limited by BlockFile.spanSize)
      See Also:

    • nKeys

      public int nKeys
      Number of keys in this span

    • keys

      public K extends Comparable<? super K>[] keys
      Array of keys

    • vals

      public V[] vals
      Array of values

    • next

      public SkipSpan<K extends Comparable<? super K>, V> next
      Next and previous spans

    • prev

      public SkipSpan<K extends Comparable<? super K>, V> prev
      Previous span

  • Constructor Details

    • SkipSpan

      protected SkipSpan()
      Protected constructor for subclasses.

    • SkipSpan

      public SkipSpan(int size)
      Create a new SkipSpan with the specified capacity.
      Parameters:
      size - the maximum number of key-value pairs
      Throws:
      IllegalArgumentException - if size too big or too small

  • Method Details

    • newInstance

      public SkipSpan<K,V> newInstance(SkipList<K,V> sl)
      Create a new instance of this span type.
      Parameters:
      sl - the SkipList to create the span for
      Returns:
      a new SkipSpan instance

    • killInstance

      public void killInstance()
      Mark this instance as killed.

    • flush

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

    • print

      public String print()
      Dump all data from this span to the end.
      Returns:
      a string representation of this span and all following spans

    • binarySearch

      private int binarySearch(K key)
      Finds the key among this span's entries.
      Parameters:
      key - the key to look for
      Returns:
      where it is, or where it belongs

    • getEnd

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

    • getSpan

      public SkipSpan<K,V> getSpan(K key, int[] search)
      Get the span containing the given key.
      Parameters:
      key - the key to locate, compared using its natural ordering
      search - search parameters and results
      Returns:
      the SkipSpan containing the key

    • get

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

    • pushTogether

      private void pushTogether(int hole)
      Moves entries left to close a hole.
      Parameters:
      hole - the entry removed to make room

    • pushApart

      private void pushApart(int start)
      Moves entries right to open a hole.
      Parameters:
      start - where the hole is opened

    • split

      private void split(int loc, K key, V val, SkipList<K,V> sl)
      Divides this span in two at a point.
      Parameters:
      loc - where to split
      key - the key being inserted
      val - its value
      sl - the list being changed

    • insert

      private SkipSpan<K,V> insert(int loc, K key, V val, SkipList<K,V> sl)
      Insert a span at the given position.
      Parameters:
      loc - the index in this span's key and value arrays to insert at
      key - the key to insert
      val - the value stored under the key
      sl - the list the entry belongs to, used to create a span on split
      Returns:
      the new span if it caused a split, else null if it went in this span

    • put

      public SkipSpan<K,V> put(K key, V val, SkipList<K,V> sl)
      Put a key-value pair into this span.
      Parameters:
      key - the key to store the value under
      val - the value
      sl - the list to bump and split
      Returns:
      the new span if it caused a split, else null if it went in this span

    • remove

      public Object[] remove(K key, SkipList<K,V> sl)
      Remove a key-value pair from this span.
      Parameters:
      key - the key whose entry is to be deleted
      sl - the list to shrink if this span empties out
      Returns:
      An array of two objects or null. rv[0] is the removed object. rv[1] is the deleted SkipSpan if the removed object was the last in the SkipSpan. rv is null if no object was removed.

    • firstKey

      public K firstKey()
      Get the first key in this span.
      Returns:
      the first key, or null if empty