write part 16

diff --git a/solutions/src/list.rs b/solutions/src/list.rs
new file mode 100644 (file)
index 0000000..180627d
--- /dev/null
+++ b/solutions/src/list.rs
@@ -0,0 +1,204 @@
+
+use std::ptr;
+use std::mem;
+use std::marker::PhantomData;
+
+fn box_into_raw<T>(b: Box<T>) -> *mut T {
+    unsafe { mem::transmute(b) }
+}
+unsafe fn raw_into_box<T>(r: *mut T) -> Box<T> {
+    mem::transmute(r)
+}
+
+struct Node<T> {
+    data: T,
+    next: NodePtr<T>,
+    prev: NodePtr<T>,
+}
+type NodePtr<T> = *mut Node<T>;
+
+pub struct LinkedList<T> {
+    first: NodePtr<T>,
+    last:  NodePtr<T>,
+    _marker: PhantomData<T>,
+}
+
+impl<T> LinkedList<T> {
+    pub fn new() -> Self {
+        LinkedList { first: ptr::null_mut(), last: ptr::null_mut(), _marker: PhantomData }
+    }
+
+    pub fn push_back(&mut self, t: T) {
+        // Create the new node.
+        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());
+            self.first = new;
+        } else {
+            debug_assert!(!self.first.is_null());
+            unsafe { (*self.last).next  = new; }
+        }
+        // Make this the last node.
+        self.last = new;
+    }
+
+    pub fn pop_back(&mut self) -> Option<T> {
+        if self.last.is_null() {
+            None
+        } else {
+            let last = self.last;
+            let new_last = unsafe { (*self.last).prev };
+            self.last = new_last;
+            if new_last.is_null() {
+                // The list is now empty.
+                self.first = new_last;
+            }
+            let last = unsafe { raw_into_box(last) } ;
+            Some(last.data)
+        }
+    }
+
+    pub fn push_front(&mut self, t: T) {
+        // Create the new node.
+        let new = Box::new( Node { data: t, next: self.first, prev: ptr::null_mut() } );
+        let new = box_into_raw(new);
+        // Update other points to this node.
+        if self.first.is_null() {
+            debug_assert!(self.last.is_null());
+            self.last = new;
+        }
+        else {
+            debug_assert!(!self.last.is_null());
+            unsafe { (*self.first).prev = new; }
+        }
+        // Make this the first node.
+        self.first = new;
+    }
+
+    pub fn pop_front(&mut self) -> Option<T> {
+        if self.first.is_null() {
+            None
+        } else {
+            let first = self.first;
+            let new_first = unsafe { (*self.first).next };
+            self.first = new_first;
+            if new_first.is_null() {
+                // The list is now empty.
+                self.last = new_first;
+            }
+            let first = unsafe { raw_into_box(first) } ;
+            Some(first.data)
+        }
+    }
+
+    pub fn for_each<F: FnMut(&mut T)>(&mut self, mut f: F) {
+        let mut cur_ptr = self.first;
+        while !cur_ptr.is_null() {
+            // Iterate over every node, and call `f`.
+            f(unsafe{ &mut (*cur_ptr).data });
+            cur_ptr = unsafe{ (*cur_ptr).next };
+        }
+    }
+
+    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 T>,
+}
+
+impl<'a, T> Iterator for IterMut<'a, T> {
+    type Item = &'a mut T;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        if self.next.is_null() {
+           None
+        } else {
+            let ret = unsafe{ &mut (*self.next).data };
+            self.next = unsafe { (*self.next).next };
+            Some(ret)
+        }
+    }
+}
+
+impl<T> Drop for LinkedList<T> {
+    fn drop(&mut self) {
+        let mut cur_ptr = self.first;
+        while !cur_ptr.is_null() {
+            let cur = unsafe { raw_into_box(cur_ptr) };
+            cur_ptr = cur.next;
+            drop(cur);
+        }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use std::rc::Rc;
+    use std::cell::Cell;
+    use super::LinkedList;
+
+    #[test]
+    fn test_pop_back() {
+        let mut l: LinkedList<i32> = LinkedList::new();
+        for i in 0..3 {
+            l.push_front(-i);
+            l.push_back(i);
+        }
+
+        assert_eq!(l.pop_back(), Some(2));
+        assert_eq!(l.pop_back(), Some(1));
+        assert_eq!(l.pop_back(), Some(0));
+        assert_eq!(l.pop_back(), Some(-0));
+        assert_eq!(l.pop_back(), Some(-1));
+        assert_eq!(l.pop_back(), Some(-2));
+        assert_eq!(l.pop_back(), None);
+        assert_eq!(l.pop_back(), None);
+    }
+
+    #[test]
+    fn test_pop_front() {
+        let mut l: LinkedList<i32> = LinkedList::new();
+        for i in 0..3 {
+            l.push_front(-i);
+            l.push_back(i);
+        }
+
+        assert_eq!(l.pop_front(), Some(-2));
+        assert_eq!(l.pop_front(), Some(-1));
+        assert_eq!(l.pop_front(), Some(-0));
+        assert_eq!(l.pop_front(), Some(0));
+        assert_eq!(l.pop_front(), Some(1));
+        assert_eq!(l.pop_front(), Some(2));
+        assert_eq!(l.pop_front(), None);
+        assert_eq!(l.pop_front(), None);
+    }
+
+    #[derive(Clone)]
+    struct DropChecker {
+        count: Rc<Cell<usize>>,
+    }
+    impl Drop for DropChecker {
+        fn drop(&mut self) {
+            self.count.set(self.count.get() + 1);
+        }
+    }
+
+    #[test]
+    fn test_drop() {
+        let count = DropChecker { count: Rc::new(Cell::new(0)) };
+        {
+            let mut l = LinkedList::new();
+            for _ in 0..10 {
+                l.push_back(count.clone());
+                l.push_front(count.clone());
+            }
+        }
+        assert_eq!(count.count.get(), 20);
+    }
+}

diff --git a/solutions/src/main.rs b/solutions/src/main.rs
index 0242f495bb928968a74f193b0859d98324d3eff4..daafe089bd72eba6acdce127fa04c456155fd1a8 100644 (file)
--- a/solutions/src/main.rs
+++ b/solutions/src/main.rs
@@ -8,8 +8,9 @@ extern crate docopt;
 pub mod bigint;
 pub mod vec;
 pub mod rgrep;
 pub mod bigint;
 pub mod vec;
 pub mod rgrep;

-pub mod counter;

 pub mod callbacks;
 pub mod callbacks;

+pub mod counter;
+pub mod list;

 
 pub fn main() {
     rgrep::main();
 
 pub fn main() {
     rgrep::main();

diff --git a/src/main.rs b/src/main.rs
index 1317856fb397a8224da1a3bd0636bc57b140340c..19abe4eacfd1ccef31fff28b0979698f9cff1a98 100644 (file)
--- a/src/main.rs
+++ b/src/main.rs
@@ -104,6 +104,7 @@ mod part12;
 mod part13;
 mod part14;
 mod part15;
 mod part13;
 mod part14;
 mod part15;

+mod part16;

 
 // To actually run the code of some part (after filling in the blanks, if necessary), simply edit the `main`
 // function.
 
 // To actually run the code of some part (after filling in the blanks, if necessary), simply edit the `main`
 // function.

diff --git a/src/part12.rs b/src/part12.rs
index 40d9ad52a0a1f7f0648f64239c2f8adb65bada10..d5b7ce32108cb26bafbe8514c458dcb5bc956a35 100644 (file)
--- a/src/part12.rs
+++ b/src/part12.rs
@@ -9,6 +9,7 @@ use std::cell::{Cell, RefCell};
 //@ (There's not even an automatic derivation happening for the cases where it would be possible.)
 //@ This restriction propagates up to `Callbacks` itself. What could we do about this?
 
 //@ (There's not even an automatic derivation happening for the cases where it would be possible.)
 //@ This restriction propagates up to `Callbacks` itself. What could we do about this?
 

+//@ ## `Rc`

 //@ The solution is to find some way of cloning `Callbacks` without cloning the environments. This can be achieved with
 //@ `Rc<T>`, a *reference-counted* pointer. This is is another example of a smart pointer. You can `clone` an `Rc` as often
 //@ as you want, that doesn't affect the data it contains. It only creates more references to the same data. Once all the
 //@ The solution is to find some way of cloning `Callbacks` without cloning the environments. This can be achieved with
 //@ `Rc<T>`, a *reference-counted* pointer. This is is another example of a smart pointer. You can `clone` an `Rc` as often
 //@ as you want, that doesn't affect the data it contains. It only creates more references to the same data. Once all the

diff --git a/src/part15.rs b/src/part15.rs
index 9ae5aaf93dd62c9508bc5119a33381490a7c3d19..ef2564a46c4d98c34a0cf845d9dc00f6305b2e20 100644 (file)
--- a/src/part15.rs
+++ b/src/part15.rs
@@ -10,6 +10,7 @@ use std::thread;
 //@ there are no data races. In Rust, shared-memory concurrency is obtained through *interior mutability*,
 //@ which we already discussed in a single-threaded context in part 12.
 //@ 
 //@ there are no data races. In Rust, shared-memory concurrency is obtained through *interior mutability*,
 //@ which we already discussed in a single-threaded context in part 12.
 //@ 

+//@ ## `Mutex`

 //@ The most basic type for interior mutability that supports concurrency is [`Mutex<T>`](http://doc.rust-lang.org/stable/std/sync/struct.Mutex.html).
 //@ This type implements *critical sections* (or *locks*), but in a data-driven way: One has to specify
 //@ the type of the data that's protected by the mutex, and Rust ensures that the data is *only* accessed
 //@ The most basic type for interior mutability that supports concurrency is [`Mutex<T>`](http://doc.rust-lang.org/stable/std/sync/struct.Mutex.html).
 //@ This type implements *critical sections* (or *locks*), but in a data-driven way: One has to specify
 //@ the type of the data that's protected by the mutex, and Rust ensures that the data is *only* accessed


@@ -111,7 +112,7 @@ pub fn main() {
 
 // **Exercise 15.3**:  Change the code above to use `RwLock`, such that multiple calls to `get` can be executed at the same time.
 
 
 // **Exercise 15.3**:  Change the code above to use `RwLock`, such that multiple calls to `get` can be executed at the same time.
 

-//@ ## Sync
+//@ ## `Sync`

 //@ Clearly, if we had used `RefCell` rather than `Mutex`, the code above could not work: `RefCell` is not prepared for
 //@ multiple threads trying to access the data at the same time. How does Rust make sure that we don't accidentally use
 //@ `RefCell` across multiple threads?
 //@ Clearly, if we had used `RefCell` rather than `Mutex`, the code above could not work: `RefCell` is not prepared for
 //@ multiple threads trying to access the data at the same time. How does Rust make sure that we don't accidentally use
 //@ `RefCell` across multiple threads?

diff --git a/src/part16.rs b/src/part16.rs
new file mode 100644 (file)
index 0000000..a613430
--- /dev/null
+++ b/src/part16.rs
@@ -0,0 +1,196 @@
+// Rust-101, Part 16: Unsafe, Drop (WIP)
+// ===============================
+
+use std::ptr;
+use std::mem;
+use std::marker::PhantomData;
+
+//@ As we saw, the rules Rust imposes can get us pretty far: A surprising amount of programming patterns
+//@ can be written within safe Rust, and, more importantly, library code like iterators or threads can make
+//@ use of the type system to ensure some level of correctness beyond basic memory safety.
+//@ 
+//@ However, there will still be programs that one cannot write in accordance with the borrow checker. And there
+//@ will be cases where it may be possible to satisfy the compiler, but only at the cost of some run-time overhead,
+//@ as we saw with `RefCell` - overhead which may not be acceptable. In such a situation, it is possible to
+//@ use *unsafe* Rust: That's a part of the language that is *known* to open the gate to invalid pointer access
+//@ and all other sorts of memory safety. It is typically disabled, guarded by the keyword `unsafe`. Of course,
+//@ `unsafe` also means "Here Be Dragons": You are on your own now. Types like `Rc` and `Vec` are implemented
+//@ `using unsafe Rust.
+//@ 
+//@ ## Unsafe Code
+//@ As an example, let us write a doubly-linked list. Clearly, such a data-structure involves aliasing and mutation:
+//@ Every node in the list is pointed to by its left and right neighbor, but still we will want to modify the nodes
+//@ (either to change the value at that place, or to insert new nodes). We could now try some clever combination of
+//@ `Rc` and `RefCell`, but this would end up being quite annoying - and it would incur some over-head. For a low-level
+//@ data-structure like a doubly-linked list, it makes sense to implement an efficient version *once*, that is unsafe
+//@ internally, but taht can be used without any risk by safe client code.
+
+//@ As usually, we start by defining the types. Everything is parameterized by the type `T` of the data stored in the list.
+// 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.
+//@ Raw pointers (`*mut T` and `*const T`) are the Rust equivalent of pointers in C. Unlike borrows, they do not come with
+//@ any guarantees: Raw pointers can be null, or they can point to garbage. They don't have a lifetime.
+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`.
+//@ The type `PhantomData<T>` does not actually store anything in memory - it has size zero. However, logically,
+//@ Rust will consider a `T` to be present. In this case, Rust knows that data of type `T` may be dropped
+//@ whenever a `LinkedList<T>` is dropped. The checks involving destructors are pretty subtle, so it's always
+//@ a good idea to provide such extra information. In safe Rust, this can all be done automatically, but here,
+//@ we just have a `*mut Node<T>`, which Rust does not consider as actually owning the data it points to.
+pub struct LinkedList<T> {
+    first: NodePtr<T>,
+    last:  NodePtr<T>,
+    _marker: PhantomData<T>,
+}
+
+//@ Before we get to the actual linked-list methods, we write two short helper functions converting between
+//@ mutable raw pointers, and owned pointers (aka `Box`). Both employ `mem::transmute`, which is Rust's
+//@ `reinterpret_cast`: It can convert anything to anything, by just re-interpreting the bytes. Clearly,
+//@ that's an unsafe operation.
+
+//@ We declare `raw_into_box` to be an `unsafe` function, telling Rust that calling this function is not generally safe.
+//@ The caller will have to ensure that `r` is a valid pointer, and that nobody else has a pointer to this data.
+unsafe fn raw_into_box<T>(r: *mut T) -> Box<T> {
+    mem::transmute(r)
+}
+//@ The case is slightly different for `box_into_raw`: Converting a `Box` to a raw pointer is always safe. I just drops some
+//@ information. Hence we keep the function itself safe, and use an *unsafe block* within the function. This is an (unchecked)
+//@ promise to the Rust compiler, saying that even though the code inside that block *could* go wrong, we actually know that
+//@ it will not.
+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.
+        //@ Calling `box_into_raw` gives up ownership of the box, which is crucial: We don't want the
+        //@ memory that it points to to be deallocated!
+        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.
+            self.first = new;                                       /*@*/
+        } else {
+            debug_assert!(!self.first.is_null());
+            // We have to update the `next` pointer of the tail node.
+            //@ Since Rust does not know that a raw pointer actually to anything, dereferencing such a pointer is
+            //@ an unsafe operation. So this unsafe block promises that the pointer will actually be valid.
+            unsafe { (*self.last).next = new; }                     /*@*/
+        }
+        // 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.
+    //@ This function just creates an instance of `IterMut`, the iterator type which does the actual work.
+    pub fn iter_mut(&self) -> IterMut<T> {
+        IterMut { next: self.first, _marker: PhantomData  }
+    }
+}
+
+//@ What does the iterator need to store? Strictly speaking, all it needs is the pointer to the next node
+//@ that it is going to visit. However, how do we make sure that this pointer remains valid? We have to
+//@ get this right ourselves, as we left the safe realms of borrowing and ownership. Remember that the
+//@ key ingredient for iterator safety was to tie the lifetime of the iterator to the lifetime of the
+//@ borrow used for `iter_mut`. We will thus give `IterMut` two parameters: A type parameter specifying
+//@ the type of the data, and a lifetime parameter specifying for how long the list was borrowed to the
+//@ iterator.
+//@ 
+//@ For Rust to accept the type, we have to add two more annotations. First of all, we have to ensure that
+//@ the data in the list lives at least as long as the iterator: If you drop the `T: 'a`, Rust will tell
+//@ you to add it back. And secondly, Rust will complain if `'a` is not actually used in the struct.
+//@ It doesn't know what it is supposed to do with that lifetime. So we use `PhantomData` again to tell
+//@ it that in terms of ownership, this type actually (mutably) borrows a linked list. This has no
+//@ operational effect, but it means that Rust can deduce the intent we had when adding that
+//@ seemingly useless lifetime parameter.
+pub struct IterMut<'a, T> where T: 'a {
+    next: NodePtr<T>,
+    _marker: PhantomData<&'a mut LinkedList<T>>,
+}
+
+//@ When implementing `Iterator` for `IterMut`, the fact that we have the lifetime `'a` around immediately
+//@ pays of: We would not even be able to write down the type `Item` without that lifetime.
+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)
+        }
+    }
+}
+
+//@ In `next` above, we made crucial use of the assumption that `self.next` is either null or a valid pointer.
+//@ This only works because if someone tries to delete elements from a list during iteration, we know that the borrow checker
+//@ will catch them: If they call `next`, the lifetime `'a` we artificially added to the iterator has to still be
+//@ active, which means the mutable borrow passed to `iter_mut` is still active, which means nobody can delete
+//@ anything from the list. In other words, we make use of the expressive type system of Rust, decorating
+//@ our own unsafe implementation with just enough information so that Rust can check *uses* of the linked-list.
+//@ If the type system were weaker, we could not write a linked-list like the above with a safe interface!
+
+// **Exercise 16.2**: Add a method `iter` and a type `Iter` providing iteration for shared borrows.
+// Add testcases for both kinds of iterators.
+
+// ## `Drop`
+//@ The linked list we wrote is already working quite nicely, but there is one problem: When the list is removed,
+//@ nobody bothers to deallocate the remaining nodes. Even worse, if `T` itself has a destructor that needs to
+//@ clean up, it is not called for the element remaining in the list. We need to take care of that ourselves.
+//@ 
+//@ In Rust, adding a destructor for a type is done by implementing the `Drop` trait. This is a very special trait.
+//@ It can only be implemented for *nominal types*, i.e., you cannot implement `Drop` for `&mut T`. You also cannot
+//@ restrict the type and lifetime parameters further - the `Drop` implementation has to apply to *all* instances
+//@ of `LinkedList`.
+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.
+            //@ We call `drop` explicitly here just for documentation purposes.
+            let cur = unsafe { raw_into_box(cur_ptr) };
+            cur_ptr = cur.next;
+            drop(cur);
+        }
+    }
+}
+
+//@ ## The End
+//@ Congratulations! You complete Rust-101. This was the last example of the last part. I hope you enjoyed it.
+//@ If you have feedback, please head to the [Rust-101](https://www.ralfj.de/projects/rust-101/) website
+//@ and let me know how you liked it. The entire course is open-source (under CC-BY-SA 4.0), and contributions are welcome!
+//@ 
+//@ The [index](main.html) contains some more links to additional resources you may find useful. With that, there's
+//@ only one thing left to say: Happy Rust Hacking!
+
+//@ [index](main.html) | [previous](part15.html)

diff --git a/workspace/src/main.rs b/workspace/src/main.rs
index a86a65a1067836efc5907c463e53975abc46f934..77632d9427cf924f55a82580a5a82e78a541208f 100644 (file)
--- a/workspace/src/main.rs
+++ b/workspace/src/main.rs
@@ -17,6 +17,7 @@ mod part12;
 mod part13;
 mod part14;
 mod part15;
 mod part13;
 mod part14;
 mod part15;

+mod part16;

 
 // This decides which part is actually run.
 fn main() {
 
 // This decides which part is actually run.
 fn main() {

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);
+        }
+    }
+}
+
+