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