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

facet_core/impls_alloc/
btreemap.rs
