Merge pull request #5 from r0e/master
[rust-101.git] / workspace / src / part16.rs
1 // Rust-101, Part 16: Unsafe Rust, Drop
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 pointer* 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     // This function adds 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 pointers 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     // Next, we are going to provide an iterator.
64     pub fn iter_mut(&mut self) -> IterMut<T> {
65         IterMut { next: self.first, _marker: PhantomData  }
66     }
67 }
68
69
70 pub struct IterMut<'a, T> where T: 'a {
71     next: NodePtr<T>,
72     _marker: PhantomData<&'a mut LinkedList<T>>,
73 }
74
75 impl<'a, T> Iterator for IterMut<'a, T> {
76     type Item = &'a mut T;
77
78     fn next(&mut self) -> Option<Self::Item> {
79         // The actual iteration is straight-forward: Once we reached a null pointer, we are done.
80         if self.next.is_null() {
81             None
82         } else {
83             // Otherwise, we can convert the next pointer to a borrow, get a borrow to the data
84             // and update the iterator.
85             let next = unsafe { &mut *self.next };
86             let ret = &mut next.data;
87             unimplemented!()
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
98 impl<T> Drop for LinkedList<T> {
99     // The destructor itself is a method which takes `self` in mutably borrowed form. It cannot own `self`, because then
100     // the destructor of `self` would be called at the end of the function, resulting in endless recursion...
101     fn drop(&mut self) {
102         let mut cur_ptr = self.first;
103         while !cur_ptr.is_null() {
104             // In the destructor, we just iterate over the entire list, successively obtaining ownership
105             // (`Box`) of every node. When the box is dropped, it will call the destructor on `data` if
106             // necessary, and subsequently free the node on the heap.
107             let cur = unsafe { raw_into_box(cur_ptr) };
108             cur_ptr = cur.next;
109             drop(cur);
110         }
111     }
112 }
113
114 // ## The End
115