1 use super::{Item, OwnedItem};
2 use crate::time::driver::Entry;
3 
4 use std::ptr;
5 
6 /// A doubly linked stack
7 #[derive(Debug)]
8 pub(crate) struct Stack {
9     head: Option<OwnedItem>,
10 }
11 
12 impl Default for Stack {
default() -> Stack13     fn default() -> Stack {
14         Stack { head: None }
15     }
16 }
17 
18 impl Stack {
is_empty(&self) -> bool19     pub(crate) fn is_empty(&self) -> bool {
20         self.head.is_none()
21     }
22 
push(&mut self, entry: OwnedItem)23     pub(crate) fn push(&mut self, entry: OwnedItem) {
24         // Get a pointer to the entry to for the prev link
25         let ptr: *const Entry = &*entry as *const _;
26 
27         // Remove the old head entry
28         let old = self.head.take();
29 
30         unsafe {
31             // Ensure the entry is not already in a stack.
32             debug_assert!((*entry.next_stack.get()).is_none());
33             debug_assert!((*entry.prev_stack.get()).is_null());
34 
35             if let Some(ref entry) = old.as_ref() {
36                 debug_assert!({
37                     // The head is not already set to the entry
38                     ptr != &***entry as *const _
39                 });
40 
41                 // Set the previous link on the old head
42                 *entry.prev_stack.get() = ptr;
43             }
44 
45             // Set this entry's next pointer
46             *entry.next_stack.get() = old;
47         }
48 
49         // Update the head pointer
50         self.head = Some(entry);
51     }
52 
53     /// Pops an item from the stack
pop(&mut self) -> Option<OwnedItem>54     pub(crate) fn pop(&mut self) -> Option<OwnedItem> {
55         let entry = self.head.take();
56 
57         unsafe {
58             if let Some(entry) = entry.as_ref() {
59                 self.head = (*entry.next_stack.get()).take();
60 
61                 if let Some(entry) = self.head.as_ref() {
62                     *entry.prev_stack.get() = ptr::null();
63                 }
64 
65                 *entry.prev_stack.get() = ptr::null();
66             }
67         }
68 
69         entry
70     }
71 
remove(&mut self, entry: &Item)72     pub(crate) fn remove(&mut self, entry: &Item) {
73         unsafe {
74             // Ensure that the entry is in fact contained by the stack
75             debug_assert!({
76                 // This walks the full linked list even if an entry is found.
77                 let mut next = self.head.as_ref();
78                 let mut contains = false;
79 
80                 while let Some(n) = next {
81                     if entry as *const _ == &**n as *const _ {
82                         debug_assert!(!contains);
83                         contains = true;
84                     }
85 
86                     next = (*n.next_stack.get()).as_ref();
87                 }
88 
89                 contains
90             });
91 
92             // Unlink `entry` from the next node
93             let next = (*entry.next_stack.get()).take();
94 
95             if let Some(next) = next.as_ref() {
96                 (*next.prev_stack.get()) = *entry.prev_stack.get();
97             }
98 
99             // Unlink `entry` from the prev node
100 
101             if let Some(prev) = (*entry.prev_stack.get()).as_ref() {
102                 *prev.next_stack.get() = next;
103             } else {
104                 // It is the head
105                 self.head = next;
106             }
107 
108             // Unset the prev pointer
109             *entry.prev_stack.get() = ptr::null();
110         }
111     }
112 }
113