1// We *mostly* avoid unsafe code, but `map::core::raw` allows it to use `RawTable` buckets.
2#![deny(unsafe_code)]
3#![warn(rust_2018_idioms)]
4#![doc(html_root_url = "https://docs.rs/indexmap/1/")]
5#![no_std]
6
7//! [`IndexMap`] is a hash table where the iteration order of the key-value
8//! pairs is independent of the hash values of the keys.
9//!
10//! [`IndexSet`] is a corresponding hash set using the same implementation and
11//! with similar properties.
12//!
13//! [`IndexMap`]: map/struct.IndexMap.html
14//! [`IndexSet`]: set/struct.IndexSet.html
15//!
16//!
17//! ### Highlights
18//!
19//! [`IndexMap`] and [`IndexSet`] are drop-in compatible with the std `HashMap`
20//! and `HashSet`, but they also have some features of note:
21//!
22//! - The ordering semantics (see their documentation for details)
23//! - Sorting methods and the [`.pop()`][IndexMap::pop] methods.
24//! - The [`Equivalent`] trait, which offers more flexible equality definitions
25//! between borrowed and owned versions of keys.
26//! - The [`MutableKeys`][map::MutableKeys] trait, which gives opt-in mutable
27//! access to hash map keys.
28//!
29//! ### Feature Flags
30//!
31//! To reduce the amount of compiled code in the crate by default, certain
32//! features are gated behind [feature flags]. These allow you to opt in to (or
33//! out of) functionality. Below is a list of the features available in this
34//! crate.
35//!
36//! * `std`: Enables features which require the Rust standard library. For more
37//! information see the section on [`no_std`].
38//! * `rayon`: Enables parallel iteration and other parallel methods.
39//! * `serde`: Adds implementations for [`Serialize`] and [`Deserialize`]
40//! to [`IndexMap`] and [`IndexSet`]. Alternative implementations for
41//! (de)serializing [`IndexMap`] as an ordered sequence are available in the
42//! [`map::serde_seq`] module.
43//! * `arbitrary`: Adds implementations for the [`arbitrary::Arbitrary`] trait
44//! to [`IndexMap`] and [`IndexSet`].
45//! * `quickcheck`: Adds implementations for the [`quickcheck::Arbitrary`] trait
46//! to [`IndexMap`] and [`IndexSet`].
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//! [`arbitrary::Arbitrary`]: `::arbitrary::Arbitrary`
55//! [`quickcheck::Arbitrary`]: `::quickcheck::Arbitrary`
56//!
57//! ### Alternate Hashers
58//!
59//! [`IndexMap`] and [`IndexSet`] have a default hasher type `S = 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.64 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`][def],
99//! [`with_hasher`][IndexMap::with_hasher],
100//! [`with_capacity_and_hasher`][IndexMap::with_capacity_and_hasher] instead.
101//! A no-std compatible hasher will be needed as well, for example
102//! from the crate `twox-hash`.
103//! - Macros [`indexmap!`] and [`indexset!`] are unavailable without `std`.
104//!
105//! [def]: map/struct.IndexMap.html#impl-Default
106
107#![cfg_attr(docsrs, feature(doc_cfg))]
108
109extern crate alloc;
110
111#[cfg(feature = "std")]
112#[macro_use]
113extern crate std;
114
115use alloc::vec::{self, Vec};
116
117mod arbitrary;
118#[macro_use]
119mod macros;
120mod mutable_keys;
121#[cfg(feature = "serde")]
122#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
123mod serde;
124mod util;
125
126pub mod map;
127pub mod set;
128
129// Placed after `map` and `set` so new `rayon` methods on the types
130// are documented after the "normal" methods.
131#[cfg(feature = "rayon")]
132#[cfg_attr(docsrs, doc(cfg(feature = "rayon")))]
133mod rayon;
134
135#[cfg(feature = "rustc-rayon")]
136mod rustc;
137
138pub use crate::map::IndexMap;
139pub use crate::set::IndexSet;
140pub use equivalent::Equivalent;
141
142// shared private items
143
144/// Hash value newtype. Not larger than usize, since anything larger
145/// isn't used for selecting position anyway.
146#[derive(Clone, Copy, Debug, PartialEq)]
147struct HashValue(usize);
148
149impl HashValue {
150 #[inline(always)]
151 fn get(self) -> u64 {
152 self.0 as u64
153 }
154}
155
156#[derive(Copy, Debug)]
157struct Bucket<K, V> {
158 hash: HashValue,
159 key: K,
160 value: V,
161}
162
163impl<K, V> Clone for Bucket<K, V>
164where
165 K: Clone,
166 V: Clone,
167{
168 fn clone(&self) -> Self {
169 Bucket {
170 hash: self.hash,
171 key: self.key.clone(),
172 value: self.value.clone(),
173 }
174 }
175
176 fn clone_from(&mut self, other: &Self) {
177 self.hash = other.hash;
178 self.key.clone_from(&other.key);
179 self.value.clone_from(&other.value);
180 }
181}
182
183impl<K, V> Bucket<K, V> {
184 // field accessors -- used for `f` instead of closures in `.map(f)`
185 fn key_ref(&self) -> &K {
186 &self.key
187 }
188 fn value_ref(&self) -> &V {
189 &self.value
190 }
191 fn value_mut(&mut self) -> &mut V {
192 &mut self.value
193 }
194 fn key(self) -> K {
195 self.key
196 }
197 fn value(self) -> V {
198 self.value
199 }
200 fn key_value(self) -> (K, V) {
201 (self.key, self.value)
202 }
203 fn refs(&self) -> (&K, &V) {
204 (&self.key, &self.value)
205 }
206 fn ref_mut(&mut self) -> (&K, &mut V) {
207 (&self.key, &mut self.value)
208 }
209 fn muts(&mut self) -> (&mut K, &mut V) {
210 (&mut self.key, &mut self.value)
211 }
212}
213
214trait Entries {
215 type Entry;
216 fn into_entries(self) -> Vec<Self::Entry>;
217 fn as_entries(&self) -> &[Self::Entry];
218 fn as_entries_mut(&mut self) -> &mut [Self::Entry];
219 fn with_entries<F>(&mut self, f: F)
220 where
221 F: FnOnce(&mut [Self::Entry]);
222}
223
224/// The error type for `try_reserve` methods.
225#[derive(Clone, PartialEq, Eq, Debug)]
226pub struct TryReserveError {
227 kind: TryReserveErrorKind,
228}
229
230#[derive(Clone, PartialEq, Eq, Debug)]
231enum TryReserveErrorKind {
232 // The standard library's kind is currently opaque to us, otherwise we could unify this.
233 Std(alloc::collections::TryReserveError),
234 CapacityOverflow,
235 AllocError { layout: alloc::alloc::Layout },
236}
237
238// These are not `From` so we don't expose them in our public API.
239impl TryReserveError {
240 fn from_alloc(error: alloc::collections::TryReserveError) -> Self {
241 Self {
242 kind: TryReserveErrorKind::Std(error),
243 }
244 }
245
246 fn from_hashbrown(error: hashbrown::TryReserveError) -> Self {
247 Self {
248 kind: match error {
249 hashbrown::TryReserveError::CapacityOverflow => {
250 TryReserveErrorKind::CapacityOverflow
251 }
252 hashbrown::TryReserveError::AllocError { layout: Layout } => {
253 TryReserveErrorKind::AllocError { layout }
254 }
255 },
256 }
257 }
258}
259
260impl core::fmt::Display for TryReserveError {
261 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
262 let reason: &str = match &self.kind {
263 TryReserveErrorKind::Std(e: &TryReserveError) => return core::fmt::Display::fmt(self:e, f),
264 TryReserveErrorKind::CapacityOverflow => {
265 " because the computed capacity exceeded the collection's maximum"
266 }
267 TryReserveErrorKind::AllocError { .. } => {
268 " because the memory allocator returned an error"
269 }
270 };
271 f.write_str(data:"memory allocation failed")?;
272 f.write_str(data:reason)
273 }
274}
275
276#[cfg(feature = "std")]
277#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
278impl std::error::Error for TryReserveError {}
279