crdt/rga
one element: its id, its origin's id, its value, its tombstone.
Since: crdt-spice-plan C5
Rga
(defstruct Rga [nodes : int clock : int])
a replicated sequence.
Since: crdt-spice-plan C5
rga-new
(rga-new :)
an empty sequence.
An Rga with no nodes and a clock at 0.
(rga-new)
Since: crdt-spice-plan C5
rga-size
(rga-size [^borrow s : Rga] :)
how many nodes the array holds, tombstones included.
| s | the sequence |
The physical node count.
(rga-size s) ; => 5
Since: crdt-spice-plan C5
rga-clock
(rga-clock [^borrow s : Rga] :)
this replica's Lamport counter.
| s | the sequence |
The highest node counter it has seen.
(rga-clock s) ; => 7
Since: crdt-spice-plan C5
rga-len
(rga-len [^borrow s : Rga] :)
how many elements are visible.
| s | the sequence |
The node count excluding tombstones -- the document's length.
(rga-len s) ; => 3
Since: crdt-spice-plan C5
rga-get
(rga-get [^borrow s : Rga i : int] :)
the value at a visible index.
| s | the sequence | |
| i | zero-based index among the LIVE elements |
The value there, or 0 when i is out of range.
(rga-get s 0) ; => 72
Since: crdt-spice-plan C5
rga-alive?
(rga-alive? [^borrow s : Rga i : int] :)
is there a visible element at this index?
| s | the sequence | |
| i | zero-based live index |
true when i is in range.
(rga-alive? s 2)
Since: crdt-spice-plan C5
rga-insert
(rga-insert [s : Rga r : Sym i : int v : int] :)
insert a value at a visible index, on behalf of a replica.
| s | the sequence | |
| r | the replica doing the insert | |
| i | the live index the new element should occupy | |
| v | the value (a character code, for text) |
A sequence with v at index i.
(rga-insert (rga-new) (quote alice) 0 72)
Since: crdt-spice-plan C5
rga-append
(rga-append [s : Rga r : Sym v : int] :)
insert at the end.
| s | the sequence | |
| r | the replica | |
| v | the value |
A sequence one longer.
(rga-append s (quote alice) 33)
Since: crdt-spice-plan C5
rga-delete
(rga-delete [s : Rga i : int] :)
tombstone the element at a visible index.
| s | the sequence | |
| i | the live index to remove |
A sequence in which that element is no longer visible. Out-of-range is a no-op.
(rga-delete s 2)
Since: crdt-spice-plan C5
rga-delta-insert
(rga-delta-insert [^borrow s : Rga r : Sym i : int v : int] :)
the DELTA of an insert.
| s | the sequence, read for the clock and the origin at index i | |
| r | the replica doing the insert | |
| i | the live index the new element should occupy | |
| v | the value |
A one-node sequence carrying the new node and its origin's id.
(rga-delta-insert s (quote alice) 0 72)
Since: crdt-spice-plan C5
rga-delta-delete
(rga-delta-delete [^borrow s : Rga i : int] :)
the DELTA of a delete.
| s | the sequence, read for the node at index i | |
| i | the live index to remove |
A one-node sequence carrying that node with its tombstone set; the empty sequence when i is out of range.
(rga-delta-delete s 2)
Since: crdt-spice-plan C5
rga-merge
(rga-merge [a : Rga b : Rga] :)
merge another sequence into this one.
| a | this sequence | |
| b | the other |
The merged sequence. Both arguments are consumed.
(rga-merge mine theirs)
Since: crdt-spice-plan C5
Internal definitions
RgaNode__alive-count-- internal.__nth-live-- internal: the array index of the i-th live node, or -1.__nth-live-loop-- internal.__id-gt?-- internal: is (c1, r1) after (c2, r2) in the total id order?__index-of-- internal: the array index of the node with this id, or -1.__index-of-loop-- internal.__scan-- internal: walk forward past every node with a LARGER id.__shift-- internal: move v[i..j) one slot right, top-down.__ins-at!-- internal: splice a node in at array index i.__integrate!-- internal: place one node, or merge its tombstone if present.__merge-dead!-- internal: a tombstone, once set, stays set.__push-dead!-- internal: copy node p into out with its tombstone set.__merge-into!-- internal: integrate every node of `src` into `dst`.__integrate-from!-- internal: integrate src[i] into dst.__min-above-- internal: index of the smallest id strictly above (pc, pr).__beats?-- internal: does node p have a smaller id than node q?__imax__rga-- internal: the larger of two ints.JoinSemilattice[Rga]-- node union with tombstone OR, re-integrated.BoundedJoin[Rga]-- the empty sequence is the least element.Eq[Rga]-- the same visible values in the same order.__same-values?-- internal.DeltaCRDT[Rga]-- the delta is a one-node sequence.