-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Contention-free STM hash 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.
--   
--   This is an implementation of the <i>transactional trie</i>, which is
--   basically a <i>lock-free concurrent hash trie</i> lifted into STM. For
--   a detailed discussion, including an evaluation of its performance, see
--   Chapter 4 of <a>my master's thesis</a>.
@package ttrie
@version 0.1.2.1


-- | 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.
module Control.Concurrent.STM.Map

-- | A map from keys <tt>k</tt> to values <tt>v</tt>.
data Map k v

-- | <i>O(1)</i>. Construct an empty map.
empty :: STM (Map k v)

-- | <i>O(log n)</i>. Associate the given value with the given key. If the
--   key is already present in the map, the old value is replaced.
insert :: (Eq k, Hashable k) => k -> v -> Map k v -> STM ()

-- | <i>O(log n)</i>. Remove the value associated with a given key from the
--   map, if present.
--   
--   <b>Note</b>: 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 <a>unsafeDelete</a>.
delete :: (Eq k, Hashable k) => k -> Map k v -> STM ()

-- | <i>O(log n)</i>. This will completely remove a given key and its
--   associated value from the map, if present. This is not an atomic
--   operation, however. <b>Use with caution!</b>
unsafeDelete :: (Eq k, Hashable k) => k -> Map k v -> IO ()

-- | <i>O(log n)</i>. Return the value associated with the given key, or
--   <a>Nothing</a>.
--   
--   <b>Note</b>: This might increase the map's memory consumption by
--   putting the key into the map. If that is not acceptable, use
--   <a>phantomLookup</a>.
lookup :: (Eq k, Hashable k) => k -> Map k v -> STM (Maybe v)

-- | <i>O(log n)</i>. Return the value associated with the given key, or
--   <a>Nothing</a>.
--   
--   In contrast to <a>lookup</a>, this will never increase the map's
--   memory consumption. However, it might allow <i>phantom reads</i> to
--   occur. Consider the following situation:
--   
--   <pre>
--   f = atomically $ do v1 &lt;- phantomLookup k m
--                       v2 &lt;- phantomLookup k m
--                       return (v1 == v2)
--   </pre>
--   
--   Under certain circumstances <tt>f</tt> might actually return
--   <tt>False</tt>, in particular if the first <tt>phantomLookup</tt>
--   happens on an empty map and some other transaction inserts a value for
--   <tt>k</tt> before the second call to <tt>phantomLookup</tt>.
phantomLookup :: (Eq k, Hashable k) => k -> Map k v -> STM (Maybe v)

-- | <i>O(log n)</i>. Is the key a member of the map?
member :: (Eq k, Hashable k) => k -> Map k v -> STM Bool

-- | <i>O(n * log n)</i>. Construct a map from a list of key/value pairs.
fromList :: (Eq k, Hashable k) => [(k, v)] -> IO (Map k v)

-- | <i>O(n)</i>. Unsafely convert the map to a list of key/value pairs.
--   
--   <b>Warning</b>: <a>unsafeToList</a> makes no atomicity guarantees.
--   Concurrent changes to the map will lead to inconsistent results.
unsafeToList :: Map k v -> IO [(k, v)]
