iddqd/id_ord_map/
iter.rs

1use super::{IdOrdItem, RefMut, tables::IdOrdMapTables};
2use crate::support::{
3    alloc::Global, borrow::DormantMutRef, btree_table, item_set::ItemSet,
4};
5use core::{hash::Hash, iter::FusedIterator};
6
7/// An iterator over the elements of an [`IdOrdMap`] by shared reference.
8///
9/// Created by [`IdOrdMap::iter`], and ordered by keys.
10///
11/// [`IdOrdMap`]: crate::IdOrdMap
12/// [`IdOrdMap::iter`]: crate::IdOrdMap::iter
13#[derive(Clone, Debug)]
14pub struct Iter<'a, T: IdOrdItem> {
15    items: &'a ItemSet<T, Global>,
16    iter: btree_table::Iter<'a>,
17}
18
19impl<'a, T: IdOrdItem> Iter<'a, T> {
20    pub(super) fn new(
21        items: &'a ItemSet<T, Global>,
22        tables: &'a IdOrdMapTables,
23    ) -> Self {
24        Self { items, iter: tables.key_to_item.iter() }
25    }
26}
27
28impl<'a, T: IdOrdItem> Iterator for Iter<'a, T> {
29    type Item = &'a T;
30
31    #[inline]
32    fn next(&mut self) -> Option<Self::Item> {
33        let index = self.iter.next()?;
34        Some(&self.items[index])
35    }
36}
37
38impl<T: IdOrdItem> ExactSizeIterator for Iter<'_, T> {
39    #[inline]
40    fn len(&self) -> usize {
41        self.iter.len()
42    }
43}
44
45// btree_set::Iter is a FusedIterator, so Iter is as well.
46impl<T: IdOrdItem> FusedIterator for Iter<'_, T> {}
47
48/// An iterator over the elements of a [`IdOrdMap`] by mutable reference.
49///
50/// This iterator returns [`RefMut`] instances.
51///
52/// Created by [`IdOrdMap::iter_mut`], and ordered by keys.
53///
54/// [`IdOrdMap`]: crate::IdOrdMap
55/// [`IdOrdMap::iter_mut`]: crate::IdOrdMap::iter_mut
56#[derive(Debug)]
57pub struct IterMut<'a, T: IdOrdItem>
58where
59    T::Key<'a>: Hash,
60{
61    items: &'a mut ItemSet<T, Global>,
62    tables: &'a IdOrdMapTables,
63    iter: btree_table::Iter<'a>,
64}
65
66impl<'a, T: IdOrdItem> IterMut<'a, T>
67where
68    T::Key<'a>: Hash,
69{
70    pub(super) fn new(
71        items: &'a mut ItemSet<T, Global>,
72        tables: &'a IdOrdMapTables,
73    ) -> Self {
74        Self { items, tables, iter: tables.key_to_item.iter() }
75    }
76}
77
78impl<'a, T: IdOrdItem + 'a> Iterator for IterMut<'a, T>
79where
80    T::Key<'a>: Hash,
81{
82    type Item = RefMut<'a, T>;
83
84    #[inline]
85    fn next(&mut self) -> Option<Self::Item> {
86        let index = self.iter.next()?;
87
88        let item = &mut self.items[index];
89
90        // SAFETY: This lifetime extension from self to 'a is safe based on two
91        // things:
92        //
93        // 1. We never repeat indexes, i.e. for an index i, once we've handed
94        //    out an item at i, creating `&mut T`, we'll never get the index i
95        //    again. (This is guaranteed from the set-based nature of the
96        //    iterator.) This means that we don't ever create a mutable alias to
97        //    the same memory.
98        //
99        //    In particular, unlike all the other places we look up data from a
100        //    btree table, we don't pass a lookup function into
101        //    self.iter.next(). If we did, then it is possible the lookup
102        //    function would have been called with an old index i. But we don't
103        //    need to do that.
104        //
105        // 2. All mutable references to data within self.items are derived from
106        //    self.items. So, the rule described at [1] is upheld:
107        //
108        //    > When creating a mutable reference, then while this reference
109        //    > exists, the memory it points to must not get accessed (read or
110        //    > written) through any other pointer or reference not derived from
111        //    > this reference.
112        //
113        // [1]:
114        //     https://doc.rust-lang.org/std/ptr/index.html#pointer-to-reference-conversion
115        let item = unsafe { core::mem::transmute::<&mut T, &'a mut T>(item) };
116
117        let (hash, dormant) = {
118            let (item, dormant) = DormantMutRef::new(item);
119            let hash = self.tables.make_hash(item);
120            (hash, dormant)
121        };
122
123        // SAFETY: item is dropped above, and self is no longer used after this
124        // point.
125        let item = unsafe { dormant.awaken() };
126
127        Some(RefMut::new(hash, item))
128    }
129}
130
131impl<'a, T: IdOrdItem + 'a> ExactSizeIterator for IterMut<'a, T>
132where
133    T::Key<'a>: Hash,
134{
135    #[inline]
136    fn len(&self) -> usize {
137        self.iter.len()
138    }
139}
140
141// hash_map::IterMut is a FusedIterator, so IterMut is as well.
142impl<'a, T: IdOrdItem + 'a> FusedIterator for IterMut<'a, T> where
143    T::Key<'a>: Hash
144{
145}
146
147/// An iterator over the elements of a [`IdOrdMap`] by ownership.
148///
149/// Created by [`IdOrdMap::into_iter`], and ordered by keys.
150///
151/// [`IdOrdMap`]: crate::IdOrdMap
152/// [`IdOrdMap::into_iter`]: crate::IdOrdMap::into_iter
153#[derive(Debug)]
154pub struct IntoIter<T: IdOrdItem> {
155    items: ItemSet<T, Global>,
156    iter: btree_table::IntoIter,
157}
158
159impl<T: IdOrdItem> IntoIter<T> {
160    pub(super) fn new(
161        items: ItemSet<T, Global>,
162        tables: IdOrdMapTables,
163    ) -> Self {
164        Self { items, iter: tables.key_to_item.into_iter() }
165    }
166}
167
168impl<T: IdOrdItem> Iterator for IntoIter<T> {
169    type Item = T;
170
171    #[inline]
172    fn next(&mut self) -> Option<Self::Item> {
173        let index = self.iter.next()?;
174        let next = self
175            .items
176            .remove(index)
177            .unwrap_or_else(|| panic!("index {index} not found in items"));
178        Some(next)
179    }
180}
iddqd/id_ord_map/iter.rs

iddqd/id_ord_map/
iter.rs
