rune_alloc/hashbrown/
mod.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
//! This is a fork of the [`hashbrown` crate].
//!
//! It's been modified to make use of the memory utilities provided by rune
//! alloc.
//!
//! This is a Rust port of Google's high-performance [SwissTable] hash map,
//! adapted to make it a drop-in replacement for Rust's standard `HashMap` and
//! `HashSet` types.
//!
//! The original C++ version of [SwissTable] can be found [here], and this
//! [CppCon talk] gives an overview of how the algorithm works.
//!
//! [`hashbrown` crate]: https://docs.rs/hashbrown
//! [SwissTable]: https://abseil.io/blog/20180927-swisstables
//! [here]:
//!     https://github.com/abseil/abseil-cpp/blob/master/absl/container/internal/raw_hash_set.h
//! [CppCon talk]: https://www.youtube.com/watch?v=ncHmEUmJZf4

// For copyright notice, see lib.rs

#![allow(clippy::missing_safety_doc)]

pub mod raw;

#[cfg(feature = "serde")]
mod serde;

mod scopeguard;

#[doc(hidden)]
pub use self::map::HashMap;
#[doc(hidden)]
pub mod map;

#[doc(hidden)]
pub use self::set::HashSet;
#[doc(hidden)]
pub mod set;

use core::marker::PhantomData;

use crate::error::CustomError;

/// Trait used to implement custom equality implementations which are not solely
/// based on traits.
pub trait EqFn<C: ?Sized, T: ?Sized, E> {
    fn eq(&self, cx: &mut C, key: &T) -> Result<bool, E>;

    #[doc(hidden)]
    fn into_tuple<V>(self) -> TupleFn<Self, V>
    where
        Self: Sized,
    {
        TupleFn {
            this: self,
            _marker: PhantomData,
        }
    }
}

impl<U, C: ?Sized, T: ?Sized, E> EqFn<C, T, E> for U
where
    U: Fn(&mut C, &T) -> Result<bool, E>,
{
    #[inline]
    fn eq(&self, cx: &mut C, key: &T) -> Result<bool, E> {
        self(cx, key)
    }
}

/// Trait used to implement custom hash implementations which are not solely
/// based on traits.
pub trait HasherFn<C: ?Sized, T: ?Sized, E> {
    fn hash(&self, cx: &mut C, key: &T) -> Result<u64, E>;

    #[doc(hidden)]
    fn into_tuple<V>(self) -> TupleFn<Self, V>
    where
        Self: Sized,
    {
        TupleFn {
            this: self,
            _marker: PhantomData,
        }
    }
}

impl<U, C: ?Sized, T: ?Sized, E> HasherFn<C, T, E> for U
where
    U: Fn(&mut C, &T) -> Result<u64, E>,
{
    #[inline]
    fn hash(&self, cx: &mut C, key: &T) -> Result<u64, E> {
        self(cx, key)
    }
}

/// Adapter for [`HasherFn`] for hashing tuples.
pub struct TupleFn<T, V> {
    this: T,
    _marker: PhantomData<V>,
}

impl<T, C: ?Sized, K, V, E> EqFn<C, (K, V), E> for TupleFn<T, V>
where
    T: EqFn<C, K, E>,
{
    #[inline]
    fn eq(&self, cx: &mut C, (key, _): &(K, V)) -> Result<bool, E> {
        self.this.eq(cx, key)
    }
}

impl<T, C: ?Sized, K, V, E> HasherFn<C, (K, V), E> for TupleFn<T, V>
where
    T: HasherFn<C, K, E>,
{
    #[inline]
    fn hash(&self, cx: &mut C, (key, _): &(K, V)) -> Result<u64, E> {
        self.this.hash(cx, key)
    }
}

/// Error raised by [`RawTable::find_or_find_insert_slot`].
///
/// [`RawTable::find_or_find_insert_slot`]:
///     crate::hashbrown::raw::RawTable::find_or_find_insert_slot
pub enum ErrorOrInsertSlot<E> {
    /// An error was returned.
    Error(CustomError<E>),
    /// A return slot was inserted.
    InsertSlot(raw::InsertSlot),
}

impl<E> From<CustomError<E>> for ErrorOrInsertSlot<E> {
    #[inline]
    fn from(error: CustomError<E>) -> Self {
        Self::Error(error)
    }
}

/// Key equivalence trait.
///
/// This trait defines the function used to compare the input value with the map
/// keys (or set values) during a lookup operation such as [`HashMap::get`] or
/// [`HashSet::contains`]. It is provided with a blanket implementation based on
/// the [`Borrow`](core::borrow::Borrow) trait.
///
/// # Correctness
///
/// Equivalent values must hash to the same value.
pub trait Equivalent<K: ?Sized> {
    /// Checks if this value is equivalent to the given key.
    ///
    /// Returns `true` if both values are equivalent, and `false` otherwise.
    ///
    /// # Correctness
    ///
    /// When this function returns `true`, both `self` and `key` must hash to
    /// the same value.
    fn equivalent(&self, key: &K) -> bool;
}

impl<Q, K> Equivalent<K> for Q
where
    Q: ?Sized + Eq,
    K: ?Sized + core::borrow::Borrow<Q>,
{
    #[inline]
    fn equivalent(&self, key: &K) -> bool {
        self == key.borrow()
    }
}