vthread 0.1.0

Bounded carrier-affine virtual threads for Rust
Documentation
//! Exact, structurally shared live-ancestry signatures.

use std::sync::Arc;

#[path = "cancellation_signature_compare.rs"]
mod compare;
#[path = "cancellation_signature_work.rs"]
mod work;
use work::Counter;

#[path = "cancellation_signature_iter.rs"]
mod iter;
use iter::Iter;

#[cfg(test)]
#[derive(Clone, Copy, Debug, Default)]
pub(super) struct Work {
    pub(super) union_items: usize,
    pub(super) equality_nodes: usize,
    pub(super) allocated_nodes: usize,
}

#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
pub(super) struct Candidate {
    len: usize,
    xor: u64,
    sum: u64,
}

#[derive(Clone, Default)]
pub(super) struct Signature(Root);

#[derive(Clone, Default)]
enum Root {
    #[default]
    Empty,
    Singleton(usize),
    Tree(Arc<Node>),
}

struct Node {
    kind: NodeKind,
    sample: usize,
    len: usize,
    xor: u64,
    sum: u64,
}

enum NodeKind {
    Leaf(usize),
    Branch {
        bit: u32,
        left: Arc<Node>,
        right: Arc<Node>,
    },
}

impl Signature {
    pub(super) fn singleton(id: usize) -> Self {
        Self(Root::Singleton(id))
    }

    pub(super) fn cardinality(&self) -> usize {
        match &self.0 {
            Root::Empty => 0,
            Root::Singleton(_) => 1,
            Root::Tree(node) => node.len,
        }
    }

    pub(super) fn candidate(&self) -> Candidate {
        match &self.0 {
            Root::Empty => Candidate {
                len: 0,
                xor: 0,
                sum: 0,
            },
            Root::Singleton(id) => Candidate {
                len: 1,
                xor: atom(*id, 0x243f_6a88_85a3_08d3),
                sum: atom(*id, 0x1319_8a2e_0370_7344),
            },
            Root::Tree(node) => Candidate {
                len: node.len,
                xor: node.xor,
                sum: node.sum,
            },
        }
    }

    pub(super) fn union(&self, other: &Self) -> Self {
        self.union_inner(other, &mut Counter::new())
    }

    #[cfg(test)]
    pub(super) fn union_counted(&self, other: &Self) -> (Self, Work) {
        let mut counter = Counter::new();
        let result = self.union_inner(other, &mut counter);
        (result, counter.finish())
    }

    fn union_inner(&self, other: &Self, counter: &mut Counter) -> Self {
        if matches!(self.0, Root::Empty) {
            return other.clone();
        }
        if matches!(other.0, Root::Empty) || self.ptr_eq(other) {
            return self.clone();
        }
        if self.candidate() == other.candidate() && self.same_set_inner(other, counter) {
            return self.clone();
        }
        let (mut result, additions) = if self.cardinality() >= other.cardinality() {
            (self.clone(), other)
        } else {
            (other.clone(), self)
        };
        for id in additions.iter() {
            counter.union_item();
            result = result.insert(id, counter);
        }
        result
    }

    pub(super) fn same_set(&self, other: &Self) -> bool {
        self.same_set_inner(other, &mut Counter::new())
    }

    #[cfg(test)]
    pub(super) fn same_set_counted(&self, other: &Self) -> (bool, Work) {
        let mut counter = Counter::new();
        let result = self.same_set_inner(other, &mut counter);
        (result, counter.finish())
    }

    fn same_set_inner(&self, other: &Self, counter: &mut Counter) -> bool {
        if self.ptr_eq(other) {
            return true;
        }
        if self.candidate() != other.candidate() {
            return false;
        }
        match (&self.0, &other.0) {
            (Root::Tree(left), Root::Tree(right)) => {
                compare::same(Some(left), Some(right), counter)
            }
            _ => false,
        }
    }

