Control.Concurrent.STM.TSkipList

This module provides an implementation of a skip list in the STM monad. The elements of the skip list are stored in a TVar.

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 (expensive) rebalancing operation, which makes it particularly suitable for concurrent programming.

See: William Pugh. Skip Lists: A Probabilistic Alternative to Balanced Trees.

This module should be imported qualified.

Example (GHCi):

 t <- newIO 0.5 5  :: IO (TSkipList Int String) 
 atomically $ sequence_ [ insert i (show i) t | i <- [1..10] ]

 putStrLn =<< atomically (toString 100 t)
 9
 9
 3 7 9
 1 3 7 9
 1 2 3 4 5 6 7 8 9 10

 atomically $ delete  7 t
 putStrLn =<< atomically (toString 100 t)
 9
 9
 3 9
 1 3 9
 1 2 3 4 5 6 8 9 10
 
 atomically $ sequence [ lookup i t | i <- [5..10] ]
 [Just "5",Just "6",Nothing,Just "8",Just "9",Just "10"]

 atomically $ update 8 "X" t
 atomically $ sequence [ lookup i t | i <- [5..10] ]
 [Just "5",Just "6",Nothing,Just "X",Just "9",Just "10"]

Data type and Construction

data TSkipList k a

newIO

Arguments

:: Float

Probability for choosing a new level

-> Int

Maximum number of levels

-> IO (TSkipList k a)

An empty skiplist that uses the standard random generator.

new

Arguments

:: Float

Probability for choosing a new level

-> Int

Maximum number of levels

-> STM (TSkipList k a)

An empty skiplist.

Operations

insert :: Ord k => k -> a -> TSkipList k a -> STM ()

lookup :: Ord k => k -> TSkipList k a -> STM (Maybe a)

update :: Ord k => k -> a -> TSkipList k a -> STM ()

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

delete :: Ord k => k -> TSkipList k a -> STM ()

Deletes an element. Does nothing if the element is not found.

geq :: Ord k => k -> TSkipList k a -> STM (Map k a)

Returns all elements greater or equal than the key. TODO: currently in O(n), should be made more efficient (like leq)

leq :: Ord k => k -> TSkipList k a -> STM (Map k a)

Returns all elements less or equal than the key.

filter :: Ord k => (k -> a -> Bool) -> TSkipList k a -> STM (Map k a)

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

Utilities

chooseLevel :: TSkipList k a -> STM 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 :: (Show k, Ord k) => k -> TSkipList k a -> STM String

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