Traditionally transient data structures use a mutable box to determine whether a node can be modified in place or not. Somehow it acts like a transaction: when the mutable box contains a non null then it means the transient is still “open” (editable nodes have not been shared yet os can be modified). Thus each node has a reference to a reference object (when the node was created by a persistent operation the reference to the reference itself is null).

When I was working on confluent map I found another way to track transients node ownership.

The main idea is to put the flag not in the node but in its parent. Since there are one flag per child, better to store them has a bitmap. Space-wise this solution is not greedier than using a reference type: a 32 bit bitmap vs a 32 bit reference (with compressed pointers) and an additional object.

The role of these flags is to tell whether a child is exclusively owned (not shared) by its parent. Now when one traverse a transient data structures from its root, one has just to check that the whole ownership chain is exclusive. When so the node is editable (mutable). No mutability required.

Tangentially related notes:

1. In confluent map, I doesn’t even need to have a separate bitmap, since I had a case left in the main bitmap.
2. CHAMP hash maps are no faster than Clojure ones, benchmarks in the paper measure differences in hash algorithms (plain Java vs Clojure Murmur3 strain) not in data structures implementations.
3. confluent maps sports 3-way merge in time linear with the number of edits (not the actual size).