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 //! ### 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 #[macro_use]
  89 mod macros;
  90 mod equivalent;
  91 mod mutable_keys;
  92 #[cfg(feature = "serde")]
  93 mod serde;
  94 #[cfg(feature = "serde")]
  95 pub mod serde_seq;
  96 mod util;
  97
  98 pub mod map;
  99 pub mod set;
 100
 101 // Placed after `map` and `set` so new `rayon` methods on the types
 102 // are documented after the "normal" methods.
 103 #[cfg(feature = "rayon")]
 104 mod rayon;
 105
 106 #[cfg(feature = "rustc-rayon")]
 107 mod rustc;
 108
 109 pub use crate::equivalent::Equivalent;
 110 pub use crate::map::IndexMap;
 111 pub use crate::set::IndexSet;
 112
 113 // shared private items
 114
 115 /// Hash value newtype. Not larger than usize, since anything larger
 116 /// isn't used for selecting position anyway.
 117 #[derive(Clone, Copy, Debug, PartialEq)]
 118 struct HashValue(usize);
 119
 120 impl HashValue {
 121     #[inline(always)]
 122     fn get(self) -> u64 {
 123         self.0 as u64
 124     }
 125 }
 126
 127 #[derive(Copy, Debug)]
 128 struct Bucket<K, V> {
 129     hash: HashValue,
 130     key: K,
 131     value: V,
 132 }
 133
 134 impl<K, V> Clone for Bucket<K, V>
 135 where
 136     K: Clone,
 137     V: Clone,
 138 {
 139     fn clone(&self) -> Self {
 140         Bucket {
 141             hash: self.hash,
 142             key: self.key.clone(),
 143             value: self.value.clone(),
 144         }
 145     }
 146
 147     fn clone_from(&mut self, other: &Self) {
 148         self.hash = other.hash;
 149         self.key.clone_from(&other.key);
 150         self.value.clone_from(&other.value);
 151     }
 152 }
 153
 154 impl<K, V> Bucket<K, V> {
 155     // field accessors -- used for `f` instead of closures in `.map(f)`
 156     fn key_ref(&self) -> &K {
 157         &self.key
 158     }
 159     fn value_ref(&self) -> &V {
 160         &self.value
 161     }
 162     fn value_mut(&mut self) -> &mut V {
 163         &mut self.value
 164     }
 165     fn key(self) -> K {
 166         self.key
 167     }
 168     fn value(self) -> V {
 169         self.value
 170     }
 171     fn key_value(self) -> (K, V) {
 172         (self.key, self.value)
 173     }
 174     fn refs(&self) -> (&K, &V) {
 175         (&self.key, &self.value)
 176     }
 177     fn ref_mut(&mut self) -> (&K, &mut V) {
 178         (&self.key, &mut self.value)
 179     }
 180     fn muts(&mut self) -> (&mut K, &mut V) {
 181         (&mut self.key, &mut self.value)
 182     }
 183 }
 184
 185 trait Entries {
 186     type Entry;
 187     fn into_entries(self) -> Vec<Self::Entry>;
 188     fn as_entries(&self) -> &[Self::Entry];
 189     fn as_entries_mut(&mut self) -> &mut [Self::Entry];
 190     fn with_entries<F>(&mut self, f: F)
 191     where
 192         F: FnOnce(&mut [Self::Entry]);
 193 }