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 | |
109 | extern crate alloc; |
110 | |
111 | #[cfg (feature = "std" )] |
112 | #[macro_use ] |
113 | extern crate std; |
114 | |
115 | use alloc::vec::{self, Vec}; |
116 | |
117 | mod arbitrary; |
118 | #[macro_use ] |
119 | mod macros; |
120 | mod mutable_keys; |
121 | #[cfg (feature = "serde" )] |
122 | #[cfg_attr (docsrs, doc(cfg(feature = "serde" )))] |
123 | mod serde; |
124 | mod util; |
125 | |
126 | pub mod map; |
127 | pub 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" )))] |
133 | mod rayon; |
134 | |
135 | #[cfg (feature = "rustc-rayon" )] |
136 | mod rustc; |
137 | |
138 | pub use crate::map::IndexMap; |
139 | pub use crate::set::IndexSet; |
140 | pub 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)] |
147 | struct HashValue(usize); |
148 | |
149 | impl HashValue { |
150 | #[inline (always)] |
151 | fn get(self) -> u64 { |
152 | self.0 as u64 |
153 | } |
154 | } |
155 | |
156 | #[derive (Copy, Debug)] |
157 | struct Bucket<K, V> { |
158 | hash: HashValue, |
159 | key: K, |
160 | value: V, |
161 | } |
162 | |
163 | impl<K, V> Clone for Bucket<K, V> |
164 | where |
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 | |
183 | impl<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 | |
214 | trait 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)] |
226 | pub struct TryReserveError { |
227 | kind: TryReserveErrorKind, |
228 | } |
229 | |
230 | #[derive (Clone, PartialEq, Eq, Debug)] |
231 | enum 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. |
239 | impl 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 | |
260 | impl 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" )))] |
278 | impl std::error::Error for TryReserveError {} |
279 | |