extract_map/
lib.rs

1//! See [`ExtractMap`] for the main documentation.
2//!
3//! ## MSRV
4//!
5//! The Minimum Supported Rust Version for this crate is 1.70, and raising it is considered a breaking change.
6#![warn(clippy::pedantic, rust_2018_idioms, missing_docs)]
7
8use std::{
9    collections::hash_map::RandomState,
10    fmt::Debug,
11    hash::{BuildHasher, Hash, Hasher as _},
12    marker::PhantomData,
13    mem::{replace, ManuallyDrop},
14};
15
16use hashbrown::{hash_table::Entry as RawEntry, HashTable};
17use mut_guard::MutGuard;
18
19#[doc(hidden)]
20pub mod doc_examples;
21pub mod entry;
22#[doc(hidden)]
23pub mod iter;
24mod mut_guard;
25#[cfg(feature = "serde")]
26mod serde;
27#[cfg(feature = "typesize")]
28mod typesize;
29
30#[cfg(feature = "serde")]
31pub use serde::serialize_as_map;
32
33fn hash_one<S: BuildHasher, H: Hash>(build_hasher: &S, val: H) -> u64 {
34    let mut hasher = build_hasher.build_hasher();
35    val.hash(&mut hasher);
36    hasher.finish()
37}
38
39/// A trait for extracting the key for an [`ExtractMap`].
40///
41/// This is relied on for correctness in the same way as [`Hash`] and [`Eq`] are and
42/// is purely designed for directly referencing a field with no interior mutability or
43/// static return type.
44pub trait ExtractKey<K: Hash + Eq> {
45    /// Extracts the key that this value should be referred to with.
46    fn extract_key(&self) -> &K;
47}
48
49/// A hash map for memory efficent storage of value types which contain their own keys.
50///
51/// This is backed by [`hashbrown::HashTable`], which is the backing storage for [`std`]'s [`HashSet`] and [`HashMap`].
52///
53/// The default hashing algorithm is the same as the standard library's hashing collections, [`RandomState`],
54/// although your own hasher can be provided via [`ExtractMap::with_hasher`] and it's similar methods.
55///
56/// [`HashSet`]: std::collections::HashSet
57/// [`HashMap`]: std::collections::HashMap
58pub struct ExtractMap<K, V, S = RandomState> {
59    // Any new fields added should be added to the `typesize` impl
60    table: hashbrown::HashTable<V>,
61    phantom: PhantomData<K>,
62    build_hasher: S,
63}
64
65impl<K, V, S: Default> Default for ExtractMap<K, V, S> {
66    fn default() -> Self {
67        Self::with_hasher(S::default())
68    }
69}
70
71impl<K, V> ExtractMap<K, V, RandomState> {
72    /// Creates a new, empty [`ExtractMap`] with the [`RandomState`] hasher.
73    #[must_use]
74    pub fn new() -> Self {
75        Self::with_hasher(RandomState::new())
76    }
77
78    /// Creates a new [`ExtractMap`] with the [`RandomState`] hasher and preallocated capacity.
79    ///
80    /// # Examples
81    /// ```
82    /// use extract_map::{ExtractMap, ExtractKey};
83    /// # use extract_map::doc_examples::User;
84    ///
85    /// let map = ExtractMap::<u64, User>::with_capacity(5);
86    ///
87    /// assert_eq!(map.len(), 0);
88    /// assert!(map.capacity() >= 5);
89    /// ```
90    #[must_use]
91    pub fn with_capacity(capacity: usize) -> Self {
92        Self::with_capacity_and_hasher(capacity, RandomState::new())
93    }
94}
95
96impl<K, V, S> ExtractMap<K, V, S> {
97    /// Creates a new, empty [`ExtractMap`] with the provided hasher.
98    #[must_use]
99    pub fn with_hasher(hash_builder: S) -> Self {
100        Self {
101            table: HashTable::new(),
102            phantom: PhantomData,
103            build_hasher: hash_builder,
104        }
105    }
106
107    /// Creates a new [`ExtractMap`] with the provided hasher and preallocated capacity.
108    ///
109    /// # Examples
110    /// ```
111    /// use std::collections::hash_map::RandomState;
112    ///
113    /// use extract_map::{ExtractMap, ExtractKey};
114    /// # use extract_map::doc_examples::User;
115    ///
116    /// let map = ExtractMap::<u64, User>::with_capacity_and_hasher(5, RandomState::new());
117    ///
118    /// assert!(map.is_empty());
119    /// assert!(map.capacity() >= 5);
120    /// ```
121    #[must_use]
122    pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
123        Self {
124            table: HashTable::with_capacity(capacity),
125            phantom: PhantomData,
126            build_hasher: hash_builder,
127        }
128    }
129}
130
131impl<K, V, S> ExtractMap<K, V, S>
132where
133    K: Hash + Eq,
134    V: ExtractKey<K>,
135    S: BuildHasher,
136{
137    fn raw_entry(&mut self, key: &K) -> RawEntry<'_, V> {
138        self.table.entry(
139            hash_one(&self.build_hasher, key),
140            |v| key == v.extract_key(),
141            |v| hash_one(&self.build_hasher, v.extract_key()),
142        )
143    }
144
145    /// Inserts a value into the [`ExtractMap`].
146    ///
147    /// This extracts the key from the value using the [`ExtractKey`] trait, and therefore does not need a key to be provided.
148    ///
149    /// # Examples
150    /// ```
151    /// use extract_map::{ExtractMap, ExtractKey};
152    /// # use extract_map::doc_examples::User;
153    ///
154    /// let mut map = ExtractMap::new();
155    /// map.insert(User { id: 1, name: "Daisy" });
156    /// map.insert(User { id: 2, name: "Elliott" });
157    ///
158    /// assert_eq!(map.len(), 2);
159    /// ```
160    pub fn insert(&mut self, value: V) -> Option<V> {
161        match self.raw_entry(value.extract_key()) {
162            RawEntry::Occupied(entry) => Some(replace(entry.into_mut(), value)),
163            RawEntry::Vacant(entry) => {
164                entry.insert(value);
165                None
166            }
167        }
168    }
169
170    /// Removes a value from the [`ExtractMap`].
171    ///
172    /// # Examples
173    /// ```
174    /// use extract_map::{ExtractMap, ExtractKey};
175    /// # use extract_map::doc_examples::User;
176    ///
177    /// let user = User { id: 1, name: "Daisy" };
178    /// let mut map = ExtractMap::new();
179    /// map.insert(user.clone());
180    ///
181    /// assert_eq!(map.remove(&1), Some(user));
182    /// assert!(map.is_empty())
183    /// ```
184    pub fn remove(&mut self, key: &K) -> Option<V> {
185        let hash = hash_one(&self.build_hasher, key);
186        let entry = self.table.find_entry(hash, |v| key == v.extract_key());
187
188        match entry {
189            Ok(entry) => Some(entry.remove().0),
190            Err(_) => None,
191        }
192    }
193
194    /// Checks if a value is in the [`ExtractMap`].
195    #[must_use]
196    pub fn contains_key(&self, key: &K) -> bool {
197        self.get(key).is_some()
198    }
199
200    /// Retrieves a value from the [`ExtractMap`].
201    #[must_use]
202    pub fn get(&self, key: &K) -> Option<&V> {
203        let hash = hash_one(&self.build_hasher, key);
204        self.table.find(hash, |v| key == v.extract_key())
205    }
206
207    /// Retrieves a mutable guard to a value in the [`ExtractMap`].
208    ///
209    /// This guard is required as the current implementation takes the value out
210    /// of the map and reinserts on Drop to allow mutation of the key field.
211    #[must_use]
212    pub fn get_mut<'a>(&'a mut self, key: &K) -> Option<MutGuard<'a, K, V, S>> {
213        let value = self.remove(key)?;
214        Some(MutGuard {
215            value: ManuallyDrop::new(value),
216            map: self,
217        })
218    }
219}
220
221impl<K, V, S> ExtractMap<K, V, S> {
222    /// Retrieves the number of remaining values that can be inserted before a reallocation.
223    #[must_use]
224    pub fn capacity(&self) -> usize {
225        self.table.capacity()
226    }
227
228    /// Retrieves the number of values currently in the [`ExtractMap`].
229    #[must_use]
230    pub fn len(&self) -> usize {
231        self.table.len()
232    }
233
234    /// Retrieves if the [`ExtractMap`] contains no values.
235    #[must_use]
236    pub fn is_empty(&self) -> bool {
237        self.table.is_empty()
238    }
239
240    /// Returns the total amount of memory allocated internally, in bytes.
241    ///
242    /// The returned number is informational only. It is intended to be
243    /// primarily used for memory profiling.
244    pub fn allocation_size(&self) -> usize {
245        self.table.allocation_size()
246    }
247
248    /// Retrieves an iterator over the borrowed values.
249    ///
250    /// If you need an iterator over the keys and values, simply use [`ExtractKey`].
251    ///
252    /// Use [`IntoIterator::into_iter`] for an iterator over owned values.
253    pub fn iter(&self) -> iter::Iter<'_, V> {
254        self.into_iter()
255    }
256
257    /// Retrieves a iterator over mutable borrowed values.
258    ///
259    /// If you need an iterator over the keys and values, simply use [`ExtractKey`], but do not mutate the key.
260    ///
261    /// Use [`IntoIterator::into_iter`] for an iterator over owned values.
262    pub fn iter_mut(&mut self) -> iter::IterMut<'_, V> {
263        self.into_iter()
264    }
265}
266
267impl<K, V: Clone, S: Clone> Clone for ExtractMap<K, V, S> {
268    fn clone(&self) -> Self {
269        Self {
270            build_hasher: self.build_hasher.clone(),
271            table: self.table.clone(),
272            phantom: PhantomData,
273        }
274    }
275
276    fn clone_from(&mut self, source: &Self) {
277        self.table.clone_from(&source.table);
278        self.build_hasher.clone_from(&source.build_hasher);
279    }
280}
281
282impl<K, V, S> Debug for ExtractMap<K, V, S>
283where
284    K: Debug + Hash + Eq,
285    V: Debug + ExtractKey<K>,
286{
287    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
288        f.debug_map()
289            .entries(self.iter().map(|v| (v.extract_key(), v)))
290            .finish()
291    }
292}
293
294impl<K, V, S> PartialEq for ExtractMap<K, V, S>
295where
296    K: Hash + Eq,
297    V: ExtractKey<K> + PartialEq,
298    S: BuildHasher,
299{
300    fn eq(&self, other: &Self) -> bool {
301        if self.len() != other.len() {
302            return false;
303        }
304
305        self.iter().all(|v| {
306            let k = v.extract_key();
307
308            other.get(k).is_some_and(|other_v| {
309                let other_k = other_v.extract_key();
310                k == other_k && v == other_v
311            })
312        })
313    }
314}
315
316impl<K, V, S> FromIterator<V> for ExtractMap<K, V, S>
317where
318    K: Hash + Eq,
319    V: ExtractKey<K>,
320    S: BuildHasher + Default,
321{
322    fn from_iter<T: IntoIterator<Item = V>>(iter: T) -> Self {
323        let iter = iter.into_iter();
324        let mut this = Self::with_capacity_and_hasher(iter.size_hint().0, S::default());
325
326        for value in iter {
327            this.insert(value);
328        }
329
330        this
331    }
332}
333
334impl<K, V, S> Extend<V> for ExtractMap<K, V, S>
335where
336    K: Hash + Eq,
337    V: ExtractKey<K>,
338    S: BuildHasher,
339{
340    fn extend<T: IntoIterator<Item = V>>(&mut self, iter: T) {
341        for item in iter {
342            self.insert(item);
343        }
344    }
345}
extract_map/lib.rs

extract_map/
lib.rs
