#![deny(missing_docs)]
#![deny(unsafe_code)]
#![deny(warnings)]
mod config;
mod list;
mod weight;
pub use crate::config::*;
use crate::list::{FixedSizeList, FixedSizeListIter, FixedSizeListIterMut};
pub use crate::weight::*;
use std::borrow::Borrow;
use std::collections::hash_map::Entry;
use std::collections::hash_map::RandomState;
use std::collections::HashMap;
use std::hash::{BuildHasher, Hash};
use std::iter::FromIterator;
use std::num::NonZeroUsize;
#[derive(Debug)]
struct CLruNode<K, V> {
key: K,
value: V,
}
#[derive(Debug)]
pub struct CLruCache<K, V, S = RandomState, W: WeightScale<K, V> = ZeroWeightScale> {
lookup: HashMap<K, usize, S>,
storage: FixedSizeList<CLruNode<K, V>>,
scale: W,
weight: usize,
}
impl<K: Eq + Hash, V> CLruCache<K, V> {
pub fn new(capacity: NonZeroUsize) -> Self {
Self {
lookup: HashMap::new(),
storage: FixedSizeList::new(capacity.get()),
scale: ZeroWeightScale,
weight: 0,
}
}
pub fn with_memory(capacity: NonZeroUsize, mut reserve: usize) -> Self {
if reserve > capacity.get() {
reserve = capacity.get();
}
Self {
lookup: HashMap::with_capacity(reserve),
storage: FixedSizeList::with_memory(capacity.get(), reserve),
scale: ZeroWeightScale,
weight: 0,
}
}
}
impl<K: Eq + Hash, V, S: BuildHasher> CLruCache<K, V, S> {
pub fn with_hasher(capacity: NonZeroUsize, hash_builder: S) -> CLruCache<K, V, S> {
Self {
lookup: HashMap::with_hasher(hash_builder),
storage: FixedSizeList::new(capacity.get()),
scale: ZeroWeightScale,
weight: 0,
}
}
}
impl<K: Eq + Hash, V, W: WeightScale<K, V>> CLruCache<K, V, RandomState, W> {
pub fn with_scale(capacity: NonZeroUsize, scale: W) -> CLruCache<K, V, RandomState, W> {
Self {
lookup: HashMap::with_hasher(RandomState::default()),
storage: FixedSizeList::new(capacity.get()),
scale,
weight: 0,
}
}
}
impl<K: Clone + Eq + Hash, V, S: BuildHasher, W: WeightScale<K, V>> CLruCache<K, V, S, W> {
pub fn with_config(config: CLruCacheConfig<K, V, S, W>) -> Self {
let CLruCacheConfig {
capacity,
hash_builder,
reserve,
scale,
..
} = config;
Self {
lookup: HashMap::with_hasher(hash_builder),
storage: if let Some(reserve) = reserve {
FixedSizeList::with_memory(capacity.get(), reserve)
} else {
FixedSizeList::new(capacity.get())
},
scale,
weight: 0,
}
}
#[inline]
pub fn len(&self) -> usize {
debug_assert_eq!(self.lookup.len(), self.storage.len());
self.storage.len()
}
#[inline]
pub fn capacity(&self) -> usize {
self.storage.capacity()
}
#[inline]
pub fn weight(&self) -> usize {
self.weight
}
#[inline]
pub fn is_empty(&self) -> bool {
debug_assert_eq!(self.lookup.is_empty(), self.storage.is_empty());
self.storage.is_empty()
}
#[inline]
pub fn is_full(&self) -> bool {
self.len() + self.weight() == self.capacity()
}
pub fn front(&self) -> Option<(&K, &V)> {
self.storage
.front()
.map(|CLruNode { key, value }| (key, value))
}
pub fn back(&self) -> Option<(&K, &V)> {
self.storage
.back()
.map(|CLruNode { key, value }| (key, value))
}
pub fn put_with_weight(&mut self, key: K, value: V) -> Result<Option<V>, (K, V)> {
let weight = self.scale.weight(&key, &value);
if weight >= self.capacity() {
return Err((key, value));
}
match self.lookup.entry(key) {
Entry::Occupied(mut occ) => {
let mut keys = Vec::new();
let old = self.storage.remove(*occ.get()).unwrap();
self.weight -= self.scale.weight(&old.key, &old.value);
while self.storage.len() + self.weight + weight >= self.storage.capacity() {
let node = self.storage.pop_back().unwrap();
self.weight -= self.scale.weight(&node.key, &node.value);
keys.push(node.key);
}
let (idx, _) = self
.storage
.push_front(CLruNode {
key: occ.key().clone(),
value,
})
.unwrap();
occ.insert(idx);
self.weight += weight;
for key in keys.drain(..) {
self.lookup.remove(&key);
}
Ok(Some(old.value))
}
Entry::Vacant(vac) => {
let mut keys = Vec::new();
while self.storage.len() + self.weight + weight >= self.storage.capacity() {
let node = self.storage.pop_back().unwrap();
self.weight -= self.scale.weight(&node.key, &node.value);
keys.push(node.key);
}
let (idx, _) = self
.storage
.push_front(CLruNode {
key: vac.key().clone(),
value,
})
.unwrap();
vac.insert(idx);
self.weight += weight;
for key in keys.drain(..) {
self.lookup.remove(&key);
}
Ok(None)
}
}
}
pub fn get<Q: ?Sized>(&mut self, key: &Q) -> Option<&V>
where
K: Borrow<Q>,
Q: Hash + Eq,
{
let idx = *self.lookup.get(key)?;
self.storage.move_front(idx).map(|node| &node.value)
}
pub fn pop<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
where
K: Borrow<Q>,
Q: Hash + Eq,
{
let idx = self.lookup.remove(key)?;
self.storage.remove(idx).map(|CLruNode { key, value, .. }| {
self.weight -= self.scale.weight(&key, &value);
value
})
}
pub fn pop_front(&mut self) -> Option<(K, V)> {
if let Some(CLruNode { key, value }) = self.storage.pop_front() {
self.lookup.remove(&key).unwrap();
self.weight -= self.scale.weight(&key, &value);
Some((key, value))
} else {
None
}
}
pub fn pop_back(&mut self) -> Option<(K, V)> {
if let Some(CLruNode { key, value }) = self.storage.pop_back() {
self.lookup.remove(&key).unwrap();
self.weight -= self.scale.weight(&key, &value);
Some((key, value))
} else {
None
}
}
pub fn peek<Q: ?Sized>(&self, key: &Q) -> Option<&V>
where
K: Borrow<Q>,
Q: Hash + Eq,
{
let idx = *self.lookup.get(key)?;
self.storage.get(idx).map(|node| &node.value)
}
pub fn contains<Q: ?Sized>(&mut self, key: &Q) -> bool
where
K: Borrow<Q>,
Q: Hash + Eq,
{
self.peek(key).is_some()
}
#[inline]
pub fn clear(&mut self) {
self.lookup.clear();
self.storage.clear();
self.weight = 0;
}
pub fn resize(&mut self, capacity: NonZeroUsize) {
while capacity.get() < self.storage.len() + self.weight() {
if let Some(CLruNode { key, value }) = self.storage.pop_back() {
self.lookup.remove(&key).unwrap();
self.weight -= self.scale.weight(&key, &value);
}
}
self.storage.resize(capacity.get());
for i in 0..self.len() {
let data = self.storage.get(i).unwrap();
*self.lookup.get_mut(&data.key).unwrap() = i;
}
}
pub fn retain<F>(&mut self, mut f: F)
where
F: FnMut(&K, &V) -> bool,
{
self.storage.retain(
#[inline]
|CLruNode { ref key, ref value }| {
if f(key, value) {
true
} else {
self.lookup.remove(key).unwrap();
false
}
},
)
}
}
impl<K, V, S, W: WeightScale<K, V>> CLruCache<K, V, S, W> {
pub fn iter(&self) -> CLruCacheIter<'_, K, V> {
CLruCacheIter {
iter: self.storage.iter(),
}
}
}
impl<K: Clone + Eq + Hash, V, S: BuildHasher> CLruCache<K, V, S> {
pub fn put(&mut self, key: K, value: V) -> Option<V> {
match self.lookup.entry(key) {
Entry::Occupied(occ) => {
let node = self.storage.move_front(*occ.get()).unwrap();
Some(std::mem::replace(&mut node.value, value))
}
Entry::Vacant(vac) => {
let key = vac.key().clone();
if self.storage.is_full() {
let idx = self.storage.back_idx();
let node = self.storage.move_front(idx).unwrap();
let obsolete_key = std::mem::replace(node, CLruNode { key, value }).key;
vac.insert(idx);
self.lookup.remove(&obsolete_key);
} else {
let (idx, _) = self.storage.push_front(CLruNode { key, value }).unwrap();
vac.insert(idx);
}
None
}
}
}
pub fn put_or_modify<T, P: FnMut(&K, T) -> V, M: FnMut(&K, &mut V, T)>(
&mut self,
key: K,
mut put_op: P,
mut modify_op: M,
data: T,
) -> &mut V {
match self.lookup.entry(key) {
Entry::Occupied(occ) => {
let node = self.storage.move_front(*occ.get()).unwrap();
modify_op(&node.key, &mut node.value, data);
&mut node.value
}
Entry::Vacant(vac) => {
let key = vac.key().clone();
let value = put_op(&key, data);
if self.storage.is_full() {
let index = self.storage.back_idx();
let node = self.storage.move_front(index).unwrap();
let obsolete_key = std::mem::replace(node, CLruNode { key, value }).key;
vac.insert(index);
self.lookup.remove(&obsolete_key);
&mut node.value
} else {
let (idx, node) = self.storage.push_front(CLruNode { key, value }).unwrap();
vac.insert(idx);
&mut node.value
}
}
}
}
pub fn try_put_or_modify<
T,
E,
P: FnMut(&K, T) -> Result<V, E>,
M: FnMut(&K, &mut V, T) -> Result<(), E>,
>(
&mut self,
key: K,
mut put_op: P,
mut modify_op: M,
data: T,
) -> Result<&mut V, E> {
match self.lookup.entry(key) {
Entry::Occupied(occ) => {
let node = self.storage.move_front(*occ.get()).unwrap();
match modify_op(&node.key, &mut node.value, data) {
Ok(()) => Ok(&mut node.value),
Err(err) => Err(err),
}
}
Entry::Vacant(vac) => {
let value = match put_op(vac.key(), data) {
Ok(value) => value,
Err(err) => return Err(err),
};
let key = vac.key().clone();
if self.storage.is_full() {
let idx = self.storage.back_idx();
let node = self.storage.move_front(idx).unwrap();
let obsolete_key = std::mem::replace(node, CLruNode { key, value }).key;
vac.insert(idx);
self.lookup.remove(&obsolete_key);
Ok(&mut node.value)
} else {
let (idx, node) = self.storage.push_front(CLruNode { key, value }).unwrap();
vac.insert(idx);
Ok(&mut node.value)
}
}
}
}
pub fn front_mut(&mut self) -> Option<(&K, &mut V)> {
self.storage
.front_mut()
.map(|CLruNode { key, value }| (&*key, value))
}
pub fn back_mut(&mut self) -> Option<(&K, &mut V)> {
self.storage
.back_mut()
.map(|CLruNode { key, value }| (&*key, value))
}
pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
where
K: Borrow<Q>,
Q: Hash + Eq,
{
let idx = *self.lookup.get(key)?;
self.storage.move_front(idx).map(|node| &mut node.value)
}
pub fn peek_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
where
K: Borrow<Q>,
Q: Hash + Eq,
{
let idx = *self.lookup.get(key)?;
self.storage.get_mut(idx).map(|node| &mut node.value)
}
pub fn retain_mut<F>(&mut self, mut f: F)
where
F: FnMut(&K, &mut V) -> bool,
{
self.storage.retain_mut(
#[inline]
|CLruNode {
ref key,
ref mut value,
}| {
if f(key, value) {
true
} else {
self.lookup.remove(key).unwrap();
false
}
},
)
}
}
impl<K, V, S> CLruCache<K, V, S> {
pub fn iter_mut(&mut self) -> CLruCacheIterMut<'_, K, V> {
CLruCacheIterMut {
iter: self.storage.iter_mut(),
}
}
}
#[derive(Clone, Debug)]
pub struct CLruCacheIter<'a, K, V> {
iter: FixedSizeListIter<'a, CLruNode<K, V>>,
}
impl<'a, K, V> Iterator for CLruCacheIter<'a, K, V> {
type Item = (&'a K, &'a V);
fn next(&mut self) -> Option<Self::Item> {
self.iter
.next()
.map(|(_, CLruNode { key, value })| (key.borrow(), value))
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
impl<'a, K, V> DoubleEndedIterator for CLruCacheIter<'a, K, V> {
fn next_back(&mut self) -> Option<Self::Item> {
self.iter
.next_back()
.map(|(_, CLruNode { key, value })| (key.borrow(), value))
}
}
impl<'a, K, V> ExactSizeIterator for CLruCacheIter<'a, K, V> {
fn len(&self) -> usize {
self.iter.len()
}
}
impl<'a, K, V, S, W: WeightScale<K, V>> IntoIterator for &'a CLruCache<K, V, S, W> {
type Item = (&'a K, &'a V);
type IntoIter = CLruCacheIter<'a, K, V>;
#[inline]
fn into_iter(self) -> CLruCacheIter<'a, K, V> {
self.iter()
}
}
pub struct CLruCacheIterMut<'a, K, V> {
iter: FixedSizeListIterMut<'a, CLruNode<K, V>>,
}
impl<'a, K, V> Iterator for CLruCacheIterMut<'a, K, V> {
type Item = (&'a K, &'a mut V);
fn next(&mut self) -> Option<Self::Item> {
self.iter
.next()
.map(|(_, CLruNode { key, value })| (&*key, value))
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
impl<'a, K, V> DoubleEndedIterator for CLruCacheIterMut<'a, K, V> {
fn next_back(&mut self) -> Option<Self::Item> {
self.iter
.next_back()
.map(|(_, CLruNode { key, value })| (&*key, value))
}
}
impl<'a, K, V> ExactSizeIterator for CLruCacheIterMut<'a, K, V> {
fn len(&self) -> usize {
self.iter.len()
}
}
impl<'a, K, V, S> IntoIterator for &'a mut CLruCache<K, V, S> {
type Item = (&'a K, &'a mut V);
type IntoIter = CLruCacheIterMut<'a, K, V>;
#[inline]
fn into_iter(self) -> CLruCacheIterMut<'a, K, V> {
self.iter_mut()
}
}
pub struct CLruCacheIntoIter<K, V, S, W: WeightScale<K, V>> {
cache: CLruCache<K, V, S, W>,
}
impl<K: Clone + Eq + Hash, V, S: BuildHasher, W: WeightScale<K, V>> Iterator
for CLruCacheIntoIter<K, V, S, W>
{
type Item = (K, V);
#[inline]
fn next(&mut self) -> Option<(K, V)> {
self.cache.pop_front()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
(self.cache.len(), Some(self.cache.len()))
}
}
impl<K: Clone + Eq + Hash, V, S: BuildHasher, W: WeightScale<K, V>> DoubleEndedIterator
for CLruCacheIntoIter<K, V, S, W>
{
fn next_back(&mut self) -> Option<Self::Item> {
self.cache.pop_back()
}
}
impl<K: Clone + Eq + Hash, V, S: BuildHasher, W: WeightScale<K, V>> ExactSizeIterator
for CLruCacheIntoIter<K, V, S, W>
{
fn len(&self) -> usize {
self.size_hint().0
}
}
impl<K: Clone + Eq + Hash, V, S: BuildHasher, W: WeightScale<K, V>> IntoIterator
for CLruCache<K, V, S, W>
{
type Item = (K, V);
type IntoIter = CLruCacheIntoIter<K, V, S, W>;
#[inline]
fn into_iter(self) -> CLruCacheIntoIter<K, V, S, W> {
CLruCacheIntoIter { cache: self }
}
}
impl<K: Clone + Eq + Hash, V, S: BuildHasher + Default> FromIterator<(K, V)>
for CLruCache<K, V, S>
{
fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
let cap = NonZeroUsize::new(usize::MAX).unwrap();
let mut cache = CLruCache::with_hasher(cap, S::default());
for (k, v) in iter {
cache.put(k, v);
}
cache.resize(
NonZeroUsize::new(cache.len()).unwrap_or_else(|| NonZeroUsize::new(1).unwrap()),
);
cache
}
}
impl<K: Clone + Eq + Hash, V, S: BuildHasher> Extend<(K, V)> for CLruCache<K, V, S> {
fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
for (k, v) in iter {
self.put(k, v);
}
}
}
#[cfg(test)]
#[allow(clippy::bool_assert_comparison)]
mod tests {
use super::*;
#[allow(unsafe_code)]
const ONE: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(1) };
#[allow(unsafe_code)]
const TWO: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(2) };
#[allow(unsafe_code)]
const THREE: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(3) };
#[allow(unsafe_code)]
const FOUR: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(4) };
#[allow(unsafe_code)]
const FIVE: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(5) };
#[allow(unsafe_code)]
const SIX: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(6) };
#[allow(unsafe_code)]
const HEIGHT: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(8) };
#[allow(unsafe_code)]
const MANY: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(200) };
#[test]
fn test_insert_and_get() {
let mut cache = CLruCache::new(TWO);
assert!(cache.is_empty());
assert_eq!(cache.put("apple", "red"), None);
assert_eq!(cache.put("banana", "yellow"), None);
assert_eq!(cache.capacity(), 2);
assert_eq!(cache.len(), 2);
assert!(!cache.is_empty());
assert!(cache.is_full());
assert_eq!(cache.get(&"apple"), Some(&"red"));
assert_eq!(cache.get(&"banana"), Some(&"yellow"));
}
#[test]
fn test_insert_and_get_mut() {
let mut cache = CLruCache::new(TWO);
cache.put("apple", "red");
cache.put("banana", "yellow");
assert_eq!(cache.capacity(), 2);
assert_eq!(cache.len(), 2);
assert!(!cache.is_empty());
assert!(cache.is_full());
assert_eq!(cache.get_mut(&"apple"), Some(&mut "red"));
assert_eq!(cache.get_mut(&"banana"), Some(&mut "yellow"));
}
#[test]
fn test_get_mut_and_update() {
let mut cache = CLruCache::new(TWO);
cache.put("apple", 1);
cache.put("banana", 3);
{
let v = cache.get_mut(&"apple").unwrap();
*v = 4;
}
assert_eq!(cache.capacity(), 2);
assert_eq!(cache.len(), 2);
assert!(!cache.is_empty());
assert!(cache.is_full());
assert_eq!(cache.get_mut(&"apple"), Some(&mut 4));
assert_eq!(cache.get_mut(&"banana"), Some(&mut 3));
}
#[test]
fn test_insert_update() {
let mut cache = CLruCache::new(ONE);
assert_eq!(cache.put("apple", "red"), None);
assert_eq!(cache.put("apple", "green"), Some("red"));
assert_eq!(cache.len(), 1);
assert_eq!(cache.get(&"apple"), Some(&"green"));
}
#[test]
fn test_insert_removes_oldest() {
let mut cache = CLruCache::new(TWO);
assert_eq!(cache.put("apple", "red"), None);
assert_eq!(cache.put("banana", "yellow"), None);
assert_eq!(cache.put("pear", "green"), None);
assert!(cache.get(&"apple").is_none());
assert_eq!(cache.get(&"banana"), Some(&"yellow"));
assert_eq!(cache.get(&"pear"), Some(&"green"));
assert_eq!(cache.put("apple", "green"), None);
assert_eq!(cache.put("tomato", "red"), None);
assert!(cache.get(&"pear").is_none());
assert_eq!(cache.get(&"apple"), Some(&"green"));
assert_eq!(cache.get(&"tomato"), Some(&"red"));
}
#[test]
fn test_peek() {
let mut cache = CLruCache::new(TWO);
cache.put("apple", "red");
cache.put("banana", "yellow");
assert_eq!(cache.peek(&"banana"), Some(&"yellow"));
assert_eq!(cache.peek(&"apple"), Some(&"red"));
cache.put("pear", "green");
assert!(cache.peek(&"apple").is_none());
assert_eq!(cache.peek(&"banana"), Some(&"yellow"));
assert_eq!(cache.peek(&"pear"), Some(&"green"));
}
#[test]
fn test_peek_mut() {
let mut cache = CLruCache::new(TWO);
cache.put("apple", "red");
cache.put("banana", "yellow");
assert_eq!(cache.peek_mut(&"banana"), Some(&mut "yellow"));
assert_eq!(cache.peek_mut(&"apple"), Some(&mut "red"));
assert!(cache.peek_mut(&"pear").is_none());
cache.put("pear", "green");
assert!(cache.peek_mut(&"apple").is_none());
assert_eq!(cache.peek_mut(&"banana"), Some(&mut "yellow"));
assert_eq!(cache.peek_mut(&"pear"), Some(&mut "green"));
{
let v = cache.peek_mut(&"banana").unwrap();
*v = "green";
}
assert_eq!(cache.peek_mut(&"banana"), Some(&mut "green"));
}
#[test]
fn test_contains() {
let mut cache = CLruCache::new(TWO);
cache.put("apple", "red");
cache.put("banana", "yellow");
cache.put("pear", "green");
assert!(!cache.contains(&"apple"));
assert!(cache.contains(&"banana"));
assert!(cache.contains(&"pear"));
}
#[test]
fn test_pop() {
let mut cache = CLruCache::new(TWO);
cache.put("apple", "red");
cache.put("banana", "yellow");
assert_eq!(cache.len(), 2);
assert_eq!(cache.get(&"apple"), Some(&"red"));
assert_eq!(cache.get(&"banana"), Some(&"yellow"));
let popped = cache.pop(&"apple");
assert!(popped.is_some());
assert_eq!(popped.unwrap(), "red");
assert_eq!(cache.len(), 1);
assert!(cache.get(&"apple").is_none());
assert_eq!(cache.get(&"banana"), Some(&"yellow"));
}
#[test]
fn test_pop_front() {
let mut cache = CLruCache::new(MANY);
for i in 0..75 {
cache.put(i, "A");
}
for i in 0..75 {
cache.put(i + 100, "B");
}
for i in 0..75 {
cache.put(i + 200, "C");
}
assert_eq!(cache.len(), 200);
for i in 0..75 {
assert_eq!(cache.get(&(74 - i + 100)), Some(&"B"));
}
assert_eq!(cache.get(&25), Some(&"A"));
assert_eq!(cache.pop_front(), Some((25, "A")));
for i in 0..75 {
assert_eq!(cache.pop_front(), Some((i + 100, "B")));
}
for i in 0..75 {
assert_eq!(cache.pop_front(), Some((74 - i + 200, "C")));
}
for i in 0..49 {
assert_eq!(cache.pop_front(), Some((74 - i, "A")));
}
for _ in 0..50 {
assert_eq!(cache.pop_front(), None);
}
}
#[test]
fn test_pop_back() {
let mut cache = CLruCache::new(MANY);
for i in 0..75 {
cache.put(i, "A");
}
for i in 0..75 {
cache.put(i + 100, "B");
}
for i in 0..75 {
cache.put(i + 200, "C");
}
assert_eq!(cache.len(), 200);
for i in 0..75 {
assert_eq!(cache.get(&(74 - i + 100)), Some(&"B"));
}
assert_eq!(cache.get(&25), Some(&"A"));
for i in 26..75 {
assert_eq!(cache.pop_back(), Some((i, "A")));
}
for i in 0..75 {
assert_eq!(cache.pop_back(), Some((i + 200, "C")));
}
for i in 0..75 {
assert_eq!(cache.pop_back(), Some((74 - i + 100, "B")));
}
assert_eq!(cache.pop_back(), Some((25, "A")));
for _ in 0..50 {
assert_eq!(cache.pop_back(), None);
}
}
#[test]
fn test_clear() {
let mut cache = CLruCache::new(TWO);
cache.put("apple", "red");
cache.put("banana", "yellow");
assert_eq!(cache.len(), 2);
assert_eq!(cache.get(&"apple"), Some(&"red"));
assert_eq!(cache.get(&"banana"), Some(&"yellow"));
cache.clear();
assert_eq!(cache.len(), 0);
}
#[test]
fn test_resize_larger() {
let mut cache = CLruCache::new(TWO);
cache.put(1, "a");
cache.put(2, "b");
cache.resize(THREE);
assert_eq!(cache.len(), 2);
assert_eq!(cache.capacity(), 3);
cache.resize(FOUR);
assert_eq!(cache.len(), 2);
assert_eq!(cache.capacity(), 4);
cache.put(3, "c");
cache.put(4, "d");
assert_eq!(cache.len(), 4);
assert_eq!(cache.capacity(), 4);
assert_eq!(cache.get(&1), Some(&"a"));
assert_eq!(cache.get(&2), Some(&"b"));
assert_eq!(cache.get(&3), Some(&"c"));
assert_eq!(cache.get(&4), Some(&"d"));
}
#[test]
fn test_resize_smaller() {
let mut cache = CLruCache::new(FOUR);
cache.put(1, "a");
cache.put(2, "b");
cache.put(3, "c");
cache.put(4, "d");
cache.resize(TWO);
assert_eq!(cache.len(), 2);
assert_eq!(cache.capacity(), 2);
assert!(cache.get(&1).is_none());
assert!(cache.get(&2).is_none());
assert_eq!(cache.get(&3), Some(&"c"));
assert_eq!(cache.get(&4), Some(&"d"));
}
#[test]
fn test_resize_equal() {
let mut cache = CLruCache::new(FOUR);
cache.put(1, "a");
cache.put(2, "b");
cache.put(3, "c");
cache.put(4, "d");
cache.resize(FOUR);
assert_eq!(cache.len(), 4);
assert_eq!(cache.capacity(), 4);
assert_eq!(cache.get(&1), Some(&"a"));
assert_eq!(cache.get(&2), Some(&"b"));
assert_eq!(cache.get(&3), Some(&"c"));
assert_eq!(cache.get(&4), Some(&"d"));
}
#[test]
fn test_iter_forwards() {
let mut cache = CLruCache::new(THREE);
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);
{
let mut iter = cache.iter();
assert_eq!(iter.len(), 3);
assert_eq!(iter.next(), Some((&"c", &3)));
assert_eq!(iter.len(), 2);
assert_eq!(iter.next(), Some((&"b", &2)));
assert_eq!(iter.len(), 1);
assert_eq!(iter.next(), Some((&"a", &1)));
assert_eq!(iter.len(), 0);
assert_eq!(iter.next(), None);
}
{
let mut iter = cache.iter_mut();
assert_eq!(iter.len(), 3);
assert_eq!(iter.next(), Some((&"c", &mut 3)));
assert_eq!(iter.len(), 2);
assert_eq!(iter.next(), Some((&"b", &mut 2)));
assert_eq!(iter.len(), 1);
assert_eq!(iter.next(), Some((&"a", &mut 1)));
assert_eq!(iter.len(), 0);
assert_eq!(iter.next(), None);
let mut vec: Vec<_> = cache.iter_mut().collect();
vec.iter_mut().for_each(|(_, v)| {
**v -= 1;
});
assert_eq!(vec, vec![(&"c", &mut 2), (&"b", &mut 1), (&"a", &mut 0)]);
}
}
#[test]
fn test_iter_backwards() {
let mut cache = CLruCache::new(THREE);
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);
{
let mut iter = cache.iter();
assert_eq!(iter.len(), 3);
assert_eq!(iter.next_back(), Some((&"a", &1)));
assert_eq!(iter.len(), 2);
assert_eq!(iter.next_back(), Some((&"b", &2)));
assert_eq!(iter.len(), 1);
assert_eq!(iter.next_back(), Some((&"c", &3)));
assert_eq!(iter.len(), 0);
assert_eq!(iter.next_back(), None);
}
{
let mut iter = cache.iter_mut();
assert_eq!(iter.len(), 3);
assert_eq!(iter.next_back(), Some((&"a", &mut 1)));
assert_eq!(iter.len(), 2);
assert_eq!(iter.next_back(), Some((&"b", &mut 2)));
assert_eq!(iter.len(), 1);
assert_eq!(iter.next_back(), Some((&"c", &mut 3)));
assert_eq!(iter.len(), 0);
assert_eq!(iter.next_back(), None);
let mut vec: Vec<_> = cache.iter_mut().rev().collect();
vec.iter_mut().for_each(|(_, v)| {
**v -= 1;
});
assert_eq!(vec, vec![(&"a", &mut 0), (&"b", &mut 1), (&"c", &mut 2)]);
}
}
#[test]
fn test_iter_forwards_and_backwards() {
let mut cache = CLruCache::new(THREE);
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);
{
let mut iter = cache.iter();
assert_eq!(iter.len(), 3);
assert_eq!(iter.next(), Some((&"c", &3)));
assert_eq!(iter.len(), 2);
assert_eq!(iter.next_back(), Some((&"a", &1)));
assert_eq!(iter.len(), 1);
assert_eq!(iter.next(), Some((&"b", &2)));
assert_eq!(iter.len(), 0);
assert_eq!(iter.next_back(), None);
}
{
let mut iter = cache.iter_mut();
assert_eq!(iter.len(), 3);
assert_eq!(iter.next(), Some((&"c", &mut 3)));
assert_eq!(iter.len(), 2);
assert_eq!(iter.next_back(), Some((&"a", &mut 1)));
assert_eq!(iter.len(), 1);
assert_eq!(iter.next(), Some((&"b", &mut 2)));
assert_eq!(iter.len(), 0);
assert_eq!(iter.next_back(), None);
}
}
#[test]
fn test_iter_clone() {
let mut cache = CLruCache::new(THREE);
cache.put("a", 1);
cache.put("b", 2);
let mut iter = cache.iter();
let mut iter_clone = iter.clone();
assert_eq!(iter.len(), 2);
assert_eq!(iter.next(), Some((&"b", &2)));
assert_eq!(iter_clone.len(), 2);
assert_eq!(iter_clone.next(), Some((&"b", &2)));
assert_eq!(iter.len(), 1);
assert_eq!(iter.next(), Some((&"a", &1)));
assert_eq!(iter_clone.len(), 1);
assert_eq!(iter_clone.next(), Some((&"a", &1)));
assert_eq!(iter.len(), 0);
assert_eq!(iter.next(), None);
assert_eq!(iter_clone.len(), 0);
assert_eq!(iter_clone.next(), None);
}
#[test]
fn test_that_pop_actually_detaches_node() {
let mut cache = CLruCache::new(FIVE);
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);
cache.put("d", 4);
cache.put("e", 5);
assert_eq!(cache.pop(&"c"), Some(3));
cache.put("f", 6);
let mut iter = cache.iter();
assert_eq!(iter.next(), Some((&"f", &6)));
assert_eq!(iter.next(), Some((&"e", &5)));
assert_eq!(iter.next(), Some((&"d", &4)));
assert_eq!(iter.next(), Some((&"b", &2)));
assert_eq!(iter.next(), Some((&"a", &1)));
assert!(iter.next().is_none());
}
#[test]
fn test_get_with_borrow() {
let mut cache = CLruCache::new(TWO);
let key = String::from("apple");
cache.put(key, "red");
assert_eq!(cache.get("apple"), Some(&"red"));
}
#[test]
fn test_get_mut_with_borrow() {
let mut cache = CLruCache::new(TWO);
let key = String::from("apple");
cache.put(key, "red");
assert_eq!(cache.get_mut("apple"), Some(&mut "red"));
}
#[test]
#[cfg_attr(miri, ignore)]
fn test_no_memory_leaks() {
use std::sync::atomic::{AtomicUsize, Ordering};
static DROP_COUNT: AtomicUsize = AtomicUsize::new(0);
struct DropCounter;
impl Drop for DropCounter {
fn drop(&mut self) {
DROP_COUNT.fetch_add(1, Ordering::SeqCst);
}
}
let n = 100;
for _ in 0..n {
let mut cache = CLruCache::new(ONE);
for i in 0..n {
cache.put(i, DropCounter {});
}
}
assert_eq!(DROP_COUNT.load(Ordering::SeqCst), n * n);
}
#[test]
fn test_retain() {
let mut cache = CLruCache::new(FIVE);
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);
cache.put("d", 4);
cache.put("e", 5);
assert_eq!(cache.len(), 5);
cache.retain_mut(|k, v| match *k {
"b" | "d" => false,
_ => {
*v += 1;
true
}
});
assert_eq!(cache.len(), 3);
assert_eq!(cache.get("a"), Some(&2));
assert_eq!(cache.get("b"), None);
assert_eq!(cache.get("c"), Some(&4));
assert_eq!(cache.get("d"), None);
assert_eq!(cache.get("e"), Some(&6));
cache.retain(|_, _| true);
assert_eq!(cache.len(), 3);
assert_eq!(cache.get("a"), Some(&2));
assert_eq!(cache.get("b"), None);
assert_eq!(cache.get("c"), Some(&4));
assert_eq!(cache.get("d"), None);
assert_eq!(cache.get("e"), Some(&6));
cache.retain(|_, _| false);
assert_eq!(cache.len(), 0);
assert_eq!(cache.get("a"), None);
assert_eq!(cache.get("b"), None);
assert_eq!(cache.get("c"), None);
assert_eq!(cache.get("d"), None);
assert_eq!(cache.get("e"), None);
}
#[test]
fn test_into_iter() {
let mut cache = CLruCache::new(FIVE);
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);
cache.put("d", 4);
cache.put("e", 5);
let mut vec = Vec::new();
for (k, v) in &cache {
vec.push((k, v));
}
assert_eq!(
vec,
vec![(&"e", &5), (&"d", &4), (&"c", &3), (&"b", &2), (&"a", &1)]
);
let mut vec = Vec::new();
for (k, v) in &mut cache {
*v -= 1;
vec.push((k, v));
}
assert_eq!(
vec,
vec![
(&"e", &mut 4),
(&"d", &mut 3),
(&"c", &mut 2),
(&"b", &mut 1),
(&"a", &mut 0)
]
);
assert_eq!(
cache.into_iter().collect::<Vec<_>>(),
vec![("e", 4), ("d", 3), ("c", 2), ("b", 1), ("a", 0)]
);
}
#[test]
fn test_put_or_modify() {
let mut cache = CLruCache::new(TWO);
let put = |key: &&str, base: Option<usize>| base.unwrap_or(0) + key.len();
let modify = |key: &&str, value: &mut usize, base: Option<usize>| {
if key.len() == *value {
*value *= 2;
} else {
*value /= 2;
}
*value += base.unwrap_or(0);
};
assert_eq!(cache.put_or_modify("a", put, modify, None), &1);
assert_eq!(cache.len(), 1);
let mut iter = cache.iter();
assert_eq!(iter.next(), Some((&"a", &1)));
assert_eq!(iter.next(), None);
assert_eq!(cache.put_or_modify("b", put, modify, Some(3)), &4);
assert_eq!(cache.len(), 2);
let mut iter = cache.iter();
assert_eq!(iter.next(), Some((&"b", &4)));
assert_eq!(iter.next(), Some((&"a", &1)));
assert_eq!(iter.next(), None);
assert_eq!(cache.put_or_modify("a", put, modify, None), &2);
assert_eq!(cache.len(), 2);
let mut iter = cache.iter();
assert_eq!(iter.next(), Some((&"a", &2)));
assert_eq!(iter.next(), Some((&"b", &4)));
assert_eq!(iter.next(), None);
assert_eq!(cache.put_or_modify("b", put, modify, Some(3)), &5);
assert_eq!(cache.len(), 2);
let mut iter = cache.iter();
assert_eq!(iter.next(), Some((&"b", &5)));
assert_eq!(iter.next(), Some((&"a", &2)));
assert_eq!(iter.next(), None);
}
#[test]
fn test_panic_in_put_or_modify() {
use std::panic::{catch_unwind, AssertUnwindSafe};
let mut cache = CLruCache::new(TWO);
let put = |_: &&str, value: usize| value;
let modify = |_: &&str, old: &mut usize, new: usize| {
panic!("old value: {:?} / new value: {:?}", old, new);
};
assert_eq!(cache.put_or_modify("a", put, modify, 3), &3);
assert_eq!(cache.put_or_modify("b", put, modify, 5), &5);
let mut iter = cache.iter();
assert_eq!(iter.next(), Some((&"b", &5)));
assert_eq!(iter.next(), Some((&"a", &3)));
assert_eq!(iter.next(), None);
assert!(catch_unwind(AssertUnwindSafe(|| {
cache.put_or_modify("a", put, modify, 7);
}))
.is_err());
let mut iter = cache.iter();
assert_eq!(iter.next(), Some((&"a", &3)));
assert_eq!(iter.next(), Some((&"b", &5)));
assert_eq!(iter.next(), None);
let put = |_: &&str, value: usize| panic!("value: {:?}", value);
assert!(catch_unwind(AssertUnwindSafe(|| {
cache.put_or_modify("c", put, modify, 7);
}))
.is_err());
let mut iter = cache.iter();
assert_eq!(iter.next(), Some((&"a", &3)));
assert_eq!(iter.next(), Some((&"b", &5)));
assert_eq!(iter.next(), None);
}
#[test]
fn test_try_put_or_modify() {
let mut cache = CLruCache::new(TWO);
let put = |_: &&str, value: usize| {
if value % 2 == 0 {
Ok(value)
} else {
Err(value)
}
};
let modify = |_: &&str, old: &mut usize, new: usize| {
if new % 2 == 0 {
*old = new;
Ok(())
} else {
Err(new)
}
};
assert_eq!(cache.try_put_or_modify("a", put, modify, 2), Ok(&mut 2));
assert_eq!(cache.len(), 1);
let mut iter = cache.iter();
assert_eq!(iter.next(), Some((&"a", &2)));
assert_eq!(iter.next(), None);
assert_eq!(cache.try_put_or_modify("b", put, modify, 4), Ok(&mut 4));
assert_eq!(cache.len(), 2);
let mut iter = cache.iter();
assert_eq!(iter.next(), Some((&"b", &4)));
assert_eq!(iter.next(), Some((&"a", &2)));
assert_eq!(iter.next(), None);
assert_eq!(cache.try_put_or_modify("a", put, modify, 3), Err(3));
assert_eq!(cache.len(), 2);
let mut iter = cache.iter();
assert_eq!(iter.next(), Some((&"a", &2)));
assert_eq!(iter.next(), Some((&"b", &4)));
assert_eq!(iter.next(), None);
assert_eq!(cache.try_put_or_modify("c", put, modify, 3), Err(3));
assert_eq!(cache.len(), 2);
let mut iter = cache.iter();
assert_eq!(iter.next(), Some((&"a", &2)));
assert_eq!(iter.next(), Some((&"b", &4)));
assert_eq!(iter.next(), None);
}
#[test]
fn test_from_iterator() {
let cache: CLruCache<&'static str, usize> =
vec![("a", 1), ("b", 2), ("c", 3), ("d", 4), ("e", 5)]
.into_iter()
.collect();
assert_eq!(cache.len(), 5);
assert_eq!(cache.capacity(), 5);
assert_eq!(cache.is_full(), true);
assert_eq!(
cache.into_iter().collect::<Vec<_>>(),
vec![("e", 5), ("d", 4), ("c", 3), ("b", 2), ("a", 1)]
);
let cache: CLruCache<&'static str, usize> = vec![].into_iter().collect();
assert_eq!(cache.len(), 0);
assert_eq!(cache.capacity(), 1);
assert_eq!(cache.is_full(), false);
assert_eq!(cache.into_iter().collect::<Vec<_>>(), vec![]);
}
#[test]
fn test_extend() {
let mut cache = CLruCache::new(FIVE);
cache.put("a", 1);
cache.put("b", 2);
assert_eq!(cache.len(), 2);
assert_eq!(cache.capacity(), 5);
assert_eq!(cache.is_full(), false);
cache.extend(vec![("c", 3), ("d", 4), ("e", 5)].into_iter());
assert_eq!(cache.len(), 5);
assert_eq!(cache.capacity(), 5);
assert_eq!(cache.is_full(), true);
assert_eq!(
cache.into_iter().collect::<Vec<_>>(),
vec![("e", 5), ("d", 4), ("c", 3), ("b", 2), ("a", 1)]
);
}
#[derive(Debug)]
struct StrStrScale;
impl WeightScale<&str, &str> for StrStrScale {
fn weight(&self, _key: &&str, value: &&str) -> usize {
value.len()
}
}
#[test]
fn test_weighted_insert_and_get() {
let mut cache = CLruCache::with_config(
CLruCacheConfig::new(NonZeroUsize::new(11).unwrap()).with_scale(StrStrScale),
);
assert!(cache.is_empty());
assert_eq!(cache.put_with_weight("apple", "red").unwrap(), None);
assert_eq!(cache.put_with_weight("banana", "yellow").unwrap(), None);
assert_eq!(cache.capacity(), 11);
assert_eq!(cache.len(), 2);
assert_eq!(cache.weight(), 9);
assert!(!cache.is_empty());
assert!(cache.is_full()); assert_eq!(cache.get(&"apple"), Some(&"red"));
assert_eq!(cache.get(&"banana"), Some(&"yellow"));
}
#[test]
fn test_zero_weight_fails() {
let mut cache = CLruCache::with_config(
CLruCacheConfig::new(NonZeroUsize::new(3).unwrap()).with_scale(StrStrScale),
);
assert!(cache.put_with_weight("apple", "red").is_err());
assert!(cache.put_with_weight("apple", "red").is_err());
}
#[test]
fn test_greater_than_max_weight_fails() {
let mut cache = CLruCache::with_config(
CLruCacheConfig::new(NonZeroUsize::new(3).unwrap()).with_scale(StrStrScale),
);
assert!(cache.put_with_weight("apple", "red").is_err());
}
#[test]
fn test_weighted_insert_update() {
let mut cache = CLruCache::with_config(
CLruCacheConfig::new(NonZeroUsize::new(6).unwrap()).with_scale(StrStrScale),
);
assert_eq!(cache.put_with_weight("apple", "red").unwrap(), None);
assert_eq!(
cache.put_with_weight("apple", "green").unwrap(),
Some("red")
);
assert_eq!(cache.len(), 1);
assert_eq!(cache.get(&"apple"), Some(&"green"));
}
#[test]
fn test_weighted_insert_removes_oldest() {
let mut cache = CLruCache::with_config(
CLruCacheConfig::new(NonZeroUsize::new(16).unwrap()).with_scale(StrStrScale),
);
assert_eq!(cache.put_with_weight("apple", "red").unwrap(), None);
assert_eq!(cache.put_with_weight("banana", "yellow").unwrap(), None);
assert_eq!(cache.put_with_weight("pear", "green").unwrap(), None);
assert!(cache.get(&"apple").is_none());
assert_eq!(cache.get(&"banana"), Some(&"yellow"));
assert_eq!(cache.get(&"pear"), Some(&"green"));
assert_eq!(cache.len(), 2);
assert_eq!(cache.weight(), 11);
assert_eq!(cache.capacity(), 16);
assert!(!cache.is_full());
assert_eq!(cache.put_with_weight("apple", "green").unwrap(), None);
assert_eq!(cache.put_with_weight("tomato", "red").unwrap(), None);
assert_eq!(cache.len(), 3); assert_eq!(cache.weight(), 13); assert_eq!(cache.capacity(), 16);
assert!(cache.is_full());
assert_eq!(cache.get(&"pear"), Some(&"green"));
assert_eq!(cache.get(&"apple"), Some(&"green"));
assert_eq!(cache.get(&"tomato"), Some(&"red"));
}
#[test]
fn test_weighted_clear() {
let mut cache = CLruCache::with_config(
CLruCacheConfig::new(NonZeroUsize::new(10).unwrap()).with_scale(StrStrScale),
);
assert_eq!(cache.put_with_weight("apple", "red"), Ok(None));
assert_eq!(cache.put_with_weight("banana", "yellow"), Ok(None));
assert_eq!(cache.len(), 1);
assert_eq!(cache.weight(), 6);
assert_eq!(cache.get(&"apple"), None);
assert_eq!(cache.get(&"banana"), Some(&"yellow"));
cache.clear();
assert_eq!(cache.len(), 0);
assert_eq!(cache.weight(), 0);
}
#[derive(Debug)]
struct IntStrScale;
impl WeightScale<usize, &str> for IntStrScale {
fn weight(&self, _key: &usize, value: &&str) -> usize {
value.len()
}
}
#[test]
fn test_weighted_resize_larger() {
let mut cache = CLruCache::with_config(
CLruCacheConfig::new(NonZeroUsize::new(4).unwrap()).with_scale(IntStrScale),
);
assert_eq!(cache.put_with_weight(1, "a"), Ok(None));
assert_eq!(cache.put_with_weight(2, "b"), Ok(None));
assert_eq!(cache.len(), 2);
assert_eq!(cache.weight(), 2);
assert_eq!(cache.capacity(), 4);
assert!(cache.is_full());
cache.resize(SIX);
assert_eq!(cache.len(), 2);
assert_eq!(cache.weight(), 2);
assert_eq!(cache.capacity(), 6);
assert!(!cache.is_full());
cache.resize(HEIGHT);
assert_eq!(cache.len(), 2);
assert_eq!(cache.weight(), 2);
assert_eq!(cache.capacity(), 8);
assert!(!cache.is_full());
assert_eq!(cache.put_with_weight(3, "c"), Ok(None));
assert_eq!(cache.put_with_weight(4, "d"), Ok(None));
assert_eq!(cache.len(), 4);
assert_eq!(cache.weight(), 4);
assert_eq!(cache.capacity(), 8);
assert!(cache.is_full());
assert_eq!(cache.get(&1), Some(&"a"));
assert_eq!(cache.get(&2), Some(&"b"));
assert_eq!(cache.get(&3), Some(&"c"));
assert_eq!(cache.get(&4), Some(&"d"));
}
#[test]
fn test_weighted_resize_smaller() {
let mut cache = CLruCache::with_config(
CLruCacheConfig::new(NonZeroUsize::new(8).unwrap()).with_scale(IntStrScale),
);
assert_eq!(cache.put_with_weight(1, "a"), Ok(None));
assert_eq!(cache.put_with_weight(2, "b"), Ok(None));
assert_eq!(cache.put_with_weight(3, "c"), Ok(None));
assert_eq!(cache.put_with_weight(4, "d"), Ok(None));
assert_eq!(cache.len(), 4);
assert_eq!(cache.weight(), 4);
assert_eq!(cache.capacity(), 8);
assert!(cache.is_full());
cache.resize(FOUR);
assert_eq!(cache.len(), 2);
assert_eq!(cache.weight(), 2);
assert_eq!(cache.capacity(), 4);
assert!(cache.is_full());
assert!(cache.get(&1).is_none());
assert!(cache.get(&2).is_none());
assert_eq!(cache.get(&3), Some(&"c"));
assert_eq!(cache.get(&4), Some(&"d"));
cache.resize(THREE);
assert_eq!(cache.len(), 1);
assert_eq!(cache.weight(), 1);
assert_eq!(cache.capacity(), 3);
assert!(!cache.is_full());
assert_eq!(cache.get(&1), None);
assert_eq!(cache.get(&2), None);
assert_eq!(cache.get(&3), None);
assert_eq!(cache.get(&4), Some(&"d"));
}
#[test]
fn test_weighted_resize_equal() {
let mut cache = CLruCache::with_config(
CLruCacheConfig::new(NonZeroUsize::new(8).unwrap()).with_scale(IntStrScale),
);
assert_eq!(cache.put_with_weight(1, "a"), Ok(None));
assert_eq!(cache.put_with_weight(2, "b"), Ok(None));
assert_eq!(cache.put_with_weight(3, "c"), Ok(None));
assert_eq!(cache.put_with_weight(4, "d"), Ok(None));
assert_eq!(cache.len(), 4);
assert_eq!(cache.weight(), 4);
assert_eq!(cache.capacity(), 8);
assert!(cache.is_full());
cache.resize(HEIGHT);
assert_eq!(cache.len(), 4);
assert_eq!(cache.weight(), 4);
assert_eq!(cache.capacity(), 8);
assert!(cache.is_full());
assert_eq!(cache.get(&1), Some(&"a"));
assert_eq!(cache.get(&2), Some(&"b"));
assert_eq!(cache.get(&3), Some(&"c"));
assert_eq!(cache.get(&4), Some(&"d"));
}
#[test]
fn test_weighted_iter() {
let mut cache = CLruCache::with_config(
CLruCacheConfig::new(NonZeroUsize::new(8).unwrap()).with_scale(IntStrScale),
);
assert_eq!(cache.put_with_weight(1, "a"), Ok(None));
assert_eq!(cache.put_with_weight(2, "b"), Ok(None));
assert_eq!(cache.put_with_weight(3, "c"), Ok(None));
assert_eq!(cache.put_with_weight(4, "d"), Ok(None));
assert_eq!(cache.len(), 4);
assert_eq!(cache.weight(), 4);
assert_eq!(cache.capacity(), 8);
assert!(cache.is_full());
}
#[test]
fn test_weighted_iter_forwards() {
let mut cache = CLruCache::with_config(
CLruCacheConfig::new(NonZeroUsize::new(8).unwrap()).with_scale(IntStrScale),
);
assert_eq!(cache.put_with_weight(1, "a"), Ok(None));
assert_eq!(cache.put_with_weight(2, "b"), Ok(None));
assert_eq!(cache.put_with_weight(3, "c"), Ok(None));
let mut iter = cache.iter();
assert_eq!(iter.len(), 3);
assert_eq!(iter.next(), Some((&3, &"c")));
assert_eq!(iter.len(), 2);
assert_eq!(iter.next(), Some((&2, &"b")));
assert_eq!(iter.len(), 1);
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.len(), 0);
assert_eq!(iter.next(), None);
}
#[test]
fn test_weighted_iter_backwards() {
let mut cache = CLruCache::with_config(
CLruCacheConfig::new(NonZeroUsize::new(8).unwrap()).with_scale(IntStrScale),
);
assert_eq!(cache.put_with_weight(1, "a"), Ok(None));
assert_eq!(cache.put_with_weight(2, "b"), Ok(None));
assert_eq!(cache.put_with_weight(3, "c"), Ok(None));
let mut iter = cache.iter();
assert_eq!(iter.len(), 3);
assert_eq!(iter.next_back(), Some((&1, &"a")));
assert_eq!(iter.len(), 2);
assert_eq!(iter.next_back(), Some((&2, &"b")));
assert_eq!(iter.len(), 1);
assert_eq!(iter.next_back(), Some((&3, &"c")));
assert_eq!(iter.len(), 0);
assert_eq!(iter.next_back(), None);
}
#[test]
fn test_weighted_iter_forwards_and_backwards() {
let mut cache = CLruCache::with_config(
CLruCacheConfig::new(NonZeroUsize::new(8).unwrap()).with_scale(IntStrScale),
);
assert_eq!(cache.put_with_weight(1, "a"), Ok(None));
assert_eq!(cache.put_with_weight(2, "b"), Ok(None));
assert_eq!(cache.put_with_weight(3, "c"), Ok(None));
let mut iter = cache.iter();
assert_eq!(iter.len(), 3);
assert_eq!(iter.next(), Some((&3, &"c")));
assert_eq!(iter.len(), 2);
assert_eq!(iter.next_back(), Some((&1, &"a")));
assert_eq!(iter.len(), 1);
assert_eq!(iter.next(), Some((&2, &"b")));
assert_eq!(iter.len(), 0);
assert_eq!(iter.next_back(), None);
}
#[test]
fn test_weighted_into_iter() {
let mut cache = CLruCache::with_config(
CLruCacheConfig::new(NonZeroUsize::new(10).unwrap()).with_scale(IntStrScale),
);
assert_eq!(cache.put_with_weight(1, "a"), Ok(None));
assert_eq!(cache.put_with_weight(2, "b"), Ok(None));
assert_eq!(cache.put_with_weight(3, "c"), Ok(None));
assert_eq!(cache.put_with_weight(4, "d"), Ok(None));
assert_eq!(cache.put_with_weight(5, "e"), Ok(None));
let mut vec = Vec::new();
for (k, v) in &cache {
vec.push((k, v));
}
assert_eq!(
vec,
vec![(&5, &"e"), (&4, &"d"), (&3, &"c"), (&2, &"b"), (&1, &"a")]
);
assert_eq!(
cache.into_iter().collect::<Vec<_>>(),
vec![(5, "e"), (4, "d"), (3, "c"), (2, "b"), (1, "a")]
);
}
#[test]
fn test_is_send() {
fn is_send<T: Send>() {}
fn cache_is_send<K: Send, V: Send, S: Send, W: WeightScale<K, V> + Send>() {
is_send::<K>();
is_send::<V>();
is_send::<S>();
is_send::<W>();
is_send::<CLruCache<K, V, S, W>>();
}
cache_is_send::<String, String, RandomState, ZeroWeightScale>();
fn cache_in_mutex<
K: Clone + Default + Eq + Hash + Send + 'static,
V: Default + Send + 'static,
S: BuildHasher + Send + 'static,
W: WeightScale<K, V> + Send + 'static,
>(
cache: CLruCache<K, V, S, W>,
) where
(K, V): std::fmt::Debug,
{
use std::sync::{Arc, Mutex};
use std::thread;
let mutex: Arc<Mutex<CLruCache<K, V, S, W>>> = Arc::new(Mutex::new(cache));
let mutex2 = mutex.clone();
let t1 = thread::spawn(move || {
mutex
.lock()
.unwrap()
.put_with_weight(Default::default(), Default::default())
.unwrap();
});
let t2 = thread::spawn(move || {
mutex2
.lock()
.unwrap()
.put_with_weight(Default::default(), Default::default())
.unwrap();
});
t1.join().unwrap();
t2.join().unwrap();
}
let cache: CLruCache<String, String> = CLruCache::new(TWO);
cache_in_mutex(cache);
}
#[test]
fn test_is_sync() {
fn is_sync<T: Sync>() {}
fn cache_is_sync<K: Sync, V: Sync, S: Sync, W: WeightScale<K, V> + Sync>() {
is_sync::<K>();
is_sync::<V>();
is_sync::<S>();
is_sync::<W>();
is_sync::<CLruCache<K, V, S, W>>();
}
cache_is_sync::<String, String, RandomState, ZeroWeightScale>();
fn cache_in_rwlock<
K: Clone + Default + Eq + Hash + Send + Sync + 'static,
V: Default + Send + Sync + 'static,
S: BuildHasher + Send + Sync + 'static,
W: WeightScale<K, V> + Send + Sync + 'static,
>(
cache: CLruCache<K, V, S, W>,
) where
(K, V): std::fmt::Debug,
{
use std::sync::{Arc, RwLock};
use std::thread;
let mutex: Arc<RwLock<CLruCache<K, V, S, W>>> = Arc::new(RwLock::new(cache));
let mutex2 = mutex.clone();
let t1 = thread::spawn(move || {
mutex
.write()
.unwrap()
.put_with_weight(Default::default(), Default::default())
.unwrap();
});
let t2 = thread::spawn(move || {
mutex2
.write()
.unwrap()
.put_with_weight(Default::default(), Default::default())
.unwrap();
});
t1.join().unwrap();
t2.join().unwrap();
}
let cache: CLruCache<String, String> = CLruCache::new(TWO);
cache_in_rwlock(cache);
}
}