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