Struct lrumap::LruBTreeMap

pub struct LruBTreeMap<Key, Value> { /* private fields */ }

A Least Recently Used map with fixed capacity that stores keys using a BTreeMap internally. Inserting and querying has similar performance to using a BTreeMap, but internally this data structure keeps track of the order in which the keys were last touched.

When inserting a new key and the map is at-capacity, the least recently used key will be evicted to make room for the new key.

To avoid unsafe, this crate must store each entry’s key twice. This means that Key must implement Clone. If you’re using expensive-to-clone keys, consider wrapping the key in an Rc/Arc or using an alternate LRU crate.

Implementations

impl<Key, Value> LruBTreeMap<Key, Value>where
    Key: Ord + Clone,

pub fn new(capacity: usize) -> Self

Creates a new map with the maximum capacity.

Panics

Panics if capacity is <= 1 or > u32::MAX.

pub fn get<QueryKey>(&mut self, key: &QueryKey) -> Option<&Value>where
    QueryKey: Ord + ?Sized,
    Key: Borrow<QueryKey>,

Returns the stored value for key, if present.

This function touches the key, making it the most recently used key.

pub fn get_without_update<QueryKey>(&self, key: &QueryKey) -> Option<&Value>where
    QueryKey: Ord + ?Sized,
    Key: Borrow<QueryKey>,

Returns the stored value for key, if present.

This function does not touch the key, preserving its current position in the lru cache.

pub fn entry<QueryKey>(
    &mut self,
    key: &QueryKey
) -> Option<EntryRef<'_, Self, Key, Value>>where
    QueryKey: Ord + ?Sized,
    Key: Borrow<QueryKey>,

Returns an EntryRef for key, if present.

This function does not touch the key, preserving its current position in the lru cache. The EntryRef can touch the key, depending on which functions are used.

use lrumap::{LruBTreeMap, LruMap, Removed};

let mut lru = LruBTreeMap::new(3);
lru.push(1, 1);
lru.push(2, 2);
lru.push(3, 3);

// The cache has been updated once since entry 2 was touched.
let mut entry = lru.entry(&2).unwrap();
assert_eq!(entry.staleness(), 1);
// Peeking the value will not update the entry's position.
assert_eq!(entry.peek_value(), &2);
assert_eq!(entry.staleness(), 1);
// Querying the value or touching the entry will move it to the
// front of the cache.
assert_eq!(entry.value(), &2);
assert_eq!(entry.staleness(), 0);

assert_eq!(lru.head().unwrap().key(), &2);

pub fn push(&mut self, key: Key, value: Value) -> Option<Removed<Key, Value>>

Inserts value for key into this map. If a value is already stored for this key, Removed::PreviousValue is returned with the previously stored value. If no value is currently stored and the map is full, the least recently used entry will be returned in Removed::Evicted. Otherwise, None will be returned.

This function touches the key, making it the most recently used key.

use lrumap::{LruBTreeMap, LruMap, Removed};

let mut lru = LruBTreeMap::new(3);
lru.push(1, 1);
lru.push(2, 2);
lru.push(3, 3);

// The cache is now full. The next push will evict an entry.
let removed = lru.push(4, 4);
assert_eq!(removed, Some(Removed::Evicted(1, 1)));

// This leaves the cache with 4 as the most recent key, and 2 as the
// least recent key.
assert_eq!(lru.head().unwrap().key(), &4);
assert_eq!(lru.tail().unwrap().key(), &2);

pub fn extend<IntoIter: IntoIterator<Item = (Key, Value)>>(
    &mut self,
    iterator: IntoIter
)

Pushes all items from iterator into this map. If there are more entries in the iterator than capacity remaining, keys will be evicted as needed.

This function is equivalent to a for loop calling Self::push().

use lrumap::{LruBTreeMap, LruMap};

let mut lru = LruBTreeMap::new(3);
lru.extend([(1, 1), (2, 2), (3, 3), (4, 4)]);

assert_eq!(lru.head().unwrap().key(), &4);
assert_eq!(lru.tail().unwrap().key(), &2);

pub fn most_recent_in_range<QueryKey, Range>(
    &mut self,
    range: Range
) -> Option<EntryRef<'_, Self, Key, Value>>where
    QueryKey: Ord + ?Sized,
    Key: Borrow<QueryKey>,
    Range: RangeBounds<QueryKey>,

Returns the most recently touched entry with a key within range.

