/rust/registry/src/index.crates.io-1949cf8c6b5b557f/hashbrown-0.17.1/src/lib.rs

Source
//! This crate is a Rust port of Google's high-performance [SwissTable] hash
//! map, adapted to make it a drop-in replacement for Rust's standard `HashMap`
//! and `HashSet` types.
//!
//! The original C++ version of [SwissTable] can be found [here], and this
//! [CppCon talk] gives an overview of how the algorithm works.
//!
//! [SwissTable]: https://abseil.io/blog/20180927-swisstables
//! [here]: https://github.com/abseil/abseil-cpp/blob/master/absl/container/internal/raw_hash_set.h
//! [CppCon talk]: https://www.youtube.com/watch?v=ncHmEUmJZf4

#![cfg_attr(not(doc), no_std)]
#![cfg_attr(
    feature = "nightly",
    feature(
        core_intrinsics,
        dropck_eyepatch,
        min_specialization,
        trivial_clone,
        extend_one,
        allocator_api,
        strict_provenance_lints
    )
)]
#![cfg_attr(feature = "nightly", warn(fuzzy_provenance_casts))]
#![cfg_attr(feature = "rustc-dep-of-std", feature(rustc_attrs))]
#![cfg_attr(feature = "nightly", expect(internal_features))]
#![cfg_attr(
    all(feature = "nightly", target_arch = "loongarch64"),
    feature(stdarch_loongarch)
)]
#![cfg_attr(
    all(feature = "nightly", feature = "default-hasher"),
    feature(hasher_prefixfree_extras)
)]

#[cfg(test)]
#[macro_use]
extern crate std;

#[cfg_attr(test, macro_use)]
#[cfg_attr(feature = "rustc-dep-of-std", allow(unused_extern_crates))]
extern crate alloc as stdalloc;

#[doc = include_str!("../README.md")]
#[cfg(doctest)]
pub struct ReadmeDoctests;

#[macro_use]
mod macros;

mod alloc;
mod control;
mod hasher;
mod raw;
mod util;

mod external_trait_impls;
mod map;
#[cfg(feature = "raw-entry")]
mod raw_entry;
#[cfg(feature = "rustc-internal-api")]
mod rustc_entry;
mod scopeguard;
mod set;
mod table;

pub use crate::hasher::DefaultHashBuilder;
#[cfg(feature = "default-hasher")]
pub use crate::hasher::DefaultHasher;

pub mod hash_map {
    //! A hash map implemented with quadratic probing and SIMD lookup.
    pub use crate::map::*;

    #[cfg(feature = "rustc-internal-api")]
    pub use crate::rustc_entry::*;

    #[cfg(feature = "rayon")]
    /// [rayon]-based parallel iterator types for hash maps.
    /// You will rarely need to interact with it directly unless you have need
    /// to name one of the iterator types.
    ///
    /// [rayon]: ::rayon
    pub mod rayon {
        pub use crate::external_trait_impls::rayon::map::*;
    }
}
pub mod hash_set {
    //! A hash set implemented as a `HashMap` where the value is `()`.
    pub use crate::set::*;

    #[cfg(feature = "rayon")]
    /// [rayon]-based parallel iterator types for hash sets.
    /// You will rarely need to interact with it directly unless you have need
    /// to name one of the iterator types.
    ///
    /// [rayon]: ::rayon
    pub mod rayon {
        pub use crate::external_trait_impls::rayon::set::*;
    }
}
pub mod hash_table {
    //! A hash table implemented with quadratic probing and SIMD lookup.
    pub use crate::table::*;

    #[cfg(feature = "rayon")]
    /// [rayon]-based parallel iterator types for hash tables.
    /// You will rarely need to interact with it directly unless you have need
    /// to name one of the iterator types.
    ///
    /// [rayon]: ::rayon
    pub mod rayon {
        pub use crate::external_trait_impls::rayon::table::*;
    }
}

pub use crate::map::HashMap;
pub use crate::set::HashSet;
pub use crate::table::HashTable;

#[cfg(feature = "equivalent")]
pub use equivalent::Equivalent;

