Safe Haskell | Trustworthy |
---|---|

Language | Haskell98 |

This module provides finite maps that only grow. It is based on a
*concurrent skip list* implementation of maps.

This module is usually a more efficient alternative to
`PureMap`

, and provides almost the same interface. However,
it's always good to test multiple data structures if you have a
performance-critical use case.

- data IMap k s v
- newEmptyMap :: Ord k => Par d s (IMap k s v)
- newMap :: Ord k => Map k v -> Par d s (IMap k s v)
- newFromList :: (Ord k, Eq v) => [(k, v)] -> Par d s (IMap k s v)
- insert :: (Ord k, Eq v) => k -> v -> IMap k s v -> Par d s ()
- getKey :: Ord k => k -> IMap k s v -> Par d s v
- waitSize :: Int -> IMap k s v -> Par d s ()
- waitValue :: (Ord k, Eq v) => v -> IMap k s v -> Par d s ()
- modify :: forall f a b d s key. (Ord key, Show key, Ord a) => IMap key s (f s a) -> key -> Par d s (f s a) -> (f s a -> Par d s b) -> Par d s b
- freezeMap :: Ord k => IMap k s v -> QPar s (IMap k Frzn v)
- traverseFrzn_ :: Ord k => (k -> a -> Par d s ()) -> IMap k Frzn a -> Par d s ()
- forEach :: IMap k s v -> (k -> v -> Par d s ()) -> Par d s ()
- forEachHP :: Maybe HandlerPool -> IMap k s v -> (k -> v -> Par d s ()) -> Par d s ()
- withCallbacksThenFreeze :: forall k v b s. Eq b => IMap k s v -> (k -> v -> QPar s ()) -> QPar s b -> QPar s b
- copy :: (Ord k, Eq v) => IMap k s v -> Par d s (IMap k s v)
- traverseMap :: (Ord k, Eq b) => (k -> a -> Par d s b) -> IMap k s a -> Par d s (IMap k s b)
- traverseMap_ :: (Ord k, Eq b) => (k -> a -> Par d s b) -> IMap k s a -> IMap k s b -> Par d s ()
- traverseMapHP :: (Ord k, Eq b) => Maybe HandlerPool -> (k -> a -> Par d s b) -> IMap k s a -> Par d s (IMap k s b)
- traverseMapHP_ :: (Ord k, Eq b) => Maybe HandlerPool -> (k -> a -> Par d s b) -> IMap k s a -> IMap k s b -> Par d s ()
- unionHP :: (Ord k, Eq a) => Maybe HandlerPool -> IMap k s a -> IMap k s a -> Par d s (IMap k s a)
- levelCounts :: IMap k s a -> IO [Int]

# The type and its basic operations

The map datatype itself. Like all other LVars, it has an `s`

parameter (think
`STRef`

) in addition to the `a`

parameter that describes the type of elements
in the set.

Performance note: this data structure reduces contention between parallel
computations inserting into the map, but all *blocking* computations are not as
scalable. All continuations waiting for not-yet-present elements will currently
share a single queue [2013.09.26].

LVarData1 (IMap k) | An |

OrderedLVarData1 (IMap k) | The |

Foldable (IMap k Trvrsbl) | |

Foldable (IMap k Frzn) | |

Eq (IMap k s v) | Equality is physical equality, as with |

(Show k, Show a) => Show (IMap k Trvrsbl a) | For convenience only; the user could define this. |

(Show k, Show a) => Show (IMap k Frzn a) | |

DeepFrz a => DeepFrz (IMap k s a) | |

type FrzType (IMap k s a) = IMap k Frzn (FrzType a) |

newEmptyMap :: Ord k => Par d s (IMap k s v) Source

Create a fresh map with nothing in it.

newMap :: Ord k => Map k v -> Par d s (IMap k s v) Source

Create a new map populated with initial elements.

newFromList :: (Ord k, Eq v) => [(k, v)] -> Par d s (IMap k s v) Source

Create a new map drawing initial elements from an existing list.

insert :: (Ord k, Eq v) => k -> v -> IMap k s v -> Par d s () Source

Put a single entry into the map. (WHNF) Strict in the key and value.

getKey :: Ord k => k -> IMap k s v -> Par d s v Source

Wait for the map to contain a specified key, and return the associated value.

waitValue :: (Ord k, Eq v) => v -> IMap k s v -> Par d s () Source

Wait until the map contains a certain value (on any key).

# Quasi-deterministic operations

freezeMap :: Ord k => IMap k s v -> QPar s (IMap k Frzn v) Source

Get the exact contents of the map. As with any
quasi-deterministic operation, using `freezeMap`

may cause your
program to exhibit a limited form of nondeterminism: it will never
return the wrong answer, but it may include synchronization bugs
that can (nondeterministically) cause exceptions.

This is an *O(1)* operation that doesn't copy the in-memory representation of the
IMap.

traverseFrzn_ :: Ord k => (k -> a -> Par d s ()) -> IMap k Frzn a -> Par d s () Source

Traverse a frozen map for side effect. This is useful (in comparison with more generic operations) because the function passed in may see the key as well as the value.

# Iteration and callbacks

forEach :: IMap k s v -> (k -> v -> Par d s ()) -> Par d s () Source

Add an (asynchronous) callback that listens for all new new key/value pairs added to the map.

:: Maybe HandlerPool | optional pool to enroll in |

-> IMap k s v | Map to listen to |

-> (k -> v -> Par d s ()) | callback |

-> Par d s () |

Add an (asynchronous) callback that listens for all new key/value pairs added to the map, optionally tied to a handler pool.

withCallbacksThenFreeze :: forall k v b s. Eq b => IMap k s v -> (k -> v -> QPar s ()) -> QPar s b -> QPar s b Source

Register a per-element callback, then run an action in this context, and freeze when all (recursive) invocations of the callback are complete. Returns the final value of the provided action.

# Higher-level derived operations

copy :: (Ord k, Eq v) => IMap k s v -> Par d s (IMap k s v) Source

Return a fresh map which will contain strictly more elements than the input. That is, things put in the former go in the latter, but not vice versa.

traverseMap :: (Ord k, Eq b) => (k -> a -> Par d s b) -> IMap k s a -> Par d s (IMap k s b) Source

Establish a monotonic map between the input and output map Produce a new result based on each element, while leaving the keys the same.

traverseMap_ :: (Ord k, Eq b) => (k -> a -> Par d s b) -> IMap k s a -> IMap k s b -> Par d s () Source

An imperative-style, in-place version of `traverseMap`

that takes the output map
as an argument.

# Alternate versions of derived ops that expose `HandlerPool`

s they create

traverseMapHP :: (Ord k, Eq b) => Maybe HandlerPool -> (k -> a -> Par d s b) -> IMap k s a -> Par d s (IMap k s b) Source

Variant of `traverseMap`

that optionally ties the handlers to a pool.

traverseMapHP_ :: (Ord k, Eq b) => Maybe HandlerPool -> (k -> a -> Par d s b) -> IMap k s a -> IMap k s b -> Par d s () Source

Variant of `traverseMap_`

that optionally ties the handlers to a pool.

unionHP :: (Ord k, Eq a) => Maybe HandlerPool -> IMap k s a -> IMap k s a -> Par d s (IMap k s a) Source

Return a new map which will (ultimately) contain everything in either input map. Conflicting entries will result in a multiple put exception. Optionally ties the handlers to a pool.

# Debugging Helpers

levelCounts :: IMap k s a -> IO [Int] Source