How to `synchronized` on "MapEntry" of Scala `TrieMap`?

Question

I would like to update the value vold of a TrieMap t for some key k iff the new value vnew some predicate p(vold, vnew) is true. Since values can be modified through multiple threads, a synchronized block is needed. The code could t.synchronized but that would block updates to other keys' values. Is it possible to block only for the key that's actually being updated?

Now that I've written out the question, does it make sense to t.keySet.filter(_ == k).head.synchronized (since there's no guarantee that k is the same instance of the key in t)? Is there a more canonical way to do this?

Answer 1

Since values can be modified through multiple threads, a synchronized block is needed.

The canonical way of working with TrieMap is to use the replace/putIfAbsent/remove methods. Get the old value, calculate the new value, and if replace fails, repeat.

Looking through the API, I don't see anything suitable to do what you want directly, and t.keySet.filter(_ == k) has to iterate through the entire Map; in most cases I'd expect it to be worse than just locking it (unless you have a lot more threads than entries?).

Answer 2

If p satisfied the following conditions:

• antisymmetry (ie p(v0, v1) implies !p(v1, v0) and !p(v0, v1) implies p(v1, v0))
• transitivity (ie p(v0, v1) and p(v1, v2) implies p(v0, v1)

The following can be implemented (WARNING: the code below is untested):

def replaceIf(key: K, newvalue: V)(predicate: (V, V) => Boolean): Option[V] = {
  val oldvalue = replace(key, newvalue)

  if (oldvalue == None || predicate(newvalue, oldvalue.get)) {
    oldvalue
  } else {
    replaceIf(key, oldvalue.get)(predicate)
  }
}