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