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 Bool

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. Returns True if the value was inserted, False if it was replaced.

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

O(log n). Remove the given key and its associated value from the map, if present. Returns True if the value was deleted, False otherwise.

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

O(log n). Associate the given value with the given key. If the key is already present in the map, don't change the value. Returns True if the value was inserted, False otherwise.

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.