facet_core/impls/alloc/
btreemap.rs

1use alloc::{boxed::Box, collections::BTreeMap};
2
3use crate::{
4    Def, Facet, IterVTable, MapDef, MapVTable, PtrConst, PtrMut, PtrUninit, Shape, ShapeBuilder,
5    TypeNameFn, TypeNameOpts, TypeParam, VTableIndirect,
6};
7
8type BTreeMapIterator<'mem, K, V> = alloc::collections::btree_map::Iter<'mem, K, V>;
9
10unsafe fn btreemap_init_in_place_with_capacity<K, V>(
11    uninit: PtrUninit,
12    _capacity: usize,
13) -> PtrMut {
14    unsafe { uninit.put(BTreeMap::<K, V>::new()) }
15}
16
17unsafe fn btreemap_insert<K: Eq + Ord + 'static, V: 'static>(
18    ptr: PtrMut,
19    key: PtrMut,
20    value: PtrMut,
21) {
22    unsafe {
23        let map = ptr.as_mut::<BTreeMap<K, V>>();
24        let k = key.read::<K>();
25        let v = value.read::<V>();
26        map.insert(k, v);
27    }
28}
29
30unsafe fn btreemap_len<K: 'static, V: 'static>(ptr: PtrConst) -> usize {
31    unsafe { ptr.get::<BTreeMap<K, V>>().len() }
32}
33
34unsafe fn btreemap_contains_key<K: Eq + Ord + 'static, V: 'static>(
35    ptr: PtrConst,
36    key: PtrConst,
37) -> bool {
38    unsafe { ptr.get::<BTreeMap<K, V>>().contains_key(key.get()) }
39}
40
41unsafe fn btreemap_get_value_ptr<K: Eq + Ord + 'static, V: 'static>(
42    ptr: PtrConst,
43    key: PtrConst,
44) -> Option<PtrConst> {
45    unsafe {
46        ptr.get::<BTreeMap<K, V>>()
47            .get(key.get())
48            .map(|v| PtrConst::new(v as *const V))
49    }
50}
51
52unsafe fn btreemap_iter_init<K: 'static, V: 'static>(ptr: PtrConst) -> PtrMut {
53    unsafe {
54        let map = ptr.get::<BTreeMap<K, V>>();
55        let iter: BTreeMapIterator<'_, K, V> = map.iter();
56        let state = Box::new(iter);
57        PtrMut::new(Box::into_raw(state) as *mut u8)
58    }
59}
60
61unsafe fn btreemap_iter_next<K: 'static, V: 'static>(
62    iter_ptr: PtrMut,
63) -> Option<(PtrConst, PtrConst)> {
64    unsafe {
65        let state = iter_ptr.as_mut::<BTreeMapIterator<'static, K, V>>();
66        state.next().map(|(key, value)| {
67            (
68                PtrConst::new(key as *const K),
69                PtrConst::new(value as *const V),
70            )
71        })
72    }
73}
74
75unsafe fn btreemap_iter_next_back<K: 'static, V: 'static>(
76    iter_ptr: PtrMut,
77) -> Option<(PtrConst, PtrConst)> {
78    unsafe {
79        let state = iter_ptr.as_mut::<BTreeMapIterator<'static, K, V>>();
80        state.next_back().map(|(key, value)| {
81            (
82                PtrConst::new(key as *const K),
83                PtrConst::new(value as *const V),
84            )
85        })
86    }
87}
88
89unsafe fn btreemap_iter_dealloc<K, V>(iter_ptr: PtrMut) {
90    unsafe {
91        drop(Box::from_raw(
92            iter_ptr.as_ptr::<BTreeMapIterator<'_, K, V>>() as *mut BTreeMapIterator<'_, K, V>,
93        ))
94    }
95}
96
97// TODO: Debug, Hash, PartialEq, Eq, PartialOrd, Ord, for BTreeMap, BTreeSet
98unsafe impl<'a, K, V> Facet<'a> for BTreeMap<K, V>
99where
100    K: Facet<'a> + core::cmp::Eq + core::cmp::Ord + 'static,
101    V: Facet<'a> + 'static,
102{
103    const SHAPE: &'static crate::Shape = &const {
104        const fn build_map_vtable<K: Eq + Ord + 'static, V: 'static>() -> MapVTable {
105            MapVTable::builder()
106                .init_in_place_with_capacity(btreemap_init_in_place_with_capacity::<K, V>)
107                .insert(btreemap_insert::<K, V>)
108                .len(btreemap_len::<K, V>)
109                .contains_key(btreemap_contains_key::<K, V>)
110                .get_value_ptr(btreemap_get_value_ptr::<K, V>)
111                .iter_vtable(IterVTable {
112                    init_with_value: Some(btreemap_iter_init::<K, V>),
113                    next: btreemap_iter_next::<K, V>,
114                    next_back: Some(btreemap_iter_next_back::<K, V>),
115                    size_hint: None,
116                    dealloc: btreemap_iter_dealloc::<K, V>,
117                })
118                .build()
119        }
120
121        const VTABLE: VTableIndirect = VTableIndirect::EMPTY;
122
123        const fn build_type_name<'a, K: Facet<'a>, V: Facet<'a>>() -> TypeNameFn {
124            fn type_name_impl<'a, K: Facet<'a>, V: Facet<'a>>(
125                _shape: &'static Shape,
126                f: &mut core::fmt::Formatter<'_>,
127                opts: TypeNameOpts,
128            ) -> core::fmt::Result {
129                write!(f, "BTreeMap")?;
130                if let Some(opts) = opts.for_children() {
131                    write!(f, "<")?;
132                    K::SHAPE.write_type_name(f, opts)?;
133                    write!(f, ", ")?;
134                    V::SHAPE.write_type_name(f, opts)?;
135                    write!(f, ">")?;
136                } else {
137                    write!(f, "<…>")?;
138                }
139                Ok(())
140            }
141            type_name_impl::<K, V>
142        }
143
144        ShapeBuilder::for_sized::<Self>("BTreeMap")
145            .type_name(build_type_name::<K, V>())
146            .vtable_indirect(&VTABLE)
147            .def(Def::Map(MapDef::new(
148                &const { build_map_vtable::<K, V>() },
149                K::SHAPE,
150                V::SHAPE,
151            )))
152            .type_params(&[
153                TypeParam {
154                    name: "K",
155                    shape: K::SHAPE,
156                },
157                TypeParam {
158                    name: "V",
159                    shape: V::SHAPE,
160                },
161            ])
162            .build()
163    };
164}
facet_core/impls/alloc/btreemap.rs

facet_core/impls/alloc/
btreemap.rs
