crdt/ormap
an observed-remove map from Sym keys to CRDT values.
Since: crdt-spice-plan C3
ORMap
(defstruct ORMap [V])
ormap-new
(ormap-new [V])
an empty map.
A map with no keys and an empty causal context.
(ormap-new)
Since: crdt-spice-plan C3
ormap-put
(ormap-put [V])
write a key, observing it in the causal context.
| m | the map | |
| r | the replica doing the write | |
| k | the key | |
| v | the value carrier |
A map with k bound to v and a fresh dot recorded.
(ormap-put (ormap-new) (quote alice) (quote score) 5)
Since: crdt-spice-plan C3
ormap-get
(ormap-get [V])
the value carrier bound to a key.
| m | the map | |
| k | the key |
The carrier, or 0 when the key is absent.
(ormap-get m (quote score)) ; => 5
Since: crdt-spice-plan C3
ormap-has?
(ormap-has? [V])
is a key bound?
| m | the map | |
| k | the key |
true when k is present.
(ormap-has? m (quote score)) ; => true
Since: crdt-spice-plan C3
ormap-remove
(ormap-remove [V])
drop a key that this replica has observed.
| m | the map | |
| k | the key |
A map without k. The causal context is KEPT, which is what makes the removal propagate instead of being undone by the next merge.
(ormap-remove m (quote score))
Since: crdt-spice-plan C3
ormap-count
(ormap-count [V])
how many keys are bound.
| m | the map |
The number of live keys.
(ormap-count m) ; => 2
Since: crdt-spice-plan C3
ormap-keys-agree?
(ormap-keys-agree? [V])
do two maps bind exactly the same keys?
| a | first map | |
| b | second map |
true when every key of each is present in the other.
(ormap-keys-agree? x y) ; => true
Since: crdt-spice-plan C3
ormap-merge-with
(ormap-merge-with [V])
merge two maps, combining shared values with `f`.
| f | how to merge two value carriers present on both sides | |
| a | first map | |
| b | second map |
The merged map.
(ormap-merge-with pn-join alice bob)
Since: crdt-spice-plan C3
ormap-join
(ormap-join [V])
merge two maps using `V`'s own JoinSemilattice instance.
| a | first map | |
| b | second map |
The merged map.
(join alice bob)
Since: crdt-spice-plan C3
OrmapDelta
(defstruct OrmapDelta [V])
a key fragment plus the EXACT dots it retracts.
Since: crdt-spice-plan C4
ormap-delta-new
(ormap-delta-new [V])
the empty delta.
A delta that writes nothing and retracts nothing.
(:: (ormap-delta-new) (OrmapDelta MaxI))
Since: crdt-spice-plan C4
ormap-delta-count
(ormap-delta-count [V])
how many keys the delta writes.
| d | the delta |
Its key count.
(ormap-delta-count d) ; => 1
Since: crdt-spice-plan C4
ormap-delta-retracts
(ormap-delta-retracts [V])
how many dots the delta withdraws.
| d | the delta |
Its retraction count.
(ormap-delta-retracts d) ; => 1
Since: crdt-spice-plan C4
ormap-delta-put
(ormap-delta-put [V])
the DELTA of writing a key.
| m | the map, read for the replica's next dot | |
| r | the replica doing the write | |
| k | the key | |
| v | the value carrier |
A one-key delta carrying a fresh dot.
(ormap-delta-put m (quote alice) (quote score) (:: 5 MaxI))
Since: crdt-spice-plan C4
ormap-delta-remove
(ormap-delta-remove [V])
the DELTA of dropping a key.
| m | the map, read for the key's recorded dot | |
| k | the key |
A delta writing nothing and retracting exactly the dot this replica has for k.
(ormap-delta-remove m (quote score))
Since: crdt-spice-plan C4
ormap-apply
(ormap-apply [V])
fold a delta into a map, merging values at V's instance.
| m | the map | |
| d | the delta |
The map with d's writes merged in and d's retractions withdrawn.
(ormap-apply mine (ormap-delta-put theirs (quote bob) (quote k) v))
Since: crdt-spice-plan C4
Internal definitions
dot-ctr__om-- internal: a dot's counter, without importing Dot's accessors.__keys-subset?-- internal: every key of a is present in b.__subset-loop-- internal.__side-- internal: fold one side's live keys into the entry accumulator.__side-loop-- internal.__vjoin-- internal: combine two value carriers at `V`'s own instance.__dots-for-- internal: the dot map for the surviving keys.__dots-loop-- internal: keep the HIGHER of the two sides' dot counters.__reps-for-- internal: the replica map for the surviving keys.__reps-loop-- internal.__seen?-- internal: has the other side's context observed src's dot for k?__put-- internal: bind k in a carrier-held map, staying a carrier.__dot-of-- internal: a key's recorded dot counter, or 0.__rms-for-key-- internal: the single dot recorded for k, as an exact set.__apply-writes-- internal: fold a delta's writes into the entry map.__apply-writes-loop-- internal.__apply-dots-- internal: overlay a delta's dot (or replica) map.__apply-dots-loop-- internal.__drop-retracted-- internal: drop every key whose dot the delta withdraws.__drop-loop-- internal.__rep-of-- internal: a key's recorded replica, or the empty name.__rms-has?__om-- internal: is this exact dot in a retraction carrier?__keep-keys-- internal: restrict a side map to the surviving keys.__keep-loop-- internal.__witness-dots-- internal: record a delta's written dots in the context.__witness-dots-loop-- internal.__witness-rms__om-- internal: record a delta's retracted dots.__witness-rms-loop__om-- internal.__max-ctr-of__om-- internal: the highest counter in a counter set.__max-ctr-loop__om-- internal.JoinSemilattice[]-- write both sides, retract both sides.ormap-delta-merge-- internal: the delta join, spelled as a defn.__merge-writes-- internal: overlay b's writes onto a's, joining shared keys.__merge-writes-loop-- internal.DeltaCRDT[]-- the delta is a key fragment plus exact retractions.JoinSemilattice[]-- an ORMap is a lattice exactly when its values are.