linkedlist.rs

use bumpalo::Bump;
use std::fmt;


mod lifetimes {
    use std::mem;

    pub unsafe fn extend_lifetime<'a, 'b, T>(value: &'a T) -> &'b T {
        mem::transmute(value)
    }

    pub unsafe fn extend_lifetime_mut<'a, 'b, T>(value: &'a mut T) -> &'b mut T {
        mem::transmute(value)
    }
}

pub struct LinkedList<'bmp, T: 'bmp> {
    bump: &'bmp Bump,
    next: Option<*mut LinkedList<'bmp, T>>,
    before: Option<*mut LinkedList<'bmp, T>>,

    pub value: *mut T,
}

impl<'bmp, T> LinkedList<'bmp, T> {
    pub fn new_with_bump(value: T, bump: &'bmp Bump) -> &mut Self {
        let bump_value = bump.alloc(value);

        bump.alloc(Self {
            bump,
            value: bump_value,
            next: None,
            before: None
        })
    }

    pub fn get_last_mut(&mut self) -> &'bmp mut LinkedList<'bmp, T> {
        let mut current = self;

        while let Some(next) = current.next {
            current = unsafe { &mut *next };
        };

        unsafe { lifetimes::extend_lifetime_mut(current) }
    }

    pub fn get_last(&self) -> &'bmp LinkedList<'bmp, T> {
        let mut current = self;

        while let Some(next) = current.next {
            current = unsafe { &*next };
        };

        unsafe { lifetimes::extend_lifetime(current) }
    }

    pub fn get_first_mut(&mut self) -> &'bmp mut LinkedList<'bmp, T> {
        let mut current = self;

        while let Some(before) = current.before {
            current = unsafe { &mut *before };
        };

        unsafe { lifetimes::extend_lifetime_mut(current) }
    }

    pub fn get_first(&self) -> &'bmp LinkedList<'bmp, T> {
        let mut current = self;

        while let Some(before) = current.before {
            current = unsafe { &*before };
        };

        unsafe { lifetimes::extend_lifetime(current) }
    }

    pub fn push_to_end(&mut self, value: T) -> &mut LinkedList<'bmp, T> {
        let next = Self::new_with_bump(value, self.bump) as *mut LinkedList<'bmp, T>;

        unsafe {
            (*next).before = Some(self as *mut _);
        }

        self.get_last_mut().next = Some(next);

        unsafe { &mut *next }
    }

    pub fn push_to_front(&mut self, value: T) -> &mut LinkedList<'bmp, T> {
        let before = Self::new_with_bump(value, self.bump) as *mut LinkedList<'bmp, T>;

        self.before = Some(before);
        unsafe { (*before).next = Some(self as *mut _) };

        unsafe { &mut *before }
    }

    pub fn iter(&self) -> Iter<'bmp, T> {
        Iter { next: Some(self as *const _) }
    }

    pub fn iter_mut(&mut self) -> IterMut<'bmp, T> {
        IterMut { next: Some(self as *mut _) }
    }
}

pub struct Iter<'bmp, T> {
    next: Option<*const LinkedList<'bmp, T>>
}

impl<'bmp, T> Iterator for Iter<'bmp, T> {
    type Item = &'bmp T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|ll| {
            self.next = unsafe {
                (*ll)
                    .next
                    .map(|ll| ll as *const _)
            };

            unsafe {&*(*ll).value}
        })
    }
}

pub struct IterMut<'bmp, T> {
    next: Option<*mut LinkedList<'bmp, T>>
}

impl<'bmp, T> Iterator for IterMut<'bmp, T> {
    type Item = &'bmp mut T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|ll| {
            self.next = unsafe { (*ll).next };
            unsafe {&mut *(*ll).value}
        })
    }
}

impl<'bmp, T: fmt::Debug> fmt::Debug for LinkedList<'bmp, T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        // skip bump field

        f.debug_struct("LinkedList")
            .field("value", unsafe { &* self.value })
            .field("next", &self.next.map(|next| unsafe { &*next }))
            .finish()
    }
}

fn main() {
    let bump = Bump::new();

    let ll = LinkedList::new_with_bump(1, &bump);

    ll.push_to_end(2);
    ll.push_to_end(3);

    let before = ll.push_to_front(0);

    println!("{before:?}");

    for value in before.iter_mut() {
        *value += 1;
    }

    for value in before.iter() {
        println!("{value}");
    };
}