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

facet_core/impls/std/
hashmap.rs
