unsafe

src/lib.rs

#![allow(unused)]
fn main() {
pub mod immutable_linked_list;
pub mod safe_linked_list;
pub mod unsafe_linked_list;
}

src/main.rs

use linked_list::immutable_linked_list::LinkedList as ImmutableList;
use linked_list::safe_linked_list::LinkedList as SafeList;
use linked_list::unsafe_linked_list::LinkedList as UnsafeList;

fn create_lists() -> (ImmutableList, SafeList, UnsafeList) {
    (ImmutableList::new(), SafeList::new(), UnsafeList::new())
}

fn main() {
    let (immutable_list, mut safe_list, mut unsafe_list) = create_lists();

    // Populate lists
    let immutable_list = immutable_list.push(1);
    let immutable_list = immutable_list.push(2);
    let immutable_list = immutable_list.push(3);

    safe_list.push(1);
    safe_list.push(2);
    safe_list.push(3);

    unsafe_list.push(1);
    unsafe_list.push(2);
    unsafe_list.push(3);

    let (i_val, immutable_list) = immutable_list.pop();
    let s_val = safe_list.pop();
    let u_val = unsafe_list.pop();

    assert_eq!(i_val, s_val);
    assert_eq!(i_val, u_val);
    assert_eq!(s_val, u_val);

    let immutable_list = immutable_list.push(4);
    safe_list.push(4);
    unsafe_list.push(4);

    immutable_list.print();
    safe_list.print();
    unsafe_list.print();

    for _j in 1..5 {
        let mut ul = UnsafeList::new();
        for i in 1..1_000_000 {
            ul.push(i);
        }
    }

    unsafe_list.print();
}

src/immutable_linked_list/mod.rs

#![allow(unused)]
fn main() {
// ANCHOR: element
struct Element {
    data: i32,
    next: Option<Box<Element>>,
}
// ANCHOR_END: element

impl Element {
    fn new(data: i32, next: Option<Box<Element>>) -> Self {
        Element { data, next }
    }
}

// ANCHOR: linked_list
pub struct LinkedList {
    head: Option<Box<Element>>,
}
// ANCHOR_END: linked_list

impl LinkedList {
    // ANCHOR: new
    pub fn new() -> Self {
        Self { head: None }
    }
    // ANCHOR_END: new

    // ANCHOR: is_empty
    pub fn is_empty(self) -> (bool, Self) {
        match self.head {
            None => (true, self),
            _ => (false, self),
        }
    }
    // ANCHOR_END: is_empty

    // ANCHOR: push
    pub fn push(self, data: i32) -> Self {
        let elem = Box::new(Element::new(data, self.head));
        Self { head: Some(elem) }
    }
    // ANCHOR_END: push

    // ANCHOR: pop
    pub fn pop(self) -> (Option<i32>, Self) {
        if let Some(elem) = self.head {
            (Some(elem.data), Self { head: elem.next })
        } else {
            (None, Self { head: None })
        }
    }
    // ANCHOR_END: pop

    // ANCHOR: print
    pub fn print(self) -> Self {
        // Attention : new_list est reconstruite en ré-empilant chaque élément en
        // tête, elle est donc renvoyée dans l'ordre inverse de `self`.
        let mut new_list = Self::new();
        // ANCHOR: while
        let mut current = self.head;
        while let Some(tmp) = current {
            print!("{} --> ", tmp.data);
            new_list = new_list.push(tmp.data);
            current = tmp.next;
        }
        println!("∅");
        // ANCHOR_END: while
        new_list
    }
    // ANCHOR_END: print

    #[allow(dead_code)]
    // ANCHOR: clear
    pub fn clear(self) {
        let mut current = self.head;
        while let Some(tmp) = current {
            current = tmp.next;
        }
    }
    // ANCHOR_END: clear
}

#[cfg(test)]
mod tests {
    use super::LinkedList;

    #[test]
    fn new() {
        let (is_empty, _) = LinkedList::new().is_empty();
        assert!(is_empty);
    }

    #[test]
    fn push() {
        let list = LinkedList::new();
        let list = list.push(1);
        let (is_empty, list) = list.is_empty();
        assert!(!is_empty);
        assert_eq!(list.head.as_ref().unwrap().data, 1);

        let list = list.push(2);
        assert_eq!(list.head.unwrap().data, 2);
    }

    #[test]
    fn pop() {
        let list = LinkedList::new();
        let (e, list) = list.pop();
        assert_eq!(e, None);

        let list = list.push(1);
        let (e, list) = list.pop();
        assert_eq!(e, Some(1));

        let (e, list) = list.pop();
        assert_eq!(e, None);

        let list = list.push(2);
        let list = list.push(3);
        let list = list.push(4);

        assert_eq!(list.head.as_ref().unwrap().data, 4);

        let (e, list) = list.pop();
        assert_eq!(list.head.as_ref().unwrap().data, 3);
        assert_eq!(e, Some(4));
        let (_, list) = list.pop();
        let (_, list) = list.pop();
        let (is_empty, _) = list.is_empty();
        assert!(is_empty);
    }
}
}

