Struct ORSet 

pub struct ORSet<T: Ord + Clone> { /* private fields */ }

An observed-remove set (OR-Set), also known as an add-wins set.

Unlike the 2P-Set, elements can be freely added and removed, and re-added after removal. Each add operation generates a unique tag. Remove only removes the tags that the remover has observed, so concurrent adds are preserved.

Example

use crdt_kit::prelude::*;

let mut s1 = ORSet::new(1);
s1.insert("apple");
s1.insert("banana");
s1.remove(&"banana");

let mut s2 = ORSet::new(2);
s2.insert("banana"); // concurrent add

s1.merge(&s2);
// banana is present because s2's add was concurrent with s1's remove
assert!(s1.contains(&"banana"));
assert!(s1.contains(&"apple"));

Implementations

impl<T: Ord + Clone> ORSet<T>

pub fn new(actor: NodeId) -> Self

Create a new empty OR-Set for the given node.

pub fn insert(&mut self, value: T)

Insert an element into the set.

Generates a unique tag for this insertion. Even if the element was previously removed, this new tag allows it to be re-added.

pub fn remove(&mut self, value: &T) -> bool

Remove an element from the set.

Only removes the tags that this replica has observed. Concurrent adds on other replicas will survive the merge.

Returns true if the element was present and removed.

pub fn contains(&self, value: &T) -> bool

Check if the set contains an element.

pub fn len(&self) -> usize

Get the number of distinct elements in the set.

pub fn is_empty(&self) -> bool

Check if the set is empty.

pub fn iter(&self) -> impl Iterator<Item = &T>

Iterate over the elements in the set.

pub fn actor(&self) -> NodeId

Get this replica’s node ID.

pub fn tombstone_count(&self) -> usize

Get the number of tombstones stored.

pub fn compact_tombstones(&mut self) -> usize

Remove tombstones that are no longer needed.

A tombstone is only needed while it might suppress a tag that hasn’t been propagated yet. Once no live element carries the same tag, the tombstone is safe to discard.

Note: this is a local-only GC. It is safe to call at any time, but for best results call it after all peers have converged.

Returns the number of tombstones removed.

pub fn compact_tombstones_all(&mut self) -> usize

Aggressively remove all tombstones.

This is safe only when every peer has converged to the same state.

Returns the number of tombstones removed.

Trait Implementations

impl<T: Clone + Ord + Clone> Clone for ORSet<T>

fn clone(&self) -> ORSet<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Ord + Clone> Crdt for ORSet<T>

fn merge(&mut self, other: &Self)

Merge another replica’s state into this one.

impl<T: Debug + Ord + Clone> Debug for ORSet<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Ord + Clone> DeltaCrdt for ORSet<T>

type Delta = ORSetDelta<T>

The type of delta produced by this CRDT.

fn delta(&self, other: &Self) -> ORSetDelta<T>

Generate a delta containing changes in self that other does not have.

fn apply_delta(&mut self, delta: &ORSetDelta<T>)

Apply a delta to this replica’s state.

impl<T: Ord + Clone> IntoIterator for ORSet<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: PartialEq + Ord + Clone> PartialEq for ORSet<T>

fn eq(&self, other: &ORSet<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Ord + Clone> Versioned for ORSet<T>

const CURRENT_VERSION: u8 = 1

Current schema version for this CRDT type’s serialization format.

const CRDT_TYPE: CrdtType = CrdtType::ORSet

The CRDT type identifier for the envelope.

impl<T: Eq + Ord + Clone> Eq for ORSet<T>

impl<T: Ord + Clone> StructuralPartialEq for ORSet<T>