1use alloc::collections::VecDeque;
2use core::hash::{BuildHasher, Hash};
3use std::collections::HashMap;
4use std::hash::RandomState;
5
6use crate::ptr::{PtrConst, PtrMut};
7
8use crate::{
9 Def, Facet, MapDef, MapIterVTable, MapVTable, MarkerTraits, ScalarAffinity, ScalarDef, Shape,
10 Type, TypeParam, UserType, VTableView, ValueVTable, value_vtable,
11};
12
13struct HashMapIterator<'mem, K> {
14 map: PtrConst<'mem>,
15 keys: VecDeque<&'mem K>,
16}
17
18unsafe impl<'a, K, V, S> Facet<'a> for HashMap<K, V, S>
19where
20 K: Facet<'a> + core::cmp::Eq + core::hash::Hash,
21 V: Facet<'a>,
22 S: Facet<'a> + Default + BuildHasher,
23{
24 const VTABLE: &'static ValueVTable = &const {
25 let mut builder = ValueVTable::builder::<Self>()
26 .marker_traits({
27 let arg_dependent_traits = MarkerTraits::SEND
28 .union(MarkerTraits::SYNC)
29 .union(MarkerTraits::EQ)
30 .union(MarkerTraits::UNPIN);
31 arg_dependent_traits
32 .intersection(V::SHAPE.vtable.marker_traits)
33 .intersection(K::SHAPE.vtable.marker_traits)
34 })
35 .type_name(|f, opts| {
36 if let Some(opts) = opts.for_children() {
37 write!(f, "HashMap<")?;
38 (K::SHAPE.vtable.type_name)(f, opts)?;
39 write!(f, ", ")?;
40 (V::SHAPE.vtable.type_name)(f, opts)?;
41 write!(f, ">")
42 } else {
43 write!(f, "HashMap<⋯>")
44 }
45 });
46
47 if K::SHAPE.vtable.debug.is_some() && V::SHAPE.vtable.debug.is_some() {
48 builder = builder.debug(|value, f| {
49 let k_debug = <VTableView<K>>::of().debug().unwrap();
50 let v_debug = <VTableView<V>>::of().debug().unwrap();
51 write!(f, "{{")?;
52 for (i, (key, val)) in value.iter().enumerate() {
53 if i > 0 {
54 write!(f, ", ")?;
55 }
56 (k_debug)(key, f)?;
57 write!(f, ": ")?;
58 (v_debug)(val, f)?;
59 }
60 write!(f, "}}")
61 });
62 }
63
64 builder = builder.default_in_place(|target| unsafe { target.put(Self::default()) });
65
66 if V::SHAPE.vtable.clone_into.is_some() && K::SHAPE.vtable.clone_into.is_some() {
67 builder = builder.clone_into(|src, dst| unsafe {
68 let map = src;
69 let mut new_map = HashMap::with_capacity_and_hasher(map.len(), S::default());
70
71 let k_clone_into = <VTableView<K>>::of().clone_into().unwrap();
72 let v_clone_into = <VTableView<V>>::of().clone_into().unwrap();
73
74 for (k, v) in map {
75 use crate::TypedPtrUninit;
76 use core::mem::MaybeUninit;
77
78 let mut new_k = MaybeUninit::<K>::uninit();
79 let mut new_v = MaybeUninit::<V>::uninit();
80
81 let uninit_k = TypedPtrUninit::new(new_k.as_mut_ptr());
82 let uninit_v = TypedPtrUninit::new(new_v.as_mut_ptr());
83
84 (k_clone_into)(k, uninit_k);
85 (v_clone_into)(v, uninit_v);
86
87 new_map.insert(new_k.assume_init(), new_v.assume_init());
88 }
89
90 dst.put(new_map)
91 });
92 }
93
94 if V::SHAPE.vtable.eq.is_some() {
95 builder = builder.eq(|a, b| {
96 let v_eq = <VTableView<V>>::of().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 }
103
104 if V::SHAPE.vtable.hash.is_some() {
105 builder = builder.hash(|map, hasher_this, hasher_write_fn| unsafe {
106 use crate::HasherProxy;
107 let v_hash = <VTableView<V>>::of().hash().unwrap();
108 let mut hasher = HasherProxy::new(hasher_this, hasher_write_fn);
109 map.len().hash(&mut hasher);
110 for (k, v) in map {
111 k.hash(&mut hasher);
112 (v_hash)(v, hasher_this, hasher_write_fn);
113 }
114 });
115 }
116
117 builder.build()
118 };
119
120 const SHAPE: &'static Shape = &const {
121 Shape::builder_for_sized::<Self>()
122 .type_params(&[
123 TypeParam {
124 name: "K",
125 shape: || K::SHAPE,
126 },
127 TypeParam {
128 name: "V",
129 shape: || V::SHAPE,
130 },
131 TypeParam {
132 name: "S",
133 shape: || S::SHAPE,
134 },
135 ])
136 .ty(Type::User(UserType::Opaque))
137 .def(Def::Map(
138 MapDef::builder()
139 .k(|| K::SHAPE)
140 .v(|| V::SHAPE)
141 .vtable(
142 &const {
143 MapVTable::builder()
144 .init_in_place_with_capacity(|uninit, capacity| unsafe {
145 uninit
146 .put(Self::with_capacity_and_hasher(capacity, S::default()))
147 })
148 .insert(|ptr, key, value| unsafe {
149 let map = ptr.as_mut::<HashMap<K, V>>();
150 let key = key.read::<K>();
151 let value = value.read::<V>();
152 map.insert(key, value);
153 })
154 .len(|ptr| unsafe {
155 let map = ptr.get::<HashMap<K, V>>();
156 map.len()
157 })
158 .contains_key(|ptr, key| unsafe {
159 let map = ptr.get::<HashMap<K, V>>();
160 map.contains_key(key.get())
161 })
162 .get_value_ptr(|ptr, key| unsafe {
163 let map = ptr.get::<HashMap<K, V>>();
164 map.get(key.get()).map(|v| PtrConst::new(v))
165 })
166 .iter(|ptr| unsafe {
167 let map = ptr.get::<HashMap<K, V>>();
168 let keys: VecDeque<&K> = map.keys().collect();
169 let iter_state = Box::new(HashMapIterator { map: ptr, keys });
170 PtrMut::new(Box::into_raw(iter_state) as *mut u8)
171 })
172 .iter_vtable(
173 MapIterVTable::builder()
174 .next(|iter_ptr| unsafe {
175 let state = iter_ptr.as_mut::<HashMapIterator<'_, K>>();
176 let map = state.map.get::<HashMap<K, V>>();
177 while let Some(key) = state.keys.pop_front() {
178 if let Some(value) = map.get(key) {
179 return Some((
180 PtrConst::new(key as *const K),
181 PtrConst::new(value as *const V),
182 ));
183 }
184 }
185
186 None
187 })
188 .next_back(|iter_ptr| unsafe {
189 let state = iter_ptr.as_mut::<HashMapIterator<'_, K>>();
190 let map = state.map.get::<HashMap<K, V>>();
191 while let Some(key) = state.keys.pop_back() {
192 if let Some(value) = map.get(key) {
193 return Some((
194 PtrConst::new(key as *const K),
195 PtrConst::new(value as *const V),
196 ));
197 }
198 }
199
200 None
201 })
202 .dealloc(|iter_ptr| unsafe {
203 drop(Box::from_raw(
204 iter_ptr.as_ptr::<HashMapIterator<'_, K>>()
205 as *mut HashMapIterator<'_, K>,
206 ));
207 })
208 .build(),
209 )
210 .build()
211 },
212 )
213 .build(),
214 ))
215 .build()
216 };
217}
218
219unsafe impl Facet<'_> for RandomState {
220 const VTABLE: &'static ValueVTable =
221 &const { value_vtable!((), |f, _opts| write!(f, "RandomState")) };
222
223 const SHAPE: &'static Shape = &const {
224 Shape::builder_for_sized::<Self>()
225 .ty(Type::User(UserType::Opaque))
226 .def(Def::Scalar(
227 ScalarDef::builder()
228 .affinity(ScalarAffinity::opaque().build())
229 .build(),
230 ))
231 .build()
232 };
233}