token_cell_linked_list.rs

use std::{
    cell::UnsafeCell,
    fmt::{self, Debug},
    marker::PhantomData,
    mem::self,
    ops::{Deref, DerefMut},
    ptr::NonNull,
};

#[macro_use]
mod token_cell {
    use super::*;
    
    pub unsafe trait Token: Send + Sync {}

    macro_rules! token {
        () => {{
            use token_cell::Token;
            fn mint_token() -> impl Token {
                struct ThrowawayType;
                unsafe impl Token for ThrowawayType {}
                ThrowawayType
            }
            mint_token()
        }};
    }
    
    unsafe impl<T, Tok> Send for TokenCell<T, Tok> where T: Send, Tok: Token {}
    unsafe impl<T, Tok> Sync for TokenCell<T, Tok> where T: Send + Sync, Tok: Token {}
    
    pub struct TokenCell<T, Tok> {
        _marker: PhantomData<Tok>,
        value: UnsafeCell<T>,
    }
    
    impl<T, Tok> TokenCell<T, Tok> {
        pub const fn new(value: T) -> Self {
            TokenCell {
                _marker: PhantomData,
                value: UnsafeCell::new(value),
            }
        }
    }
    
    impl<T, Tok: Token> TokenCell<T, Tok> {
        pub fn into_inner(self) -> T {
            self.value.into_inner()
        }
        
        pub fn get_mut(&mut self) -> &T {
            self.value.get_mut()
        }
        
        pub fn from_mut(t: &mut T) -> &mut Self {
            unsafe {
                // Safety: `T` and `TokenCell<T, _>` have an identical representation.
                mem::transmute(t)
            }
        }
        
        pub fn borrow<'a>(&'a self, _token: &'a Tok) -> &'a T {
            unsafe {
                &*self.value.get()
            }
        }
        
        pub fn borrow_mut<'a>(&'a self, _token: &'a mut Tok) -> &'a mut T {
            unsafe {
                &mut *self.value.get()
            }
        }
    }
} // mod anon_cell

mod static_rc {
    use super::*;
    
    /// Parameters:
    /// -   T: the value owned, shared.
    /// -   C / N: the ratio of shares owned by the current instance.
    pub struct StaticRc<T: ?Sized, const C: usize, const N: usize> {
        pointer: NonNull<T>,
    }
    
    impl<T, const N: usize> StaticRc<T, N, N> {
        pub fn new(value: T) -> Self {
            let pointer = NonNull::from(Box::leak(Box::new(value)));
            Self { pointer }
        }
    
        pub fn into_inner(this: Self) -> T {
            //  Safety:
            //  -   C == N, hence complete ownership.
            let b = unsafe { Box::from_raw(this.pointer.as_ptr()) };
            mem::forget(this);
    
            *b
        }
    }
    
    impl<T: ?Sized, const C: usize, const N: usize> StaticRc<T, C, N> {
        /// Returns the (non-null) pointer.
        pub fn as_ptr(this: &Self) -> NonNull<T> { this.pointer }
    
        /// Adjusts the ratio of shares to a different base; the ratio is preserved.
        pub fn adjust<const D: usize, const O: usize>(this: Self) -> StaticRc<T, D, O> {
            //  C / N == D / O
            //  <=> C * O == D * N.
            assert_eq!(C.checked_mul(O).unwrap(), D.checked_mul(N).unwrap(),
                "{} / {} != {} / {}", C, N, D, O);
    
            let pointer = this.pointer;
            mem::forget(this);
    
            StaticRc { pointer }
        }
    
        /// Splits the count C into A and Tok, where A + Tok = C.
        pub fn split<const A: usize, const B: usize>(this: Self) -> (StaticRc<T, A, N>, StaticRc<T, B, N>) {
            assert_eq!(C, A + B, "{} != {} + {}", C, A, B);
    
            let pointer = this.pointer;
            mem::forget(this);
            
            (StaticRc { pointer }, StaticRc { pointer })
        }
    
        /// Joins the counts together, where A + C = TOTAL.
        ///
        /// Panics if the pointer between the two handles differ.
        pub fn join<const TOTAL: usize, const A: usize>(this: Self, other: StaticRc<T, A, N>) -> StaticRc<T, TOTAL, N> {
            assert_eq!(C + A, TOTAL, "{} + {} != {}", C, A, TOTAL);
            debug_assert!(TOTAL <= N, "{} > {}", TOTAL, N);
    
            assert_eq!(this.pointer, other.pointer);
    
            let pointer = this.pointer;
            mem::forget(this);
            mem::forget(other);
    
            StaticRc { pointer }
        }
    }
    
    impl<T: ?Sized, const C: usize, const N: usize> Drop for StaticRc<T, C, N> {
        fn drop(&mut self) {
            assert_eq!(C, N, "attempted to drop a `StaticRc` without full ownership");
            //  Safety:
            //  -   C == N, hence complete ownership.
            //  -   `self.pointer` was allocated by Box.
            unsafe { Box::from_raw(self.pointer.as_ptr()) };
        }
    }
    
    impl<T: ?Sized + Debug, const C: usize, const N: usize> Debug for StaticRc<T, C, N> {
        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
            let value: &T = &*self;
            write!(f, "StaticRc<_, {}, {}>{{{:?}}}", C, N, value)
        }
    }
    
    impl<T: ?Sized, const C: usize, const N: usize> Deref for StaticRc<T, C, N> {
        type Target = T;
    
        fn deref(&self) -> &T { unsafe { self.pointer.as_ref() } }
    }
    
    impl<T: ?Sized, const N: usize> DerefMut for StaticRc<T, N, N> {
        fn deref_mut(&mut self) -> &mut T { unsafe { self.pointer.as_mut() } }
    }
} // mod static_rc

