Portability | non-portable (requires STM) |
---|---|

Stability | experimental |

Maintainer | Peter Robinson <thaldyron@gmail.com> |

Safe Haskell | Safe-Infered |

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 TSkipList k a
- newIO :: Float -> Int -> IO (TSkipList k a)
- new :: Float -> Int -> STM (TSkipList k a)
- 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 ()
- delete :: Ord k => k -> TSkipList k a -> STM ()
- geq :: Ord k => k -> TSkipList k a -> STM (Map k a)
- leq :: Ord k => k -> TSkipList k a -> STM (Map k a)
- filter :: Ord k => (k -> a -> Bool) -> TSkipList k a -> STM (Map k a)
- chooseLevel :: TSkipList k a -> STM Int
- toString :: (Show k, Ord k) => k -> TSkipList k a -> STM String

# Data type and Construction

An empty skiplist that uses the standard random generator.

An empty skiplist.

# Operations

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

Inserts/updates the value for a specific key.

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

Updates an element. Throws `AssertionFailed`

if the element is not in the
list.

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

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

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

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)Source

Returns all elements less or equal than the key.

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

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

# Utilities

chooseLevel :: TSkipList k a -> STM IntSource

Returns a randomly chosen level. Is used for inserting new elements.
For performance reasons, this function uses `unsafeIOToSTM`

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.