]>
Commit | Line | Data |
---|---|---|
3dfed10e XL |
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 | //! ### Feature 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 | //! ### Alternate Hashers | |
30 | //! | |
31 | //! [`IndexMap`] and [`IndexSet`] have a default hasher type `S = RandomState`, | |
32 | //! just like the standard `HashMap` and `HashSet`, which is resistant to | |
33 | //! HashDoS attacks but not the most performant. Type aliases can make it easier | |
34 | //! to use alternate hashers: | |
35 | //! | |
36 | //! ``` | |
37 | //! use fnv::FnvBuildHasher; | |
38 | //! use fxhash::FxBuildHasher; | |
39 | //! use indexmap::{IndexMap, IndexSet}; | |
40 | //! | |
41 | //! type FnvIndexMap<K, V> = IndexMap<K, V, FnvBuildHasher>; | |
42 | //! type FnvIndexSet<T> = IndexSet<T, FnvBuildHasher>; | |
43 | //! | |
44 | //! type FxIndexMap<K, V> = IndexMap<K, V, FxBuildHasher>; | |
45 | //! type FxIndexSet<T> = IndexSet<T, FxBuildHasher>; | |
46 | //! | |
47 | //! let std: IndexSet<i32> = (0..100).collect(); | |
48 | //! let fnv: FnvIndexSet<i32> = (0..100).collect(); | |
49 | //! let fx: FxIndexSet<i32> = (0..100).collect(); | |
50 | //! assert_eq!(std, fnv); | |
51 | //! assert_eq!(std, fx); | |
52 | //! ``` | |
53 | //! | |
54 | //! ### Rust Version | |
55 | //! | |
923072b8 | 56 | //! This version of indexmap requires Rust 1.56 or later. |
3dfed10e XL |
57 | //! |
58 | //! The indexmap 1.x release series will use a carefully considered version | |
59 | //! upgrade policy, where in a later 1.x version, we will raise the minimum | |
60 | //! required Rust version. | |
61 | //! | |
62 | //! ## No Standard Library Targets | |
63 | //! | |
5869c6ff | 64 | //! This crate supports being built without `std`, requiring |
3dfed10e XL |
65 | //! `alloc` instead. This is enabled automatically when it is detected that |
66 | //! `std` is not available. There is no crate feature to enable/disable to | |
67 | //! trigger this. It can be tested by building for a std-less target. | |
68 | //! | |
69 | //! - Creating maps and sets using [`new`][IndexMap::new] and | |
70 | //! [`with_capacity`][IndexMap::with_capacity] is unavailable without `std`. | |
71 | //! Use methods [`IndexMap::default`][def], | |
72 | //! [`with_hasher`][IndexMap::with_hasher], | |
73 | //! [`with_capacity_and_hasher`][IndexMap::with_capacity_and_hasher] instead. | |
74 | //! A no-std compatible hasher will be needed as well, for example | |
75 | //! from the crate `twox-hash`. | |
76 | //! - Macros [`indexmap!`] and [`indexset!`] are unavailable without `std`. | |
77 | //! | |
78 | //! [def]: map/struct.IndexMap.html#impl-Default | |
79 | ||
3dfed10e XL |
80 | extern crate alloc; |
81 | ||
82 | #[cfg(has_std)] | |
83 | #[macro_use] | |
84 | extern crate std; | |
85 | ||
3dfed10e XL |
86 | use alloc::vec::{self, Vec}; |
87 | ||
6522a427 | 88 | mod arbitrary; |
3dfed10e XL |
89 | #[macro_use] |
90 | mod macros; | |
91 | mod equivalent; | |
92 | mod mutable_keys; | |
5869c6ff | 93 | #[cfg(feature = "serde")] |
3dfed10e | 94 | mod serde; |
5869c6ff XL |
95 | #[cfg(feature = "serde")] |
96 | pub mod serde_seq; | |
3dfed10e XL |
97 | mod util; |
98 | ||
99 | pub mod map; | |
100 | pub mod set; | |
101 | ||
102 | // Placed after `map` and `set` so new `rayon` methods on the types | |
103 | // are documented after the "normal" methods. | |
104 | #[cfg(feature = "rayon")] | |
105 | mod rayon; | |
106 | ||
5099ac24 FG |
107 | #[cfg(feature = "rustc-rayon")] |
108 | mod rustc; | |
109 | ||
3dfed10e XL |
110 | pub use crate::equivalent::Equivalent; |
111 | pub use crate::map::IndexMap; | |
112 | pub use crate::set::IndexSet; | |
113 | ||
114 | // shared private items | |
115 | ||
116 | /// Hash value newtype. Not larger than usize, since anything larger | |
117 | /// isn't used for selecting position anyway. | |
118 | #[derive(Clone, Copy, Debug, PartialEq)] | |
119 | struct HashValue(usize); | |
120 | ||
121 | impl HashValue { | |
122 | #[inline(always)] | |
123 | fn get(self) -> u64 { | |
124 | self.0 as u64 | |
125 | } | |
126 | } | |
127 | ||
128 | #[derive(Copy, Debug)] | |
129 | struct Bucket<K, V> { | |
130 | hash: HashValue, | |
131 | key: K, | |
132 | value: V, | |
133 | } | |
134 | ||
135 | impl<K, V> Clone for Bucket<K, V> | |
136 | where | |
137 | K: Clone, | |
138 | V: Clone, | |
139 | { | |
140 | fn clone(&self) -> Self { | |
141 | Bucket { | |
142 | hash: self.hash, | |
143 | key: self.key.clone(), | |
144 | value: self.value.clone(), | |
145 | } | |
146 | } | |
147 | ||
148 | fn clone_from(&mut self, other: &Self) { | |
149 | self.hash = other.hash; | |
150 | self.key.clone_from(&other.key); | |
151 | self.value.clone_from(&other.value); | |
152 | } | |
153 | } | |
154 | ||
155 | impl<K, V> Bucket<K, V> { | |
156 | // field accessors -- used for `f` instead of closures in `.map(f)` | |
157 | fn key_ref(&self) -> &K { | |
158 | &self.key | |
159 | } | |
160 | fn value_ref(&self) -> &V { | |
161 | &self.value | |
162 | } | |
163 | fn value_mut(&mut self) -> &mut V { | |
164 | &mut self.value | |
165 | } | |
166 | fn key(self) -> K { | |
167 | self.key | |
168 | } | |
5099ac24 FG |
169 | fn value(self) -> V { |
170 | self.value | |
171 | } | |
3dfed10e XL |
172 | fn key_value(self) -> (K, V) { |
173 | (self.key, self.value) | |
174 | } | |
175 | fn refs(&self) -> (&K, &V) { | |
176 | (&self.key, &self.value) | |
177 | } | |
178 | fn ref_mut(&mut self) -> (&K, &mut V) { | |
179 | (&self.key, &mut self.value) | |
180 | } | |
181 | fn muts(&mut self) -> (&mut K, &mut V) { | |
182 | (&mut self.key, &mut self.value) | |
183 | } | |
184 | } | |
185 | ||
186 | trait Entries { | |
187 | type Entry; | |
188 | fn into_entries(self) -> Vec<Self::Entry>; | |
189 | fn as_entries(&self) -> &[Self::Entry]; | |
190 | fn as_entries_mut(&mut self) -> &mut [Self::Entry]; | |
191 | fn with_entries<F>(&mut self, f: F) | |
192 | where | |
193 | F: FnOnce(&mut [Self::Entry]); | |
194 | } |