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
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
(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
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.