LruMap
A set of safe Least-Recently-Used (LRU) cache types aimed at providing flexible map-like structures that automatically evict the least recently used key and value when its capacity is reached.
LRU Implementation
This crate utilizes an "arena"-style linked list implementation, where all nodes of the linked list are stored in a Vec. Instead of using pointers to the nodes, all references to a node in the linked list is done using an index into the Vec.
This allows all LRU list operations to be performed in constant time and remain very efficient. Each of the implementations in this crate use this internal LRU linked list implementation.
LruHashMap
The LruHashMap type is an LRU implementation that internally uses a HashMap to track keys. Its performance characteristics will be similar to the underlying hash map and hash implementation.
For most users, this type will be the best choice.
This crate has no features enabled by default, but transparently can switch to hashbrown and its default hasher by enabling feature hashbrown.
use lrumap::{LruHashMap, Removed};
let mut lru = LruHashMap::new(3);
lru.push(1, "one");
lru.push(2, "two");
lru.push(3, "three");
// The cache is now full. The next push will evict the least recently touched entry.
let removed = lru.push(4, "four");
assert_eq!(removed, Some(Removed::Evicted(1, "one")));
LruBTreeMap
The LruBTreeMap type is an LRU implementation that internally uses a BTreeMap to track keys. Its performance characteristics will be similar to the underlying container implementation.
By using a BTreeMap to track keys, this type enables efficient range-based queries:
use lrumap::LruBTreeMap;
let mut lru = LruBTreeMap::new(5);
lru.extend([(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)]);
assert_eq!(lru.most_recent_in_range(2..=4).unwrap().key(), &4);
// Change the order by retrieving key 2.
lru.get(&2);
assert_eq!(lru.most_recent_in_range(2..=4).unwrap().key(), &2);
Why another LRU crate?
For Nebari, we needed to introduce an LRU cache to the StdFileManager to close files that haven't been used recently. Each file can have multiple readers, leading to an issue of needing to scan the LRU map for all values that match a specific file. In the end, @ecton decided an LRU implementation that used a BTreeMap instead of a HashMap would be able to solve this problem by offering an most_recent_in_range(key) function. No existing crates seemed to offer this functionality.
Open-source Licenses
This project, like all projects from Khonsu Labs, are open-source. This repository is available under the MIT License or the Apache License 2.0.
To learn more about contributing, please see CONTRIBUTING.md.
3 Jun 28, 2022
2 Dec 14, 2022
12 Dec 31, 2022
7 Apr 21, 2023
25 Jun 15, 2022
104 Dec 23, 2022
83 Dec 11, 2022
57 Dec 19, 2022
37 Dec 21, 2022
67 Jan 1, 2023
294 Dec 23, 2022
2 May 3, 2022
5 Nov 4, 2020
2 Jun 1, 2022
18 Aug 6, 2023
8 Aug 23, 2022
13 Nov 30, 2022
22 Sep 16, 2023
37 Dec 21, 2022
310 Dec 29, 2022
996 Jan 7, 2023
3 Dec 8, 2022
1 Jan 12, 2022
15 Oct 1, 2022
274 Dec 14, 2022
8 Jul 23, 2022
27 Aug 15, 2022
58 Dec 2, 2022