This function uses BTreeMap::range to identify all entries that match the given range. For each returned entry, the entry’s staleness is compared, and the least stale entry is returned. If no keys match the range, None is returned.

This function does not touch any keys, preserving the current order of the lru cache. The EntryRef returned can be used to peek, touch, or remove the entry.

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

pub fn most_recent_in_range_where<QueryKey, Range, Condition>(
    &mut self,
    range: Range,
    condition: Condition
) -> Option<EntryRef<'_, Self, Key, Value>>where
    QueryKey: Ord + ?Sized,
    Key: Borrow<QueryKey>,
    Range: RangeBounds<QueryKey>,
    Condition: for<'key, 'value> FnMut(&'key Key, &'value Value) -> bool,

Returns the most recently touched entry with a key within range that passes the condition check.

This function uses BTreeMap::range to identify all entries that match the given range. Each key and value that matches is passed to condition. For each entry where condition returns true, the staleness is compared, and the least stale entry is returned. If no keys match the range, None is returned.

This function does not touch any keys, preserving the current order of the lru cache. The EntryRef returned can be used to peek, touch, or remove the entry.

use lrumap::LruBTreeMap;

let mut lru = LruBTreeMap::<u32, u16>::new(5);
lru.extend([(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)]);

let condition = |key: &u32, value: &u16| key == &3 || value == &4;
assert_eq!(
    lru.most_recent_in_range_where(2..=4, condition)
        .unwrap()
        .key(),
    &4
);

// Change the order by retrieving key 2. However, 2 doesn't meet the
// condition, so the result is unchanged.
lru.get(&2);
assert_eq!(
    lru.most_recent_in_range_where(2..=4, condition)
        .unwrap()
        .key(),
    &4
);

// Request 3, moving it to the front. Since 3 matches the condition, the
// result is now 3.
lru.get(&3);
assert_eq!(
    lru.most_recent_in_range_where(2..=4, condition)
        .unwrap()
        .key(),
    &3
);

Trait Implementations

impl<Key: Debug, Value: Debug> Debug for LruBTreeMap<Key, Value>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<Key, Value> IntoIterator for LruBTreeMap<Key, Value>where
    Key: Ord + Clone,

type IntoIter = IntoIter<Key, Value>

Which kind of iterator are we turning this into?

type Item = (Key, Value)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<Key, Value> LruMap<Key, Value> for LruBTreeMap<Key, Value>where
    Key: Ord + Clone,

fn new(capacity: usize) -> Self

Creates a new map with the maximum capacity.

fn len(&self) -> usize

Returns the number of keys present in this map.

fn head(&mut self) -> Option<EntryRef<'_, Self, Key, Value>>

Returns a reference to the most recently used key.

fn tail(&mut self) -> Option<EntryRef<'_, Self, Key, Value>>

Returns a reference to the least recently used key.

fn iter(&self) -> Iter<'_, Key, Value>

Returns an iterator over the keys and values in order from most recently touched to least recently touched.

fn get<QueryKey>(&mut self, key: &QueryKey) -> Option<&Value>where
    QueryKey: Ord + Hash + Eq + ?Sized,
    Key: Borrow<QueryKey> + Ord + Eq + Hash,

Returns the stored value for key, if present.

fn get_without_update<QueryKey>(&self, key: &QueryKey) -> Option<&Value>where
    QueryKey: Ord + Hash + Eq + ?Sized,
    Key: Borrow<QueryKey> + Ord + Eq + Hash,

Returns the stored value for key, if present.

fn entry<QueryKey>(
    &mut self,
    key: &QueryKey
) -> Option<EntryRef<'_, Self, Key, Value>>where
    QueryKey: Ord + Hash + Eq + ?Sized,
    Key: Borrow<QueryKey> + Ord + Eq + Hash,

Returns an EntryRef for key, if present.

fn push(&mut self, key: Key, value: Value) -> Option<Removed<Key, Value>>

Inserts value for key into this map. If a value is already stored for this key, Removed::PreviousValue is returned with the previously stored value. If no value is currently stored and the map is full, the least recently used entry will be returned in Removed::Evicted. Otherwise, None will be returned.

fn extend<IntoIter: IntoIterator<Item = (Key, Value)>>(
    &mut self,
    iterator: IntoIter
)

Pushes all items from iterator into this map. If there are more entries in the iterator than capacity remaining, keys will be evicted as needed.

fn is_empty(&self) -> bool

Retruns true if this map contains no keys.