Data.NonBlocking.WaitFree.TreeCounter

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.

Documentation

data TreeCounter r

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

TreeCounter inside the IO Monad.

type TreeCounterSTM = TreeCounter TVar

TreeCounter inside the STM Monad.

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

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)

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

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

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