// We *mostly* avoid unsafe code, but `map::core::raw` allows it to use `RawTable` buckets. #![deny(unsafe_code)] #![warn(rust_2018_idioms)] #![no_std] //! [`IndexMap`] is a hash table where the iteration order of the key-value //! pairs is independent of the hash values of the keys. //! //! [`IndexSet`] is a corresponding hash set using the same implementation and //! with similar properties. //! //! ### Highlights //! //! [`IndexMap`] and [`IndexSet`] are drop-in compatible with the std `HashMap` //! and `HashSet`, but they also have some features of note: //! //! - The ordering semantics (see their documentation for details) //! - Sorting methods and the [`.pop()`][IndexMap::pop] methods. //! - The [`Equivalent`] trait, which offers more flexible equality definitions //! between borrowed and owned versions of keys. //! - The [`MutableKeys`][map::MutableKeys] trait, which gives opt-in mutable //! access to map keys, and [`MutableValues`][set::MutableValues] for sets. //! //! ### Feature Flags //! //! To reduce the amount of compiled code in the crate by default, certain //! features are gated behind [feature flags]. These allow you to opt in to (or //! out of) functionality. Below is a list of the features available in this //! crate. //! //! * `std`: Enables features which require the Rust standard library. For more //! information see the section on [`no_std`]. //! * `rayon`: Enables parallel iteration and other parallel methods. //! * `serde`: Adds implementations for [`Serialize`] and [`Deserialize`] //! to [`IndexMap`] and [`IndexSet`]. Alternative implementations for //! (de)serializing [`IndexMap`] as an ordered sequence are available in the //! [`map::serde_seq`] module. //! * `borsh`: Adds implementations for [`BorshSerialize`] and [`BorshDeserialize`] //! to [`IndexMap`] and [`IndexSet`]. //! * `arbitrary`: Adds implementations for the [`arbitrary::Arbitrary`] trait //! to [`IndexMap`] and [`IndexSet`]. //! * `quickcheck`: Adds implementations for the [`quickcheck::Arbitrary`] trait //! to [`IndexMap`] and [`IndexSet`]. //! //! _Note: only the `std` feature is enabled by default._ //! //! [feature flags]: https://doc.rust-lang.org/cargo/reference/manifest.html#the-features-section //! [`no_std`]: #no-standard-library-targets //! [`Serialize`]: `::serde::Serialize` //! [`Deserialize`]: `::serde::Deserialize` //! [`BorshSerialize`]: `::borsh::BorshSerialize` //! [`BorshDeserialize`]: `::borsh::BorshDeserialize` //! [`arbitrary::Arbitrary`]: `::arbitrary::Arbitrary` //! [`quickcheck::Arbitrary`]: `::quickcheck::Arbitrary` //! //! ### Alternate Hashers //! //! [`IndexMap`] and [`IndexSet`] have a default hasher type //! [`S = RandomState`][std::collections::hash_map::RandomState], //! just like the standard `HashMap` and `HashSet`, which is resistant to //! HashDoS attacks but not the most performant. Type aliases can make it easier //! to use alternate hashers: //! //! ``` //! use fnv::FnvBuildHasher; //! use fxhash::FxBuildHasher; //! use indexmap::{IndexMap, IndexSet}; //! //! type FnvIndexMap = IndexMap; //! type FnvIndexSet = IndexSet; //! //! type FxIndexMap = IndexMap; //! type FxIndexSet = IndexSet; //! //! let std: IndexSet = (0..100).collect(); //! let fnv: FnvIndexSet = (0..100).collect(); //! let fx: FxIndexSet = (0..100).collect(); //! assert_eq!(std, fnv); //! assert_eq!(std, fx); //! ``` //! //! ### Rust Version //! //! This version of indexmap requires Rust 1.63 or later. //! //! The indexmap 2.x release series will use a carefully considered version //! upgrade policy, where in a later 2.x version, we will raise the minimum //! required Rust version. //! //! ## No Standard Library Targets //! //! This crate supports being built without `std`, requiring `alloc` instead. //! This is chosen by disabling the default "std" cargo feature, by adding //! `default-features = false` to your dependency specification. //! //! - Creating maps and sets using [`new`][IndexMap::new] and //! [`with_capacity`][IndexMap::with_capacity] is unavailable without `std`. //! Use methods [`IndexMap::default`], [`with_hasher`][IndexMap::with_hasher], //! [`with_capacity_and_hasher`][IndexMap::with_capacity_and_hasher] instead. //! A no-std compatible hasher will be needed as well, for example //! from the crate `twox-hash`. //! - Macros [`indexmap!`] and [`indexset!`] are unavailable without `std`. #![cfg_attr(docsrs, feature(doc_cfg))] extern crate alloc; #[cfg(feature = "std")] #[macro_use] extern crate std; use alloc::vec::{self, Vec}; mod arbitrary; #[macro_use] mod macros; #[cfg(feature = "borsh")] mod borsh; #[cfg(feature = "serde")] mod serde; mod util; pub mod map; pub mod set; // Placed after `map` and `set` so new `rayon` methods on the types // are documented after the "normal" methods. #[cfg(feature = "rayon")] mod rayon; #[cfg(feature = "rustc-rayon")] mod rustc; pub use crate::map::IndexMap; pub use crate::set::IndexSet; pub use equivalent::Equivalent; // shared private items /// Hash value newtype. Not larger than usize, since anything larger /// isn't used for selecting position anyway. #[derive(Clone, Copy, Debug, PartialEq)] struct HashValue(usize); impl HashValue { #[inline(always)] fn get(self) -> u64 { self.0 as u64 } } #[derive(Copy, Debug)] struct Bucket { hash: HashValue, key: K, value: V, } impl Clone for Bucket where K: Clone, V: Clone, { fn clone(&self) -> Self { Bucket { hash: self.hash, key: self.key.clone(), value: self.value.clone(), } } fn clone_from(&mut self, other: &Self) { self.hash = other.hash; self.key.clone_from(&other.key); self.value.clone_from(&other.value); } } impl Bucket { // field accessors -- used for `f` instead of closures in `.map(f)` fn key_ref(&self) -> &K { &self.key } fn value_ref(&self) -> &V { &self.value } fn value_mut(&mut self) -> &mut V { &mut self.value } fn key(self) -> K { self.key } fn value(self) -> V { self.value } fn key_value(self) -> (K, V) { (self.key, self.value) } fn refs(&self) -> (&K, &V) { (&self.key, &self.value) } fn ref_mut(&mut self) -> (&K, &mut V) { (&self.key, &mut self.value) } fn muts(&mut self) -> (&mut K, &mut V) { (&mut self.key, &mut self.value) } } trait Entries { type Entry; fn into_entries(self) -> Vec; fn as_entries(&self) -> &[Self::Entry]; fn as_entries_mut(&mut self) -> &mut [Self::Entry]; fn with_entries(&mut self, f: F) where F: FnOnce(&mut [Self::Entry]); } /// The error type for [`try_reserve`][IndexMap::try_reserve] methods. #[derive(Clone, PartialEq, Eq, Debug)] pub struct TryReserveError { kind: TryReserveErrorKind, } #[derive(Clone, PartialEq, Eq, Debug)] enum TryReserveErrorKind { // The standard library's kind is currently opaque to us, otherwise we could unify this. Std(alloc::collections::TryReserveError), CapacityOverflow, AllocError { layout: alloc::alloc::Layout }, } // These are not `From` so we don't expose them in our public API. impl TryReserveError { fn from_alloc(error: alloc::collections::TryReserveError) -> Self { Self { kind: TryReserveErrorKind::Std(error), } } fn from_hashbrown(error: hashbrown::TryReserveError) -> Self { Self { kind: match error { hashbrown::TryReserveError::CapacityOverflow => { TryReserveErrorKind::CapacityOverflow } hashbrown::TryReserveError::AllocError { layout } => { TryReserveErrorKind::AllocError { layout } } }, } } } impl core::fmt::Display for TryReserveError { fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { let reason = match &self.kind { TryReserveErrorKind::Std(e) => return core::fmt::Display::fmt(e, f), TryReserveErrorKind::CapacityOverflow => { " because the computed capacity exceeded the collection's maximum" } TryReserveErrorKind::AllocError { .. } => { " because the memory allocator returned an error" } }; f.write_str("memory allocation failed")?; f.write_str(reason) } } #[cfg(feature = "std")] #[cfg_attr(docsrs, doc(cfg(feature = "std")))] impl std::error::Error for TryReserveError {}