#![deny(
missing_docs,
missing_debug_implementations,
missing_copy_implementations,
trivial_casts,
trivial_numeric_casts,
unsafe_code,
unstable_features,
unused_import_braces,
unused_qualifications,
clippy::all
)]
#![warn(clippy::pedantic)]
use std::borrow::Borrow;
use std::fmt;
use std::hash::{BuildHasher, Hash};
use std::iter;
use linked_hash_map::LinkedHashMap;
use std::collections::hash_map::RandomState;
#[derive(Clone, PartialEq, Eq)]
pub struct Cache<K: Eq + Hash, V, S: BuildHasher = RandomState> {
recent: LinkedHashMap<K, V, S>,
frequent: LinkedHashMap<K, V, S>,
ghost: LinkedHashMap<K, (), S>,
size: usize,
ghost_size: usize,
}
impl<K: Eq + Hash, V> Cache<K, V, RandomState> {
pub fn new(size: usize) -> Self {
Self::with_hasher(size, RandomState::new())
}
}
impl<K: Eq + Hash, V, S: BuildHasher + Clone> Cache<K, V, S> {
pub fn with_hasher(size: usize, hash_builder: S) -> Self {
assert!(size > 0);
let ghost_size = size * 4;
Self {
recent: LinkedHashMap::with_capacity_and_hasher(size, hash_builder.clone()),
frequent: LinkedHashMap::with_capacity_and_hasher(size, hash_builder.clone()),
ghost: LinkedHashMap::with_capacity_and_hasher(ghost_size, hash_builder),
size,
ghost_size,
}
}
}
impl<K: Eq + Hash, V, S: BuildHasher> Cache<K, V, S> {
pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
where
K: Borrow<Q>,
Q: Eq + Hash,
{
self.recent.contains_key(key) || self.frequent.contains_key(key)
}
pub fn peek<Q: ?Sized>(&self, key: &Q) -> Option<&V>
where
K: Borrow<Q>,
Q: Eq + Hash,
{
self.recent.get(key).or_else(|| self.frequent.get(key))
}
pub fn get<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
where
K: Borrow<Q>,
Q: Eq + Hash,
{
if let Some(value) = self.recent.get_refresh(key) {
return Some(value);
}
self.frequent.get_refresh(key)
}
pub fn insert(&mut self, key: K, value: V) -> Option<V> {
match self.entry(key) {
Entry::Occupied(mut entry) => Some(entry.insert(value)),
Entry::Vacant(entry) => {
entry.insert(value);
None
}
}
}
pub fn peek_entry(&mut self, key: K) -> Entry<K, V, S> {
if self.recent.contains_key(&key) {
return Entry::Occupied(OccupiedEntry::new(OccupiedKind::Recent, key, &mut self.recent));
}
if self.frequent.contains_key(&key) {
return Entry::Occupied(OccupiedEntry::new(OccupiedKind::Frequent, key, &mut self.frequent));
}
if self.ghost.contains_key(&key) {
return Entry::Vacant(VacantEntry {
cache: self,
kind: VacantKind::Ghost,
key,
});
}
Entry::Vacant(VacantEntry {
cache: self,
kind: VacantKind::Unknown,
key,
})
}
pub fn entry(&mut self, key: K) -> Entry<K, V, S> {
if self.recent.get_refresh(&key).is_some() {
return Entry::Occupied(OccupiedEntry::new(OccupiedKind::Recent, key, &mut self.recent));
}
if self.frequent.get_refresh(&key).is_some() {
return Entry::Occupied(OccupiedEntry::new(OccupiedKind::Frequent, key, &mut self.frequent));
}
if self.ghost.contains_key(&key) {
return Entry::Vacant(VacantEntry {
cache: self,
kind: VacantKind::Ghost,
key,
});
}
Entry::Vacant(VacantEntry {
cache: self,
kind: VacantKind::Unknown,
key,
})
}
pub fn len(&self) -> usize {
self.recent.len() + self.frequent.len()
}
pub fn is_empty(&self) -> bool {
self.recent.is_empty() && self.frequent.is_empty()
}
pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
where
K: Borrow<Q>,
Q: Eq + Hash,
{
self.recent
.remove(key)
.or_else(|| self.frequent.remove(key))
}
pub fn clear(&mut self) {
self.recent.clear();
self.ghost.clear();
self.frequent.clear();
}
pub fn iter(&self) -> Iter<K, V> {
Iter {
inner: self.recent.iter().chain(self.frequent.iter()),
}
}
}
impl<'a, K: 'a + Eq + Hash, V: 'a> IntoIterator for &'a Cache<K, V> {
type Item = (&'a K, &'a V);
type IntoIter = Iter<'a, K, V>;
fn into_iter(self) -> Iter<'a, K, V> {
self.iter()
}
}
impl<K: Eq + Hash + fmt::Debug, V: fmt::Debug, S: BuildHasher> fmt::Debug for Cache<K, V, S> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_map().entries(self.iter()).finish()
}
}
pub enum Entry<'a, K: 'a + Eq + Hash, V: 'a, S: 'a + BuildHasher = RandomState> {
Occupied(OccupiedEntry<'a, K, V, S>),
Vacant(VacantEntry<'a, K, V, S>),
}
impl<'a, K: 'a + fmt::Debug + Eq + Hash, V: 'a + fmt::Debug, S: 'a + BuildHasher> fmt::Debug
for Entry<'a, K, V, S>
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match *self {
Entry::Vacant(ref v) => f.debug_tuple("Entry").field(v).finish(),
Entry::Occupied(ref o) => f.debug_tuple("Entry").field(o).finish(),
}
}
}
impl<'a, K: 'a + Eq + Hash, V: 'a, S: 'a + BuildHasher> Entry<'a, K, V, S> {
pub fn key(&self) -> &K {
match *self {
Entry::Occupied(ref entry) => entry.key(),
Entry::Vacant(ref entry) => entry.key(),
}
}
pub fn or_insert(self, default: V) -> &'a mut V {
match self {
Entry::Occupied(entry) => entry.into_mut(),
Entry::Vacant(entry) => entry.insert(default),
}
}
pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
match self {
Entry::Occupied(entry) => entry.into_mut(),
Entry::Vacant(entry) => entry.insert(default()),
}
}
pub fn and_modify<F>(self, f: F) -> Self
where
F: FnOnce(&mut V),
{
match self {
Entry::Occupied(mut entry) => {
f(entry.get_mut());
Entry::Occupied(entry)
},
Entry::Vacant(entry) => Entry::Vacant(entry)
}
}
}
impl<'a, K: 'a + Eq + Hash, V: 'a + Default, S: 'a + BuildHasher> Entry<'a, K, V, S> {
pub fn or_default(self) -> &'a mut V {
match self {
Entry::Occupied(entry) => entry.into_mut(),
Entry::Vacant(entry) => entry.insert(V::default()),
}
}
}
pub struct OccupiedEntry<'a, K: 'a + Eq + Hash, V: 'a, S: 'a = RandomState> {
kind: OccupiedKind,
entry: linked_hash_map::OccupiedEntry<'a, K, V, S>,
}
impl<'a, K: 'a + fmt::Debug + Eq + Hash, V: 'a + fmt::Debug, S: 'a + BuildHasher> fmt::Debug
for OccupiedEntry<'a, K, V, S>
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_struct("OccupiedEntry")
.field("key", self.key())
.field("value", self.get())
.field(
"kind",
&if self.kind == OccupiedKind::Frequent {
"frequent"
} else {
"recent"
},
)
.finish()
}
}
impl<'a, K: 'a + Eq + Hash, V: 'a, S: 'a + BuildHasher> OccupiedEntry<'a, K, V, S> {
fn new(kind: OccupiedKind, key: K, map: &'a mut LinkedHashMap<K, V, S>) -> Self {
let entry = match map.entry(key) {
linked_hash_map::Entry::Occupied(entry) => entry,
linked_hash_map::Entry::Vacant(_) => panic!("Expected entry for key"),
};
Self {
kind,
entry,
}
}
pub fn key(&self) -> &K {
self.entry.key()
}
pub fn get(&self) -> &V {
self.entry.get()
}
pub fn get_mut(&mut self) -> &mut V {
self.entry.get_mut()
}
pub fn into_mut(self) -> &'a mut V {
self.entry.into_mut()
}
pub fn insert(&mut self, value: V) -> V {
self.entry.insert(value)
}
pub fn remove(self) -> V {
self.entry.remove()
}
}
pub struct VacantEntry<'a, K: 'a + Eq + Hash, V: 'a, S: 'a + BuildHasher = RandomState> {
cache: &'a mut Cache<K, V, S>,
kind: VacantKind,
key: K,
}
impl<'a, K: 'a + fmt::Debug + Eq + Hash, V: 'a + fmt::Debug, S: 'a + BuildHasher> fmt::Debug
for VacantEntry<'a, K, V, S>
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_struct("VacantEntry")
.field("key", self.key())
.field("remembered", &(self.kind == VacantKind::Ghost))
.finish()
}
}
impl<'a, K: 'a + Eq + Hash, V: 'a, S: 'a + BuildHasher> VacantEntry<'a, K, V, S> {
pub fn key(&self) -> &K {
&self.key
}
pub fn into_key(self) -> K {
self.key
}
pub fn is_remembered(&self) -> bool {
self.kind == VacantKind::Ghost
}
}
impl<'a, K: 'a + Eq + Hash, V: 'a, S: 'a + BuildHasher> VacantEntry<'a, K, V, S> {
pub fn insert(self, value: V) -> &'a mut V {
let VacantEntry { cache, key, kind } = self;
match kind {
VacantKind::Ghost => {
cache.ghost.remove(&key).expect("No ghost with key");
if cache.frequent.len() + 1 > cache.size {
cache.frequent.pop_front();
}
cache.frequent.entry(key).or_insert(value)
}
VacantKind::Unknown => {
if cache.recent.len() + 1 > cache.size {
let (old_key, _) = cache.recent.pop_front().unwrap();
if cache.ghost.len() + 1 > cache.ghost_size {
cache.ghost.pop_back();
}
cache.ghost.insert(old_key, ());
}
cache.recent.entry(key).or_insert(value)
}
}
}
}
type InnerIter<'a, K, V> =
iter::Chain<linked_hash_map::Iter<'a, K, V>, linked_hash_map::Iter<'a, K, V>>;
pub struct Iter<'a, K: 'a, V: 'a> {
inner: InnerIter<'a, K, V>,
}
impl<'a, K: 'a, V: 'a> Clone for Iter<'a, K, V> {
fn clone(&self) -> Self {
Iter {
inner: self.inner.clone(),
}
}
}
impl<'a, K: 'a + fmt::Debug, V: 'a + fmt::Debug> fmt::Debug for Iter<'a, K, V> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_list().entries(self.clone()).finish()
}
}
impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
type Item = (&'a K, &'a V);
fn next(&mut self) -> Option<Self::Item> {
self.inner.next()
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
fn count(self) -> usize {
self.inner.count()
}
fn last(self) -> Option<Self::Item> {
self.inner.last()
}
fn nth(&mut self, n: usize) -> Option<Self::Item> {
self.inner.nth(n)
}
fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
where
P: FnMut(&Self::Item) -> bool,
{
self.inner.find(predicate)
}
}
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
enum VacantKind {
Ghost,
Unknown,
}
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
enum OccupiedKind {
Recent,
Frequent,
}
#[cfg(test)]
mod tests {
use super::Cache;
#[test]
fn expected_sizes() {
let cache: Cache<u8, u8> = Cache::new(16);
assert_eq!(cache.size, 16);
assert_eq!(cache.ghost_size, 16 * 4);
}
#[test]
fn cache_zero_sized_entries() {
let mut cache = Cache::new(8);
for _ in 0..1024 {
cache.entry(()).or_insert_with(|| ());
}
}
#[test]
fn get_borrowed() {
let mut cache = Cache::new(8);
cache.entry("hi".to_string()).or_insert(0);
cache.entry("there".to_string()).or_insert(0);
assert_eq!(*cache.get("hi").unwrap(), 0);
}
#[test]
#[should_panic]
fn empty_cache() {
Cache::<(), ()>::new(0);
}
#[test]
fn size_1_cache() {
let mut cache = Cache::new(1);
cache.insert(100, "value");
assert_eq!(cache.get(&100), Some(&mut "value"));
cache.insert(200, "other");
assert_eq!(cache.get(&200), Some(&mut "other"));
assert_eq!(cache.get(&100), None);
assert!(cache.ghost.contains_key(&100));
cache.insert(10, "value");
assert_eq!(cache.get(&10), Some(&mut "value"));
assert!(cache.ghost.contains_key(&100));
assert!(cache.ghost.contains_key(&200));
cache.insert(20, "other");
assert_eq!(cache.get(&20), Some(&mut "other"));
assert_eq!(cache.get(&10), None);
assert_eq!(cache.get(&100), None);
}
#[test]
fn frequents() {
let mut cache = Cache::new(2);
cache.insert(100, "100");
cache.insert(200, "200");
assert_eq!(
cache.recent.iter().collect::<Vec<_>>(),
vec![(&100, &"100"), (&200, &"200")]
);
cache.insert(300, "300");
assert_eq!(
cache.recent.iter().collect::<Vec<_>>(),
vec![(&200, &"200"), (&300, &"300")]
);
assert_eq!(cache.ghost.iter().collect::<Vec<_>>(), vec![(&100, &())]);
cache.insert(400, "400");
assert_eq!(
cache.recent.iter().collect::<Vec<_>>(),
vec![(&300, &"300"), (&400, &"400")]
);
assert_eq!(
cache.ghost.iter().collect::<Vec<_>>(),
vec![(&100, &()), (&200, &())]
);
cache.insert(100, "100");
assert_eq!(
cache.recent.iter().collect::<Vec<_>>(),
vec![(&300, &"300"), (&400, &"400")]
);
assert_eq!(cache.ghost.iter().collect::<Vec<_>>(), vec![(&200, &())]);
assert_eq!(
cache.frequent.iter().collect::<Vec<_>>(),
vec![(&100, &"100")]
);
for x in 500..600 {
cache.insert(x, "junk");
}
assert_eq!(cache.get(&100), Some(&mut "100"));
}
}