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

hashbrown/
lib.rs
