vendor/indexmap/src/lib.rs

   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.63 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 } => {
 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 = match &self.kind {
 263             TryReserveErrorKind::Std(e) => return core::fmt::Display::fmt(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("memory allocation failed")?;
 272         f.write_str(reason)
 273     }
 274 }
 275
 276 #[cfg(feature = "std")]
 277 #[cfg_attr(docsrs, doc(cfg(feature = "std")))]
 278 impl std::error::Error for TryReserveError {}