Struct lrumap::LruHashMap

pub struct LruHashMap<Key, Value, State = DefaultState> { /* private fields */ }

A Least Recently Used map with fixed capacity that stores keys using a HashMap internally. Inserting and querying has similar performance to using a HashMap, 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> LruHashMap<Key, Value, DefaultState>where
    Key: Hash + Eq + Clone,

pub fn new(capacity: usize) -> Self

Creates a new map with the maximum capacity.

Panics

Panics if capacity is <= 1.

impl<Key, Value, State> LruHashMap<Key, Value, State>where
    Key: Hash + Eq + Clone,
    State: BuildHasher,

pub fn with_hasher(capacity: usize, hasher: State) -> Self

Creates a new map with the maximum capacity and hasher.

Panics

Panics if capacity is <= 1

pub fn get<QueryKey>(&mut self, key: &QueryKey) -> Option<&Value>where
    QueryKey: Hash + Eq + ?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_mut<QueryKey>(&mut self, key: &QueryKey) -> Option<&mut Value>where
    QueryKey: Hash + Eq + ?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: Hash + Eq + ?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: Hash + Eq + ?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::{LruHashMap, LruMap, Removed};

let mut lru = LruHashMap::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::{LruHashMap, LruMap, Removed};

let mut lru = LruHashMap::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::{LruHashMap, LruMap};

let mut lru = LruHashMap::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);

Trait Implementations

impl<Key: Debug, Value: Debug, State: Debug> Debug for LruHashMap<Key, Value, State>

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

Formats the value using the given formatter.

impl<Key, Value, State> IntoIterator for LruHashMap<Key, Value, State>where
    Key: Hash + Eq + Clone,
    State: BuildHasher,

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 LruHashMap<Key, Value, DefaultState>where
    Key: Hash + Eq + 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 get<QueryKey>(&mut self, key: &QueryKey) -> Option<&Value>where
    QueryKey: Ord + Hash + Eq + ?Sized,
    Key: Borrow<QueryKey> + Ord + Hash + Eq,

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 + Hash + Eq,

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 + Hash + Eq,

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 iter(&self) -> Iter<'_, Key, Value>

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

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.