hashbrown/
lib.rs

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]
43extern crate std;
44
45#[cfg_attr(test, macro_use)]
46extern crate alloc;
47
48#[cfg(feature = "nightly")]
49#[cfg(doctest)]
50doc_comment::doctest!("../README.md");
51
52#[macro_use]
53mod macros;
54
55#[cfg(feature = "raw")]
56/// Experimental and unsafe `RawTable` API. This module is only available if the
57/// `raw` feature is enabled.
58pub 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"))]
76mod raw;
77
78mod external_trait_impls;
79mod map;
80#[cfg(feature = "rustc-internal-api")]
81mod rustc_entry;
82mod scopeguard;
83mod set;
84
85pub 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}
102pub 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
117pub use crate::map::HashMap;
118pub use crate::set::HashSet;
119
120/// The error type for `try_reserve` methods.
121#[derive(Clone, PartialEq, Eq, Debug)]
122pub 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)]
141pub struct BumpWrapper<'a>(pub &'a bumpalo::Bump);
142
143#[cfg(feature = "bumpalo")]
144#[test]
145fn 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}
hashbrown/lib.rs

hashbrown/
lib.rs
