arctic/concurrent/
iter.rs

1use core::marker::PhantomData;
2use core::ops::ControlFlow;
3use core::sync::atomic::Ordering;
4
5use crate::Key;
6use crate::concurrent::Value;
7use crate::concurrent::smr;
8use crate::raw;
9use crate::raw::iter::Order;
10
11/// Immutable reference to a subtree rooted at a key prefix, optionally bounded by a key range.
12pub struct Shard<'g, 'k, K: Key, V, R, G> {
13    _guard: G,
14    inner: raw::Shard<'g, 'k, K, R>,
15    _value: PhantomData<V>,
16}
17
18impl<'g, 'k, K, V, R, G> Shard<'g, 'k, K, V, R, G>
19where
20    K: Key,
21    V: Value,
22    R: raw::iter::Range<K::Read<'k>>,
23    G: smr::Guard<V>,
24{
25    #[inline]
26    pub(super) unsafe fn new(
27        guard: G,
28        prefix: raw::Shard<'g, 'k, K, R>,
29    ) -> Shard<'g, 'k, K, V, R, G> {
30        Shard {
31            _guard: guard,
32            inner: prefix,
33            _value: PhantomData,
34        }
35    }
36}
37
38impl<'g, 'k, K, V, R, G> Shard<'g, 'k, K, V, R, G>
39where
40    K: Key,
41    V: Value,
42    R: raw::iter::Range<K::Read<'k>>,
43    G: smr::Guard<V>,
44{
45    /// Get an iterator over keys and immutable references to values in `O` order.
46    #[inline]
47    pub fn entries(&self, order: Order) -> EntryIter<'_, 'k, K, V, R> {
48        EntryIter {
49            inner: self.inner.entries(Some(order)),
50            value: 0,
51            _value: PhantomData,
52        }
53    }
54
55    /// Get an iterator over immutable references to values in `O` order.
56    #[inline]
57    pub fn values(&self, order: Order) -> ValueIter<'_, 'k, K, V, R> {
58        ValueIter {
59            inner: self.inner.values(Some(order)),
60            value: 0,
61            _value: PhantomData,
62        }
63    }
64}
65
66/// Iterator over keys and references to values.
67pub struct EntryIter<'g, 'k, K: Key, V: Value, R: raw::iter::Range<K::Read<'k>>> {
68    inner: raw::iter::EntryIter<'g, 'k, K, R>,
69    value: u64,
70    _value: PhantomData<V>,
71}
72
73impl<'g, 'k, K, V, R> EntryIter<'g, 'k, K, V, R>
74where
75    K: Key,
76    V: Value,
77    R: raw::iter::Range<K::Read<'k>>,
78{
79    /// Lending equivalent to [`Iterator::next`] that borrows the current key and
80    /// value from this [`EntryIter`].
81    #[inline]
82    pub fn lend(&mut self) -> Option<(K::Insert<'_>, &V::Borrowed)> {
83        self.inner.lend().map(|(key, value, _)| {
84            self.value = value;
85
86            if V::INDIRECT {
87                // Synchronizes with release compare_exchanges in
88                // `concurrent::Map::upsert_with_raw` and `concurrent::Map::update_with_raw`.
89                crate::sync::atomic::fence(Ordering::Acquire);
90            }
91
92            (key, unsafe { V::borrow_from_raw_unchecked(&self.value) })
93        })
94    }
95
96    /// Internal iteration over keys and immutable references to values.
97    #[inline]
98    pub fn try_fold<F, B, C>(mut self, init: C, mut apply: F) -> ControlFlow<B, C>
99    where
100        F: FnMut(C, (K::Insert<'_>, &V::Borrowed)) -> ControlFlow<B, C>,
101    {
102        self.inner.try_fold(init, |acc, (key, value, _)| {
103            self.value = value;
104
105            if V::INDIRECT {
106                // Synchronizes with release compare_exchanges in
107                // `concurrent::Map::upsert_with_raw` and `concurrent::Map::update_with_raw`.
108                crate::sync::atomic::fence(Ordering::Acquire);
109            }
110
111            apply(
112                acc,
113                (key, unsafe { V::borrow_from_raw_unchecked(&self.value) }),
114            )
115        })
116    }
117}
118
119impl<'g, 'k, K, V, R> Iterator for EntryIter<'g, 'k, K, V, R>
120where
121    K: Key,
122    V: Value,
123    V::Borrowed: Clone,
124    R: raw::iter::Range<K::Read<'k>>,
125{
126    type Item = (K, V::Borrowed);
127
128    // FIXME: specialize for `Arc` values
129    fn next(&mut self) -> Option<Self::Item> {
130        self.lend()
131            .map(|(key, value)| (K::insert_to_key(key), value.clone()))
132    }
133}
134
135/// Iterator over references to values.
136pub struct ValueIter<'g, 'k, K: Key, V: Value, R: raw::iter::Range<K::Read<'k>>> {
137    inner: raw::iter::ValueIter<'g, 'k, K, R>,
138    value: u64,
139    _value: PhantomData<V>,
140}
141
142impl<'g, 'k, K, V, R> ValueIter<'g, 'k, K, V, R>
143where
144    K: Key,
145    V: Value,
146    R: raw::iter::Range<K::Read<'k>>,
147{
148    /// Lending equivalent to [`Iterator::next`] that borrows the current value from this [`EntryIter`].
149    #[inline]
150    pub fn lend(&mut self) -> Option<&V::Borrowed> {
151        self.inner.lend().map(|(value, _)| {
152            self.value = value;
153
154            if V::INDIRECT {
155                // Synchronizes with release compare_exchanges in
156                // `concurrent::Map::upsert_with_raw` and `concurrent::Map::update_with_raw`.
157                crate::sync::atomic::fence(Ordering::Acquire);
158            }
159
160            unsafe { V::borrow_from_raw_unchecked(&self.value) }
161        })
162    }
163
164    /// Internal iteration over immutable references to values.
165    #[inline]
166    pub fn try_fold<F: FnMut(C, &V::Borrowed) -> ControlFlow<B, C>, B, C>(
167        mut self,
168        init: C,
169        mut apply: F,
170    ) -> ControlFlow<B, C> {
171        self.inner.try_fold(init, |acc, (value, _)| {
172            self.value = value;
173
174            if V::INDIRECT {
175                // Synchronizes with release compare_exchanges in
176                // `concurrent::Map::upsert_with_raw` and `concurrent::Map::update_with_raw`.
177                crate::sync::atomic::fence(Ordering::Acquire);
178            }
179
180            apply(acc, unsafe { V::borrow_from_raw_unchecked(&self.value) })
181        })
182    }
183}
184
185impl<'g, 'k, K, V, R> Iterator for ValueIter<'g, 'k, K, V, R>
186where
187    K: Key,
188    V: Value,
189    V::Borrowed: Clone,
190    R: raw::iter::Range<K::Read<'k>>,
191{
192    type Item = V::Borrowed;
193
194    // FIXME: specialize for `Arc` values
195    fn next(&mut self) -> Option<Self::Item> {
196        self.lend().cloned()
197    }
198}
arctic/concurrent/iter.rs

arctic/concurrent/
iter.rs
