Data.STM.PriorityQueue.Internal.PTSTASLPQ

An implementation of Class based on skip-list.

Expected time complexity of deletion is O(1), while insertion still normally has logarithmic complexity.

The skip-list's nodes are implemented via TArray. In addition, unboxed RNG seeds are distributed among capabilities which reduces contention and also accelerates internal random-number generation.

Default maximum height of skip-list node is 16. Use explicit constructor in case the height needs to be changed.

Note: number of capabilities is not supposed to be changed during execution.

Documentation

data PTSTASLPQ k v

Abbreviation stands for Per Thread Seed TArray Skip-List Priority Queue

Instances

PriorityQueue PTSTASLPQ

new' :: Ord k => Int -> STM (PTSTASLPQ k v)

Parameterizing constructor which determines maximum height of skip-list node.