1//! Another LRU cache implementation in rust.
2//! It has two main characteristics that differentiates it from other implementation:
3//!
4//! 1. It is backed by a [HashMap](https://doc.rust-lang.org/std/collections/struct.HashMap.html): it
5//! offers a O(1) time complexity (amortized average) for any operation that requires to lookup an entry from
6//! a key.
7//!
8//! 2. It is a weighted cache: each key-value pair has a weight and the capacity serves as both as:
9//! * a limit to the number of elements
10//! * and as a limit to the total weight of its elements
11//!
12//! using the following formula:
13//!
14//! [`CLruCache::len`] + [`CLruCache::weight`] <= [`CLruCache::capacity`]
15//!
16//! Even though most operations don't depend on the number of elements in the cache,
17//! [`CLruCache::put_with_weight`] has a special behavior: because it needs to make room
18//! for the new element, it will remove enough least recently used elements. In the worst
19//! case, that will require to fully empty the cache. Additionally, if the weight of the
20//! new element is too big, the insertion can fail.
21//!
22//! For the common case of an LRU cache whose elements don't have a weight, a default
23//! [`ZeroWeightScale`] is provided and unlocks some useful APIs like:
24//!
25//! * [`CLruCache::put`]: an infallible insertion that will remove a maximum of 1 element.
26//! * [`CLruCache::put_or_modify`]: a conditional insertion or modification flow similar
27//! to the entry API of [`HashMap`].
28//! * [`CLruCache::try_put_or_modify`]: fallible version of [`CLruCache::put_or_modify`].
29//! * All APIs that allow to retrieve a mutable reference to a value (e.g.: [`CLruCache::get_mut`]).
30//!
31//! The cache requires the keys to be clonable because it will store 2 instances
32//! of each key in different internal data structures. If cloning a key can be
33//! expensive, you might want to consider using an [`std::rc::Rc`] or an [`std::sync::Arc`].
34//!
35//! ## Examples
36//!
37//! ### Using the default [`ZeroWeightScale`]:
38//!
39//! ```rust
40//!
41//! use std::num::NonZeroUsize;
42//! use clru::CLruCache;
43//!
44//! let mut cache = CLruCache::new(NonZeroUsize::new(2).unwrap());
45//! cache.put("apple".to_string(), 3);
46//! cache.put("banana".to_string(), 2);
47//!
48//! assert_eq!(cache.get("apple"), Some(&3));
49//! assert_eq!(cache.get("banana"), Some(&2));
50//! assert!(cache.get("pear").is_none());
51//!
52//! assert_eq!(cache.put("banana".to_string(), 4), Some(2));
53//! assert_eq!(cache.put("pear".to_string(), 5), None);
54//!
55//! assert_eq!(cache.get("pear"), Some(&5));
56//! assert_eq!(cache.get("banana"), Some(&4));
57//! assert!(cache.get("apple").is_none());
58//!
59//! {
60//! let v = cache.get_mut("banana").unwrap();
61//! *v = 6;
62//! }
63//!
64//! assert_eq!(cache.get("banana"), Some(&6));
65//! ```
66//!
67//! ### Using a custom [`WeightScale`] implementation:
68//!
69//! ```rust
70//!
71//! use std::num::NonZeroUsize;
72//! use clru::{CLruCache, CLruCacheConfig, WeightScale};
73//!
74//! struct CustomScale;
75//!
76//! impl WeightScale<String, &str> for CustomScale {
77//! fn weight(&self, _key: &String, value: &&str) -> usize {
78//! value.len()
79//! }
80//! }
81//!
82//! let mut cache = CLruCache::with_config(
83//! CLruCacheConfig::new(NonZeroUsize::new(6).unwrap()).with_scale(CustomScale),
84//! );
85//!
86//! assert_eq!(cache.put_with_weight("apple".to_string(), "red").unwrap(), None);
87//! assert_eq!(
88//! cache.put_with_weight("apple".to_string(), "green").unwrap(),
89//! Some("red")
90//! );
91//!
92//! assert_eq!(cache.len(), 1);
93//! assert_eq!(cache.get("apple"), Some(&"green"));
94//! ```
95
96#![deny(missing_docs)]
97#![deny(unsafe_code)]
98#![deny(warnings)]
99
100mod config;
101mod list;
102mod weight;
103
104pub use crate::config::*;
105use crate::list::{FixedSizeList, FixedSizeListIter, FixedSizeListIterMut};
106pub use crate::weight::*;
107
108use std::borrow::Borrow;
109use std::collections::hash_map::Entry;
110use std::collections::hash_map::RandomState;
111use std::collections::HashMap;
112use std::hash::{BuildHasher, Hash};
113use std::iter::FromIterator;
114use std::num::NonZeroUsize;
115
116#[derive(Debug)]
117struct CLruNode<K, V> {
118 key: K,
119 value: V,
120}
121
122/// A weighted LRU cache with mostly¹ constant time operations.
123///
124/// Each key-value pair in the cache can have a weight that is retrieved
125/// using the provided [`WeightScale`] implementation. The default scale is
126/// [`ZeroWeightScale`] and always return 0. The number of elements that
127/// can be stored in the cache is conditioned by the sum of [`CLruCache::len`]
128/// and [`CLruCache::weight`]:
129///
130/// [`CLruCache::len`] + [`CLruCache::weight`] <= [`CLruCache::capacity`]
131///
132/// Using the default [`ZeroWeightScale`] scale unlocks some useful APIs
133/// that can currently only be implemented for this scale. The most interesting
134/// ones are probably:
135///
136/// * [`CLruCache::put`]
137/// * [`CLruCache::put_or_modify`]
138/// * [`CLruCache::try_put_or_modify`]
139///
140/// But more generally, using [`ZeroWeightScale`] unlocks all methods that return
141/// a mutable reference to the value of an element.
142/// This is because modifying the value of an element can lead to a modification
143/// of its weight and therefore would put the cache into an incoherent state.
144/// For the same reason, it is a logic error for a value to change weight while
145/// being stored in the cache.
146///
147/// The cache requires the keys to be clonable because it will store 2 instances
148/// of each key in different internal data structures. If cloning a key can be
149/// expensive, you might want to consider using an `Rc` or an `Arc`.
150///
151/// Note 1: See [`CLruCache::put_with_weight`]
152#[derive(Debug)]
153pub struct CLruCache<K, V, S = RandomState, W: WeightScale<K, V> = ZeroWeightScale> {
154 lookup: HashMap<K, usize, S>,
155 storage: FixedSizeList<CLruNode<K, V>>,
156 scale: W,
157 weight: usize,
158}
159
160impl<K: Eq + Hash, V> CLruCache<K, V> {
161 /// Creates a new LRU cache that holds at most `capacity` elements.
162 pub fn new(capacity: NonZeroUsize) -> Self {
163 Self {
164 lookup: HashMap::new(),
165 storage: FixedSizeList::new(capacity.get()),
166 scale: ZeroWeightScale,
167 weight: 0,
168 }
169 }
170
171 /// Creates a new LRU cache that holds at most `capacity` elements
172 /// and pre-allocates memory in order to hold at least `reserve` elements
173 /// without reallocating.
174 pub fn with_memory(capacity: NonZeroUsize, mut reserve: usize) -> Self {
175 if reserve > capacity.get() {
176 reserve = capacity.get();
177 }
178 Self {
179 lookup: HashMap::with_capacity(reserve),
180 storage: FixedSizeList::with_memory(capacity.get(), reserve),
181 scale: ZeroWeightScale,
182 weight: 0,
183 }
184 }
185}
186
187impl<K: Eq + Hash, V, S: BuildHasher> CLruCache<K, V, S> {
188 /// Creates a new LRU cache that holds at most `capacity` elements
189 /// and uses the provided hash builder to hash keys.
190 pub fn with_hasher(capacity: NonZeroUsize, hash_builder: S) -> CLruCache<K, V, S> {
191 Self {
192 lookup: HashMap::with_hasher(hash_builder),
193 storage: FixedSizeList::new(capacity.get()),
194 scale: ZeroWeightScale,
195 weight: 0,
196 }
197 }
198}
199
200impl<K: Eq + Hash, V, W: WeightScale<K, V>> CLruCache<K, V, RandomState, W> {
201 /// Creates a new LRU cache that holds at most `capacity` elements
202 /// and uses the provided scale to retrieve value's weight.
203 pub fn with_scale(capacity: NonZeroUsize, scale: W) -> CLruCache<K, V, RandomState, W> {
204 Self {
205 lookup: HashMap::with_hasher(hash_builder:RandomState::default()),
206 storage: FixedSizeList::new(capacity.get()),
207 scale,
208 weight: 0,
209 }
210 }
211}
212
213impl<K: Clone + Eq + Hash, V, S: BuildHasher, W: WeightScale<K, V>> CLruCache<K, V, S, W> {
214 /// Creates a new LRU cache using the provided configuration.
215 pub fn with_config(config: CLruCacheConfig<K, V, S, W>) -> Self {
216 let CLruCacheConfig {
217 capacity,
218 hash_builder,
219 reserve,
220 scale,
221 ..
222 } = config;
223 Self {
224 lookup: HashMap::with_hasher(hash_builder),
225 storage: if let Some(reserve) = reserve {
226 FixedSizeList::with_memory(capacity.get(), reserve)
227 } else {
228 FixedSizeList::new(capacity.get())
229 },
230 scale,
231 weight: 0,
232 }
233 }
234
235 /// Returns the number of key-value pairs that are currently in the cache.
236 #[inline]
237 pub fn len(&self) -> usize {
238 debug_assert_eq!(self.lookup.len(), self.storage.len());
239 self.storage.len()
240 }
241
242 /// Returns the capacity of the cache. It serves as a limit for
243 /// * the number of elements that the cache can hold.
244 /// * the total weight of the elements in the cache.
245 #[inline]
246 pub fn capacity(&self) -> usize {
247 self.storage.capacity()
248 }
249
250 /// Returns the total weight of the elements in the cache.
251 #[inline]
252 pub fn weight(&self) -> usize {
253 self.weight
254 }
255
256 /// Returns a bool indicating whether the cache is empty or not.
257 #[inline]
258 pub fn is_empty(&self) -> bool {
259 debug_assert_eq!(self.lookup.is_empty(), self.storage.is_empty());
260 self.storage.is_empty()
261 }
262
263 /// Returns a bool indicating whether the cache is full or not.
264 #[inline]
265 pub fn is_full(&self) -> bool {
266 self.len() + self.weight() == self.capacity()
267 }
268
269 /// Returns the value corresponding to the most recently used item or `None` if the cache is empty.
270 /// Like `peek`, `front` does not update the LRU list so the item's position will be unchanged.
271 pub fn front(&self) -> Option<(&K, &V)> {
272 self.storage
273 .front()
274 .map(|CLruNode { key, value }| (key, value))
275 }
276
277 /// Returns the value corresponding to the least recently used item or `None` if the cache is empty.
278 /// Like `peek`, `back` does not update the LRU list so the item's position will be unchanged.
279 pub fn back(&self) -> Option<(&K, &V)> {
280 self.storage
281 .back()
282 .map(|CLruNode { key, value }| (key, value))
283 }
284
285 /// Puts a key-value pair into cache taking it's weight into account.
286 /// If the weight of the new element is greater than what the cache can hold,
287 /// it returns the provided key-value pair as an error.
288 /// Otherwise, it removes enough elements for the new element to be inserted,
289 /// thus making it a non constant time operation.
290 /// If the key already exists in the cache, then it updates the key's value and returns the old value.
291 /// Otherwise, `None` is returned.
292 pub fn put_with_weight(&mut self, key: K, value: V) -> Result<Option<V>, (K, V)> {
293 let weight = self.scale.weight(&key, &value);
294 if weight >= self.capacity() {
295 return Err((key, value));
296 }
297 match self.lookup.entry(key) {
298 Entry::Occupied(mut occ) => {
299 // TODO: store keys in the cache itself for reuse.
300 let mut keys = Vec::new();
301 let old = self.storage.remove(*occ.get()).unwrap();
302 self.weight -= self.scale.weight(&old.key, &old.value);
303 while self.storage.len() + self.weight + weight >= self.storage.capacity() {
304 let node = self.storage.pop_back().unwrap();
305 self.weight -= self.scale.weight(&node.key, &node.value);
306 keys.push(node.key);
307 }
308 // It's fine to unwrap here because:
309 // * the cache capacity is non zero
310 // * the cache cannot be full
311 let (idx, _) = self
312 .storage
313 .push_front(CLruNode {
314 key: occ.key().clone(),
315 value,
316 })
317 .unwrap();
318 occ.insert(idx);
319 self.weight += weight;
320 for key in keys.drain(..) {
321 self.lookup.remove(&key);
322 }
323 Ok(Some(old.value))
324 }
325 Entry::Vacant(vac) => {
326 let mut keys = Vec::new();
327 while self.storage.len() + self.weight + weight >= self.storage.capacity() {
328 let node = self.storage.pop_back().unwrap();
329 self.weight -= self.scale.weight(&node.key, &node.value);
330 keys.push(node.key);
331 }
332 // It's fine to unwrap here because:
333 // * the cache capacity is non zero
334 // * the cache cannot be full
335 let (idx, _) = self
336 .storage
337 .push_front(CLruNode {
338 key: vac.key().clone(),
339 value,
340 })
341 .unwrap();
342 vac.insert(idx);
343 self.weight += weight;
344 for key in keys.drain(..) {
345 self.lookup.remove(&key);
346 }
347 Ok(None)
348 }
349 }
350 }
351
352 /// Returns a reference to the value of the key in the cache or `None` if it is not present in the cache.
353 /// Moves the key to the head of the LRU list if it exists.
354 pub fn get<Q>(&mut self, key: &Q) -> Option<&V>
355 where
356 K: Borrow<Q>,
357 Q: Hash + Eq + ?Sized,
358 {
359 let idx = *self.lookup.get(key)?;
360 self.storage.move_front(idx).map(|node| &node.value)
361 }
362
363 /// Removes and returns the value corresponding to the key from the cache or `None` if it does not exist.
364 pub fn pop<Q>(&mut self, key: &Q) -> Option<V>
365 where
366 K: Borrow<Q>,
367 Q: Hash + Eq + ?Sized,
368 {
369 let idx = self.lookup.remove(key)?;
370 self.storage.remove(idx).map(|CLruNode { key, value, .. }| {
371 self.weight -= self.scale.weight(&key, &value);
372 value
373 })
374 }
375
376 /// Removes and returns the key and value corresponding to the most recently used item or `None` if the cache is empty.
377 pub fn pop_front(&mut self) -> Option<(K, V)> {
378 if let Some(CLruNode { key, value }) = self.storage.pop_front() {
379 self.lookup.remove(&key).unwrap();
380 self.weight -= self.scale.weight(&key, &value);
381 Some((key, value))
382 } else {
383 None
384 }
385 }
386
387 /// Removes and returns the key and value corresponding to the least recently used item or `None` if the cache is empty.
388 pub fn pop_back(&mut self) -> Option<(K, V)> {
389 if let Some(CLruNode { key, value }) = self.storage.pop_back() {
390 self.lookup.remove(&key).unwrap();
391 self.weight -= self.scale.weight(&key, &value);
392 Some((key, value))
393 } else {
394 None
395 }
396 }
397
398 /// Returns a reference to the value corresponding to the key in the cache or `None` if it is not present in the cache.
399 /// Unlike `get`, `peek` does not update the LRU list so the key's position will be unchanged.
400 pub fn peek<Q>(&self, key: &Q) -> Option<&V>
401 where
402 K: Borrow<Q>,
403 Q: Hash + Eq + ?Sized,
404 {
405 let idx = *self.lookup.get(key)?;
406 self.storage.get(idx).map(|node| &node.value)
407 }
408
409 /// Returns a bool indicating whether the given key is in the cache.
410 /// Like `peek`, `contains` does not update the LRU list so the key's position will be unchanged.
411 pub fn contains<Q>(&self, key: &Q) -> bool
412 where
413 K: Borrow<Q>,
414 Q: Hash + Eq + ?Sized,
415 {
416 self.peek(key).is_some()
417 }
418
419 /// Clears the contents of the cache.
420 #[inline]
421 pub fn clear(&mut self) {
422 self.lookup.clear();
423 self.storage.clear();
424 self.weight = 0;
425 }
426
427 /// Resizes the cache.
428 /// If the new capacity is smaller than the size of the current cache any entries past the new capacity are discarded.
429 pub fn resize(&mut self, capacity: NonZeroUsize) {
430 while capacity.get() < self.storage.len() + self.weight() {
431 if let Some(CLruNode { key, value }) = self.storage.pop_back() {
432 self.lookup.remove(&key).unwrap();
433 self.weight -= self.scale.weight(&key, &value);
434 }
435 }
436 self.storage.resize(capacity.get());
437 for i in 0..self.len() {
438 let data = self.storage.get(i).unwrap();
439 *self.lookup.get_mut(&data.key).unwrap() = i;
440 }
441 }
442
443 /// Retains only the elements specified by the predicate.
444 /// In other words, remove all pairs `(k, v)` such that `f(&k, &v)` returns `false`.
445 pub fn retain<F>(&mut self, mut f: F)
446 where
447 F: FnMut(&K, &V) -> bool,
448 {
449 self.storage.retain(
450 #[inline]
451 |CLruNode { ref key, ref value }| {
452 if f(key, value) {
453 true
454 } else {
455 self.lookup.remove(key).unwrap();
456 false
457 }
458 },
459 )
460 }
461}
462
463impl<K, V, S, W: WeightScale<K, V>> CLruCache<K, V, S, W> {
464 /// Returns an iterator visiting all entries in order.
465 /// The iterator element type is `(&'a K, &'a V)`.
466 pub fn iter(&self) -> CLruCacheIter<'_, K, V> {
467 CLruCacheIter {
468 iter: self.storage.iter(),
469 }
470 }
471}
472
473impl<K: Clone + Eq + Hash, V, S: BuildHasher> CLruCache<K, V, S> {
474 /// Puts a key-value pair into cache.
475 /// If the key already exists in the cache, then it updates the key's value and returns the old value.
476 /// Otherwise, `None` is returned.
477 pub fn put(&mut self, key: K, value: V) -> Option<V> {
478 match self.lookup.entry(key) {
479 Entry::Occupied(occ) => {
480 // It's fine to unwrap here because:
481 // * the entry already exists
482 let node = self.storage.move_front(*occ.get()).unwrap();
483 Some(std::mem::replace(&mut node.value, value))
484 }
485 Entry::Vacant(vac) => {
486 let key = vac.key().clone();
487 if self.storage.is_full() {
488 let idx = self.storage.back_idx();
489 // It's fine to unwrap here because:
490 // * the cache capacity is non zero
491 // * the cache is full
492 let node = self.storage.move_front(idx).unwrap();
493 let obsolete_key = std::mem::replace(node, CLruNode { key, value }).key;
494 vac.insert(idx);
495 self.lookup.remove(&obsolete_key);
496 } else {
497 // It's fine to unwrap here because:
498 // * the cache capacity is non zero
499 // * the cache is not full
500 let (idx, _) = self.storage.push_front(CLruNode { key, value }).unwrap();
501 vac.insert(idx);
502 }
503 None
504 }
505 }
506 }
507
508 /// Puts a new key-value pair or modify an already existing value.
509 /// If the key already exists in the cache, then `modify_op` supplied function is called.
510 /// Otherwise, `put_op` supplied function is called.
511 /// Returns a mutable reference to the value.
512 ///
513 /// The additional `data` argument can be used to pass extra information
514 /// to the supplied functions. This can useful when both functions need
515 /// to access the same variable.
516 pub fn put_or_modify<T, P: FnMut(&K, T) -> V, M: FnMut(&K, &mut V, T)>(
517 &mut self,
518 key: K,
519 mut put_op: P,
520 mut modify_op: M,
521 data: T,
522 ) -> &mut V {
523 match self.lookup.entry(key) {
524 Entry::Occupied(occ) => {
525 // It's fine to unwrap here because:
526 // * the entry already exists
527 let node = self.storage.move_front(*occ.get()).unwrap();
528 modify_op(&node.key, &mut node.value, data);
529 &mut node.value
530 }
531 Entry::Vacant(vac) => {
532 let key = vac.key().clone();
533 let value = put_op(&key, data);
534 if self.storage.is_full() {
535 let index = self.storage.back_idx();
536 // It's fine to unwrap here because:
537 // * the cache capacity is non zero
538 // * the cache is full
539 let node = self.storage.move_front(index).unwrap();
540 let obsolete_key = std::mem::replace(node, CLruNode { key, value }).key;
541 vac.insert(index);
542 self.lookup.remove(&obsolete_key);
543 &mut node.value
544 } else {
545 // It's fine to unwrap here because:
546 // * the cache capacity is non zero
547 // * the cache cannot be full
548 let (idx, node) = self.storage.push_front(CLruNode { key, value }).unwrap();
549 vac.insert(idx);
550 &mut node.value
551 }
552 }
553 }
554 }
555
556 /// Puts a new key-value pair or modify an already existing value.
557 /// If the key already exists in the cache, then `modify_op` supplied function is called.
558 /// Otherwise, `put_op` supplied function is called.
559 /// Returns a mutable reference to the value or an error.
560 ///
561 /// The additional `data` argument can be used to pass extra information
562 /// to the supplied functions. This can useful when both functions need
563 /// to access the same variable.
564 ///
565 /// This is the fallible version of [`CLruCache::put_or_modify`].
566 pub fn try_put_or_modify<
567 T,
568 E,
569 P: FnMut(&K, T) -> Result<V, E>,
570 M: FnMut(&K, &mut V, T) -> Result<(), E>,
571 >(
572 &mut self,
573 key: K,
574 mut put_op: P,
575 mut modify_op: M,
576 data: T,
577 ) -> Result<&mut V, E> {
578 match self.lookup.entry(key) {
579 Entry::Occupied(occ) => {
580 // It's fine to unwrap here because:
581 // * the entry already exists
582 let node = self.storage.move_front(*occ.get()).unwrap();
583 match modify_op(&node.key, &mut node.value, data) {
584 Ok(()) => Ok(&mut node.value),
585 Err(err) => Err(err),
586 }
587 }
588 Entry::Vacant(vac) => {
589 let value = match put_op(vac.key(), data) {
590 Ok(value) => value,
591 Err(err) => return Err(err),
592 };
593 let key = vac.key().clone();
594 if self.storage.is_full() {
595 let idx = self.storage.back_idx();
596 // It's fine to unwrap here because:
597 // * the cache capacity is non zero
598 // * the cache is full
599 let node = self.storage.move_front(idx).unwrap();
600 let obsolete_key = std::mem::replace(node, CLruNode { key, value }).key;
601 vac.insert(idx);
602 self.lookup.remove(&obsolete_key);
603 Ok(&mut node.value)
604 } else {
605 // It's fine to unwrap here because:
606 // * the cache capacity is non zero
607 // * the cache cannot be full
608 let (idx, node) = self.storage.push_front(CLruNode { key, value }).unwrap();
609 vac.insert(idx);
610 Ok(&mut node.value)
611 }
612 }
613 }
614 }
615
616 /// Returns the value corresponding to the most recently used item or `None` if the cache is empty.
617 /// Like `peek`, `font` does not update the LRU list so the item's position will be unchanged.
618 pub fn front_mut(&mut self) -> Option<(&K, &mut V)> {
619 self.storage
620 .front_mut()
621 .map(|CLruNode { key, value }| (&*key, value))
622 }
623
624 /// Returns the value corresponding to the least recently used item or `None` if the cache is empty.
625 /// Like `peek`, `back` does not update the LRU list so the item's position will be unchanged.
626 pub fn back_mut(&mut self) -> Option<(&K, &mut V)> {
627 self.storage
628 .back_mut()
629 .map(|CLruNode { key, value }| (&*key, value))
630 }
631
632 /// Returns a mutable reference to the value of the key in the cache or `None` if it is not present in the cache.
633 /// Moves the key to the head of the LRU list if it exists.
634 pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
635 where
636 K: Borrow<Q>,
637 Q: Hash + Eq + ?Sized,
638 {
639 let idx = *self.lookup.get(key)?;
640 self.storage.move_front(idx).map(|node| &mut node.value)
641 }
642
643 /// Returns a mutable reference to the value corresponding to the key in the cache or `None` if it is not present in the cache.
644 /// Unlike `get_mut`, `peek_mut` does not update the LRU list so the key's position will be unchanged.
645 pub fn peek_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
646 where
647 K: Borrow<Q>,
648 Q: Hash + Eq + ?Sized,
649 {
650 let idx = *self.lookup.get(key)?;
651 self.storage.get_mut(idx).map(|node| &mut node.value)
652 }
653
654 /// Retains only the elements specified by the predicate.
655 /// In other words, remove all pairs `(k, v)` such that `f(&k, &mut v)` returns `false`.
656 pub fn retain_mut<F>(&mut self, mut f: F)
657 where
658 F: FnMut(&K, &mut V) -> bool,
659 {
660 self.storage.retain_mut(
661 #[inline]
662 |CLruNode {
663 ref key,
664 ref mut value,
665 }| {
666 if f(key, value) {
667 true
668 } else {
669 self.lookup.remove(key).unwrap();
670 false
671 }
672 },
673 )
674 }
675}
676
677impl<K, V, S> CLruCache<K, V, S> {
678 /// Returns an iterator visiting all entries in order, giving a mutable reference on V.
679 /// The iterator element type is `(&'a K, &'a mut V)`.
680 pub fn iter_mut(&mut self) -> CLruCacheIterMut<'_, K, V> {
681 CLruCacheIterMut {
682 iter: self.storage.iter_mut(),
683 }
684 }
685}
686
687/// An iterator over the entries of a `CLruCache`.
688///
689/// This `struct` is created by the [`iter`] method on [`CLruCache`][`CLruCache`].
690/// See its documentation for more.
691///
692/// [`iter`]: struct.CLruCache.html#method.iter
693/// [`CLruCache`]: struct.CLruCache.html
694#[derive(Clone, Debug)]
695pub struct CLruCacheIter<'a, K, V> {
696 iter: FixedSizeListIter<'a, CLruNode<K, V>>,
697}
698
699impl<'a, K, V> Iterator for CLruCacheIter<'a, K, V> {
700 type Item = (&'a K, &'a V);
701
702 fn next(&mut self) -> Option<Self::Item> {
703 self.iter
704 .next()
705 .map(|(_, CLruNode { key: &K, value: &V })| (key.borrow(), value))
706 }
707
708 fn size_hint(&self) -> (usize, Option<usize>) {
709 self.iter.size_hint()
710 }
711}
712
713impl<'a, K, V> DoubleEndedIterator for CLruCacheIter<'a, K, V> {
714 fn next_back(&mut self) -> Option<Self::Item> {
715 self.iter
716 .next_back()
717 .map(|(_, CLruNode { key: &K, value: &V })| (key.borrow(), value))
718 }
719}
720
721impl<'a, K, V> ExactSizeIterator for CLruCacheIter<'a, K, V> {
722 fn len(&self) -> usize {
723 self.iter.len()
724 }
725}
726
727impl<'a, K, V, S, W: WeightScale<K, V>> IntoIterator for &'a CLruCache<K, V, S, W> {
728 type Item = (&'a K, &'a V);
729 type IntoIter = CLruCacheIter<'a, K, V>;
730
731 #[inline]
732 fn into_iter(self) -> CLruCacheIter<'a, K, V> {
733 self.iter()
734 }
735}
736
737/// An iterator over mutables entries of a `CLruCache`.
738///
739/// This `struct` is created by the [`iter_mut`] method on [`CLruCache`][`CLruCache`].
740/// See its documentation for more.
741///
742/// [`iter_mut`]: struct.CLruCache.html#method.iter_mut
743/// [`CLruCache`]: struct.CLruCache.html
744pub struct CLruCacheIterMut<'a, K, V> {
745 iter: FixedSizeListIterMut<'a, CLruNode<K, V>>,
746}
747
748impl<'a, K, V> Iterator for CLruCacheIterMut<'a, K, V> {
749 type Item = (&'a K, &'a mut V);
750
751 fn next(&mut self) -> Option<Self::Item> {
752 self.iter
753 .next()
754 .map(|(_, CLruNode { key: &mut K, value: &mut V })| (&*key, value))
755 }
756
757 fn size_hint(&self) -> (usize, Option<usize>) {
758 self.iter.size_hint()
759 }
760}
761
762impl<'a, K, V> DoubleEndedIterator for CLruCacheIterMut<'a, K, V> {
763 fn next_back(&mut self) -> Option<Self::Item> {
764 self.iter
765 .next_back()
766 .map(|(_, CLruNode { key: &mut K, value: &mut V })| (&*key, value))
767 }
768}
769
770impl<'a, K, V> ExactSizeIterator for CLruCacheIterMut<'a, K, V> {
771 fn len(&self) -> usize {
772 self.iter.len()
773 }
774}
775
776impl<'a, K, V, S> IntoIterator for &'a mut CLruCache<K, V, S> {
777 type Item = (&'a K, &'a mut V);
778 type IntoIter = CLruCacheIterMut<'a, K, V>;
779
780 #[inline]
781 fn into_iter(self) -> CLruCacheIterMut<'a, K, V> {
782 self.iter_mut()
783 }
784}
785
786/// An owning iterator over the elements of a `CLruCache`.
787///
788/// This `struct` is created by the [`into_iter`] method on [`CLruCache`]
789/// (provided by the `IntoIterator` trait). See its documentation for more.
790///
791/// [`into_iter`]: struct.CLruCache.html#method.into_iter
792pub struct CLruCacheIntoIter<K, V, S, W: WeightScale<K, V>> {
793 cache: CLruCache<K, V, S, W>,
794}
795
796impl<K: Clone + Eq + Hash, V, S: BuildHasher, W: WeightScale<K, V>> Iterator
797 for CLruCacheIntoIter<K, V, S, W>
798{
799 type Item = (K, V);
800
801 #[inline]
802 fn next(&mut self) -> Option<(K, V)> {
803 self.cache.pop_front()
804 }
805
806 #[inline]
807 fn size_hint(&self) -> (usize, Option<usize>) {
808 (self.cache.len(), Some(self.cache.len()))
809 }
810}
811
812impl<K: Clone + Eq + Hash, V, S: BuildHasher, W: WeightScale<K, V>> DoubleEndedIterator
813 for CLruCacheIntoIter<K, V, S, W>
814{
815 fn next_back(&mut self) -> Option<Self::Item> {
816 self.cache.pop_back()
817 }
818}
819
820impl<K: Clone + Eq + Hash, V, S: BuildHasher, W: WeightScale<K, V>> ExactSizeIterator
821 for CLruCacheIntoIter<K, V, S, W>
822{
823 fn len(&self) -> usize {
824 self.size_hint().0
825 }
826}
827
828impl<K: Clone + Eq + Hash, V, S: BuildHasher, W: WeightScale<K, V>> IntoIterator
829 for CLruCache<K, V, S, W>
830{
831 type Item = (K, V);
832 type IntoIter = CLruCacheIntoIter<K, V, S, W>;
833
834 /// Consumes the cache into an iterator yielding elements by value.
835 #[inline]
836 fn into_iter(self) -> CLruCacheIntoIter<K, V, S, W> {
837 CLruCacheIntoIter { cache: self }
838 }
839}
840
841impl<K: Clone + Eq + Hash, V, S: BuildHasher + Default> FromIterator<(K, V)>
842 for CLruCache<K, V, S>
843{
844 fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
845 let cap: NonZero = NonZeroUsize::new(usize::MAX).unwrap();
846 let mut cache: CLruCache = CLruCache::with_hasher(capacity:cap, S::default());
847
848 for (k: K, v: V) in iter {
849 cache.put(key:k, value:v);
850 }
851
852 cache.resize(
853 capacity:NonZeroUsize::new(cache.len()).unwrap_or_else(|| NonZeroUsize::new(1).unwrap()),
854 );
855
856 cache
857 }
858}
859
860impl<K: Clone + Eq + Hash, V, S: BuildHasher> Extend<(K, V)> for CLruCache<K, V, S> {
861 fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
862 for (k: K, v: V) in iter {
863 self.put(key:k, value:v);
864 }
865 }
866}
867
868#[cfg(test)]
869#[allow(clippy::bool_assert_comparison)]
870mod tests {
871 use super::*;
872
873 #[allow(unsafe_code)]
874 const ONE: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(1) };
875 #[allow(unsafe_code)]
876 const TWO: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(2) };
877 #[allow(unsafe_code)]
878 const THREE: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(3) };
879 #[allow(unsafe_code)]
880 const FOUR: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(4) };
881 #[allow(unsafe_code)]
882 const FIVE: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(5) };
883 #[allow(unsafe_code)]
884 const SIX: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(6) };
885 #[allow(unsafe_code)]
886 const HEIGHT: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(8) };
887 #[allow(unsafe_code)]
888 const MANY: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(200) };
889
890 #[test]
891 fn test_insert_and_get() {
892 let mut cache = CLruCache::new(TWO);
893 assert!(cache.is_empty());
894
895 assert_eq!(cache.put("apple", "red"), None);
896 assert_eq!(cache.put("banana", "yellow"), None);
897
898 assert_eq!(cache.capacity(), 2);
899 assert_eq!(cache.len(), 2);
900 assert!(!cache.is_empty());
901 assert!(cache.is_full());
902 assert_eq!(cache.get(&"apple"), Some(&"red"));
903 assert_eq!(cache.get(&"banana"), Some(&"yellow"));
904 }
905
906 #[test]
907 fn test_insert_and_get_mut() {
908 let mut cache = CLruCache::new(TWO);
909
910 cache.put("apple", "red");
911 cache.put("banana", "yellow");
912
913 assert_eq!(cache.capacity(), 2);
914 assert_eq!(cache.len(), 2);
915 assert!(!cache.is_empty());
916 assert!(cache.is_full());
917 assert_eq!(cache.get_mut(&"apple"), Some(&mut "red"));
918 assert_eq!(cache.get_mut(&"banana"), Some(&mut "yellow"));
919 }
920
921 #[test]
922 fn test_get_mut_and_update() {
923 let mut cache = CLruCache::new(TWO);
924
925 cache.put("apple", 1);
926 cache.put("banana", 3);
927
928 {
929 let v = cache.get_mut(&"apple").unwrap();
930 *v = 4;
931 }
932
933 assert_eq!(cache.capacity(), 2);
934 assert_eq!(cache.len(), 2);
935 assert!(!cache.is_empty());
936 assert!(cache.is_full());
937 assert_eq!(cache.get_mut(&"apple"), Some(&mut 4));
938 assert_eq!(cache.get_mut(&"banana"), Some(&mut 3));
939 }
940
941 #[test]
942 fn test_insert_update() {
943 let mut cache = CLruCache::new(ONE);
944
945 assert_eq!(cache.put("apple", "red"), None);
946 assert_eq!(cache.put("apple", "green"), Some("red"));
947
948 assert_eq!(cache.len(), 1);
949 assert_eq!(cache.get(&"apple"), Some(&"green"));
950 }
951
952 #[test]
953 fn test_insert_removes_oldest() {
954 let mut cache = CLruCache::new(TWO);
955
956 assert_eq!(cache.put("apple", "red"), None);
957 assert_eq!(cache.put("banana", "yellow"), None);
958 assert_eq!(cache.put("pear", "green"), None);
959
960 assert!(cache.get(&"apple").is_none());
961 assert_eq!(cache.get(&"banana"), Some(&"yellow"));
962 assert_eq!(cache.get(&"pear"), Some(&"green"));
963
964 // Even though we inserted "apple" into the cache earlier it has since been removed from
965 // the cache so there is no current value for `insert` to return.
966 assert_eq!(cache.put("apple", "green"), None);
967 assert_eq!(cache.put("tomato", "red"), None);
968
969 assert!(cache.get(&"pear").is_none());
970 assert_eq!(cache.get(&"apple"), Some(&"green"));
971 assert_eq!(cache.get(&"tomato"), Some(&"red"));
972 }
973
974 #[test]
975 fn test_peek() {
976 let mut cache = CLruCache::new(TWO);
977
978 cache.put("apple", "red");
979 cache.put("banana", "yellow");
980
981 assert_eq!(cache.peek(&"banana"), Some(&"yellow"));
982 assert_eq!(cache.peek(&"apple"), Some(&"red"));
983
984 cache.put("pear", "green");
985
986 assert!(cache.peek(&"apple").is_none());
987 assert_eq!(cache.peek(&"banana"), Some(&"yellow"));
988 assert_eq!(cache.peek(&"pear"), Some(&"green"));
989 }
990
991 #[test]
992 fn test_peek_mut() {
993 let mut cache = CLruCache::new(TWO);
994
995 cache.put("apple", "red");
996 cache.put("banana", "yellow");
997
998 assert_eq!(cache.peek_mut(&"banana"), Some(&mut "yellow"));
999 assert_eq!(cache.peek_mut(&"apple"), Some(&mut "red"));
1000 assert!(cache.peek_mut(&"pear").is_none());
1001
1002 cache.put("pear", "green");
1003
1004 assert!(cache.peek_mut(&"apple").is_none());
1005 assert_eq!(cache.peek_mut(&"banana"), Some(&mut "yellow"));
1006 assert_eq!(cache.peek_mut(&"pear"), Some(&mut "green"));
1007
1008 {
1009 let v = cache.peek_mut(&"banana").unwrap();
1010 *v = "green";
1011 }
1012
1013 assert_eq!(cache.peek_mut(&"banana"), Some(&mut "green"));
1014 }
1015
1016 #[test]
1017 fn test_contains() {
1018 let mut cache = CLruCache::new(TWO);
1019
1020 cache.put("apple", "red");
1021 cache.put("banana", "yellow");
1022 cache.put("pear", "green");
1023
1024 assert!(!cache.contains(&"apple"));
1025 assert!(cache.contains(&"banana"));
1026 assert!(cache.contains(&"pear"));
1027 }
1028
1029 #[test]
1030 fn test_pop() {
1031 let mut cache = CLruCache::new(TWO);
1032
1033 cache.put("apple", "red");
1034 cache.put("banana", "yellow");
1035
1036 assert_eq!(cache.len(), 2);
1037 assert_eq!(cache.get(&"apple"), Some(&"red"));
1038 assert_eq!(cache.get(&"banana"), Some(&"yellow"));
1039
1040 let popped = cache.pop(&"apple");
1041 assert!(popped.is_some());
1042 assert_eq!(popped.unwrap(), "red");
1043 assert_eq!(cache.len(), 1);
1044 assert!(cache.get(&"apple").is_none());
1045 assert_eq!(cache.get(&"banana"), Some(&"yellow"));
1046 }
1047
1048 #[test]
1049 fn test_pop_front() {
1050 let mut cache = CLruCache::new(MANY);
1051
1052 for i in 0..75 {
1053 cache.put(i, "A");
1054 }
1055 for i in 0..75 {
1056 cache.put(i + 100, "B");
1057 }
1058 for i in 0..75 {
1059 cache.put(i + 200, "C");
1060 }
1061 assert_eq!(cache.len(), 200);
1062
1063 for i in 0..75 {
1064 assert_eq!(cache.get(&(74 - i + 100)), Some(&"B"));
1065 }
1066 assert_eq!(cache.get(&25), Some(&"A"));
1067
1068 assert_eq!(cache.pop_front(), Some((25, "A")));
1069 for i in 0..75 {
1070 assert_eq!(cache.pop_front(), Some((i + 100, "B")));
1071 }
1072 for i in 0..75 {
1073 assert_eq!(cache.pop_front(), Some((74 - i + 200, "C")));
1074 }
1075 for i in 0..49 {
1076 assert_eq!(cache.pop_front(), Some((74 - i, "A")));
1077 }
1078 for _ in 0..50 {
1079 assert_eq!(cache.pop_front(), None);
1080 }
1081 }
1082
1083 #[test]
1084 fn test_pop_back() {
1085 let mut cache = CLruCache::new(MANY);
1086
1087 for i in 0..75 {
1088 cache.put(i, "A");
1089 }
1090 for i in 0..75 {
1091 cache.put(i + 100, "B");
1092 }
1093 for i in 0..75 {
1094 cache.put(i + 200, "C");
1095 }
1096 assert_eq!(cache.len(), 200);
1097
1098 for i in 0..75 {
1099 assert_eq!(cache.get(&(74 - i + 100)), Some(&"B"));
1100 }
1101 assert_eq!(cache.get(&25), Some(&"A"));
1102
1103 for i in 26..75 {
1104 assert_eq!(cache.pop_back(), Some((i, "A")));
1105 }
1106 for i in 0..75 {
1107 assert_eq!(cache.pop_back(), Some((i + 200, "C")));
1108 }
1109 for i in 0..75 {
1110 assert_eq!(cache.pop_back(), Some((74 - i + 100, "B")));
1111 }
1112 assert_eq!(cache.pop_back(), Some((25, "A")));
1113 for _ in 0..50 {
1114 assert_eq!(cache.pop_back(), None);
1115 }
1116 }
1117
1118 #[test]
1119 fn test_clear() {
1120 let mut cache = CLruCache::new(TWO);
1121
1122 cache.put("apple", "red");
1123 cache.put("banana", "yellow");
1124
1125 assert_eq!(cache.len(), 2);
1126 assert_eq!(cache.get(&"apple"), Some(&"red"));
1127 assert_eq!(cache.get(&"banana"), Some(&"yellow"));
1128
1129 cache.clear();
1130 assert_eq!(cache.len(), 0);
1131 }
1132
1133 #[test]
1134 fn test_resize_larger() {
1135 let mut cache = CLruCache::new(TWO);
1136
1137 cache.put(1, "a");
1138 cache.put(2, "b");
1139
1140 cache.resize(THREE);
1141
1142 assert_eq!(cache.len(), 2);
1143 assert_eq!(cache.capacity(), 3);
1144
1145 cache.resize(FOUR);
1146
1147 assert_eq!(cache.len(), 2);
1148 assert_eq!(cache.capacity(), 4);
1149
1150 cache.put(3, "c");
1151 cache.put(4, "d");
1152
1153 assert_eq!(cache.len(), 4);
1154 assert_eq!(cache.capacity(), 4);
1155 assert_eq!(cache.get(&1), Some(&"a"));
1156 assert_eq!(cache.get(&2), Some(&"b"));
1157 assert_eq!(cache.get(&3), Some(&"c"));
1158 assert_eq!(cache.get(&4), Some(&"d"));
1159 }
1160
1161 #[test]
1162 fn test_resize_smaller() {
1163 let mut cache = CLruCache::new(FOUR);
1164
1165 cache.put(1, "a");
1166 cache.put(2, "b");
1167 cache.put(3, "c");
1168 cache.put(4, "d");
1169
1170 cache.resize(TWO);
1171
1172 assert_eq!(cache.len(), 2);
1173 assert_eq!(cache.capacity(), 2);
1174 assert!(cache.get(&1).is_none());
1175 assert!(cache.get(&2).is_none());
1176 assert_eq!(cache.get(&3), Some(&"c"));
1177 assert_eq!(cache.get(&4), Some(&"d"));
1178 }
1179
1180 #[test]
1181 fn test_resize_equal() {
1182 let mut cache = CLruCache::new(FOUR);
1183
1184 cache.put(1, "a");
1185 cache.put(2, "b");
1186 cache.put(3, "c");
1187 cache.put(4, "d");
1188
1189 cache.resize(FOUR);
1190
1191 assert_eq!(cache.len(), 4);
1192 assert_eq!(cache.capacity(), 4);
1193 assert_eq!(cache.get(&1), Some(&"a"));
1194 assert_eq!(cache.get(&2), Some(&"b"));
1195 assert_eq!(cache.get(&3), Some(&"c"));
1196 assert_eq!(cache.get(&4), Some(&"d"));
1197 }
1198
1199 #[test]
1200 fn test_iter_forwards() {
1201 let mut cache = CLruCache::new(THREE);
1202 cache.put("a", 1);
1203 cache.put("b", 2);
1204 cache.put("c", 3);
1205
1206 {
1207 // iter const
1208 let mut iter = cache.iter();
1209 assert_eq!(iter.len(), 3);
1210 assert_eq!(iter.next(), Some((&"c", &3)));
1211
1212 assert_eq!(iter.len(), 2);
1213 assert_eq!(iter.next(), Some((&"b", &2)));
1214
1215 assert_eq!(iter.len(), 1);
1216 assert_eq!(iter.next(), Some((&"a", &1)));
1217
1218 assert_eq!(iter.len(), 0);
1219 assert_eq!(iter.next(), None);
1220 }
1221 {
1222 // iter mut
1223 let mut iter = cache.iter_mut();
1224 assert_eq!(iter.len(), 3);
1225 assert_eq!(iter.next(), Some((&"c", &mut 3)));
1226
1227 assert_eq!(iter.len(), 2);
1228 assert_eq!(iter.next(), Some((&"b", &mut 2)));
1229
1230 assert_eq!(iter.len(), 1);
1231 assert_eq!(iter.next(), Some((&"a", &mut 1)));
1232
1233 assert_eq!(iter.len(), 0);
1234 assert_eq!(iter.next(), None);
1235
1236 let mut vec: Vec<_> = cache.iter_mut().collect();
1237 vec.iter_mut().for_each(|(_, v)| {
1238 **v -= 1;
1239 });
1240 assert_eq!(vec, vec![(&"c", &mut 2), (&"b", &mut 1), (&"a", &mut 0)]);
1241 }
1242 }
1243
1244 #[test]
1245 fn test_iter_backwards() {
1246 let mut cache = CLruCache::new(THREE);
1247 cache.put("a", 1);
1248 cache.put("b", 2);
1249 cache.put("c", 3);
1250
1251 {
1252 // iter const
1253 let mut iter = cache.iter();
1254 assert_eq!(iter.len(), 3);
1255 assert_eq!(iter.next_back(), Some((&"a", &1)));
1256
1257 assert_eq!(iter.len(), 2);
1258 assert_eq!(iter.next_back(), Some((&"b", &2)));
1259
1260 assert_eq!(iter.len(), 1);
1261 assert_eq!(iter.next_back(), Some((&"c", &3)));
1262
1263 assert_eq!(iter.len(), 0);
1264 assert_eq!(iter.next_back(), None);
1265 }
1266
1267 {
1268 // iter mut
1269 let mut iter = cache.iter_mut();
1270 assert_eq!(iter.len(), 3);
1271 assert_eq!(iter.next_back(), Some((&"a", &mut 1)));
1272
1273 assert_eq!(iter.len(), 2);
1274 assert_eq!(iter.next_back(), Some((&"b", &mut 2)));
1275
1276 assert_eq!(iter.len(), 1);
1277 assert_eq!(iter.next_back(), Some((&"c", &mut 3)));
1278
1279 assert_eq!(iter.len(), 0);
1280 assert_eq!(iter.next_back(), None);
1281
1282 let mut vec: Vec<_> = cache.iter_mut().rev().collect();
1283 vec.iter_mut().for_each(|(_, v)| {
1284 **v -= 1;
1285 });
1286 assert_eq!(vec, vec![(&"a", &mut 0), (&"b", &mut 1), (&"c", &mut 2)]);
1287 }
1288 }
1289
1290 #[test]
1291 fn test_iter_forwards_and_backwards() {
1292 let mut cache = CLruCache::new(THREE);
1293 cache.put("a", 1);
1294 cache.put("b", 2);
1295 cache.put("c", 3);
1296
1297 {
1298 // iter const
1299 let mut iter = cache.iter();
1300 assert_eq!(iter.len(), 3);
1301 assert_eq!(iter.next(), Some((&"c", &3)));
1302
1303 assert_eq!(iter.len(), 2);
1304 assert_eq!(iter.next_back(), Some((&"a", &1)));
1305
1306 assert_eq!(iter.len(), 1);
1307 assert_eq!(iter.next(), Some((&"b", &2)));
1308
1309 assert_eq!(iter.len(), 0);
1310 assert_eq!(iter.next_back(), None);
1311 }
1312 {
1313 // iter mut
1314 let mut iter = cache.iter_mut();
1315 assert_eq!(iter.len(), 3);
1316 assert_eq!(iter.next(), Some((&"c", &mut 3)));
1317
1318 assert_eq!(iter.len(), 2);
1319 assert_eq!(iter.next_back(), Some((&"a", &mut 1)));
1320
1321 assert_eq!(iter.len(), 1);
1322 assert_eq!(iter.next(), Some((&"b", &mut 2)));
1323
1324 assert_eq!(iter.len(), 0);
1325 assert_eq!(iter.next_back(), None);
1326 }
1327 }
1328
1329 #[test]
1330 fn test_iter_clone() {
1331 let mut cache = CLruCache::new(THREE);
1332 cache.put("a", 1);
1333 cache.put("b", 2);
1334
1335 let mut iter = cache.iter();
1336 let mut iter_clone = iter.clone();
1337
1338 assert_eq!(iter.len(), 2);
1339 assert_eq!(iter.next(), Some((&"b", &2)));
1340 assert_eq!(iter_clone.len(), 2);
1341 assert_eq!(iter_clone.next(), Some((&"b", &2)));
1342
1343 assert_eq!(iter.len(), 1);
1344 assert_eq!(iter.next(), Some((&"a", &1)));
1345 assert_eq!(iter_clone.len(), 1);
1346 assert_eq!(iter_clone.next(), Some((&"a", &1)));
1347
1348 assert_eq!(iter.len(), 0);
1349 assert_eq!(iter.next(), None);
1350 assert_eq!(iter_clone.len(), 0);
1351 assert_eq!(iter_clone.next(), None);
1352 }
1353
1354 #[test]
1355 fn test_that_pop_actually_detaches_node() {
1356 let mut cache = CLruCache::new(FIVE);
1357
1358 cache.put("a", 1);
1359 cache.put("b", 2);
1360 cache.put("c", 3);
1361 cache.put("d", 4);
1362 cache.put("e", 5);
1363
1364 assert_eq!(cache.pop(&"c"), Some(3));
1365
1366 cache.put("f", 6);
1367
1368 let mut iter = cache.iter();
1369 assert_eq!(iter.next(), Some((&"f", &6)));
1370 assert_eq!(iter.next(), Some((&"e", &5)));
1371 assert_eq!(iter.next(), Some((&"d", &4)));
1372 assert_eq!(iter.next(), Some((&"b", &2)));
1373 assert_eq!(iter.next(), Some((&"a", &1)));
1374 assert!(iter.next().is_none());
1375 }
1376
1377 #[test]
1378 fn test_get_with_borrow() {
1379 let mut cache = CLruCache::new(TWO);
1380
1381 let key = String::from("apple");
1382 cache.put(key, "red");
1383
1384 assert_eq!(cache.get("apple"), Some(&"red"));
1385 }
1386
1387 #[test]
1388 fn test_get_mut_with_borrow() {
1389 let mut cache = CLruCache::new(TWO);
1390
1391 let key = String::from("apple");
1392 cache.put(key, "red");
1393
1394 assert_eq!(cache.get_mut("apple"), Some(&mut "red"));
1395 }
1396
1397 #[test]
1398 #[cfg_attr(miri, ignore)]
1399 fn test_no_memory_leaks() {
1400 use std::sync::atomic::{AtomicUsize, Ordering};
1401
1402 static DROP_COUNT: AtomicUsize = AtomicUsize::new(0);
1403
1404 struct DropCounter;
1405
1406 impl Drop for DropCounter {
1407 fn drop(&mut self) {
1408 DROP_COUNT.fetch_add(1, Ordering::SeqCst);
1409 }
1410 }
1411
1412 let n = 100;
1413 for _ in 0..n {
1414 let mut cache = CLruCache::new(ONE);
1415 for i in 0..n {
1416 cache.put(i, DropCounter {});
1417 }
1418 }
1419 assert_eq!(DROP_COUNT.load(Ordering::SeqCst), n * n);
1420 }
1421
1422 #[test]
1423 fn test_retain() {
1424 let mut cache = CLruCache::new(FIVE);
1425
1426 cache.put("a", 1);
1427 cache.put("b", 2);
1428 cache.put("c", 3);
1429 cache.put("d", 4);
1430 cache.put("e", 5);
1431
1432 assert_eq!(cache.len(), 5);
1433
1434 cache.retain_mut(|k, v| match *k {
1435 "b" | "d" => false,
1436 _ => {
1437 *v += 1;
1438 true
1439 }
1440 });
1441
1442 assert_eq!(cache.len(), 3);
1443
1444 assert_eq!(cache.get("a"), Some(&2));
1445 assert_eq!(cache.get("b"), None);
1446 assert_eq!(cache.get("c"), Some(&4));
1447 assert_eq!(cache.get("d"), None);
1448 assert_eq!(cache.get("e"), Some(&6));
1449
1450 cache.retain(|_, _| true);
1451
1452 assert_eq!(cache.len(), 3);
1453
1454 assert_eq!(cache.get("a"), Some(&2));
1455 assert_eq!(cache.get("b"), None);
1456 assert_eq!(cache.get("c"), Some(&4));
1457 assert_eq!(cache.get("d"), None);
1458 assert_eq!(cache.get("e"), Some(&6));
1459
1460 cache.retain(|_, _| false);
1461
1462 assert_eq!(cache.len(), 0);
1463
1464 assert_eq!(cache.get("a"), None);
1465 assert_eq!(cache.get("b"), None);
1466 assert_eq!(cache.get("c"), None);
1467 assert_eq!(cache.get("d"), None);
1468 assert_eq!(cache.get("e"), None);
1469 }
1470
1471 #[test]
1472 fn test_into_iter() {
1473 let mut cache = CLruCache::new(FIVE);
1474
1475 cache.put("a", 1);
1476 cache.put("b", 2);
1477 cache.put("c", 3);
1478 cache.put("d", 4);
1479 cache.put("e", 5);
1480
1481 let mut vec = Vec::new();
1482 for (k, v) in &cache {
1483 vec.push((k, v));
1484 }
1485 assert_eq!(
1486 vec,
1487 vec![(&"e", &5), (&"d", &4), (&"c", &3), (&"b", &2), (&"a", &1)]
1488 );
1489
1490 let mut vec = Vec::new();
1491 for (k, v) in &mut cache {
1492 *v -= 1;
1493 vec.push((k, v));
1494 }
1495 assert_eq!(
1496 vec,
1497 vec![
1498 (&"e", &mut 4),
1499 (&"d", &mut 3),
1500 (&"c", &mut 2),
1501 (&"b", &mut 1),
1502 (&"a", &mut 0)
1503 ]
1504 );
1505
1506 assert_eq!(
1507 cache.into_iter().collect::<Vec<_>>(),
1508 vec![("e", 4), ("d", 3), ("c", 2), ("b", 1), ("a", 0)]
1509 );
1510 }
1511
1512 #[test]
1513 fn test_put_or_modify() {
1514 let mut cache = CLruCache::new(TWO);
1515
1516 let put = |key: &&str, base: Option<usize>| base.unwrap_or(0) + key.len();
1517
1518 let modify = |key: &&str, value: &mut usize, base: Option<usize>| {
1519 if key.len() == *value {
1520 *value *= 2;
1521 } else {
1522 *value /= 2;
1523 }
1524 *value += base.unwrap_or(0);
1525 };
1526
1527 assert_eq!(cache.put_or_modify("a", put, modify, None), &1);
1528 assert_eq!(cache.len(), 1);
1529
1530 let mut iter = cache.iter();
1531 assert_eq!(iter.next(), Some((&"a", &1)));
1532 assert_eq!(iter.next(), None);
1533
1534 assert_eq!(cache.put_or_modify("b", put, modify, Some(3)), &4);
1535 assert_eq!(cache.len(), 2);
1536
1537 let mut iter = cache.iter();
1538 assert_eq!(iter.next(), Some((&"b", &4)));
1539 assert_eq!(iter.next(), Some((&"a", &1)));
1540 assert_eq!(iter.next(), None);
1541
1542 assert_eq!(cache.put_or_modify("a", put, modify, None), &2);
1543 assert_eq!(cache.len(), 2);
1544
1545 let mut iter = cache.iter();
1546 assert_eq!(iter.next(), Some((&"a", &2)));
1547 assert_eq!(iter.next(), Some((&"b", &4)));
1548 assert_eq!(iter.next(), None);
1549
1550 assert_eq!(cache.put_or_modify("b", put, modify, Some(3)), &5);
1551 assert_eq!(cache.len(), 2);
1552
1553 let mut iter = cache.iter();
1554 assert_eq!(iter.next(), Some((&"b", &5)));
1555 assert_eq!(iter.next(), Some((&"a", &2)));
1556 assert_eq!(iter.next(), None);
1557 }
1558
1559 #[test]
1560 fn test_panic_in_put_or_modify() {
1561 use std::panic::{catch_unwind, AssertUnwindSafe};
1562
1563 let mut cache = CLruCache::new(TWO);
1564
1565 let put = |_: &&str, value: usize| value;
1566
1567 let modify = |_: &&str, old: &mut usize, new: usize| {
1568 panic!("old value: {:?} / new value: {:?}", old, new);
1569 };
1570
1571 assert_eq!(cache.put_or_modify("a", put, modify, 3), &3);
1572
1573 assert_eq!(cache.put_or_modify("b", put, modify, 5), &5);
1574
1575 let mut iter = cache.iter();
1576 assert_eq!(iter.next(), Some((&"b", &5)));
1577 assert_eq!(iter.next(), Some((&"a", &3)));
1578 assert_eq!(iter.next(), None);
1579
1580 // A panic in the modify closure will move the
1581 // key at the top of the cache.
1582 assert!(catch_unwind(AssertUnwindSafe(|| {
1583 cache.put_or_modify("a", put, modify, 7);
1584 }))
1585 .is_err());
1586
1587 let mut iter = cache.iter();
1588 assert_eq!(iter.next(), Some((&"a", &3)));
1589 assert_eq!(iter.next(), Some((&"b", &5)));
1590 assert_eq!(iter.next(), None);
1591
1592 let put = |_: &&str, value: usize| panic!("value: {:?}", value);
1593
1594 // A panic in the put closure won't have any
1595 // any impact on the cache.
1596 assert!(catch_unwind(AssertUnwindSafe(|| {
1597 cache.put_or_modify("c", put, modify, 7);
1598 }))
1599 .is_err());
1600
1601 let mut iter = cache.iter();
1602 assert_eq!(iter.next(), Some((&"a", &3)));
1603 assert_eq!(iter.next(), Some((&"b", &5)));
1604 assert_eq!(iter.next(), None);
1605 }
1606
1607 #[test]
1608 fn test_try_put_or_modify() {
1609 let mut cache = CLruCache::new(TWO);
1610
1611 let put = |_: &&str, value: usize| {
1612 if value % 2 == 0 {
1613 Ok(value)
1614 } else {
1615 Err(value)
1616 }
1617 };
1618
1619 let modify = |_: &&str, old: &mut usize, new: usize| {
1620 if new % 2 == 0 {
1621 *old = new;
1622 Ok(())
1623 } else {
1624 Err(new)
1625 }
1626 };
1627
1628 assert_eq!(cache.try_put_or_modify("a", put, modify, 2), Ok(&mut 2));
1629 assert_eq!(cache.len(), 1);
1630
1631 let mut iter = cache.iter();
1632 assert_eq!(iter.next(), Some((&"a", &2)));
1633 assert_eq!(iter.next(), None);
1634
1635 assert_eq!(cache.try_put_or_modify("b", put, modify, 4), Ok(&mut 4));
1636 assert_eq!(cache.len(), 2);
1637
1638 let mut iter = cache.iter();
1639 assert_eq!(iter.next(), Some((&"b", &4)));
1640 assert_eq!(iter.next(), Some((&"a", &2)));
1641 assert_eq!(iter.next(), None);
1642
1643 // An error in the modify closure will move the
1644 // key at the top of the cache.
1645 assert_eq!(cache.try_put_or_modify("a", put, modify, 3), Err(3));
1646 assert_eq!(cache.len(), 2);
1647
1648 let mut iter = cache.iter();
1649 assert_eq!(iter.next(), Some((&"a", &2)));
1650 assert_eq!(iter.next(), Some((&"b", &4)));
1651 assert_eq!(iter.next(), None);
1652
1653 // An error in the put closure won't have any
1654 // any impact on the cache.
1655 assert_eq!(cache.try_put_or_modify("c", put, modify, 3), Err(3));
1656 assert_eq!(cache.len(), 2);
1657
1658 let mut iter = cache.iter();
1659 assert_eq!(iter.next(), Some((&"a", &2)));
1660 assert_eq!(iter.next(), Some((&"b", &4)));
1661 assert_eq!(iter.next(), None);
1662 }
1663
1664 #[test]
1665 fn test_from_iterator() {
1666 let cache: CLruCache<&'static str, usize> =
1667 vec![("a", 1), ("b", 2), ("c", 3), ("d", 4), ("e", 5)]
1668 .into_iter()
1669 .collect();
1670
1671 assert_eq!(cache.len(), 5);
1672 assert_eq!(cache.capacity(), 5);
1673 assert_eq!(cache.is_full(), true);
1674
1675 assert_eq!(
1676 cache.into_iter().collect::<Vec<_>>(),
1677 vec![("e", 5), ("d", 4), ("c", 3), ("b", 2), ("a", 1)]
1678 );
1679
1680 let cache: CLruCache<&'static str, usize> = vec![].into_iter().collect();
1681
1682 assert_eq!(cache.len(), 0);
1683 assert_eq!(cache.capacity(), 1);
1684 assert_eq!(cache.is_full(), false);
1685
1686 assert_eq!(cache.into_iter().collect::<Vec<_>>(), vec![]);
1687 }
1688
1689 #[test]
1690 fn test_extend() {
1691 let mut cache = CLruCache::new(FIVE);
1692
1693 cache.put("a", 1);
1694 cache.put("b", 2);
1695
1696 assert_eq!(cache.len(), 2);
1697 assert_eq!(cache.capacity(), 5);
1698 assert_eq!(cache.is_full(), false);
1699
1700 cache.extend([("c", 3), ("d", 4), ("e", 5)]);
1701
1702 assert_eq!(cache.len(), 5);
1703 assert_eq!(cache.capacity(), 5);
1704 assert_eq!(cache.is_full(), true);
1705
1706 assert_eq!(
1707 cache.into_iter().collect::<Vec<_>>(),
1708 vec![("e", 5), ("d", 4), ("c", 3), ("b", 2), ("a", 1)]
1709 );
1710 }
1711
1712 #[derive(Debug)]
1713 struct StrStrScale;
1714
1715 impl WeightScale<&str, &str> for StrStrScale {
1716 fn weight(&self, _key: &&str, value: &&str) -> usize {
1717 value.len()
1718 }
1719 }
1720
1721 #[test]
1722 fn test_weighted_insert_and_get() {
1723 let mut cache = CLruCache::with_config(
1724 CLruCacheConfig::new(NonZeroUsize::new(11).unwrap()).with_scale(StrStrScale),
1725 );
1726 assert!(cache.is_empty());
1727
1728 assert_eq!(cache.put_with_weight("apple", "red").unwrap(), None);
1729 assert_eq!(cache.put_with_weight("banana", "yellow").unwrap(), None);
1730
1731 assert_eq!(cache.capacity(), 11);
1732 assert_eq!(cache.len(), 2);
1733 assert_eq!(cache.weight(), 9);
1734 assert!(!cache.is_empty());
1735 assert!(cache.is_full()); // because of weight
1736 assert_eq!(cache.get(&"apple"), Some(&"red"));
1737 assert_eq!(cache.get(&"banana"), Some(&"yellow"));
1738 }
1739
1740 #[test]
1741 fn test_zero_weight_fails() {
1742 let mut cache = CLruCache::with_config(
1743 CLruCacheConfig::new(NonZeroUsize::new(3).unwrap()).with_scale(StrStrScale),
1744 );
1745
1746 assert!(cache.put_with_weight("apple", "red").is_err());
1747 assert!(cache.put_with_weight("apple", "red").is_err());
1748 }
1749
1750 #[test]
1751 fn test_greater_than_max_weight_fails() {
1752 let mut cache = CLruCache::with_config(
1753 CLruCacheConfig::new(NonZeroUsize::new(3).unwrap()).with_scale(StrStrScale),
1754 );
1755
1756 assert!(cache.put_with_weight("apple", "red").is_err());
1757 }
1758
1759 #[test]
1760 fn test_weighted_insert_update() {
1761 let mut cache = CLruCache::with_config(
1762 CLruCacheConfig::new(NonZeroUsize::new(6).unwrap()).with_scale(StrStrScale),
1763 );
1764
1765 assert_eq!(cache.put_with_weight("apple", "red").unwrap(), None);
1766 assert_eq!(
1767 cache.put_with_weight("apple", "green").unwrap(),
1768 Some("red")
1769 );
1770
1771 assert_eq!(cache.len(), 1);
1772 assert_eq!(cache.get(&"apple"), Some(&"green"));
1773 }
1774
1775 #[test]
1776 fn test_weighted_insert_removes_oldest() {
1777 let mut cache = CLruCache::with_config(
1778 CLruCacheConfig::new(NonZeroUsize::new(16).unwrap()).with_scale(StrStrScale),
1779 );
1780
1781 assert_eq!(cache.put_with_weight("apple", "red").unwrap(), None);
1782 assert_eq!(cache.put_with_weight("banana", "yellow").unwrap(), None);
1783 assert_eq!(cache.put_with_weight("pear", "green").unwrap(), None);
1784
1785 assert!(cache.get(&"apple").is_none());
1786 assert_eq!(cache.get(&"banana"), Some(&"yellow"));
1787 assert_eq!(cache.get(&"pear"), Some(&"green"));
1788 assert_eq!(cache.len(), 2);
1789 assert_eq!(cache.weight(), 11);
1790 assert_eq!(cache.capacity(), 16);
1791 assert!(!cache.is_full());
1792
1793 // Even though we inserted "apple" into the cache earlier it has since been removed from
1794 // the cache so there is no current value for `insert` to return.
1795 assert_eq!(cache.put_with_weight("apple", "green").unwrap(), None);
1796 assert_eq!(cache.put_with_weight("tomato", "red").unwrap(), None);
1797
1798 assert_eq!(cache.len(), 3); // tomato, apple, pear
1799 assert_eq!(cache.weight(), 13); // 3 + 5 + 5
1800 assert_eq!(cache.capacity(), 16);
1801 assert!(cache.is_full());
1802
1803 assert_eq!(cache.get(&"pear"), Some(&"green"));
1804 assert_eq!(cache.get(&"apple"), Some(&"green"));
1805 assert_eq!(cache.get(&"tomato"), Some(&"red"));
1806 }
1807
1808 #[test]
1809 fn test_weighted_clear() {
1810 let mut cache = CLruCache::with_config(
1811 CLruCacheConfig::new(NonZeroUsize::new(10).unwrap()).with_scale(StrStrScale),
1812 );
1813
1814 assert_eq!(cache.put_with_weight("apple", "red"), Ok(None));
1815 assert_eq!(cache.put_with_weight("banana", "yellow"), Ok(None));
1816
1817 assert_eq!(cache.len(), 1);
1818 assert_eq!(cache.weight(), 6);
1819 assert_eq!(cache.get(&"apple"), None);
1820 assert_eq!(cache.get(&"banana"), Some(&"yellow"));
1821
1822 cache.clear();
1823 assert_eq!(cache.len(), 0);
1824 assert_eq!(cache.weight(), 0);
1825 }
1826
1827 #[derive(Debug)]
1828 struct IntStrScale;
1829
1830 impl WeightScale<usize, &str> for IntStrScale {
1831 fn weight(&self, _key: &usize, value: &&str) -> usize {
1832 value.len()
1833 }
1834 }
1835
1836 #[test]
1837 fn test_weighted_resize_larger() {
1838 let mut cache = CLruCache::with_config(
1839 CLruCacheConfig::new(NonZeroUsize::new(4).unwrap()).with_scale(IntStrScale),
1840 );
1841
1842 assert_eq!(cache.put_with_weight(1, "a"), Ok(None));
1843 assert_eq!(cache.put_with_weight(2, "b"), Ok(None));
1844 assert_eq!(cache.len(), 2);
1845 assert_eq!(cache.weight(), 2);
1846 assert_eq!(cache.capacity(), 4);
1847 assert!(cache.is_full());
1848
1849 cache.resize(SIX);
1850
1851 assert_eq!(cache.len(), 2);
1852 assert_eq!(cache.weight(), 2);
1853 assert_eq!(cache.capacity(), 6);
1854 assert!(!cache.is_full());
1855
1856 cache.resize(HEIGHT);
1857
1858 assert_eq!(cache.len(), 2);
1859 assert_eq!(cache.weight(), 2);
1860 assert_eq!(cache.capacity(), 8);
1861 assert!(!cache.is_full());
1862
1863 assert_eq!(cache.put_with_weight(3, "c"), Ok(None));
1864 assert_eq!(cache.put_with_weight(4, "d"), Ok(None));
1865
1866 assert_eq!(cache.len(), 4);
1867 assert_eq!(cache.weight(), 4);
1868 assert_eq!(cache.capacity(), 8);
1869 assert!(cache.is_full());
1870 assert_eq!(cache.get(&1), Some(&"a"));
1871 assert_eq!(cache.get(&2), Some(&"b"));
1872 assert_eq!(cache.get(&3), Some(&"c"));
1873 assert_eq!(cache.get(&4), Some(&"d"));
1874 }
1875
1876 #[test]
1877 fn test_weighted_resize_smaller() {
1878 let mut cache = CLruCache::with_config(
1879 CLruCacheConfig::new(NonZeroUsize::new(8).unwrap()).with_scale(IntStrScale),
1880 );
1881
1882 assert_eq!(cache.put_with_weight(1, "a"), Ok(None));
1883 assert_eq!(cache.put_with_weight(2, "b"), Ok(None));
1884 assert_eq!(cache.put_with_weight(3, "c"), Ok(None));
1885 assert_eq!(cache.put_with_weight(4, "d"), Ok(None));
1886 assert_eq!(cache.len(), 4);
1887 assert_eq!(cache.weight(), 4);
1888 assert_eq!(cache.capacity(), 8);
1889 assert!(cache.is_full());
1890
1891 cache.resize(FOUR);
1892
1893 assert_eq!(cache.len(), 2);
1894 assert_eq!(cache.weight(), 2);
1895 assert_eq!(cache.capacity(), 4);
1896 assert!(cache.is_full());
1897
1898 assert!(cache.get(&1).is_none());
1899 assert!(cache.get(&2).is_none());
1900 assert_eq!(cache.get(&3), Some(&"c"));
1901 assert_eq!(cache.get(&4), Some(&"d"));
1902
1903 cache.resize(THREE);
1904
1905 assert_eq!(cache.len(), 1);
1906 assert_eq!(cache.weight(), 1);
1907 assert_eq!(cache.capacity(), 3);
1908 assert!(!cache.is_full());
1909
1910 assert_eq!(cache.get(&1), None);
1911 assert_eq!(cache.get(&2), None);
1912 assert_eq!(cache.get(&3), None);
1913 assert_eq!(cache.get(&4), Some(&"d"));
1914 }
1915
1916 #[test]
1917 fn test_weighted_resize_equal() {
1918 let mut cache = CLruCache::with_config(
1919 CLruCacheConfig::new(NonZeroUsize::new(8).unwrap()).with_scale(IntStrScale),
1920 );
1921
1922 assert_eq!(cache.put_with_weight(1, "a"), Ok(None));
1923 assert_eq!(cache.put_with_weight(2, "b"), Ok(None));
1924 assert_eq!(cache.put_with_weight(3, "c"), Ok(None));
1925 assert_eq!(cache.put_with_weight(4, "d"), Ok(None));
1926
1927 assert_eq!(cache.len(), 4);
1928 assert_eq!(cache.weight(), 4);
1929 assert_eq!(cache.capacity(), 8);
1930 assert!(cache.is_full());
1931
1932 cache.resize(HEIGHT);
1933
1934 assert_eq!(cache.len(), 4);
1935 assert_eq!(cache.weight(), 4);
1936 assert_eq!(cache.capacity(), 8);
1937 assert!(cache.is_full());
1938
1939 assert_eq!(cache.get(&1), Some(&"a"));
1940 assert_eq!(cache.get(&2), Some(&"b"));
1941 assert_eq!(cache.get(&3), Some(&"c"));
1942 assert_eq!(cache.get(&4), Some(&"d"));
1943 }
1944
1945 #[test]
1946 fn test_weighted_iter() {
1947 let mut cache = CLruCache::with_config(
1948 CLruCacheConfig::new(NonZeroUsize::new(8).unwrap()).with_scale(IntStrScale),
1949 );
1950
1951 assert_eq!(cache.put_with_weight(1, "a"), Ok(None));
1952 assert_eq!(cache.put_with_weight(2, "b"), Ok(None));
1953 assert_eq!(cache.put_with_weight(3, "c"), Ok(None));
1954 assert_eq!(cache.put_with_weight(4, "d"), Ok(None));
1955
1956 assert_eq!(cache.len(), 4);
1957 assert_eq!(cache.weight(), 4);
1958 assert_eq!(cache.capacity(), 8);
1959 assert!(cache.is_full());
1960 }
1961
1962 #[test]
1963 fn test_weighted_iter_forwards() {
1964 let mut cache = CLruCache::with_config(
1965 CLruCacheConfig::new(NonZeroUsize::new(8).unwrap()).with_scale(IntStrScale),
1966 );
1967 assert_eq!(cache.put_with_weight(1, "a"), Ok(None));
1968 assert_eq!(cache.put_with_weight(2, "b"), Ok(None));
1969 assert_eq!(cache.put_with_weight(3, "c"), Ok(None));
1970
1971 let mut iter = cache.iter();
1972 assert_eq!(iter.len(), 3);
1973 assert_eq!(iter.next(), Some((&3, &"c")));
1974
1975 assert_eq!(iter.len(), 2);
1976 assert_eq!(iter.next(), Some((&2, &"b")));
1977
1978 assert_eq!(iter.len(), 1);
1979 assert_eq!(iter.next(), Some((&1, &"a")));
1980
1981 assert_eq!(iter.len(), 0);
1982 assert_eq!(iter.next(), None);
1983 }
1984
1985 #[test]
1986 fn test_weighted_iter_backwards() {
1987 let mut cache = CLruCache::with_config(
1988 CLruCacheConfig::new(NonZeroUsize::new(8).unwrap()).with_scale(IntStrScale),
1989 );
1990 assert_eq!(cache.put_with_weight(1, "a"), Ok(None));
1991 assert_eq!(cache.put_with_weight(2, "b"), Ok(None));
1992 assert_eq!(cache.put_with_weight(3, "c"), Ok(None));
1993
1994 let mut iter = cache.iter();
1995 assert_eq!(iter.len(), 3);
1996 assert_eq!(iter.next_back(), Some((&1, &"a")));
1997
1998 assert_eq!(iter.len(), 2);
1999 assert_eq!(iter.next_back(), Some((&2, &"b")));
2000
2001 assert_eq!(iter.len(), 1);
2002 assert_eq!(iter.next_back(), Some((&3, &"c")));
2003
2004 assert_eq!(iter.len(), 0);
2005 assert_eq!(iter.next_back(), None);
2006 }
2007
2008 #[test]
2009 fn test_weighted_iter_forwards_and_backwards() {
2010 let mut cache = CLruCache::with_config(
2011 CLruCacheConfig::new(NonZeroUsize::new(8).unwrap()).with_scale(IntStrScale),
2012 );
2013 assert_eq!(cache.put_with_weight(1, "a"), Ok(None));
2014 assert_eq!(cache.put_with_weight(2, "b"), Ok(None));
2015 assert_eq!(cache.put_with_weight(3, "c"), Ok(None));
2016
2017 let mut iter = cache.iter();
2018 assert_eq!(iter.len(), 3);
2019 assert_eq!(iter.next(), Some((&3, &"c")));
2020
2021 assert_eq!(iter.len(), 2);
2022 assert_eq!(iter.next_back(), Some((&1, &"a")));
2023
2024 assert_eq!(iter.len(), 1);
2025 assert_eq!(iter.next(), Some((&2, &"b")));
2026
2027 assert_eq!(iter.len(), 0);
2028 assert_eq!(iter.next_back(), None);
2029 }
2030
2031 #[test]
2032 fn test_weighted_into_iter() {
2033 let mut cache = CLruCache::with_config(
2034 CLruCacheConfig::new(NonZeroUsize::new(10).unwrap()).with_scale(IntStrScale),
2035 );
2036
2037 assert_eq!(cache.put_with_weight(1, "a"), Ok(None));
2038 assert_eq!(cache.put_with_weight(2, "b"), Ok(None));
2039 assert_eq!(cache.put_with_weight(3, "c"), Ok(None));
2040 assert_eq!(cache.put_with_weight(4, "d"), Ok(None));
2041 assert_eq!(cache.put_with_weight(5, "e"), Ok(None));
2042
2043 let mut vec = Vec::new();
2044 for (k, v) in &cache {
2045 vec.push((k, v));
2046 }
2047 assert_eq!(
2048 vec,
2049 vec![(&5, &"e"), (&4, &"d"), (&3, &"c"), (&2, &"b"), (&1, &"a")]
2050 );
2051
2052 assert_eq!(
2053 cache.into_iter().collect::<Vec<_>>(),
2054 vec![(5, "e"), (4, "d"), (3, "c"), (2, "b"), (1, "a")]
2055 );
2056 }
2057
2058 #[test]
2059 fn test_is_send() {
2060 fn is_send<T: Send>() {}
2061
2062 fn cache_is_send<K: Send, V: Send, S: Send, W: WeightScale<K, V> + Send>() {
2063 is_send::<K>();
2064 is_send::<V>();
2065 is_send::<S>();
2066 is_send::<W>();
2067 is_send::<CLruCache<K, V, S, W>>();
2068 }
2069
2070 cache_is_send::<String, String, RandomState, ZeroWeightScale>();
2071
2072 fn cache_in_mutex<
2073 K: Clone + Default + Eq + Hash + Send + 'static,
2074 V: Default + Send + 'static,
2075 S: BuildHasher + Send + 'static,
2076 W: WeightScale<K, V> + Send + 'static,
2077 >(
2078 cache: CLruCache<K, V, S, W>,
2079 ) where
2080 (K, V): std::fmt::Debug,
2081 {
2082 use std::sync::{Arc, Mutex};
2083 use std::thread;
2084
2085 let mutex: Arc<Mutex<CLruCache<K, V, S, W>>> = Arc::new(Mutex::new(cache));
2086 let mutex2 = mutex.clone();
2087 let t1 = thread::spawn(move || {
2088 mutex
2089 .lock()
2090 .unwrap()
2091 .put_with_weight(Default::default(), Default::default())
2092 .unwrap();
2093 });
2094 let t2 = thread::spawn(move || {
2095 mutex2
2096 .lock()
2097 .unwrap()
2098 .put_with_weight(Default::default(), Default::default())
2099 .unwrap();
2100 });
2101 t1.join().unwrap();
2102 t2.join().unwrap();
2103 }
2104
2105 let cache: CLruCache<String, String> = CLruCache::new(TWO);
2106 cache_in_mutex(cache);
2107 }
2108
2109 #[test]
2110 fn test_is_sync() {
2111 fn is_sync<T: Sync>() {}
2112
2113 fn cache_is_sync<K: Sync, V: Sync, S: Sync, W: WeightScale<K, V> + Sync>() {
2114 is_sync::<K>();
2115 is_sync::<V>();
2116 is_sync::<S>();
2117 is_sync::<W>();
2118 is_sync::<CLruCache<K, V, S, W>>();
2119 }
2120
2121 cache_is_sync::<String, String, RandomState, ZeroWeightScale>();
2122
2123 fn cache_in_rwlock<
2124 K: Clone + Default + Eq + Hash + Send + Sync + 'static,
2125 V: Default + Send + Sync + 'static,
2126 S: BuildHasher + Send + Sync + 'static,
2127 W: WeightScale<K, V> + Send + Sync + 'static,
2128 >(
2129 cache: CLruCache<K, V, S, W>,
2130 ) where
2131 (K, V): std::fmt::Debug,
2132 {
2133 use std::sync::{Arc, RwLock};
2134 use std::thread;
2135
2136 let mutex: Arc<RwLock<CLruCache<K, V, S, W>>> = Arc::new(RwLock::new(cache));
2137 let mutex2 = mutex.clone();
2138 let t1 = thread::spawn(move || {
2139 mutex
2140 .write()
2141 .unwrap()
2142 .put_with_weight(Default::default(), Default::default())
2143 .unwrap();
2144 });
2145 let t2 = thread::spawn(move || {
2146 mutex2
2147 .write()
2148 .unwrap()
2149 .put_with_weight(Default::default(), Default::default())
2150 .unwrap();
2151 });
2152 t1.join().unwrap();
2153 t2.join().unwrap();
2154 }
2155
2156 let cache: CLruCache<String, String> = CLruCache::new(TWO);
2157 cache_in_rwlock(cache);
2158 }
2159}
2160