-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Transactional variables and data structures with IO hooks
--
-- This package provides STM data structures with IO hooks. The basic
-- building blocks are instances of class TBox. Such an instance
-- is an STM variable that might contain a value of some type a.
-- In contrast to a plain 'TVar (Maybe a)', a TBox has IO hooks
-- that are executed transparently on writes and reads. The IO hooks of
-- the AdvSTM monad extend the atomicity of STM transactions to
-- the on-commit IO actions, which makes it particularly suitable for
-- implementing a persistent and thread-safe storage.
--
-- See module Control.Concurrent.TFile for a (simple) instance of a
-- TBox that serializes its content to a file via
-- Data.Binary.
--
-- New in this release is the implementation of a skip list in module
-- Control.Concurrent.TBox.TSkipList. A skip list is a probabilistic data
-- structure that provides expected run time of O(log n) for
-- dictionary operations (insert, lookup, filter, delete, update) similar
-- to a balanced tree. The main advantage of a skip list is that it does
-- not need rebalancing, which could cause lots of contention among
-- transactions. The TFile skip list instance tries to reconstruct
-- its content from the TFile-directory. See module
-- Control.Concurrent.TFile.TSkipList for a usage example.
--
-- Feedback is highly appreciated!
@package tbox
@version 0.1.0
-- | The type class TBox.
module Control.Concurrent.TBox.Internal.Class
-- | An instance of TBox is a (Adv)STM variable that might contain a
-- value of some type a. In contrast to a plain 'TVar (Maybe
-- a)', a TBox has IO hooks that are executed transparently on
-- writes and reads, which makes it particularly suitable for
-- implementing a persistent and thread-safe storage. The type variable
-- k can be used to provide additional storage information,
-- e.g., a filepath.
--
-- Important: Note that the read/write functions of this type
-- class, i.e., readIO, readSTM, writeIO,
-- writeSTM, clearIO, clearSTM should only be
-- used to derive new instances and do not serve to modify the state of a
-- TBox. The interface defined in module TBox.Operations
-- provides operations on TBoxs that guarantee consistency.
--
-- See the module Control.Concurrent.TFile for a sample
-- instance.
class TBox t k a
new :: TBox t k a => k -> a -> AdvSTM (t k a)
newIO :: TBox t k a => k -> a -> IO (t k a)
newEmpty :: TBox t k a => k -> AdvSTM (t k a)
newEmptyIO :: TBox t k a => k -> IO (t k a)
writeSTM :: TBox t k a => t k a -> a -> AdvSTM ()
writeIO :: TBox t k a => t k a -> a -> IO ()
readSTM :: TBox t k a => t k a -> AdvSTM (Maybe a)
readIO :: TBox t k a => t k a -> IO (Maybe a)
clearSTM :: TBox t k a => t k a -> AdvSTM ()
clearIO :: TBox t k a => t k a -> IO ()
isDirty :: TBox t k a => t k a -> AdvSTM Bool
setDirty :: TBox t k a => t k a -> Bool -> AdvSTM ()
-- | Operations on instances of TBox.
module Control.Concurrent.TBox.Internal.Operations
-- | Deletes the content.
clear :: TBox t k a => t k a -> AdvSTM ()
-- | Writes the new content.
write :: TBox t k a => t k a -> a -> AdvSTM ()
-- | If the TBox is dirty, this retries the transaction and rereads the
-- content using readIO in a separate thread. Otherwise it simply
-- returns the result of readSTM.
--
-- Note: Depending on the instance implementation, careless use of
-- setDirty and read in the same transaction might lead to
-- nonterminating retry loops.
read :: TBox t k a => t k a -> AdvSTM (Maybe a)
-- | Returns True iff the TBox is empty.
isEmpty :: TBox t k a => t k a -> AdvSTM Bool
-- | Returns True iff the TBox is empty and not dirty.
isEmptyNotDirty :: TBox t k a => t k a -> AdvSTM Bool
-- | An abstract interface for transactional variables with IO hooks.
module Control.Concurrent.TBox
-- | An instance of TBox is a (Adv)STM variable that might contain a
-- value of some type a. In contrast to a plain 'TVar (Maybe
-- a)', a TBox has IO hooks that are executed transparently on
-- writes and reads, which makes it particularly suitable for
-- implementing a persistent and thread-safe storage. The type variable
-- k can be used to provide additional storage information,
-- e.g., a filepath.
--
-- Important: Note that the read/write functions of this type
-- class, i.e., readIO, readSTM, writeIO,
-- writeSTM, clearIO, clearSTM should only be
-- used to derive new instances and do not serve to modify the state of a
-- TBox. The interface defined in module TBox.Operations
-- provides operations on TBoxs that guarantee consistency.
--
-- See the module Control.Concurrent.TFile for a sample
-- instance.
class TBox t k a
new :: TBox t k a => k -> a -> AdvSTM (t k a)
newIO :: TBox t k a => k -> a -> IO (t k a)
newEmpty :: TBox t k a => k -> AdvSTM (t k a)
newEmptyIO :: TBox t k a => k -> IO (t k a)
writeSTM :: TBox t k a => t k a -> a -> AdvSTM ()
writeIO :: TBox t k a => t k a -> a -> IO ()
readSTM :: TBox t k a => t k a -> AdvSTM (Maybe a)
readIO :: TBox t k a => t k a -> IO (Maybe a)
clearSTM :: TBox t k a => t k a -> AdvSTM ()
clearIO :: TBox t k a => t k a -> IO ()
isDirty :: TBox t k a => t k a -> AdvSTM Bool
setDirty :: TBox t k a => t k a -> Bool -> AdvSTM ()
-- | If the TBox is dirty, this retries the transaction and rereads the
-- content using readIO in a separate thread. Otherwise it simply
-- returns the result of readSTM.
--
-- Note: Depending on the instance implementation, careless use of
-- setDirty and read in the same transaction might lead to
-- nonterminating retry loops.
read :: TBox t k a => t k a -> AdvSTM (Maybe a)
-- | Writes the new content.
write :: TBox t k a => t k a -> a -> AdvSTM ()
-- | Deletes the content.
clear :: TBox t k a => t k a -> AdvSTM ()
-- | Returns True iff the TBox is empty.
isEmpty :: TBox t k a => t k a -> AdvSTM Bool
-- | Returns True iff the TBox is empty and not dirty.
isEmptyNotDirty :: TBox t k a => t k a -> AdvSTM Bool
-- | Provides an implementation of a skip list in the AdvSTM monad.
-- 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 rebalancing, which makes it suitable for concurrent programming.
-- See: William Pugh. Skip Lists: A Probabilistic Alternative to
-- Balanced Trees.
--
-- The elements of the skip list are stored in a TBox. When an
-- element of the skip list is modified, the operation is relegated to
-- the corresponding TBox.
--
-- For a concrete instance see module
-- Control.Concurrent.TFile.TSkipList
module Control.Concurrent.TBox.TSkipList
data TSkipList t k a
-- | An empty skiplist.
newIO :: TBox t k a => Float -> Int -> IO (TSkipList t 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)
-- | Updates an element. Throws AssertionFailed if the element is
-- not in the list.
update :: (Ord k, TBox t k a) => k -> a -> TSkipList t k a -> AdvSTM ()
delete :: (Ord k, TBox t k a) => k -> TSkipList t k a -> AdvSTM ()
-- | Returns all elements that are greater than the key. TODO: currently in
-- O(n), can be made more efficient (like leq)
geq :: (Ord k, TBox t k a) => k -> TSkipList t k a -> AdvSTM (Map k a)
-- | Returns all elements that are smaller than the key.
leq :: (Ord k, TBox t k a) => k -> TSkipList t k a -> AdvSTM (Map k a)
-- | Returns the element with the least key, if it exists. O(1).
min :: (Ord k, TBox t k a) => TSkipList t k a -> AdvSTM (Maybe a)
-- | Returns all elements that satisfy the predicate. O(n).
filter :: (Ord k, TBox t k a) => (k -> a -> Bool) -> TSkipList t k a -> AdvSTM (Map k a)
insertNode :: (Ord k, TBox t k a) => k -> Node t k a -> TSkipList t k a -> AdvSTM ()
lookupNode :: (Ord k, TBox t k a) => k -> TSkipList t k a -> AdvSTM (Maybe (Node t k a))
-- | Reads the TBox of the node. If the TBox is empty, the
-- node is removed from the skip list. This is necessary when
-- TBoxs are shared between different data structures.
readAndValidate :: (Ord k, TBox t k a) => TSkipList t k a -> Node t k a -> AdvSTM (Maybe a)
newNode :: TBox t k a => k -> t k a -> Int -> AdvSTM (Node t k a)
contentTBox :: Node t k a -> t k a
key :: Node t k a -> k
-- | Returns a randomly chosen level. Is used for inserting new elements.
-- Note that this function uses unsafeIOToAdvSTM to access the
-- random number generator.
chooseLevel :: TSkipList t k a -> AdvSTM Int
-- | Debug helper. Returns the skip list as a string. All elements smaller
-- than the given key are written to the string.
toString :: (Ord k, Show k, TBox t k a) => k -> TSkipList t k a -> AdvSTM String
-- | A transactional variable that writes its content to a file when
-- updated. Due to the atomicity guarantees of the AdvSTM monad,
-- an update to a TFile is only committed when the file operation
-- succeeds.
--
-- This module should be imported qualified.
module Control.Concurrent.TFile
-- | A transactional variable that writes its content to a file on each
-- update. The file is created in directory "./_TFile/".
--
--
-- - The onCommit hook of the AdvSTM monad guarantee that
-- the updated memory content of the TFile is only visible to other
-- threads iff the file has been written successfully.
-- - If the TFile is "dirty", the content is (re)read from the
-- file on the next read.
--
data TFile k a
-- | Takes a key and an initial value
new :: TBox t k a => k -> a -> AdvSTM (t k a)
-- | Takes a key and an initial value. Has a default implementation.
newIO :: TBox t k a => k -> a -> IO (t k a)
-- | Tries to construct a TFile from a given filepath. Reads the
-- content of the file into memory.
newFromFileIO :: (Read k, TBox TFile k a) => FilePath -> IO (TFile k a, k)
-- | Takes a key and returns an empty t
newEmpty :: TBox t k a => k -> AdvSTM (t k a)
-- | Takes a key and returns an empty t. Has a default
-- implementation.
newEmptyIO :: TBox t k a => k -> IO (t k a)
-- | Tries to construct a TFile from a given filepath. Note that the
-- content of the file is read into memory only on demand, i.e., when
-- executing TBox.read. Throws AssertionFailed if the
-- filename could not be parsed.
newEmptyFromFileIO :: (Read k, TBox TFile k a) => FilePath -> IO (TFile k a, k)
-- | If the TBox is dirty, this retries the transaction and rereads the
-- content using readIO in a separate thread. Otherwise it simply
-- returns the result of readSTM.
--
-- Note: Depending on the instance implementation, careless use of
-- setDirty and read in the same transaction might lead to
-- nonterminating retry loops.
read :: TBox t k a => t k a -> AdvSTM (Maybe a)
-- | Writes the new content.
write :: TBox t k a => t k a -> a -> AdvSTM ()
-- | Deletes the content.
clear :: TBox t k a => t k a -> AdvSTM ()
-- | Returns True iff the TBox is empty.
isEmpty :: TBox t k a => t k a -> AdvSTM Bool
-- | Currently set to "./_TFile" TODO: provide interface for updating base
-- directory within a transaction(?)
basedir :: FilePath
instance Typeable2 TFile
instance (Binary a, Show k) => TBox TFile k a
-- | 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"]
--
module Control.Concurrent.TFile.TSkipList
type TSkipList k a = TSkipList TFile k a
-- | Returns a new (reconstructed!) TSkipList. Automatically inserts
-- all TFile entries found in "basedir/". Note that the
-- TFiles are initially empty, i.e., the file content will only be
-- read into memory on demand.
newEmptyIO :: (Binary a, Show k, Ord k, Read k, TBox TFile k a) => Float -> Int -> IO (TSkipList k a)
-- | Returns a new (reconstructed!) TSkipList. Automatically inserts
-- all TFile entries found in "basedir/". In contrast to
-- newEmptyIO, the TFiles initially contain the file
-- content. Use this if you want to have all data in memory from the
-- start.
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)
-- | Updates an element. Throws AssertionFailed if the element is
-- not in the list.
update :: (Ord k, TBox t k a) => k -> a -> TSkipList t k a -> AdvSTM ()
-- | Returns all elements that are smaller than the key.
leq :: (Ord k, TBox t k a) => k -> TSkipList t k a -> AdvSTM (Map k a)
-- | Returns all elements that are greater than the key. TODO: currently in
-- O(n), can be made more efficient (like leq)
geq :: (Ord k, TBox t k a) => k -> TSkipList t k a -> AdvSTM (Map k a)
-- | Returns the element with the least key, if it exists. O(1).
min :: (Ord k, TBox t k a) => TSkipList t k a -> AdvSTM (Maybe a)
-- | Returns all elements that satisfy the predicate. O(n).
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 ()
-- | Returns a randomly chosen level. Is used for inserting new elements.
-- Note that this function uses unsafeIOToAdvSTM to access the
-- random number generator.
chooseLevel :: TSkipList t k a -> AdvSTM Int
-- | Debug helper. Returns the skip list as a string. All elements smaller
-- than the given key are written to the string.
toString :: (Ord k, Show k, TBox t k a) => k -> TSkipList t k a -> AdvSTM String