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