src/safe_linked_list/mod.rs

#![allow(unused)]
fn main() {
// ANCHOR: element
struct Element {
    data: i32,
    next: Option<Box<Element>>,
}
// ANCHOR_END: element

impl Element {
    fn new(data: i32, next: Option<Box<Element>>) -> Self {
        Element { data, next }
    }
}

// ANCHOR: linked_list
pub struct LinkedList {
    head: Option<Box<Element>>,
}
// ANCHOR_END: linked_list

impl LinkedList {
    // ANCHOR: new
    pub fn new() -> Self {
        Self { head: None }
    }
    // ANCHOR_END: new

    // ANCHOR: is_empty
    pub fn is_empty(&self) -> bool {
        self.head.is_none()
    }
    // ANCHOR_END: is_empty

    // ANCHOR: push
    pub fn push(&mut self, data: i32) {
        // let new_element = Box::new(Element::new(data, self.head));
        // Cela ne peut pas fonctionner, parce qu'on est derrière une référence partagée
        // et donc on ne peut pas "move" self.head

        // ANCHOR: take
        let new_head = Box::new(Element::new(data, self.head.take()));
        // ANCHOR_END: take
        // take retourne la valeur qui se trouve dans Some et laisse un None
        // à la place de l'option.
        // C'est strictement équivalent au replace (ci-dessous)
        self.head = Some(new_head);
    }
    // ANCHOR_END: push

    // ANCHOR: push_replace
    pub fn push_replace(&mut self, data: i32) {
        // ANCHOR: replace
        let old_head = std::mem::replace(&mut self.head, None);
        let new_head = Box::new(Element::new(data, old_head));
        // ANCHOR_END: replace
        // replace retourne self.head et remplace l'ancienne valeur par None (comme ça le compilateur est content)
        self.head = Some(new_head);
    }
    // ANCHOR_END: push_replace

    // ANCHOR: push_unsafe
    pub fn push_unsafe(&mut self, data: i32) {
        let old_head = unsafe {
            // De la documentation:
            // `read` crée une copie bit à bit de `T`, que `T` soit [`Copy`] ou non.
            // Si `T` n'est pas [`Copy`], utiliser à la fois la valeur renvoyée et la valeur de
            // `*src` peut violer la sécurité de la mémoire. Notez que l'assignation à `*src` compte comme une
            // utilisation parce qu'elle tentera de `drop` la valeur à `*src`.
            let result = std::ptr::read(&self.head);
            std::ptr::write(&mut self.head, None);
            // Ce `write` est en fait un "truc" pour enlever l'aliasing entre
            // self.head et result. Il écrase la valeur à self.head avec None
            // sans `drop` self.head et donc result.
            result
        };
        let new_head = Box::new(Element::new(data, old_head));
        self.head = Some(new_head);
    }
    // ANCHOR_END: push_unsafe

    // ANCHOR: pop
    pub fn pop(&mut self) -> Option<i32> {
        // map prend la valeur dans Some, lui applique la fonction anonyme
        // et remballe la valeur obtenue dans un Some. Si l'Option
        // originale est None, il se passe rien.
        self.head.take().map(|element| {
            self.head = element.next;
            element.data
        })
    }
    // ANCHOR_END: pop

    // ANCHOR: print
    pub fn print(&self) {
        let mut current = &self.head;
        while let Some(tmp) = &current {
            print!("{} --> ", tmp.data);
            current = &tmp.next;
        }
        println!("∅");
    }
    // ANCHOR_END: print
}

impl Drop for LinkedList {
    fn drop(&mut self) {
        let mut current = self.head.take();
        while let Some(mut tmp) = current {
            current = tmp.next.take();
        }
    }
}

#[cfg(test)]
mod test {
    use super::LinkedList;

    #[test]
    fn new() {
        assert!(LinkedList::new().is_empty());
    }

    #[test]
    fn push() {
        let mut list = LinkedList::new();
        list.push(1);
        assert_eq!(list.head.as_ref().unwrap().data, 1);
        list.push(2);
        assert_eq!(list.head.as_ref().unwrap().data, 2);
    }

    #[test]
    fn pop() {
        let mut list = LinkedList::new();
        let e = list.pop();
        assert_eq!(e, None);

        list.push(1);
        let e = list.pop();
        assert_eq!(e, Some(1));

        let e = list.pop();
        assert_eq!(e, None);

        list.push(2);
        list.push(3);
        list.push(4);

        assert_eq!(list.head.as_ref().unwrap().data, 4);

        let e = list.pop();
        assert_eq!(list.head.as_ref().unwrap().data, 3);
        assert_eq!(e, Some(4));
        list.push(5);
        list.push(6);
        let e = list.pop();
        assert_eq!(list.head.as_ref().unwrap().data, 5);
        assert_eq!(e, Some(6));
    }
}
}

