1 // Rust-101, Part 16: Unsafe Rust, Drop
2 // ====================================
6 use std::marker::PhantomData;
9 // A node of the list consists of the data, and two node pointers for the predecessor and successor.
15 // A node pointer is a *mutable raw pointer* to a node.
16 type NodePtr<T> = *mut Node<T>;
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> {
23 _marker: PhantomData<T>,
27 unsafe fn raw_into_box<T>(r: *mut T) -> Box<T> {
30 fn box_into_raw<T>(b: Box<T>) -> *mut T {
31 unsafe { mem::transmute(b) }
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 }
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.
51 debug_assert!(!self.first.is_null());
52 // We have to update the `next` pointer of the tail node.
55 // Make this the last node.
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>`.
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 }
70 pub struct IterMut<'a, T> where T: 'a {
72 _marker: PhantomData<&'a mut LinkedList<T>>,
75 impl<'a, T> Iterator for IterMut<'a, T> {
76 type Item = &'a mut T;
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() {
83 // Otherwise, we can convert the next pointer to a reference, get a reference to the data
84 // and update the iterator.
85 let next = unsafe { &mut *self.next };
86 let ret = &mut next.data;
93 // **Exercise 16.2**: Add a method `iter` and a type `Iter` providing iteration for shared references.
94 // Add testcases for both kinds of iterators.
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.
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) };