Debian Codegraph @

.cargo/vendor/indexmap/src/lib.rs

raw
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 //!
56 //! This version of indexmap requires Rust 1.56 or later.
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 //!
64 //! This crate supports being built without `std`, requiring
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
80 extern crate alloc;
81
82 #[cfg(has_std)]
83 #[macro_use]
84 extern crate std;
85
86 use alloc::vec::{self, Vec};
87
88 mod arbitrary;
89 #[macro_use]
90 mod macros;
91 mod equivalent;
92 mod mutable_keys;
93 #[cfg(feature = "serde")]
94 mod serde;
95 #[cfg(feature = "serde")]
96 pub mod serde_seq;
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
107 #[cfg(feature = "rustc-rayon")]
108 mod rustc;
109
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 }
169 fn value(self) -> V {
170 self.value
171 }
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 }