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