unc_sdk/store/unordered_map/
iter.rs

1use std::iter::FusedIterator;
2
3use borsh::{BorshDeserialize, BorshSerialize};
4
5use super::{LookupMap, ToKey, UnorderedMap, ValueAndIndex, ERR_INCONSISTENT_STATE};
6use crate::{env, store::free_list};
7
8impl<'a, K, V, H> IntoIterator for &'a UnorderedMap<K, V, H>
9where
10    K: BorshSerialize + Ord + BorshDeserialize + Clone,
11    V: BorshSerialize + BorshDeserialize,
12    H: ToKey,
13{
14    type Item = (&'a K, &'a V);
15    type IntoIter = Iter<'a, K, V, H>;
16
17    fn into_iter(self) -> Self::IntoIter {
18        self.iter()
19    }
20}
21
22impl<'a, K, V, H> IntoIterator for &'a mut UnorderedMap<K, V, H>
23where
24    K: BorshSerialize + Ord + BorshDeserialize + Clone,
25    V: BorshSerialize + BorshDeserialize,
26    H: ToKey,
27{
28    type Item = (&'a K, &'a mut V);
29    type IntoIter = IterMut<'a, K, V, H>;
30
31    fn into_iter(self) -> Self::IntoIter {
32        self.iter_mut()
33    }
34}
35
36/// An iterator over elements of a [`UnorderedMap`].
37///
38/// This `struct` is created by the `iter` method on [`UnorderedMap`].
39pub struct Iter<'a, K, V, H>
40where
41    K: BorshSerialize + Ord + BorshDeserialize,
42    V: BorshSerialize,
43    H: ToKey,
44{
45    /// Values iterator which contains empty and filled cells.
46    keys: free_list::Iter<'a, K>,
47    /// Reference to underlying map to lookup values with `keys`.
48    values: &'a LookupMap<K, ValueAndIndex<V>, H>,
49}
50
51impl<'a, K, V, H> Iter<'a, K, V, H>
52where
53    K: BorshSerialize + Ord + BorshDeserialize,
54    V: BorshSerialize,
55    H: ToKey,
56{
57    pub(super) fn new(map: &'a UnorderedMap<K, V, H>) -> Self {
58        Self { keys: map.keys.iter(), values: &map.values }
59    }
60}
61
62impl<'a, K, V, H> Iterator for Iter<'a, K, V, H>
63where
64    K: BorshSerialize + Ord + BorshDeserialize + Clone,
65    V: BorshSerialize + BorshDeserialize,
66    H: ToKey,
67{
68    type Item = (&'a K, &'a V);
69
70    fn next(&mut self) -> Option<Self::Item> {
71        <Self as Iterator>::nth(self, 0)
72    }
73
74    fn nth(&mut self, n: usize) -> Option<Self::Item> {
75        let key = self.keys.nth(n)?;
76        let entry = self.values.get(key).unwrap_or_else(|| env::panic_str(ERR_INCONSISTENT_STATE));
77
78        Some((key, &entry.value))
79    }
80
81    fn size_hint(&self) -> (usize, Option<usize>) {
82        self.keys.size_hint()
83    }
84
85    fn count(self) -> usize {
86        self.keys.count()
87    }
88}
89
90impl<'a, K, V, H> ExactSizeIterator for Iter<'a, K, V, H>
91where
92    K: BorshSerialize + Ord + BorshDeserialize + Clone,
93    V: BorshSerialize + BorshDeserialize,
94    H: ToKey,
95{
96}
97impl<'a, K, V, H> FusedIterator for Iter<'a, K, V, H>
98where
99    K: BorshSerialize + Ord + BorshDeserialize + Clone,
100    V: BorshSerialize + BorshDeserialize,
101    H: ToKey,
102{
103}
104
105impl<'a, K, V, H> DoubleEndedIterator for Iter<'a, K, V, H>
106where
107    K: BorshSerialize + Ord + BorshDeserialize + Clone,
108    V: BorshSerialize + BorshDeserialize,
109    H: ToKey,
110{
111    fn next_back(&mut self) -> Option<Self::Item> {
112        <Self as DoubleEndedIterator>::nth_back(self, 0)
113    }
114
115    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
116        let key = self.keys.nth_back(n)?;
117        let entry = self.values.get(key).unwrap_or_else(|| env::panic_str(ERR_INCONSISTENT_STATE));
118
119        Some((key, &entry.value))
120    }
121}
122
123/// A mutable iterator over elements of a [`UnorderedMap`].
124///
125/// This `struct` is created by the `iter_mut` method on [`UnorderedMap`].
126pub struct IterMut<'a, K, V, H>
127where
128    K: BorshSerialize + Ord + BorshDeserialize,
129    V: BorshSerialize,
130    H: ToKey,
131{
132    /// Values iterator which contains empty and filled cells.
133    keys: free_list::Iter<'a, K>,
134    /// Exclusive reference to underlying map to lookup values with `keys`.
135    values: &'a mut LookupMap<K, ValueAndIndex<V>, H>,
136}
137
138impl<'a, K, V, H> IterMut<'a, K, V, H>
139where
140    K: BorshSerialize + Ord + BorshDeserialize,
141    V: BorshSerialize,
142    H: ToKey,
143{
144    pub(super) fn new(map: &'a mut UnorderedMap<K, V, H>) -> Self {
145        Self { keys: map.keys.iter(), values: &mut map.values }
146    }
147    fn get_entry_mut<'b>(&'b mut self, key: &'a K) -> (&'a K, &'a mut V)
148    where
149        K: Clone,
150        V: BorshDeserialize,
151    {
152        let entry =
153            self.values.get_mut(key).unwrap_or_else(|| env::panic_str(ERR_INCONSISTENT_STATE));
154        //* SAFETY: The lifetime can be swapped here because we can assert that the iterator
155        //*         will only give out one mutable reference for every individual key in the bucket
156        //*         during the iteration, and there is no overlap. This operates under the
157        //*         assumption that all elements in the bucket are unique and no hash collisions.
158        //*         Because we use 32 byte hashes and all keys are verified unique based on the
159        //*         `UnorderedMap` API, this is safe.
160        let value = unsafe { &mut *(&mut entry.value as *mut V) };
161        (key, value)
162    }
163}
164
165impl<'a, K, V, H> Iterator for IterMut<'a, K, V, H>
166where
167    K: BorshSerialize + Ord + BorshDeserialize + Clone,
168    V: BorshSerialize + BorshDeserialize,
169    H: ToKey,
170{
171    type Item = (&'a K, &'a mut V);
172
173    fn next(&mut self) -> Option<Self::Item> {
174        <Self as Iterator>::nth(self, 0)
175    }
176
177    fn nth(&mut self, n: usize) -> Option<Self::Item> {
178        let key = self.keys.nth(n)?;
179        Some(self.get_entry_mut(key))
180    }
181
182    fn size_hint(&self) -> (usize, Option<usize>) {
183        self.keys.size_hint()
184    }
185
186    fn count(self) -> usize {
187        self.keys.count()
188    }
189}
190
191impl<'a, K, V, H> ExactSizeIterator for IterMut<'a, K, V, H>
192where
193    K: BorshSerialize + Ord + BorshDeserialize + Clone,
194    V: BorshSerialize + BorshDeserialize,
195    H: ToKey,
196{
197}
198impl<'a, K, V, H> FusedIterator for IterMut<'a, K, V, H>
199where
200    K: BorshSerialize + Ord + BorshDeserialize + Clone,
201    V: BorshSerialize + BorshDeserialize,
202    H: ToKey,
203{
204}
205
206impl<'a, K, V, H> DoubleEndedIterator for IterMut<'a, K, V, H>
207where
208    K: BorshSerialize + Ord + BorshDeserialize + Clone,
209    V: BorshSerialize + BorshDeserialize,
210    H: ToKey,
211{
212    fn next_back(&mut self) -> Option<Self::Item> {
213        <Self as DoubleEndedIterator>::nth_back(self, 0)
214    }
215
216    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
217        let key = self.keys.nth_back(n)?;
218        Some(self.get_entry_mut(key))
219    }
220}
221
222/// An iterator over the keys of a [`UnorderedMap`].
223///
224/// This `struct` is created by the `keys` method on [`UnorderedMap`].
225pub struct Keys<'a, K: 'a>
226where
227    K: BorshSerialize + BorshDeserialize,
228{
229    inner: free_list::Iter<'a, K>,
230}
231
232impl<'a, K> Keys<'a, K>
233where
234    K: BorshSerialize + BorshDeserialize,
235{
236    pub(super) fn new<V, H>(map: &'a UnorderedMap<K, V, H>) -> Self
237    where
238        K: Ord,
239        V: BorshSerialize,
240        H: ToKey,
241    {
242        Self { inner: map.keys.iter() }
243    }
244}
245
246impl<'a, K> Iterator for Keys<'a, K>
247where
248    K: BorshSerialize + BorshDeserialize,
249{
250    type Item = &'a K;
251
252    fn next(&mut self) -> Option<&'a K> {
253        self.inner.next()
254    }
255
256    fn size_hint(&self) -> (usize, Option<usize>) {
257        self.inner.size_hint()
258    }
259
260    fn count(self) -> usize {
261        self.inner.count()
262    }
263}
264
265impl<'a, K> ExactSizeIterator for Keys<'a, K> where K: BorshSerialize + BorshDeserialize {}
266impl<'a, K> FusedIterator for Keys<'a, K> where K: BorshSerialize + BorshDeserialize {}
267
268impl<'a, K> DoubleEndedIterator for Keys<'a, K>
269where
270    K: BorshSerialize + Ord + BorshDeserialize,
271{
272    fn next_back(&mut self) -> Option<&'a K> {
273        self.inner.next_back()
274    }
275}
276
277/// An iterator over the values of a [`UnorderedMap`].
278///
279/// This `struct` is created by the `values` method on [`UnorderedMap`].
280pub struct Values<'a, K, V, H>
281where
282    K: BorshSerialize + Ord + BorshDeserialize,
283    V: BorshSerialize,
284    H: ToKey,
285{
286    inner: Iter<'a, K, V, H>,
287}
288
289impl<'a, K, V, H> Values<'a, K, V, H>
290where
291    K: BorshSerialize + Ord + BorshDeserialize,
292    V: BorshSerialize,
293    H: ToKey,
294{
295    pub(super) fn new(map: &'a UnorderedMap<K, V, H>) -> Self {
296        Self { inner: map.iter() }
297    }
298}
299
300impl<'a, K, V, H> Iterator for Values<'a, K, V, H>
301where
302    K: BorshSerialize + Ord + BorshDeserialize + Clone,
303    V: BorshSerialize + BorshDeserialize,
304    H: ToKey,
305{
306    type Item = &'a V;
307
308    fn next(&mut self) -> Option<Self::Item> {
309        <Self as Iterator>::nth(self, 0)
310    }
311
312    fn nth(&mut self, n: usize) -> Option<Self::Item> {
313        self.inner.nth(n).map(|(_, v)| v)
314    }
315
316    fn size_hint(&self) -> (usize, Option<usize>) {
317        self.inner.size_hint()
318    }
319
320    fn count(self) -> usize {
321        self.inner.count()
322    }
323}
324
325impl<'a, K, V, H> ExactSizeIterator for Values<'a, K, V, H>
326where
327    K: BorshSerialize + Ord + BorshDeserialize + Clone,
328    V: BorshSerialize + BorshDeserialize,
329    H: ToKey,
330{
331}
332impl<'a, K, V, H> FusedIterator for Values<'a, K, V, H>
333where
334    K: BorshSerialize + Ord + BorshDeserialize + Clone,
335    V: BorshSerialize + BorshDeserialize,
336    H: ToKey,
337{
338}
339
340impl<'a, K, V, H> DoubleEndedIterator for Values<'a, K, V, H>
341where
342    K: BorshSerialize + Ord + BorshDeserialize + Clone,
343    V: BorshSerialize + BorshDeserialize,
344    H: ToKey,
345{
346    fn next_back(&mut self) -> Option<Self::Item> {
347        <Self as DoubleEndedIterator>::nth_back(self, 0)
348    }
349
350    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
351        self.inner.nth_back(n).map(|(_, v)| v)
352    }
353}
354
355/// A mutable iterator over values of a [`UnorderedMap`].
356///
357/// This `struct` is created by the `values_mut` method on [`UnorderedMap`].
358pub struct ValuesMut<'a, K, V, H>
359where
360    K: BorshSerialize + Ord + BorshDeserialize,
361    V: BorshSerialize,
362    H: ToKey,
363{
364    inner: IterMut<'a, K, V, H>,
365}
366
367impl<'a, K, V, H> ValuesMut<'a, K, V, H>
368where
369    K: BorshSerialize + Ord + BorshDeserialize,
370    V: BorshSerialize,
371    H: ToKey,
372{
373    pub(super) fn new(map: &'a mut UnorderedMap<K, V, H>) -> Self {
374        Self { inner: map.iter_mut() }
375    }
376}
377
378impl<'a, K, V, H> Iterator for ValuesMut<'a, K, V, H>
379where
380    K: BorshSerialize + Ord + BorshDeserialize + Clone,
381    V: BorshSerialize + BorshDeserialize,
382    H: ToKey,
383{
384    type Item = &'a mut V;
385
386    fn next(&mut self) -> Option<Self::Item> {
387        <Self as Iterator>::nth(self, 0)
388    }
389
390    fn nth(&mut self, n: usize) -> Option<Self::Item> {
391        self.inner.nth(n).map(|(_, v)| v)
392    }
393
394    fn size_hint(&self) -> (usize, Option<usize>) {
395        self.inner.size_hint()
396    }
397
398    fn count(self) -> usize {
399        self.inner.count()
400    }
401}
402
403impl<'a, K, V, H> ExactSizeIterator for ValuesMut<'a, K, V, H>
404where
405    K: BorshSerialize + Ord + BorshDeserialize + Clone,
406    V: BorshSerialize + BorshDeserialize,
407    H: ToKey,
408{
409}
410impl<'a, K, V, H> FusedIterator for ValuesMut<'a, K, V, H>
411where
412    K: BorshSerialize + Ord + BorshDeserialize + Clone,
413    V: BorshSerialize + BorshDeserialize,
414    H: ToKey,
415{
416}
417
418impl<'a, K, V, H> DoubleEndedIterator for ValuesMut<'a, K, V, H>
419where
420    K: BorshSerialize + Ord + BorshDeserialize + Clone,
421    V: BorshSerialize + BorshDeserialize,
422    H: ToKey,
423{
424    fn next_back(&mut self) -> Option<Self::Item> {
425        <Self as DoubleEndedIterator>::nth_back(self, 0)
426    }
427
428    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
429        self.inner.nth_back(n).map(|(_, v)| v)
430    }
431}
432
433/// A draining iterator for [`UnorderedMap<K, V, H>`].
434#[derive(Debug)]
435pub struct Drain<'a, K, V, H>
436where
437    K: BorshSerialize + BorshDeserialize + Ord,
438    V: BorshSerialize,
439    H: ToKey,
440{
441    keys: free_list::Drain<'a, K>,
442    values: &'a mut LookupMap<K, ValueAndIndex<V>, H>,
443}
444
445impl<'a, K, V, H> Drain<'a, K, V, H>
446where
447    K: BorshSerialize + BorshDeserialize + Ord,
448    V: BorshSerialize,
449    H: ToKey,
450{
451    pub(crate) fn new(list: &'a mut UnorderedMap<K, V, H>) -> Self {
452        Self { keys: list.keys.drain(), values: &mut list.values }
453    }
454
455    fn remaining(&self) -> usize {
456        self.keys.remaining()
457    }
458
459    fn remove_value(&mut self, key: K) -> (K, V)
460    where
461        K: Clone,
462        V: BorshDeserialize,
463    {
464        let value = self
465            .values
466            .remove(&key)
467            .unwrap_or_else(|| env::panic_str(ERR_INCONSISTENT_STATE))
468            .value;
469
470        (key, value)
471    }
472}
473
474impl<'a, K, V, H> Iterator for Drain<'a, K, V, H>
475where
476    K: BorshSerialize + BorshDeserialize + Ord + Clone,
477    V: BorshSerialize + BorshDeserialize,
478    H: ToKey,
479{
480    type Item = (K, V);
481
482    fn next(&mut self) -> Option<Self::Item> {
483        let key = self.keys.next()?;
484        Some(self.remove_value(key))
485    }
486
487    fn size_hint(&self) -> (usize, Option<usize>) {
488        let remaining = self.remaining();
489        (remaining, Some(remaining))
490    }
491
492    fn count(self) -> usize {
493        self.remaining()
494    }
495}
496
497impl<'a, K, V, H> ExactSizeIterator for Drain<'a, K, V, H>
498where
499    K: BorshSerialize + Ord + BorshDeserialize + Clone,
500    V: BorshSerialize + BorshDeserialize,
501    H: ToKey,
502{
503}
504
505impl<'a, K, V, H> FusedIterator for Drain<'a, K, V, H>
506where
507    K: BorshSerialize + Ord + BorshDeserialize + Clone,
508    V: BorshSerialize + BorshDeserialize,
509    H: ToKey,
510{
511}
512
513impl<'a, K, V, H> DoubleEndedIterator for Drain<'a, K, V, H>
514where
515    K: BorshSerialize + Ord + BorshDeserialize + Clone,
516    V: BorshSerialize + BorshDeserialize,
517    H: ToKey,
518{
519    fn next_back(&mut self) -> Option<Self::Item> {
520        let key = self.keys.next_back()?;
521        Some(self.remove_value(key))
522    }
523}
unc_sdk/store/unordered_map/iter.rs

unc_sdk/store/unordered_map/
iter.rs
