java.lang.Object
net.metanotion.util.skiplist.SkipList<K,V>
Type Parameters:
K - type of keys, must be comparable
V - type of values
All Implemented Interfaces:
Flushable, Iterable<V>
Direct Known Subclasses:
BSkipList
public class SkipList<K extends Comparable<? super K>, V>extends Object implements Flushable, Iterable<V>
Skip list data structure implementation for efficient key-value storage and retrieval. Provides O(log n) average time complexity for search, insertion, and deletion operations.

  • Field Summary

    Modifier and Type
    Field
    Description
    protected SkipSpan<K,V>
    first
    First span in the list.
    private static final int
    MIN_SLOTS
    What maxLevels() reports - span counts are no longer tracked here.
    protected static final int
    P
    The probability of each next higher level.
    static final Random
    rng
    Random number generator, the I2P one rather than the upstream default.
    protected int
    size
    Number of items in the list.
    protected SkipLevels<K,V>
    stack
    Level stack above the first span.

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    SkipList()
    Constructor for subclass use.
    SkipList(int span)
    Create a new skip list.

  • Method Summary

    All Methods
    Modifier and Type
    Method
    Description
    void
    addItem()
    Increment item count.
    void
    balance()
    Rebalance the skip list levels, adjusted to guarantee O(log n) searches.
    void
    delItem()
    Decrement item count, minimum zero.
    SkipIterator<K,V>
    find(K key)
    Look up the first stored key greater than or equal to the one given, returning an iterator already positioned there.
    void
    flush()
    Flush any pending writes.
    int
    generateColHeight()
    Choose the column height for a newly inserted node, using the geometric distribution that keeps the list's search cost logarithmic.
    V
    get(K key)
    Get the value for a key.
    SkipIterator<K,V>
    iterator()
    Return an iterator over all entries.
    int
    maxLevels()
    Fix if for some reason you want a huge in-memory skiplist.
    void
    put(K key, V val)
    Insert or update a key-value pair in the skip list.
    V
    remove(K key)
    Remove a key-value pair from the skip list.
    int
    size()
    Return the number of items.

    Methods inherited from class Object

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

    Methods inherited from interface Iterable

    forEach, spliterator

  • Field Details

    • P

      protected static final int P
      The probability of each next higher level.
      See Also:

    • MIN_SLOTS

      private static final int MIN_SLOTS
      What maxLevels() reports - span counts are no longer tracked here.
      See Also:

    • first

      protected SkipSpan<K extends Comparable<? super K>, V> first
      First span in the list. Reassigned, though it is never replaced after construction.

    • stack

      protected SkipLevels<K extends Comparable<? super K>, V> stack
      Level stack above the first span.

    • rng

      public static final Random rng
      Random number generator, the I2P one rather than the upstream default.

    • size

      protected int size
      Number of items in the list.

  • Constructor Details

    • SkipList

      protected SkipList()
      Constructor for subclass use.

    • SkipList

      public SkipList(int span)
      Create a new skip list.
      Parameters:
      span - the maximum number of entries per span, 1 to SkipSpan.MAX_SIZE
      Throws:
      IllegalArgumentException - if size too big or too small

  • Method Details

    • flush

      public void flush()
      Flush any pending writes.
      Specified by:
      flush in interface Flushable

    • size

      public int size()
      Return the number of items.
      Returns:
      the number of entries currently held in the list

    • addItem

      public void addItem()
      Increment item count.

    • delItem

      public void delItem()
      Decrement item count, minimum zero.

    • maxLevels

      public int maxLevels()
      Fix if for some reason you want a huge in-memory skiplist.
      Returns:
      4 since we don't track span count here any more - see override

    • generateColHeight

      public int generateColHeight()
      Choose the column height for a newly inserted node, using the geometric distribution that keeps the list's search cost logarithmic.
      Returns:
      0..maxLevels(), each successive one with probability 1 / P

    • put

      public void put(K key, V val)
      Insert or update a key-value pair in the skip list.
      Parameters:
      key - the key to insert, or whose existing entry is to be replaced
      val - the value stored under that key

    • remove

      public V remove(K key)
      Remove a key-value pair from the skip list.
      Parameters:
      key - the key whose entry is to be removed
      Returns:
      the previous value, or null if not found

    • get

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

    • iterator

      public SkipIterator<K,V> iterator()
      Return an iterator over all entries.
      Specified by:
      iterator in interface Iterable<K extends Comparable<? super K>>

    • find

      public SkipIterator<K,V> find(K key)
      Look up the first stored key greater than or equal to the one given, returning an iterator already positioned there.
      Parameters:
      key - the key to position the iterator at
      Returns:
      an iterator where nextKey() is the first one greater than or equal to 'key'

    • balance

      public void balance()
      Rebalance the skip list levels, adjusted to guarantee O(log n) searches. The work is proportional to the number of spans.