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 dictionary operations (similar to Data.Map). 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 ()

Inserts/updates the value for a specific key.

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 -> Int

Returns a randomly chosen level. Is used for inserting new elements. For performance reasons, this function uses unsafePerformIO to access the random number generator. (It would be possible to store the random number generator in a TVar and thus be able to access it safely from within the STM monad. This, however, might cause high contention among threads.

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.