broker_tokio/time/driver/
stack.rs

1use crate::time::driver::Entry;
2use crate::time::wheel;
3
4use std::ptr;
5use std::sync::Arc;
6
7/// A doubly linked stack
8#[derive(Debug)]
9pub(crate) struct Stack {
10    head: Option<Arc<Entry>>,
11}
12
13impl Default for Stack {
14    fn default() -> Stack {
15        Stack { head: None }
16    }
17}
18
19impl wheel::Stack for Stack {
20    type Owned = Arc<Entry>;
21    type Borrowed = Entry;
22    type Store = ();
23
24    fn is_empty(&self) -> bool {
25        self.head.is_none()
26    }
27
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
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
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
118    fn when(item: &Entry, _: &()) -> u64 {
119        item.when_internal().expect("invalid internal state")
120    }
121}
broker_tokio/time/driver/stack.rs

broker_tokio/time/driver/
stack.rs
