facet_core/impls/std/
hashmap.rs

1use core::hash::BuildHasher;
2use core::ptr::NonNull;
3use std::collections::HashMap;
4use std::hash::RandomState;
5
6use crate::{PtrConst, PtrMut, PtrUninit};
7
8use crate::{
9    Def, Facet, IterVTable, MapDef, MapVTable, Shape, ShapeBuilder, Type, TypeNameFn, TypeNameOpts,
10    TypeOpsIndirect, TypeParam, UserType, VTableDirect, VTableIndirect, Variance, VarianceDep,
11    VarianceDesc,
12};
13
14type HashMapIterator<'mem, K, V> = std::collections::hash_map::Iter<'mem, K, V>;
15
16unsafe extern "C" fn hashmap_init_in_place_with_capacity<K, V, S: Default + BuildHasher>(
17    uninit: PtrUninit,
18    capacity: usize,
19) -> PtrMut {
20    unsafe {
21        uninit.put(HashMap::<K, V, S>::with_capacity_and_hasher(
22            capacity,
23            S::default(),
24        ))
25    }
26}
27
28unsafe extern "C" fn hashmap_insert<K: Eq + core::hash::Hash, V>(
29    ptr: PtrMut,
30    key: PtrMut,
31    value: PtrMut,
32) {
33    let map = unsafe { ptr.as_mut::<HashMap<K, V>>() };
34    let key = unsafe { key.read::<K>() };
35    let value = unsafe { value.read::<V>() };
36    map.insert(key, value);
37}
38
39unsafe extern "C" fn hashmap_len<K, V>(ptr: PtrConst) -> usize {
40    unsafe { ptr.get::<HashMap<K, V>>().len() }
41}
42
43unsafe extern "C" fn hashmap_contains_key<K: Eq + core::hash::Hash, V>(
44    ptr: PtrConst,
45    key: PtrConst,
46) -> bool {
47    unsafe { ptr.get::<HashMap<K, V>>().contains_key(key.get()) }
48}
49
50unsafe extern "C" fn hashmap_get_value_ptr<K: Eq + core::hash::Hash, V>(
51    ptr: PtrConst,
52    key: PtrConst,
53) -> *const u8 {
54    unsafe {
55        ptr.get::<HashMap<K, V>>()
56            .get(key.get())
57            .map_or(core::ptr::null(), |v| {
58                NonNull::from(v).as_ptr() as *const u8
59            })
60    }
61}
62
63/// Build a HashMap from a contiguous slice of (K, V) pairs.
64///
65/// This uses `from_iter` with known capacity to avoid rehashing.
66unsafe extern "C" fn hashmap_from_pair_slice<
67    K: Eq + core::hash::Hash,
68    V,
69    S: Default + BuildHasher,
70>(
71    uninit: PtrUninit,
72    pairs_ptr: *mut u8,
73    count: usize,
74) -> PtrMut {
75    // Create an iterator that reads and moves (K, V) pairs from the buffer
76    let pairs = pairs_ptr as *mut (K, V);
77    let iter = (0..count).map(|i| unsafe {
78        let pair_ptr = pairs.add(i);
79        core::ptr::read(pair_ptr)
80    });
81
82    // Build HashMap with from_iter (which uses reserve internally)
83    let map: HashMap<K, V, S> = iter.collect();
84    unsafe { uninit.put(map) }
85}
86
87unsafe extern "C" fn hashmap_iter_init<K, V>(ptr: PtrConst) -> PtrMut {
88    unsafe {
89        let map = ptr.get::<HashMap<K, V>>();
90        let iter: HashMapIterator<'_, K, V> = map.iter();
91        let iter_state = Box::new(iter);
92        PtrMut::new(Box::into_raw(iter_state) as *mut u8)
93    }
94}
95
96unsafe fn hashmap_iter_next<K, V>(iter_ptr: PtrMut) -> Option<(PtrConst, PtrConst)> {
97    unsafe {
98        // SAFETY: We're extending the lifetime from '_ to 'static through a raw pointer cast.
99        // This is sound because:
100        // 1. The iterator was allocated in hashmap_iter_init and lives until hashmap_iter_dealloc
101        // 2. We only return pointers (PtrConst), not references with the extended lifetime
102        // 3. The actual lifetime of the data is managed by the HashMap, not this iterator
103        let ptr = iter_ptr.as_mut_ptr::<HashMapIterator<'_, K, V>>();
104        let state = &mut *ptr;
105        state.next().map(|(key, value)| {
106            (
107                PtrConst::new(NonNull::from(key).as_ptr()),
108                PtrConst::new(NonNull::from(value).as_ptr()),
109            )
110        })
111    }
112}
113
114unsafe extern "C" fn hashmap_iter_dealloc<K, V>(iter_ptr: PtrMut) {
115    unsafe {
116        drop(Box::from_raw(
117            iter_ptr.as_ptr::<HashMapIterator<'_, K, V>>() as *mut HashMapIterator<'_, K, V>,
118        ));
119    }
120}
121
122unsafe fn hashmap_drop<K, V, S>(ox: crate::OxPtrMut) {
123    unsafe {
124        core::ptr::drop_in_place(ox.as_mut::<HashMap<K, V, S>>());
125    }
126}
127
128unsafe fn hashmap_default<K, V, S: Default + BuildHasher>(ox: crate::OxPtrUninit) -> bool {
129    unsafe { ox.put(HashMap::<K, V, S>::default()) };
130    true
131}
132
133unsafe fn hashmap_is_truthy<K, V>(ptr: PtrConst) -> bool {
134    !unsafe { ptr.get::<HashMap<K, V>>().is_empty() }
135}
136
137// TODO: Debug, PartialEq, Eq for HashMap, HashSet
138unsafe impl<'a, K, V, S> Facet<'a> for HashMap<K, V, S>
139where
140    K: Facet<'a> + core::cmp::Eq + core::hash::Hash,
141    V: Facet<'a>,
142    S: 'a + Default + BuildHasher,
143{
144    const SHAPE: &'static Shape = &const {
145        const fn build_map_vtable<K: Eq + core::hash::Hash, V, S: Default + BuildHasher>()
146        -> MapVTable {
147            MapVTable::builder()
148                .init_in_place_with_capacity(hashmap_init_in_place_with_capacity::<K, V, S>)
149                .insert(hashmap_insert::<K, V>)
150                .len(hashmap_len::<K, V>)
151                .contains_key(hashmap_contains_key::<K, V>)
152                .get_value_ptr(hashmap_get_value_ptr::<K, V>)
153                .iter_vtable(IterVTable {
154                    init_with_value: Some(hashmap_iter_init::<K, V>),
155                    next: hashmap_iter_next::<K, V>,
156                    next_back: None,
157                    size_hint: None,
158                    dealloc: hashmap_iter_dealloc::<K, V>,
159                })
160                .from_pair_slice(Some(hashmap_from_pair_slice::<K, V, S>))
161                .pair_stride(core::mem::size_of::<(K, V)>())
162                .value_offset_in_pair(core::mem::offset_of!((K, V), 1))
163                .build()
164        }
165
166        const fn build_type_name<'a, K: Facet<'a>, V: Facet<'a>>() -> TypeNameFn {
167            fn type_name_impl<'a, K: Facet<'a>, V: Facet<'a>>(
168                _shape: &'static Shape,
169                f: &mut core::fmt::Formatter<'_>,
170                opts: TypeNameOpts,
171            ) -> core::fmt::Result {
172                write!(f, "HashMap")?;
173                if let Some(opts) = opts.for_children() {
174                    write!(f, "<")?;
175                    K::SHAPE.write_type_name(f, opts)?;
176                    write!(f, ", ")?;
177                    V::SHAPE.write_type_name(f, opts)?;
178                    write!(f, ">")?;
179                } else {
180                    write!(f, "<…>")?;
181                }
182                Ok(())
183            }
184            type_name_impl::<K, V>
185        }
186
187        ShapeBuilder::for_sized::<Self>("HashMap")
188            .module_path("std::collections::hash_map")
189            .type_name(build_type_name::<K, V>())
190            .ty(Type::User(UserType::Opaque))
191            .def(Def::Map(MapDef {
192                vtable: &const { build_map_vtable::<K, V, S>() },
193                k: K::SHAPE,
194                v: V::SHAPE,
195            }))
196            .type_params(&[
197                TypeParam {
198                    name: "K",
199                    shape: K::SHAPE,
200                },
201                TypeParam {
202                    name: "V",
203                    shape: V::SHAPE,
204                },
205            ])
206            // HashMap<K, V> combines K and V variances
207            .variance(VarianceDesc {
208                base: Variance::Bivariant,
209                deps: &const {
210                    [
211                        VarianceDep::covariant(K::SHAPE),
212                        VarianceDep::covariant(V::SHAPE),
213                    ]
214                },
215            })
216            .vtable_indirect(&VTableIndirect::EMPTY)
217            .type_ops_indirect(
218                &const {
219                    TypeOpsIndirect {
220                        drop_in_place: hashmap_drop::<K, V, S>,
221                        default_in_place: Some(hashmap_default::<K, V, S>),
222                        clone_into: None,
223                        is_truthy: Some(hashmap_is_truthy::<K, V>),
224                    }
225                },
226            )
227            .build()
228    };
229}
230
231unsafe impl Facet<'_> for RandomState {
232    const SHAPE: &'static Shape = &const {
233        const VTABLE: VTableDirect = VTableDirect::empty();
234
235        ShapeBuilder::for_sized::<Self>("RandomState")
236            .module_path("std::hash")
237            .ty(Type::User(UserType::Opaque))
238            .def(Def::Scalar)
239            .vtable_direct(&VTABLE)
240            .build()
241    };
242}
facet_core/impls/std/hashmap.rs

facet_core/impls/std/
hashmap.rs
