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