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 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, "{}<", Self::SHAPE.type_identifier)?;
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 .debug(|| {
41 if K::VTABLE.has_debug() && V::VTABLE.has_debug() {
42 Some(|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 } else {
57 None
58 }
59 })
60 .default_in_place(|| Some(|target| unsafe { target.put(Self::default()) }))
61 .clone_into(|| {
62 if K::SHAPE.vtable.has_clone_into() && V::SHAPE.vtable.has_clone_into() {
63 Some(|src, dst| unsafe {
64 let mut new_map = BTreeMap::new();
65
66 let k_clone_into = <VTableView<K>>::of().clone_into().unwrap();
67 let v_clone_into = <VTableView<V>>::of().clone_into().unwrap();
68
69 for (k, v) in src {
70 use crate::TypedPtrUninit;
71 use core::mem::MaybeUninit;
72
73 let mut new_k = MaybeUninit::<K>::uninit();
74 let mut new_v = MaybeUninit::<V>::uninit();
75
76 let uninit_k = TypedPtrUninit::new(new_k.as_mut_ptr());
77 let uninit_v = TypedPtrUninit::new(new_v.as_mut_ptr());
78
79 (k_clone_into)(k, uninit_k);
80 (v_clone_into)(v, uninit_v);
81
82 new_map.insert(new_k.assume_init(), new_v.assume_init());
83 }
84
85 dst.put(new_map)
86 })
87 } else {
88 None
89 }
90 })
91 .partial_eq(|| {
92 if V::SHAPE.vtable.has_partial_eq() {
93 Some(|a, b| {
94 let v_eq = <VTableView<V>>::of().partial_eq().unwrap();
95 a.len() == b.len()
96 && a.iter().all(|(key_a, val_a)| {
97 b.get(key_a).is_some_and(|val_b| (v_eq)(val_a, val_b))
98 })
99 })
100 } else {
101 None
102 }
103 })
104 .hash(|| {
105 if K::SHAPE.vtable.has_hash() && V::SHAPE.vtable.has_hash() {
106 Some(|map, hasher_this, hasher_write_fn| unsafe {
107 use crate::HasherProxy;
108 use core::hash::Hash;
109
110 let k_hash = <VTableView<K>>::of().hash().unwrap();
111 let v_hash = <VTableView<V>>::of().hash().unwrap();
112 let mut hasher = HasherProxy::new(hasher_this, hasher_write_fn);
113 map.len().hash(&mut hasher);
114 for (k, v) in map {
115 (k_hash)(k, hasher_this, hasher_write_fn);
116 (v_hash)(v, hasher_this, hasher_write_fn);
117 }
118 })
119 } else {
120 None
121 }
122 })
123 .build()
124 };
125
126 const SHAPE: &'static crate::Shape<'static> = &const {
127 Shape::builder_for_sized::<Self>()
128 .type_identifier("BTreeMap")
129 .type_params(&[
130 crate::TypeParam {
131 name: "K",
132 shape: || K::SHAPE,
133 },
134 crate::TypeParam {
135 name: "V",
136 shape: || V::SHAPE,
137 },
138 ])
139 .ty(Type::User(UserType::Opaque))
140 .def(Def::Map(
141 MapDef::builder()
142 .k(|| K::SHAPE)
143 .v(|| V::SHAPE)
144 .vtable(
145 &const {
146 MapVTable::builder()
147 .init_in_place_with_capacity(|uninit, _capacity| unsafe {
148 uninit.put(Self::new())
149 })
150 .insert(|ptr, key, value| unsafe {
151 let map = ptr.as_mut::<Self>();
152 let k = key.read::<K>();
153 let v = value.read::<V>();
154 map.insert(k, v);
155 })
156 .len(|ptr| unsafe {
157 let map = ptr.get::<Self>();
158 map.len()
159 })
160 .contains_key(|ptr, key| unsafe {
161 let map = ptr.get::<Self>();
162 map.contains_key(key.get())
163 })
164 .get_value_ptr(|ptr, key| unsafe {
165 let map = ptr.get::<Self>();
166 map.get(key.get()).map(|v| PtrConst::new(v as *const _))
167 })
168 .iter_vtable(
169 IterVTable::builder()
170 .init_with_value(|ptr| unsafe {
171 let map = ptr.get::<Self>();
172 let iter: BTreeMapIterator<'_, K, V> = map.iter();
173 let state = Box::new(iter);
174 PtrMut::new(Box::into_raw(state) as *mut u8)
175 })
176 .next(|iter_ptr| unsafe {
177 let state =
178 iter_ptr.as_mut::<BTreeMapIterator<'_, K, V>>();
179 state.next().map(|(key, value)| {
180 (PtrConst::new(key), PtrConst::new(value))
181 })
182 })
183 .next_back(|iter_ptr| unsafe {
184 let state =
185 iter_ptr.as_mut::<BTreeMapIterator<'_, K, V>>();
186 state.next_back().map(|(key, value)| {
187 (PtrConst::new(key), PtrConst::new(value))
188 })
189 })
190 .dealloc(|iter_ptr| unsafe {
191 drop(Box::from_raw(
192 iter_ptr.as_ptr::<BTreeMapIterator<'_, K, V>>()
193 as *mut BTreeMapIterator<'_, K, V>,
194 ))
195 })
196 .build(),
197 )
198 .build()
199 },
200 )
201 .build(),
202 ))
203 .build()
204 };
205}