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