dynode 0.0.0

A utility library for creating node-based structures that can hold dynamically sized values
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
123
124
125
126
127
128
129
130

use core::mem;

use dynode::NodePtr;

#[cfg_attr(test, test)]
fn main() {
    let mut queue = LinkedQueue::<u8>::new();

    queue.queue(1);
    println!("{:?}", queue.dequeue());
    queue.queue(2);
    queue.queue(3);
    println!("{:?}", queue.dequeue());
    queue.queue(4);
    queue.queue(5);
    println!("{:?}", queue.dequeue());
    println!("{:?}", queue.dequeue());
    println!("{:?}", queue.dequeue());

    assert!(queue.is_empty());

    queue.queue(255);
}

type Node<T> = NodePtr<Header<T>, T>;
struct Header<T> {
    next: Option<Node<T>>,
}

struct LinkedQueue<T> {
    ends: Option<(Node<T>, Node<T>)>,
}

impl<T> LinkedQueue<T> {
    const fn new() -> Self {
        Self { ends: None }
    }

    const fn is_empty(&self) -> bool {
        self.ends.is_none()
    }

    fn queue(&mut self, value: T) {
        let node = Node::allocate_sized();
        unsafe { node.header_ptr().write(Header { next: None }) };
        unsafe { node.data_ptr().write(value) };

        match self.ends {
            None => self.ends = Some((node, node)),
            Some((front, back)) => {
                unsafe { back.header_ptr().as_mut() }.next = Some(node);
                self.ends = Some((front, node));
            }
        }
    }

    fn dequeue(&mut self) -> Option<T> {
        let (front, back) = self.ends?;

        let next = unsafe { front.header_ptr().as_ref() }.next;
        if let Some(next) = next {
            self.ends = Some((next, back));
        } else {
            debug_assert_eq!(front, back);
            self.ends = None;
        }

        let value = unsafe { front.data_ptr().read() };
        unsafe { front.deallocate_global() };
        Some(value)
    }

    fn delete_front(&mut self) -> bool {
        struct Guard<T> {
            node: Node<T>,
        }

        impl<T> Drop for Guard<T> {
            fn drop(&mut self) {
                unsafe { self.node.deallocate_global() };
            }
        }

        let Some((front, back)) = self.ends else {
            return false;
        };

        let next = unsafe { front.header_ptr().as_ref() }.next;
        if let Some(next) = next {
            self.ends = Some((next, back));
        } else {
            debug_assert_eq!(front, back);
            self.ends = None;
        }

        // If `<T as Drop>::drop` panics, we still want to deallocate the node.
        // In the event of a panic, the guard's `drop` will still be called
        // (unless an abort happens).
        let guard = Guard { node: front };
        unsafe { guard.node.data_ptr().drop_in_place() };
        // Explicitly calling drop is unnecessary but it makes the flow more
        // obvious.
        drop(guard);
        true
    }
}

impl<T> Drop for LinkedQueue<T> {
    fn drop(&mut self) {
        // Based on https://doc.rust-lang.org/1.82.0/src/alloc/collections/linked_list.rs.html#1169-1186

        struct Guard<'a, T> {
            queue: &'a mut LinkedQueue<T>,
        }

        impl<T> Drop for Guard<'_, T> {
            fn drop(&mut self) {
                // A call to `<T as Drop>::drop` panicked, keep dropping nodes.
                // If another one panics, the program will abort.
                while self.queue.delete_front() {}
            }
        }

        // We construct a 'drop guard' so that if a call to `<T as Drop>::drop`
        // (via `ptr::drop_in_place`) panics, we can try to keep dropping nodes.
        let guard = Guard { queue: self };
        while guard.queue.delete_front() {}
        mem::forget(guard);
    }
}