workspace/src/part16.rs

   1 // Rust-101, Part 16: Unsafe, Drop (WIP)
   2 // ===============================
   3
   4 use std::ptr;
   5 use std::mem;
   6 use std::marker::PhantomData;
   7
   8
   9 // A node of the list consists of the data, and two node pointers for the predecessor and successor.
  10 struct Node<T> {
  11     next: NodePtr<T>,
  12     prev: NodePtr<T>,
  13     data: T,
  14 }
  15 // A node pointer is a *mutable raw point* to a node.
  16 type NodePtr<T> = *mut Node<T>;
  17
  18 // The linked list itself stores pointers to the first and the last node. In addition, we tell Rust that this type
  19 // will own data of type `T`.
  20 pub struct LinkedList<T> {
  21     first: NodePtr<T>,
  22     last:  NodePtr<T>,
  23     _marker: PhantomData<T>,
  24 }
  25
  26
  27 unsafe fn raw_into_box<T>(r: *mut T) -> Box<T> {
  28     mem::transmute(r)
  29 }
  30 fn box_into_raw<T>(b: Box<T>) -> *mut T {
  31     unsafe { mem::transmute(b) }
  32 }
  33
  34 impl<T> LinkedList<T> {
  35     // A new linked list just contains null pointers. `PhantomData` is how we construct any `PhantomData<T>`.
  36     pub fn new() -> Self {
  37         LinkedList { first: ptr::null_mut(), last: ptr::null_mut(), _marker: PhantomData }
  38     }
  39
  40     // Add a new node to the end of the list.
  41     pub fn push_back(&mut self, t: T) {
  42         // Create the new node, and make it a raw pointer.
  43         let new = Box::new( Node { data: t, next: ptr::null_mut(), prev: self.last } );
  44         let new = box_into_raw(new);
  45         // Update other points to this node.
  46         if self.last.is_null() {
  47             debug_assert!(self.first.is_null());
  48             // The list is currently empty, so we have to update the head pointer.
  49             unimplemented!()
  50         } else {
  51             debug_assert!(!self.first.is_null());
  52             // We have to update the `next` pointer of the tail node.
  53             unimplemented!()
  54         }
  55         // Make this the last node.
  56         self.last = new;
  57     }
  58
  59     // **Exercise 16.1**: Add some more operations to `LinkedList`: `pop_back`, `push_front` and `pop_front`.
  60     // Add testcases for `push_back` and all of your functions. The `pop` functions should take `&mut self`
  61     // and return `Option<T>`.
  62
  63     // Of course, we will also want to provide an iterator.
  64     pub fn iter_mut(&self) -> IterMut<T> {
  65         IterMut { next: self.first, _marker: PhantomData  }
  66     }
  67 }
  68
  69 pub struct IterMut<'a, T> where T: 'a {
  70     next: NodePtr<T>,
  71     _marker: PhantomData<&'a mut LinkedList<T>>,
  72 }
  73
  74 impl<'a, T> Iterator for IterMut<'a, T> {
  75     type Item = &'a mut T;
  76
  77     fn next(&mut self) -> Option<Self::Item> {
  78         // The actual iteration is straight-forward: Once we reached a null pointer, we are done.
  79         if self.next.is_null() {
  80            None
  81         } else {
  82             // Otherwise, we can convert the next pointer to a borrow, get a borrow to the data
  83             // and update the iterator.
  84             let next = unsafe { &mut *self.next };
  85             let ret = &mut next.data;
  86             self.next = next.next;
  87             Some(ret)
  88         }
  89     }
  90 }
  91
  92
  93 // **Exercise 16.2**: Add a method `iter` and a type `Iter` providing iteration for shared borrows.
  94 // Add testcases for both kinds of iterators.
  95
  96 // ## `Drop`
  97 impl<T> Drop for LinkedList<T> {
  98     // The destructor itself is a method which takes `self` in mutably borrowed form. It cannot own `self`, because then
  99     // the destructor of `self` would be called at the end pf the function, resulting in endless recursion...
 100     fn drop(&mut self) {
 101         let mut cur_ptr = self.first;
 102         while !cur_ptr.is_null() {
 103             // In the destructor, we just iterate over the entire list, successively obtaining ownership
 104             // (`Box`) of every node. When the box is dropped, it will call the destructor on `data` if
 105             // necessary, and subsequently free the node on the heap.
 106             let cur = unsafe { raw_into_box(cur_ptr) };
 107             cur_ptr = cur.next;
 108             drop(cur);
 109         }
 110     }
 111 }
 112
 113