Control.Concurrent.STM.TSkipList.Internal

Data types and Construction

data TSkipList k a

A skip list data type.

Constructors

TSkipList

Fields

• maxLevel :: Int

  The maximal height of the skip list.

• probability :: Float

  Probability parameter.

• curLevel :: TVar Int

  The current max level.

• listHead :: ForwardPtrs k a

  Pointer to the first element in the highest level.

newIO :: IO (TSkipList k a)

Creates a skiplist. Default values for storing up to 2^16 elements.

newIO'

Arguments

:: Float

Probability for choosing a new level

-> Int

Maximum number of levels.

-> IO (TSkipList k a)

Creates a skiplist.

new :: STM (TSkipList k a)

Creates a skiplist. Default values for storing up to 2^16 elements.

new'

Arguments

:: Float

Probability for choosing a new level

-> Int

Maximum number of levels

-> STM (TSkipList k a)

Creates a skiplist.

data Traversal k a b

Traversal strategy.

Constructors

Traversal

Fields

• onLT :: Node k a -> Int -> STM b
• onGT :: Node k a -> Int -> STM b
• onEQ :: Node k a -> Int -> STM b
• onNil :: Node k a -> Int -> STM b
• onSuccSuccNil :: Maybe (Node k a -> Int -> STM b)

type ForwardPtrs k a = TArray Int (Node k a)

data Node k a

An entry of the skip list.

Constructors

Nil

Node

Fields

• key :: k
• contentTVar :: TVar a
• forwardPtrs :: ForwardPtrs k a

Operations

insert :: Ord k => k -> a -> TSkipList k a -> STM ()

Insertsupdates the value for a specific key. O(log n)/.

lookup :: Ord k => k -> TSkipList k a -> STM (Maybe a)

Searches for a given entry. O(log n).

update :: Ord k => k -> a -> TSkipList k a -> STM ()

Updates an element. Throws AssertionFailed if the element is not in the list. O(log n).

delete :: Ord k => k -> TSkipList k a -> STM ()

Deletes an element. Does nothing if the element is not found. O(log n).

filter :: Ord k => (k -> Bool) -> TSkipList k a -> STM (Map k a)

Returns all elements that satisfy the predicate on keys. O(n).

filterGT :: Ord k => k -> TSkipList k a -> STM (Map k a)

Returns all elements greater than the key. TODO: currently in O(n), should be made more efficient (like leq)

filterLT :: Ord k => k -> TSkipList k a -> STM (Map k a)

Returns all elements less than the key. Takes O(m) where m is the number of elements that have a smaller key.

filterElems :: Ord k => (k -> a -> Bool) -> TSkipList k a -> STM (Map k a)

Returns all elements that satisfy the predicate on keys and values. O(n).

minimum :: Ord k => TSkipList k a -> STM (k, a)

Returns the minimum entry. O(1).

maximum :: Ord k => TSkipList k a -> STM (k, a)

Returns the maximum entry. O(log n).

filterRange :: Ord k => (k, k) -> TSkipList k a -> STM [(k, a)]

Finds all elements within a specific key range (k1,k2). O(log n + k2 - k1).

Low-level Operations

traverseSL

Arguments

:: Ord k

=> k

search key

-> ForwardPtrs k a

forward pointers to the next node

-> Int

current level

-> Traversal k a b

traversal strategy

-> b

default value

-> STM b

lookupNode :: Ord k => k -> TSkipList k a -> STM (Maybe (Node k a))

insertNode :: Ord k => k -> Node k a -> TSkipList k a -> STM ()

Utilities

chooseLevel :: TSkipList k a -> Int

Returns a randomly chosen level. Used for inserting new elements. O(1). For performance reasons, this function uses unsafePerformIO to access the random number generator. (It would be possible to store the random number generator in a TVar and thus be able to access it safely from within the STM monad. This, however, might cause high contention among threads.)

toString :: (Show k, Ord k) => TSkipList k a -> STM String

Returns the skip list as a string.