base/array/
linked_list.rs

1/// An intrusive linked list
2///
3/// A clean room implementation of the one used in CS140e 2018 Winter
4///
5/// Thanks Sergio Benitez for his excellent work,
6/// See [CS140e](https://cs140e.sergio.bz/) for more information
7#[derive(Clone, Copy)]
8pub struct LinkedList {
9   pub head: *mut usize,
10}
11
12unsafe impl Send for LinkedList{}
13
14impl LinkedList {
15   /// Creates a new [`LinkedList`](LinkedList).
16   pub const fn new() -> LinkedList {
17      return LinkedList{
18         head: ptr::null_mut(),
19      };
20   }
21
22   /// Return `true` if the list is empty.
23   pub fn empty(&self) -> bool {
24      return self.head.is_null();
25   }
26
27   /// Push `item` to the front of the list.
28   ///
29   /// ## Arguments
30   ///
31   /// * `item` - A [`*mut usize`](prim@usize) item list.
32   ///
33   /// ## Safety
34   ///
35   /// Unsafe because we are working with raw pointers.
36   pub unsafe fn push(&mut self, item: *mut usize) {
37      *item = self.head as usize;
38      self.head = item;
39   }
40
41   /// Try to remove the first item from the list.
42   pub fn pop(&mut self) -> Option<*mut usize> {
43      return match self.empty() {
44         true => None,
45         false => {
46            let item: *mut usize = self.head;
47            self.head = unsafe{ *item as *mut usize };
48            Some(item)
49         }
50      };
51   }
52
53   /// Get an iterator over the items in the list.
54   pub fn iterator(&self) -> Iter {
55      return Iter{
56         current: self.head,
57         list: PhantomData,
58      }
59   }
60
61   /// Get a mutable iterator over the items in the list.
62   pub fn iterator_mut(&mut self) -> IterMut {
63      return IterMut{
64         previous: &mut self.head as *mut *mut usize as *mut usize,
65         current: self.head,
66         list: PhantomData,
67      };
68   }
69}
70
71impl Debug for LinkedList {
72   fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
73      f.debug_list().entries(self.iterator()).finish()
74   }
75}
76
77/// A mutable list node in [`LinkedList`](crate::alloc::list::LinkedList)
78pub struct ListNode {
79   pub previous: *mut usize,
80   pub current: *mut usize,
81}
82
83impl ListNode {
84   pub fn pop(self) -> *mut usize {
85      // Skip the current item.
86      unsafe{
87         *(self.previous) = *(self.current);
88      }
89
90      return self.current;
91   }
92
93   pub fn value(&self) -> *mut usize {
94      return self.current;
95   }
96}
97
98pub struct Iter<'a> {
99   pub current: *mut usize,
100   list: PhantomData<&'a LinkedList>,
101}
102
103impl<'a> Iterator for Iter<'a> {
104   type Item = *mut usize;
105
106   fn next(&mut self) -> Option<Self::Item> {
107      return if self.current.is_null() {
108         None
109      } else {
110         let item: *mut usize = self.current;
111         let next: *mut usize = unsafe{ *item as *mut usize };
112         self.current = next;
113
114         Some(item)
115      }
116   }
117}
118
119/// A mutable interior over the linked list.
120pub struct IterMut<'a> {
121   list: PhantomData<&'a mut LinkedList>,
122   pub current: *mut usize,
123   pub previous: *mut usize,
124}
125
126impl<'a> Iterator for IterMut<'a> {
127   type Item = ListNode;
128
129   fn next(&mut self) -> Option<Self::Item> {
130      return if self.current.is_null() {
131         None
132      } else {
133         let result = ListNode{
134            current: self.current,
135            previous: self.previous,
136         };
137
138         self.previous = self.current;
139         self.current = unsafe{ *self.current as *mut usize };
140
141         Some(result)
142      };
143   }
144}
145
146// IMPORTS //
147
148use {
149   core::{
150      fmt::{Debug, Formatter},
151      marker::PhantomData,
152      ptr,
153   },
154};
base/array/linked_list.rs

base/array/
linked_list.rs
