stm-data-collection-0.1.0.0: Collection of STM-based Data Structures

Copyright(c) Alex Semin, 2015
LicenseBSD3
Maintaineralllex.semin@gmail.com
Stabilityexperimental
Portabilityportable
Safe HaskellNone
LanguageHaskell2010

Data.STM.PriorityQueue.Internal.PTRLLSLPQ

Description

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 fine-grained Linked List. In addition, RNG are distributed among capabilities which reduces contention.

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.

Synopsis

Documentation

data PTRLLSLPQ k v Source

Abbreviation stands for Per Thread Random Linked List (-based) Skip-List PQ

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

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