hashbrown/
lib.rs

1//! This crate is a Rust port of Google's high-performance [SwissTable] hash
2//! map, adapted to make it a drop-in replacement for Rust's standard `HashMap`
3//! and `HashSet` types.
4//!
5//! The original C++ version of [SwissTable] can be found [here], and this
6//! [CppCon talk] gives an overview of how the algorithm works.
7//!
8//! [SwissTable]: https://abseil.io/blog/20180927-swisstables
9//! [here]: https://github.com/abseil/abseil-cpp/blob/master/absl/container/internal/raw_hash_set.h
10//! [CppCon talk]: https://www.youtube.com/watch?v=ncHmEUmJZf4
11
12#![cfg_attr(not(doc), no_std)]
13#![cfg_attr(
14    feature = "nightly",
15    feature(
16        core_intrinsics,
17        dropck_eyepatch,
18        min_specialization,
19        trivial_clone,
20        extend_one,
21        allocator_api,
22        strict_provenance_lints
23    )
24)]
25#![cfg_attr(feature = "nightly", warn(fuzzy_provenance_casts))]
26#![cfg_attr(feature = "rustc-dep-of-std", feature(rustc_attrs))]
27#![cfg_attr(feature = "nightly", expect(internal_features))]
28#![cfg_attr(
29    all(feature = "nightly", target_arch = "loongarch64"),
30    feature(stdarch_loongarch)
31)]
32#![cfg_attr(
33    all(feature = "nightly", feature = "default-hasher"),
34    feature(hasher_prefixfree_extras)
35)]
36
37#[cfg(test)]
38#[macro_use]
39extern crate std;
40
41#[cfg_attr(test, macro_use)]
42#[cfg_attr(feature = "rustc-dep-of-std", allow(unused_extern_crates))]
43extern crate alloc as stdalloc;
44
45#[doc = include_str!("../README.md")]
46#[cfg(doctest)]
47pub struct ReadmeDoctests;
48
49#[macro_use]
50mod macros;
51
52mod alloc;
53mod control;
54mod hasher;
55mod raw;
56mod util;
57
58mod external_trait_impls;
59mod map;
60#[cfg(feature = "raw-entry")]
61mod raw_entry;
62#[cfg(feature = "rustc-internal-api")]
63mod rustc_entry;
64mod scopeguard;
65mod set;
66mod table;
67
68pub use crate::hasher::DefaultHashBuilder;
69#[cfg(feature = "default-hasher")]
70pub use crate::hasher::DefaultHasher;
71
72pub mod hash_map {
73    //! A hash map implemented with quadratic probing and SIMD lookup.
74    pub use crate::map::*;
75
76    #[cfg(feature = "rustc-internal-api")]
77    pub use crate::rustc_entry::*;
78
79    #[cfg(feature = "rayon")]
80    /// [rayon]-based parallel iterator types for hash maps.
81    /// You will rarely need to interact with it directly unless you have need
82    /// to name one of the iterator types.
83    ///
84    /// [rayon]: ::rayon
85    pub mod rayon {
86        pub use crate::external_trait_impls::rayon::map::*;
87    }
88}
89pub mod hash_set {
90    //! A hash set implemented as a `HashMap` where the value is `()`.
91    pub use crate::set::*;
92
93    #[cfg(feature = "rayon")]
94    /// [rayon]-based parallel iterator types for hash sets.
95    /// You will rarely need to interact with it directly unless you have need
96    /// to name one of the iterator types.
97    ///
98    /// [rayon]: ::rayon
99    pub mod rayon {
100        pub use crate::external_trait_impls::rayon::set::*;
101    }
102}
103pub mod hash_table {
104    //! A hash table implemented with quadratic probing and SIMD lookup.
105    pub use crate::table::*;
106
107    #[cfg(feature = "rayon")]
108    /// [rayon]-based parallel iterator types for hash tables.
109    /// You will rarely need to interact with it directly unless you have need
110    /// to name one of the iterator types.
111    ///
112    /// [rayon]: ::rayon
113    pub mod rayon {
114        pub use crate::external_trait_impls::rayon::table::*;
115    }
116}
117
118pub use crate::map::HashMap;
119pub use crate::set::HashSet;
120pub use crate::table::HashTable;
121
122#[cfg(feature = "equivalent")]
123pub use equivalent::Equivalent;
124
125// This is only used as a fallback when building as part of `std`.
126#[cfg(not(feature = "equivalent"))]
127/// Key equivalence trait.
128///
129/// This trait defines the function used to compare the input value with the
130/// map keys (or set values) during a lookup operation such as [`HashMap::get`]
131/// or [`HashSet::contains`].
132/// It is provided with a blanket implementation based on the
133/// [`Borrow`](core::borrow::Borrow) trait.
134///
135/// # Correctness
136///
137/// Equivalent values must hash to the same value.
138pub trait Equivalent<K: ?Sized> {
139    /// Checks if this value is equivalent to the given key.
140    ///
141    /// Returns `true` if both values are equivalent, and `false` otherwise.
142    ///
143    /// # Correctness
144    ///
145    /// When this function returns `true`, both `self` and `key` must hash to
146    /// the same value.
147    fn equivalent(&self, key: &K) -> bool;
148}
149
150#[cfg(not(feature = "equivalent"))]
151impl<Q: ?Sized, K: ?Sized> Equivalent<K> for Q
152where
153    Q: Eq,
154    K: core::borrow::Borrow<Q>,
155{
156    fn equivalent(&self, key: &K) -> bool {
157        self == key.borrow()
158    }
159}
160
161/// The error type for `try_reserve` methods.
162#[derive(Clone, PartialEq, Eq, Debug)]
163pub enum TryReserveError {
164    /// Error due to the computed capacity exceeding the collection's maximum
165    /// (usually `isize::MAX` bytes).
166    CapacityOverflow,
167
168    /// The memory allocator returned an error
169    AllocError {
170        /// The layout of the allocation request that failed.
171        layout: stdalloc::alloc::Layout,
172    },
173}
174
175// matches stdalloc::collections::TryReserveError
176impl core::fmt::Display for TryReserveError {
177    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
178        f.write_str("memory allocation failed")?;
179        let reason = match self {
180            TryReserveError::CapacityOverflow => {
181                " because the computed capacity exceeded the collection's maximum"
182            }
183            TryReserveError::AllocError { .. } => " because the memory allocator returned an error",
184        };
185        f.write_str(reason)
186    }
187}
188
189impl core::error::Error for TryReserveError {}
hashbrown/lib.rs

hashbrown/
lib.rs
