iddqd/id_ord_map/
iter.rs

1use super::{IdOrdItem, RefMut, tables::IdOrdMapTables};
2use crate::support::{
3    alloc::Global,
4    borrow::DormantMutRef,
5    btree_table,
6    item_set::{ConsumingItemSet, ItemSet, ItemSlotsPtr},
7};
8use core::{hash::Hash, iter::FusedIterator};
9
10/// An iterator over the elements of an [`IdOrdMap`] by shared reference.
11///
12/// Created by [`IdOrdMap::iter`], and ordered by keys.
13///
14/// [`IdOrdMap`]: crate::IdOrdMap
15/// [`IdOrdMap::iter`]: crate::IdOrdMap::iter
16#[derive(Clone, Debug)]
17pub struct Iter<'a, T: IdOrdItem> {
18    items: &'a ItemSet<T, Global>,
19    iter: btree_table::Iter<'a>,
20}
21
22impl<'a, T: IdOrdItem> Iter<'a, T> {
23    pub(super) fn new(
24        items: &'a ItemSet<T, Global>,
25        tables: &'a IdOrdMapTables,
26    ) -> Self {
27        Self { items, iter: tables.key_to_item.iter() }
28    }
29}
30
31impl<'a, T: IdOrdItem> Iterator for Iter<'a, T> {
32    type Item = &'a T;
33
34    #[inline]
35    fn next(&mut self) -> Option<Self::Item> {
36        let index = self.iter.next()?;
37        Some(&self.items[index])
38    }
39}
40
41impl<T: IdOrdItem> ExactSizeIterator for Iter<'_, T> {
42    #[inline]
43    fn len(&self) -> usize {
44        self.iter.len()
45    }
46}
47
48// btree_set::Iter is a FusedIterator, so Iter is as well.
49impl<T: IdOrdItem> FusedIterator for Iter<'_, T> {}
50
51/// An iterator over the elements of a [`IdOrdMap`] by mutable reference.
52///
53/// This iterator returns [`RefMut`] instances.
54///
55/// Created by [`IdOrdMap::iter_mut`], and ordered by keys.
56///
57/// [`IdOrdMap`]: crate::IdOrdMap
58/// [`IdOrdMap::iter_mut`]: crate::IdOrdMap::iter_mut
59#[derive(Debug)]
60pub struct IterMut<'a, T: IdOrdItem>
61where
62    T::Key<'a>: Hash,
63{
64    items: ItemSlotsPtr<'a, T>,
65    tables: &'a IdOrdMapTables,
66    iter: btree_table::Iter<'a>,
67}
68
69impl<'a, T: IdOrdItem> IterMut<'a, T>
70where
71    T::Key<'a>: Hash,
72{
73    pub(super) fn new(
74        items: &'a mut ItemSet<T, Global>,
75        tables: &'a IdOrdMapTables,
76    ) -> Self {
77        Self {
78            items: ItemSlotsPtr::new(items.slots_mut()),
79            tables,
80            iter: tables.key_to_item.iter(),
81        }
82    }
83}
84
85impl<'a, T: IdOrdItem + 'a> Iterator for IterMut<'a, T>
86where
87    T::Key<'a>: Hash,
88{
89    type Item = RefMut<'a, T>;
90
91    #[inline]
92    fn next(&mut self) -> Option<Self::Item> {
93        let index = self.iter.next()?;
94
95        // SAFETY: The B-tree is a set, so each call to `self.iter.next()`
96        // yields a distinct `index`. Therefore the `&mut T` references that
97        // `get_mut` hands out across iterations never alias.
98        let item: &'a mut T = unsafe { self.items.get_mut(index) };
99
100        let (hash, dormant) = {
101            let (item, dormant) = DormantMutRef::new(item);
102            let hash = self.tables.make_hash(item);
103            (hash, dormant)
104        };
105
106        // SAFETY: The `&mut T` that `DormantMutRef::new` produced inside
107        // the block above (and used for hashing) was dropped when the
108        // block closed, so the dormant ref is now the unique borrow of
109        // the slot. The `self.tables.state()` access below touches a
110        // different allocation and does not alias.
111        let item = unsafe { dormant.awaken() };
112
113        Some(RefMut::new(self.tables.state().clone(), hash, item))
114    }
115}
116
117impl<'a, T: IdOrdItem + 'a> ExactSizeIterator for IterMut<'a, T>
118where
119    T::Key<'a>: Hash,
120{
121    #[inline]
122    fn len(&self) -> usize {
123        self.iter.len()
124    }
125}
126
127impl<'a, T: IdOrdItem + 'a> FusedIterator for IterMut<'a, T> where
128    T::Key<'a>: Hash
129{
130}
131
132/// An iterator over the elements of a [`IdOrdMap`] by ownership.
133///
134/// Created by [`IdOrdMap::into_iter`], and ordered by keys.
135///
136/// [`IdOrdMap`]: crate::IdOrdMap
137/// [`IdOrdMap::into_iter`]: crate::IdOrdMap::into_iter
138#[derive(Debug)]
139pub struct IntoIter<T: IdOrdItem> {
140    items: ConsumingItemSet<T, Global>,
141    iter: btree_table::IntoIter,
142}
143
144impl<T: IdOrdItem> IntoIter<T> {
145    pub(super) fn new(
146        items: ItemSet<T, Global>,
147        tables: IdOrdMapTables,
148    ) -> Self {
149        Self {
150            items: items.into_consuming(),
151            iter: tables.key_to_item.into_iter(),
152        }
153    }
154}
155
156impl<T: IdOrdItem> Iterator for IntoIter<T> {
157    type Item = T;
158
159    #[inline]
160    fn next(&mut self) -> Option<Self::Item> {
161        let index = self.iter.next()?;
162        // We own `self.items` and the B-tree's indexes are never revisited, so
163        // we can take directly from the consuming view.
164        let next = self
165            .items
166            .take(index)
167            .unwrap_or_else(|| panic!("index {index} not found in items"));
168        Some(next)
169    }
170}
iddqd/id_ord_map/iter.rs

iddqd/id_ord_map/
iter.rs