// This is only used as a fallback when building as part of `std`.
#[cfg(not(feature = "equivalent"))]
/// Key equivalence trait.
///
/// This trait defines the function used to compare the input value with the
/// map keys (or set values) during a lookup operation such as [`HashMap::get`]
/// or [`HashSet::contains`].
/// It is provided with a blanket implementation based on the
/// [`Borrow`](core::borrow::Borrow) trait.
///
/// # Correctness
///
/// Equivalent values must hash to the same value.
pub trait Equivalent<K: ?Sized> {
    /// Checks if this value is equivalent to the given key.
    ///
    /// Returns `true` if both values are equivalent, and `false` otherwise.
    ///
    /// # Correctness
    ///
    /// When this function returns `true`, both `self` and `key` must hash to
    /// the same value.
    fn equivalent(&self, key: &K) -> bool;
}

#[cfg(not(feature = "equivalent"))]
impl<Q: ?Sized, K: ?Sized> Equivalent<K> for Q
where
    Q: Eq,
    K: core::borrow::Borrow<Q>,
{
    fn equivalent(&self, key: &K) -> bool {
        self == key.borrow()
    }
}

/// The error type for `try_reserve` methods.
#[derive(Clone, PartialEq, Eq, Debug)]
pub enum TryReserveError {
    /// Error due to the computed capacity exceeding the collection's maximum
    /// (usually `isize::MAX` bytes).
    CapacityOverflow,

    /// The memory allocator returned an error
    AllocError {
        /// The layout of the allocation request that failed.
        layout: stdalloc::alloc::Layout,
    },
}

// matches stdalloc::collections::TryReserveError
impl core::fmt::Display for TryReserveError {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.write_str("memory allocation failed")?;
        let reason = match self {
            TryReserveError::CapacityOverflow => {
                " because the computed capacity exceeded the collection's maximum"
            }
            TryReserveError::AllocError { .. } => " because the memory allocator returned an error",
        };
        f.write_str(reason)
    }
}

impl core::error::Error for TryReserveError {}

