Chih-Hung Hsieh | cdc803b | 2020-11-09 15:57:01 -0800 | [diff] [blame] | 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", |
Joel Galenson | 486b321 | 2021-04-01 16:55:16 -0700 | [diff] [blame] | 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, |
David LeGare | 9f6431d | 2022-03-10 16:15:25 +0000 | [diff] [blame] | 24 | maybe_uninit_array_assume_init |
Joel Galenson | 486b321 | 2021-04-01 16:55:16 -0700 | [diff] [blame] | 25 | ) |
Chih-Hung Hsieh | cdc803b | 2020-11-09 15:57:01 -0800 | [diff] [blame] | 26 | )] |
| 27 | #![allow( |
| 28 | clippy::doc_markdown, |
| 29 | clippy::module_name_repetitions, |
| 30 | clippy::must_use_candidate, |
Joel Galenson | 486b321 | 2021-04-01 16:55:16 -0700 | [diff] [blame] | 31 | clippy::option_if_let_else, |
| 32 | clippy::redundant_else, |
| 33 | clippy::manual_map |
Chih-Hung Hsieh | cdc803b | 2020-11-09 15:57:01 -0800 | [diff] [blame] | 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")] |
Joel Galenson | 486b321 | 2021-04-01 16:55:16 -0700 | [diff] [blame] | 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 |
Chih-Hung Hsieh | cdc803b | 2020-11-09 15:57:01 -0800 | [diff] [blame] | 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 | } |
Joel Galenson | 486b321 | 2021-04-01 16:55:16 -0700 | [diff] [blame] | 130 | |
David LeGare | 9f6431d | 2022-03-10 16:15:25 +0000 | [diff] [blame] | 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 | |
Joel Galenson | 486b321 | 2021-04-01 16:55:16 -0700 | [diff] [blame] | 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] |
| 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 | } |