]>
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, | |
24 | maybe_uninit_array_assume_init | |
25 | ) | |
48663c56 | 26 | )] |
3dfed10e XL |
27 | #![allow( |
28 | clippy::doc_markdown, | |
29 | clippy::module_name_repetitions, | |
30 | clippy::must_use_candidate, | |
6a06907d XL |
31 | clippy::option_if_let_else, |
32 | clippy::redundant_else, | |
33 | clippy::manual_map | |
3dfed10e | 34 | )] |
48663c56 | 35 | #![warn(missing_docs)] |
48663c56 XL |
36 | #![warn(rust_2018_idioms)] |
37 | ||
38 | #[cfg(test)] | |
39 | #[macro_use] | |
40 | extern crate std; | |
41 | ||
48663c56 XL |
42 | #[cfg_attr(test, macro_use)] |
43 | extern crate alloc; | |
48663c56 | 44 | |
e74abb32 XL |
45 | #[cfg(feature = "nightly")] |
46 | #[cfg(doctest)] | |
47 | doc_comment::doctest!("../README.md"); | |
48 | ||
48663c56 XL |
49 | #[macro_use] |
50 | mod macros; | |
51 | ||
e74abb32 XL |
52 | #[cfg(feature = "raw")] |
53 | /// Experimental and unsafe `RawTable` API. This module is only available if the | |
54 | /// `raw` feature is enabled. | |
55 | pub mod raw { | |
56 | // The RawTable API is still experimental and is not properly documented yet. | |
57 | #[allow(missing_docs)] | |
58 | #[path = "mod.rs"] | |
59 | mod inner; | |
60 | pub use inner::*; | |
61 | ||
62 | #[cfg(feature = "rayon")] | |
6a06907d XL |
63 | /// [rayon]-based parallel iterator types for hash maps. |
64 | /// You will rarely need to interact with it directly unless you have need | |
65 | /// to name one of the iterator types. | |
66 | /// | |
67 | /// [rayon]: https://docs.rs/rayon/1.0/rayon | |
e74abb32 XL |
68 | pub mod rayon { |
69 | pub use crate::external_trait_impls::rayon::raw::*; | |
70 | } | |
71 | } | |
72 | #[cfg(not(feature = "raw"))] | |
73 | mod raw; | |
74 | ||
48663c56 | 75 | mod external_trait_impls; |
48663c56 | 76 | mod map; |
e74abb32 | 77 | #[cfg(feature = "rustc-internal-api")] |
48663c56 XL |
78 | mod rustc_entry; |
79 | mod scopeguard; | |
80 | mod set; | |
81 | ||
82 | pub mod hash_map { | |
83 | //! A hash map implemented with quadratic probing and SIMD lookup. | |
84 | pub use crate::map::*; | |
85 | ||
e74abb32 | 86 | #[cfg(feature = "rustc-internal-api")] |
48663c56 XL |
87 | pub use crate::rustc_entry::*; |
88 | ||
89 | #[cfg(feature = "rayon")] | |
90 | /// [rayon]-based parallel iterator types for hash maps. | |
91 | /// You will rarely need to interact with it directly unless you have need | |
92 | /// to name one of the iterator types. | |
93 | /// | |
94 | /// [rayon]: https://docs.rs/rayon/1.0/rayon | |
95 | pub mod rayon { | |
96 | pub use crate::external_trait_impls::rayon::map::*; | |
97 | } | |
98 | } | |
99 | pub mod hash_set { | |
100 | //! A hash set implemented as a `HashMap` where the value is `()`. | |
101 | pub use crate::set::*; | |
102 | ||
103 | #[cfg(feature = "rayon")] | |
104 | /// [rayon]-based parallel iterator types for hash sets. | |
105 | /// You will rarely need to interact with it directly unless you have need | |
106 | /// to name one of the iterator types. | |
107 | /// | |
108 | /// [rayon]: https://docs.rs/rayon/1.0/rayon | |
109 | pub mod rayon { | |
110 | pub use crate::external_trait_impls::rayon::set::*; | |
111 | } | |
112 | } | |
113 | ||
114 | pub use crate::map::HashMap; | |
115 | pub use crate::set::HashSet; | |
116 | ||
3dfed10e | 117 | /// The error type for `try_reserve` methods. |
48663c56 | 118 | #[derive(Clone, PartialEq, Eq, Debug)] |
3dfed10e | 119 | pub enum TryReserveError { |
48663c56 XL |
120 | /// Error due to the computed capacity exceeding the collection's maximum |
121 | /// (usually `isize::MAX` bytes). | |
122 | CapacityOverflow, | |
3dfed10e XL |
123 | |
124 | /// The memory allocator returned an error | |
125 | AllocError { | |
416331ca XL |
126 | /// The layout of the allocation request that failed. |
127 | layout: alloc::alloc::Layout, | |
128 | }, | |
48663c56 | 129 | } |
6a06907d XL |
130 | |
131 | /// The error type for [`RawTable::get_each_mut`](crate::raw::RawTable::get_each_mut), | |
132 | /// [`HashMap::get_each_mut`], and [`HashMap::get_each_key_value_mut`]. | |
133 | #[cfg(feature = "nightly")] | |
134 | #[derive(Clone, PartialEq, Eq, Debug)] | |
135 | pub enum UnavailableMutError { | |
136 | /// The requested entry is not present in the table. | |
137 | Absent, | |
138 | /// The requested entry is present, but a mutable reference to it was already created and | |
139 | /// returned from this call to `get_each_mut` or `get_each_key_value_mut`. | |
140 | /// | |
141 | /// Includes the index of the existing mutable reference in the returned array. | |
142 | Duplicate(usize), | |
143 | } | |
144 | ||
145 | /// Wrapper around `Bump` which allows it to be used as an allocator for | |
146 | /// `HashMap`, `HashSet` and `RawTable`. | |
147 | /// | |
148 | /// `Bump` can be used directly without this wrapper on nightly if you enable | |
149 | /// the `allocator-api` feature of the `bumpalo` crate. | |
150 | #[cfg(feature = "bumpalo")] | |
151 | #[derive(Clone, Copy, Debug)] | |
152 | pub struct BumpWrapper<'a>(&'a bumpalo::Bump); | |
153 | ||
154 | #[cfg(feature = "bumpalo")] | |
155 | #[test] | |
156 | fn test_bumpalo() { | |
157 | use bumpalo::Bump; | |
158 | let bump = Bump::new(); | |
159 | let mut map = HashMap::new_in(BumpWrapper(&bump)); | |
160 | map.insert(0, 1); | |
161 | } |