skippy-rs 0.0.0-alpha.4

A set of lock free, thread safe, and fast data structures implemented via a Skip List
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

use crate::internal::utils::Node;

use super::{Entry, SkipList};
use core::iter::{FromIterator, IntoIterator, Iterator};

pub struct Iter<'a, K, V> {
    list: &'a SkipList<'a, K, V>,
    next: Option<Entry<'a, K, V>>,
}

impl<'a, K, V> Iter<'a, K, V>
where
    K: Ord + Send + Sync,
    V: Send + Sync,
{
    pub fn from_list(list: &'a SkipList<'a, K, V>) -> Self {
        Self {
            list,
            next: list.get_first(),
        }
    }
}

impl<'a, K, V> core::iter::Iterator for Iter<'a, K, V>
where
    K: Ord + Send + Sync,
    V: Send + Sync,
{
    type Item = Entry<'a, K, V>;
    fn next(&mut self) -> Option<Self::Item> {
        if let Some(next) = self.next.take() {
            self.next = self.list.next_node(&next);
            return Some(next);
        }

        None
    }
}

impl<'a, K, V> IntoIterator for SkipList<'a, K, V>
where
    K: Ord + Send + Sync,
    V: Send + Sync,
{
    type Item = (K, V);
    type IntoIter = IntoIter<K, V>;
    fn into_iter(self) -> Self::IntoIter {
        IntoIter::from_list(self)
    }
}

impl<'a, K, V> FromIterator<(K, V)> for SkipList<'a, K, V>
where
    K: Ord + Send + Sync,
    V: Send + Sync,
{
    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
        let list = Self::new();
        for (k, v) in iter {
            list.insert(k, v);
        }

        list
    }
}

pub struct IntoIter<K, V> {
    next: *mut Node<K, V>,
}

impl<K, V> IntoIter<K, V>
where
    K: Ord + Send + Sync,
    V: Send + Sync,
{
    pub fn from_list<'a>(mut list: SkipList<'a, K, V>) -> Self {
        unsafe {
            let next = list.head.as_ref().levels[0].load_ptr();
            for level in list.head.as_mut().levels.pointers.iter_mut() {
                level.store_ptr(core::ptr::null_mut());
            }

            IntoIter { next }
        }
    }
}

impl<K, V> core::iter::Iterator for IntoIter<K, V>
where
    K: Ord + Send + Sync,
    V: Send + Sync,
{
    type Item = (K, V);
    fn next(&mut self) -> Option<Self::Item> {
        if self.next.is_null() {
            return None;
        }

        let next = self.next;

        self.next = unsafe { (*next).levels[0].load_ptr() };

        let (key, val) = unsafe { (core::ptr::read(&(*next).key), core::ptr::read(&(*next).val)) };

        unsafe {
            Node::dealloc(next);
        }

        (key, val).into()
    }
}