dope 0.12.0

The manifold runtime
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

use std::cell::Cell;
use std::marker::PhantomData;
use std::pin::Pin;
use std::ptr::NonNull;
use std::time::Instant;

use dope_core::driver::ready::CompletionWaker;
use o3::collections::intrusive::{AvlNode, AvlTree};

#[repr(C)]
pub struct Waiter<'d> {
    node: AvlNode,
    wake: Cell<Option<CompletionWaker<'d>>>,
    deadline: Cell<Instant>,
    queued: Cell<bool>,
    _driver: PhantomData<fn(&'d ()) -> &'d ()>,
}

impl Waiter<'_> {
    pub fn new() -> Self {
        Self {
            node: AvlNode::new(),
            wake: Cell::new(None),
            deadline: Cell::new(Instant::now()),
            queued: Cell::new(false),
            _driver: PhantomData,
        }
    }

    fn node(self: Pin<&Self>) -> Pin<&AvlNode> {
        unsafe { self.map_unchecked(|waiter| &waiter.node) }
    }
}

impl Default for Waiter<'_> {
    fn default() -> Self {
        Self::new()
    }
}

pub(crate) struct StarvedTree<'d> {
    tree: AvlTree,
    _marker: PhantomData<&'d ()>,
}

impl<'d> StarvedTree<'d> {
    pub(crate) fn new() -> Self {
        Self {
            tree: AvlTree::new(),
            _marker: PhantomData,
        }
    }

    pub(crate) fn register(
        &self,
        waiter: Pin<&Waiter<'d>>,
        deadline: Instant,
        wake: CompletionWaker<'d>,
    ) {
        let node = waiter.node();
        let waiter = waiter.get_ref();
        waiter.wake.set(Some(wake));
        if waiter.queued.get() {
            return;
        }
        waiter.deadline.set(deadline);
        waiter.queued.set(true);
        unsafe { self.tree.insert(node, Self::before) };
    }

    pub(crate) fn unregister(&self, waiter: Pin<&Waiter<'d>>) {
        let waiter = waiter.get_ref();
        if waiter.queued.get() {
            unsafe { self.tree.remove(NonNull::from(&waiter.node)) };
            waiter.queued.set(false);
        }
        waiter.wake.set(None);
    }

    pub(crate) fn wake_min(&self) {
        let Some(min) = self.tree.first() else {
            return;
        };
        let waiter = unsafe { Self::waiter(min) };
        unsafe { self.tree.remove(min) };
        waiter.queued.set(false);
        if let Some(wake) = waiter.wake.get() {
            wake.wake();
        }
    }

    pub(crate) fn expire(&self, now: Instant) {
        while let Some(min) = self.tree.first() {
            let waiter = unsafe { Self::waiter(min) };
            if waiter.deadline.get() > now {
                break;
            }
            unsafe { self.tree.remove(min) };
            waiter.queued.set(false);
            if let Some(wake) = waiter.wake.get() {
                wake.wake();
            }
        }
    }

    pub(crate) fn min_deadline(&self) -> Option<Instant> {
        self.tree
            .first()
            .map(|node| unsafe { Self::waiter(node) }.deadline.get())
    }

    fn before(a: NonNull<AvlNode>, b: NonNull<AvlNode>) -> bool {
        let (first, second) = unsafe { (Self::waiter(a), Self::waiter(b)) };
        (first.deadline.get(), a.as_ptr() as usize) < (second.deadline.get(), b.as_ptr() as usize)
    }

    /// # Safety
    /// `node` is the leading intrusive AVL `AvlNode` field of a live `Waiter`.
    unsafe fn waiter<'a>(node: NonNull<AvlNode>) -> &'a Waiter<'d> {
        unsafe { node.cast().as_ref() }
    }
}