nolock/thread_data/storage/
trie.rs

1use alloc::boxed::Box;
2use core::fmt::Debug;
3
4mod level;
5use level::Level;
6
7mod entry;
8use entry::Entry;
9
10mod ptr;
11use ptr::{CustomPtr, PtrTarget};
12
13use crate::thread_data::StorageBackend;
14
15/// A Lock-Free Trie that can be used as the StorageBackend for Thread-Local-Data
16pub struct Trie<T> {
17    // The Pointer to the first Level
18    initial_ptr: *mut Level<T>,
19}
20
21impl<T> Debug for Trie<T>
22where
23    T: Debug,
24{
25    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
26        // Safety:
27        // This is save to do because we create the Pointer when creating the
28        // Trie meaning it is always going to be a valid pointer to a Level.
29        // The Memory being pointed to is also still valid because we only
30        // deallocate it once the Trie is dropped.
31        let initial_level = unsafe { &*self.initial_ptr };
32        write!(f, "Trie ({:?})", initial_level)
33    }
34}
35
36impl<T> Trie<T> {
37    /// Creates a new Trie instance
38    pub fn new() -> Self {
39        let initial_level = Level::new(0, 3, core::ptr::null());
40
41        Self {
42            initial_ptr: Box::into_raw(initial_level),
43        }
44    }
45}
46
47impl<T> StorageBackend<T> for Trie<T> {
48    fn get(&self, id: u64) -> Option<&T> {
49        // This simply "forwards" the get to the first initial Level of the
50        // Trie
51
52        // Safety:
53        // This is save to do because we create the Pointer when creating the
54        // Trie meaning it is always going to be a valid pointer to a Level.
55        // The Memory being pointed to is also still valid because we only
56        // deallocate it once the Trie is dropped.
57        let level = unsafe { &*self.initial_ptr };
58        level.get(id)
59    }
60
61    fn insert(&self, id: u64, data: T) -> &T {
62        // This simply "forwards" the insert to the first initial Level of the
63        // Trie
64
65        // Safety:
66        // This is save to do because we create the Pointer when creating the
67        // Trie meaning it is always going to be a valid pointer to a Level.
68        // The Memory being pointed to is also still valid because we only
69        // deallocate it once the Trie is dropped.
70        let level = unsafe { &*self.initial_ptr };
71        level.insert(id, data)
72    }
73}
74
75impl<T> Default for Trie<T> {
76    fn default() -> Self {
77        Self::new()
78    }
79}
80
81impl<T> Drop for Trie<T> {
82    fn drop(&mut self) {
83        unsafe { Box::from_raw(self.initial_ptr) };
84    }
85}
86
87#[cfg(test)]
88mod tests {
89    use super::*;
90
91    #[test]
92    fn new() {
93        Trie::<usize>::new();
94    }
95
96    #[test]
97    fn get_empty() {
98        let trie = Trie::<usize>::new();
99
100        assert_eq!(None, trie.get(123));
101        drop(trie);
102    }
103
104    #[test]
105    fn insert() {
106        let trie = Trie::<usize>::new();
107
108        let value = trie.insert(123, 13);
109        assert_eq!(13, *value);
110    }
111
112    #[test]
113    fn insert_get() {
114        let trie = Trie::<usize>::new();
115
116        let value = trie.insert(123, 13);
117        assert_eq!(13, *value);
118
119        let result = trie.get(123);
120        assert_eq!(Some(&13), result);
121    }
122
123    #[test]
124    fn insert_get_colliding() {
125        let trie = Trie::<usize>::new();
126
127        assert_eq!(13, *trie.insert(0x1234, 13));
128        assert_eq!(14, *trie.insert(0x1334, 14));
129        assert_eq!(15, *trie.insert(0x1434, 15));
130
131        assert_eq!(Some(&13), trie.get(0x1234));
132        assert_eq!(Some(&14), trie.get(0x1334));
133        assert_eq!(Some(&15), trie.get(0x1434));
134    }
135}
nolock/thread_data/storage/trie.rs

nolock/thread_data/storage/
trie.rs
