Crate clru

Another LRU cache implementation in rust. It has two main characteristics that differentiates it from other implementation:

1. It is backed by a HashMap: it offers a O(1) time complexity (amortized average) for any operation that requires to lookup an entry from a key.

2. It is a weighted cache: each key-value pair has a weight and the capacity serves as both as:

   • a limit to the number of elements
   • and as a limit to the total weight of its elements

   using the following formula:

   CLruCache::len + CLruCache::weight <= CLruCache::capacity

Even though most operations don’t depend on the number of elements in the cache, CLruCache::put_with_weight has a special behavior: because it needs to make room for the new element, it will remove enough least recently used elements. In the worst case, that will require to fully empty the cache. Additionally, if the weight of the new element is too big, the insertion can fail.

For the common case of an LRU cache whose elements don’t have a weight, a default ZeroWeightScale is provided and unlocks some useful APIs like:

• CLruCache::put: an infallible insertion that will remove a maximum of 1 element.
• CLruCache::put_or_modify: a conditional insertion or modification flow similar to the entry API of HashMap.
• CLruCache::try_put_or_modify: fallible version of CLruCache::put_or_modify.
• All APIs that allow to retrieve a mutable reference to a value (e.g.: CLruCache::get_mut).

The cache requires the keys to be clonable because it will store 2 instances of each key in different internal data structures. If cloning a key can be expensive, you might want to consider using an std::rc::Rc or an std::sync::Arc.

Examples

Using the default ZeroWeightScale:

use std::num::NonZeroUsize;
use clru::CLruCache;

let mut cache = CLruCache::new(NonZeroUsize::new(2).unwrap());
cache.put("apple".to_string(), 3);
cache.put("banana".to_string(), 2);

assert_eq!(cache.get("apple"), Some(&3));
assert_eq!(cache.get("banana"), Some(&2));
assert!(cache.get("pear").is_none());

assert_eq!(cache.put("banana".to_string(), 4), Some(2));
assert_eq!(cache.put("pear".to_string(), 5), None);

assert_eq!(cache.get("pear"), Some(&5));
assert_eq!(cache.get("banana"), Some(&4));
assert!(cache.get("apple").is_none());

{
    let v = cache.get_mut("banana").unwrap();
    *v = 6;
}

assert_eq!(cache.get("banana"), Some(&6));

Using a custom WeightScale implementation:

use std::num::NonZeroUsize;
use clru::{CLruCache, CLruCacheConfig, WeightScale};

struct CustomScale;

impl WeightScale<String, &str> for CustomScale {
    fn weight(&self, _key: &String, value: &&str) -> usize {
        value.len()
    }
}

let mut cache = CLruCache::with_config(
    CLruCacheConfig::new(NonZeroUsize::new(6).unwrap()).with_scale(CustomScale),
);

assert_eq!(cache.put_with_weight("apple".to_string(), "red").unwrap(), None);
assert_eq!(
    cache.put_with_weight("apple".to_string(), "green").unwrap(),
    Some("red")
);

assert_eq!(cache.len(), 1);
assert_eq!(cache.get("apple"), Some(&"green"));

Structs

• CLruCache
  A weighted LRU cache with mostly¹ constant time operations.
• CLruCacheConfig
  A configuration structure used to create an LRU cache.
• CLruCacheIntoIter
  An owning iterator over the elements of a CLruCache.
• CLruCacheIter
  An iterator over the entries of a CLruCache.
• CLruCacheIterMut
  An iterator over mutables entries of a CLruCache.
• ZeroWeightScale
  A scale that always return 0.

Traits

• WeightScale
  Trait used to retrieve the weight of a key-value pair.