rune/hashbrown/
table.rs

Help
1use rune_alloc::hash_map;
2
3use core::hash::BuildHasher;
4use core::iter;
5use core::marker::PhantomData;
6use core::mem;
7use core::ptr;
8
9use crate::alloc;
10use crate::alloc::prelude::*;
11
12#[cfg(feature = "alloc")]
13use crate::runtime::Hasher;
14use crate::runtime::{ProtocolCaller, RawAnyGuard, Ref, Value, VmError, VmResult};
15
16use crate::alloc::hashbrown::raw::{RawIter, RawTable};
17use crate::alloc::hashbrown::ErrorOrInsertSlot;
18
19pub(crate) struct Table<V> {
20    table: RawTable<(Value, V)>,
21    state: hash_map::RandomState,
22}
23
24impl<V> Table<V> {
25    #[inline(always)]
26    pub(crate) fn new() -> Self {
27        Self {
28            table: RawTable::new(),
29            state: hash_map::RandomState::new(),
30        }
31    }
32
33    #[inline(always)]
34    pub(crate) fn try_with_capacity(capacity: usize) -> alloc::Result<Self> {
35        Ok(Self {
36            table: RawTable::try_with_capacity(capacity)?,
37            state: hash_map::RandomState::new(),
38        })
39    }
40
41    #[inline(always)]
42    pub(crate) fn len(&self) -> usize {
43        self.table.len()
44    }
45
46    #[inline(always)]
47    pub(crate) fn capacity(&self) -> usize {
48        self.table.capacity()
49    }
50
51    #[inline(always)]
52    pub(crate) fn is_empty(&self) -> bool {
53        self.table.is_empty()
54    }
55
56    #[inline(always)]
57    pub(crate) fn insert_with(
58        &mut self,
59        key: Value,
60        value: V,
61        caller: &mut dyn ProtocolCaller,
62    ) -> VmResult<Option<V>> {
63        let hash = vm_try!(hash(&self.state, &key, caller));
64
65        let existing = match self.table.find_or_find_insert_slot(
66            caller,
67            hash,
68            KeyEq::new(&key),
69            StateHasher::new(&self.state),
70        ) {
71            Ok(bucket) => Some(mem::replace(unsafe { &mut bucket.as_mut().1 }, value)),
72            Err(ErrorOrInsertSlot::InsertSlot(slot)) => {
73                unsafe {
74                    self.table.insert_in_slot(hash, slot, (key, value));
75                }
76                None
77            }
78            Err(ErrorOrInsertSlot::Error(error)) => return VmResult::err(error),
79        };
80
81        VmResult::Ok(existing)
82    }
83
84    pub(crate) fn get(
85        &self,
86        key: &Value,
87        caller: &mut dyn ProtocolCaller,
88    ) -> VmResult<Option<&(Value, V)>> {
89        if self.table.is_empty() {
90            return VmResult::Ok(None);
91        }
92
93        let hash = vm_try!(hash(&self.state, key, caller));
94        VmResult::Ok(vm_try!(self.table.get(caller, hash, KeyEq::new(key))))
95    }
96
97    #[inline(always)]
98    pub(crate) fn remove_with(
99        &mut self,
100        key: &Value,
101        caller: &mut dyn ProtocolCaller,
102    ) -> VmResult<Option<V>> {
103        let hash = vm_try!(hash(&self.state, key, caller));
104
105        match self.table.remove_entry(caller, hash, KeyEq::new(key)) {
106            Ok(value) => VmResult::Ok(value.map(|(_, value)| value)),
107            Err(error) => VmResult::Err(error),
108        }
109    }
110
111    #[inline(always)]
112    pub(crate) fn clear(&mut self) {
113        self.table.clear()
114    }
115
116    pub(crate) fn iter(&self) -> Iter<'_, V> {
117        // SAFETY: lifetime is held by returned iterator.
118        let iter = unsafe { self.table.iter() };
119
120        Iter {
121            iter,
122            _marker: PhantomData,
123        }
124    }
125
126    #[inline(always)]
127    pub(crate) fn iter_ref(this: Ref<Self>) -> IterRef<V> {
128        let (this, _guard) = Ref::into_raw(this);
129        // SAFETY: Table will be alive and a reference to it held for as long as
130        // `RawAnyGuard` is alive.
131        let iter = unsafe { this.as_ref().table.iter() };
132        IterRef {
133            iter,
134            guard: _guard,
135        }
136    }
137
138    #[inline(always)]
139    pub(crate) unsafe fn iter_ref_raw(this: ptr::NonNull<Table<V>>) -> RawIter<(Value, V)> {
140        this.as_ref().table.iter()
141    }
142
143    #[inline(always)]
144    pub(crate) fn keys_ref(this: Ref<Self>) -> KeysRef<V> {
145        let (this, _guard) = Ref::into_raw(this);
146        // SAFETY: Table will be alive and a reference to it held for as long as
147        // `RawAnyGuard` is alive.
148        let iter = unsafe { this.as_ref().table.iter() };
149        KeysRef {
150            iter,
151            guard: _guard,
152        }
153    }
154
155    #[inline(always)]
156    pub(crate) fn values_ref(this: Ref<Self>) -> ValuesRef<V> {
157        let (this, _guard) = Ref::into_raw(this);
158        // SAFETY: Table will be alive and a reference to it held for as long as
159        // `RawAnyGuard` is alive.
160        let iter = unsafe { this.as_ref().table.iter() };
161        ValuesRef {
162            iter,
163            guard: _guard,
164        }
165    }
166}
167
168impl<V> TryClone for Table<V>
169where
170    V: TryClone,
171{
172    fn try_clone(&self) -> alloc::Result<Self> {
173        Ok(Self {
174            table: self.table.try_clone()?,
175            state: self.state.clone(),
176        })
177    }
178
179    #[inline]
180    fn try_clone_from(&mut self, source: &Self) -> alloc::Result<()> {
181        self.table.try_clone_from(&source.table)
182    }
183}
184
185pub(crate) struct Iter<'a, V> {
186    iter: RawIter<(Value, V)>,
187    _marker: PhantomData<&'a V>,
188}
189
190impl<'a, V> iter::Iterator for Iter<'a, V> {
191    type Item = &'a (Value, V);
192
193    #[inline]
194    fn next(&mut self) -> Option<Self::Item> {
195        // SAFETY: we're still holding onto the `RawAnyGuard` guard.
196        unsafe { Some(self.iter.next()?.as_ref()) }
197    }
198
199    #[inline]
200    fn size_hint(&self) -> (usize, Option<usize>) {
201        self.iter.size_hint()
202    }
203}
204
205pub(crate) struct IterRef<V> {
206    iter: RawIter<(Value, V)>,
207    #[allow(unused)]
208    guard: RawAnyGuard,
209}
210
211impl<V> iter::Iterator for IterRef<V>
212where
213    V: Clone,
214{
215    type Item = (Value, V);
216
217    #[inline]
218    fn next(&mut self) -> Option<Self::Item> {
219        // SAFETY: we're still holding onto the `RawAnyGuard` guard.
220        unsafe { Some(self.iter.next()?.as_ref().clone()) }
221    }
222
223    #[inline]
224    fn size_hint(&self) -> (usize, Option<usize>) {
225        self.iter.size_hint()
226    }
227}
228
229impl<V> iter::ExactSizeIterator for IterRef<V>
230where
231    V: Clone,
232{
233    #[inline]
234    fn len(&self) -> usize {
235        self.iter.len()
236    }
237}
238
239pub(crate) struct KeysRef<V> {
240    iter: RawIter<(Value, V)>,
241    #[allow(unused)]
242    guard: RawAnyGuard,
243}
244
245impl<V> iter::Iterator for KeysRef<V> {
246    type Item = Value;
247
248    #[inline]
249    fn next(&mut self) -> Option<Self::Item> {
250        // SAFETY: we're still holding onto the `RawAnyGuard` guard.
251        unsafe { Some(self.iter.next()?.as_ref().0.clone()) }
252    }
253
254    #[inline]
255    fn size_hint(&self) -> (usize, Option<usize>) {
256        self.iter.size_hint()
257    }
258}
259
260pub(crate) struct ValuesRef<V> {
261    iter: RawIter<(Value, V)>,
262    #[allow(unused)]
263    guard: RawAnyGuard,
264}
265
266impl<V> iter::Iterator for ValuesRef<V>
267where
268    V: Clone,
269{
270    type Item = V;
271
272    #[inline]
273    fn next(&mut self) -> Option<Self::Item> {
274        // SAFETY: we're still holding onto the `RawAnyGuard` guard.
275        unsafe { Some(self.iter.next()?.as_ref().1.clone()) }
276    }
277
278    #[inline]
279    fn size_hint(&self) -> (usize, Option<usize>) {
280        self.iter.size_hint()
281    }
282}
283
284/// Convenience function to hash a value.
285fn hash<S>(state: &S, value: &Value, caller: &mut dyn ProtocolCaller) -> VmResult<u64>
286where
287    S: BuildHasher<Hasher = hash_map::Hasher>,
288{
289    let mut hasher = Hasher::new_with(state);
290    vm_try!(value.hash_with(&mut hasher, caller));
291    VmResult::Ok(hasher.finish())
292}
293
294struct StateHasher<'a> {
295    state: &'a hash_map::RandomState,
296}
297
298impl<'a> StateHasher<'a> {
299    #[inline]
300    fn new(state: &'a hash_map::RandomState) -> Self {
301        Self { state }
302    }
303}
304
305impl<V> alloc::hashbrown::HasherFn<dyn ProtocolCaller, (Value, V), VmError> for StateHasher<'_> {
306    #[inline]
307    fn hash(&self, cx: &mut dyn ProtocolCaller, (key, _): &(Value, V)) -> Result<u64, VmError> {
308        hash(self.state, key, cx).into_result()
309    }
310}
311
312/// Construct an equality function for a value in the table that will compare an
313/// entry with the current key.
314struct KeyEq<'a> {
315    key: &'a Value,
316}
317
318impl<'a> KeyEq<'a> {
319    #[inline]
320    fn new(key: &'a Value) -> Self {
321        Self { key }
322    }
323}
324
325impl<V> alloc::hashbrown::EqFn<dyn ProtocolCaller, (Value, V), VmError> for KeyEq<'_> {
326    #[inline]
327    fn eq(&self, cx: &mut dyn ProtocolCaller, (other, _): &(Value, V)) -> Result<bool, VmError> {
328        self.key.eq_with(other, cx).into_result()
329    }
330}
rune/hashbrown/table.rs

rune/hashbrown/
table.rs
