1#![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
88struct 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 #![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#[repr(transparent)]
114struct KeyWrapper<K: ?Sized>(K);
115
116impl<K: ?Sized> KeyWrapper<K> {
117 fn from_ref(key: &K) -> &Self {
118 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 #![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
152struct 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
186pub struct LruCache<K, V, S = DefaultHasher> {
188 map: HashMap<KeyRef<K>, NonNull<LruEntry<K, V>>, S>,
189 cap: NonZeroUsize,
190
191 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 pub fn new(cap: NonZeroUsize) -> LruCache<K, V> {
223 LruCache::construct(cap, HashMap::with_capacity(cap.get()))
224 }
225
226 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 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 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 fn construct(
277 cap: NonZeroUsize,
278 map: HashMap<KeyRef<K>, NonNull<LruEntry<K, V>>, S>,
279 ) -> LruCache<K, V, S> {
280 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 pub fn put(&mut self, k: K, v: V) -> Option<V> {
315 self.capturing_put(k, v, false).map(|(_, v)| v)
316 }
317
318 pub fn push(&mut self, k: K, v: V) -> Option<(K, V)> {
343 self.capturing_put(k, v, true)
344 }
345
346 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 let node_ptr: *mut LruEntry<K, V> = node_ref.as_ptr();
357
358 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 #[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 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 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 (None, unsafe {
408 NonNull::new_unchecked(Box::into_raw(Box::new(LruEntry::new(k, v))))
409 })
410 }
411 }
412
413 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 pub fn pop_lru(&mut self) -> Option<(K, V)> {
1218 let node = self.remove_last()?;
1219 let node = *node;
1221 let LruEntry { key, val, .. } = node;
1222 unsafe { Some((key.assume_init(), val.assume_init())) }
1223 }
1224
1225 pub fn pop_mru(&mut self) -> Option<(K, V)> {
1246 let node = self.remove_first()?;
1247 let node = *node;
1249 let LruEntry { key, val, .. } = node;
1250 unsafe { Some((key.assume_init(), val.assume_init())) }
1251 }
1252
1253 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 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 pub fn len(&self) -> usize {
1343 self.map.len()
1344 }
1345
1346 pub fn is_empty(&self) -> bool {
1360 self.map.len() == 0
1361 }
1362
1363 pub fn cap(&self) -> NonZeroUsize {
1374 self.cap
1375 }
1376
1377 pub fn resize(&mut self, cap: NonZeroUsize) {
1400 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 pub fn clear(&mut self) {
1433 while self.pop_lru().is_some() {}
1434 }
1435
1436 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 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 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 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 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
1592unsafe 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
1607pub 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
1679unsafe 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
1684pub 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
1745unsafe 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
1750pub 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 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 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 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 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 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 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 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
2805fn _test_lifetimes() {}