talc 5.0.3

A fast and flexible allocator for no_std and WebAssembly
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
131
132
133
134
135
136
137
138
139
140
141
142
143

use core::ptr::NonNull;

/// Describes a linked list node.
///
/// # Safety:
/// `LlistNode`s are inherently unsafe due to the referential dependency between nodes. This requires
/// that `LlistNode`s are never invalidated (e.g. overwritten) without removal, otherwise using the list becomes
/// referentially unsound and may lead to undefined behavior. Moving `Node`s will also not do what you expect.
///
/// This data structure is not thread-safe, use mutexes/locks to mutually exclude data access.
#[derive(Debug, Clone, Copy)]
#[repr(C)]
pub(crate) struct Node {
    pub next: Option<NonNull<Node>>,
    pub next_of_prev: *mut Option<NonNull<Node>>,
}

impl Node {
    #[inline]
    pub fn addr_of_next(ptr: *mut Self) -> *mut Option<NonNull<Self>> {
        ptr.cast() /* .cast::<u8>().wrapping_add(core::mem::offset_of!(LlistNode, next)) */
    }

    /// Create a new node as a member of an existing linked list at `node`.
    #[inline]
    pub unsafe fn link_at(ptr: *mut Self, data: Self) {
        debug_assert!(!ptr.is_null());
        debug_assert!(!data.next_of_prev.is_null());

        *data.next_of_prev = Some(NonNull::new_unchecked(ptr));

        if let Some(next) = data.next {
            (*next.as_ptr()).next_of_prev = Self::addr_of_next(ptr);
        }

        ptr.write(data);
    }

    /// Remove `node` from it's linked list.
    #[inline]
    pub unsafe fn unlink(self) {
        let Node { next, next_of_prev } = self;
        debug_assert!(!next_of_prev.is_null());

        *next_of_prev = next;

        if let Some(next) = next {
            (*next.as_ptr()).next_of_prev = next_of_prev;
        }
    }

    /// Creates an iterator over the linked list from the specified node.
    #[inline]
    pub unsafe fn iter_mut(first: Option<NonNull<Self>>) -> IterMut {
        IterMut::new(first)
    }
}

/// An iterator over the circular linked list `LlistNode`s, excluding the 'head'.
///
/// This `struct` is created by `LlistNode::iter_mut`. See its documentation for more.
#[derive(Debug)]
#[must_use = "iterators are lazy and do nothing unless consumed"]
pub(crate) struct IterMut(Option<NonNull<Node>>);

impl IterMut {
    /// Create a new iterator over the linked list from `first`.
    pub unsafe fn new(first: Option<NonNull<Node>>) -> Self {
        Self(first)
    }
}

impl Iterator for IterMut {
    type Item = NonNull<Node>;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        let current = self.0?;
        self.0 = unsafe { (*current.as_ptr()).next };
        Some(current)
    }
}

#[cfg(test)]
mod tests {
    use core::mem::MaybeUninit;

    use super::*;

    #[test]
    fn test_node() {
        unsafe {
            let x = Box::into_raw(Box::new(MaybeUninit::<Node>::uninit())).cast::<Node>();
            let y = Box::into_raw(Box::new(MaybeUninit::<Node>::uninit())).cast::<Node>();
            let z = Box::into_raw(Box::new(MaybeUninit::<Node>::uninit())).cast::<Node>();

            Node::link_at(y, Node { next: None, next_of_prev: Node::addr_of_next(x) });
            Node::link_at(
                z,
                Node { next: Some(NonNull::new(y).unwrap()), next_of_prev: Node::addr_of_next(x) },
            );

            let mut iter = Node::iter_mut(Some(NonNull::new(x)).unwrap());
            assert!(iter.next().is_some_and(|n| n.as_ptr() == x));
            assert!(iter.next().is_some_and(|n| n.as_ptr() == z));
            assert!(iter.next().is_some_and(|n| n.as_ptr() == y));
            assert!(iter.next().is_none());

            let mut iter = Node::iter_mut(Some(NonNull::new(y).unwrap()));
            assert!(iter.next().is_some_and(|n| n.as_ptr() == y));
            assert!(iter.next().is_none());

            Node::unlink(z.read());

            let mut iter = Node::iter_mut(Some(NonNull::new(x).unwrap()));
            assert!(iter.next().is_some_and(|n| n.as_ptr() == x));
            assert!(iter.next().is_some_and(|n| n.as_ptr() == y));
            assert!(iter.next().is_none());

            Node::link_at(
                z,
                Node { next: Some(NonNull::new(y).unwrap()), next_of_prev: Node::addr_of_next(x) },
            );

            let mut iter = Node::iter_mut(Some(NonNull::new(x).unwrap()));
            assert!(iter.next().is_some_and(|n| n.as_ptr() == x));
            assert!(iter.next().is_some_and(|n| n.as_ptr() == z));
            assert!(iter.next().is_some_and(|n| n.as_ptr() == y));
            assert!(iter.next().is_none());

            Node::unlink(z.read());
            Node::unlink(y.read());

            let mut iter = Node::iter_mut(Some(NonNull::new(x).unwrap()));
            assert!(iter.next().is_some_and(|n| n.as_ptr() == x));
            assert!(iter.next().is_none());

            drop(Box::from_raw(x));
            drop(Box::from_raw(y));
            drop(Box::from_raw(z));
        }
    }
}