facet_core/impls_alloc/
btreemap.rs

1use core::write;
2
3use alloc::{
4    boxed::Box,
5    collections::{BTreeMap, VecDeque},
6};
7
8use crate::{
9    Def, Facet, MapDef, MapIterVTable, MapVTable, MarkerTraits, PtrConst, PtrMut, Shape, Type,
10    UserType, VTableView, ValueVTable,
11};
12
13struct BTreeMapIterator<'mem, K> {
14    map: PtrConst<'mem>,
15    keys: VecDeque<&'mem K>,
16}
17
18unsafe impl<'a, K, V> Facet<'a> for BTreeMap<K, V>
19where
20    K: Facet<'a> + core::cmp::Eq + core::cmp::Ord,
21    V: Facet<'a>,
22{
23    const VTABLE: &'static ValueVTable = &const {
24        let mut builder = ValueVTable::builder::<Self>()
25            .marker_traits({
26                let arg_dependent_traits = MarkerTraits::SEND
27                    .union(MarkerTraits::SYNC)
28                    .union(MarkerTraits::EQ);
29                arg_dependent_traits
30                    .intersection(V::SHAPE.vtable.marker_traits)
31                    .intersection(K::SHAPE.vtable.marker_traits)
32                    // only depends on `A` which we are not generic over (yet)
33                    .union(MarkerTraits::UNPIN)
34            })
35            .type_name(|f, opts| {
36                if let Some(opts) = opts.for_children() {
37                    write!(f, "BTreeMap<")?;
38                    (K::SHAPE.vtable.type_name)(f, opts)?;
39                    write!(f, ", ")?;
40                    (V::SHAPE.vtable.type_name)(f, opts)?;
41                    write!(f, ">")
42                } else {
43                    write!(f, "BTreeMap<⋯>")
44                }
45            });
46
47        if K::SHAPE.vtable.debug.is_some() && V::SHAPE.vtable.debug.is_some() {
48            builder = builder.debug(|value, f| {
49                let k_debug = <VTableView<K>>::of().debug().unwrap();
50                let v_debug = <VTableView<V>>::of().debug().unwrap();
51                write!(f, "{{")?;
52                for (i, (key, val)) in value.iter().enumerate() {
53                    if i > 0 {
54                        write!(f, ", ")?;
55                    }
56                    (k_debug)(key, f)?;
57                    write!(f, ": ")?;
58                    (v_debug)(val, f)?;
59                }
60                write!(f, "}}")
61            })
62        }
63
64        builder = builder.default_in_place(|target| unsafe { target.put(Self::default()) });
65
66        if V::SHAPE.vtable.clone_into.is_some() && K::SHAPE.vtable.clone_into.is_some() {
67            builder = builder.clone_into(|src, dst| unsafe {
68                let mut new_map = BTreeMap::new();
69
70                let k_clone_into = <VTableView<K>>::of().clone_into().unwrap();
71                let v_clone_into = <VTableView<V>>::of().clone_into().unwrap();
72
73                for (k, v) in src {
74                    use crate::TypedPtrUninit;
75                    use core::mem::MaybeUninit;
76
77                    let mut new_k = MaybeUninit::<K>::uninit();
78                    let mut new_v = MaybeUninit::<V>::uninit();
79
80                    let uninit_k = TypedPtrUninit::new(new_k.as_mut_ptr());
81                    let uninit_v = TypedPtrUninit::new(new_v.as_mut_ptr());
82
83                    (k_clone_into)(k, uninit_k);
84                    (v_clone_into)(v, uninit_v);
85
86                    new_map.insert(new_k.assume_init(), new_v.assume_init());
87                }
88
89                dst.put(new_map)
90            });
91        }
92
93        if V::SHAPE.vtable.eq.is_some() {
94            builder = builder.eq(|a, b| {
95                let v_eq = <VTableView<V>>::of().eq().unwrap();
96                a.len() == b.len()
97                    && a.iter().all(|(key_a, val_a)| {
98                        b.get(key_a).is_some_and(|val_b| (v_eq)(val_a, val_b))
99                    })
100            });
101        }
102
103        if K::SHAPE.vtable.hash.is_some() && V::SHAPE.vtable.hash.is_some() {
104            builder = builder.hash(|map, hasher_this, hasher_write_fn| unsafe {
105                use crate::HasherProxy;
106                use core::hash::Hash;
107
108                let k_hash = <VTableView<K>>::of().hash().unwrap();
109                let v_hash = <VTableView<V>>::of().hash().unwrap();
110                let mut hasher = HasherProxy::new(hasher_this, hasher_write_fn);
111                map.len().hash(&mut hasher);
112                for (k, v) in map {
113                    (k_hash)(k, hasher_this, hasher_write_fn);
114                    (v_hash)(v, hasher_this, hasher_write_fn);
115                }
116            });
117        }
118
119        builder.build()
120    };
121
122    const SHAPE: &'static crate::Shape = &const {
123        Shape::builder_for_sized::<Self>()
124            .type_params(&[
125                crate::TypeParam {
126                    name: "K",
127                    shape: || K::SHAPE,
128                },
129                crate::TypeParam {
130                    name: "V",
131                    shape: || V::SHAPE,
132                },
133            ])
134            .ty(Type::User(UserType::Opaque))
135            .def(Def::Map(
136                MapDef::builder()
137                    .k(|| K::SHAPE)
138                    .v(|| V::SHAPE)
139                    .vtable(
140                        &const {
141                            MapVTable::builder()
142                                .init_in_place_with_capacity(|uninit, _capacity| unsafe {
143                                    uninit.put(Self::new())
144                                })
145                                .insert(|ptr, key, value| unsafe {
146                                    let map = ptr.as_mut::<Self>();
147                                    let k = key.read::<K>();
148                                    let v = value.read::<V>();
149                                    map.insert(k, v);
150                                })
151                                .len(|ptr| unsafe {
152                                    let map = ptr.get::<Self>();
153                                    map.len()
154                                })
155                                .contains_key(|ptr, key| unsafe {
156                                    let map = ptr.get::<Self>();
157                                    map.contains_key(key.get())
158                                })
159                                .get_value_ptr(|ptr, key| unsafe {
160                                    let map = ptr.get::<Self>();
161                                    map.get(key.get()).map(|v| PtrConst::new(v as *const _))
162                                })
163                                .iter(|ptr| unsafe {
164                                    let map = ptr.get::<Self>();
165                                    let keys: VecDeque<&K> = map.keys().collect();
166                                    let iter_state = Box::new(BTreeMapIterator { map: ptr, keys });
167                                    PtrMut::new(Box::into_raw(iter_state) as *mut u8)
168                                })
169                                .iter_vtable(
170                                    MapIterVTable::builder()
171                                        .next(|iter_ptr| unsafe {
172                                            let state =
173                                                iter_ptr.as_mut::<BTreeMapIterator<'_, K>>();
174                                            let map = state.map.get::<Self>();
175                                            while let Some(key) = state.keys.pop_front() {
176                                                if let Some(value) = map.get(key) {
177                                                    return Some((
178                                                        PtrConst::new(key as *const K),
179                                                        PtrConst::new(value as *const V),
180                                                    ));
181                                                }
182                                            }
183
184                                            None
185                                        })
186                                        .next_back(|iter_ptr| unsafe {
187                                            let state =
188                                                iter_ptr.as_mut::<BTreeMapIterator<'_, K>>();
189                                            let map = state.map.get::<Self>();
190                                            while let Some(key) = state.keys.pop_back() {
191                                                if let Some(value) = map.get(key) {
192                                                    return Some((
193                                                        PtrConst::new(key as *const K),
194                                                        PtrConst::new(value as *const V),
195                                                    ));
196                                                }
197                                            }
198
199                                            None
200                                        })
201                                        .dealloc(|iter_ptr| unsafe {
202                                            drop(Box::from_raw(
203                                                iter_ptr.as_ptr::<BTreeMapIterator<'_, K>>()
204                                                    as *mut BTreeMapIterator<'_, K>,
205                                            ))
206                                        })
207                                        .build(),
208                                )
209                                .build()
210                        },
211                    )
212                    .build(),
213            ))
214            .build()
215    };
216}
facet_core/impls_alloc/btreemap.rs

facet_core/impls_alloc/
btreemap.rs
