vendor/hashbrown/src/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]
  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 }