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#![no_std]
13#![cfg_attr(
14    feature = "nightly",
15    feature(
16        test,
17        core_intrinsics,
18        dropck_eyepatch,
19        min_specialization,
20        extend_one,
21        allocator_api,
22        slice_ptr_get,
23        maybe_uninit_array_assume_init,
24        strict_provenance_lints
25    )
26)]
27#![cfg_attr(feature = "rustc-dep-of-std", feature(rustc_attrs))]
28#![allow(
29    clippy::doc_markdown,
30    clippy::module_name_repetitions,
31    clippy::must_use_candidate,
32    clippy::option_if_let_else,
33    clippy::redundant_else,
34    clippy::manual_map,
35    clippy::missing_safety_doc,
36    clippy::missing_errors_doc
37)]
38#![warn(missing_docs)]
39#![warn(rust_2018_idioms)]
40#![cfg_attr(feature = "nightly", warn(fuzzy_provenance_casts))]
41#![cfg_attr(
42    feature = "nightly",
43    allow(clippy::incompatible_msrv, internal_features)
44)]
45#![cfg_attr(
46    all(feature = "nightly", target_arch = "loongarch64"),
47    feature(stdarch_loongarch)
48)]
49#![cfg_attr(
50    all(feature = "nightly", feature = "default-hasher"),
51    feature(hasher_prefixfree_extras)
52)]
53
54#[cfg(test)]
55#[macro_use]
56extern crate std;
57
58#[cfg_attr(test, macro_use)]
59#[cfg_attr(feature = "rustc-dep-of-std", allow(unused_extern_crates))]
60extern crate alloc;
61
62#[cfg(feature = "nightly")]
63#[cfg(doctest)]
64doc_comment::doctest!("../README.md");
65
66#[macro_use]
67mod macros;
68
69mod control;
70mod hasher;
71mod raw;
72mod util;
73
74mod external_trait_impls;
75mod map;
76#[cfg(feature = "raw-entry")]
77mod raw_entry;
78#[cfg(feature = "rustc-internal-api")]
79mod rustc_entry;
80mod scopeguard;
81mod set;
82mod table;
83
84pub use crate::hasher::DefaultHashBuilder;
85#[cfg(feature = "default-hasher")]
86pub use crate::hasher::DefaultHasher;
87
88pub mod hash_map {
89    //! A hash map implemented with quadratic probing and SIMD lookup.
90    pub use crate::map::*;
91
92    #[cfg(feature = "rustc-internal-api")]
93    pub use crate::rustc_entry::*;
94
95    #[cfg(feature = "rayon")]
96    /// [rayon]-based parallel iterator types for hash maps.
97    /// You will rarely need to interact with it directly unless you have need
98    /// to name one of the iterator types.
99    ///
100    /// [rayon]: https://docs.rs/rayon/1.0/rayon
101    pub mod rayon {
102        pub use crate::external_trait_impls::rayon::map::*;
103    }
104}
105pub mod hash_set {
106    //! A hash set implemented as a `HashMap` where the value is `()`.
107    pub use crate::set::*;
108
109    #[cfg(feature = "rayon")]
110    /// [rayon]-based parallel iterator types for hash sets.
111    /// You will rarely need to interact with it directly unless you have need
112    /// to name one of the iterator types.
113    ///
114    /// [rayon]: https://docs.rs/rayon/1.0/rayon
115    pub mod rayon {
116        pub use crate::external_trait_impls::rayon::set::*;
117    }
118}
119pub mod hash_table {
120    //! A hash table implemented with quadratic probing and SIMD lookup.
121    pub use crate::table::*;
122
123    #[cfg(feature = "rayon")]
124    /// [rayon]-based parallel iterator types for hash tables.
125    /// You will rarely need to interact with it directly unless you have need
126    /// to name one of the iterator types.
127    ///
128    /// [rayon]: https://docs.rs/rayon/1.0/rayon
129    pub mod rayon {
130        pub use crate::external_trait_impls::rayon::table::*;
131    }
132}
133
134pub use crate::map::HashMap;
135pub use crate::set::HashSet;
136pub use crate::table::HashTable;
137
138#[cfg(feature = "equivalent")]
139pub use equivalent::Equivalent;
140
141// This is only used as a fallback when building as part of `std`.
142#[cfg(not(feature = "equivalent"))]
143/// Key equivalence trait.
144///
145/// This trait defines the function used to compare the input value with the
146/// map keys (or set values) during a lookup operation such as [`HashMap::get`]
147/// or [`HashSet::contains`].
148/// It is provided with a blanket implementation based on the
149/// [`Borrow`](core::borrow::Borrow) trait.
150///
151/// # Correctness
152///
153/// Equivalent values must hash to the same value.
154pub trait Equivalent<K: ?Sized> {
155    /// Checks if this value is equivalent to the given key.
156    ///
157    /// Returns `true` if both values are equivalent, and `false` otherwise.
158    ///
159    /// # Correctness
160    ///
161    /// When this function returns `true`, both `self` and `key` must hash to
162    /// the same value.
163    fn equivalent(&self, key: &K) -> bool;
164}
165
166#[cfg(not(feature = "equivalent"))]
167impl<Q: ?Sized, K: ?Sized> Equivalent<K> for Q
168where
169    Q: Eq,
170    K: core::borrow::Borrow<Q>,
171{
172    fn equivalent(&self, key: &K) -> bool {
173        self == key.borrow()
174    }
175}
176
177/// The error type for `try_reserve` methods.
178#[derive(Clone, PartialEq, Eq, Debug)]
179pub enum TryReserveError {
180    /// Error due to the computed capacity exceeding the collection's maximum
181    /// (usually `isize::MAX` bytes).
182    CapacityOverflow,
183
184    /// The memory allocator returned an error
185    AllocError {
186        /// The layout of the allocation request that failed.
187        layout: alloc::alloc::Layout,
188    },
189}
hashbrown/lib.rs

hashbrown/
lib.rs
