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 ] |
43 | extern crate std; |
44 | |
45 | #[cfg_attr (test, macro_use)] |
46 | extern crate alloc; |
47 | |
48 | #[cfg (feature = "nightly" )] |
49 | #[cfg (doctest)] |
50 | doc_comment::doctest!("../README.md" ); |
51 | |
52 | #[macro_use ] |
53 | mod macros; |
54 | |
55 | #[cfg (feature = "raw" )] |
56 | /// Experimental and unsafe `RawTable` API. This module is only available if the |
57 | /// `raw` feature is enabled. |
58 | pub 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" ))] |
76 | mod raw; |
77 | |
78 | mod external_trait_impls; |
79 | mod map; |
80 | #[cfg (feature = "rustc-internal-api" )] |
81 | mod rustc_entry; |
82 | mod scopeguard; |
83 | mod set; |
84 | mod table; |
85 | |
86 | pub 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 | } |
103 | pub 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 | } |
117 | pub 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 | |
132 | pub use crate::map::HashMap; |
133 | pub use crate::set::HashSet; |
134 | pub use crate::table::HashTable; |
135 | |
136 | #[cfg (feature = "equivalent" )] |
137 | pub 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. |
152 | pub 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" ))] |
165 | impl<Q: ?Sized, K: ?Sized> Equivalent<K> for Q |
166 | where |
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)] |
177 | pub 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 | |