Control.Concurrent.Map

A non-blocking concurrent map from hashable keys to values.

The implementation is based on lock-free concurrent hash tries (aka Ctries) as described by:

• Aleksander Prokopec, Phil Bagwell, Martin Odersky, "Cache-Aware Lock-Free Concurent Hash Tries"
• Aleksander Prokopec, Nathan G. Bronson, Phil Bagwell, Martin Odersky "/Concurrent Tries with Efficient Non-Blocking Snapshots/"

Operations have a worst-case complexity of O(log n), with a base equal to the size of the native Word.

Documentation

data Map k v

A map from keys k to values v.

Construction

empty :: IO (Map k v)

O(1). Construct an empty map.

Modification

insert :: (Eq k, Hashable k) => k -> v -> Map k v -> IO ()

O(log n). Associate the given value with the given key. If the key is already present in the map, the old value is replaced.

delete :: (Eq k, Hashable k) => k -> Map k v -> IO ()

O(log n). Remove the given key and its associated value from the map, if present.

Query

lookup :: (Eq k, Hashable k) => k -> Map k v -> IO (Maybe v)

O(log n). Return the value associated with the given key, or Nothing.

Lists

fromList :: (Eq k, Hashable k) => [(k, v)] -> IO (Map k v)

O(n * log n). Construct a map from a list of key/value pairs.

unsafeToList :: Map k v -> IO [(k, v)]

O(n). Unsafely convert the map to a list of key/value pairs.

WARNING: unsafeToList makes no atomicity guarantees. Concurrent changes to the map will lead to inconsistent results.