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

hashbrown/
lib.rs
