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

Stability | experimental |

Maintainer | Peter Robinson <robinson@ecs.tuwien.ac.at> |

Instantiates the STM skiplist implementation of
Control.Concurrent.TBox.TSkipList with the `TFile`

backend.

This module should be imported qualified.

Example:

t <- newIO 0.5 5 :: IO (TSkipList Int String) atomically $ sequence_ [ insert i (show i) t | i <- [1..10] ] putStr =<< 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 putStr =<< 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"]

- type TSkipList k a = TSkipList TFile k a
- newEmptyIO :: (Binary a, Show k, Ord k, Read k, TBox TFile k a) => Float -> Int -> IO (TSkipList k a)
- newIO :: (Binary a, Show k, Ord k, Read k, TBox TFile k a) => Float -> Int -> IO (TSkipList k a)
- 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 ()
- leq :: (Ord k, TBox t k a) => k -> TSkipList t k a -> AdvSTM (Map k a)
- geq :: (Ord k, TBox t k a) => k -> TSkipList t k a -> AdvSTM (Map k a)
- min :: (Ord k, TBox t k a) => TSkipList t k a -> AdvSTM (Maybe a)
- filter :: (Ord k, TBox t k a) => (k -> a -> Bool) -> TSkipList t k a -> AdvSTM (Map k a)
- delete :: (Ord k, TBox t k a) => k -> TSkipList t k a -> AdvSTM ()
- chooseLevel :: TSkipList t k a -> AdvSTM Int
- toString :: (Ord k, Show k, TBox t k a) => k -> TSkipList t k a -> AdvSTM String

# Data type

newEmptyIO :: (Binary a, Show k, Ord k, Read k, TBox TFile k a) => Float -> Int -> IO (TSkipList k a)Source

newIO :: (Binary a, Show k, Ord k, Read k, TBox TFile k a) => Float -> Int -> IO (TSkipList k a)Source

Returns a new (reconstructed!) `TSkipList`

. Automatically inserts all `TFile`

entries found
in "basedir/".
In contrast to `newEmptyIO`

, the `TFile`

s initially contain the file content.
Use this if you want to have all data in memory from the start.

# Operations

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

Updates an element. Throws `AssertionFailed`

if the element is not in the
list.

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

Returns all elements that are smaller than the key.

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

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

)

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

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

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

# Utilities

chooseLevel :: TSkipList t k a -> AdvSTM IntSource

Returns a randomly chosen level. Is used for inserting new elements.
Note that this function uses `unsafeIOToAdvSTM`

to access the random
number generator.