]>
Commit | Line | Data |
---|---|---|
48663c56 XL |
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", | |
6a06907d XL |
15 | feature( |
16 | test, | |
17 | core_intrinsics, | |
18 | dropck_eyepatch, | |
19 | min_specialization, | |
20 | extend_one, | |
21 | allocator_api, | |
22 | slice_ptr_get, | |
23 | nonnull_slice_from_raw_parts, | |
5099ac24 FG |
24 | maybe_uninit_array_assume_init, |
25 | build_hasher_simple_hash_one | |
6a06907d | 26 | ) |
48663c56 | 27 | )] |
3dfed10e XL |
28 | #![allow( |
29 | clippy::doc_markdown, | |
30 | clippy::module_name_repetitions, | |
31 | clippy::must_use_candidate, | |
6a06907d XL |
32 | clippy::option_if_let_else, |
33 | clippy::redundant_else, | |
923072b8 FG |
34 | clippy::manual_map, |
35 | clippy::missing_safety_doc, | |
36 | clippy::missing_errors_doc | |
3dfed10e | 37 | )] |
48663c56 | 38 | #![warn(missing_docs)] |
48663c56 XL |
39 | #![warn(rust_2018_idioms)] |
40 | ||
41 | #[cfg(test)] | |
42 | #[macro_use] | |
43 | extern crate std; | |
44 | ||
48663c56 XL |
45 | #[cfg_attr(test, macro_use)] |
46 | extern crate alloc; | |
48663c56 | 47 | |
e74abb32 XL |
48 | #[cfg(feature = "nightly")] |
49 | #[cfg(doctest)] | |
50 | doc_comment::doctest!("../README.md"); | |
51 | ||
48663c56 XL |
52 | #[macro_use] |
53 | mod macros; | |
54 | ||
e74abb32 XL |
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")] | |
6a06907d XL |
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 | |
e74abb32 XL |
71 | pub mod rayon { |
72 | pub use crate::external_trait_impls::rayon::raw::*; | |
73 | } | |
74 | } | |
75 | #[cfg(not(feature = "raw"))] | |
76 | mod raw; | |
77 | ||
48663c56 | 78 | mod external_trait_impls; |
48663c56 | 79 | mod map; |
e74abb32 | 80 | #[cfg(feature = "rustc-internal-api")] |
48663c56 XL |
81 | mod rustc_entry; |
82 | mod scopeguard; | |
83 | mod set; | |
84 | ||
85 | pub mod hash_map { | |
86 | //! A hash map implemented with quadratic probing and SIMD lookup. | |
87 | pub use crate::map::*; | |
88 | ||
e74abb32 | 89 | #[cfg(feature = "rustc-internal-api")] |
48663c56 XL |
90 | pub use crate::rustc_entry::*; |
91 | ||
92 | #[cfg(feature = "rayon")] | |
93 | /// [rayon]-based parallel iterator types for hash maps. | |
94 | /// You will rarely need to interact with it directly unless you have need | |
95 | /// to name one of the iterator types. | |
96 | /// | |
97 | /// [rayon]: https://docs.rs/rayon/1.0/rayon | |
98 | pub mod rayon { | |
99 | pub use crate::external_trait_impls::rayon::map::*; | |
100 | } | |
101 | } | |
102 | pub mod hash_set { | |
103 | //! A hash set implemented as a `HashMap` where the value is `()`. | |
104 | pub use crate::set::*; | |
105 | ||
106 | #[cfg(feature = "rayon")] | |
107 | /// [rayon]-based parallel iterator types for hash sets. | |
108 | /// You will rarely need to interact with it directly unless you have need | |
109 | /// to name one of the iterator types. | |
110 | /// | |
111 | /// [rayon]: https://docs.rs/rayon/1.0/rayon | |
112 | pub mod rayon { | |
113 | pub use crate::external_trait_impls::rayon::set::*; | |
114 | } | |
115 | } | |
116 | ||
117 | pub use crate::map::HashMap; | |
118 | pub use crate::set::HashSet; | |
119 | ||
6522a427 EL |
120 | /// Key equivalence trait. |
121 | /// | |
122 | /// This trait defines the function used to compare the input value with the | |
123 | /// map keys (or set values) during a lookup operation such as [`HashMap::get`] | |
124 | /// or [`HashSet::contains`]. | |
125 | /// It is provided with a blanket implementation based on the | |
126 | /// [`Borrow`](core::borrow::Borrow) trait. | |
127 | /// | |
128 | /// # Correctness | |
129 | /// | |
130 | /// Equivalent values must hash to the same value. | |
131 | pub trait Equivalent<K: ?Sized> { | |
132 | /// Checks if this value is equivalent to the given key. | |
133 | /// | |
134 | /// Returns `true` if both values are equivalent, and `false` otherwise. | |
135 | /// | |
136 | /// # Correctness | |
137 | /// | |
138 | /// When this function returns `true`, both `self` and `key` must hash to | |
139 | /// the same value. | |
140 | fn equivalent(&self, key: &K) -> bool; | |
141 | } | |
142 | ||
143 | impl<Q: ?Sized, K: ?Sized> Equivalent<K> for Q | |
144 | where | |
145 | Q: Eq, | |
146 | K: core::borrow::Borrow<Q>, | |
147 | { | |
148 | fn equivalent(&self, key: &K) -> bool { | |
149 | self == key.borrow() | |
150 | } | |
151 | } | |
152 | ||
3dfed10e | 153 | /// The error type for `try_reserve` methods. |
48663c56 | 154 | #[derive(Clone, PartialEq, Eq, Debug)] |
3dfed10e | 155 | pub enum TryReserveError { |
48663c56 XL |
156 | /// Error due to the computed capacity exceeding the collection's maximum |
157 | /// (usually `isize::MAX` bytes). | |
158 | CapacityOverflow, | |
3dfed10e XL |
159 | |
160 | /// The memory allocator returned an error | |
161 | AllocError { | |
416331ca XL |
162 | /// The layout of the allocation request that failed. |
163 | layout: alloc::alloc::Layout, | |
164 | }, | |
48663c56 | 165 | } |
6a06907d | 166 | |
6a06907d XL |
167 | /// Wrapper around `Bump` which allows it to be used as an allocator for |
168 | /// `HashMap`, `HashSet` and `RawTable`. | |
169 | /// | |
170 | /// `Bump` can be used directly without this wrapper on nightly if you enable | |
171 | /// the `allocator-api` feature of the `bumpalo` crate. | |
172 | #[cfg(feature = "bumpalo")] | |
173 | #[derive(Clone, Copy, Debug)] | |
136023e0 | 174 | pub struct BumpWrapper<'a>(pub &'a bumpalo::Bump); |
6a06907d XL |
175 | |
176 | #[cfg(feature = "bumpalo")] | |
177 | #[test] | |
178 | fn test_bumpalo() { | |
179 | use bumpalo::Bump; | |
180 | let bump = Bump::new(); | |
181 | let mut map = HashMap::new_in(BumpWrapper(&bump)); | |
182 | map.insert(0, 1); | |
183 | } |