memo_map/
lib.rs

1//! A concurrent insert only hash map.
2//!
3//! This crate implements a "memo map" which is in many ways similar to a
4//! [`HashMap`] with some crucial differences:
5//!
6//! * Unlike a regular hash map, a memo map is thread safe and synchronized.
7//! * Adding or retrieving keys works through a shared reference, removing only
8//!   through a mutable reference.
9//! * Retrieving a value from a memo map returns a plain old reference.
10//!
11//! Together these purposes allow one to use this type of structure to
12//! implement something similar to lazy loading in places where the API
13//! has been constrained to references before.
14//!
15//! The entries in the map are individually boxed up so that resizing of the
16//! map retains the previously issued references.
17//!
18//! ```
19//! use memo_map::MemoMap;
20//!
21//! let memo = MemoMap::new();
22//! let one = memo.get_or_insert(&1, || "one".to_string());
23//! let one2 = memo.get_or_insert(&1, || "not one".to_string());
24//! assert_eq!(one, "one");
25//! assert_eq!(one2, "one");
26//! ```
27//!
28//! # Notes on Iteration
29//!
30//! Because the memo map internally uses a mutex it needs to be held during
31//! iteration.  This is potentially dangerous as it means you can easily
32//! deadlock yourself when trying to use the memo map while iterating.  The
33//! iteration functionality thus has to be used with great care.
34//!
35//! # Notes on Removal
36//!
37//! Items can be removed from a memo map but this operation requires a mutable
38//! reference to the memo map.  This is so that it can ensure that there are no
39//! borrows outstanding that would be invalidated through the removal of the item.
40use std::borrow::Borrow;
41use std::cell::UnsafeCell;
42use std::collections::hash_map::{self, Entry, RandomState};
43use std::collections::HashMap;
44use std::convert::Infallible;
45use std::hash::{BuildHasher, Hash};
46use std::marker::PhantomPinned;
47use std::mem::{transmute, ManuallyDrop};
48use std::pin::Pin;
49use std::sync::{Mutex, MutexGuard};
50
51macro_rules! lock {
52    ($mutex:expr) => {
53        match $mutex.lock() {
54            Ok(guard) => guard,
55            Err(poisoned) => poisoned.into_inner(),
56        }
57    };
58}
59
60macro_rules! get_mut {
61    (let $target:ident, $mutex:expr) => {
62        let mut $target = $mutex.get_mut();
63        let $target = match $target {
64            Ok(guard) => guard,
65            Err(ref mut poisoned) => poisoned.get_mut(),
66        };
67    };
68}
69
70struct StableEntryInner<K, V> {
71    key: K,
72    value: UnsafeCell<V>,
73    _pin: PhantomPinned,
74}
75
76struct StableEntry<K, V>(Pin<Box<StableEntryInner<K, V>>>);
77
78impl<K, V> StableEntry<K, V> {
79    fn new(key: K, value: V) -> Self {
80        StableEntry(Box::pin(StableEntryInner {
81            key,
82            value: UnsafeCell::new(value),
83            _pin: PhantomPinned,
84        }))
85    }
86
87    fn key(&self) -> &K {
88        &self.0.key
89    }
90
91    fn value(&self) -> &V {
92        // SAFETY: Values are only mutated through an exclusive borrow of the
93        // MemoMap. Shared access to a MemoMap never changes existing values.
94        unsafe { &*self.0.value.get() }
95    }
96
97    fn value_ptr(&self) -> *mut V {
98        self.0.value.get()
99    }
100
101    fn into_value(self) -> V {
102        // SAFETY: The entry has been removed from the map, and an exclusive
103        // borrow of the MemoMap ensures no references into it are outstanding.
104        unsafe { Pin::into_inner_unchecked(self.0) }
105            .value
106            .into_inner()
107    }
108}
109
110impl<K: Clone, V: Clone> Clone for StableEntry<K, V> {
111    fn clone(&self) -> Self {
112        StableEntry::new(self.key().clone(), self.value().clone())
113    }
114}
115
116impl<K: Hash, V> Hash for StableEntry<K, V> {
117    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
118        self.key().hash(state);
119    }
120}
121
122impl<K: PartialEq, V> PartialEq for StableEntry<K, V> {
123    fn eq(&self, other: &Self) -> bool {
124        self.key().eq(other.key())
125    }
126}
127
128impl<K: Eq, V> Eq for StableEntry<K, V> {}
129
130impl<K, V, Q: ?Sized> Borrow<BorrowedKey<Q>> for StableEntry<K, V>
131where
132    K: Borrow<Q>,
133{
134    fn borrow(&self) -> &BorrowedKey<Q> {
135        BorrowedKey::from_ref(self.key().borrow())
136    }
137}
138
139#[repr(transparent)]
140struct BorrowedKey<Q: ?Sized>(Q);
141
142impl<Q: ?Sized> BorrowedKey<Q> {
143    fn from_ref(key: &Q) -> &Self {
144        // SAFETY: BorrowedKey is transparent over Q, so their references have
145        // identical layouts and metadata.
146        unsafe { &*(key as *const Q as *const BorrowedKey<Q>) }
147    }
148}
149
150impl<Q: Hash + ?Sized> Hash for BorrowedKey<Q> {
151    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
152        self.0.hash(state);
153    }
154}
155
156impl<Q: PartialEq + ?Sized> PartialEq for BorrowedKey<Q> {
157    fn eq(&self, other: &Self) -> bool {
158        self.0.eq(&other.0)
159    }
160}
161
162impl<Q: Eq + ?Sized> Eq for BorrowedKey<Q> {}
163
164type InnerMap<K, V, S> = HashMap<StableEntry<K, V>, (), S>;
165
166struct DebugMap<'a, K, V, S>(&'a InnerMap<K, V, S>);
167
168impl<K: std::fmt::Debug, V: std::fmt::Debug, S> std::fmt::Debug for DebugMap<'_, K, V, S> {
169    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
170        let mut map = f.debug_map();
171        for entry in self.0.keys() {
172            map.entry(entry.key(), entry.value());
173        }
174        map.finish()
175    }
176}
177
178/// An insert only, thread safe hash map to memoize values.
179///
180/// Keys and values need to be [`Sync`] for the map itself to be [`Sync`],
181/// because references to both can be returned after the internal lock is
182/// released.
183///
184/// ```compile_fail
185/// use memo_map::MemoMap;
186/// use std::cell::Cell;
187///
188/// fn assert_sync<T: Sync>() {}
189/// assert_sync::<MemoMap<u32, Cell<u32>>>();
190/// ```
191///
192/// ```compile_fail
193/// use memo_map::MemoMap;
194/// use std::cell::Cell;
195///
196/// fn assert_sync<T: Sync>() {}
197/// assert_sync::<MemoMap<Cell<u32>, u32>>();
198/// ```
199pub struct MemoMap<K, V, S = RandomState> {
200    inner: Mutex<InnerMap<K, V, S>>,
201}
202
203impl<K: std::fmt::Debug, V: std::fmt::Debug, S> std::fmt::Debug for MemoMap<K, V, S> {
204    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
205        let inner = lock!(self.inner);
206        f.debug_struct("MemoMap")
207            .field("inner", &DebugMap(&inner))
208            .finish()
209    }
210}
211
212// SAFETY: Moving a MemoMap between threads moves all stored keys, values, and
213// the hash builder, so each of them must be Send.
214unsafe impl<K: Send, V: Send, S: Send> Send for MemoMap<K, V, S> {}
215
216// SAFETY: Access to the hash map is synchronized, and the keys and values are
217// additionally Sync because shared references to them can outlive the lock.
218unsafe impl<K: Send + Sync, V: Send + Sync, S: Send> Sync for MemoMap<K, V, S> {}
219
220impl<K: Clone, V: Clone, S: Clone> Clone for MemoMap<K, V, S> {
221    fn clone(&self) -> Self {
222        Self {
223            inner: Mutex::new(lock!(self.inner).clone()),
224        }
225    }
226}
227
228impl<K, V, S: Default> Default for MemoMap<K, V, S> {
229    fn default() -> Self {
230        MemoMap {
231            inner: Mutex::new(HashMap::default()),
232        }
233    }
234}
235
236impl<K, V> MemoMap<K, V, RandomState> {
237    /// Creates an empty `MemoMap`.
238    pub fn new() -> MemoMap<K, V, RandomState> {
239        MemoMap {
240            inner: Mutex::default(),
241        }
242    }
243}
244
245impl<K, V, S> MemoMap<K, V, S> {
246    /// Creates an empty `MemoMap` which will use the given hash builder to hash
247    /// keys.
248    pub fn with_hasher(hash_builder: S) -> MemoMap<K, V, S> {
249        MemoMap {
250            inner: Mutex::new(HashMap::with_hasher(hash_builder)),
251        }
252    }
253}
254
255impl<K, V, S> MemoMap<K, V, S>
256where
257    K: Eq + Hash,
258    S: BuildHasher,
259{
260    /// Inserts a value into the memo map.
261    ///
262    /// This inserts a value for a specific key into the memo map.  If the
263    /// key already exists, this method does nothing and instead returns `false`.
264    /// Otherwise the value is inserted and `true` is returned.  It's generally
265    /// recommended to instead use [`get_or_insert`](Self::get_or_insert) or
266    /// it's sibling [`get_or_try_insert`](Self::get_or_try_insert).
267    pub fn insert(&self, key: K, value: V) -> bool {
268        let mut inner = lock!(self.inner);
269        match inner.entry(StableEntry::new(key, value)) {
270            Entry::Occupied(_) => false,
271            Entry::Vacant(vacant) => {
272                vacant.insert(());
273                true
274            }
275        }
276    }
277
278    /// Inserts a value into the memo map replacing the old value.
279    ///
280    /// This has the same restrictions as [`remove`](Self::remove) and
281    /// [`clear`](Self::clear) in that it requires a mutable reference to
282    /// the map.
283    pub fn replace(&mut self, key: K, value: V) {
284        let mut inner = lock!(self.inner);
285        if let Some((entry, _)) = inner.get_key_value(BorrowedKey::from_ref(&key)) {
286            // SAFETY: replace requires an exclusive borrow of the MemoMap, so
287            // no references to a stored value can be outstanding.
288            let old_value = unsafe { std::mem::replace(&mut *entry.value_ptr(), value) };
289            drop(old_value);
290        } else {
291            inner.insert(StableEntry::new(key, value), ());
292        }
293    }
294
295    /// Returns true if the map contains a value for the specified key.
296    ///
297    /// The key may be any borrowed form of the map's key type, but [`Hash`] and
298    /// [`Eq`] on the borrowed form must match those for the key type.
299    pub fn contains_key<Q>(&self, key: &Q) -> bool
300    where
301        Q: Hash + Eq + ?Sized,
302        K: Borrow<Q>,
303    {
304        lock!(self.inner).contains_key(BorrowedKey::from_ref(key))
305    }
306
307    /// Returns a reference to the value corresponding to the key.
308    ///
309    /// The key may be any borrowed form of the map's key type, but [`Hash`] and
310    /// [`Eq`] on the borrowed form must match those for the key type.
311    pub fn get<Q>(&self, key: &Q) -> Option<&V>
312    where
313        Q: Hash + Eq + ?Sized,
314        K: Borrow<Q>,
315    {
316        let inner = lock!(self.inner);
317        let value = inner.get_key_value(BorrowedKey::from_ref(key))?.0.value();
318        Some(unsafe { transmute::<&V, &V>(value) })
319    }
320
321    /// Returns a mutable reference to the value corresponding to the key.
322    ///
323    /// The key may be any borrowed form of the map's key type, but [`Hash`] and
324    /// [`Eq`] on the borrowed form must match those for the key type.
325    #[allow(clippy::mutable_key_type)] // Only the non-hashed value is mutable.
326    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
327    where
328        Q: Hash + Eq + ?Sized,
329        K: Borrow<Q>,
330    {
331        get_mut!(let map, self.inner);
332        let entry = map.get_key_value(BorrowedKey::from_ref(key))?.0;
333        // SAFETY: get_mut requires an exclusive borrow of the MemoMap, so no
334        // other references to the value can be outstanding.
335        Some(unsafe { &mut *entry.value_ptr() })
336    }
337
338    /// Returns a reference to the value corresponding to the key or inserts.
339    ///
340    /// This is the preferred way to work with a memo map: if the value has not
341    /// been in the map yet the creator function is invoked to create the value,
342    /// otherwise the already stored value is returned.  The creator function itself
343    /// can be falliable and the error is passed through.
344    ///
345    /// If the creator is infallible, [`get_or_insert`](Self::get_or_insert) can be used.
346    pub fn get_or_try_insert<Q, F, E>(&self, key: &Q, creator: F) -> Result<&V, E>
347    where
348        Q: Hash + Eq + ToOwned<Owned = K> + ?Sized,
349        K: Borrow<Q>,
350        F: FnOnce() -> Result<V, E>,
351    {
352        let mut inner = lock!(self.inner);
353        let key = BorrowedKey::from_ref(key);
354        if let Some((entry, _)) = inner.get_key_value(key) {
355            return Ok(unsafe { transmute::<&V, &V>(entry.value()) });
356        }
357
358        let entry = StableEntry::new(key.0.to_owned(), creator()?);
359        let value_ptr = match inner.entry(entry) {
360            Entry::Occupied(entry) => entry.key().value_ptr(),
361            Entry::Vacant(entry) => {
362                let value_ptr = entry.key().value_ptr();
363                entry.insert(());
364                value_ptr
365            }
366        };
367        // SAFETY: the entry is individually boxed and cannot be removed while
368        // the returned reference keeps the MemoMap borrowed.
369        Ok(unsafe { &*value_ptr })
370    }
371
372    /// Like [`get_or_insert`](Self::get_or_insert) but with an owned key.
373    pub fn get_or_insert_owned<F>(&self, key: K, creator: F) -> &V
374    where
375        F: FnOnce() -> V,
376    {
377        self.get_or_try_insert_owned(key, || Ok::<_, Infallible>(creator()))
378            .unwrap()
379    }
380
381    /// Like [`get_or_try_insert`](Self::get_or_try_insert) but with an owned key.
382    ///
383    /// If the creator is infallible, [`get_or_insert_owned`](Self::get_or_insert_owned) can be used.
384    pub fn get_or_try_insert_owned<F, E>(&self, key: K, creator: F) -> Result<&V, E>
385    where
386        F: FnOnce() -> Result<V, E>,
387    {
388        let mut inner = lock!(self.inner);
389        if let Some((entry, _)) = inner.get_key_value(BorrowedKey::from_ref(&key)) {
390            return Ok(unsafe { transmute::<&V, &V>(entry.value()) });
391        }
392
393        let entry = StableEntry::new(key, creator()?);
394        let value_ptr = match inner.entry(entry) {
395            Entry::Occupied(entry) => entry.key().value_ptr(),
396            Entry::Vacant(entry) => {
397                let value_ptr = entry.key().value_ptr();
398                entry.insert(());
399                value_ptr
400            }
401        };
402        // SAFETY: the entry is individually boxed and cannot be removed while
403        // the returned reference keeps the MemoMap borrowed.
404        Ok(unsafe { &*value_ptr })
405    }
406
407    /// Returns a reference to the value corresponding to the key or inserts.
408    ///
409    /// This is the preferred way to work with a memo map: if the value has not
410    /// been in the map yet the creator function is invoked to create the value,
411    /// otherwise the already stored value is returned.
412    ///
413    /// If the creator is fallible, [`get_or_try_insert`](Self::get_or_try_insert) can be used.
414    ///
415    /// # Example
416    ///
417    /// ```
418    /// # use memo_map::MemoMap;
419    /// let memo = MemoMap::new();
420    ///
421    /// // first time inserts
422    /// let value = memo.get_or_insert("key", || "23");
423    /// assert_eq!(*value, "23");
424    ///
425    /// // second time returns old value
426    /// let value = memo.get_or_insert("key", || "24");
427    /// assert_eq!(*value, "23");
428    /// ```
429    pub fn get_or_insert<Q, F>(&self, key: &Q, creator: F) -> &V
430    where
431        Q: Hash + Eq + ToOwned<Owned = K> + ?Sized,
432        K: Borrow<Q>,
433        F: FnOnce() -> V,
434    {
435        self.get_or_try_insert(key, || Ok::<_, Infallible>(creator()))
436            .unwrap()
437    }
438
439    /// Removes a key from the memo map, returning the value at the key if the key
440    /// was previously in the map.
441    ///
442    /// A key can only be removed if a mutable reference to the memo map exists.
443    /// In other words a key can not be removed if there can be borrows to the item.
444    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
445    where
446        Q: Hash + Eq + ?Sized,
447        K: Borrow<Q>,
448    {
449        lock!(self.inner)
450            .remove_entry(BorrowedKey::from_ref(key))
451            .map(|(entry, ())| entry.into_value())
452    }
453
454    /// Clears the map, removing all elements.
455    pub fn clear(&mut self) {
456        lock!(self.inner).clear();
457    }
458
459    /// Returns the number of items in the map.
460    ///
461    /// # Example
462    ///
463    /// ```
464    /// # use memo_map::MemoMap;
465    /// let memo = MemoMap::new();
466    ///
467    /// assert_eq!(memo.len(), 0);
468    /// memo.insert(1, "a");
469    /// memo.insert(2, "b");
470    /// memo.insert(2, "not b");
471    /// assert_eq!(memo.len(), 2);
472    /// ```
473    pub fn len(&self) -> usize {
474        lock!(self.inner).len()
475    }
476
477    /// Returns `true` if the memo map contains no items.
478    pub fn is_empty(&self) -> bool {
479        lock!(self.inner).is_empty()
480    }
481
482    /// An iterator visiting all key-value pairs in arbitrary order. The
483    /// iterator element type is `(&'a K, &'a V)`.
484    ///
485    /// Important note: during iteration the map is locked!  This means that you
486    /// must not perform calls to the map or you will run into deadlocks.  This
487    /// makes the iterator rather useless in practice for a lot of operations.
488    pub fn iter(&self) -> Iter<'_, K, V, S> {
489        let guard = lock!(self.inner);
490        let iter = guard.iter();
491        Iter {
492            iter: ManuallyDrop::new(unsafe {
493                transmute::<
494                    hash_map::Iter<'_, StableEntry<K, V>, ()>,
495                    hash_map::Iter<'_, StableEntry<K, V>, ()>,
496                >(iter)
497            }),
498            guard: ManuallyDrop::new(guard),
499        }
500    }
501
502    /// An iterator visiting all key-value pairs in arbitrary order, with mutable
503    /// references to the values.  The iterator element type is `(&'a K, &'a mut V)`.
504    ///
505    /// This iterator requires a mutable reference to the map.
506    #[allow(clippy::mutable_key_type)] // Only the non-hashed values are mutable.
507    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
508        get_mut!(let map, self.inner);
509        IterMut {
510            iter: unsafe {
511                transmute::<
512                    hash_map::IterMut<'_, StableEntry<K, V>, ()>,
513                    hash_map::IterMut<'_, StableEntry<K, V>, ()>,
514                >(map.iter_mut())
515            },
516        }
517    }
518
519    /// An iterator visiting all values mutably in arbitrary order.  The iterator
520    /// element type is `&'a mut V`.
521    ///
522    /// This iterator requires a mutable reference to the map.
523    #[allow(clippy::mutable_key_type)] // Only the non-hashed values are mutable.
524    pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
525        get_mut!(let map, self.inner);
526        ValuesMut {
527            iter: unsafe {
528                transmute::<
529                    hash_map::IterMut<'_, StableEntry<K, V>, ()>,
530                    hash_map::IterMut<'_, StableEntry<K, V>, ()>,
531                >(map.iter_mut())
532            },
533        }
534    }
535
536    /// An iterator visiting all keys in arbitrary order. The iterator element
537    /// type is `&'a K`.
538    pub fn keys(&self) -> Keys<'_, K, V, S> {
539        Keys { iter: self.iter() }
540    }
541}
542
543/// An iterator over the items of a [`MemoMap`].
544///
545/// This struct is created by the [`iter`](MemoMap::iter) method on [`MemoMap`].
546/// See its documentation for more information.
547pub struct Iter<'a, K, V, S> {
548    iter: ManuallyDrop<hash_map::Iter<'a, StableEntry<K, V>, ()>>,
549    guard: ManuallyDrop<MutexGuard<'a, InnerMap<K, V, S>>>,
550}
551
552impl<K, V, S> Drop for Iter<'_, K, V, S> {
553    fn drop(&mut self) {
554        unsafe {
555            // The iterator borrows data protected by the guard, so it must be
556            // dropped before the guard unlocks the map.
557            ManuallyDrop::drop(&mut self.iter);
558            ManuallyDrop::drop(&mut self.guard);
559        }
560    }
561}
562
563impl<'a, K, V, S> Iterator for Iter<'a, K, V, S> {
564    type Item = (&'a K, &'a V);
565
566    fn next(&mut self) -> Option<Self::Item> {
567        self.iter
568            .next()
569            .map(|(entry, ())| (entry.key(), entry.value()))
570    }
571}
572
573/// An iterator over the keys of a [`MemoMap`].
574///
575/// This struct is created by the [`keys`](MemoMap::keys) method on [`MemoMap`].
576/// See its documentation for more information.
577pub struct Keys<'a, K, V, S> {
578    iter: Iter<'a, K, V, S>,
579}
580
581impl<'a, K, V, S> Iterator for Keys<'a, K, V, S> {
582    type Item = &'a K;
583
584    fn next(&mut self) -> Option<Self::Item> {
585        self.iter.next().map(|(k, _)| k)
586    }
587}
588
589/// A mutable iterator over a [`MemoMap`].
590pub struct IterMut<'a, K, V> {
591    iter: hash_map::IterMut<'a, StableEntry<K, V>, ()>,
592}
593
594impl<'a, K, V> Iterator for IterMut<'a, K, V> {
595    type Item = (&'a K, &'a mut V);
596
597    fn next(&mut self) -> Option<Self::Item> {
598        self.iter.next().map(|(entry, ())| {
599            // SAFETY: IterMut holds an exclusive borrow of the MemoMap.
600            (entry.key(), unsafe { &mut *entry.value_ptr() })
601        })
602    }
603}
604
605/// A mutable iterator over a [`MemoMap`].
606pub struct ValuesMut<'a, K, V> {
607    iter: hash_map::IterMut<'a, StableEntry<K, V>, ()>,
608}
609
610impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
611    type Item = &'a mut V;
612
613    fn next(&mut self) -> Option<Self::Item> {
614        self.iter.next().map(|(entry, ())| {
615            // SAFETY: ValuesMut holds an exclusive borrow of the MemoMap.
616            unsafe { &mut *entry.value_ptr() }
617        })
618    }
619}
620
621#[cfg(test)]
622mod tests {
623    use super::*;
624
625    #[test]
626    fn test_insert() {
627        let memo = MemoMap::new();
628        assert!(memo.insert(23u32, Box::new(1u32)));
629        assert!(!memo.insert(23u32, Box::new(2u32)));
630        assert_eq!(memo.get(&23u32).cloned(), Some(Box::new(1)));
631    }
632
633    #[test]
634    fn test_iter() {
635        let memo = MemoMap::new();
636        memo.insert(1, "one");
637        memo.insert(2, "two");
638        memo.insert(3, "three");
639        let mut values = memo.iter().map(|(k, v)| (*k, *v)).collect::<Vec<_>>();
640        values.sort();
641        assert_eq!(values, vec![(1, "one"), (2, "two"), (3, "three")]);
642    }
643
644    #[test]
645    fn test_keys() {
646        let memo = MemoMap::new();
647        memo.insert(1, "one");
648        memo.insert(2, "two");
649        memo.insert(3, "three");
650        let mut values = memo.keys().copied().collect::<Vec<_>>();
651        values.sort();
652        assert_eq!(values, vec![1, 2, 3]);
653    }
654
655    #[test]
656    fn test_contains() {
657        let memo = MemoMap::new();
658        memo.insert(1, "one");
659        assert!(memo.contains_key(&1));
660        assert!(!memo.contains_key(&2));
661    }
662
663    #[test]
664    fn test_remove() {
665        let mut memo = MemoMap::new();
666        memo.insert(1, "one");
667        let value = memo.get(&1);
668        assert!(value.is_some());
669        let old_value = memo.remove(&1);
670        assert_eq!(old_value, Some("one"));
671        let value = memo.get(&1);
672        assert!(value.is_none());
673    }
674
675    #[test]
676    fn test_clear() {
677        let mut memo = MemoMap::new();
678        memo.insert(1, "one");
679        memo.insert(2, "two");
680        assert_eq!(memo.len(), 2);
681        assert!(!memo.is_empty());
682        memo.clear();
683        assert_eq!(memo.len(), 0);
684        assert!(memo.is_empty());
685    }
686
687    #[test]
688    fn test_ref_after_resize() {
689        let memo = MemoMap::new();
690        let mut refs = Vec::new();
691
692        let iterations = if cfg!(miri) { 100 } else { 10000 };
693
694        for key in 0..iterations {
695            refs.push((key, memo.get_or_insert(&key, || Box::new(key))));
696        }
697        for (key, val) in refs {
698            dbg!(key, val);
699            assert_eq!(memo.get(&key), Some(val));
700        }
701    }
702
703    #[test]
704    fn test_ref_after_resize_owned() {
705        let memo = MemoMap::new();
706        let mut refs = Vec::new();
707
708        let iterations = if cfg!(miri) { 100 } else { 10000 };
709
710        for key in 0..iterations {
711            refs.push((
712                key,
713                memo.get_or_insert_owned(key.to_string(), || Box::new(key)),
714            ));
715        }
716        for (key, val) in refs {
717            dbg!(key, val);
718            assert_eq!(memo.get(&key.to_string()), Some(val));
719        }
720    }
721
722    #[test]
723    fn test_key_ref_after_resize() {
724        let memo = MemoMap::new();
725        memo.insert(0usize, 0usize);
726
727        let key = memo.keys().next().unwrap();
728        let iterations = if cfg!(miri) { 100 } else { 10000 };
729        for value in 1..iterations {
730            memo.insert(value, value);
731        }
732
733        assert_eq!(*key, 0);
734    }
735
736    #[test]
737    fn test_borrowed_key_lookup() {
738        let mut memo = MemoMap::new();
739        memo.insert("key".to_string(), 42);
740
741        assert!(memo.contains_key("key"));
742        assert_eq!(memo.get("key"), Some(&42));
743        *memo.get_mut("key").unwrap() = 43;
744        assert_eq!(memo.remove("key"), Some(43));
745    }
746
747    #[test]
748    fn test_replace() {
749        let mut memo = MemoMap::new();
750        memo.insert("foo", "bar");
751        memo.replace("foo", "bar2");
752        assert_eq!(memo.get("foo"), Some(&"bar2"));
753    }
754
755    #[test]
756    fn test_get_mut() {
757        let mut memo = MemoMap::new();
758        memo.insert("foo", "bar");
759        *memo.get_mut("foo").unwrap() = "bar2";
760        assert_eq!(memo.get("foo"), Some(&"bar2"));
761    }
762
763    #[test]
764    fn test_iter_mut() {
765        let mut memo = MemoMap::new();
766        memo.insert("foo", "bar");
767        for item in memo.iter_mut() {
768            *item.1 = "bar2";
769        }
770        assert_eq!(memo.get("foo"), Some(&"bar2"));
771    }
772
773    #[test]
774    fn test_values_mut() {
775        let mut memo = MemoMap::new();
776        memo.insert("foo", "bar");
777        for item in memo.values_mut() {
778            *item = "bar2";
779        }
780        assert_eq!(memo.get("foo"), Some(&"bar2"));
781    }
782}
memo_map/lib.rs

memo_map/
lib.rs