Line	Count	Source
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		#![cfg_attr(not(doc), no_std)]
13		#![cfg_attr(
14		feature = "nightly",
15		feature(
16		core_intrinsics,
17		dropck_eyepatch,
18		min_specialization,
19		trivial_clone,
20		extend_one,
21		allocator_api,
22		strict_provenance_lints
23		)
24		)]
25		#![cfg_attr(feature = "nightly", warn(fuzzy_provenance_casts))]
26		#![cfg_attr(feature = "rustc-dep-of-std", feature(rustc_attrs))]
27		#![cfg_attr(feature = "nightly", expect(internal_features))]
28		#![cfg_attr(
29		all(feature = "nightly", target_arch = "loongarch64"),
30		feature(stdarch_loongarch)
31		)]
32		#![cfg_attr(
33		all(feature = "nightly", feature = "default-hasher"),
34		feature(hasher_prefixfree_extras)
35		)]
36
37		#[cfg(test)]
38		#[macro_use]
39		extern crate std;
40
41		#[cfg_attr(test, macro_use)]
42		#[cfg_attr(feature = "rustc-dep-of-std", allow(unused_extern_crates))]
43		extern crate alloc as stdalloc;
44
45		#[doc = include_str!("../README.md")]
46		#[cfg(doctest)]
47		pub struct ReadmeDoctests;
48
49		#[macro_use]
50		mod macros;
51
52		mod alloc;
53		mod control;
54		mod hasher;
55		mod raw;
56		mod util;
57
58		mod external_trait_impls;
59		mod map;
60		#[cfg(feature = "raw-entry")]
61		mod raw_entry;
62		#[cfg(feature = "rustc-internal-api")]
63		mod rustc_entry;
64		mod scopeguard;
65		mod set;
66		mod table;
67
68		pub use crate::hasher::DefaultHashBuilder;
69		#[cfg(feature = "default-hasher")]
70		pub use crate::hasher::DefaultHasher;
71
72		pub mod hash_map {
73		//! A hash map implemented with quadratic probing and SIMD lookup.
74		pub use crate::map::*;
75
76		#[cfg(feature = "rustc-internal-api")]
77		pub use crate::rustc_entry::*;
78
79		#[cfg(feature = "rayon")]
80		/// [rayon]-based parallel iterator types for hash maps.
81		/// You will rarely need to interact with it directly unless you have need
82		/// to name one of the iterator types.
83		///
84		/// [rayon]: ::rayon
85		pub mod rayon {
86		pub use crate::external_trait_impls::rayon::map::*;
87		}
88		}
89		pub mod hash_set {
90		//! A hash set implemented as a `HashMap` where the value is `()`.
91		pub use crate::set::*;
92
93		#[cfg(feature = "rayon")]
94		/// [rayon]-based parallel iterator types for hash sets.
95		/// You will rarely need to interact with it directly unless you have need
96		/// to name one of the iterator types.
97		///
98		/// [rayon]: ::rayon
99		pub mod rayon {
100		pub use crate::external_trait_impls::rayon::set::*;
101		}
102		}
103		pub mod hash_table {
104		//! A hash table implemented with quadratic probing and SIMD lookup.
105		pub use crate::table::*;
106
107		#[cfg(feature = "rayon")]
108		/// [rayon]-based parallel iterator types for hash tables.
109		/// You will rarely need to interact with it directly unless you have need
110		/// to name one of the iterator types.
111		///
112		/// [rayon]: ::rayon
113		pub mod rayon {
114		pub use crate::external_trait_impls::rayon::table::*;
115		}
116		}
117
118		pub use crate::map::HashMap;
119		pub use crate::set::HashSet;
120		pub use crate::table::HashTable;
121
122		#[cfg(feature = "equivalent")]
123		pub use equivalent::Equivalent;
124
125		// This is only used as a fallback when building as part of `std`.
126		#[cfg(not(feature = "equivalent"))]
127		/// Key equivalence trait.
128		///
129		/// This trait defines the function used to compare the input value with the
130		/// map keys (or set values) during a lookup operation such as [`HashMap::get`]
131		/// or [`HashSet::contains`].
132		/// It is provided with a blanket implementation based on the
133		/// [`Borrow`](core::borrow::Borrow) trait.
134		///
135		/// # Correctness
136		///
137		/// Equivalent values must hash to the same value.
138		pub trait Equivalent<K: ?Sized> {
139		/// Checks if this value is equivalent to the given key.
140		///
141		/// Returns `true` if both values are equivalent, and `false` otherwise.
142		///
143		/// # Correctness
144		///
145		/// When this function returns `true`, both `self` and `key` must hash to
146		/// the same value.
147		fn equivalent(&self, key: &K) -> bool;
148		}
149
150		#[cfg(not(feature = "equivalent"))]
151		impl<Q: ?Sized, K: ?Sized> Equivalent<K> for Q
152		where
153		Q: Eq,
154		K: core::borrow::Borrow<Q>,
155		{
156	0	fn equivalent(&self, key: &K) -> bool {
157	0	self == key.borrow()
158	0	} Unexecuted instantiation: <_ as hashbrown::Equivalent<_>>::equivalent Unexecuted instantiation: <gix_hash::object_id::ObjectId as hashbrown::Equivalent<gix_hash::object_id::ObjectId>>::equivalent Unexecuted instantiation: <_ as hashbrown::Equivalent<_>>::equivalent Unexecuted instantiation: <gix_hash::borrowed::oid as hashbrown::Equivalent<gix_hash::object_id::ObjectId>>::equivalent Unexecuted instantiation: <gix_hash::object_id::ObjectId as hashbrown::Equivalent<gix_hash::object_id::ObjectId>>::equivalent
159		}
160
161		/// The error type for `try_reserve` methods.
162		#[derive(Clone, PartialEq, Eq, Debug)]
163		pub enum TryReserveError {
164		/// Error due to the computed capacity exceeding the collection's maximum
165		/// (usually `isize::MAX` bytes).
166		CapacityOverflow,
167
168		/// The memory allocator returned an error
169		AllocError {
170		/// The layout of the allocation request that failed.
171		layout: stdalloc::alloc::Layout,
172		},
173		}
174
175		// matches stdalloc::collections::TryReserveError
176		impl core::fmt::Display for TryReserveError {
177	0	fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
178	0	f.write_str("memory allocation failed")?;
179	0	let reason = match self {
180		TryReserveError::CapacityOverflow => {
181	0	" because the computed capacity exceeded the collection's maximum"
182		}
183	0	TryReserveError::AllocError { .. } => " because the memory allocator returned an error",
184		};
185	0	f.write_str(reason)
186	0	} Unexecuted instantiation: <hashbrown::TryReserveError as core::fmt::Display>::fmt Unexecuted instantiation: <hashbrown::TryReserveError as core::fmt::Display>::fmt Unexecuted instantiation: <hashbrown::TryReserveError as core::fmt::Display>::fmt
187		}
188
189		impl core::error::Error for TryReserveError {}

Coverage Report

Created: 2026-06-30 06:48