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

hashbrown/
lib.rs
