Control.Concurrent.TBox.TSkipList

Provides an implementation of a skip list in the AdvSTM monad. A skip list is a probabilistic data structure with map-like operations. In contrast to a balanced tree, a skip list does not need any rebalancing, which makes it suitable for concurrent programming. See: William Pugh. Skip Lists: A Probabilistic Alternative to Balanced Trees.

The elements of the skip list are stored in a TBox. When an element of the skip list is modified, the operation is relegated to the corresponding TBox.

For a concrete instance see module Control.Concurrent.TFile.TSkipList

Data type

data TSkipList t k a

newIO

Arguments

:: TBox t k a

=> Float

Probability for choosing a new level

-> Int

Maximum number of levels

-> IO (TSkipList t k a)

An empty skiplist.

Operations

insert :: (Ord k, TBox t k a) => k -> a -> TSkipList t k a -> AdvSTM ()

lookup :: (Ord k, TBox t k a) => k -> TSkipList t k a -> AdvSTM (Maybe a)

update :: (Ord k, TBox t k a) => k -> a -> TSkipList t k a -> AdvSTM ()

Updates an element. Throws AssertionFailed if the element is not in the list.

delete :: (Ord k, TBox t k a) => k -> TSkipList t k a -> AdvSTM ()

geq :: (Ord k, TBox t k a) => k -> TSkipList t k a -> AdvSTM (Map k a)

Returns all elements that are greater than the key. TODO: currently in O(n), can be made more efficient (like leq)

leq :: (Ord k, TBox t k a) => k -> TSkipList t k a -> AdvSTM (Map k a)

Returns all elements that are smaller than the key.

min :: (Ord k, TBox t k a) => TSkipList t k a -> AdvSTM (Maybe a)

Returns the element with the least key, if it exists. O(1).

filter :: (Ord k, TBox t k a) => (k -> a -> Bool) -> TSkipList t k a -> AdvSTM (Map k a)

Returns all elements that satisfy the predicate. O(n).

Low-level Operations

insertNode :: (Ord k, TBox t k a) => k -> Node t k a -> TSkipList t k a -> AdvSTM ()

lookupNode :: (Ord k, TBox t k a) => k -> TSkipList t k a -> AdvSTM (Maybe (Node t k a))

readAndValidate :: (Ord k, TBox t k a) => TSkipList t k a -> Node t k a -> AdvSTM (Maybe a)

Reads the TBox of the node. If the TBox is empty, the node is removed from the skip list. This is necessary when TBoxs are shared between different data structures.

newNode :: TBox t k a => k -> t k a -> Int -> AdvSTM (Node t k a)

contentTBox :: Node t k a -> t k a

key :: Node t k a -> k

Utilities

chooseLevel :: TSkipList t k a -> AdvSTM Int

Returns a randomly chosen level. Is used for inserting new elements. Note that this function uses unsafeIOToAdvSTM to access the random number generator.

toString :: (Ord k, Show k, TBox t k a) => k -> TSkipList t k a -> AdvSTM String

Debug helper. Returns the skip list as a string. All elements smaller than the given key are written to the string.