Please help me write this snippet of code in 100% safe rust (beginner question)

help
1

I am trying to learn rust and would appreciate help in how to write the following snippet in 100% safe rust. This is a is doubly linked list for some specific use case and therefore it does not have all the methods one would typically expect.

#![feature(box_into_raw_non_null)]

use core::ptr::NonNull;
use core::marker::PhantomData;
use std::{ iter::Iterator, boxed::Box};
use std::mem;

extern crate core;


struct Dll<T> {
    head: Option<NonNull<Node<T>>>,
    tail: Option<NonNull<Node<T>>>,
    len: usize,
    marker: PhantomData<Box<Node<T>>>
}

struct Node<T> {
    next: Option<NonNull<Node<T>>>,
    prev: Option<NonNull<Node<T>>>,
    data: T
}

impl<T> Node<T> {
    pub fn new(data: T) -> Self {
        Node {
            next: None,
            prev: None,
            data
        }
    }
}

impl<T: Default> Dll<T> {
    pub fn new() -> Self {
        Dll {
            head: None,
            tail: None,
            len: 0,
            marker: PhantomData,
        }
    }

    /// Always adds the element to the end of the list.
    pub fn append(&mut self, data: T) -> NonNull<Node<T>> {
        let mut node = Node::new(data);
        node.prev = self.tail;
        node.next = None;
        let boxed_node = Box::new(node);
        let non_null_boxed_node = Box::into_raw_non_null(boxed_node);
        let opt_node = Some(non_null_boxed_node);
        match self.tail {
            Some(mut tail) => {
                unsafe {
                    tail.as_mut().next = opt_node;
                }
            }
            None => self.head = opt_node,
        }
        self.tail = opt_node;
        self.len += 1;
        non_null_boxed_node
    }

    fn unlink_node(&mut self, mut in_node: NonNull<Node<T>>) -> T {
        let node;
        unsafe {
            node = in_node.as_mut();
        }
        match node.prev {
            Some(mut prev) => unsafe {
                prev.as_mut().next = node.next.clone()
            },
            None => self.head = node.next.clone()
        }

        match node.next {
            Some(mut next) => unsafe {
                next.as_mut().prev = node.prev.clone()
            },
            None => self.tail = node.prev.clone()
        }
        self.len -= 1;

        mem::replace(&mut node.data, T::default())
    }
    /// This works in two folds:
    /// - remove the element from its old position, this might require to adjust
    ///   its previous and next to point to each other with some changes to tail
    ///   and head if required.
    /// - then move it to the end of the list.
    pub fn move_to_end(&mut self, node: NonNull<Node<T>>) ->
        NonNull<Node<T>> {
        let data = self.unlink_node(node);
        self.append(data)
    }

    pub fn iter(&self) -> Iter<'_, T> {
        Iter {
            head: self.head,
            len: self.len,
            marker: PhantomData,
        }
    }
}

pub struct Iter<'a, T: 'a> {
    head: Option<NonNull<Node<T>>>,
    len: usize,
    marker: PhantomData<&'a Node<T>>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    #[inline]
    fn next(&mut self) -> Option<&'a T> {
        if self.len == 0 {
            None
        } else {
            self.head.map(|non_null_node| {
                // Need an unbound lifetime to get 'a
                let node: &Node<T>;
                unsafe {
                    node = &*non_null_node.as_ptr();
                }
                self.len -= 1;
                self.head = node.next;
                &node.data
            })
        }
    }
}

#[test]
fn test() {
    let mut list = Dll::new();
    let node1 = list.append(1);
    let _node2 = list.append(2);
    let _node3 = list.append(3);
    assert_eq!(vec![&1, &2, &3], list.iter().collect::<Vec<_>>());
    list.move_to_end(node1);
    assert_eq!(vec![&2, &3, &1], list.iter().collect::<Vec<_>>());
}

How can I remove the unsafe parts with safe rust ?

2

You can't use NonNull or write a doubly linked list in safe Rust. Have you read

Edit: not possible to write an efficient doubly linked list in safe Rust

3

Thanks a lot @RustyYato for your response.

I have skimmedthrough the github link you refer to. They have implemented a singly linked list though, if I haven't missed something.
When you say, " You can’t use NonNull or write a doubly linked list in safe Rust", do you mean writing a doubly linked list in safe rust is impossible ?

4

Later in the book

They give a doubly linked list using safe Rust

I missed a single word, efficient, edited to fix it.

1 Like
5

Its a dqueue, so elements can only be added or removed in the end or the beginning.
Thanks a lot @RustyYato. I will read it and experiment with it being in the safe waters :slight_smile: . But as you say, that won't be efficient. Thanks again.

6

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.