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" )] |
45 | pub type DefaultHashBuilder = foldhash::fast::RandomState; |
46 | |
47 | /// Dummy default hasher for [`HashMap`] and [`HashSet`]. |
48 | #[cfg (not(feature = "default-hasher" ))] |
49 | pub enum DefaultHashBuilder {} |
50 | |
51 | #[cfg (test)] |
52 | #[macro_use ] |
53 | extern crate std; |
54 | |
55 | #[cfg_attr (test, macro_use)] |
56 | #[cfg_attr (feature = "rustc-dep-of-std" , allow(unused_extern_crates))] |
57 | extern crate alloc; |
58 | |
59 | #[cfg (feature = "nightly" )] |
60 | #[cfg (doctest)] |
61 | doc_comment::doctest!("../README.md" ); |
62 | |
63 | #[macro_use ] |
64 | mod macros; |
65 | |
66 | mod control; |
67 | mod raw; |
68 | mod util; |
69 | |
70 | mod external_trait_impls; |
71 | mod map; |
72 | #[cfg (feature = "raw-entry" )] |
73 | mod raw_entry; |
74 | #[cfg (feature = "rustc-internal-api" )] |
75 | mod rustc_entry; |
76 | mod scopeguard; |
77 | mod set; |
78 | mod table; |
79 | |
80 | pub 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 | } |
97 | pub 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 | } |
111 | pub 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 | |
126 | pub use crate::map::HashMap; |
127 | pub use crate::set::HashSet; |
128 | pub use crate::table::HashTable; |
129 | |
130 | #[cfg (feature = "equivalent" )] |
131 | pub 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. |
146 | pub 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" ))] |
159 | impl<Q: ?Sized, K: ?Sized> Equivalent<K> for Q |
160 | where |
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)] |
171 | pub 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 | } |
182 | |