src/unsafe_linked_list/mod.rs

#![allow(unused)]
fn main() {
use std::alloc::{Layout, alloc, dealloc, handle_alloc_error};
use std::ptr;

// ANCHOR: element
struct Element {
    data: i32,
    next: *mut Element,
}
// ANCHOR_END: element

impl Element {
    // ANCHOR: new
    fn new(data: i32, next: *mut Element) -> *mut Element {
        let layout = Layout::new::<Element>();
        let e = unsafe { alloc(layout) as *mut Element };
        if e.is_null() {
            handle_alloc_error(layout);
        }
        // On écrit dans la mémoire fraîchement allouée, encore non initialisée.
        // L'opérateur `=` tenterait normalement de `drop` l'ancienne valeur du champ :
        // c'est sans danger ici, `i32` et `*mut Element` n'ayant pas de destructeur.
        // Pour un champ avec destructeur, il faudrait passer par `ptr::write`.
        unsafe {
            (*e).data = data;
            (*e).next = next;
        }
        e
    }
    // ANCHOR_END: new
}

//ANCHOR: drop
impl Drop for Element {
    fn drop(&mut self) {
        let elem = self as *mut Element;
        if !elem.is_null() {
            let layout = Layout::new::<Element>();
            unsafe {
                dealloc(elem as *mut u8, layout);
            }
        }
    }
}
//ANCHOR_END: drop

// ANCHOR: linked_list
pub struct LinkedList {
    head: *mut Element,
}
// ANCHOR_END: linked_list

impl LinkedList {
    // ANCHOR: ll_new
    pub fn new() -> LinkedList {
        LinkedList {
            head: ptr::null_mut(),
        }
    }
    // ANCHOR_END: ll_new

    // ANCHOR: is_empty
    fn is_empty(&self) -> bool {
        self.head.is_null()
    }
    // ANCHOR_END: is_empty

    // ANCHOR: push
    pub fn push(&mut self, data: i32) {
        let new_head = Element::new(data, self.head);
        self.head = new_head;
    }
    // ANCHOR_END: push

    // ANCHOR: pop
    pub fn pop(&mut self) -> Option<i32> {
        if self.is_empty() {
            None
        } else {
            let old_head = self.head;
            unsafe {
                self.head = (*self.head).next;
            }
            let val = unsafe { (*old_head).data };
            unsafe {
                old_head.drop_in_place();
            }
            Some(val)
        }
    }
    // ANCHOR_END: pop

    // ANCHOR: print
    pub fn print(&self) {
        let mut current_head = self.head;
        while !current_head.is_null() {
            unsafe {
                print!("{} --> ", (*current_head).data);
                current_head = (*current_head).next;
            }
        }
        println!("∅");
    }
    // ANCHOR_END: print
}

// ANCHOR: ll_drop
impl Drop for LinkedList {
    fn drop(&mut self) {
        while !self.is_empty() {
            let _ = self.pop();
        }
    }
}
// ANCHOR_END: ll_drop

#[cfg(test)]
mod tests {
    use super::LinkedList;

    #[test]
    fn new() {
        assert!(LinkedList::new().is_empty());
    }

    #[test]
    fn push() {
        let mut list = LinkedList::new();
        list.push(1);
        assert_eq!(unsafe { (*list.head).data }, 1);
        list.push(2);
        assert_eq!(unsafe { (*list.head).data }, 2);
    }

    #[test]
    fn pop() {
        let mut list = LinkedList::new();
        let e = list.pop();
        assert_eq!(e, None);

        list.push(1);
        let e = list.pop();
        assert_eq!(e, Some(1));

        let e = list.pop();
        assert_eq!(e, None);

        list.push(2);
        list.push(3);
        list.push(4);

        assert_eq!(unsafe { (*list.head).data }, 4);

        let e = list.pop();
        assert_eq!(unsafe { (*list.head).data }, 3);
        assert_eq!(e, Some(4));
        list.push(5);
        list.push(6);
        let e = list.pop();
        assert_eq!(unsafe { (*list.head).data }, 5);
        assert_eq!(e, Some(6));
    }
}
}