lru/
lib.rs

1// MIT License
2
3// Copyright (c) 2016 Jerome Froelich
4
5// Permission is hereby granted, free of charge, to any person obtaining a copy
6// of this software and associated documentation files (the "Software"), to deal
7// in the Software without restriction, including without limitation the rights
8// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9// copies of the Software, and to permit persons to whom the Software is
10// furnished to do so, subject to the following conditions:
11
12// The above copyright notice and this permission notice shall be included in all
13// copies or substantial portions of the Software.
14
15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
21// SOFTWARE.
22
23//! An implementation of a LRU cache. The cache supports `get`, `get_mut`, `put`,
24//! and `pop` operations, all of which are O(1). This crate was heavily influenced
25//! by the [LRU Cache implementation in an earlier version of Rust's std::collections crate](https://doc.rust-lang.org/0.12.0/std/collections/lru_cache/struct.LruCache.html).
26//!
27//! ## Example
28//!
29//! ```rust
30//! extern crate lru;
31//!
32//! use lru::LruCache;
33//! use std::num::NonZeroUsize;
34//!
35//! fn main() {
36//!         let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
37//!         cache.put("apple", 3);
38//!         cache.put("banana", 2);
39//!
40//!         assert_eq!(*cache.get(&"apple").unwrap(), 3);
41//!         assert_eq!(*cache.get(&"banana").unwrap(), 2);
42//!         assert!(cache.get(&"pear").is_none());
43//!
44//!         assert_eq!(cache.put("banana", 4), Some(2));
45//!         assert_eq!(cache.put("pear", 5), None);
46//!
47//!         assert_eq!(*cache.get(&"pear").unwrap(), 5);
48//!         assert_eq!(*cache.get(&"banana").unwrap(), 4);
49//!         assert!(cache.get(&"apple").is_none());
50//!
51//!         {
52//!             let v = cache.get_mut(&"banana").unwrap();
53//!             *v = 6;
54//!         }
55//!
56//!         assert_eq!(*cache.get(&"banana").unwrap(), 6);
57//! }
58//! ```
59
60#![no_std]
61
62#[cfg(feature = "hashbrown")]
63extern crate hashbrown;
64
65#[cfg(test)]
66extern crate scoped_threadpool;
67
68use alloc::borrow::Borrow;
69use alloc::boxed::Box;
70use core::fmt;
71use core::hash::{BuildHasher, Hash, Hasher};
72use core::iter::FusedIterator;
73use core::marker::PhantomData;
74use core::mem;
75use core::num::NonZeroUsize;
76use core::ptr::{self, NonNull};
77
78#[cfg(any(test, not(feature = "hashbrown")))]
79extern crate std;
80
81#[cfg(feature = "hashbrown")]
82use hashbrown::HashMap;
83#[cfg(not(feature = "hashbrown"))]
84use std::collections::HashMap;
85
86extern crate alloc;
87
88// Struct used to hold a reference to a key
89struct KeyRef<K> {
90    k: *const K,
91}
92
93impl<K: Hash> Hash for KeyRef<K> {
94    fn hash<H: Hasher>(&self, state: &mut H) {
95        unsafe { (*self.k).hash(state) }
96    }
97}
98
99impl<K: PartialEq> PartialEq for KeyRef<K> {
100    // NB: The unconditional_recursion lint was added in 1.76.0 and can be removed
101    // once the current stable version of Rust is 1.76.0 or higher.
102    #![allow(unknown_lints)]
103    #[allow(clippy::unconditional_recursion)]
104    fn eq(&self, other: &KeyRef<K>) -> bool {
105        unsafe { (*self.k).eq(&*other.k) }
106    }
107}
108
109impl<K: Eq> Eq for KeyRef<K> {}
110
111// This type exists to allow a "blanket" Borrow impl for KeyRef without conflicting with the
112//  stdlib blanket impl
113#[repr(transparent)]
114struct KeyWrapper<K: ?Sized>(K);
115
116impl<K: ?Sized> KeyWrapper<K> {
117    fn from_ref(key: &K) -> &Self {
118        // safety: KeyWrapper is transparent, so casting the ref like this is allowable
119        unsafe { &*(key as *const K as *const KeyWrapper<K>) }
120    }
121}
122
123impl<K: ?Sized + Hash> Hash for KeyWrapper<K> {
124    fn hash<H: Hasher>(&self, state: &mut H) {
125        self.0.hash(state)
126    }
127}
128
129impl<K: ?Sized + PartialEq> PartialEq for KeyWrapper<K> {
130    // NB: The unconditional_recursion lint was added in 1.76.0 and can be removed
131    // once the current stable version of Rust is 1.76.0 or higher.
132    #![allow(unknown_lints)]
133    #[allow(clippy::unconditional_recursion)]
134    fn eq(&self, other: &Self) -> bool {
135        self.0.eq(&other.0)
136    }
137}
138
139impl<K: ?Sized + Eq> Eq for KeyWrapper<K> {}
140
141impl<K, Q> Borrow<KeyWrapper<Q>> for KeyRef<K>
142where
143    K: Borrow<Q>,
144    Q: ?Sized,
145{
146    fn borrow(&self) -> &KeyWrapper<Q> {
147        let key = unsafe { &*self.k }.borrow();
148        KeyWrapper::from_ref(key)
149    }
150}
151
152// Struct used to hold a key value pair. Also contains references to previous and next entries
153// so we can maintain the entries in a linked list ordered by their use.
154struct LruEntry<K, V> {
155    key: mem::MaybeUninit<K>,
156    val: mem::MaybeUninit<V>,
157    prev: *mut LruEntry<K, V>,
158    next: *mut LruEntry<K, V>,
159}
160
161impl<K, V> LruEntry<K, V> {
162    fn new(key: K, val: V) -> Self {
163        LruEntry {
164            key: mem::MaybeUninit::new(key),
165            val: mem::MaybeUninit::new(val),
166            prev: ptr::null_mut(),
167            next: ptr::null_mut(),
168        }
169    }
170
171    fn new_sigil() -> Self {
172        LruEntry {
173            key: mem::MaybeUninit::uninit(),
174            val: mem::MaybeUninit::uninit(),
175            prev: ptr::null_mut(),
176            next: ptr::null_mut(),
177        }
178    }
179}
180
181#[cfg(feature = "hashbrown")]
182pub type DefaultHasher = hashbrown::DefaultHashBuilder;
183#[cfg(not(feature = "hashbrown"))]
184pub type DefaultHasher = std::collections::hash_map::RandomState;
185
186/// An LRU Cache
187pub struct LruCache<K, V, S = DefaultHasher> {
188    map: HashMap<KeyRef<K>, NonNull<LruEntry<K, V>>, S>,
189    cap: NonZeroUsize,
190
191    // head and tail are sigil nodes to facilitate inserting entries
192    head: *mut LruEntry<K, V>,
193    tail: *mut LruEntry<K, V>,
194}
195
196impl<K, V> Clone for LruCache<K, V>
197where
198    K: Hash + PartialEq + Eq + Clone,
199    V: Clone,
200{
201    fn clone(&self) -> Self {
202        let mut new_lru = LruCache::new(self.cap());
203
204        for (key, value) in self.iter().rev() {
205            new_lru.push(key.clone(), value.clone());
206        }
207
208        new_lru
209    }
210}
211
212impl<K: Hash + Eq, V> LruCache<K, V> {
213    /// Creates a new LRU Cache that holds at most `cap` items.
214    ///
215    /// # Example
216    ///
217    /// ```
218    /// use lru::LruCache;
219    /// use std::num::NonZeroUsize;
220    /// let mut cache: LruCache<isize, &str> = LruCache::new(NonZeroUsize::new(10).unwrap());
221    /// ```
222    pub fn new(cap: NonZeroUsize) -> LruCache<K, V> {
223        LruCache::construct(cap, HashMap::with_capacity(cap.get()))
224    }
225
226    /// Creates a new LRU Cache that never automatically evicts items.
227    ///
228    /// # Example
229    ///
230    /// ```
231    /// use lru::LruCache;
232    /// use std::num::NonZeroUsize;
233    /// let mut cache: LruCache<isize, &str> = LruCache::unbounded();
234    /// ```
235    pub fn unbounded() -> LruCache<K, V> {
236        LruCache::construct(NonZeroUsize::MAX, HashMap::default())
237    }
238}
239
240impl<K: Hash + Eq, V, S: BuildHasher> LruCache<K, V, S> {
241    /// Creates a new LRU Cache that holds at most `cap` items and
242    /// uses the provided hash builder to hash keys.
243    ///
244    /// # Example
245    ///
246    /// ```
247    /// use lru::{LruCache, DefaultHasher};
248    /// use std::num::NonZeroUsize;
249    ///
250    /// let s = DefaultHasher::default();
251    /// let mut cache: LruCache<isize, &str> = LruCache::with_hasher(NonZeroUsize::new(10).unwrap(), s);
252    /// ```
253    pub fn with_hasher(cap: NonZeroUsize, hash_builder: S) -> LruCache<K, V, S> {
254        LruCache::construct(
255            cap,
256            HashMap::with_capacity_and_hasher(cap.into(), hash_builder),
257        )
258    }
259
260    /// Creates a new LRU Cache that never automatically evicts items and
261    /// uses the provided hash builder to hash keys.
262    ///
263    /// # Example
264    ///
265    /// ```
266    /// use lru::{LruCache, DefaultHasher};
267    ///
268    /// let s = DefaultHasher::default();
269    /// let mut cache: LruCache<isize, &str> = LruCache::unbounded_with_hasher(s);
270    /// ```
271    pub fn unbounded_with_hasher(hash_builder: S) -> LruCache<K, V, S> {
272        LruCache::construct(NonZeroUsize::MAX, HashMap::with_hasher(hash_builder))
273    }
274
275    /// Creates a new LRU Cache with the given capacity.
276    fn construct(
277        cap: NonZeroUsize,
278        map: HashMap<KeyRef<K>, NonNull<LruEntry<K, V>>, S>,
279    ) -> LruCache<K, V, S> {
280        // NB: The compiler warns that cache does not need to be marked as mutable if we
281        // declare it as such since we only mutate it inside the unsafe block.
282        let cache = LruCache {
283            map,
284            cap,
285            head: Box::into_raw(Box::new(LruEntry::new_sigil())),
286            tail: Box::into_raw(Box::new(LruEntry::new_sigil())),
287        };
288
289        unsafe {
290            (*cache.head).next = cache.tail;
291            (*cache.tail).prev = cache.head;
292        }
293
294        cache
295    }
296
297    /// Puts a key-value pair into cache. If the key already exists in the cache, then it updates
298    /// the key's value and returns the old value. Otherwise, `None` is returned.
299    ///
300    /// # Example
301    ///
302    /// ```
303    /// use lru::LruCache;
304    /// use std::num::NonZeroUsize;
305    /// let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
306    ///
307    /// assert_eq!(None, cache.put(1, "a"));
308    /// assert_eq!(None, cache.put(2, "b"));
309    /// assert_eq!(Some("b"), cache.put(2, "beta"));
310    ///
311    /// assert_eq!(cache.get(&1), Some(&"a"));
312    /// assert_eq!(cache.get(&2), Some(&"beta"));
313    /// ```
314    pub fn put(&mut self, k: K, v: V) -> Option<V> {
315        self.capturing_put(k, v, false).map(|(_, v)| v)
316    }
317
318    /// Pushes a key-value pair into the cache. If an entry with key `k` already exists in
319    /// the cache or another cache entry is removed (due to the lru's capacity),
320    /// then it returns the old entry's key-value pair. Otherwise, returns `None`.
321    ///
322    /// # Example
323    ///
324    /// ```
325    /// use lru::LruCache;
326    /// use std::num::NonZeroUsize;
327    /// let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
328    ///
329    /// assert_eq!(None, cache.push(1, "a"));
330    /// assert_eq!(None, cache.push(2, "b"));
331    ///
332    /// // This push call returns (2, "b") because that was previously 2's entry in the cache.
333    /// assert_eq!(Some((2, "b")), cache.push(2, "beta"));
334    ///
335    /// // This push call returns (1, "a") because the cache is at capacity and 1's entry was the lru entry.
336    /// assert_eq!(Some((1, "a")), cache.push(3, "alpha"));
337    ///
338    /// assert_eq!(cache.get(&1), None);
339    /// assert_eq!(cache.get(&2), Some(&"beta"));
340    /// assert_eq!(cache.get(&3), Some(&"alpha"));
341    /// ```
342    pub fn push(&mut self, k: K, v: V) -> Option<(K, V)> {
343        self.capturing_put(k, v, true)
344    }
345
346    // Used internally by `put` and `push` to add a new entry to the lru.
347    // Takes ownership of and returns entries replaced due to the cache's capacity
348    // when `capture` is true.
349    fn capturing_put(&mut self, k: K, mut v: V, capture: bool) -> Option<(K, V)> {
350        let node_ref = self.map.get_mut(&KeyRef { k: &k });
351
352        match node_ref {
353            Some(node_ref) => {
354                // if the key is already in the cache just update its value and move it to the
355                // front of the list
356                let node_ptr: *mut LruEntry<K, V> = node_ref.as_ptr();
357
358                // gets a reference to the node to perform a swap and drops it right after
359                let node_ref = unsafe { &mut (*(*node_ptr).val.as_mut_ptr()) };
360                mem::swap(&mut v, node_ref);
361                let _ = node_ref;
362
363                self.detach(node_ptr);
364                self.attach(node_ptr);
365                Some((k, v))
366            }
367            None => {
368                let (replaced, node) = self.replace_or_create_node(k, v);
369                let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
370
371                self.attach(node_ptr);
372
373                let keyref = unsafe { (*node_ptr).key.as_ptr() };
374                self.map.insert(KeyRef { k: keyref }, node);
375
376                replaced.filter(|_| capture)
377            }
378        }
379    }
380
381    // Used internally to swap out a node if the cache is full or to create a new node if space
382    // is available. Shared between `put`, `push`, `get_or_insert`, and `get_or_insert_mut`.
383    #[allow(clippy::type_complexity)]
384    fn replace_or_create_node(&mut self, k: K, v: V) -> (Option<(K, V)>, NonNull<LruEntry<K, V>>) {
385        if self.len() == self.cap().get() {
386            // if the cache is full, remove the last entry so we can use it for the new key
387            let old_key = KeyRef {
388                k: unsafe { &(*(*(*self.tail).prev).key.as_ptr()) },
389            };
390            let old_node = self.map.remove(&old_key).unwrap();
391            let node_ptr: *mut LruEntry<K, V> = old_node.as_ptr();
392
393            // read out the node's old key and value and then replace it
394            let replaced = unsafe {
395                (
396                    mem::replace(&mut (*node_ptr).key, mem::MaybeUninit::new(k)).assume_init(),
397                    mem::replace(&mut (*node_ptr).val, mem::MaybeUninit::new(v)).assume_init(),
398                )
399            };
400
401            self.detach(node_ptr);
402
403            (Some(replaced), old_node)
404        } else {
405            // if the cache is not full allocate a new LruEntry
406            // Safety: We allocate, turn into raw, and get NonNull all in one step.
407            (None, unsafe {
408                NonNull::new_unchecked(Box::into_raw(Box::new(LruEntry::new(k, v))))
409            })
410        }
411    }
412
413    /// Returns a reference to the value of the key in the cache or `None` if it is not
414    /// present in the cache. Moves the key to the head of the LRU list if it exists.
415    ///
416    /// # Example
417    ///
418    /// ```
419    /// use lru::LruCache;
420    /// use std::num::NonZeroUsize;
421    /// let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
422    ///
423    /// cache.put(1, "a");
424    /// cache.put(2, "b");
425    /// cache.put(2, "c");
426    /// cache.put(3, "d");
427    ///
428    /// assert_eq!(cache.get(&1), None);
429    /// assert_eq!(cache.get(&2), Some(&"c"));
430    /// assert_eq!(cache.get(&3), Some(&"d"));
431    /// ```
432    pub fn get<'a, Q>(&'a mut self, k: &Q) -> Option<&'a V>
433    where
434        K: Borrow<Q>,
435        Q: Hash + Eq + ?Sized,
436    {
437        if let Some(node) = self.map.get_mut(KeyWrapper::from_ref(k)) {
438            let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
439
440            self.detach(node_ptr);
441            self.attach(node_ptr);
442
443            Some(unsafe { &*(*node_ptr).val.as_ptr() })
444        } else {
445            None
446        }
447    }
448
449    /// Returns a mutable reference to the value of the key in the cache or `None` if it
450    /// is not present in the cache. Moves the key to the head of the LRU list if it exists.
451    ///
452    /// # Example
453    ///
454    /// ```
455    /// use lru::LruCache;
456    /// use std::num::NonZeroUsize;
457    /// let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
458    ///
459    /// cache.put("apple", 8);
460    /// cache.put("banana", 4);
461    /// cache.put("banana", 6);
462    /// cache.put("pear", 2);
463    ///
464    /// assert_eq!(cache.get_mut(&"apple"), None);
465    /// assert_eq!(cache.get_mut(&"banana"), Some(&mut 6));
466    /// assert_eq!(cache.get_mut(&"pear"), Some(&mut 2));
467    /// ```
468    pub fn get_mut<'a, Q>(&'a mut self, k: &Q) -> Option<&'a mut V>
469    where
470        K: Borrow<Q>,
471        Q: Hash + Eq + ?Sized,
472    {
473        if let Some(node) = self.map.get_mut(KeyWrapper::from_ref(k)) {
474            let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
475
476            self.detach(node_ptr);
477            self.attach(node_ptr);
478
479            Some(unsafe { &mut *(*node_ptr).val.as_mut_ptr() })
480        } else {
481            None
482        }
483    }
484
485    /// Returns a key-value references pair of the key in the cache or `None` if it is not
486    /// present in the cache. Moves the key to the head of the LRU list if it exists.
487    ///
488    /// # Example
489    ///
490    /// ```
491    /// use lru::LruCache;
492    /// use std::num::NonZeroUsize;
493    /// let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
494    ///
495    /// cache.put(String::from("1"), "a");
496    /// cache.put(String::from("2"), "b");
497    /// cache.put(String::from("2"), "c");
498    /// cache.put(String::from("3"), "d");
499    ///
500    /// assert_eq!(cache.get_key_value("1"), None);
501    /// assert_eq!(cache.get_key_value("2"), Some((&String::from("2"), &"c")));
502    /// assert_eq!(cache.get_key_value("3"), Some((&String::from("3"), &"d")));
503    /// ```
504    pub fn get_key_value<'a, Q>(&'a mut self, k: &Q) -> Option<(&'a K, &'a V)>
505    where
506        K: Borrow<Q>,
507        Q: Hash + Eq + ?Sized,
508    {
509        if let Some(node) = self.map.get_mut(KeyWrapper::from_ref(k)) {
510            let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
511
512            self.detach(node_ptr);
513            self.attach(node_ptr);
514
515            Some(unsafe { (&*(*node_ptr).key.as_ptr(), &*(*node_ptr).val.as_ptr()) })
516        } else {
517            None
518        }
519    }
520
521    /// Returns a key-value references pair of the key in the cache or `None` if it is not
522    /// present in the cache. The reference to the value of the key is mutable. Moves the key to
523    /// the head of the LRU list if it exists.
524    ///
525    /// # Example
526    ///
527    /// ```
528    /// use lru::LruCache;
529    /// use std::num::NonZeroUsize;
530    /// let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
531    ///
532    /// cache.put(1, "a");
533    /// cache.put(2, "b");
534    /// let (k, v) = cache.get_key_value_mut(&1).unwrap();
535    /// assert_eq!(k, &1);
536    /// assert_eq!(v, &mut "a");
537    /// *v = "aa";
538    /// cache.put(3, "c");
539    /// assert_eq!(cache.get_key_value(&2), None);
540    /// assert_eq!(cache.get_key_value(&1), Some((&1, &"aa")));
541    /// assert_eq!(cache.get_key_value(&3), Some((&3, &"c")));
542    /// ```
543    pub fn get_key_value_mut<'a, Q>(&'a mut self, k: &Q) -> Option<(&'a K, &'a mut V)>
544    where
545        K: Borrow<Q>,
546        Q: Hash + Eq + ?Sized,
547    {
548        if let Some(node) = self.map.get_mut(KeyWrapper::from_ref(k)) {
549            let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
550
551            self.detach(node_ptr);
552            self.attach(node_ptr);
553
554            Some(unsafe {
555                (
556                    &*(*node_ptr).key.as_ptr(),
557                    &mut *(*node_ptr).val.as_mut_ptr(),
558                )
559            })
560        } else {
561            None
562        }
563    }
564
565    /// Returns a reference to the value of the key in the cache if it is
566    /// present in the cache and moves the key to the head of the LRU list.
567    /// If the key does not exist the provided `FnOnce` is used to populate
568    /// the list and a reference is returned.
569    ///
570    /// # Example
571    ///
572    /// ```
573    /// use lru::LruCache;
574    /// use std::num::NonZeroUsize;
575    /// let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
576    ///
577    /// cache.put(1, "a");
578    /// cache.put(2, "b");
579    /// cache.put(2, "c");
580    /// cache.put(3, "d");
581    ///
582    /// assert_eq!(cache.get_or_insert(2, ||"a"), &"c");
583    /// assert_eq!(cache.get_or_insert(3, ||"a"), &"d");
584    /// assert_eq!(cache.get_or_insert(1, ||"a"), &"a");
585    /// assert_eq!(cache.get_or_insert(1, ||"b"), &"a");
586    /// ```
587    pub fn get_or_insert<F>(&mut self, k: K, f: F) -> &V
588    where
589        F: FnOnce() -> V,
590    {
591        if let Some(node) = self.map.get_mut(&KeyRef { k: &k }) {
592            let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
593
594            self.detach(node_ptr);
595            self.attach(node_ptr);
596
597            unsafe { &*(*node_ptr).val.as_ptr() }
598        } else {
599            let v = f();
600            let (_, node) = self.replace_or_create_node(k, v);
601            let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
602
603            self.attach(node_ptr);
604
605            let keyref = unsafe { (*node_ptr).key.as_ptr() };
606            self.map.insert(KeyRef { k: keyref }, node);
607            unsafe { &*(*node_ptr).val.as_ptr() }
608        }
609    }
610
611    /// Returns a reference to the value of the key in the cache if it is
612    /// present in the cache and moves the key to the head of the LRU list.
613    /// If the key does not exist the provided `FnOnce` is used to populate
614    /// the list and a reference is returned. The value referenced by the
615    /// key is only cloned (using `to_owned()`) if it doesn't exist in the
616    /// cache.
617    ///
618    /// # Example
619    ///
620    /// ```
621    /// use lru::LruCache;
622    /// use std::num::NonZeroUsize;
623    /// use std::rc::Rc;
624    ///
625    /// let key1 = Rc::new("1".to_owned());
626    /// let key2 = Rc::new("2".to_owned());
627    /// let mut cache = LruCache::<Rc<String>, String>::new(NonZeroUsize::new(2).unwrap());
628    /// assert_eq!(cache.get_or_insert_ref(&key1, ||"One".to_owned()), "One");
629    /// assert_eq!(cache.get_or_insert_ref(&key2, ||"Two".to_owned()), "Two");
630    /// assert_eq!(cache.get_or_insert_ref(&key2, ||"Not two".to_owned()), "Two");
631    /// assert_eq!(cache.get_or_insert_ref(&key2, ||"Again not two".to_owned()), "Two");
632    /// assert_eq!(Rc::strong_count(&key1), 2);
633    /// assert_eq!(Rc::strong_count(&key2), 2); // key2 was only cloned once even though we
634    ///                                         // queried it 3 times
635    /// ```
636    pub fn get_or_insert_ref<'a, Q, F>(&'a mut self, k: &'_ Q, f: F) -> &'a V
637    where
638        K: Borrow<Q>,
639        Q: Hash + Eq + ?Sized + alloc::borrow::ToOwned<Owned = K>,
640        F: FnOnce() -> V,
641    {
642        if let Some(node) = self.map.get_mut(KeyWrapper::from_ref(k)) {
643            let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
644
645            self.detach(node_ptr);
646            self.attach(node_ptr);
647
648            unsafe { &*(*node_ptr).val.as_ptr() }
649        } else {
650            let v = f();
651            let (_, node) = self.replace_or_create_node(k.to_owned(), v);
652            let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
653
654            self.attach(node_ptr);
655
656            let keyref = unsafe { (*node_ptr).key.as_ptr() };
657            self.map.insert(KeyRef { k: keyref }, node);
658            unsafe { &*(*node_ptr).val.as_ptr() }
659        }
660    }
661
662    /// Returns a reference to the value of the key in the cache if it is
663    /// present in the cache and moves the key to the head of the LRU list.
664    /// If the key does not exist the provided `FnOnce` is used to populate
665    /// the list and a reference is returned. If `FnOnce` returns `Err`,
666    /// returns the `Err`.
667    ///
668    /// # Example
669    ///
670    /// ```
671    /// use lru::LruCache;
672    /// use std::num::NonZeroUsize;
673    /// let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
674    ///
675    /// cache.put(1, "a");
676    /// cache.put(2, "b");
677    /// cache.put(2, "c");
678    /// cache.put(3, "d");
679    ///
680    /// let f = ||->Result<&str, String> {Err("failed".to_owned())};
681    /// let a = ||->Result<&str, String> {Ok("a")};
682    /// let b = ||->Result<&str, String> {Ok("b")};
683    /// assert_eq!(cache.try_get_or_insert(2, a), Ok(&"c"));
684    /// assert_eq!(cache.try_get_or_insert(3, a), Ok(&"d"));
685    /// assert_eq!(cache.try_get_or_insert(4, f), Err("failed".to_owned()));
686    /// assert_eq!(cache.try_get_or_insert(5, b), Ok(&"b"));
687    /// assert_eq!(cache.try_get_or_insert(5, a), Ok(&"b"));
688    /// ```
689    pub fn try_get_or_insert<F, E>(&mut self, k: K, f: F) -> Result<&V, E>
690    where
691        F: FnOnce() -> Result<V, E>,
692    {
693        if let Some(node) = self.map.get_mut(&KeyRef { k: &k }) {
694            let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
695
696            self.detach(node_ptr);
697            self.attach(node_ptr);
698
699            unsafe { Ok(&*(*node_ptr).val.as_ptr()) }
700        } else {
701            let v = f()?;
702            let (_, node) = self.replace_or_create_node(k, v);
703            let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
704
705            self.attach(node_ptr);
706
707            let keyref = unsafe { (*node_ptr).key.as_ptr() };
708            self.map.insert(KeyRef { k: keyref }, node);
709            Ok(unsafe { &*(*node_ptr).val.as_ptr() })
710        }
711    }
712
713    /// Returns a reference to the value of the key in the cache if it is
714    /// present in the cache and moves the key to the head of the LRU list.
715    /// If the key does not exist the provided `FnOnce` is used to populate
716    /// the list and a reference is returned. If `FnOnce` returns `Err`,
717    /// returns the `Err`. The value referenced by the key is only cloned
718    /// (using `to_owned()`) if it doesn't exist in the cache and `FnOnce`
719    /// succeeds.
720    ///
721    /// # Example
722    ///
723    /// ```
724    /// use lru::LruCache;
725    /// use std::num::NonZeroUsize;
726    /// use std::rc::Rc;
727    ///
728    /// let key1 = Rc::new("1".to_owned());
729    /// let key2 = Rc::new("2".to_owned());
730    /// let mut cache = LruCache::<Rc<String>, String>::new(NonZeroUsize::new(2).unwrap());
731    /// let f = ||->Result<String, ()> {Err(())};
732    /// let a = ||->Result<String, ()> {Ok("One".to_owned())};
733    /// let b = ||->Result<String, ()> {Ok("Two".to_owned())};
734    /// assert_eq!(cache.try_get_or_insert_ref(&key1, a), Ok(&"One".to_owned()));
735    /// assert_eq!(cache.try_get_or_insert_ref(&key2, f), Err(()));
736    /// assert_eq!(cache.try_get_or_insert_ref(&key2, b), Ok(&"Two".to_owned()));
737    /// assert_eq!(cache.try_get_or_insert_ref(&key2, a), Ok(&"Two".to_owned()));
738    /// assert_eq!(Rc::strong_count(&key1), 2);
739    /// assert_eq!(Rc::strong_count(&key2), 2); // key2 was only cloned once even though we
740    ///                                         // queried it 3 times
741    /// ```
742    pub fn try_get_or_insert_ref<'a, Q, F, E>(&'a mut self, k: &'_ Q, f: F) -> Result<&'a V, E>
743    where
744        K: Borrow<Q>,
745        Q: Hash + Eq + ?Sized + alloc::borrow::ToOwned<Owned = K>,
746        F: FnOnce() -> Result<V, E>,
747    {
748        if let Some(node) = self.map.get_mut(KeyWrapper::from_ref(k)) {
749            let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
750
751            self.detach(node_ptr);
752            self.attach(node_ptr);
753
754            unsafe { Ok(&*(*node_ptr).val.as_ptr()) }
755        } else {
756            let v = f()?;
757            let (_, node) = self.replace_or_create_node(k.to_owned(), v);
758            let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
759
760            self.attach(node_ptr);
761
762            let keyref = unsafe { (*node_ptr).key.as_ptr() };
763            self.map.insert(KeyRef { k: keyref }, node);
764            Ok(unsafe { &*(*node_ptr).val.as_ptr() })
765        }
766    }
767
768    /// Returns a mutable reference to the value of the key in the cache if it is
769    /// present in the cache and moves the key to the head of the LRU list.
770    /// If the key does not exist the provided `FnOnce` is used to populate
771    /// the list and a mutable reference is returned.
772    ///
773    /// # Example
774    ///
775    /// ```
776    /// use lru::LruCache;
777    /// use std::num::NonZeroUsize;
778    /// let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
779    ///
780    /// cache.put(1, "a");
781    /// cache.put(2, "b");
782    ///
783    /// let v = cache.get_or_insert_mut(2, ||"c");
784    /// assert_eq!(v, &"b");
785    /// *v = "d";
786    /// assert_eq!(cache.get_or_insert_mut(2, ||"e"), &mut "d");
787    /// assert_eq!(cache.get_or_insert_mut(3, ||"f"), &mut "f");
788    /// assert_eq!(cache.get_or_insert_mut(3, ||"e"), &mut "f");
789    /// ```
790    pub fn get_or_insert_mut<F>(&mut self, k: K, f: F) -> &mut V
791    where
792        F: FnOnce() -> V,
793    {
794        if let Some(node) = self.map.get_mut(&KeyRef { k: &k }) {
795            let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
796
797            self.detach(node_ptr);
798            self.attach(node_ptr);
799
800            unsafe { &mut *(*node_ptr).val.as_mut_ptr() }
801        } else {
802            let v = f();
803            let (_, node) = self.replace_or_create_node(k, v);
804            let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
805
806            self.attach(node_ptr);
807
808            let keyref = unsafe { (*node_ptr).key.as_ptr() };
809            self.map.insert(KeyRef { k: keyref }, node);
810            unsafe { &mut *(*node_ptr).val.as_mut_ptr() }
811        }
812    }
813
814    /// Returns a mutable reference to the value of the key in the cache if it is
815    /// present in the cache and moves the key to the head of the LRU list.
816    /// If the key does not exist the provided `FnOnce` is used to populate
817    /// the list and a mutable reference is returned. The value referenced by the
818    /// key is only cloned (using `to_owned()`) if it doesn't exist in the cache.
819    ///
820    /// # Example
821    ///
822    /// ```
823    /// use lru::LruCache;
824    /// use std::num::NonZeroUsize;
825    /// use std::rc::Rc;
826    ///
827    /// let key1 = Rc::new("1".to_owned());
828    /// let key2 = Rc::new("2".to_owned());
829    /// let mut cache = LruCache::<Rc<String>, &'static str>::new(NonZeroUsize::new(2).unwrap());
830    /// cache.get_or_insert_mut_ref(&key1, ||"One");
831    /// let v = cache.get_or_insert_mut_ref(&key2, ||"Two");
832    /// *v = "New two";
833    /// assert_eq!(cache.get_or_insert_mut_ref(&key2, ||"Two"), &mut "New two");
834    /// assert_eq!(Rc::strong_count(&key1), 2);
835    /// assert_eq!(Rc::strong_count(&key2), 2); // key2 was only cloned once even though we
836    ///                                         // queried it 2 times
837    /// ```
838    pub fn get_or_insert_mut_ref<'a, Q, F>(&mut self, k: &'_ Q, f: F) -> &'a mut V
839    where
840        K: Borrow<Q>,
841        Q: Hash + Eq + ?Sized + alloc::borrow::ToOwned<Owned = K>,
842        F: FnOnce() -> V,
843    {
844        if let Some(node) = self.map.get_mut(KeyWrapper::from_ref(k)) {
845            let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
846
847            self.detach(node_ptr);
848            self.attach(node_ptr);
849
850            unsafe { &mut *(*node_ptr).val.as_mut_ptr() }
851        } else {
852            let v = f();
853            let (_, node) = self.replace_or_create_node(k.to_owned(), v);
854            let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
855
856            self.attach(node_ptr);
857
858            let keyref = unsafe { (*node_ptr).key.as_ptr() };
859            self.map.insert(KeyRef { k: keyref }, node);
860            unsafe { &mut *(*node_ptr).val.as_mut_ptr() }
861        }
862    }
863
864    /// Returns a mutable reference to the value of the key in the cache if it is
865    /// present in the cache and moves the key to the head of the LRU list.
866    /// If the key does not exist the provided `FnOnce` is used to populate
867    /// the list and a mutable reference is returned. If `FnOnce` returns `Err`,
868    /// returns the `Err`.
869    ///
870    /// # Example
871    ///
872    /// ```
873    /// use lru::LruCache;
874    /// use std::num::NonZeroUsize;
875    /// let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
876    ///
877    /// cache.put(1, "a");
878    /// cache.put(2, "b");
879    /// cache.put(2, "c");
880    ///
881    /// let f = ||->Result<&str, String> {Err("failed".to_owned())};
882    /// let a = ||->Result<&str, String> {Ok("a")};
883    /// let b = ||->Result<&str, String> {Ok("b")};
884    /// if let Ok(v) = cache.try_get_or_insert_mut(2, a) {
885    ///     *v = "d";
886    /// }
887    /// assert_eq!(cache.try_get_or_insert_mut(2, a), Ok(&mut "d"));
888    /// assert_eq!(cache.try_get_or_insert_mut(3, f), Err("failed".to_owned()));
889    /// assert_eq!(cache.try_get_or_insert_mut(4, b), Ok(&mut "b"));
890    /// assert_eq!(cache.try_get_or_insert_mut(4, a), Ok(&mut "b"));
891    /// ```
892    pub fn try_get_or_insert_mut<F, E>(&mut self, k: K, f: F) -> Result<&mut V, E>
893    where
894        F: FnOnce() -> Result<V, E>,
895    {
896        if let Some(node) = self.map.get_mut(&KeyRef { k: &k }) {
897            let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
898
899            self.detach(node_ptr);
900            self.attach(node_ptr);
901
902            unsafe { Ok(&mut *(*node_ptr).val.as_mut_ptr()) }
903        } else {
904            let v = f()?;
905            let (_, node) = self.replace_or_create_node(k, v);
906            let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
907
908            self.attach(node_ptr);
909
910            let keyref = unsafe { (*node_ptr).key.as_ptr() };
911            self.map.insert(KeyRef { k: keyref }, node);
912            unsafe { Ok(&mut *(*node_ptr).val.as_mut_ptr()) }
913        }
914    }
915
916    /// Returns a mutable reference to the value of the key in the cache if it is
917    /// present in the cache and moves the key to the head of the LRU list.
918    /// If the key does not exist the provided `FnOnce` is used to populate
919    /// the list and a mutable reference is returned. If `FnOnce` returns `Err`,
920    /// returns the `Err`. The value referenced by the key is only cloned
921    /// (using `to_owned()`) if it doesn't exist in the cache and `FnOnce`
922    /// succeeds.
923    ///
924    /// # Example
925    ///
926    /// ```
927    /// use lru::LruCache;
928    /// use std::num::NonZeroUsize;
929    /// use std::rc::Rc;
930    ///
931    /// let key1 = Rc::new("1".to_owned());
932    /// let key2 = Rc::new("2".to_owned());
933    /// let mut cache = LruCache::<Rc<String>, String>::new(NonZeroUsize::new(2).unwrap());
934    /// let f = ||->Result<String, ()> {Err(())};
935    /// let a = ||->Result<String, ()> {Ok("One".to_owned())};
936    /// let b = ||->Result<String, ()> {Ok("Two".to_owned())};
937    /// assert_eq!(cache.try_get_or_insert_mut_ref(&key1, a), Ok(&mut "One".to_owned()));
938    /// assert_eq!(cache.try_get_or_insert_mut_ref(&key2, f), Err(()));
939    /// if let Ok(v) = cache.try_get_or_insert_mut_ref(&key2, b) {
940    ///     *v = "New two".to_owned();
941    /// }
942    /// assert_eq!(cache.try_get_or_insert_mut_ref(&key2, a), Ok(&mut "New two".to_owned()));
943    /// assert_eq!(Rc::strong_count(&key1), 2);
944    /// assert_eq!(Rc::strong_count(&key2), 2); // key2 was only cloned once even though we
945    ///                                         // queried it 3 times
946    /// ```
947    pub fn try_get_or_insert_mut_ref<'a, Q, F, E>(
948        &'a mut self,
949        k: &'_ Q,
950        f: F,
951    ) -> Result<&'a mut V, E>
952    where
953        K: Borrow<Q>,
954        Q: Hash + Eq + ?Sized + alloc::borrow::ToOwned<Owned = K>,
955        F: FnOnce() -> Result<V, E>,
956    {
957        if let Some(node) = self.map.get_mut(KeyWrapper::from_ref(k)) {
958            let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
959
960            self.detach(node_ptr);
961            self.attach(node_ptr);
962
963            unsafe { Ok(&mut *(*node_ptr).val.as_mut_ptr()) }
964        } else {
965            let v = f()?;
966            let (_, node) = self.replace_or_create_node(k.to_owned(), v);
967            let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
968
969            self.attach(node_ptr);
970
971            let keyref = unsafe { (*node_ptr).key.as_ptr() };
972            self.map.insert(KeyRef { k: keyref }, node);
973            unsafe { Ok(&mut *(*node_ptr).val.as_mut_ptr()) }
974        }
975    }
976
977    /// Returns a reference to the value corresponding to the key in the cache or `None` if it is
978    /// not present in the cache. Unlike `get`, `peek` does not update the LRU list so the key's
979    /// position will be unchanged.
980    ///
981    /// # Example
982    ///
983    /// ```
984    /// use lru::LruCache;
985    /// use std::num::NonZeroUsize;
986    /// let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
987    ///
988    /// cache.put(1, "a");
989    /// cache.put(2, "b");
990    ///
991    /// assert_eq!(cache.peek(&1), Some(&"a"));
992    /// assert_eq!(cache.peek(&2), Some(&"b"));
993    /// ```
994    pub fn peek<'a, Q>(&'a self, k: &Q) -> Option<&'a V>
995    where
996        K: Borrow<Q>,
997        Q: Hash + Eq + ?Sized,
998    {
999        self.map
1000            .get(KeyWrapper::from_ref(k))
1001            .map(|node| unsafe { &*node.as_ref().val.as_ptr() })
1002    }
1003
1004    /// Returns a mutable reference to the value corresponding to the key in the cache or `None`
1005    /// if it is not present in the cache. Unlike `get_mut`, `peek_mut` does not update the LRU
1006    /// list so the key's position will be unchanged.
1007    ///
1008    /// # Example
1009    ///
1010    /// ```
1011    /// use lru::LruCache;
1012    /// use std::num::NonZeroUsize;
1013    /// let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
1014    ///
1015    /// cache.put(1, "a");
1016    /// cache.put(2, "b");
1017    ///
1018    /// assert_eq!(cache.peek_mut(&1), Some(&mut "a"));
1019    /// assert_eq!(cache.peek_mut(&2), Some(&mut "b"));
1020    /// ```
1021    pub fn peek_mut<'a, Q>(&'a mut self, k: &Q) -> Option<&'a mut V>
1022    where
1023        K: Borrow<Q>,
1024        Q: Hash + Eq + ?Sized,
1025    {
1026        match self.map.get_mut(KeyWrapper::from_ref(k)) {
1027            None => None,
1028            Some(node) => Some(unsafe { &mut *(*node.as_ptr()).val.as_mut_ptr() }),
1029        }
1030    }
1031
1032    /// Returns the value corresponding to the least recently used item or `None` if the
1033    /// cache is empty. Like `peek`, `peek_lru` does not update the LRU list so the item's
1034    /// position will be unchanged.
1035    ///
1036    /// # Example
1037    ///
1038    /// ```
1039    /// use lru::LruCache;
1040    /// use std::num::NonZeroUsize;
1041    /// let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
1042    ///
1043    /// cache.put(1, "a");
1044    /// cache.put(2, "b");
1045    ///
1046    /// assert_eq!(cache.peek_lru(), Some((&1, &"a")));
1047    /// ```
1048    pub fn peek_lru(&self) -> Option<(&K, &V)> {
1049        if self.is_empty() {
1050            return None;
1051        }
1052
1053        let (key, val);
1054        unsafe {
1055            let node = (*self.tail).prev;
1056            key = &(*(*node).key.as_ptr()) as &K;
1057            val = &(*(*node).val.as_ptr()) as &V;
1058        }
1059
1060        Some((key, val))
1061    }
1062
1063    /// Returns the value corresponding to the most recently used item or `None` if the
1064    /// cache is empty. Like `peek`, `peek_mru` does not update the LRU list so the item's
1065    /// position will be unchanged.
1066    ///
1067    /// # Example
1068    ///
1069    /// ```
1070    /// use lru::LruCache;
1071    /// use std::num::NonZeroUsize;
1072    /// let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
1073    ///
1074    /// cache.put(1, "a");
1075    /// cache.put(2, "b");
1076    ///
1077    /// assert_eq!(cache.peek_mru(), Some((&2, &"b")));
1078    /// ```
1079    pub fn peek_mru(&self) -> Option<(&K, &V)> {
1080        if self.is_empty() {
1081            return None;
1082        }
1083
1084        let (key, val);
1085        unsafe {
1086            let node: *mut LruEntry<K, V> = (*self.head).next;
1087            key = &(*(*node).key.as_ptr()) as &K;
1088            val = &(*(*node).val.as_ptr()) as &V;
1089        }
1090
1091        Some((key, val))
1092    }
1093
1094    /// Returns a bool indicating whether the given key is in the cache. Does not update the
1095    /// LRU list.
1096    ///
1097    /// # Example
1098    ///
1099    /// ```
1100    /// use lru::LruCache;
1101    /// use std::num::NonZeroUsize;
1102    /// let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
1103    ///
1104    /// cache.put(1, "a");
1105    /// cache.put(2, "b");
1106    /// cache.put(3, "c");
1107    ///
1108    /// assert!(!cache.contains(&1));
1109    /// assert!(cache.contains(&2));
1110    /// assert!(cache.contains(&3));
1111    /// ```
1112    pub fn contains<Q>(&self, k: &Q) -> bool
1113    where
1114        K: Borrow<Q>,
1115        Q: Hash + Eq + ?Sized,
1116    {
1117        self.map.contains_key(KeyWrapper::from_ref(k))
1118    }
1119
1120    /// Removes and returns the value corresponding to the key from the cache or
1121    /// `None` if it does not exist.
1122    ///
1123    /// # Example
1124    ///
1125    /// ```
1126    /// use lru::LruCache;
1127    /// use std::num::NonZeroUsize;
1128    /// let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
1129    ///
1130    /// cache.put(2, "a");
1131    ///
1132    /// assert_eq!(cache.pop(&1), None);
1133    /// assert_eq!(cache.pop(&2), Some("a"));
1134    /// assert_eq!(cache.pop(&2), None);
1135    /// assert_eq!(cache.len(), 0);
1136    /// ```
1137    pub fn pop<Q>(&mut self, k: &Q) -> Option<V>
1138    where
1139        K: Borrow<Q>,
1140        Q: Hash + Eq + ?Sized,
1141    {
1142        match self.map.remove(KeyWrapper::from_ref(k)) {
1143            None => None,
1144            Some(old_node) => {
1145                let mut old_node = unsafe {
1146                    let mut old_node = *Box::from_raw(old_node.as_ptr());
1147                    ptr::drop_in_place(old_node.key.as_mut_ptr());
1148
1149                    old_node
1150                };
1151
1152                self.detach(&mut old_node);
1153
1154                let LruEntry { key: _, val, .. } = old_node;
1155                unsafe { Some(val.assume_init()) }
1156            }
1157        }
1158    }
1159
1160    /// Removes and returns the key and the value corresponding to the key from the cache or
1161    /// `None` if it does not exist.
1162    ///
1163    /// # Example
1164    ///
1165    /// ```
1166    /// use lru::LruCache;
1167    /// use std::num::NonZeroUsize;
1168    /// let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
1169    ///
1170    /// cache.put(1, "a");
1171    /// cache.put(2, "a");
1172    ///
1173    /// assert_eq!(cache.pop(&1), Some("a"));
1174    /// assert_eq!(cache.pop_entry(&2), Some((2, "a")));
1175    /// assert_eq!(cache.pop(&1), None);
1176    /// assert_eq!(cache.pop_entry(&2), None);
1177    /// assert_eq!(cache.len(), 0);
1178    /// ```
1179    pub fn pop_entry<Q>(&mut self, k: &Q) -> Option<(K, V)>
1180    where
1181        K: Borrow<Q>,
1182        Q: Hash + Eq + ?Sized,
1183    {
1184        match self.map.remove(KeyWrapper::from_ref(k)) {
1185            None => None,
1186            Some(old_node) => {
1187                let mut old_node = unsafe { *Box::from_raw(old_node.as_ptr()) };
1188
1189                self.detach(&mut old_node);
1190
1191                let LruEntry { key, val, .. } = old_node;
1192                unsafe { Some((key.assume_init(), val.assume_init())) }
1193            }
1194        }
1195    }
1196
1197    /// Removes and returns the key and value corresponding to the least recently
1198    /// used item or `None` if the cache is empty.
1199    ///
1200    /// # Example
1201    ///
1202    /// ```
1203    /// use lru::LruCache;
1204    /// use std::num::NonZeroUsize;
1205    /// let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
1206    ///
1207    /// cache.put(2, "a");
1208    /// cache.put(3, "b");
1209    /// cache.put(4, "c");
1210    /// cache.get(&3);
1211    ///
1212    /// assert_eq!(cache.pop_lru(), Some((4, "c")));
1213    /// assert_eq!(cache.pop_lru(), Some((3, "b")));
1214    /// assert_eq!(cache.pop_lru(), None);
1215    /// assert_eq!(cache.len(), 0);
1216    /// ```
1217    pub fn pop_lru(&mut self) -> Option<(K, V)> {
1218        let node = self.remove_last()?;
1219        // N.B.: Can't destructure directly because of https://github.com/rust-lang/rust/issues/28536
1220        let node = *node;
1221        let LruEntry { key, val, .. } = node;
1222        unsafe { Some((key.assume_init(), val.assume_init())) }
1223    }
1224
1225    /// Removes and returns the key and value corresponding to the most recently
1226    /// used item or `None` if the cache is empty.
1227    ///
1228    /// # Example
1229    ///
1230    /// ```
1231    /// use lru::LruCache;
1232    /// use std::num::NonZeroUsize;
1233    /// let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
1234    ///
1235    /// cache.put(2, "a");
1236    /// cache.put(3, "b");
1237    /// cache.put(4, "c");
1238    /// cache.get(&3);
1239    ///
1240    /// assert_eq!(cache.pop_mru(), Some((3, "b")));
1241    /// assert_eq!(cache.pop_mru(), Some((4, "c")));
1242    /// assert_eq!(cache.pop_mru(), None);
1243    /// assert_eq!(cache.len(), 0);
1244    /// ```
1245    pub fn pop_mru(&mut self) -> Option<(K, V)> {
1246        let node = self.remove_first()?;
1247        // N.B.: Can't destructure directly because of https://github.com/rust-lang/rust/issues/28536
1248        let node = *node;
1249        let LruEntry { key, val, .. } = node;
1250        unsafe { Some((key.assume_init(), val.assume_init())) }
1251    }
1252
1253    /// Marks the key as the most recently used one.
1254    ///
1255    /// # Example
1256    ///
1257    /// ```
1258    /// use lru::LruCache;
1259    /// use std::num::NonZeroUsize;
1260    /// let mut cache = LruCache::new(NonZeroUsize::new(3).unwrap());
1261    ///
1262    /// cache.put(1, "a");
1263    /// cache.put(2, "b");
1264    /// cache.put(3, "c");
1265    /// cache.get(&1);
1266    /// cache.get(&2);
1267    ///
1268    /// // If we do `pop_lru` now, we would pop 3.
1269    /// // assert_eq!(cache.pop_lru(), Some((3, "c")));
1270    ///
1271    /// // By promoting 3, we make sure it isn't popped.
1272    /// cache.promote(&3);
1273    /// assert_eq!(cache.pop_lru(), Some((1, "a")));
1274    /// ```
1275    pub fn promote<Q>(&mut self, k: &Q)
1276    where
1277        K: Borrow<Q>,
1278        Q: Hash + Eq + ?Sized,
1279    {
1280        if let Some(node) = self.map.get_mut(KeyWrapper::from_ref(k)) {
1281            let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
1282            self.detach(node_ptr);
1283            self.attach(node_ptr);
1284        }
1285    }
1286
1287    /// Marks the key as the least recently used one.
1288    ///
1289    /// # Example
1290    ///
1291    /// ```
1292    /// use lru::LruCache;
1293    /// use std::num::NonZeroUsize;
1294    /// let mut cache = LruCache::new(NonZeroUsize::new(3).unwrap());
1295    ///
1296    /// cache.put(1, "a");
1297    /// cache.put(2, "b");
1298    /// cache.put(3, "c");
1299    /// cache.get(&1);
1300    /// cache.get(&2);
1301    ///
1302    /// // If we do `pop_lru` now, we would pop 3.
1303    /// // assert_eq!(cache.pop_lru(), Some((3, "c")));
1304    ///
1305    /// // By demoting 1 and 2, we make sure those are popped first.
1306    /// cache.demote(&2);
1307    /// cache.demote(&1);
1308    /// assert_eq!(cache.pop_lru(), Some((1, "a")));
1309    /// assert_eq!(cache.pop_lru(), Some((2, "b")));
1310    /// ```
1311    pub fn demote<Q>(&mut self, k: &Q)
1312    where
1313        K: Borrow<Q>,
1314        Q: Hash + Eq + ?Sized,
1315    {
1316        if let Some(node) = self.map.get_mut(KeyWrapper::from_ref(k)) {
1317            let node_ptr: *mut LruEntry<K, V> = node.as_ptr();
1318            self.detach(node_ptr);
1319            self.attach_last(node_ptr);
1320        }
1321    }
1322
1323    /// Returns the number of key-value pairs that are currently in the the cache.
1324    ///
1325    /// # Example
1326    ///
1327    /// ```
1328    /// use lru::LruCache;
1329    /// use std::num::NonZeroUsize;
1330    /// let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
1331    /// assert_eq!(cache.len(), 0);
1332    ///
1333    /// cache.put(1, "a");
1334    /// assert_eq!(cache.len(), 1);
1335    ///
1336    /// cache.put(2, "b");
1337    /// assert_eq!(cache.len(), 2);
1338    ///
1339    /// cache.put(3, "c");
1340    /// assert_eq!(cache.len(), 2);
1341    /// ```
1342    pub fn len(&self) -> usize {
1343        self.map.len()
1344    }
1345
1346    /// Returns a bool indicating whether the cache is empty or not.
1347    ///
1348    /// # Example
1349    ///
1350    /// ```
1351    /// use lru::LruCache;
1352    /// use std::num::NonZeroUsize;
1353    /// let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
1354    /// assert!(cache.is_empty());
1355    ///
1356    /// cache.put(1, "a");
1357    /// assert!(!cache.is_empty());
1358    /// ```
1359    pub fn is_empty(&self) -> bool {
1360        self.map.len() == 0
1361    }
1362
1363    /// Returns the maximum number of key-value pairs the cache can hold.
1364    ///
1365    /// # Example
1366    ///
1367    /// ```
1368    /// use lru::LruCache;
1369    /// use std::num::NonZeroUsize;
1370    /// let mut cache: LruCache<isize, &str> = LruCache::new(NonZeroUsize::new(2).unwrap());
1371    /// assert_eq!(cache.cap().get(), 2);
1372    /// ```
1373    pub fn cap(&self) -> NonZeroUsize {
1374        self.cap
1375    }
1376
1377    /// Resizes the cache. If the new capacity is smaller than the size of the current
1378    /// cache any entries past the new capacity are discarded.
1379    ///
1380    /// # Example
1381    ///
1382    /// ```
1383    /// use lru::LruCache;
1384    /// use std::num::NonZeroUsize;
1385    /// let mut cache: LruCache<isize, &str> = LruCache::new(NonZeroUsize::new(2).unwrap());
1386    ///
1387    /// cache.put(1, "a");
1388    /// cache.put(2, "b");
1389    /// cache.resize(NonZeroUsize::new(4).unwrap());
1390    /// cache.put(3, "c");
1391    /// cache.put(4, "d");
1392    ///
1393    /// assert_eq!(cache.len(), 4);
1394    /// assert_eq!(cache.get(&1), Some(&"a"));
1395    /// assert_eq!(cache.get(&2), Some(&"b"));
1396    /// assert_eq!(cache.get(&3), Some(&"c"));
1397    /// assert_eq!(cache.get(&4), Some(&"d"));
1398    /// ```
1399    pub fn resize(&mut self, cap: NonZeroUsize) {
1400        // return early if capacity doesn't change
1401        if cap == self.cap {
1402            return;
1403        }
1404
1405        while self.map.len() > cap.get() {
1406            self.pop_lru();
1407        }
1408        self.map.shrink_to_fit();
1409
1410        self.cap = cap;
1411    }
1412
1413    /// Clears the contents of the cache.
1414    ///
1415    /// # Example
1416    ///
1417    /// ```
1418    /// use lru::LruCache;
1419    /// use std::num::NonZeroUsize;
1420    /// let mut cache: LruCache<isize, &str> = LruCache::new(NonZeroUsize::new(2).unwrap());
1421    /// assert_eq!(cache.len(), 0);
1422    ///
1423    /// cache.put(1, "a");
1424    /// assert_eq!(cache.len(), 1);
1425    ///
1426    /// cache.put(2, "b");
1427    /// assert_eq!(cache.len(), 2);
1428    ///
1429    /// cache.clear();
1430    /// assert_eq!(cache.len(), 0);
1431    /// ```
1432    pub fn clear(&mut self) {
1433        while self.pop_lru().is_some() {}
1434    }
1435
1436    /// An iterator visiting all entries in most-recently used order. The iterator element type is
1437    /// `(&K, &V)`.
1438    ///
1439    /// # Examples
1440    ///
1441    /// ```
1442    /// use lru::LruCache;
1443    /// use std::num::NonZeroUsize;
1444    ///
1445    /// let mut cache = LruCache::new(NonZeroUsize::new(3).unwrap());
1446    /// cache.put("a", 1);
1447    /// cache.put("b", 2);
1448    /// cache.put("c", 3);
1449    ///
1450    /// for (key, val) in cache.iter() {
1451    ///     println!("key: {} val: {}", key, val);
1452    /// }
1453    /// ```
1454    pub fn iter(&self) -> Iter<'_, K, V> {
1455        Iter {
1456            len: self.len(),
1457            ptr: unsafe { (*self.head).next },
1458            end: unsafe { (*self.tail).prev },
1459            phantom: PhantomData,
1460        }
1461    }
1462
1463    /// An iterator visiting all entries in most-recently-used order, giving a mutable reference on
1464    /// V.  The iterator element type is `(&K, &mut V)`.
1465    ///
1466    /// # Examples
1467    ///
1468    /// ```
1469    /// use lru::LruCache;
1470    /// use std::num::NonZeroUsize;
1471    ///
1472    /// struct HddBlock {
1473    ///     dirty: bool,
1474    ///     data: [u8; 512]
1475    /// }
1476    ///
1477    /// let mut cache = LruCache::new(NonZeroUsize::new(3).unwrap());
1478    /// cache.put(0, HddBlock { dirty: false, data: [0x00; 512]});
1479    /// cache.put(1, HddBlock { dirty: true,  data: [0x55; 512]});
1480    /// cache.put(2, HddBlock { dirty: true,  data: [0x77; 512]});
1481    ///
1482    /// // write dirty blocks to disk.
1483    /// for (block_id, block) in cache.iter_mut() {
1484    ///     if block.dirty {
1485    ///         // write block to disk
1486    ///         block.dirty = false
1487    ///     }
1488    /// }
1489    /// ```
1490    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
1491        IterMut {
1492            len: self.len(),
1493            ptr: unsafe { (*self.head).next },
1494            end: unsafe { (*self.tail).prev },
1495            phantom: PhantomData,
1496        }
1497    }
1498
1499    fn remove_first(&mut self) -> Option<Box<LruEntry<K, V>>> {
1500        let next;
1501        unsafe { next = (*self.head).next }
1502        if !core::ptr::eq(next, self.tail) {
1503            let old_key = KeyRef {
1504                k: unsafe { &(*(*(*self.head).next).key.as_ptr()) },
1505            };
1506            let old_node = self.map.remove(&old_key).unwrap();
1507            let node_ptr: *mut LruEntry<K, V> = old_node.as_ptr();
1508            self.detach(node_ptr);
1509            unsafe { Some(Box::from_raw(node_ptr)) }
1510        } else {
1511            None
1512        }
1513    }
1514
1515    fn remove_last(&mut self) -> Option<Box<LruEntry<K, V>>> {
1516        let prev;
1517        unsafe { prev = (*self.tail).prev }
1518        if !core::ptr::eq(prev, self.head) {
1519            let old_key = KeyRef {
1520                k: unsafe { &(*(*(*self.tail).prev).key.as_ptr()) },
1521            };
1522            let old_node = self.map.remove(&old_key).unwrap();
1523            let node_ptr: *mut LruEntry<K, V> = old_node.as_ptr();
1524            self.detach(node_ptr);
1525            unsafe { Some(Box::from_raw(node_ptr)) }
1526        } else {
1527            None
1528        }
1529    }
1530
1531    fn detach(&mut self, node: *mut LruEntry<K, V>) {
1532        unsafe {
1533            (*(*node).prev).next = (*node).next;
1534            (*(*node).next).prev = (*node).prev;
1535        }
1536    }
1537
1538    // Attaches `node` after the sigil `self.head` node.
1539    fn attach(&mut self, node: *mut LruEntry<K, V>) {
1540        unsafe {
1541            (*node).next = (*self.head).next;
1542            (*node).prev = self.head;
1543            (*self.head).next = node;
1544            (*(*node).next).prev = node;
1545        }
1546    }
1547
1548    // Attaches `node` before the sigil `self.tail` node.
1549    fn attach_last(&mut self, node: *mut LruEntry<K, V>) {
1550        unsafe {
1551            (*node).next = self.tail;
1552            (*node).prev = (*self.tail).prev;
1553            (*self.tail).prev = node;
1554            (*(*node).prev).next = node;
1555        }
1556    }
1557}
1558
1559impl<K, V, S> Drop for LruCache<K, V, S> {
1560    fn drop(&mut self) {
1561        self.map.drain().for_each(|(_, node)| unsafe {
1562            let mut node = *Box::from_raw(node.as_ptr());
1563            ptr::drop_in_place((node).key.as_mut_ptr());
1564            ptr::drop_in_place((node).val.as_mut_ptr());
1565        });
1566        // We rebox the head/tail, and because these are maybe-uninit
1567        // they do not have the absent k/v dropped.
1568
1569        let _head = unsafe { *Box::from_raw(self.head) };
1570        let _tail = unsafe { *Box::from_raw(self.tail) };
1571    }
1572}
1573
1574impl<'a, K: Hash + Eq, V, S: BuildHasher> IntoIterator for &'a LruCache<K, V, S> {
1575    type Item = (&'a K, &'a V);
1576    type IntoIter = Iter<'a, K, V>;
1577
1578    fn into_iter(self) -> Iter<'a, K, V> {
1579        self.iter()
1580    }
1581}
1582
1583impl<'a, K: Hash + Eq, V, S: BuildHasher> IntoIterator for &'a mut LruCache<K, V, S> {
1584    type Item = (&'a K, &'a mut V);
1585    type IntoIter = IterMut<'a, K, V>;
1586
1587    fn into_iter(self) -> IterMut<'a, K, V> {
1588        self.iter_mut()
1589    }
1590}
1591
1592// The compiler does not automatically derive Send and Sync for LruCache because it contains
1593// raw pointers. The raw pointers are safely encapsulated by LruCache though so we can
1594// implement Send and Sync for it below.
1595unsafe impl<K: Send, V: Send, S: Send> Send for LruCache<K, V, S> {}
1596unsafe impl<K: Sync, V: Sync, S: Sync> Sync for LruCache<K, V, S> {}
1597
1598impl<K: Hash + Eq, V, S: BuildHasher> fmt::Debug for LruCache<K, V, S> {
1599    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1600        f.debug_struct("LruCache")
1601            .field("len", &self.len())
1602            .field("cap", &self.cap())
1603            .finish()
1604    }
1605}
1606
1607/// An iterator over the entries of a `LruCache`.
1608///
1609/// This `struct` is created by the [`iter`] method on [`LruCache`][`LruCache`]. See its
1610/// documentation for more.
1611///
1612/// [`iter`]: struct.LruCache.html#method.iter
1613/// [`LruCache`]: struct.LruCache.html
1614pub struct Iter<'a, K: 'a, V: 'a> {
1615    len: usize,
1616
1617    ptr: *const LruEntry<K, V>,
1618    end: *const LruEntry<K, V>,
1619
1620    phantom: PhantomData<&'a K>,
1621}
1622
1623impl<'a, K, V> Iterator for Iter<'a, K, V> {
1624    type Item = (&'a K, &'a V);
1625
1626    fn next(&mut self) -> Option<(&'a K, &'a V)> {
1627        if self.len == 0 {
1628            return None;
1629        }
1630
1631        let key = unsafe { &(*(*self.ptr).key.as_ptr()) as &K };
1632        let val = unsafe { &(*(*self.ptr).val.as_ptr()) as &V };
1633
1634        self.len -= 1;
1635        self.ptr = unsafe { (*self.ptr).next };
1636
1637        Some((key, val))
1638    }
1639
1640    fn size_hint(&self) -> (usize, Option<usize>) {
1641        (self.len, Some(self.len))
1642    }
1643
1644    fn count(self) -> usize {
1645        self.len
1646    }
1647}
1648
1649impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
1650    fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
1651        if self.len == 0 {
1652            return None;
1653        }
1654
1655        let key = unsafe { &(*(*self.end).key.as_ptr()) as &K };
1656        let val = unsafe { &(*(*self.end).val.as_ptr()) as &V };
1657
1658        self.len -= 1;
1659        self.end = unsafe { (*self.end).prev };
1660
1661        Some((key, val))
1662    }
1663}
1664
1665impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {}
1666impl<'a, K, V> FusedIterator for Iter<'a, K, V> {}
1667
1668impl<'a, K, V> Clone for Iter<'a, K, V> {
1669    fn clone(&self) -> Iter<'a, K, V> {
1670        Iter {
1671            len: self.len,
1672            ptr: self.ptr,
1673            end: self.end,
1674            phantom: PhantomData,
1675        }
1676    }
1677}
1678
1679// The compiler does not automatically derive Send and Sync for Iter because it contains
1680// raw pointers.
1681unsafe impl<'a, K: Send, V: Send> Send for Iter<'a, K, V> {}
1682unsafe impl<'a, K: Sync, V: Sync> Sync for Iter<'a, K, V> {}
1683
1684/// An iterator over mutables entries of a `LruCache`.
1685///
1686/// This `struct` is created by the [`iter_mut`] method on [`LruCache`][`LruCache`]. See its
1687/// documentation for more.
1688///
1689/// [`iter_mut`]: struct.LruCache.html#method.iter_mut
1690/// [`LruCache`]: struct.LruCache.html
1691pub struct IterMut<'a, K: 'a, V: 'a> {
1692    len: usize,
1693
1694    ptr: *mut LruEntry<K, V>,
1695    end: *mut LruEntry<K, V>,
1696
1697    phantom: PhantomData<&'a K>,
1698}
1699
1700impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1701    type Item = (&'a K, &'a mut V);
1702
1703    fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1704        if self.len == 0 {
1705            return None;
1706        }
1707
1708        let key = unsafe { &mut (*(*self.ptr).key.as_mut_ptr()) as &mut K };
1709        let val = unsafe { &mut (*(*self.ptr).val.as_mut_ptr()) as &mut V };
1710
1711        self.len -= 1;
1712        self.ptr = unsafe { (*self.ptr).next };
1713
1714        Some((key, val))
1715    }
1716
1717    fn size_hint(&self) -> (usize, Option<usize>) {
1718        (self.len, Some(self.len))
1719    }
1720
1721    fn count(self) -> usize {
1722        self.len
1723    }
1724}
1725
1726impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
1727    fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1728        if self.len == 0 {
1729            return None;
1730        }
1731
1732        let key = unsafe { &mut (*(*self.end).key.as_mut_ptr()) as &mut K };
1733        let val = unsafe { &mut (*(*self.end).val.as_mut_ptr()) as &mut V };
1734
1735        self.len -= 1;
1736        self.end = unsafe { (*self.end).prev };
1737
1738        Some((key, val))
1739    }
1740}
1741
1742impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {}
1743impl<'a, K, V> FusedIterator for IterMut<'a, K, V> {}
1744
1745// The compiler does not automatically derive Send and Sync for Iter because it contains
1746// raw pointers.
1747unsafe impl<'a, K: Send, V: Send> Send for IterMut<'a, K, V> {}
1748unsafe impl<'a, K: Sync, V: Sync> Sync for IterMut<'a, K, V> {}
1749
1750/// An iterator that moves out of a `LruCache`.
1751///
1752/// This `struct` is created by the [`into_iter`] method on [`LruCache`][`LruCache`]. See its
1753/// documentation for more.
1754///
1755/// [`into_iter`]: struct.LruCache.html#method.into_iter
1756/// [`LruCache`]: struct.LruCache.html
1757pub struct IntoIter<K, V>
1758where
1759    K: Hash + Eq,
1760{
1761    cache: LruCache<K, V>,
1762}
1763
1764impl<K, V> Iterator for IntoIter<K, V>
1765where
1766    K: Hash + Eq,
1767{
1768    type Item = (K, V);
1769
1770    fn next(&mut self) -> Option<(K, V)> {
1771        self.cache.pop_lru()
1772    }
1773
1774    fn size_hint(&self) -> (usize, Option<usize>) {
1775        let len = self.cache.len();
1776        (len, Some(len))
1777    }
1778
1779    fn count(self) -> usize {
1780        self.cache.len()
1781    }
1782}
1783
1784impl<K, V> ExactSizeIterator for IntoIter<K, V> where K: Hash + Eq {}
1785impl<K, V> FusedIterator for IntoIter<K, V> where K: Hash + Eq {}
1786
1787impl<K: Hash + Eq, V> IntoIterator for LruCache<K, V> {
1788    type Item = (K, V);
1789    type IntoIter = IntoIter<K, V>;
1790
1791    fn into_iter(self) -> IntoIter<K, V> {
1792        IntoIter { cache: self }
1793    }
1794}
1795
1796#[cfg(test)]
1797mod tests {
1798    use super::LruCache;
1799    use core::{fmt::Debug, num::NonZeroUsize};
1800    use scoped_threadpool::Pool;
1801    use std::rc::Rc;
1802    use std::sync::atomic::{AtomicUsize, Ordering};
1803
1804    fn assert_opt_eq<V: PartialEq + Debug>(opt: Option<&V>, v: V) {
1805        assert!(opt.is_some());
1806        assert_eq!(opt.unwrap(), &v);
1807    }
1808
1809    fn assert_opt_eq_mut<V: PartialEq + Debug>(opt: Option<&mut V>, v: V) {
1810        assert!(opt.is_some());
1811        assert_eq!(opt.unwrap(), &v);
1812    }
1813
1814    fn assert_opt_eq_tuple<K: PartialEq + Debug, V: PartialEq + Debug>(
1815        opt: Option<(&K, &V)>,
1816        kv: (K, V),
1817    ) {
1818        assert!(opt.is_some());
1819        let res = opt.unwrap();
1820        assert_eq!(res.0, &kv.0);
1821        assert_eq!(res.1, &kv.1);
1822    }
1823
1824    fn assert_opt_eq_mut_tuple<K: PartialEq + Debug, V: PartialEq + Debug>(
1825        opt: Option<(&K, &mut V)>,
1826        kv: (K, V),
1827    ) {
1828        assert!(opt.is_some());
1829        let res = opt.unwrap();
1830        assert_eq!(res.0, &kv.0);
1831        assert_eq!(res.1, &kv.1);
1832    }
1833
1834    #[test]
1835    fn test_unbounded() {
1836        let mut cache = LruCache::unbounded();
1837        for i in 0..13370 {
1838            cache.put(i, ());
1839        }
1840        assert_eq!(cache.len(), 13370);
1841    }
1842
1843    #[test]
1844    #[cfg(feature = "hashbrown")]
1845    fn test_with_hasher() {
1846        use core::num::NonZeroUsize;
1847
1848        use hashbrown::DefaultHashBuilder;
1849
1850        let s = DefaultHashBuilder::default();
1851        let mut cache = LruCache::with_hasher(NonZeroUsize::new(16).unwrap(), s);
1852
1853        for i in 0..13370 {
1854            cache.put(i, ());
1855        }
1856        assert_eq!(cache.len(), 16);
1857    }
1858
1859    #[test]
1860    fn test_put_and_get() {
1861        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
1862        assert!(cache.is_empty());
1863
1864        assert_eq!(cache.put("apple", "red"), None);
1865        assert_eq!(cache.put("banana", "yellow"), None);
1866
1867        assert_eq!(cache.cap().get(), 2);
1868        assert_eq!(cache.len(), 2);
1869        assert!(!cache.is_empty());
1870        assert_opt_eq(cache.get(&"apple"), "red");
1871        assert_opt_eq(cache.get(&"banana"), "yellow");
1872    }
1873
1874    #[test]
1875    fn test_put_and_get_or_insert() {
1876        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
1877        assert!(cache.is_empty());
1878
1879        assert_eq!(cache.put("apple", "red"), None);
1880        assert_eq!(cache.put("banana", "yellow"), None);
1881
1882        assert_eq!(cache.cap().get(), 2);
1883        assert_eq!(cache.len(), 2);
1884        assert!(!cache.is_empty());
1885        assert_eq!(cache.get_or_insert("apple", || "orange"), &"red");
1886        assert_eq!(cache.get_or_insert("banana", || "orange"), &"yellow");
1887        assert_eq!(cache.get_or_insert("lemon", || "orange"), &"orange");
1888        assert_eq!(cache.get_or_insert("lemon", || "red"), &"orange");
1889    }
1890
1891    #[test]
1892    fn test_get_or_insert_ref() {
1893        use alloc::borrow::ToOwned;
1894        use alloc::string::String;
1895
1896        let key1 = Rc::new("1".to_owned());
1897        let key2 = Rc::new("2".to_owned());
1898        let mut cache = LruCache::<Rc<String>, String>::new(NonZeroUsize::new(2).unwrap());
1899        assert!(cache.is_empty());
1900        assert_eq!(cache.get_or_insert_ref(&key1, || "One".to_owned()), "One");
1901        assert_eq!(cache.get_or_insert_ref(&key2, || "Two".to_owned()), "Two");
1902        assert_eq!(cache.len(), 2);
1903        assert!(!cache.is_empty());
1904        assert_eq!(
1905            cache.get_or_insert_ref(&key2, || "Not two".to_owned()),
1906            "Two"
1907        );
1908        assert_eq!(
1909            cache.get_or_insert_ref(&key2, || "Again not two".to_owned()),
1910            "Two"
1911        );
1912        assert_eq!(Rc::strong_count(&key1), 2);
1913        assert_eq!(Rc::strong_count(&key2), 2);
1914    }
1915
1916    #[test]
1917    fn test_try_get_or_insert() {
1918        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
1919
1920        assert_eq!(
1921            cache.try_get_or_insert::<_, &str>("apple", || Ok("red")),
1922            Ok(&"red")
1923        );
1924        assert_eq!(
1925            cache.try_get_or_insert::<_, &str>("apple", || Err("failed")),
1926            Ok(&"red")
1927        );
1928        assert_eq!(
1929            cache.try_get_or_insert::<_, &str>("banana", || Ok("orange")),
1930            Ok(&"orange")
1931        );
1932        assert_eq!(
1933            cache.try_get_or_insert::<_, &str>("lemon", || Err("failed")),
1934            Err("failed")
1935        );
1936        assert_eq!(
1937            cache.try_get_or_insert::<_, &str>("banana", || Err("failed")),
1938            Ok(&"orange")
1939        );
1940    }
1941
1942    #[test]
1943    fn test_try_get_or_insert_ref() {
1944        use alloc::borrow::ToOwned;
1945        use alloc::string::String;
1946
1947        let key1 = Rc::new("1".to_owned());
1948        let key2 = Rc::new("2".to_owned());
1949        let mut cache = LruCache::<Rc<String>, String>::new(NonZeroUsize::new(2).unwrap());
1950        let f = || -> Result<String, ()> { Err(()) };
1951        let a = || -> Result<String, ()> { Ok("One".to_owned()) };
1952        let b = || -> Result<String, ()> { Ok("Two".to_owned()) };
1953        assert_eq!(cache.try_get_or_insert_ref(&key1, a), Ok(&"One".to_owned()));
1954        assert_eq!(cache.try_get_or_insert_ref(&key2, f), Err(()));
1955        assert_eq!(cache.try_get_or_insert_ref(&key2, b), Ok(&"Two".to_owned()));
1956        assert_eq!(cache.try_get_or_insert_ref(&key2, a), Ok(&"Two".to_owned()));
1957        assert_eq!(cache.len(), 2);
1958        assert_eq!(Rc::strong_count(&key1), 2);
1959        assert_eq!(Rc::strong_count(&key2), 2);
1960    }
1961
1962    #[test]
1963    fn test_put_and_get_or_insert_mut() {
1964        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
1965        assert!(cache.is_empty());
1966
1967        assert_eq!(cache.put("apple", "red"), None);
1968        assert_eq!(cache.put("banana", "yellow"), None);
1969
1970        assert_eq!(cache.cap().get(), 2);
1971        assert_eq!(cache.len(), 2);
1972
1973        let v = cache.get_or_insert_mut("apple", || "orange");
1974        assert_eq!(v, &"red");
1975        *v = "blue";
1976
1977        assert_eq!(cache.get_or_insert_mut("apple", || "orange"), &"blue");
1978        assert_eq!(cache.get_or_insert_mut("banana", || "orange"), &"yellow");
1979        assert_eq!(cache.get_or_insert_mut("lemon", || "orange"), &"orange");
1980        assert_eq!(cache.get_or_insert_mut("lemon", || "red"), &"orange");
1981    }
1982
1983    #[test]
1984    fn test_get_or_insert_mut_ref() {
1985        use alloc::borrow::ToOwned;
1986        use alloc::string::String;
1987
1988        let key1 = Rc::new("1".to_owned());
1989        let key2 = Rc::new("2".to_owned());
1990        let mut cache = LruCache::<Rc<String>, &'static str>::new(NonZeroUsize::new(2).unwrap());
1991        assert_eq!(cache.get_or_insert_mut_ref(&key1, || "One"), &mut "One");
1992        let v = cache.get_or_insert_mut_ref(&key2, || "Two");
1993        *v = "New two";
1994        assert_eq!(cache.get_or_insert_mut_ref(&key2, || "Two"), &mut "New two");
1995        assert_eq!(Rc::strong_count(&key1), 2);
1996        assert_eq!(Rc::strong_count(&key2), 2);
1997    }
1998
1999    #[test]
2000    fn test_try_get_or_insert_mut() {
2001        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
2002
2003        cache.put(1, "a");
2004        cache.put(2, "b");
2005        cache.put(2, "c");
2006
2007        let f = || -> Result<&str, &str> { Err("failed") };
2008        let a = || -> Result<&str, &str> { Ok("a") };
2009        let b = || -> Result<&str, &str> { Ok("b") };
2010        if let Ok(v) = cache.try_get_or_insert_mut(2, a) {
2011            *v = "d";
2012        }
2013        assert_eq!(cache.try_get_or_insert_mut(2, a), Ok(&mut "d"));
2014        assert_eq!(cache.try_get_or_insert_mut(3, f), Err("failed"));
2015        assert_eq!(cache.try_get_or_insert_mut(4, b), Ok(&mut "b"));
2016        assert_eq!(cache.try_get_or_insert_mut(4, a), Ok(&mut "b"));
2017    }
2018
2019    #[test]
2020    fn test_try_get_or_insert_mut_ref() {
2021        use alloc::borrow::ToOwned;
2022        use alloc::string::String;
2023
2024        let key1 = Rc::new("1".to_owned());
2025        let key2 = Rc::new("2".to_owned());
2026        let mut cache = LruCache::<Rc<String>, String>::new(NonZeroUsize::new(2).unwrap());
2027        let f = || -> Result<String, ()> { Err(()) };
2028        let a = || -> Result<String, ()> { Ok("One".to_owned()) };
2029        let b = || -> Result<String, ()> { Ok("Two".to_owned()) };
2030        assert_eq!(
2031            cache.try_get_or_insert_mut_ref(&key1, a),
2032            Ok(&mut "One".to_owned())
2033        );
2034        assert_eq!(cache.try_get_or_insert_mut_ref(&key2, f), Err(()));
2035        if let Ok(v) = cache.try_get_or_insert_mut_ref(&key2, b) {
2036            assert_eq!(v, &mut "Two");
2037            *v = "New two".to_owned();
2038        }
2039        assert_eq!(
2040            cache.try_get_or_insert_mut_ref(&key2, a),
2041            Ok(&mut "New two".to_owned())
2042        );
2043        assert_eq!(Rc::strong_count(&key1), 2);
2044        assert_eq!(Rc::strong_count(&key2), 2);
2045    }
2046
2047    #[test]
2048    fn test_put_and_get_mut() {
2049        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
2050
2051        cache.put("apple", "red");
2052        cache.put("banana", "yellow");
2053
2054        assert_eq!(cache.cap().get(), 2);
2055        assert_eq!(cache.len(), 2);
2056        assert_opt_eq_mut(cache.get_mut(&"apple"), "red");
2057        assert_opt_eq_mut(cache.get_mut(&"banana"), "yellow");
2058    }
2059
2060    #[test]
2061    fn test_get_mut_and_update() {
2062        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
2063
2064        cache.put("apple", 1);
2065        cache.put("banana", 3);
2066
2067        {
2068            let v = cache.get_mut(&"apple").unwrap();
2069            *v = 4;
2070        }
2071
2072        assert_eq!(cache.cap().get(), 2);
2073        assert_eq!(cache.len(), 2);
2074        assert_opt_eq_mut(cache.get_mut(&"apple"), 4);
2075        assert_opt_eq_mut(cache.get_mut(&"banana"), 3);
2076    }
2077
2078    #[test]
2079    fn test_put_update() {
2080        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
2081
2082        assert_eq!(cache.put("apple", "red"), None);
2083        assert_eq!(cache.put("apple", "green"), Some("red"));
2084
2085        assert_eq!(cache.len(), 1);
2086        assert_opt_eq(cache.get(&"apple"), "green");
2087    }
2088
2089    #[test]
2090    fn test_put_removes_oldest() {
2091        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
2092
2093        assert_eq!(cache.put("apple", "red"), None);
2094        assert_eq!(cache.put("banana", "yellow"), None);
2095        assert_eq!(cache.put("pear", "green"), None);
2096
2097        assert!(cache.get(&"apple").is_none());
2098        assert_opt_eq(cache.get(&"banana"), "yellow");
2099        assert_opt_eq(cache.get(&"pear"), "green");
2100
2101        // Even though we inserted "apple" into the cache earlier it has since been removed from
2102        // the cache so there is no current value for `put` to return.
2103        assert_eq!(cache.put("apple", "green"), None);
2104        assert_eq!(cache.put("tomato", "red"), None);
2105
2106        assert!(cache.get(&"pear").is_none());
2107        assert_opt_eq(cache.get(&"apple"), "green");
2108        assert_opt_eq(cache.get(&"tomato"), "red");
2109    }
2110
2111    #[test]
2112    fn test_peek() {
2113        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
2114
2115        cache.put("apple", "red");
2116        cache.put("banana", "yellow");
2117
2118        assert_opt_eq(cache.peek(&"banana"), "yellow");
2119        assert_opt_eq(cache.peek(&"apple"), "red");
2120
2121        cache.put("pear", "green");
2122
2123        assert!(cache.peek(&"apple").is_none());
2124        assert_opt_eq(cache.peek(&"banana"), "yellow");
2125        assert_opt_eq(cache.peek(&"pear"), "green");
2126    }
2127
2128    #[test]
2129    fn test_peek_mut() {
2130        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
2131
2132        cache.put("apple", "red");
2133        cache.put("banana", "yellow");
2134
2135        assert_opt_eq_mut(cache.peek_mut(&"banana"), "yellow");
2136        assert_opt_eq_mut(cache.peek_mut(&"apple"), "red");
2137        assert!(cache.peek_mut(&"pear").is_none());
2138
2139        cache.put("pear", "green");
2140
2141        assert!(cache.peek_mut(&"apple").is_none());
2142        assert_opt_eq_mut(cache.peek_mut(&"banana"), "yellow");
2143        assert_opt_eq_mut(cache.peek_mut(&"pear"), "green");
2144
2145        {
2146            let v = cache.peek_mut(&"banana").unwrap();
2147            *v = "green";
2148        }
2149
2150        assert_opt_eq_mut(cache.peek_mut(&"banana"), "green");
2151    }
2152
2153    #[test]
2154    fn test_peek_lru() {
2155        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
2156
2157        assert!(cache.peek_lru().is_none());
2158
2159        cache.put("apple", "red");
2160        cache.put("banana", "yellow");
2161        assert_opt_eq_tuple(cache.peek_lru(), ("apple", "red"));
2162
2163        cache.get(&"apple");
2164        assert_opt_eq_tuple(cache.peek_lru(), ("banana", "yellow"));
2165
2166        cache.clear();
2167        assert!(cache.peek_lru().is_none());
2168    }
2169
2170    #[test]
2171    fn test_peek_mru() {
2172        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
2173
2174        assert!(cache.peek_mru().is_none());
2175
2176        cache.put("apple", "red");
2177        cache.put("banana", "yellow");
2178        assert_opt_eq_tuple(cache.peek_mru(), ("banana", "yellow"));
2179
2180        cache.get(&"apple");
2181        assert_opt_eq_tuple(cache.peek_mru(), ("apple", "red"));
2182
2183        cache.clear();
2184        assert!(cache.peek_mru().is_none());
2185    }
2186
2187    #[test]
2188    fn test_contains() {
2189        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
2190
2191        cache.put("apple", "red");
2192        cache.put("banana", "yellow");
2193        cache.put("pear", "green");
2194
2195        assert!(!cache.contains(&"apple"));
2196        assert!(cache.contains(&"banana"));
2197        assert!(cache.contains(&"pear"));
2198    }
2199
2200    #[test]
2201    fn test_pop() {
2202        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
2203
2204        cache.put("apple", "red");
2205        cache.put("banana", "yellow");
2206
2207        assert_eq!(cache.len(), 2);
2208        assert_opt_eq(cache.get(&"apple"), "red");
2209        assert_opt_eq(cache.get(&"banana"), "yellow");
2210
2211        let popped = cache.pop(&"apple");
2212        assert!(popped.is_some());
2213        assert_eq!(popped.unwrap(), "red");
2214        assert_eq!(cache.len(), 1);
2215        assert!(cache.get(&"apple").is_none());
2216        assert_opt_eq(cache.get(&"banana"), "yellow");
2217    }
2218
2219    #[test]
2220    fn test_pop_entry() {
2221        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
2222        cache.put("apple", "red");
2223        cache.put("banana", "yellow");
2224
2225        assert_eq!(cache.len(), 2);
2226        assert_opt_eq(cache.get(&"apple"), "red");
2227        assert_opt_eq(cache.get(&"banana"), "yellow");
2228
2229        let popped = cache.pop_entry(&"apple");
2230        assert!(popped.is_some());
2231        assert_eq!(popped.unwrap(), ("apple", "red"));
2232        assert_eq!(cache.len(), 1);
2233        assert!(cache.get(&"apple").is_none());
2234        assert_opt_eq(cache.get(&"banana"), "yellow");
2235    }
2236
2237    #[test]
2238    fn test_pop_lru() {
2239        let mut cache = LruCache::new(NonZeroUsize::new(200).unwrap());
2240
2241        for i in 0..75 {
2242            cache.put(i, "A");
2243        }
2244        for i in 0..75 {
2245            cache.put(i + 100, "B");
2246        }
2247        for i in 0..75 {
2248            cache.put(i + 200, "C");
2249        }
2250        assert_eq!(cache.len(), 200);
2251
2252        for i in 0..75 {
2253            assert_opt_eq(cache.get(&(74 - i + 100)), "B");
2254        }
2255        assert_opt_eq(cache.get(&25), "A");
2256
2257        for i in 26..75 {
2258            assert_eq!(cache.pop_lru(), Some((i, "A")));
2259        }
2260        for i in 0..75 {
2261            assert_eq!(cache.pop_lru(), Some((i + 200, "C")));
2262        }
2263        for i in 0..75 {
2264            assert_eq!(cache.pop_lru(), Some((74 - i + 100, "B")));
2265        }
2266        assert_eq!(cache.pop_lru(), Some((25, "A")));
2267        for _ in 0..50 {
2268            assert_eq!(cache.pop_lru(), None);
2269        }
2270    }
2271
2272    #[test]
2273    fn test_pop_mru() {
2274        let mut cache = LruCache::new(NonZeroUsize::new(200).unwrap());
2275
2276        for i in 0..75 {
2277            cache.put(i, "A");
2278        }
2279        for i in 0..75 {
2280            cache.put(i + 100, "B");
2281        }
2282        for i in 0..75 {
2283            cache.put(i + 200, "C");
2284        }
2285        assert_eq!(cache.len(), 200);
2286
2287        for i in 0..75 {
2288            assert_opt_eq(cache.get(&(74 - i + 100)), "B");
2289        }
2290        assert_opt_eq(cache.get(&25), "A");
2291
2292        assert_eq!(cache.pop_mru(), Some((25, "A")));
2293        for i in 0..75 {
2294            assert_eq!(cache.pop_mru(), Some((i + 100, "B")));
2295        }
2296        for i in 0..75 {
2297            assert_eq!(cache.pop_mru(), Some((74 - i + 200, "C")));
2298        }
2299        for i in (26..75).into_iter().rev() {
2300            assert_eq!(cache.pop_mru(), Some((i, "A")));
2301        }
2302        for _ in 0..50 {
2303            assert_eq!(cache.pop_mru(), None);
2304        }
2305    }
2306
2307    #[test]
2308    fn test_clear() {
2309        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
2310
2311        cache.put("apple", "red");
2312        cache.put("banana", "yellow");
2313
2314        assert_eq!(cache.len(), 2);
2315        assert_opt_eq(cache.get(&"apple"), "red");
2316        assert_opt_eq(cache.get(&"banana"), "yellow");
2317
2318        cache.clear();
2319        assert_eq!(cache.len(), 0);
2320    }
2321
2322    #[test]
2323    fn test_resize_larger() {
2324        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
2325
2326        cache.put(1, "a");
2327        cache.put(2, "b");
2328        cache.resize(NonZeroUsize::new(4).unwrap());
2329        cache.put(3, "c");
2330        cache.put(4, "d");
2331
2332        assert_eq!(cache.len(), 4);
2333        assert_eq!(cache.get(&1), Some(&"a"));
2334        assert_eq!(cache.get(&2), Some(&"b"));
2335        assert_eq!(cache.get(&3), Some(&"c"));
2336        assert_eq!(cache.get(&4), Some(&"d"));
2337    }
2338
2339    #[test]
2340    fn test_resize_smaller() {
2341        let mut cache = LruCache::new(NonZeroUsize::new(4).unwrap());
2342
2343        cache.put(1, "a");
2344        cache.put(2, "b");
2345        cache.put(3, "c");
2346        cache.put(4, "d");
2347
2348        cache.resize(NonZeroUsize::new(2).unwrap());
2349
2350        assert_eq!(cache.len(), 2);
2351        assert!(cache.get(&1).is_none());
2352        assert!(cache.get(&2).is_none());
2353        assert_eq!(cache.get(&3), Some(&"c"));
2354        assert_eq!(cache.get(&4), Some(&"d"));
2355    }
2356
2357    #[test]
2358    fn test_send() {
2359        use std::thread;
2360
2361        let mut cache = LruCache::new(NonZeroUsize::new(4).unwrap());
2362        cache.put(1, "a");
2363
2364        let handle = thread::spawn(move || {
2365            assert_eq!(cache.get(&1), Some(&"a"));
2366        });
2367
2368        assert!(handle.join().is_ok());
2369    }
2370
2371    #[test]
2372    fn test_multiple_threads() {
2373        let mut pool = Pool::new(1);
2374        let mut cache = LruCache::new(NonZeroUsize::new(4).unwrap());
2375        cache.put(1, "a");
2376
2377        let cache_ref = &cache;
2378        pool.scoped(|scoped| {
2379            scoped.execute(move || {
2380                assert_eq!(cache_ref.peek(&1), Some(&"a"));
2381            });
2382        });
2383
2384        assert_eq!((cache_ref).peek(&1), Some(&"a"));
2385    }
2386
2387    #[test]
2388    fn test_iter_forwards() {
2389        let mut cache = LruCache::new(NonZeroUsize::new(3).unwrap());
2390        cache.put("a", 1);
2391        cache.put("b", 2);
2392        cache.put("c", 3);
2393
2394        {
2395            // iter const
2396            let mut iter = cache.iter();
2397            assert_eq!(iter.len(), 3);
2398            assert_opt_eq_tuple(iter.next(), ("c", 3));
2399
2400            assert_eq!(iter.len(), 2);
2401            assert_opt_eq_tuple(iter.next(), ("b", 2));
2402
2403            assert_eq!(iter.len(), 1);
2404            assert_opt_eq_tuple(iter.next(), ("a", 1));
2405
2406            assert_eq!(iter.len(), 0);
2407            assert_eq!(iter.next(), None);
2408        }
2409        {
2410            // iter mut
2411            let mut iter = cache.iter_mut();
2412            assert_eq!(iter.len(), 3);
2413            assert_opt_eq_mut_tuple(iter.next(), ("c", 3));
2414
2415            assert_eq!(iter.len(), 2);
2416            assert_opt_eq_mut_tuple(iter.next(), ("b", 2));
2417
2418            assert_eq!(iter.len(), 1);
2419            assert_opt_eq_mut_tuple(iter.next(), ("a", 1));
2420
2421            assert_eq!(iter.len(), 0);
2422            assert_eq!(iter.next(), None);
2423        }
2424    }
2425
2426    #[test]
2427    fn test_iter_backwards() {
2428        let mut cache = LruCache::new(NonZeroUsize::new(3).unwrap());
2429        cache.put("a", 1);
2430        cache.put("b", 2);
2431        cache.put("c", 3);
2432
2433        {
2434            // iter const
2435            let mut iter = cache.iter();
2436            assert_eq!(iter.len(), 3);
2437            assert_opt_eq_tuple(iter.next_back(), ("a", 1));
2438
2439            assert_eq!(iter.len(), 2);
2440            assert_opt_eq_tuple(iter.next_back(), ("b", 2));
2441
2442            assert_eq!(iter.len(), 1);
2443            assert_opt_eq_tuple(iter.next_back(), ("c", 3));
2444
2445            assert_eq!(iter.len(), 0);
2446            assert_eq!(iter.next_back(), None);
2447        }
2448
2449        {
2450            // iter mut
2451            let mut iter = cache.iter_mut();
2452            assert_eq!(iter.len(), 3);
2453            assert_opt_eq_mut_tuple(iter.next_back(), ("a", 1));
2454
2455            assert_eq!(iter.len(), 2);
2456            assert_opt_eq_mut_tuple(iter.next_back(), ("b", 2));
2457
2458            assert_eq!(iter.len(), 1);
2459            assert_opt_eq_mut_tuple(iter.next_back(), ("c", 3));
2460
2461            assert_eq!(iter.len(), 0);
2462            assert_eq!(iter.next_back(), None);
2463        }
2464    }
2465
2466    #[test]
2467    fn test_iter_forwards_and_backwards() {
2468        let mut cache = LruCache::new(NonZeroUsize::new(3).unwrap());
2469        cache.put("a", 1);
2470        cache.put("b", 2);
2471        cache.put("c", 3);
2472
2473        {
2474            // iter const
2475            let mut iter = cache.iter();
2476            assert_eq!(iter.len(), 3);
2477            assert_opt_eq_tuple(iter.next(), ("c", 3));
2478
2479            assert_eq!(iter.len(), 2);
2480            assert_opt_eq_tuple(iter.next_back(), ("a", 1));
2481
2482            assert_eq!(iter.len(), 1);
2483            assert_opt_eq_tuple(iter.next(), ("b", 2));
2484
2485            assert_eq!(iter.len(), 0);
2486            assert_eq!(iter.next_back(), None);
2487        }
2488        {
2489            // iter mut
2490            let mut iter = cache.iter_mut();
2491            assert_eq!(iter.len(), 3);
2492            assert_opt_eq_mut_tuple(iter.next(), ("c", 3));
2493
2494            assert_eq!(iter.len(), 2);
2495            assert_opt_eq_mut_tuple(iter.next_back(), ("a", 1));
2496
2497            assert_eq!(iter.len(), 1);
2498            assert_opt_eq_mut_tuple(iter.next(), ("b", 2));
2499
2500            assert_eq!(iter.len(), 0);
2501            assert_eq!(iter.next_back(), None);
2502        }
2503    }
2504
2505    #[test]
2506    fn test_iter_multiple_threads() {
2507        let mut pool = Pool::new(1);
2508        let mut cache = LruCache::new(NonZeroUsize::new(3).unwrap());
2509        cache.put("a", 1);
2510        cache.put("b", 2);
2511        cache.put("c", 3);
2512
2513        let mut iter = cache.iter();
2514        assert_eq!(iter.len(), 3);
2515        assert_opt_eq_tuple(iter.next(), ("c", 3));
2516
2517        {
2518            let iter_ref = &mut iter;
2519            pool.scoped(|scoped| {
2520                scoped.execute(move || {
2521                    assert_eq!(iter_ref.len(), 2);
2522                    assert_opt_eq_tuple(iter_ref.next(), ("b", 2));
2523                });
2524            });
2525        }
2526
2527        assert_eq!(iter.len(), 1);
2528        assert_opt_eq_tuple(iter.next(), ("a", 1));
2529
2530        assert_eq!(iter.len(), 0);
2531        assert_eq!(iter.next(), None);
2532    }
2533
2534    #[test]
2535    fn test_iter_clone() {
2536        let mut cache = LruCache::new(NonZeroUsize::new(3).unwrap());
2537        cache.put("a", 1);
2538        cache.put("b", 2);
2539
2540        let mut iter = cache.iter();
2541        let mut iter_clone = iter.clone();
2542
2543        assert_eq!(iter.len(), 2);
2544        assert_opt_eq_tuple(iter.next(), ("b", 2));
2545        assert_eq!(iter_clone.len(), 2);
2546        assert_opt_eq_tuple(iter_clone.next(), ("b", 2));
2547
2548        assert_eq!(iter.len(), 1);
2549        assert_opt_eq_tuple(iter.next(), ("a", 1));
2550        assert_eq!(iter_clone.len(), 1);
2551        assert_opt_eq_tuple(iter_clone.next(), ("a", 1));
2552
2553        assert_eq!(iter.len(), 0);
2554        assert_eq!(iter.next(), None);
2555        assert_eq!(iter_clone.len(), 0);
2556        assert_eq!(iter_clone.next(), None);
2557    }
2558
2559    #[test]
2560    fn test_into_iter() {
2561        let mut cache = LruCache::new(NonZeroUsize::new(3).unwrap());
2562        cache.put("a", 1);
2563        cache.put("b", 2);
2564        cache.put("c", 3);
2565
2566        let mut iter = cache.into_iter();
2567        assert_eq!(iter.len(), 3);
2568        assert_eq!(iter.next(), Some(("a", 1)));
2569
2570        assert_eq!(iter.len(), 2);
2571        assert_eq!(iter.next(), Some(("b", 2)));
2572
2573        assert_eq!(iter.len(), 1);
2574        assert_eq!(iter.next(), Some(("c", 3)));
2575
2576        assert_eq!(iter.len(), 0);
2577        assert_eq!(iter.next(), None);
2578    }
2579
2580    #[test]
2581    fn test_that_pop_actually_detaches_node() {
2582        let mut cache = LruCache::new(NonZeroUsize::new(5).unwrap());
2583
2584        cache.put("a", 1);
2585        cache.put("b", 2);
2586        cache.put("c", 3);
2587        cache.put("d", 4);
2588        cache.put("e", 5);
2589
2590        assert_eq!(cache.pop(&"c"), Some(3));
2591
2592        cache.put("f", 6);
2593
2594        let mut iter = cache.iter();
2595        assert_opt_eq_tuple(iter.next(), ("f", 6));
2596        assert_opt_eq_tuple(iter.next(), ("e", 5));
2597        assert_opt_eq_tuple(iter.next(), ("d", 4));
2598        assert_opt_eq_tuple(iter.next(), ("b", 2));
2599        assert_opt_eq_tuple(iter.next(), ("a", 1));
2600        assert!(iter.next().is_none());
2601    }
2602
2603    #[test]
2604    fn test_get_with_borrow() {
2605        use alloc::string::String;
2606
2607        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
2608
2609        let key = String::from("apple");
2610        cache.put(key, "red");
2611
2612        assert_opt_eq(cache.get("apple"), "red");
2613    }
2614
2615    #[test]
2616    fn test_get_mut_with_borrow() {
2617        use alloc::string::String;
2618
2619        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
2620
2621        let key = String::from("apple");
2622        cache.put(key, "red");
2623
2624        assert_opt_eq_mut(cache.get_mut("apple"), "red");
2625    }
2626
2627    #[test]
2628    fn test_no_memory_leaks() {
2629        static DROP_COUNT: AtomicUsize = AtomicUsize::new(0);
2630
2631        struct DropCounter;
2632
2633        impl Drop for DropCounter {
2634            fn drop(&mut self) {
2635                DROP_COUNT.fetch_add(1, Ordering::SeqCst);
2636            }
2637        }
2638
2639        let n = 100;
2640        for _ in 0..n {
2641            let mut cache = LruCache::new(NonZeroUsize::new(1).unwrap());
2642            for i in 0..n {
2643                cache.put(i, DropCounter {});
2644            }
2645        }
2646        assert_eq!(DROP_COUNT.load(Ordering::SeqCst), n * n);
2647    }
2648
2649    #[test]
2650    fn test_no_memory_leaks_with_clear() {
2651        static DROP_COUNT: AtomicUsize = AtomicUsize::new(0);
2652
2653        struct DropCounter;
2654
2655        impl Drop for DropCounter {
2656            fn drop(&mut self) {
2657                DROP_COUNT.fetch_add(1, Ordering::SeqCst);
2658            }
2659        }
2660
2661        let n = 100;
2662        for _ in 0..n {
2663            let mut cache = LruCache::new(NonZeroUsize::new(1).unwrap());
2664            for i in 0..n {
2665                cache.put(i, DropCounter {});
2666            }
2667            cache.clear();
2668        }
2669        assert_eq!(DROP_COUNT.load(Ordering::SeqCst), n * n);
2670    }
2671
2672    #[test]
2673    fn test_no_memory_leaks_with_resize() {
2674        static DROP_COUNT: AtomicUsize = AtomicUsize::new(0);
2675
2676        struct DropCounter;
2677
2678        impl Drop for DropCounter {
2679            fn drop(&mut self) {
2680                DROP_COUNT.fetch_add(1, Ordering::SeqCst);
2681            }
2682        }
2683
2684        let n = 100;
2685        for _ in 0..n {
2686            let mut cache = LruCache::new(NonZeroUsize::new(1).unwrap());
2687            for i in 0..n {
2688                cache.put(i, DropCounter {});
2689            }
2690            cache.clear();
2691        }
2692        assert_eq!(DROP_COUNT.load(Ordering::SeqCst), n * n);
2693    }
2694
2695    #[test]
2696    fn test_no_memory_leaks_with_pop() {
2697        static DROP_COUNT: AtomicUsize = AtomicUsize::new(0);
2698
2699        #[derive(Hash, Eq)]
2700        struct KeyDropCounter(usize);
2701
2702        impl PartialEq for KeyDropCounter {
2703            fn eq(&self, other: &Self) -> bool {
2704                self.0.eq(&other.0)
2705            }
2706        }
2707
2708        impl Drop for KeyDropCounter {
2709            fn drop(&mut self) {
2710                DROP_COUNT.fetch_add(1, Ordering::SeqCst);
2711            }
2712        }
2713
2714        let n = 100;
2715        for _ in 0..n {
2716            let mut cache = LruCache::new(NonZeroUsize::new(1).unwrap());
2717
2718            for i in 0..100 {
2719                cache.put(KeyDropCounter(i), i);
2720                cache.pop(&KeyDropCounter(i));
2721            }
2722        }
2723
2724        assert_eq!(DROP_COUNT.load(Ordering::SeqCst), n * n * 2);
2725    }
2726
2727    #[test]
2728    fn test_promote_and_demote() {
2729        let mut cache = LruCache::new(NonZeroUsize::new(5).unwrap());
2730        for i in 0..5 {
2731            cache.push(i, i);
2732        }
2733        cache.promote(&1);
2734        cache.promote(&0);
2735        cache.demote(&3);
2736        cache.demote(&4);
2737        assert_eq!(cache.pop_lru(), Some((4, 4)));
2738        assert_eq!(cache.pop_lru(), Some((3, 3)));
2739        assert_eq!(cache.pop_lru(), Some((2, 2)));
2740        assert_eq!(cache.pop_lru(), Some((1, 1)));
2741        assert_eq!(cache.pop_lru(), Some((0, 0)));
2742        assert_eq!(cache.pop_lru(), None);
2743    }
2744
2745    #[test]
2746    fn test_get_key_value() {
2747        use alloc::string::String;
2748
2749        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
2750
2751        let key = String::from("apple");
2752        cache.put(key, "red");
2753
2754        assert_eq!(
2755            cache.get_key_value("apple"),
2756            Some((&String::from("apple"), &"red"))
2757        );
2758        assert_eq!(cache.get_key_value("banana"), None);
2759    }
2760
2761    #[test]
2762    fn test_get_key_value_mut() {
2763        use alloc::string::String;
2764
2765        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
2766
2767        let key = String::from("apple");
2768        cache.put(key, "red");
2769
2770        let (k, v) = cache.get_key_value_mut("apple").unwrap();
2771        assert_eq!(k, &String::from("apple"));
2772        assert_eq!(v, &mut "red");
2773        *v = "green";
2774
2775        assert_eq!(
2776            cache.get_key_value("apple"),
2777            Some((&String::from("apple"), &"green"))
2778        );
2779        assert_eq!(cache.get_key_value("banana"), None);
2780    }
2781
2782    #[test]
2783    fn test_clone() {
2784        let mut cache = LruCache::new(NonZeroUsize::new(3).unwrap());
2785        cache.put("a", 1);
2786        cache.put("b", 2);
2787        cache.put("c", 3);
2788
2789        let mut cloned = cache.clone();
2790
2791        assert_eq!(cache.pop_lru(), Some(("a", 1)));
2792        assert_eq!(cloned.pop_lru(), Some(("a", 1)));
2793
2794        assert_eq!(cache.pop_lru(), Some(("b", 2)));
2795        assert_eq!(cloned.pop_lru(), Some(("b", 2)));
2796
2797        assert_eq!(cache.pop_lru(), Some(("c", 3)));
2798        assert_eq!(cloned.pop_lru(), Some(("c", 3)));
2799
2800        assert_eq!(cache.pop_lru(), None);
2801        assert_eq!(cloned.pop_lru(), None);
2802    }
2803}
2804
2805/// Doctests for what should *not* compile
2806///
2807/// ```compile_fail
2808/// let mut cache = lru::LruCache::<u32, u32>::unbounded();
2809/// let _: &'static u32 = cache.get_or_insert(0, || 92);
2810/// ```
2811///
2812/// ```compile_fail
2813/// let mut cache = lru::LruCache::<u32, u32>::unbounded();
2814/// let _: Option<(&'static u32, _)> = cache.peek_lru();
2815/// let _: Option<(_, &'static u32)> = cache.peek_lru();
2816/// ```
2817fn _test_lifetimes() {}