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 -> 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 -> IntSource
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.