use std::hash::Hash;
use indexmap::IndexSet;
#[cfg(debug_assertions)]
use rand::seq::SliceRandom;
use tether_map::Ptr;
use tether_map::linked_hash_map::LinkedHashMap;
use tether_map::linked_hash_map::RemovedEntry;
use tether_map::linked_hash_map::{
self,
};
use crate::EntryValue;
use crate::InsertOrUpdateAction;
use crate::InsertionResult;
use crate::Metadata;
use crate::Policy;
use crate::RandomState;
use crate::private;
#[derive(Debug, Clone, Copy)]
#[doc(hidden)]
pub struct RandomPolicy;
impl private::Sealed for RandomPolicy {}
#[derive(Debug, Clone, Copy)]
#[doc(hidden)]
pub struct RandomEntry<Value> {
value: Value,
}
impl<Value> private::Sealed for RandomEntry<Value> {}
impl<Value> EntryValue<Value> for RandomEntry<Value> {
fn new(value: Value) -> Self {
Self { value }
}
fn into_value(self) -> Value {
self.value
}
fn value(&self) -> &Value {
&self.value
}
fn value_mut(&mut self) -> &mut Value {
&mut self.value
}
}
#[derive(Debug, Clone, Default)]
#[doc(hidden)]
pub struct RandomMetadata {
ptrs: IndexSet<Ptr>,
}
impl private::Sealed for RandomMetadata {}
impl<T> Metadata<T> for RandomMetadata {
type EntryType = RandomEntry<T>;
fn candidate_removal_index<K>(
&self,
queue: &LinkedHashMap<K, RandomEntry<T>, RandomState>,
) -> Option<Ptr> {
if queue.is_empty() {
return None;
}
self.ptrs
.get_index(rand::random_range(0..self.ptrs.len()))
.copied()
}
fn clone_from<K>(
&mut self,
_: &Self,
new_queue: &LinkedHashMap<K, Self::EntryType, RandomState>,
) {
self.ptrs.clear();
let Some(mut cursor) = new_queue.head_ptr() else {
return;
};
loop {
self.ptrs.insert(cursor);
let Some(next) = new_queue
.next_ptr(cursor)
.filter(|next| Some(*next) != new_queue.head_ptr())
else {
break;
};
cursor = next;
}
}
}
impl<T> Policy<T> for RandomPolicy {
type IntoIter<K: Hash + Eq> = IntoIter<K, T>;
type MetadataType = RandomMetadata;
#[inline]
fn insert_or_update_entry<K: std::hash::Hash + Eq>(
key: K,
make_room_on_insert: bool,
get_value: impl FnOnce(&K, /* is_insert */ bool) -> InsertOrUpdateAction<T>,
metadata: &mut Self::MetadataType,
queue: &mut LinkedHashMap<K, <Self::MetadataType as Metadata<T>>::EntryType, RandomState>,
) -> InsertionResult<K, T> {
let would_evict = metadata.candidate_removal_index(queue);
match queue.entry(key) {
linked_hash_map::Entry::Occupied(mut occupied_entry) => {
let ptr = occupied_entry.ptr();
match get_value(occupied_entry.key(), false) {
InsertOrUpdateAction::NoInsert(_) => {
unreachable!("Cache hit should not return NoInsert");
}
InsertOrUpdateAction::TouchNoUpdate => {
InsertionResult::FoundTouchedNoUpdate(ptr)
}
InsertOrUpdateAction::InsertOrUpdate(value) => {
let entry = occupied_entry.get_mut();
*entry.value_mut() = value;
InsertionResult::Updated(ptr)
}
}
}
linked_hash_map::Entry::Vacant(vacant_entry) => {
let value = match get_value(vacant_entry.key(), true) {
InsertOrUpdateAction::TouchNoUpdate => {
unreachable!("Cache miss should not return TouchNoUpdate");
}
InsertOrUpdateAction::NoInsert(value) => {
return InsertionResult::NotFoundNoInsert(vacant_entry.into_key(), value);
}
InsertOrUpdateAction::InsertOrUpdate(value) => value,
};
let (ptr, evicted) = if make_room_on_insert {
let ptr = vacant_entry.insert_tail(RandomEntry::new(value)).0;
let evicted = Self::remove_entry(would_evict.unwrap(), metadata, queue)
.1
.map(|(_, entry)| entry.into_value());
metadata.ptrs.swap_remove(&would_evict.unwrap());
(ptr, evicted)
} else {
(vacant_entry.insert_tail(RandomEntry::new(value)).0, None)
};
metadata.ptrs.insert(ptr);
InsertionResult::Inserted(ptr, evicted)
}
}
}
#[inline]
fn touch_entry<K: std::hash::Hash + Eq>(
_: Ptr,
_: &mut Self::MetadataType,
_: &mut LinkedHashMap<K, <Self::MetadataType as Metadata<T>>::EntryType, RandomState>,
) {
}
#[inline]
fn remove_entry<K: std::hash::Hash + Eq>(
ptr: Ptr,
_: &mut Self::MetadataType,
queue: &mut LinkedHashMap<K, <Self::MetadataType as Metadata<T>>::EntryType, RandomState>,
) -> (
Option<Ptr>,
Option<(K, <Self::MetadataType as Metadata<T>>::EntryType)>,
) {
let Some(RemovedEntry {
key, value, next, ..
}) = queue.remove_ptr(ptr)
else {
return (None, None);
};
(next, Some((key, value)))
}
#[inline]
fn remove_key<K: std::hash::Hash + Eq>(
key: &K,
_: &mut Self::MetadataType,
queue: &mut LinkedHashMap<K, <Self::MetadataType as Metadata<T>>::EntryType, RandomState>,
) -> Option<<Self::MetadataType as Metadata<T>>::EntryType> {
queue.remove(key)
}
#[inline]
fn iter<'q, K>(
metadata: &'q Self::MetadataType,
queue: &'q LinkedHashMap<K, RandomEntry<T>, RandomState>,
) -> impl Iterator<Item = (&'q K, &'q T)>
where
T: 'q,
{
#[cfg(debug_assertions)]
let mut order = (0..queue.len()).collect::<Vec<_>>();
#[cfg(debug_assertions)]
order.shuffle(&mut rand::rng());
Iter {
#[cfg(debug_assertions)]
index: order.pop().unwrap_or(queue.len()),
#[cfg(not(debug_assertions))]
index: 0,
#[cfg(debug_assertions)]
order,
index_to_ptr: &metadata.ptrs,
queue,
}
}
#[inline]
fn into_iter<K: Hash + Eq>(
_metadata: Self::MetadataType,
queue: LinkedHashMap<K, RandomEntry<T>, RandomState>,
) -> Self::IntoIter<K> {
#[cfg(debug_assertions)]
let mut order = (0..queue.len()).collect::<Vec<_>>();
#[cfg(debug_assertions)]
order.shuffle(&mut rand::rng());
IntoIter {
#[cfg(debug_assertions)]
index: order.pop().unwrap_or(queue.len()),
#[cfg(not(debug_assertions))]
index: 0,
#[cfg(debug_assertions)]
order,
queue: queue.into_iter().map(Some).collect(),
}
}
#[inline]
fn into_entries<K>(
_metadata: Self::MetadataType,
queue: LinkedHashMap<K, RandomEntry<T>, RandomState>,
) -> impl Iterator<Item = (K, RandomEntry<T>)> {
#[cfg(debug_assertions)]
let mut order = (0..queue.len()).collect::<Vec<_>>();
#[cfg(debug_assertions)]
order.shuffle(&mut rand::rng());
IntoEntriesIter {
#[cfg(debug_assertions)]
index: order.pop().unwrap_or(queue.len()),
#[cfg(not(debug_assertions))]
index: 0,
#[cfg(debug_assertions)]
order,
queue: queue.into_iter().map(Some).collect(),
}
}
#[cfg(all(debug_assertions, feature = "internal-debugging"))]
#[inline]
fn debug_validate<K: std::hash::Hash + Eq>(
_: &Self::MetadataType,
_: &LinkedHashMap<K, RandomEntry<T>, RandomState>,
) {
}
}
struct Iter<'q, K, T> {
#[cfg(debug_assertions)]
order: Vec<usize>,
index_to_ptr: &'q IndexSet<Ptr>,
queue: &'q LinkedHashMap<K, RandomEntry<T>, RandomState>,
index: usize,
}
impl<'q, K, T> Iterator for Iter<'q, K, T> {
type Item = (&'q K, &'q T);
fn next(&mut self) -> Option<Self::Item> {
if self.index < self.queue.len() {
let ptr = self.index_to_ptr.get_index(self.index).copied()?;
#[cfg(debug_assertions)]
{
self.index = self.order.pop().unwrap_or(self.queue.len());
}
#[cfg(not(debug_assertions))]
{
self.index += 1;
}
self.queue
.ptr_get_entry(ptr)
.map(|(key, entry)| (key, entry.value()))
} else {
None
}
}
}
#[doc(hidden)]
pub struct IntoIter<K, T> {
#[cfg(debug_assertions)]
order: Vec<usize>,
queue: Vec<Option<(K, RandomEntry<T>)>>,
index: usize,
}
impl<K, T> Iterator for IntoIter<K, T> {
type Item = (K, T);
fn next(&mut self) -> Option<Self::Item> {
if self.index < self.queue.len() {
let (key, entry) = self.queue.get_mut(self.index)?.take()?;
#[cfg(debug_assertions)]
{
self.index = self.order.pop().unwrap_or(self.queue.len());
}
#[cfg(not(debug_assertions))]
{
self.index += 1;
}
Some((key, entry.into_value()))
} else {
None
}
}
}
#[doc(hidden)]
pub struct IntoEntriesIter<K, T> {
#[cfg(debug_assertions)]
order: Vec<usize>,
queue: Vec<Option<(K, RandomEntry<T>)>>,
index: usize,
}
impl<K, T> Iterator for IntoEntriesIter<K, T> {
type Item = (K, RandomEntry<T>);
fn next(&mut self) -> Option<Self::Item> {
if self.index < self.queue.len() {
let (key, entry) = self.queue.get_mut(self.index)?.take()?;
#[cfg(debug_assertions)]
{
self.index = self.order.pop().unwrap_or(self.queue.len());
}
#[cfg(not(debug_assertions))]
{
self.index += 1;
}
Some((key, entry))
} else {
None
}
}
}
#[cfg(test)]
mod tests {
use std::num::NonZeroUsize;
use ntest::timeout;
use crate::Random;
#[test]
#[timeout(5000)]
fn test_random_empty_cache() {
let mut cache = Random::<i32, i32>::new(NonZeroUsize::new(3).unwrap());
assert!(cache.is_empty());
assert_eq!(cache.len(), 0);
assert_eq!(cache.capacity(), 3);
assert_eq!(cache.get(&1), None);
assert_eq!(cache.peek(&1), None);
assert_eq!(cache.remove(&1), None);
assert_eq!(cache.pop(), None);
assert!(cache.tail().is_none());
assert!(!cache.contains_key(&1));
}
}