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

hashbrown/
lib.rs
