Struct lrumap::LruHashMap
source · [−]pub struct LruHashMap<Key, Value, State = DefaultState> { /* private fields */ }
Expand description
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
sourceimpl<Key, Value> LruHashMap<Key, Value, DefaultState>where
Key: Hash + Eq + Clone,
impl<Key, Value> LruHashMap<Key, Value, DefaultState>where
Key: Hash + Eq + Clone,
sourceimpl<Key, Value, State> LruHashMap<Key, Value, State>where
Key: Hash + Eq + Clone,
State: BuildHasher,
impl<Key, Value, State> LruHashMap<Key, Value, State>where
Key: Hash + Eq + Clone,
State: BuildHasher,
sourcepub fn with_hasher(capacity: usize, hasher: State) -> Self
pub fn with_hasher(capacity: usize, hasher: State) -> Self
sourcepub fn get<QueryKey>(&mut self, key: &QueryKey) -> Option<&Value>where
QueryKey: Hash + Eq + ?Sized,
Key: Borrow<QueryKey>,
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.
sourcepub fn get_mut<QueryKey>(&mut self, key: &QueryKey) -> Option<&mut Value>where
QueryKey: Hash + Eq + ?Sized,
Key: Borrow<QueryKey>,
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.
sourcepub fn get_without_update<QueryKey>(&self, key: &QueryKey) -> Option<&Value>where
QueryKey: Hash + Eq + ?Sized,
Key: Borrow<QueryKey>,
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.
sourcepub fn entry<QueryKey>(
&mut self,
key: &QueryKey
) -> Option<EntryRef<'_, Self, Key, Value>>where
QueryKey: Hash + Eq + ?Sized,
Key: Borrow<QueryKey>,
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);
sourcepub fn push(&mut self, key: Key, value: Value) -> Option<Removed<Key, Value>>
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);
sourcepub fn extend<IntoIter: IntoIterator<Item = (Key, Value)>>(
&mut self,
iterator: IntoIter
)
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
sourceimpl<Key, Value, State> IntoIterator for LruHashMap<Key, Value, State>where
Key: Hash + Eq + Clone,
State: BuildHasher,
impl<Key, Value, State> IntoIterator for LruHashMap<Key, Value, State>where
Key: Hash + Eq + Clone,
State: BuildHasher,
sourceimpl<Key, Value> LruMap<Key, Value> for LruHashMap<Key, Value, DefaultState>where
Key: Hash + Eq + Clone,
impl<Key, Value> LruMap<Key, Value> for LruHashMap<Key, Value, DefaultState>where
Key: Hash + Eq + Clone,
sourcefn head(&mut self) -> Option<EntryRef<'_, Self, Key, Value>>
fn head(&mut self) -> Option<EntryRef<'_, Self, Key, Value>>
sourcefn tail(&mut self) -> Option<EntryRef<'_, Self, Key, Value>>
fn tail(&mut self) -> Option<EntryRef<'_, Self, Key, Value>>
sourcefn get<QueryKey>(&mut self, key: &QueryKey) -> Option<&Value>where
QueryKey: Ord + Hash + Eq + ?Sized,
Key: Borrow<QueryKey> + Ord + Hash + Eq,
fn get<QueryKey>(&mut self, key: &QueryKey) -> Option<&Value>where
QueryKey: Ord + Hash + Eq + ?Sized,
Key: Borrow<QueryKey> + Ord + Hash + Eq,
key
, if present. Read moresourcefn get_without_update<QueryKey>(&self, key: &QueryKey) -> Option<&Value>where
QueryKey: Ord + Hash + Eq + ?Sized,
Key: Borrow<QueryKey> + Ord + Hash + Eq,
fn get_without_update<QueryKey>(&self, key: &QueryKey) -> Option<&Value>where
QueryKey: Ord + Hash + Eq + ?Sized,
Key: Borrow<QueryKey> + Ord + Hash + Eq,
key
, if present. Read moresourcefn entry<QueryKey>(
&mut self,
key: &QueryKey
) -> Option<EntryRef<'_, Self, Key, Value>>where
QueryKey: Ord + Hash + Eq + ?Sized,
Key: Borrow<QueryKey> + Ord + Hash + Eq,
fn entry<QueryKey>(
&mut self,
key: &QueryKey
) -> Option<EntryRef<'_, Self, Key, Value>>where
QueryKey: Ord + Hash + Eq + ?Sized,
Key: Borrow<QueryKey> + Ord + Hash + Eq,
sourcefn push(&mut self, key: Key, value: Value) -> Option<Removed<Key, Value>>
fn push(&mut self, key: Key, value: Value) -> Option<Removed<Key, Value>>
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. Read moresourcefn iter(&self) -> Iter<'_, Key, Value>ⓘNotable traits for Iter<'a, Key, Value>impl<'a, Key, Value> Iterator for Iter<'a, Key, Value> type Item = (&'a Key, &'a Value);
fn iter(&self) -> Iter<'_, Key, Value>ⓘNotable traits for Iter<'a, Key, Value>impl<'a, Key, Value> Iterator for Iter<'a, Key, Value> type Item = (&'a Key, &'a Value);
sourcefn extend<IntoIter: IntoIterator<Item = (Key, Value)>>(
&mut self,
iterator: IntoIter
)
fn extend<IntoIter: IntoIterator<Item = (Key, Value)>>(
&mut self,
iterator: IntoIter
)
iterator
into this map. If there are more
entries in the iterator than capacity remaining, keys will be evicted as
needed. Read more