| 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 |
build_hasher_simple_hash_one |
| 26 |
) |
| 27 |
)] |
| 28 |
#![allow( |
| 29 |
clippy::doc_markdown, |
| 30 |
clippy::module_name_repetitions, |
| 31 |
clippy::must_use_candidate, |
| 32 |
clippy::option_if_let_else, |
| 33 |
clippy::redundant_else, |
| 34 |
clippy::manual_map, |
| 35 |
clippy::missing_safety_doc, |
| 36 |
clippy::missing_errors_doc |
| 37 |
)] |
| 38 |
#![warn(missing_docs)] |
| 39 |
#![warn(rust_2018_idioms)] |
| 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 |
|
| 85 |
pub mod hash_map { |
| 86 |
//! A hash map implemented with quadratic probing and SIMD lookup. |
| 87 |
pub use crate::map::*; |
| 88 |
|
| 89 |
#[cfg(feature = "rustc-internal-api")] |
| 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 |
|
| 120 |
/// The error type for `try_reserve` methods. |
| 121 |
#[derive(Clone, PartialEq, Eq, Debug)] |
| 122 |
pub enum TryReserveError { |
| 123 |
/// Error due to the computed capacity exceeding the collection's maximum |
| 124 |
/// (usually `isize::MAX` bytes). |
| 125 |
CapacityOverflow, |
| 126 |
|
| 127 |
/// The memory allocator returned an error |
| 128 |
AllocError { |
| 129 |
/// The layout of the allocation request that failed. |
| 130 |
layout: alloc::alloc::Layout, |
| 131 |
}, |
| 132 |
} |
| 133 |
|
| 134 |
/// Wrapper around `Bump` which allows it to be used as an allocator for |
| 135 |
/// `HashMap`, `HashSet` and `RawTable`. |
| 136 |
/// |
| 137 |
/// `Bump` can be used directly without this wrapper on nightly if you enable |
| 138 |
/// the `allocator-api` feature of the `bumpalo` crate. |
| 139 |
#[cfg(feature = "bumpalo")] |
| 140 |
#[derive(Clone, Copy, Debug)] |
| 141 |
pub struct BumpWrapper<'a>(pub &'a bumpalo::Bump); |
| 142 |
|
| 143 |
#[cfg(feature = "bumpalo")] |
| 144 |
#[test] |
| 145 |
fn test_bumpalo() { |
| 146 |
use bumpalo::Bump; |
| 147 |
let bump = Bump::new(); |
| 148 |
let mut map = HashMap::new_in(BumpWrapper(&bump)); |
| 149 |
map.insert(0, 1); |
| 150 |
} |