rune_alloc/hashbrown/
mod.rs

Help
1//! This is a fork of the [`hashbrown` crate].
2//!
3//! It's been modified to make use of the memory utilities provided by rune
4//! alloc.
5//!
6//! This is a Rust port of Google's high-performance [SwissTable] hash map,
7//! adapted to make it a drop-in replacement for Rust's standard `HashMap` and
8//! `HashSet` types.
9//!
10//! The original C++ version of [SwissTable] can be found [here], and this
11//! [CppCon talk] gives an overview of how the algorithm works.
12//!
13//! [`hashbrown` crate]: https://docs.rs/hashbrown
14//! [SwissTable]: https://abseil.io/blog/20180927-swisstables
15//! [here]:
16//!     https://github.com/abseil/abseil-cpp/blob/master/absl/container/internal/raw_hash_set.h
17//! [CppCon talk]: https://www.youtube.com/watch?v=ncHmEUmJZf4
18
19// For copyright notice, see lib.rs
20
21#![allow(clippy::missing_safety_doc)]
22
23pub mod raw;
24
25#[cfg(feature = "serde")]
26mod serde;
27
28mod scopeguard;
29
30#[doc(hidden)]
31pub use self::map::HashMap;
32#[doc(hidden)]
33pub mod map;
34
35#[doc(hidden)]
36pub use self::set::HashSet;
37#[doc(hidden)]
38pub mod set;
39
40use core::marker::PhantomData;
41
42use crate::error::CustomError;
43
44/// Trait used to implement custom equality implementations which are not solely
45/// based on traits.
46pub trait EqFn<C: ?Sized, T: ?Sized, E> {
47    fn eq(&self, cx: &mut C, key: &T) -> Result<bool, E>;
48
49    #[doc(hidden)]
50    fn into_tuple<V>(self) -> TupleFn<Self, V>
51    where
52        Self: Sized,
53    {
54        TupleFn {
55            this: self,
56            _marker: PhantomData,
57        }
58    }
59}
60
61impl<U, C: ?Sized, T: ?Sized, E> EqFn<C, T, E> for U
62where
63    U: Fn(&mut C, &T) -> Result<bool, E>,
64{
65    #[inline]
66    fn eq(&self, cx: &mut C, key: &T) -> Result<bool, E> {
67        self(cx, key)
68    }
69}
70
71/// Trait used to implement custom hash implementations which are not solely
72/// based on traits.
73pub trait HasherFn<C: ?Sized, T: ?Sized, E> {
74    fn hash(&self, cx: &mut C, key: &T) -> Result<u64, E>;
75
76    #[doc(hidden)]
77    fn into_tuple<V>(self) -> TupleFn<Self, V>
78    where
79        Self: Sized,
80    {
81        TupleFn {
82            this: self,
83            _marker: PhantomData,
84        }
85    }
86}
87
88impl<U, C: ?Sized, T: ?Sized, E> HasherFn<C, T, E> for U
89where
90    U: Fn(&mut C, &T) -> Result<u64, E>,
91{
92    #[inline]
93    fn hash(&self, cx: &mut C, key: &T) -> Result<u64, E> {
94        self(cx, key)
95    }
96}
97
98/// Adapter for [`HasherFn`] for hashing tuples.
99pub struct TupleFn<T, V> {
100    this: T,
101    _marker: PhantomData<V>,
102}
103
104impl<T, C: ?Sized, K, V, E> EqFn<C, (K, V), E> for TupleFn<T, V>
105where
106    T: EqFn<C, K, E>,
107{
108    #[inline]
109    fn eq(&self, cx: &mut C, (key, _): &(K, V)) -> Result<bool, E> {
110        self.this.eq(cx, key)
111    }
112}
113
114impl<T, C: ?Sized, K, V, E> HasherFn<C, (K, V), E> for TupleFn<T, V>
115where
116    T: HasherFn<C, K, E>,
117{
118    #[inline]
119    fn hash(&self, cx: &mut C, (key, _): &(K, V)) -> Result<u64, E> {
120        self.this.hash(cx, key)
121    }
122}
123
124/// Error raised by [`RawTable::find_or_find_insert_slot`].
125///
126/// [`RawTable::find_or_find_insert_slot`]:
127///     crate::hashbrown::raw::RawTable::find_or_find_insert_slot
128pub enum ErrorOrInsertSlot<E> {
129    /// An error was returned.
130    Error(CustomError<E>),
131    /// A return slot was inserted.
132    InsertSlot(raw::InsertSlot),
133}
134
135impl<E> From<CustomError<E>> for ErrorOrInsertSlot<E> {
136    #[inline]
137    fn from(error: CustomError<E>) -> Self {
138        Self::Error(error)
139    }
140}
141
142/// Key equivalence trait.
143///
144/// This trait defines the function used to compare the input value with the map
145/// keys (or set values) during a lookup operation such as [`HashMap::get`] or
146/// [`HashSet::contains`]. It is provided with a blanket implementation based on
147/// the [`Borrow`](core::borrow::Borrow) trait.
148///
149/// # Correctness
150///
151/// Equivalent values must hash to the same value.
152pub trait Equivalent<K: ?Sized> {
153    /// Checks if this value is equivalent to the given key.
154    ///
155    /// Returns `true` if both values are equivalent, and `false` otherwise.
156    ///
157    /// # Correctness
158    ///
159    /// When this function returns `true`, both `self` and `key` must hash to
160    /// the same value.
161    fn equivalent(&self, key: &K) -> bool;
162}
163
164impl<Q, K> Equivalent<K> for Q
165where
166    Q: ?Sized + Eq,
167    K: ?Sized + core::borrow::Borrow<Q>,
168{
169    #[inline]
170    fn equivalent(&self, key: &K) -> bool {
171        self == key.borrow()
172    }
173}
rune_alloc/hashbrown/mod.rs

rune_alloc/hashbrown/
mod.rs
