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