Control.Concurrent.STM.Map

A contention-free STM hash map. "Contention-free" means that the map will never cause spurious conflicts. A transaction operating on the map will only ever have to retry if another transaction is operating on the same key at the same time.

Documentation

data Map k v

A map from keys k to values v.

Construction

empty :: STM (Map k v)

O(1). Construct an empty map.

Modification

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

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 -> STM ()

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

Note: This does not actually remove the key from the map. In fact, it might actually increase the map's memory consumption by putting the key into the map. To completely delete an entry, including its key, use unsafeDelete.

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

O(log n). This will completely remove a given key and its associated value from the map, if present. This is not an atomic operation, however. Use with caution!

Query

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

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

Note: This might increase the map's memory consumption by putting the key into the map. If that is not acceptable, use phantomLookup.

phantomLookup :: (Eq k, Hashable k) => k -> Map k v -> STM (Maybe v)

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

In contrast to lookup, this will never increase the map's memory consumption. However, it might allow phantom reads to occur. Consider the following situation:

f = atomically $ do v1 <- phantomLookup k m
                    v2 <- phantomLookup k m
                    return (v1 == v2)

Under certain circumstances f might actually return False, in particular if the first phantomLookup happens on an empty map and some other transaction inserts a value for k before the second call to phantomLookup.

member :: (Eq k, Hashable k) => k -> Map k v -> STM Bool

O(log n). Is the key a member of the map?

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.