(std stm map)

Reference

Overview

Transactional hash map (TMap) supporting fine-grained concurrent updates and CML retry.

(import (std stm))
(import (std stm map))

(def stock (make-tmap))
(def orders (make-tmap))

(atomically (fun (tx) (tmap-set! tx stock "apples" 10)))

;; Deduct stock for order 17, or retry until sufficient inventory exists:
(atomically
 (fun (tx)
   (let ((n (tmap-ref-or tx stock "apples" 0)))
     (if (< n 3)
         (tx-retry tx)
         (begin
           (tmap-set! tx stock "apples" (- n 3))
           (tmap-set! tx orders 17 "3 apples"))))))

(TMap K V) is a concurrent hash map designed for software transactional memory. Key type K must implement Eq (providing = and eq-hash). All operations take a Tx transaction log parameter and execute within transactions via atomically or atomically-evt.

Naming conventions. Operations mirror the prelude’s Map API using the tmap- prefix: tmap-try-ref, tmap-ref-or, tmap-set!, tmap-remove!, and tmap-update!.

Conditional retry. When a required entry is absent, transactions can call tx-retry to suspend until the corresponding hash branch is updated.

Fine-grained concurrency. Implemented as a hash trie where each branch node is a separate transactional Loc. Lookups and updates access only the nodes along the key’s hash path. Transactions modifying distinct keys rarely conflict. Map size is tracked using a striped TCounter to avoid bottlenecking concurrent insertions on a shared count (inspired by Haskell’s stm-containers).

Performance characteristics. Lookups, insertions, and removals run in O(log32 n) time. Whole-map operations (tmap-fold, tmap->list) read all branch locations, conflicting with any concurrent modification.

See also: TMap, tmap-set!, tmap-try-ref, tmap-update!

Reference

Types

Functions

Types

TMap

record ↑ Types

Transactional hash map mapping %k to %v.

%k
The key type (must implement Eq).
%v
The value type.

See also: make-tmap

TMapSlot

union ↑ Types

Internal slot node type for TMap.

%k
The key type.
%v
The value type.

TMapBranch

record ↑ Types

Internal branch node type for TMap.

%k
The key type.
%v
The value type.

TMapChange

union ↑ Types

Internal change descriptor type for TMap.

%k
The key type.
%v
The value type.

Functions

make-tmap

function ↑ Functions

(: make-tmap (-> (TMap %k %v)))
(make-tmap)

Creates an empty transactional hash map.

returns
A new empty TMap.

tmap-try-ref

function ↑ Functions

(: tmap-try-ref (-> Tx (TMap %k %v) %k (Option %v)))
(tmap-try-ref tx m k)

Returns (Some value) for key k within a transaction, or None if absent.

tx
The transaction log context.
m
The map.
k
The key to look up.
returns
(Some value) if k is present, otherwise None.

tmap-ref

function ↑ Functions

(: tmap-ref (-> Tx (TMap %k %v) %k %v))
(tmap-ref tx m k)

Returns the value for key k within a transaction, raising if missing.

tx
The transaction log context.
m
The map.
k
The key to look up.
returns
The value associated with k.
raises System.Collections.Generic.KeyNotFoundException
When k is not in the map.

tmap-ref-or

function ↑ Functions

(: tmap-ref-or (-> Tx (TMap %k %v) %k %v %v))
(tmap-ref-or tx m k default)

Returns the value for key k within a transaction, or a fallback default.

tx
The transaction log context.
m
The map.
k
The key to look up.
default
Fallback value returned if k is absent.
returns
The value associated with k, or default.

tmap-contains?

function ↑ Functions

(: tmap-contains? (-> Tx (TMap %k %v) %k bool))
(tmap-contains? tx m k)

Tests if key k exists in the map within a transaction.

tx
The transaction log context.
m
The map.
k
The key to locate.
returns
#t if k is present, otherwise #f.

tmap-set!

function ↑ Functions

(: tmap-set! (-> Tx (TMap %k %v) %k %v void))
(tmap-set! tx m k v)

Associates key k with value v within a transaction.

tx
The transaction log context.
m
The map.
k
The key.
v
The value to associate with k.

tmap-remove!

function ↑ Functions

(: tmap-remove! (-> Tx (TMap %k %v) %k void))
(tmap-remove! tx m k)

Removes key k from the map within a transaction.

tx
The transaction log context.
m
The map.
k
The key to remove.

tmap-update!

function ↑ Functions

(: tmap-update! (-> Tx (TMap %k %v) %k (-> (Option %v) (Option %v)) void))
(tmap-update! tx m k f)

Updates or removes key k via transformation function f within a transaction.

tx
The transaction log context.
m
The map.
k
The key.
f
Function receiving (Some old-value) or None, returning (Some new-value) to update or None to remove.
;; Increment a counter entry:
(tmap-update! tx counts word
              (fun (old) (match old
                           ((Some n) (Some (+ n 1)))
                           (None (Some 1)))))

Performs lookup and mutation in a single trie descent.

tmap-length

function ↑ Functions

(: tmap-length (-> Tx (TMap %k %v) int))
(tmap-length tx m)

Returns the number of keys in the map within a transaction.

tx
The transaction log context.
m
The map.
returns
The count of key-value pairs.

Reads the underlying striped counter, conflicting with transactions that add or remove entries.

tmap-empty?

function ↑ Functions

(: tmap-empty? (-> Tx (TMap %k %v) bool))
(tmap-empty? tx m)

Tests if the map contains no entries within a transaction.

tx
The transaction log context.
m
The map.
returns
#t if empty, otherwise #f.

Inspects only the root trie branch without scanning all stripes.

tmap-fold

function ↑ Functions

(: tmap-fold (-> Tx (-> %k %v %s %s) %s (TMap %k %v) %s))
(tmap-fold tx f init m)

Folds over all key-value entries in the map within a transaction.

tx
The transaction log context.
f
Accumulator function called as (f key value acc).
init
Initial accumulator value.
m
The map.
returns
The final accumulator value.

Traverses all trie branches in hash order, conflicting with any concurrent modification to the map.

tmap->list

function ↑ Functions

(: tmap->list (-> Tx (TMap %k %v) (List (Tuple %k %v))))
(tmap->list tx m)

Converts all entries in the map to a list of (Tuple key value) pairs within a transaction.

tx
The transaction log context.
m
The map.
returns
A list of (Tuple key value) pairs in arbitrary hash order.

Traverses all trie branches, conflicting with any concurrent modification.