use std::fmt::{Debug, Display, Formatter};
use std::hash::Hash;
use std::iter::FusedIterator;
use std::ptr::NonNull;
use std::rc::Rc;
use super::lfu_entry::Detached;
use super::node::WithFrequency;
use super::{LfuEntry, Node};
#[derive(Eq, PartialEq, Ord, PartialOrd, Hash)]
pub(super) struct FrequencyList<Key: Hash + Eq, T> {
pub(super) head: Option<NonNull<Node<Key, T>>>,
}
impl<Key: Hash + Eq, Value> Default for FrequencyList<Key, Value> {
fn default() -> Self {
Self::new()
}
}
#[cfg(not(tarpaulin_include))]
impl<Key: Hash + Eq, T> Debug for FrequencyList<Key, T> {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
let mut dbg = f.debug_struct("FrequencyList");
let mut node = self.head;
while let Some(cur_node) = node {
let cur_node = unsafe { cur_node.as_ref() };
dbg.field(
&format!("node freq {} num elements", &cur_node.frequency),
&cur_node.len(),
);
node = cur_node.next;
}
dbg.finish()
}
}
#[cfg(not(tarpaulin_include))]
impl<Key: Hash + Eq, T: Display> Display for FrequencyList<Key, T> {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
let mut cur_node = self.head;
while let Some(ref node) = cur_node {
let node = unsafe { node.as_ref() };
writeln!(f, " Node (freq value = {}) [", node.frequency)?;
let mut cur_ele = node.elements;
while let Some(ref ele) = cur_ele {
let ele = unsafe { ele.as_ref() };
writeln!(f, " {},", ele.value)?;
cur_ele = ele.next;
}
writeln!(f, " ]")?;
cur_node = node.next;
}
Ok(())
}
}
impl<Key: Hash + Eq, T> Drop for FrequencyList<Key, T> {
fn drop(&mut self) {
if let Some(ptr) = self.head {
unsafe { Box::from_raw(ptr.as_ptr()) };
}
}
}
impl<Key: Hash + Eq, T> FrequencyList<Key, T> {
#[inline]
pub(super) const fn new() -> Self {
Self { head: None }
}
pub(super) fn insert(&mut self, key: Rc<Key>, value: T) -> NonNull<LfuEntry<Key, T>> {
let head = match self.head {
Some(head) if unsafe { head.as_ref() }.frequency == 0 => head,
_ => self.init_front(),
};
Node::push(head, Detached::new(key, value))
}
fn init_front(&mut self) -> NonNull<Node<Key, T>> {
let node = Box::new(Node {
next: self.head,
prev: None,
elements: None,
frequency: 0,
});
let node = NonNull::from(Box::leak(node));
if let Some(mut head) = self.head {
if let Some(mut next) = unsafe { head.as_ref() }.next {
let next = unsafe { next.as_mut() };
next.prev = Some(head);
}
let head = unsafe { head.as_mut() };
head.prev = Some(node);
}
self.head = Some(node);
node
}
pub(super) fn update(&mut self, mut entry: NonNull<LfuEntry<Key, T>>) {
let freq_list_node = unsafe { (*entry.as_ptr()).owner.as_ptr() };
let freq_list_node_freq = unsafe { &*freq_list_node }.frequency;
let next_node = match unsafe { &*freq_list_node }.next {
Some(node) if unsafe { node.as_ref() }.frequency == freq_list_node_freq + 1 => node,
_ => Node::create_increment(NonNull::new(freq_list_node).unwrap()),
};
let freq_list_node = unsafe { entry.as_mut().owner.as_mut() };
let detached = freq_list_node.remove_ref(entry);
Node::push_ref(next_node, detached);
if freq_list_node.elements.is_none() {
let freq_head = unsafe { Box::from_raw(freq_list_node) };
if self.head == Some(NonNull::from(&*freq_head)) {
self.head = freq_head.next;
}
freq_head.detach();
}
}
#[inline]
pub(super) fn pop_lfu(&mut self) -> Option<WithFrequency<Detached<Key, T>>> {
let mut head_node_ptr = self.head?;
let head_node = unsafe { head_node_ptr.as_mut() };
let item = head_node.pop();
if head_node.elements.is_none() {
self.head = head_node.next;
let owned = unsafe { Box::from_raw(head_node_ptr.as_ptr()) };
owned.detach();
}
item
}
#[inline]
pub(super) fn peek_lfu(&self) -> Option<&T> {
self.head.and_then(|node| unsafe { node.as_ref() }.peek())
}
pub(super) fn frequencies(&self) -> impl Iterator<Item = usize> + FusedIterator + '_ {
self.iter().map(|node| node.frequency)
}
#[cfg(test)]
pub fn len(&self) -> usize {
self.iter().count()
}
fn iter(&self) -> Iter<'_, Key, T> {
Iter(self.head.map(|v| unsafe { v.as_ref() }))
}
}
#[derive(Debug)]
struct Iter<'a, Key: Hash + Eq, Value>(Option<&'a Node<Key, Value>>);
impl<'a, Key: Hash + Eq, Value> Iterator for Iter<'a, Key, Value> {
type Item = &'a Node<Key, Value>;
fn next(&mut self) -> Option<Self::Item> {
let ret = self.0?;
self.0 = ret.next.map(|v| unsafe { v.as_ref() });
Some(ret)
}
}
impl<'a, Key: Hash + Eq, Value> FusedIterator for Iter<'a, Key, Value> {}
#[cfg(test)]
mod frequency_list {
use std::{ptr::NonNull, rc::Rc};
use super::FrequencyList;
fn init_list() -> FrequencyList<i32, i32> {
FrequencyList::new()
}
#[test]
fn new_is_empty() {
let list = init_list();
assert!(list.head.is_none());
assert_eq!(list.len(), 0);
assert!(list.frequencies().count() == 0);
}
#[test]
fn insert() {
let mut list = init_list();
let entry = unsafe { Box::from_raw(list.insert(Rc::new(1), 2).as_ptr()) };
assert_eq!(entry.prev, None);
assert_eq!(entry.next, None);
assert_eq!(entry.value, 2);
assert_eq!(entry.owner, list.head.unwrap());
}
#[test]
fn insert_non_empty() {
let mut list = init_list();
let entry_0 = list.insert(Rc::new(1), 2);
let entry_1 = list.insert(Rc::new(3), 4);
let entry_0_ref = unsafe { entry_0.as_ref() };
let entry_1_ref = unsafe { entry_1.as_ref() };
assert_eq!(entry_1_ref.prev, None);
assert_eq!(entry_1_ref.next, Some(entry_0));
assert_eq!(entry_1_ref.value, 4);
assert_eq!(entry_1_ref.owner, list.head.unwrap());
assert_eq!(entry_0_ref.prev, Some(entry_1));
assert_eq!(entry_0_ref.next, None);
assert_eq!(entry_0_ref.value, 2);
assert_eq!(entry_0_ref.owner, list.head.unwrap());
unsafe {
drop(Box::from_raw(entry_0.as_ptr()));
drop(Box::from_raw(entry_1.as_ptr()));
}
}
#[test]
fn insert_non_empty_non_freq_zero() {
let mut list = init_list();
let entry_0_ptr = list.insert(Rc::new(1), 2).as_ptr();
list.update(NonNull::new(entry_0_ptr).unwrap());
let entry_1_ptr = list.insert(Rc::new(3), 4).as_ptr();
let entry_0 = unsafe { &*entry_0_ptr };
assert_eq!(entry_0.prev, None);
assert_eq!(entry_0.next, None);
assert_eq!(entry_0.value, 2);
assert_ne!(entry_0.owner, list.head.unwrap());
let entry_1 = unsafe { &*entry_1_ptr };
assert_eq!(entry_1.prev, None);
assert_eq!(entry_1.next, None);
assert_eq!(entry_1.value, 4);
assert_eq!(entry_1.owner, list.head.unwrap());
unsafe {
drop(Box::from_raw(entry_0_ptr));
drop(Box::from_raw(entry_1_ptr));
}
}
#[test]
fn init_front_empty() {
let mut list = init_list();
let front_node = list.init_front();
assert_eq!(list.head, Some(front_node));
assert_eq!(list.len(), 1);
let front_node = unsafe { front_node.as_ref() };
assert_eq!(front_node.prev, None);
assert_eq!(front_node.next, None);
}
#[test]
fn init_front_non_empty() {
let mut list = init_list();
let back_node = list.init_front();
assert_eq!(list.head, Some(back_node));
assert_eq!(list.len(), 1);
{
let back_node = unsafe { back_node.as_ref() };
assert_eq!(back_node.prev, None);
assert_eq!(back_node.next, None);
}
let middle_node = list.init_front();
assert_eq!(list.head, Some(middle_node));
assert_eq!(list.len(), 2);
{
let middle_node = unsafe { middle_node.as_ref() };
assert_eq!(middle_node.prev, None);
assert_eq!(middle_node.next, Some(back_node));
}
{
let back_node = unsafe { back_node.as_ref() };
assert_eq!(back_node.prev, Some(middle_node));
assert_eq!(back_node.next, None);
}
let front_node = list.init_front();
assert_eq!(list.head, Some(front_node));
assert_eq!(list.len(), 3);
{
let front_node = unsafe { front_node.as_ref() };
assert_eq!(front_node.prev, None);
assert_eq!(front_node.next, Some(middle_node));
}
{
let middle_node = unsafe { middle_node.as_ref() };
assert_eq!(middle_node.prev, Some(front_node));
assert_eq!(middle_node.next, Some(back_node));
}
{
let back_node = unsafe { back_node.as_ref() };
assert_eq!(back_node.prev, Some(middle_node));
assert_eq!(back_node.next, None);
}
}
#[test]
fn update_removes_empty_node() {
let mut list = init_list();
let entry = list.insert(Rc::new(1), 2);
list.update(entry);
assert_eq!(unsafe { list.head.unwrap().as_ref() }.frequency, 1);
list.update(entry);
assert_eq!(unsafe { list.head.unwrap().as_ref() }.frequency, 2);
unsafe { Box::from_raw(entry.as_ptr()) };
}
#[test]
fn update_does_not_remove_non_empty_node() {
let mut list = init_list();
let entry_0 = list.insert(Rc::new(1), 2);
let entry_1 = list.insert(Rc::new(3), 4);
list.update(entry_0);
assert_eq!(unsafe { list.head.unwrap().as_ref() }.frequency, 0);
assert_eq!(list.frequencies().collect::<Vec<_>>(), vec![0, 1]);
list.update(entry_1);
list.update(entry_0);
assert_eq!(unsafe { list.head.unwrap().as_ref() }.frequency, 1);
assert_eq!(list.frequencies().collect::<Vec<_>>(), vec![1, 2]);
unsafe { Box::from_raw(entry_0.as_ptr()) };
unsafe { Box::from_raw(entry_1.as_ptr()) };
}
#[test]
fn update_correctly_removes_in_middle_nodes() {
let mut list = init_list();
let entry_0 = list.insert(Rc::new(1), 2);
let entry_1 = list.insert(Rc::new(3), 4);
list.update(entry_0);
assert_eq!(unsafe { list.head.unwrap().as_ref() }.frequency, 0);
assert_eq!(list.frequencies().collect::<Vec<_>>(), vec![0, 1]);
list.update(entry_0);
assert_eq!(unsafe { list.head.unwrap().as_ref() }.frequency, 0);
assert_eq!(list.frequencies().collect::<Vec<_>>(), vec![0, 2]);
unsafe { Box::from_raw(entry_0.as_ptr()) };
unsafe { Box::from_raw(entry_1.as_ptr()) };
}
}