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