crdt/set
GSet
(defstruct GSet [elems : int])
grow-only set of interned names.
Since: crdt-spice-plan C2
gset-new
(gset-new :)
an empty G-Set.
A G-Set with no elements.
(gset-new)
Since: crdt-spice-plan C2
gset-add
(gset-add [s : GSet x : Sym] :)
add an element.
| s | the set | |
| x | the element |
A new G-Set containing x; the old one remains valid.
(gset-add (gset-new) (quote apple))
Since: crdt-spice-plan C2
gset-has?
(gset-has? [^borrow s : GSet x : Sym] :)
is x in the set?
| s | the set | |
| x | the element |
true when x has been added.
(gset-has? s (quote apple))
Since: crdt-spice-plan C2
gset-count
(gset-count [^borrow s : GSet] :)
how many elements.
| s | the set |
The element count.
(gset-count s) ; => 3
Since: crdt-spice-plan C2
gset-delta-add
(gset-delta-add [x : Sym] :)
the DELTA of adding an element.
| x | the element |
A one-element G-Set.
(gset-delta-add (quote apple))
Since: crdt-spice-plan C4
TwoPSet
(defstruct TwoPSet [adds : GSet dels : GSet])
add-once, remove-once set: elements plus tombstones.
Since: crdt-spice-plan C2
twopset-new
(twopset-new :)
an empty 2P-Set.
A 2P-Set with no elements and no tombstones.
(twopset-new)
Since: crdt-spice-plan C2
twopset-add
(twopset-add [s : TwoPSet x : Sym] :)
add an element.
| s | the set | |
| x | the element |
A new 2P-Set. If x has already been removed this has NO effect on membership -- the tombstone wins, permanently.
(twopset-add (twopset-new) (quote apple))
Since: crdt-spice-plan C2
twopset-remove
(twopset-remove [s : TwoPSet x : Sym] :)
remove an element, permanently.
| s | the set | |
| x | the element |
A new 2P-Set in which x can never again be present.
(twopset-remove s (quote apple))
Since: crdt-spice-plan C2
twopset-has?
(twopset-has? [^borrow s : TwoPSet x : Sym] :)
is x present?
| s | the set | |
| x | the element |
true when x was added and never removed.
(twopset-has? s (quote apple))
Since: crdt-spice-plan C2
twopset-count
(twopset-count [^borrow s : TwoPSet] :)
how many elements are present.
| s | the set |
adds minus tombstones. Exact only while every tombstone corresponds to an added element, which twopset-remove does not enforce.
(twopset-count s) ; => 2
Since: crdt-spice-plan C2
twopset-size
(twopset-size [^borrow s : TwoPSet] :)
how much state this set is carrying.
| s | the set |
adds PLUS tombstones -- what a full-state send would cost, as distinct from `twopset-count`, which is what a reader sees.
(twopset-size s) ; => 5
Since: crdt-spice-plan C4
twopset-delta-add
(twopset-delta-add [x : Sym] :)
the DELTA of adding an element.
| x | the element |
A 2P-Set with one add and no tombstone.
(twopset-delta-add (quote apple))
Since: crdt-spice-plan C4
twopset-delta-remove
(twopset-delta-remove [x : Sym] :)
the DELTA of removing an element.
| x | the element |
A 2P-Set with one tombstone and no add.
(twopset-delta-remove (quote apple))
Since: crdt-spice-plan C4
Internal definitions
JoinSemilattice[GSet]-- union.BoundedJoin[GSet]-- the empty set is the least element.Eq[GSet]-- same size.DeltaCRDT[GSet]-- the delta is a one-element G-Set.JoinSemilattice[TwoPSet]-- join each side.BoundedJoin[TwoPSet]-- both sides empty.Eq[TwoPSet]-- equal on both sides.DeltaCRDT[TwoPSet]-- the delta is a 2P-Set with one side empty.