write part 16

[rust-101.git] / workspace / src / part16.rs

diff --git a/workspace/src/part16.rs b/workspace/src/part16.rs
new file mode 100644 (file)
index 0000000..a804f8e
--- /dev/null
+++ b/workspace/src/part16.rs
@@ -0,0 +1,113 @@
+// Rust-101, Part 16: Unsafe, Drop (WIP)
+// ===============================
+
+use std::ptr;
+use std::mem;
+use std::marker::PhantomData;
+
+
+// A node of the list consists of the data, and two node pointers for the predecessor and successor.
+struct Node<T> {
+    next: NodePtr<T>,
+    prev: NodePtr<T>,
+    data: T,
+}
+// A node pointer is a *mutable raw point* to a node.
+type NodePtr<T> = *mut Node<T>;
+
+// The linked list itself stores pointers to the first and the last node. In addition, we tell Rust that this type
+// will own data of type `T`.
+pub struct LinkedList<T> {
+    first: NodePtr<T>,
+    last:  NodePtr<T>,
+    _marker: PhantomData<T>,
+}
+
+
+unsafe fn raw_into_box<T>(r: *mut T) -> Box<T> {
+    mem::transmute(r)
+}
+fn box_into_raw<T>(b: Box<T>) -> *mut T {
+    unsafe { mem::transmute(b) }
+}
+
+impl<T> LinkedList<T> {
+    // A new linked list just contains null pointers. `PhantomData` is how we construct any `PhantomData<T>`.
+    pub fn new() -> Self {
+        LinkedList { first: ptr::null_mut(), last: ptr::null_mut(), _marker: PhantomData }
+    }
+
+    // Add a new node to the end of the list.
+    pub fn push_back(&mut self, t: T) {
+        // Create the new node, and make it a raw pointer.
+        let new = Box::new( Node { data: t, next: ptr::null_mut(), prev: self.last } );
+        let new = box_into_raw(new);
+        // Update other points to this node.
+        if self.last.is_null() {
+            debug_assert!(self.first.is_null());
+            // The list is currently empty, so we have to update the head pointer.
+            unimplemented!()
+        } else {
+            debug_assert!(!self.first.is_null());
+            // We have to update the `next` pointer of the tail node.
+            unimplemented!()
+        }
+        // Make this the last node.
+        self.last = new;
+    }
+
+    // **Exercise 16.1**: Add some more operations to `LinkedList`: `pop_back`, `push_front` and `pop_front`.
+    // Add testcases for `push_back` and all of your functions. The `pop` functions should take `&mut self`
+    // and return `Option<T>`.
+
+    // Of course, we will also want to provide an iterator.
+    pub fn iter_mut(&self) -> IterMut<T> {
+        IterMut { next: self.first, _marker: PhantomData  }
+    }
+}
+
+pub struct IterMut<'a, T> where T: 'a {
+    next: NodePtr<T>,
+    _marker: PhantomData<&'a mut LinkedList<T>>,
+}
+
+impl<'a, T> Iterator for IterMut<'a, T> {
+    type Item = &'a mut T;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        // The actual iteration is straight-forward: Once we reached a null pointer, we are done.
+        if self.next.is_null() {
+           None
+        } else {
+            // Otherwise, we can convert the next pointer to a borrow, get a borrow to the data
+            // and update the iterator.
+            let next = unsafe { &mut *self.next };
+            let ret = &mut next.data;
+            self.next = next.next;
+            Some(ret)
+        }
+    }
+}
+
+
+// **Exercise 16.2**: Add a method `iter` and a type `Iter` providing iteration for shared borrows.
+// Add testcases for both kinds of iterators.
+
+// ## `Drop`
+impl<T> Drop for LinkedList<T> {
+    // The destructor itself is a method which takes `self` in mutably borrowed form. It cannot own `self`, because then
+    // the destructor of `self` would be called at the end pf the function, resulting in endless recursion...
+    fn drop(&mut self) {
+        let mut cur_ptr = self.first;
+        while !cur_ptr.is_null() {
+            // In the destructor, we just iterate over the entire list, successively obtaining ownership
+            // (`Box`) of every node. When the box is dropped, it will call the destructor on `data` if
+            // necessary, and subsequently free the node on the heap.
+            let cur = unsafe { raw_into_box(cur_ptr) };
+            cur_ptr = cur.next;
+            drop(cur);
+        }
+    }
+}
+
+