diff options
Diffstat (limited to 'vendor/clru/src')
| -rw-r--r-- | vendor/clru/src/config.rs | 72 | ||||
| -rw-r--r-- | vendor/clru/src/lib.rs | 2159 | ||||
| -rw-r--r-- | vendor/clru/src/list.rs | 629 | ||||
| -rw-r--r-- | vendor/clru/src/weight.rs | 16 |
4 files changed, 2876 insertions, 0 deletions
diff --git a/vendor/clru/src/config.rs b/vendor/clru/src/config.rs new file mode 100644 index 000000000..37369411d --- /dev/null +++ b/vendor/clru/src/config.rs @@ -0,0 +1,72 @@ +use crate::weight::{WeightScale, ZeroWeightScale}; +use std::collections::hash_map::RandomState; +use std::hash::BuildHasher; +use std::marker::PhantomData; +use std::num::NonZeroUsize; + +/// A configuration structure used to create an LRU cache. +pub struct CLruCacheConfig<K, V, S = RandomState, W = ZeroWeightScale> { + pub(crate) capacity: NonZeroUsize, + pub(crate) hash_builder: S, + pub(crate) reserve: Option<usize>, + pub(crate) scale: W, + _marker: PhantomData<(K, V)>, +} + +impl<K, V> CLruCacheConfig<K, V> { + /// Creates a new configuration that will create an LRU cache + /// that will hold at most `capacity` elements and default parameters. + pub fn new(capacity: NonZeroUsize) -> Self { + Self { + capacity, + hash_builder: RandomState::default(), + reserve: None, + scale: ZeroWeightScale, + _marker: PhantomData, + } + } +} + +impl<K, V, S: BuildHasher, W: WeightScale<K, V>> CLruCacheConfig<K, V, S, W> { + /// Configure the provided hash builder. + pub fn with_hasher<O: BuildHasher>(self, hash_builder: O) -> CLruCacheConfig<K, V, O, W> { + let Self { + capacity, + reserve, + scale, + _marker, + .. + } = self; + CLruCacheConfig { + capacity, + hash_builder, + reserve, + scale, + _marker, + } + } + + /// Configure the amount of pre-allocated memory in order to hold at least `reserve` elements + /// without reallocating. + pub fn with_memory(mut self, reserve: usize) -> Self { + self.reserve = Some(reserve); + self + } + + /// Configure the provided scale. + pub fn with_scale<O: WeightScale<K, V>>(self, scale: O) -> CLruCacheConfig<K, V, S, O> { + let Self { + capacity, + hash_builder, + reserve, + .. + } = self; + CLruCacheConfig { + capacity, + hash_builder, + reserve, + scale, + _marker: PhantomData, + } + } +} diff --git a/vendor/clru/src/lib.rs b/vendor/clru/src/lib.rs new file mode 100644 index 000000000..4ea08a150 --- /dev/null +++ b/vendor/clru/src/lib.rs @@ -0,0 +1,2159 @@ +//! Another LRU cache implementation in rust. +//! It has two main characteristics that differentiates it from other implementation: +//! +//! 1. It is backed by a [HashMap](https://doc.rust-lang.org/std/collections/struct.HashMap.html): it +//! offers a O(1) time complexity (amortized average) for any operation that requires to lookup an entry from +//! a key. +//! +//! 2. It is a weighted cache: each key-value pair has a weight and the capacity serves as both as: +//! * a limit to the number of elements +//! * and as a limit to the total weight of its elements +//! +//! using the following formula: +//! +//! [`CLruCache::len`] + [`CLruCache::weight`] <= [`CLruCache::capacity`] +//! +//! Even though most operations don't depend on the number of elements in the cache, +//! [`CLruCache::put_with_weight`] has a special behavior: because it needs to make room +//! for the new element, it will remove enough least recently used elements. In the worst +//! case, that will require to fully empty the cache. Additionally, if the weight of the +//! new element is too big, the insertion can fail. +//! +//! For the common case of an LRU cache whose elements don't have a weight, a default +//! [`ZeroWeightScale`] is provided and unlocks some useful APIs like: +//! +//! * [`CLruCache::put`]: an infallible insertion that will remove a maximum of 1 element. +//! * [`CLruCache::put_or_modify`]: a conditional insertion or modification flow similar +//! to the entry API of [`HashMap`]. +//! * [`CLruCache::try_put_or_modify`]: fallible version of [`CLruCache::put_or_modify`]. +//! * All APIs that allow to retrieve a mutable reference to a value (e.g.: [`CLruCache::get_mut`]). +//! +//! The cache requires the keys to be clonable because it will store 2 instances +//! of each key in different internal data structures. If cloning a key can be +//! expensive, you might want to consider using an [`std::rc::Rc`] or an [`std::sync::Arc`]. +//! +//! ## Examples +//! +//! ### Using the default [`ZeroWeightScale`]: +//! +//! ```rust +//! +//! use std::num::NonZeroUsize; +//! use clru::CLruCache; +//! +//! let mut cache = CLruCache::new(NonZeroUsize::new(2).unwrap()); +//! cache.put("apple".to_string(), 3); +//! cache.put("banana".to_string(), 2); +//! +//! assert_eq!(cache.get("apple"), Some(&3)); +//! assert_eq!(cache.get("banana"), Some(&2)); +//! assert!(cache.get("pear").is_none()); +//! +//! assert_eq!(cache.put("banana".to_string(), 4), Some(2)); +//! assert_eq!(cache.put("pear".to_string(), 5), None); +//! +//! assert_eq!(cache.get("pear"), Some(&5)); +//! assert_eq!(cache.get("banana"), Some(&4)); +//! assert!(cache.get("apple").is_none()); +//! +//! { +//! let v = cache.get_mut("banana").unwrap(); +//! *v = 6; +//! } +//! +//! assert_eq!(cache.get("banana"), Some(&6)); +//! ``` +//! +//! ### Using a custom [`WeightScale`] implementation: +//! +//! ```rust +//! +//! use std::num::NonZeroUsize; +//! use clru::{CLruCache, CLruCacheConfig, WeightScale}; +//! +//! struct CustomScale; +//! +//! impl WeightScale<String, &str> for CustomScale { +//! fn weight(&self, _key: &String, value: &&str) -> usize { +//! value.len() +//! } +//! } +//! +//! let mut cache = CLruCache::with_config( +//! CLruCacheConfig::new(NonZeroUsize::new(6).unwrap()).with_scale(CustomScale), +//! ); +//! +//! assert_eq!(cache.put_with_weight("apple".to_string(), "red").unwrap(), None); +//! assert_eq!( +//! cache.put_with_weight("apple".to_string(), "green").unwrap(), +//! Some("red") +//! ); +//! +//! assert_eq!(cache.len(), 1); +//! assert_eq!(cache.get("apple"), Some(&"green")); +//! ``` + +#![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, +} + +/// A weighted LRU cache with mostly¹ constant time operations. +/// +/// Each key-value pair in the cache can have a weight that is retrieved +/// using the provided [`WeightScale`] implementation. The default scale is +/// [`ZeroWeightScale`] and always return 0. The number of elements that +/// can be stored in the cache is conditioned by the sum of [`CLruCache::len`] +/// and [`CLruCache::weight`]: +/// +/// [`CLruCache::len`] + [`CLruCache::weight`] <= [`CLruCache::capacity`] +/// +/// Using the default [`ZeroWeightScale`] scale unlocks some useful APIs +/// that can currently only be implemented for this scale. The most interesting +/// ones are probably: +/// +/// * [`CLruCache::put`] +/// * [`CLruCache::put_or_modify`] +/// * [`CLruCache::try_put_or_modify`] +/// +/// But more generally, using [`ZeroWeightScale`] unlocks all methods that return +/// a mutable reference to the value of an element. +/// This is because modifying the value of an element can lead to a modification +/// of its weight and therefore would put the cache into an incoherent state. +/// For the same reason, it is a logic error for a value to change weight while +/// being stored in the cache. +/// +/// The cache requires the keys to be clonable because it will store 2 instances +/// of each key in different internal data structures. If cloning a key can be +/// expensive, you might want to consider using an `Rc` or an `Arc`. +/// +/// Note 1: See [`CLruCache::put_with_weight`] +#[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> { + /// Creates a new LRU cache that holds at most `capacity` elements. + pub fn new(capacity: NonZeroUsize) -> Self { + Self { + lookup: HashMap::new(), + storage: FixedSizeList::new(capacity.get()), + scale: ZeroWeightScale, + weight: 0, + } + } + + /// Creates a new LRU cache that holds at most `capacity` elements + /// and pre-allocates memory in order to hold at least `reserve` elements + /// without reallocating. + 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> { + /// Creates a new LRU cache that holds at most `capacity` elements + /// and uses the provided hash builder to hash keys. + 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> { + /// Creates a new LRU cache that holds at most `capacity` elements + /// and uses the provided scale to retrieve value's weight. + 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> { + /// Creates a new LRU cache using the provided configuration. + 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, + } + } + + /// Returns the number of key-value pairs that are currently in the cache. + #[inline] + pub fn len(&self) -> usize { + debug_assert_eq!(self.lookup.len(), self.storage.len()); + self.storage.len() + } + + /// Returns the capacity of the cache. It serves as a limit for + /// * the number of elements that the cache can hold. + /// * the total weight of the elements in the cache. + #[inline] + pub fn capacity(&self) -> usize { + self.storage.capacity() + } + + /// Returns the total weight of the elements in the cache. + #[inline] + pub fn weight(&self) -> usize { + self.weight + } + + /// Returns a bool indicating whether the cache is empty or not. + #[inline] + pub fn is_empty(&self) -> bool { + debug_assert_eq!(self.lookup.is_empty(), self.storage.is_empty()); + self.storage.is_empty() + } + + /// Returns a bool indicating whether the cache is full or not. + #[inline] + pub fn is_full(&self) -> bool { + self.len() + self.weight() == self.capacity() + } + + /// Returns the value corresponding to the most recently used item or `None` if the cache is empty. + /// Like `peek`, `front` does not update the LRU list so the item's position will be unchanged. + pub fn front(&self) -> Option<(&K, &V)> { + self.storage + .front() + .map(|CLruNode { key, value }| (key, value)) + } + + /// Returns the value corresponding to the least recently used item or `None` if the cache is empty. + /// Like `peek`, `back` does not update the LRU list so the item's position will be unchanged. + pub fn back(&self) -> Option<(&K, &V)> { + self.storage + .back() + .map(|CLruNode { key, value }| (key, value)) + } + + /// Puts a key-value pair into cache taking it's weight into account. + /// If the weight of the new element is greater than what the cache can hold, + /// it returns the provided key-value pair as an error. + /// Otherwise, it removes enough elements for the new element to be inserted, + /// thus making it a non constant time operation. + /// If the key already exists in the cache, then it updates the key's value and returns the old value. + /// Otherwise, `None` is returned. + 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) => { + // TODO: store keys in the cache itself for reuse. + 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); + } + // It's fine to unwrap here because: + // * the cache capacity is non zero + // * the cache cannot be full + 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); + } + // It's fine to unwrap here because: + // * the cache capacity is non zero + // * the cache cannot be full + 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) + } + } + } + + /// Returns a reference to the value of the key in the cache or `None` if it is not present in the cache. + /// Moves the key to the head of the LRU list if it exists. + 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) + } + + /// Removes and returns the value corresponding to the key from the cache or `None` if it does not exist. + 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 + }) + } + + /// Removes and returns the key and value corresponding to the most recently used item or `None` if the cache is empty. + 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 + } + } + + /// Removes and returns the key and value corresponding to the least recently used item or `None` if the cache is empty. + 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 + } + } + + /// Returns a reference to the value corresponding to the key in the cache or `None` if it is not present in the cache. + /// Unlike `get`, `peek` does not update the LRU list so the key's position will be unchanged. + 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) + } + + /// Returns a bool indicating whether the given key is in the cache. + /// Does not update the LRU list. + pub fn contains<Q: ?Sized>(&mut self, key: &Q) -> bool + where + K: Borrow<Q>, + Q: Hash + Eq, + { + self.peek(key).is_some() + } + + /// Clears the contents of the cache. + #[inline] + pub fn clear(&mut self) { + self.lookup.clear(); + self.storage.clear(); + self.weight = 0; + } + + /// Resizes the cache. + /// If the new capacity is smaller than the size of the current cache any entries past the new capacity are discarded. + 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; + } + } + + /// Retains only the elements specified by the predicate. + /// In other words, remove all pairs `(k, v)` such that `f(&k, &v)` returns `false`. + 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> { + /// Returns an iterator visiting all entries in order. + /// The iterator element type is `(&'a K, &'a V)`. + pub fn iter(&self) -> CLruCacheIter<'_, K, V> { + CLruCacheIter { + iter: self.storage.iter(), + } + } +} + +impl<K: Clone + Eq + Hash, V, S: BuildHasher> CLruCache<K, V, S> { + /// Puts a key-value pair into cache. + /// If the key already exists in the cache, then it updates the key's value and returns the old value. + /// Otherwise, `None` is returned. + pub fn put(&mut self, key: K, value: V) -> Option<V> { + match self.lookup.entry(key) { + Entry::Occupied(occ) => { + // It's fine to unwrap here because: + // * the entry already exists + 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(); + // It's fine to unwrap here because: + // * the cache capacity is non zero + // * the cache is full + 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 { + // It's fine to unwrap here because: + // * the cache capacity is non zero + // * the cache is not full + let (idx, _) = self.storage.push_front(CLruNode { key, value }).unwrap(); + vac.insert(idx); + } + None + } + } + } + + /// Puts a new key-value pair or modify an already existing value. + /// If the key already exists in the cache, then `modify_op` supplied function is called. + /// Otherwise, `put_op` supplied function is called. + /// Returns a mutable reference to the value. + /// + /// The additional `data` argument can be used to pass extra information + /// to the supplied functions. This can useful when both functions need + /// to access the same variable. + 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) => { + // It's fine to unwrap here because: + // * the entry already exists + 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(); + // It's fine to unwrap here because: + // * the cache capacity is non zero + // * the cache is full + 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 { + // It's fine to unwrap here because: + // * the cache capacity is non zero + // * the cache cannot be full + let (idx, node) = self.storage.push_front(CLruNode { key, value }).unwrap(); + vac.insert(idx); + &mut node.value + } + } + } + } + + /// Puts a new key-value pair or modify an already existing value. + /// If the key already exists in the cache, then `modify_op` supplied function is called. + /// Otherwise, `put_op` supplied function is called. + /// Returns a mutable reference to the value or an error. + /// + /// The additional `data` argument can be used to pass extra information + /// to the supplied functions. This can useful when both functions need + /// to access the same variable. + /// + /// This is the fallible version of [`CLruCache::put_or_modify`]. + 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) => { + // It's fine to unwrap here because: + // * the entry already exists + 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(); + // It's fine to unwrap here because: + // * the cache capacity is non zero + // * the cache is full + 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 { + // It's fine to unwrap here because: + // * the cache capacity is non zero + // * the cache cannot be full + let (idx, node) = self.storage.push_front(CLruNode { key, value }).unwrap(); + vac.insert(idx); + Ok(&mut node.value) + } + } + } + } + + /// Returns the value corresponding to the most recently used item or `None` if the cache is empty. + /// Like `peek`, `font` does not update the LRU list so the item's position will be unchanged. + pub fn front_mut(&mut self) -> Option<(&K, &mut V)> { + self.storage + .front_mut() + .map(|CLruNode { key, value }| (&*key, value)) + } + + /// Returns the value corresponding to the least recently used item or `None` if the cache is empty. + /// Like `peek`, `back` does not update the LRU list so the item's position will be unchanged. + pub fn back_mut(&mut self) -> Option<(&K, &mut V)> { + self.storage + .back_mut() + .map(|CLruNode { key, value }| (&*key, value)) + } + + /// Returns a mutable reference to the value of the key in the cache or `None` if it is not present in the cache. + /// Moves the key to the head of the LRU list if it exists. + 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) + } + + /// Returns a mutable reference to the value corresponding to the key in the cache or `None` if it is not present in the cache. + /// Unlike `get_mut`, `peek_mut` does not update the LRU list so the key's position will be unchanged. + 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) + } + + /// Retains only the elements specified by the predicate. + /// In other words, remove all pairs `(k, v)` such that `f(&k, &mut v)` returns `false`. + 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> { + /// Returns an iterator visiting all entries in order, giving a mutable reference on V. + /// The iterator element type is `(&'a K, &'a mut V)`. + pub fn iter_mut(&mut self) -> CLruCacheIterMut<'_, K, V> { + CLruCacheIterMut { + iter: self.storage.iter_mut(), + } + } +} + +/// An iterator over the entries of a `CLruCache`. +/// +/// This `struct` is created by the [`iter`] method on [`CLruCache`][`CLruCache`]. +/// See its documentation for more. +/// +/// [`iter`]: struct.CLruCache.html#method.iter +/// [`CLruCache`]: struct.CLruCache.html +#[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() + } +} + +/// An iterator over mutables entries of a `CLruCache`. +/// +/// This `struct` is created by the [`iter_mut`] method on [`CLruCache`][`CLruCache`]. +/// See its documentation for more. +/// +/// [`iter_mut`]: struct.CLruCache.html#method.iter_mut +/// [`CLruCache`]: struct.CLruCache.html +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() + } +} + +/// An owning iterator over the elements of a `CLruCache`. +/// +/// This `struct` is created by the [`into_iter`] method on [`CLruCache`] +/// (provided by the `IntoIterator` trait). See its documentation for more. +/// +/// [`into_iter`]: struct.CLruCache.html#method.into_iter +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>; + + /// Consumes the cache into an iterator yielding elements by value. + #[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")); + + // Even though we inserted "apple" into the cache earlier it has since been removed from + // the cache so there is no current value for `insert` to return. + 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); + + { + // iter const + 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); + } + { + // iter mut + 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); + + { + // iter const + 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); + } + + { + // iter mut + 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); + + { + // iter const + 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); + } + { + // iter mut + 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); + + // A panic in the modify closure will move the + // key at the top of the cache. + 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); + + // A panic in the put closure won't have any + // any impact on the cache. + 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); + + // An error in the modify closure will move the + // key at the top of the cache. + 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); + + // An error in the put closure won't have any + // any impact on the cache. + 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()); // because of weight + 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()); + + // Even though we inserted "apple" into the cache earlier it has since been removed from + // the cache so there is no current value for `insert` to return. + 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); // tomato, apple, pear + assert_eq!(cache.weight(), 13); // 3 + 5 + 5 + 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); + } +} diff --git a/vendor/clru/src/list.rs b/vendor/clru/src/list.rs new file mode 100644 index 000000000..a89bd7f5d --- /dev/null +++ b/vendor/clru/src/list.rs @@ -0,0 +1,629 @@ +use std::cmp::Ordering; +use std::ptr::NonNull; + +#[derive(Debug)] +struct FixedSizeListNode<T> { + prev: usize, + next: usize, + data: T, +} + +#[derive(Debug)] +pub(crate) struct FixedSizeList<T> { + capacity: usize, + nodes: Vec<Option<FixedSizeListNode<T>>>, + // An un-ordered set of indices that are not in use in `nodes`. + // All `None` entries in `nodes` _must_ be listed in `free`. + // A `Vec<usize>` was choosen in order to have O(1) complexity + // for pop and avoid having to go through `nodes` in order to + // to find a free place. + free: Vec<usize>, + front: usize, + back: usize, +} + +impl<T> FixedSizeList<T> { + #[inline] + pub(crate) fn new(capacity: usize) -> Self { + Self { + capacity, + nodes: Vec::new(), + free: Vec::new(), + front: usize::MAX, + back: usize::MAX, + } + } + + #[inline] + pub(crate) fn with_memory(capacity: usize, mut reserve: usize) -> Self { + if reserve > capacity { + reserve = capacity; + } + Self { + capacity, + nodes: Vec::with_capacity(reserve), + free: Vec::new(), + front: usize::MAX, + back: usize::MAX, + } + } + + #[inline] + pub(crate) fn capacity(&self) -> usize { + self.capacity + } + + #[inline] + pub(crate) fn len(&self) -> usize { + self.nodes.len() - self.free.len() + } + + #[inline] + pub(crate) fn is_empty(&self) -> bool { + self.len() == 0 + } + + #[inline] + pub(crate) fn is_full(&self) -> bool { + self.len() == self.capacity() + } + + pub(crate) fn clear(&mut self) { + self.nodes.clear(); + self.free.clear(); + self.front = usize::MAX; + self.back = usize::MAX; + } + + fn next(&mut self) -> Option<usize> { + if self.is_full() { + None + } else if self.free.is_empty() { + let len = self.len(); + self.nodes.push(None); + Some(len) + } else { + self.free.pop() + } + } + + #[inline] + fn node_ref(&self, idx: usize) -> Option<&FixedSizeListNode<T>> { + self.nodes.get(idx).and_then(|node| node.as_ref()) + } + + #[inline] + pub(crate) fn get(&self, idx: usize) -> Option<&T> { + self.node_ref(idx).map(|node| &node.data) + } + + #[inline] + fn node_mut(&mut self, idx: usize) -> Option<&mut FixedSizeListNode<T>> { + self.nodes.get_mut(idx).and_then(|node| node.as_mut()) + } + + #[inline] + pub(crate) fn get_mut(&mut self, idx: usize) -> Option<&mut T> { + self.node_mut(idx).map(|node| &mut node.data) + } + + #[inline] + pub(crate) fn front(&self) -> Option<&T> { + self.node_ref(self.front).map(|node| &node.data) + } + + #[inline] + pub(crate) fn front_mut(&mut self) -> Option<&mut T> { + self.node_mut(self.front).map(|node| &mut node.data) + } + + #[inline] + pub(crate) fn back_idx(&self) -> usize { + self.back + } + + #[inline] + pub(crate) fn back(&self) -> Option<&T> { + self.node_ref(self.back).map(|node| &node.data) + } + + #[inline] + pub(crate) fn back_mut(&mut self) -> Option<&mut T> { + self.node_mut(self.back).map(|node| &mut node.data) + } + + pub(crate) fn push_front(&mut self, data: T) -> Option<(usize, &mut T)> { + let idx = self.next()?; + if let Some(front) = self.node_mut(self.front) { + front.prev = idx; + } + if self.node_ref(self.back).is_none() { + self.back = idx; + } + let node = self.nodes.get_mut(idx).unwrap().insert(FixedSizeListNode { + prev: usize::MAX, + next: self.front, + data, + }); + self.front = idx; + Some((idx, &mut node.data)) + } + + #[cfg(test)] + fn push_back(&mut self, data: T) -> Option<(usize, &mut T)> { + let idx = self.next()?; + if let Some(back) = self.node_mut(self.back) { + back.next = idx; + } + if self.node_ref(self.front).is_none() { + self.front = idx; + } + let node = self.nodes.get_mut(idx).unwrap().insert(FixedSizeListNode { + prev: self.back, + next: usize::MAX, + data, + }); + self.back = idx; + Some((idx, &mut node.data)) + } + + #[inline] + pub(crate) fn pop_front(&mut self) -> Option<T> { + self.remove(self.front) + } + + #[inline] + pub(crate) fn pop_back(&mut self) -> Option<T> { + self.remove(self.back) + } + + pub(crate) fn remove(&mut self, idx: usize) -> Option<T> { + let node = self.nodes.get_mut(idx)?.take()?; + if let Some(prev) = self.node_mut(node.prev) { + prev.next = node.next; + } else { + self.front = node.next; + } + if let Some(next) = self.node_mut(node.next) { + next.prev = node.prev; + } else { + self.back = node.prev; + } + self.free.push(idx); + Some(node.data) + } + + #[inline] + pub(crate) fn iter(&self) -> FixedSizeListIter<'_, T> { + FixedSizeListIter { + list: self, + front: self.front, + back: self.back, + len: self.len(), + } + } + + #[inline] + pub(crate) fn iter_mut(&mut self) -> FixedSizeListIterMut<'_, T> { + let front = self.front; + let back = self.back; + let len = self.len(); + FixedSizeListIterMut::new(&mut self.nodes, front, back, len) + } + + fn reorder(&mut self) { + if self.is_empty() { + return; + } + + let len = self.len(); + let mut current = 0; + while current < len { + let front = self.front; + let front_data = self.pop_front().unwrap(); + if front != current { + debug_assert!(current < front, "{} < {}", current, front); + // We need to free self.nodes[current] if its occupied + if let Some(current_node) = self.nodes[current].take() { + if let Some(node) = self.node_mut(current_node.prev) { + node.next = front; + } else { + self.front = front; + } + if let Some(node) = self.node_mut(current_node.next) { + node.prev = front; + } else { + self.back = front; + } + self.nodes[front] = Some(current_node); + } + } + // Assign new front node + self.nodes[current] = Some(FixedSizeListNode { + prev: current.wrapping_sub(1), + next: current + 1, + data: front_data, + }); + current += 1; + } + self.front = 0; + self.nodes[len - 1].as_mut().unwrap().next = usize::MAX; + self.back = len - 1; + self.free.clear(); + self.free.extend((len..self.nodes.len()).rev()); + } + + pub(crate) fn resize(&mut self, capacity: usize) { + let len = self.len(); + let cap = self.capacity(); + match capacity.cmp(&cap) { + Ordering::Less => { + self.reorder(); + self.nodes.truncate(capacity); + self.free.clear(); + self.free.extend(len..self.nodes.len()); + self.capacity = capacity; + } + Ordering::Equal => {} + Ordering::Greater => { + self.capacity = capacity; + } + }; + debug_assert_eq!(self.len(), len); + debug_assert_eq!(self.capacity(), capacity); + } + + pub(crate) fn retain<F>(&mut self, mut f: F) + where + F: FnMut(&T) -> bool, + { + let mut front = self.front; + while front != usize::MAX { + let node = self.node_ref(front).unwrap(); + let next = node.next; + if !f(&node.data) { + self.remove(front); + } + front = next; + } + } + + pub(crate) fn retain_mut<F>(&mut self, mut f: F) + where + F: FnMut(&mut T) -> bool, + { + let mut front = self.front; + while front != usize::MAX { + let node = self.node_mut(front).unwrap(); + let next = node.next; + if !f(&mut node.data) { + self.remove(front); + } + front = next; + } + } + + #[inline] + pub(crate) fn move_front(&mut self, idx: usize) -> Option<&mut T> { + // TODO: try to optimize this funtion as it is a fairly hot path + let node = self.nodes.get_mut(idx)?.take()?; + if let Some(prev) = self.node_mut(node.prev) { + prev.next = node.next; + } else { + self.front = node.next; + } + if let Some(next) = self.node_mut(node.next) { + next.prev = node.prev; + } else { + self.back = node.prev; + } + + if let Some(front) = self.node_mut(self.front) { + front.prev = idx; + } + if self.node_ref(self.back).is_none() { + self.back = idx; + } + + let node = self.nodes.get_mut(idx).unwrap().insert(FixedSizeListNode { + prev: usize::MAX, + next: self.front, + data: node.data, + }); + self.front = idx; + Some(&mut node.data) + } +} + +#[derive(Debug)] +pub(crate) struct FixedSizeListIter<'a, T> { + list: &'a FixedSizeList<T>, + front: usize, + back: usize, + len: usize, +} + +impl<'a, T> Clone for FixedSizeListIter<'a, T> { + fn clone(&self) -> Self { + Self { + list: self.list, + front: self.front, + back: self.back, + len: self.len, + } + } +} + +impl<'a, T> Iterator for FixedSizeListIter<'a, T> { + type Item = (usize, &'a T); + + fn next(&mut self) -> Option<Self::Item> { + if self.len > 0 { + let front = self.front; + let node = self.list.node_ref(front).unwrap(); + self.front = node.next; + self.len -= 1; + Some((front, &node.data)) + } else { + None + } + } + + fn size_hint(&self) -> (usize, Option<usize>) { + (self.len, Some(self.len)) + } +} + +impl<'a, T> DoubleEndedIterator for FixedSizeListIter<'a, T> { + fn next_back(&mut self) -> Option<Self::Item> { + if self.len > 0 { + let back = self.back; + let node = self.list.node_ref(back).unwrap(); + self.back = node.prev; + self.len -= 1; + Some((back, &node.data)) + } else { + None + } + } +} + +impl<'a, T> ExactSizeIterator for FixedSizeListIter<'a, T> { + fn len(&self) -> usize { + self.size_hint().0 + } +} + +pub(crate) struct FixedSizeListIterMut<'a, T> { + ptr: NonNull<Option<FixedSizeListNode<T>>>, + front: usize, + back: usize, + len: usize, + _marker: std::marker::PhantomData<&'a mut T>, +} + +impl<'a, T> FixedSizeListIterMut<'a, T> { + #[allow(unsafe_code)] + fn new( + slice: &'a mut [Option<FixedSizeListNode<T>>], + front: usize, + back: usize, + len: usize, + ) -> Self { + let ptr = slice.as_mut_ptr(); + Self { + ptr: unsafe { NonNull::new_unchecked(ptr) }, + front, + back, + len, + _marker: std::marker::PhantomData, + } + } +} + +impl<'a, T> Iterator for FixedSizeListIterMut<'a, T> { + type Item = (usize, &'a mut T); + + #[allow(unsafe_code)] + fn next(&mut self) -> Option<Self::Item> { + if self.len > 0 { + let front = self.front; + + // Safety: + // * `self.ptr` is a valid non null pointer since it can only be created through `FixedSizeListIterMut::new`. + // * `front` is guaranteed to be a valid index within the slice pointed to by `self.ptr`. + // Notes: implementation is inspired by the iterator over mutable slice from the standard rust library + // * https://doc.rust-lang.org/src/core/slice/iter.rs.html + // * https://doc.rust-lang.org/src/core/slice/iter/macros.rs.html + let node_ref = unsafe { + let ptr = NonNull::new_unchecked(self.ptr.as_ptr().add(front)).as_ptr(); + &mut *ptr + }; + + let node = node_ref.as_mut().unwrap(); + self.front = node.next; + self.len -= 1; + Some((front, &mut node.data)) + } else { + None + } + } + + fn size_hint(&self) -> (usize, Option<usize>) { + (self.len, Some(self.len)) + } +} + +impl<'a, T> DoubleEndedIterator for FixedSizeListIterMut<'a, T> { + #[allow(unsafe_code)] + fn next_back(&mut self) -> Option<Self::Item> { + if self.len > 0 { + let back = self.back; + + // Safety: + // * `self.ptr` is a valid non null pointer since it can only be created through `FixedSizeListIterMut::new`. + // * `back` is guaranteed to be a valid index within the slice pointed to by `self.ptr`. + // Notes: implementation is inspired by the iterator over mutable slice from the standard rust library + // * https://doc.rust-lang.org/src/core/slice/iter.rs.html + // * https://doc.rust-lang.org/src/core/slice/iter/macros.rs.html + let node_ref = unsafe { + let ptr = NonNull::new_unchecked(self.ptr.as_ptr().add(back)).as_ptr(); + &mut *ptr + }; + + let node = node_ref.as_mut().unwrap(); + self.back = node.prev; + self.len -= 1; + Some((back, &mut node.data)) + } else { + None + } + } +} + +impl<'a, T> ExactSizeIterator for FixedSizeListIterMut<'a, T> { + fn len(&self) -> usize { + self.size_hint().0 + } +} + +#[cfg(test)] +#[allow(clippy::bool_assert_comparison)] +mod tests { + use super::*; + + #[test] + fn test_fixed_size_list() { + let mut list = FixedSizeList::new(4); + + assert!(list.is_empty()); + assert_eq!(list.len(), 0); + + assert_eq!(list.front(), None); + assert_eq!(list.front_mut(), None); + + assert_eq!(list.back(), None); + assert_eq!(list.back_mut(), None); + + assert_eq!(list.iter().count(), 0); + assert_eq!(list.iter().rev().count(), 0); + + assert_eq!(list.push_front(7), Some((0, &mut 7))); + + assert!(!list.is_empty()); + assert_eq!(list.len(), 1); + + assert_eq!(list.front(), Some(&7)); + assert_eq!(list.front_mut(), Some(&mut 7)); + + assert_eq!(list.back(), Some(&7)); + assert_eq!(list.back_mut(), Some(&mut 7)); + + assert_eq!(list.iter().collect::<Vec<_>>(), vec![(0, &7)]); + assert_eq!(list.iter().rev().collect::<Vec<_>>(), vec![(0, &7)]); + + assert_eq!(list.push_front(5), Some((1, &mut 5))); + + assert!(!list.is_empty()); + assert_eq!(list.len(), 2); + + assert_eq!(list.front(), Some(&5)); + assert_eq!(list.front_mut(), Some(&mut 5)); + + assert_eq!(list.back(), Some(&7)); + assert_eq!(list.back_mut(), Some(&mut 7)); + + assert_eq!(list.iter().collect::<Vec<_>>(), vec![(1, &5), (0, &7)]); + assert_eq!( + list.iter().rev().collect::<Vec<_>>(), + vec![(0, &7), (1, &5)] + ); + + assert_eq!(list.push_front(3), Some((2, &mut 3))); + + assert!(!list.is_empty()); + assert_eq!(list.len(), 3); + + assert_eq!(list.front(), Some(&3)); + assert_eq!(list.front_mut(), Some(&mut 3)); + + assert_eq!(list.back(), Some(&7)); + assert_eq!(list.back_mut(), Some(&mut 7)); + + assert_eq!( + list.iter().collect::<Vec<_>>(), + vec![(2, &3), (1, &5), (0, &7)] + ); + assert_eq!( + list.iter().rev().collect::<Vec<_>>(), + vec![(0, &7), (1, &5), (2, &3)] + ); + + list.remove(1); + + assert!(!list.is_empty()); + assert_eq!(list.len(), 2); + + assert_eq!(list.front(), Some(&3)); + assert_eq!(list.front_mut(), Some(&mut 3)); + + assert_eq!(list.back(), Some(&7)); + assert_eq!(list.back_mut(), Some(&mut 7)); + + assert_eq!(list.iter().collect::<Vec<_>>(), vec![(2, &3), (0, &7)]); + assert_eq!( + list.iter().rev().collect::<Vec<_>>(), + vec![(0, &7), (2, &3)] + ); + + list.remove(0); + + assert!(!list.is_empty()); + assert_eq!(list.len(), 1); + + assert_eq!(list.front(), Some(&3)); + assert_eq!(list.front_mut(), Some(&mut 3)); + + assert_eq!(list.back(), Some(&3)); + assert_eq!(list.back_mut(), Some(&mut 3)); + + assert_eq!(list.iter().collect::<Vec<_>>(), vec![(2, &3)]); + assert_eq!(list.iter().rev().collect::<Vec<_>>(), vec![(2, &3)]); + + list.remove(2); + + assert!(list.is_empty()); + assert_eq!(list.len(), 0); + + assert_eq!(list.front(), None); + assert_eq!(list.front_mut(), None); + + assert_eq!(list.back(), None); + assert_eq!(list.back_mut(), None); + + assert_eq!(list.iter().count(), 0); + assert_eq!(list.iter().rev().count(), 0); + } + + #[test] + fn test_fixed_size_list_reorder() { + let mut list = FixedSizeList::new(4); + + list.push_back('a'); + list.push_front('b'); + list.push_back('c'); + list.push_front('d'); + + assert_eq!( + list.iter().collect::<Vec<_>>(), + vec![(3, &'d'), (1, &'b'), (0, &'a'), (2, &'c')] + ); + + list.reorder(); + + assert_eq!( + list.iter().collect::<Vec<_>>(), + vec![(0, &'d'), (1, &'b'), (2, &'a'), (3, &'c')] + ); + } +} diff --git a/vendor/clru/src/weight.rs b/vendor/clru/src/weight.rs new file mode 100644 index 000000000..59c8a5688 --- /dev/null +++ b/vendor/clru/src/weight.rs @@ -0,0 +1,16 @@ +/// Trait used to retrieve the weight of a key-value pair. +pub trait WeightScale<K, V> { + /// Returns the weight of a key-value pair. + fn weight(&self, key: &K, value: &V) -> usize; +} + +/// A scale that always return 0. +#[derive(Clone, Copy, Debug, Default)] +pub struct ZeroWeightScale; + +impl<K, V> WeightScale<K, V> for ZeroWeightScale { + #[inline] + fn weight(&self, _: &K, _: &V) -> usize { + 0 + } +} |