skippy_rs/internal/sync/
iter.rs

1use crate::internal::utils::Node;
2
3use super::{Entry, SkipList};
4use core::iter::{FromIterator, IntoIterator, Iterator};
5
6pub struct Iter<'a, K, V> {
7    list: &'a SkipList<'a, K, V>,
8    next: Option<Entry<'a, K, V>>,
9}
10
11impl<'a, K, V> Iter<'a, K, V>
12where
13    K: Ord + Send + Sync,
14    V: Send + Sync,
15{
16    pub fn from_list(list: &'a SkipList<'a, K, V>) -> Self {
17        Self {
18            list,
19            next: list.get_first(),
20        }
21    }
22}
23
24impl<'a, K, V> core::iter::Iterator for Iter<'a, K, V>
25where
26    K: Ord + Send + Sync,
27    V: Send + Sync,
28{
29    type Item = Entry<'a, K, V>;
30    fn next(&mut self) -> Option<Self::Item> {
31        if let Some(next) = self.next.take() {
32            self.next = self.list.next_node(&next);
33            return Some(next);
34        }
35
36        None
37    }
38}
39
40impl<'a, K, V> IntoIterator for SkipList<'a, K, V>
41where
42    K: Ord + Send + Sync,
43    V: Send + Sync,
44{
45    type Item = (K, V);
46    type IntoIter = IntoIter<K, V>;
47    fn into_iter(self) -> Self::IntoIter {
48        IntoIter::from_list(self)
49    }
50}
51
52impl<'a, K, V> FromIterator<(K, V)> for SkipList<'a, K, V>
53where
54    K: Ord + Send + Sync,
55    V: Send + Sync,
56{
57    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
58        let list = Self::new();
59        for (k, v) in iter {
60            list.insert(k, v);
61        }
62
63        list
64    }
65}
66
67pub struct IntoIter<K, V> {
68    next: *mut Node<K, V>,
69}
70
71impl<K, V> IntoIter<K, V>
72where
73    K: Ord + Send + Sync,
74    V: Send + Sync,
75{
76    pub fn from_list<'a>(mut list: SkipList<'a, K, V>) -> Self {
77        unsafe {
78            let next = list.head.as_ref().levels[0].load_ptr();
79            for level in list.head.as_mut().levels.pointers.iter_mut() {
80                level.store_ptr(core::ptr::null_mut());
81            }
82
83            IntoIter { next }
84        }
85    }
86}
87
88impl<K, V> core::iter::Iterator for IntoIter<K, V>
89where
90    K: Ord + Send + Sync,
91    V: Send + Sync,
92{
93    type Item = (K, V);
94    fn next(&mut self) -> Option<Self::Item> {
95        if self.next.is_null() {
96            return None;
97        }
98
99        let next = self.next;
100
101        self.next = unsafe { (*next).levels[0].load_ptr() };
102
103        let (key, val) = unsafe { (core::ptr::read(&(*next).key), core::ptr::read(&(*next).val)) };
104
105        unsafe {
106            Node::dealloc(next);
107        }
108
109        (key, val).into()
110    }
111}
skippy_rs/internal/sync/iter.rs

skippy_rs/internal/sync/
iter.rs
