CLru

CLru 是 Rust 中的另一个 LRU 缓存 实现。它有两个主要特点，使其与其他实现不同

1. 它背后有一个 HashMap：它为常见的操作如

   • get / get_mut
   • put / pop
   • peek / peek_mut

2. 提供 O(1) 时间复杂度（摊销平均时间）

   • 它是一个加权缓存：每个键值对都有一个权重，容量同时作为
   • 元素数量的限制

   以及其元素总权重的限制

   使用以下公式

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

对于元素没有权重的常见 LRU 缓存情况，提供了一个默认的 ZeroWeightScale，并解锁了一些有用的 API，例如

• CLruCache::put：一个不可失败的插入操作，最多删除1个元素。
• CLruCache::put_or_modify：类似于HashMap入口API的条件插入或修改流程。
• CLruCache::try_put_or_modify：CLruCache::put_or_modify的可失败版本。
• 所有允许检索值可变引用的API（例如：CLruCache::get_mut）。

免责声明

大部分的API、文档、示例和测试都受到了lru crate的很大启发。我想感谢jeromefroe，没有他的工作，这个crate可能永远不会发布。

与lru的差异

主要差异包括

• 更少的unsafe代码。只要经过彻底审查和理解，unsafe代码本身并没有什么不好，但可能很难正确实现。减少unsafe代码的数量应该可以减少错误或未定义的行为。
• API更接近标准HashMap集合，允许使用通过Borrow-ed版本的键进行查找。

示例

以下是如何实例化和使用这个LRU缓存的简单示例。

使用默认的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));

使用自定义的WeightScale实现

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"));

测试

每个贡献都通过常规编译器、miri和4种sanitizer（地址、内存、线程和泄漏）进行测试。这应该有助于尽早捕捉到错误。

待办事项

• 改进文档并添加示例