dakv_skiplist/
skipnode.rs

1use crate::{Arena, K_MAX_HEIGHT};
2use bytes::Bytes;
3use std::fmt::{Error, Formatter};
4use std::sync::atomic::{AtomicPtr, Ordering};
5use std::{fmt, mem, ptr};
6
7pub struct Node {
8    pub data: Bytes,
9    pub forward: [AtomicPtr<Self>; K_MAX_HEIGHT],
10}
11
12impl Node {
13    #[allow(clippy::mut_from_ref)]
14    pub fn new<A: Arena>(data: Bytes, height: usize, arena: &A) -> &mut Self {
15        let size = mem::size_of::<Self>() /* 32 */
16                - (K_MAX_HEIGHT - height) * mem::size_of::<AtomicPtr<Self>>(); /* 8 * height*/
17
18        let ptr = arena.alloc(size) as *mut Node;
19
20        unsafe {
21            let node = &mut *ptr;
22            ptr::write(&mut node.data, data);
23            ptr::write_bytes(node.forward.as_mut_ptr(), 0, height);
24            node
25        }
26    }
27
28    #[allow(clippy::mut_from_ref)]
29    pub fn head<A: Arena>(arena: &A) -> &mut Self {
30        Self::new(Bytes::new(), K_MAX_HEIGHT, arena)
31    }
32
33    #[inline]
34    pub fn set_next(&self, n: usize, node: *mut Node) {
35        self.forward[n].store(node, Ordering::SeqCst);
36    }
37
38    #[inline]
39    pub fn get_next(&self, n: usize) -> *mut Node {
40        self.forward[n].load(Ordering::SeqCst)
41    }
42}
43
44impl fmt::Display for Node {
45    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
46        write!(f, "{:?}", self.data.as_ref())
47    }
48}
49
50#[cfg(test)]
51mod tests {
52    use super::Node;
53    use crate::ArenaImpl;
54
55    #[test]
56    fn test_new_node() {
57        let arena = ArenaImpl::new();
58
59        let node = Node::head(&arena);
60        assert_eq!(format!("{}", node), "[]");
61
62        let node = Node::new("da".into(), 0, &arena);
63        assert_eq!(format!("{}", node), "[100, 97]");
64    }
65
66    #[test]
67    fn test_next() {
68        let arena = ArenaImpl::new();
69
70        let node = Node::new(vec![1].into(), 3, &arena);
71        let next = Node::new(vec![2].into(), 4, &arena);
72        let tail = Node::new(vec![3].into(), 1, &arena);
73        node.set_next(2, next);
74        let ret = node.get_next(1);
75        assert!(ret.is_null());
76        let ret = node.get_next(2);
77        assert!(!ret.is_null());
78        unsafe {
79            assert_eq!((*ret).data.as_ref(), &[2]);
80        }
81
82        next.set_next(3, tail);
83        let v = next.get_next(3);
84        unsafe {
85            assert_eq!((*v).data.as_ref(), &[3]);
86        }
87    }
88}
dakv_skiplist/skipnode.rs

dakv_skiplist/
skipnode.rs
