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 nonnull_slice_from_raw_parts,
24 maybe_uninit_array_assume_init
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 )]
35 #![warn(missing_docs)]
36 #![warn(rust_2018_idioms)]
37
38 #[cfg(test)]
39 #[macro_use]
40 extern crate std;
41
42 #[cfg_attr(test, macro_use)]
43 extern crate alloc;
44
45 #[cfg(feature = "nightly")]
46 #[cfg(doctest)]
47 doc_comment::doctest!("../README.md");
48
49 #[macro_use]
50 mod macros;
51
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")]
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
68 pub mod rayon {
69 pub use crate::external_trait_impls::rayon::raw::*;
70 }
71 }
72 #[cfg(not(feature = "raw"))]
73 mod raw;
74
75 mod external_trait_impls;
76 mod map;
77 #[cfg(feature = "rustc-internal-api")]
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
86 #[cfg(feature = "rustc-internal-api")]
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
117 /// The error type for `try_reserve` methods.
118 #[derive(Clone, PartialEq, Eq, Debug)]
119 pub enum TryReserveError {
120 /// Error due to the computed capacity exceeding the collection's maximum
121 /// (usually `isize::MAX` bytes).
122 CapacityOverflow,
123
124 /// The memory allocator returned an error
125 AllocError {
126 /// The layout of the allocation request that failed.
127 layout: alloc::alloc::Layout,
128 },
129 }
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>(pub &'a bumpalo::Bump);
153
154 #[cfg(feature = "bumpalo")]
155 #[test]
test_bumpalo()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 }
162