TMap.View, which are STM-integrated concurrent maps. As for
TMap operations check at compile time that they are inside
TMap.View can be used either inside or outside a transaction. There is also a corresponding
As an example, let’s use
TMap to create an in-memory map that works like a database table with indices (actually indices over a view). It looks like this in the REPL
A high-level sketch
The key of the
IndexedMap works like the primary key of a database table; it is used to uniquely identify entries to update or remove. An initial cut at
IndexedMap (without indices) can just pass operations through to an underlying
TMap. Since reads are only a single transactional operation it is more concise and more efficient to use the
TMap.View returned from
Types for the view function and index
An index on the
IndexedMap is defined by a function from an entry to a derived value, the one that will be indexed. We can add flexibility with little effort by letting the function return 0 or more derived values, and then declaring that the entry matches if the desired value is one of the derived ones. This means that the function that defines an index has the type
(A, B) => Iterable[C].
An index should allow us to locate all of the entries with a particular property, so the return type of an index lookup should be a collection of entries. It is likely that the caller will want the actual values, but to resolve duplicates the entries should also be identified by key. This suggests that an index lookup should return something that can be iterated to get pairs of
Map[A, B] is an
Iterable[(A, B)], and fits the bill nicely. Locating entries is the entire purpose of an index, so an index can just be a function, rather than a new public named type.
Tracking and updating indices
We’ll keep track of the indices with a
Ref that holds an immutable
List. The STM’s transactional types mix well with Scala’s immutable collections, because there is no problem sharing those between threads. Note that we’re careful to add all of the existing elements of the map to a new index.
To simplify the index implementation,
put will separate updates into an index removal and an index insert. (It is straightforward to make a more efficient implementation would optimize the case that a call to
put did not change an indexed property.)
Now all that’s left is the actual index implementation, which relies on another
TMap. This map maintains the exact mapping from property to entries that is required to implement
Index.apply. There’s a bit of care required to handle the case when there are new derived properties or when all of the entries for a property are removed.
The code for this example is part of the ScalaSTM source on github: IndexedMap.scala.