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