    fn ptr_eq(&self, other: &Self) -> bool {
        match (&self.0, &other.0) {
            (Root::Empty, Root::Empty) => true,
            (Root::Singleton(left), Root::Singleton(right)) => left == right,
            (Root::Tree(left), Root::Tree(right)) => Arc::ptr_eq(left, right),
            _ => false,
        }
    }

    fn insert(&self, id: usize, counter: &mut Counter) -> Self {
        let root = match &self.0 {
            Root::Empty => return Self(Root::Singleton(id)),
            Root::Singleton(existing) => {
                if *existing == id {
                    return self.clone();
                }
                Node::leaf(*existing, counter)
            }
            Root::Tree(root) => Arc::clone(root),
        };
        let routed = route(id);
        let existing = find_leaf(&root, routed);
        if existing == id {
            return self.clone();
        }
        let differing = highest_bit(routed ^ route(existing));
        let leaf = Node::leaf(id, counter);
        Self(Root::Tree(insert_at(
            root, leaf, routed, differing, counter,
        )))
    }

    fn iter(&self) -> Iter<'_> {
        Iter::new(&self.0)
    }
}

impl Node {
    fn leaf(id: usize, counter: &mut Counter) -> Arc<Self> {
        counter.allocated_node();
        Arc::new(Self {
            kind: NodeKind::Leaf(id),
            sample: route(id),
            len: 1,
            xor: atom(id, 0x243f_6a88_85a3_08d3),
            sum: atom(id, 0x1319_8a2e_0370_7344),
        })
    }

    fn branch(bit: u32, left: Arc<Self>, right: Arc<Self>, counter: &mut Counter) -> Arc<Self> {
        assert!(!bit_set(left.sample, bit));
        assert!(bit_set(right.sample, bit));
        counter.allocated_node();
        Arc::new(Self {
            sample: left.sample,
            len: left.len + right.len,
            xor: left.xor ^ right.xor,
            sum: left.sum.wrapping_add(right.sum),
            kind: NodeKind::Branch { bit, left, right },
        })
    }
}

fn find_leaf(root: &Arc<Node>, route: usize) -> usize {
    let mut node = root.as_ref();
    loop {
        match &node.kind {
            NodeKind::Leaf(id) => return *id,
            NodeKind::Branch { bit, left, right } => {
                node = if bit_set(route, *bit) {
                    right.as_ref()
                } else {
                    left.as_ref()
                };
            }
        }
    }
}

fn insert_at(
    root: Arc<Node>,
    leaf: Arc<Node>,
    route: usize,
    bit: u32,
    counter: &mut Counter,
) -> Arc<Node> {
    if let NodeKind::Branch {
        bit: current,
        left,
        right,
    } = &root.kind
        && *current > bit
    {
        return if bit_set(route, *current) {
            Node::branch(
                *current,
                Arc::clone(left),
                insert_at(Arc::clone(right), leaf, route, bit, counter),
                counter,
            )
        } else {
            Node::branch(
                *current,
                insert_at(Arc::clone(left), leaf, route, bit, counter),
                Arc::clone(right),
                counter,
            )
        };
    }
    if bit_set(route, bit) {
        Node::branch(bit, root, leaf, counter)
    } else {
        Node::branch(bit, leaf, root, counter)
    }
}

fn highest_bit(value: usize) -> u32 {
    assert_ne!(value, 0);
    usize::BITS - 1 - value.leading_zeros()
}

fn bit_set(value: usize, bit: u32) -> bool {
    value & (1usize << bit) != 0
}

fn route(id: usize) -> usize {
    id.reverse_bits()
}

fn atom(id: usize, salt: u64) -> u64 {
    let mut value = (id as u64) ^ salt;
    value = (value ^ (value >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
    value = (value ^ (value >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
    value ^ (value >> 31)
}

#[cfg(test)]
#[path = "cancellation_signature_test.rs"]
mod cancellation_signature_test;