intrex 0.2.0

//! An example program using [`intrex::list`] to implement an API similar to the
//! [`intrusive-collections`][1] crate.
//!
//! [1]: https://crates.io/crates/intrusive-collections
use std::rc::Rc;

use proptest::prelude::*;

mod list_rc {
    use std::{cell::Cell, ptr::NonNull, rc::Rc};

    use intrex::list;

    macro_rules! intrusive_adapter {
        (
            $vis:vis $Name:ident = Rc<$Node:ty> { $field:ident => LinkedListLink }
        ) => {
            #[derive(Debug, Default)]
            $vis struct $Name;

            unsafe impl $crate::list_rc::Adapter for $Name {
                type Node = $Node;

                unsafe fn get_node(
                    &self,
                    link: *const $crate::list_rc::Link,
                ) -> *const Self::Node {
                    unsafe { link.byte_sub(::std::mem::offset_of!($Node, $field)) }.cast()
                }

                unsafe fn get_link(
                    &self,
                    value: *const Self::Node,
                ) -> *const $crate::list_rc::Link {
                    unsafe { value.byte_add(::std::mem::offset_of!($Node, $field)) }.cast()
                }
            }
        };
    }
    pub(crate) use intrusive_adapter;

    #[expect(clippy::missing_safety_doc)]
    pub unsafe trait Adapter {
        type Node;

        unsafe fn get_node(&self, link: *const Link) -> *const Self::Node;
        unsafe fn get_link(&self, value: *const Self::Node) -> *const Link;
    }

    #[derive(Default, Debug)]
    pub struct Link(Cell<Option<list::Link<NonNull<Link>>>>);

    pub struct LinkedList<A: Adapter> {
        adapter: A,
        head: list::Head<NonNull<Link>>,
    }

    impl<A: Adapter + Default> Default for LinkedList<A> {
        fn default() -> Self {
            Self {
                adapter: A::default(),
                head: list::Head::default(),
            }
        }
    }

    impl<A: Adapter> LinkedList<A> {
        pub fn push_back(&mut self, val: Rc<A::Node>) {
            unsafe {
                let link = self.adapter.get_link(Rc::into_raw(val));
                assert!((*link).0.get().is_none(), "node is already linked");
                self.head
                    .write(Nodes)
                    .push_back(NonNull::new_unchecked(link.cast_mut()));
            }
        }

        pub fn pop_front(&mut self) -> Option<Rc<A::Node>> {
            unsafe {
                let link = self.head.write(Nodes).pop_front()?;
                Some(Rc::from_raw(self.adapter.get_node(link.as_ptr())))
            }
        }
    }

    impl<A: Adapter> Drop for LinkedList<A> {
        fn drop(&mut self) {
            while self.pop_front().is_some() {}
        }
    }

    struct Nodes;

    impl list::NodesLink<NonNull<Link>> for Nodes {
        fn node_link(&self, node: NonNull<Link>) -> Option<list::Link<NonNull<Link>>> {
            unsafe { node.as_ref().0.get() }
        }
    }

    impl list::NodesLinkMut<NonNull<Link>> for Nodes {
        fn node_link(&mut self, node: NonNull<Link>) -> Option<list::Link<NonNull<Link>>> {
            unsafe { node.as_ref().0.get() }
        }

        fn replace_node_link(
            &mut self,
            node: NonNull<Link>,
            link: Option<list::Link<NonNull<Link>>>,
        ) -> Option<list::Link<NonNull<Link>>> {
            unsafe { node.as_ref().0.replace(link) }
        }

        fn update_node_link(
            &mut self,
            node: NonNull<Link>,
            f: impl FnOnce(&mut list::Link<NonNull<Link>>),
        ) {
            unsafe {
                node.as_ref().0.update(|mut link| {
                    f(link.as_mut().unwrap());
                    link
                })
            }
        }
    }
}

struct Node {
    link_x: list_rc::Link,
    link_y: list_rc::Link,
    x: usize,
    y: usize,
}

list_rc::intrusive_adapter!(AdapterX = Rc<Node> { link_x => LinkedListLink });
list_rc::intrusive_adapter!(AdapterY = Rc<Node> { link_y => LinkedListLink });

#[proptest::property_test]
fn buckets_xy(
    #[strategy = prop::collection::vec((0..5_usize, 0..5_usize), 0..100)] node_values: Vec<(
        usize,
        usize,
    )>,
) {
    let nodes: Vec<Rc<Node>> = node_values
        .iter()
        .map(|&(x, y)| {
            Rc::new(Node {
                link_x: <_>::default(),
                link_y: <_>::default(),
                x,
                y,
            })
        })
        .collect();

    let mut buckets_x: Vec<list_rc::LinkedList<AdapterX>> =
        (0..5).map(|_| list_rc::LinkedList::default()).collect();
    let mut buckets_y: Vec<list_rc::LinkedList<AdapterY>> =
        (0..5).map(|_| list_rc::LinkedList::default()).collect();

    // Add nodes to lists
    for node in &nodes {
        buckets_x[node.x].push_back(Rc::clone(node));
        buckets_y[node.y].push_back(Rc::clone(node));
    }

    // Check that all lists contain the correct nodes
    let mut count = 0;
    for (i, bucket) in buckets_x.iter_mut().enumerate() {
        while let Some(node) = bucket.pop_front() {
            assert_eq!(node.x, i);
            count += 1;
        }
    }
    assert_eq!(count, node_values.len());

    let mut count = 0;
    for (i, bucket) in buckets_y.iter_mut().enumerate() {
        while let Some(node) = bucket.pop_front() {
            assert_eq!(node.y, i);
            count += 1;
        }
    }
    assert_eq!(count, node_values.len());
}