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
80extern crate alloc;
81
82#[cfg(has_std)]
83#[macro_use]
84extern crate std;
85
86use alloc::vec::{self, Vec};
87
88mod arbitrary;
89#[macro_use]
90mod macros;
91mod equivalent;
92mod mutable_keys;
93#[cfg(feature = "serde")]
94mod serde;
95#[cfg(feature = "serde")]
96pub mod serde_seq;
97mod util;
98
99pub mod map;
100pub 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")]
105mod rayon;
106
107#[cfg(feature = "rustc-rayon")]
108mod rustc;
109
110pub use crate::equivalent::Equivalent;
111pub use crate::map::IndexMap;
112pub 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)]
119struct HashValue(usize);
120
121impl HashValue {
122 #[inline(always)]
123 fn get(self) -> u64 {
124 self.0 as u64
125 }
126}
127
128#[derive(Copy, Debug)]
129struct Bucket<K, V> {
130 hash: HashValue,
131 key: K,
132 value: V,
133}
134
135impl<K, V> Clone for Bucket<K, V>
136where
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
155impl<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
186trait 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}
195