License | BSD3 |
---|---|

Maintainer | Julian Sutherland (julian.sutherland10@imperial.ac.uk) |

Safe Haskell | None |

Language | Haskell98 |

A wait-free tree counter. Creates a binary tree of counters, with each leaf associated with a thread. Leaves can be split, creating a new leaf for the current thread and another that can be used by another thread. Each thread will act on different leaves, meaning the actions are wait-free. A read is performed on the counter by recursively traversing it and summing the value of the counters in the nodes and leaves of the tree.

- data TreeCounter r
- type TreeCounterIO = TreeCounter IORef
- type TreeCounterSTM = TreeCounter TVar
- newTreeCounter :: (MonadAtomicRef r m, Integral a) => a -> m (TreeCounter r)
- splitTreeCounter :: MonadAtomicRef r m => TreeCounter r -> m (TreeCounter r)
- incTreeCounter :: MonadAtomicRef r m => TreeCounter r -> m ()
- readTreeCounter :: (MonadAtomicRef r m, Num a) => TreeCounter r -> m a

# Documentation

data TreeCounter r Source

A wait-free concurrent Tree Counter, a binary tree of counters, with each leaf associated with a thread. Leaves can be split, creating a new leaf for the current thread and another that can be used by another thread. Increments are wait-free as long as each thread performs them on different instance of TreeCounter split from an initial instance using `splitTreeCounter`

, prone to ABA problem otherwise.

type TreeCounterIO = TreeCounter IORef Source

TreeCounter inside the IO Monad.

type TreeCounterSTM = TreeCounter TVar Source

TreeCounter inside the STM Monad.

newTreeCounter :: (MonadAtomicRef r m, Integral a) => a -> m (TreeCounter r) Source

Creates a new instance of the `TreeCounter`

data type, instanciated to the value of the input, with type in the `Integral`

class.

splitTreeCounter :: MonadAtomicRef r m => TreeCounter r -> m (TreeCounter r) Source

Splits a `TreeCounter`

instance, updating it to a new leaf and creating a new one, allowing another thread to increment the counter in a wait-free manner.

incTreeCounter :: MonadAtomicRef r m => TreeCounter r -> m () Source

Increments the `TreeCounter`

in an atomic manner as long as this thread is the only thread incrementing the counter from this instance `TreeCounter`

readTreeCounter :: (MonadAtomicRef r m, Num a) => TreeCounter r -> m a Source

Reads the total value of the binary tree of counters associated with this instance of `TreeCounter`

.