1// We *mostly* avoid unsafe code, but `Slice` allows it for DST casting.
2#![deny(unsafe_code)]
3#![warn(rust_2018_idioms)]
4#![no_std]
5
6//! [`IndexMap`] is a hash table where the iteration order of the key-value
7//! pairs is independent of the hash values of the keys.
8//!
9//! [`IndexSet`] is a corresponding hash set using the same implementation and
10//! with similar properties.
11//!
12//! ### Highlights
13//!
14//! [`IndexMap`] and [`IndexSet`] are drop-in compatible with the std `HashMap`
15//! and `HashSet`, but they also have some features of note:
16//!
17//! - The ordering semantics (see their documentation for details)
18//! - Sorting methods and the [`.pop()`][IndexMap::pop] methods.
19//! - The [`Equivalent`] trait, which offers more flexible equality definitions
20//! between borrowed and owned versions of keys.
21//! - The [`MutableKeys`][map::MutableKeys] trait, which gives opt-in mutable
22//! access to map keys, and [`MutableValues`][set::MutableValues] for sets.
23//!
24//! ### Feature Flags
25//!
26//! To reduce the amount of compiled code in the crate by default, certain
27//! features are gated behind [feature flags]. These allow you to opt in to (or
28//! out of) functionality. Below is a list of the features available in this
29//! crate.
30//!
31//! * `std`: Enables features which require the Rust standard library. For more
32//! information see the section on [`no_std`].
33//! * `rayon`: Enables parallel iteration and other parallel methods.
34//! * `serde`: Adds implementations for [`Serialize`] and [`Deserialize`]
35//! to [`IndexMap`] and [`IndexSet`]. Alternative implementations for
36//! (de)serializing [`IndexMap`] as an ordered sequence are available in the
37//! [`map::serde_seq`] module.
38//! * `borsh`: Adds implementations for [`BorshSerialize`] and [`BorshDeserialize`]
39//! to [`IndexMap`] and [`IndexSet`].
40//! * `arbitrary`: Adds implementations for the [`arbitrary::Arbitrary`] trait
41//! to [`IndexMap`] and [`IndexSet`].
42//! * `quickcheck`: Adds implementations for the [`quickcheck::Arbitrary`] trait
43//! to [`IndexMap`] and [`IndexSet`].
44//!
45//! _Note: only the `std` feature is enabled by default._
46//!
47//! [feature flags]: https://doc.rust-lang.org/cargo/reference/manifest.html#the-features-section
48//! [`no_std`]: #no-standard-library-targets
49//! [`Serialize`]: `::serde::Serialize`
50//! [`Deserialize`]: `::serde::Deserialize`
51//! [`BorshSerialize`]: `::borsh::BorshSerialize`
52//! [`BorshDeserialize`]: `::borsh::BorshDeserialize`
53//! [`arbitrary::Arbitrary`]: `::arbitrary::Arbitrary`
54//! [`quickcheck::Arbitrary`]: `::quickcheck::Arbitrary`
55//!
56//! ### Alternate Hashers
57//!
58//! [`IndexMap`] and [`IndexSet`] have a default hasher type
59//! [`S = RandomState`][std::collections::hash_map::RandomState],
60//! just like the standard `HashMap` and `HashSet`, which is resistant to
61//! HashDoS attacks but not the most performant. Type aliases can make it easier
62//! to use alternate hashers:
63//!
64//! ```
65//! use fnv::FnvBuildHasher;
66//! use fxhash::FxBuildHasher;
67//! use indexmap::{IndexMap, IndexSet};
68//!
69//! type FnvIndexMap<K, V> = IndexMap<K, V, FnvBuildHasher>;
70//! type FnvIndexSet<T> = IndexSet<T, FnvBuildHasher>;
71//!
72//! type FxIndexMap<K, V> = IndexMap<K, V, FxBuildHasher>;
73//! type FxIndexSet<T> = IndexSet<T, FxBuildHasher>;
74//!
75//! let std: IndexSet<i32> = (0..100).collect();
76//! let fnv: FnvIndexSet<i32> = (0..100).collect();
77//! let fx: FxIndexSet<i32> = (0..100).collect();
78//! assert_eq!(std, fnv);
79//! assert_eq!(std, fx);
80//! ```
81//!
82//! ### Rust Version
83//!
84//! This version of indexmap requires Rust 1.63 or later.
85//!
86//! The indexmap 2.x release series will use a carefully considered version
87//! upgrade policy, where in a later 2.x version, we will raise the minimum
88//! required Rust version.
89//!
90//! ## No Standard Library Targets
91//!
92//! This crate supports being built without `std`, requiring `alloc` instead.
93//! This is chosen by disabling the default "std" cargo feature, by adding
94//! `default-features = false` to your dependency specification.
95//!
96//! - Creating maps and sets using [`new`][IndexMap::new] and
97//! [`with_capacity`][IndexMap::with_capacity] is unavailable without `std`.
98//! Use methods [`IndexMap::default`], [`with_hasher`][IndexMap::with_hasher],
99//! [`with_capacity_and_hasher`][IndexMap::with_capacity_and_hasher] instead.
100//! A no-std compatible hasher will be needed as well, for example
101//! from the crate `twox-hash`.
102//! - Macros [`indexmap!`] and [`indexset!`] are unavailable without `std`.
103
104#![cfg_attr(docsrs, feature(doc_cfg))]
105
106extern crate alloc;
107
108#[cfg(feature = "std")]
109#[macro_use]
110extern crate std;
111
112use alloc::vec::{self, Vec};
113
114mod arbitrary;
115#[macro_use]
116mod macros;
117#[cfg(feature = "borsh")]
118mod borsh;
119#[cfg(feature = "serde")]
120mod serde;
121mod util;
122
123pub mod map;
124pub mod set;
125
126// Placed after `map` and `set` so new `rayon` methods on the types
127// are documented after the "normal" methods.
128#[cfg(feature = "rayon")]
129mod rayon;
130
131#[cfg(feature = "rustc-rayon")]
132mod rustc;
133
134pub use crate::map::IndexMap;
135pub use crate::set::IndexSet;
136pub use equivalent::Equivalent;
137
138// shared private items
139
140/// Hash value newtype. Not larger than usize, since anything larger
141/// isn't used for selecting position anyway.
142#[derive(Clone, Copy, Debug, PartialEq)]
143struct HashValue(usize);
144
145impl HashValue {
146 #[inline(always)]
147 fn get(self) -> u64 {
148 self.0 as u64
149 }
150}
151
152#[derive(Copy, Debug)]
153struct Bucket<K, V> {
154 hash: HashValue,
155 key: K,
156 value: V,
157}
158
159impl<K, V> Clone for Bucket<K, V>
160where
161 K: Clone,
162 V: Clone,
163{
164 fn clone(&self) -> Self {
165 Bucket {
166 hash: self.hash,
167 key: self.key.clone(),
168 value: self.value.clone(),
169 }
170 }
171
172 fn clone_from(&mut self, other: &Self) {
173 self.hash = other.hash;
174 self.key.clone_from(&other.key);
175 self.value.clone_from(&other.value);
176 }
177}
178
179impl<K, V> Bucket<K, V> {
180 // field accessors -- used for `f` instead of closures in `.map(f)`
181 fn key_ref(&self) -> &K {
182 &self.key
183 }
184 fn value_ref(&self) -> &V {
185 &self.value
186 }
187 fn value_mut(&mut self) -> &mut V {
188 &mut self.value
189 }
190 fn key(self) -> K {
191 self.key
192 }
193 fn value(self) -> V {
194 self.value
195 }
196 fn key_value(self) -> (K, V) {
197 (self.key, self.value)
198 }
199 fn refs(&self) -> (&K, &V) {
200 (&self.key, &self.value)
201 }
202 fn ref_mut(&mut self) -> (&K, &mut V) {
203 (&self.key, &mut self.value)
204 }
205 fn muts(&mut self) -> (&mut K, &mut V) {
206 (&mut self.key, &mut self.value)
207 }
208}
209
210trait Entries {
211 type Entry;
212 fn into_entries(self) -> Vec<Self::Entry>;
213 fn as_entries(&self) -> &[Self::Entry];
214 fn as_entries_mut(&mut self) -> &mut [Self::Entry];
215 fn with_entries<F>(&mut self, f: F)
216 where
217 F: FnOnce(&mut [Self::Entry]);
218}
219
220/// The error type for [`try_reserve`][IndexMap::try_reserve] methods.
221#[derive(Clone, PartialEq, Eq, Debug)]
222pub struct TryReserveError {
223 kind: TryReserveErrorKind,
224}
225
226#[derive(Clone, PartialEq, Eq, Debug)]
227enum TryReserveErrorKind {
228 // The standard library's kind is currently opaque to us, otherwise we could unify this.
229 Std(alloc::collections::TryReserveError),
230 CapacityOverflow,
231 AllocError { layout: alloc::alloc::Layout },
232}
233
234// These are not `From` so we don't expose them in our public API.
235impl TryReserveError {
236 fn from_alloc(error: alloc::collections::TryReserveError) -> Self {
237 Self {
238 kind: TryReserveErrorKind::Std(error),
239 }
240 }
241
242 fn from_hashbrown(error: hashbrown::TryReserveError) -> Self {
243 Self {
244 kind: match error {
245 hashbrown::TryReserveError::CapacityOverflow => {
246 TryReserveErrorKind::CapacityOverflow
247 }
248 hashbrown::TryReserveError::AllocError { layout: Layout } => {
249 TryReserveErrorKind::AllocError { layout }
250 }
251 },
252 }
253 }
254}
255
256impl core::fmt::Display for TryReserveError {
257 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
258 let reason: &'static str = match &self.kind {
259 TryReserveErrorKind::Std(e: &TryReserveError) => return core::fmt::Display::fmt(self:e, f),
260 TryReserveErrorKind::CapacityOverflow => {
261 " because the computed capacity exceeded the collection's maximum"
262 }
263 TryReserveErrorKind::AllocError { .. } => {
264 " because the memory allocator returned an error"
265 }
266 };
267 f.write_str(data:"memory allocation failed")?;
268 f.write_str(data:reason)
269 }
270}
271
272#[cfg(feature = "std")]
273#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
274impl std::error::Error for TryReserveError {}
275