mod linked_list {
    use super::token_cell::{TokenCell, Token};
    use super::static_rc::StaticRc;
    
    type TokenNode<T, Tok> = TokenCell<Node<T, Tok>, Tok>;
    type HalfNodePtr<T, Tok> = StaticRc<TokenNode<T, Tok>, 1, 2>;
    type FullNodePtr<T, Tok> = StaticRc<TokenNode<T, Tok>, 2, 2>;
    
    struct Node<T, Tok> {
        data: T,
        prev: Option<HalfNodePtr<T, Tok>>,
        next: Option<HalfNodePtr<T, Tok>>,
    }
    
    pub struct List<T, Tok> {
        token: Tok,
        head_tail: Option<(HalfNodePtr<T, Tok>, HalfNodePtr<T, Tok>)>,
    }
    
    impl<T, Tok: Token> List<T, Tok> {
        pub fn new(token: Tok) -> Self {
            Self { token, head_tail: None, }
        }
    
        pub fn is_empty(&self) -> bool { self.head_tail.is_none() }
    
        pub fn clear(&mut self) {
            while let Some(_) = self.pop_back() {}
        }
    
        pub fn front(&self) -> Option<&T> {
            self.head_tail.as_ref().map(|(head, _)| {
                &head.borrow(&self.token).data
            })
        }
    
        pub fn front_mut(&mut self) -> Option<&mut T> {
            //  Work-around lack of field-borrow in closures.
            let token = &mut self.token;
        
            self.head_tail.as_mut().map(move |(head, _)| {
                &mut head.borrow_mut(token).data
            })
        }
    
        pub fn back(&self) -> Option<&T> {
            self.head_tail.as_ref().map(|(_, tail)| {
                &tail.borrow(&self.token).data
            })
        }
    
        pub fn back_mut(&mut self) -> Option<&mut T> {
            //  Work-around lack of field-borrow in closures.
            let token = &mut self.token;
        
            self.head_tail.as_mut().map(move |(_, tail)| {
                &mut tail.borrow_mut(token).data
            })
        }
    
        pub fn push_front(&mut self, data: T) {
            let (one, two) = List::new_halves(data);
    
            let head_tail = if let Some((head, tail)) = self.head_tail.take() {
                head.borrow_mut(&mut self.token).prev = Some(one);
    
                two.borrow_mut(&mut self.token).next = Some(head);
    
                (two, tail)
            } else {
                (one, two)
            };
    
            self.head_tail = Some(head_tail);
        }
    
        pub fn pop_front(&mut self) -> Option<T> {
            let (head, tail) = self.head_tail.take()?;
    
            if StaticRc::as_ptr(&head) == StaticRc::as_ptr(&tail) {
                return Some(Self::into_inner(head, tail));
            }
    
            let next = head.borrow_mut(&mut self.token).next.take()
                .expect("Non-tail should have a next node");
            let other_head = next.borrow_mut(&mut self.token).prev.take()
                .expect("Non-head should have a previous node");
    
            self.head_tail = Some((next, tail));
    
            Some(Self::into_inner(head, other_head))
        }
    
        pub fn push_back(&mut self, data: T) {
            let (one, two) = List::new_halves(data);
    
            let head_tail = if let Some((head, tail)) = self.head_tail.take() {
                tail.borrow_mut(&mut self.token).next = Some(one);
    
                two.borrow_mut(&mut self.token).prev = Some(tail);
    
                (head, two)
            } else {
                (one, two)
            };
    
            self.head_tail = Some(head_tail);
        }
    
        pub fn pop_back(&mut self) -> Option<T> {
            let (head, tail) = self.head_tail.take()?;
    
            if StaticRc::as_ptr(&head) == StaticRc::as_ptr(&tail) {
                return Some(Self::into_inner(head, tail));
            }
    
            let prev = tail.borrow_mut(&mut self.token).prev.take()
                .expect("Non-head should have a previous node");
            let other_tail = prev.borrow_mut(&mut self.token).next.take()
                .expect("Non-tail should have a next node");
    
            self.head_tail = Some((head, prev));
    
            Some(Self::into_inner(tail, other_tail))
        }
    
        fn new_halves(data: T) -> (HalfNodePtr<T, Tok>, HalfNodePtr<T, Tok>) {
            let node = Node { data, prev: None, next: None, };
            let full = FullNodePtr::new(TokenNode::new(node));
    
            StaticRc::split::<1, 1>(full)
        }
    
        fn into_inner(left: HalfNodePtr<T, Tok>, right: HalfNodePtr<T, Tok>) -> T {
            let full = HalfNodePtr::join::<2, 1>(left, right);
            let token_cell = FullNodePtr::into_inner(full);
            let node = TokenNode::into_inner(token_cell);
    
            //  If the node still has a prev and next, they are leaked.
            debug_assert!(node.prev.is_none());
            debug_assert!(node.next.is_none());
    
            node.data
        }
    }
} // mod linked_list

use linked_list::List;

fn main() {
    let token = token!();
    
    let mut list = List::new(token);
    list.push_back("Hello, World again!".to_string());
    list.push_back("Hello, World!".to_string());

    while let Some(element) = list.pop_back() {
        println!("{:?}", element);
    }
    
}