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