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//! * `arbitrary`: Adds implementations for the [`arbitrary::Arbitrary`] trait
39//! to [`IndexMap`] and [`IndexSet`].
40//! * `quickcheck`: Adds implementations for the [`quickcheck::Arbitrary`] trait
41//! to [`IndexMap`] and [`IndexSet`].
42//! * `borsh` (**deprecated**): Adds implementations for [`BorshSerialize`] and
43//! [`BorshDeserialize`] to [`IndexMap`] and [`IndexSet`]. Due to a cyclic
44//! dependency that arose between [`borsh`] and `indexmap`, `borsh v1.5.6`
45//! added an `indexmap` feature that should be used instead of enabling the
46//! feature here.
47//!
48//! _Note: only the `std` feature is enabled by default._
49//!
50//! [feature flags]: https://doc.rust-lang.org/cargo/reference/manifest.html#the-features-section
51//! [`no_std`]: #no-standard-library-targets
52//! [`Serialize`]: `::serde::Serialize`
53//! [`Deserialize`]: `::serde::Deserialize`
54//! [`BorshSerialize`]: `::borsh::BorshSerialize`
55//! [`BorshDeserialize`]: `::borsh::BorshDeserialize`
56//! [`borsh`]: `::borsh`
57//! [`arbitrary::Arbitrary`]: `::arbitrary::Arbitrary`
58//! [`quickcheck::Arbitrary`]: `::quickcheck::Arbitrary`
59//!
60//! ### Alternate Hashers
61//!
62//! [`IndexMap`] and [`IndexSet`] have a default hasher type
63//! [`S = RandomState`][std::collections::hash_map::RandomState],
64//! just like the standard `HashMap` and `HashSet`, which is resistant to
65//! HashDoS attacks but not the most performant. Type aliases can make it easier
66//! to use alternate hashers:
67//!
68//! ```
69//! use fnv::FnvBuildHasher;
70//! use indexmap::{IndexMap, IndexSet};
71//!
72//! type FnvIndexMap<K, V> = IndexMap<K, V, FnvBuildHasher>;
73//! type FnvIndexSet<T> = IndexSet<T, FnvBuildHasher>;
74//!
75//! let std: IndexSet<i32> = (0..100).collect();
76//! let fnv: FnvIndexSet<i32> = (0..100).collect();
77//! assert_eq!(std, fnv);
78//! ```
79//!
80//! ### Rust Version
81//!
82//! This version of indexmap requires Rust 1.63 or later.
83//!
84//! The indexmap 2.x release series will use a carefully considered version
85//! upgrade policy, where in a later 2.x version, we will raise the minimum
86//! required Rust version.
87//!
88//! ## No Standard Library Targets
89//!
90//! This crate supports being built without `std`, requiring `alloc` instead.
91//! This is chosen by disabling the default "std" cargo feature, by adding
92//! `default-features = false` to your dependency specification.
93//!
94//! - Creating maps and sets using [`new`][IndexMap::new] and
95//! [`with_capacity`][IndexMap::with_capacity] is unavailable without `std`.
96//! Use methods [`IndexMap::default`], [`with_hasher`][IndexMap::with_hasher],
97//! [`with_capacity_and_hasher`][IndexMap::with_capacity_and_hasher] instead.
98//! A no-std compatible hasher will be needed as well, for example
99//! from the crate `twox-hash`.
100//! - Macros [`indexmap!`] and [`indexset!`] are unavailable without `std`. Use
101//! the macros [`indexmap_with_default!`] and [`indexset_with_default!`] instead.
102
103#![cfg_attr(docsrs, feature(doc_cfg))]
104
105extern crate alloc;
106
107#[cfg(feature = "std")]
108#[macro_use]
109extern crate std;
110
111use alloc::vec::{self, Vec};
112
113mod arbitrary;
114#[macro_use]
115mod macros;
116#[cfg(feature = "borsh")]
117mod borsh;
118#[cfg(feature = "serde")]
119mod serde;
120mod util;
121
122pub mod map;
123pub mod set;
124
125// Placed after `map` and `set` so new `rayon` methods on the types
126// are documented after the "normal" methods.
127#[cfg(feature = "rayon")]
128mod rayon;
129
130pub use crate::map::IndexMap;
131pub use crate::set::IndexSet;
132pub use equivalent::Equivalent;
133
134// shared private items
135
136/// Hash value newtype. Not larger than usize, since anything larger
137/// isn't used for selecting position anyway.
138#[derive(Clone, Copy, Debug, PartialEq)]
139struct HashValue(usize);
140
141impl HashValue {
142 #[inline(always)]
143 fn get(self) -> u64 {
144 self.0 as u64
145 }
146}
147
148#[derive(Copy, Debug)]
149struct Bucket<K, V> {
150 hash: HashValue,
151 key: K,
152 value: V,
153}
154
155impl<K, V> Clone for Bucket<K, V>
156where
157 K: Clone,
158 V: Clone,
159{
160 fn clone(&self) -> Self {
161 Bucket {
162 hash: self.hash,
163 key: self.key.clone(),
164 value: self.value.clone(),
165 }
166 }
167
168 fn clone_from(&mut self, other: &Self) {
169 self.hash = other.hash;
170 self.key.clone_from(&other.key);
171 self.value.clone_from(&other.value);
172 }
173}
174
175impl<K, V> Bucket<K, V> {
176 // field accessors -- used for `f` instead of closures in `.map(f)`
177 fn key_ref(&self) -> &K {
178 &self.key
179 }
180 fn value_ref(&self) -> &V {
181 &self.value
182 }
183 fn value_mut(&mut self) -> &mut V {
184 &mut self.value
185 }
186 fn key(self) -> K {
187 self.key
188 }
189 fn value(self) -> V {
190 self.value
191 }
192 fn key_value(self) -> (K, V) {
193 (self.key, self.value)
194 }
195 fn refs(&self) -> (&K, &V) {
196 (&self.key, &self.value)
197 }
198 fn ref_mut(&mut self) -> (&K, &mut V) {
199 (&self.key, &mut self.value)
200 }
201 fn muts(&mut self) -> (&mut K, &mut V) {
202 (&mut self.key, &mut self.value)
203 }
204}
205
206trait Entries {
207 type Entry;
208 fn into_entries(self) -> Vec<Self::Entry>;
209 fn as_entries(&self) -> &[Self::Entry];
210 fn as_entries_mut(&mut self) -> &mut [Self::Entry];
211 fn with_entries<F>(&mut self, f: F)
212 where
213 F: FnOnce(&mut [Self::Entry]);
214}
215
216/// The error type for [`try_reserve`][IndexMap::try_reserve] methods.
217#[derive(Clone, PartialEq, Eq, Debug)]
218pub struct TryReserveError {
219 kind: TryReserveErrorKind,
220}
221
222#[derive(Clone, PartialEq, Eq, Debug)]
223enum TryReserveErrorKind {
224 // The standard library's kind is currently opaque to us, otherwise we could unify this.
225 Std(alloc::collections::TryReserveError),
226 CapacityOverflow,
227 AllocError { layout: alloc::alloc::Layout },
228}
229
230// These are not `From` so we don't expose them in our public API.
231impl TryReserveError {
232 fn from_alloc(error: alloc::collections::TryReserveError) -> Self {
233 Self {
234 kind: TryReserveErrorKind::Std(error),
235 }
236 }
237
238 fn from_hashbrown(error: hashbrown::TryReserveError) -> Self {
239 Self {
240 kind: match error {
241 hashbrown::TryReserveError::CapacityOverflow => {
242 TryReserveErrorKind::CapacityOverflow
243 }
244 hashbrown::TryReserveError::AllocError { layout: Layout } => {
245 TryReserveErrorKind::AllocError { layout }
246 }
247 },
248 }
249 }
250}
251
252impl core::fmt::Display for TryReserveError {
253 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
254 let reason: &'static str = match &self.kind {
255 TryReserveErrorKind::Std(e: &TryReserveError) => return core::fmt::Display::fmt(self:e, f),
256 TryReserveErrorKind::CapacityOverflow => {
257 " because the computed capacity exceeded the collection's maximum"
258 }
259 TryReserveErrorKind::AllocError { .. } => {
260 " because the memory allocator returned an error"
261 }
262 };
263 f.write_str(data:"memory allocation failed")?;
264 f.write_str(data:reason)
265 }
266}
267
268#[cfg(feature = "std")]
269#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
270impl std::error::Error for TryReserveError {}
271
272// NOTE: This is copied from the slice module in the std lib.
273/// The error type returned by [`get_disjoint_indices_mut`][`IndexMap::get_disjoint_indices_mut`].
274///
275/// It indicates one of two possible errors:
276/// - An index is out-of-bounds.
277/// - The same index appeared multiple times in the array.
278// (or different but overlapping indices when ranges are provided)
279#[derive(Debug, Clone, PartialEq, Eq)]
280pub enum GetDisjointMutError {
281 /// An index provided was out-of-bounds for the slice.
282 IndexOutOfBounds,
283 /// Two indices provided were overlapping.
284 OverlappingIndices,
285}
286
287impl core::fmt::Display for GetDisjointMutError {
288 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
289 let msg: &'static str = match self {
290 GetDisjointMutError::IndexOutOfBounds => "an index is out of bounds",
291 GetDisjointMutError::OverlappingIndices => "there were overlapping indices",
292 };
293
294 core::fmt::Display::fmt(self:msg, f)
295 }
296}
297
298#[cfg(feature = "std")]
299#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
300impl std::error::Error for GetDisjointMutError {}
301