Skip to content

Instantly share code, notes, and snippets.

@vmolsa

vmolsa/cachelist.rs

Last active September 14, 2024 08:29
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save vmolsa/35bc3f5286ad5f44ab42170ccea1d8dd to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save vmolsa/35bc3f5286ad5f44ab42170ccea1d8dd to your computer and use it in GitHub Desktop.
Download ZIP
Linked list with cache option
Raw
cachelist.rs
use std::{fmt::{self, Debug},ops::{Deref, DerefMut}, ptr::NonNull};
/// A doubly linked list that caches nodes for reuse to minimize allocation overhead.
///
/// `CacheList` is designed for scenarios where frequent insertions and deletions occur,
/// and reusing nodes can significantly improve performance by reducing memory allocations.
///
/// # Type Parameters
///
/// - `T`: The type of values stored in the list.
/// - `C`: The maximum number of nodes to cache for reuse.
/// - `L`: The maximum number of nodes to be allocated.
///
/// # Features
///
/// - Reuses nodes when possible, reducing memory allocations and deallocations.
/// - Supports efficient insertion and removal of nodes from both ends of the list.
/// - Provides a mutable iterator allowing in-place modification and removal of nodes.
///
/// # Examples
///
/// ```
/// use crate::CacheList;
///
/// let mut list: CacheList<i32, 10> = CacheList::new();
///
/// // Push elements to the list
/// for i in 0..10 {
/// list.push(i);
/// }
///
/// // Remove nodes with even values using the mutable iterator
/// let mut iter = list.iter_mut();
///
/// while let Some(value) = iter.next() {
/// if *value % 2 == 0 {
/// iter.remove_current();
/// }
/// }
///
/// // Push more elements to demonstrate node reuse
/// for i in 100..110 {
/// list.push(i);
/// }
///
/// println!("{:?}", list);
/// ```
pub struct CacheList<T: Debug, const C: usize, const L: usize = { usize::MAX }> {
avail: Option<NonNull<Node<T>>>,
head: Option<NonNull<Node<T>>>,
tail: Option<NonNull<Node<T>>>,
capacity: usize,
len: usize,
}
impl<T: Debug, const C: usize, const L: usize> Drop for CacheList<T, C, L> {
/// Drops the `CacheList`, deallocating all nodes in the list and the cache.
fn drop(&mut self) {
// Deallocate all nodes in the main list.
while let Some(node) = self.head {
unsafe {
self.unlink_node(node);
drop(Box::from_raw(node.as_ptr()));
}
}
// Deallocate all cached nodes.
while let Some(node) = self.avail {
unsafe {
self.avail = (*node.as_ptr()).next;
drop(Box::from_raw(node.as_ptr()));
}
}
}
}
impl<T: Debug, const C: usize, const L: usize> CacheList<T, C, L> {
/// Creates a new, empty `CacheList`.
///
/// # Returns
///
/// A new instance of `CacheList` with no nodes.
///
/// # Examples
///
/// ```
/// use crate::CacheList;
///
/// let list: CacheList<i32, 10> = CacheList::new();
///
/// assert!(list.is_empty());
/// ```
pub fn new() -> Self {
Self {
avail: None,
head: None,
tail: None,
capacity: 0,
len: 0,
}
}
/// Adds a node to the cache, resetting its value and pointers.
///
/// If the cache size reaches the limit `C`, the node will be deallocated instead of cached.
fn make_avail(avail: &mut Option<NonNull<Node<T>>>, mut node: NonNull<Node<T>>) {
unsafe {
let node_mut = node.as_mut();
node_mut.next = *avail;
node_mut.prev = None;
node_mut.value = None;
*avail = Some(node);
}
}
/// Allocates a node with the given value, reusing an available node from the cache if possible.
///
/// If a reusable node is available in the cache, it will be repurposed with the new value. If no
/// reusable nodes are available, a new node is allocated if the overall capacity (`L`) has not been
/// reached. Otherwise, allocation fails and returns `None`.
///
/// # Parameters
/// - `value`: The value to be stored in the new node.
///
/// # Returns
/// - `Option<NonNull<Node<T>>>`: A `NonNull` pointer to the newly allocated or reused node, or
/// `None` if allocation fails due to capacity limits.
///
/// # Safety
/// The returned node is managed with raw pointers, and correct usage is critical to avoid memory
/// errors. The caller must ensure that the node is correctly linked or deallocated to prevent
/// memory leaks or undefined behavior.
fn allocate_node(&mut self, value: T) -> Option<NonNull<Node<T>>> {
if let Some(mut available_node) = self.avail {
unsafe {
let node_mut = available_node.as_mut();
self.avail = node_mut.next;
node_mut.next = None;
node_mut.value = Some(value);
Some(available_node)
}
} else {
if self.capacity < L {
let boxed_node = Box::new(Node {
value: Some(value),
next: None,
prev: None,
});
self.capacity += 1;
Some(unsafe { NonNull::new_unchecked(Box::into_raw(boxed_node)) })
} else {
None
}
}
}
/// Unlinks a node from the list, updating the adjacent nodes' pointers.
///
/// This method is used internally to safely remove nodes without deallocating them.
///
/// # Safety
///
/// This function must only be called when `node` is valid and properly linked in the list.
unsafe fn unlink_node(&mut self, mut node: NonNull<Node<T>>) {
let node_mut = node.as_mut();
match node_mut.prev {
Some(prev) => unsafe { (*prev.as_ptr()).next = node_mut.next },
None => self.head = node_mut.next,
};
match node_mut.next {
Some(next) => unsafe { (*next.as_ptr()).prev = node_mut.prev },
None => self.tail = node_mut.prev,
};
}
/// Removes a node from the list, caching it if the cache limit allows, otherwise deallocating it.
///
/// # Parameters
///
/// - `node`: The node to be removed and potentially cached.
///
/// # Safety
///
/// This method assumes that `node` is valid and part of the list.
fn remove(&mut self, node: NonNull<Node<T>>) {
unsafe {
self.unlink_node(node);
if self.capacity < C {
Self::make_avail(&mut self.avail, node)
} else {
self.capacity -= 1;
drop(Box::from_raw(node.as_ptr()));
}
}
self.len -= 1;
}
/// Appends a new value to the end of the list.
///
/// Allocates a new node with the given value and links it as the new tail of the list. If node
/// allocation fails due to reaching capacity limits, the operation returns `None`.
///
/// # Parameters
/// - `value`: The value to be stored in the new node.
///
/// # Returns
/// - `Option<&mut T>`: A mutable reference to the newly added value, or `None` if the list
/// capacity is reached or node allocation fails.
///
/// # Safety
/// Uses `unsafe` code to manage raw pointers when updating the list. This function must only be
/// used when the list is correctly maintained to avoid undefined behavior.
///
/// # Examples
/// ```
/// use crate::CacheList;
///
/// let mut list: CacheList<i32, 10> = CacheList::new();
///
/// list.push(42); // Append value
///
/// assert_eq!(list.len(), 1); // Check list length
/// ```
pub fn push(&mut self, value: T) -> Option<&mut T> {
if let Some(mut new_node) = self.allocate_node(value) {
unsafe {
let node_mut = new_node.as_mut();
node_mut.next = None;
node_mut.prev = self.tail;
let node = Some(new_node);
match self.tail {
None => self.head = node,
Some(tail) => (*tail.as_ptr()).next = node,
}
self.tail = node;
self.len += 1;
return node_mut.value.as_mut()
}
}
None
}
/// Returns a mutable iterator over the list.
///
/// The iterator allows traversal and in-place modification of the list elements.
///
/// # Examples
///
/// ```
/// use crate::CacheList;
///
/// let mut list: CacheList<i32, 10> = CacheList::new();
///
/// list.push(1);
/// list.push(2);
/// list.push(3);
///
/// let mut iter = list.iter_mut();
///
/// while let Some(value) = iter.next() {
/// *value *= 2;
/// }
/// ```
pub fn iter_mut(&mut self) -> CacheListIterMut<T, C, L> {
CacheListIterMut {
next: self.head,
list: self,
current: None,
}
}
/// Returns `true` if the list is empty.
///
/// # Examples
///
/// ```
/// use crate::CacheList;
///
/// let list: CacheList<i32, 10> = CacheList::new();
///
/// assert!(list.is_empty());
/// ```
pub fn is_empty(&self) -> bool {
self.head.is_none()
}
/// Returns the length of the list.
///
/// # Examples
///
/// ```
/// use crate::CacheList;
///
/// let mut list: CacheList<i32, 10> = CacheList::new();
///
/// list.push(1);
///
/// assert_eq!(list.len(), 1);
/// ```
pub fn len(&self) -> usize {
self.len
}
/// Returns the capacity of the list.
///
/// # Examples
///
/// ```
/// use crate::CacheList;
///
/// let mut list: CacheList<i32, 10> = CacheList::new();
///
/// list.push(1);
///
/// assert_eq!(list.capacity(), 1);
/// ```
pub fn capacity(&self) -> usize {
self.capacity
}
}
/// A node within the `CacheList`, which stores a value and pointers to adjacent nodes in the list.
///
/// # Type Parameters
///
/// - `T`: The type of value stored within the node.
pub struct Node<T> {
value: Option<T>,
next: Option<NonNull<Node<T>>>,
prev: Option<NonNull<Node<T>>>,
}
impl<T> Deref for Node<T> {
type Target = Option<T>;
fn deref(&self) -> &Self::Target {
&self.value
}
}
impl<T> DerefMut for Node<T> {
fn deref_mut(&mut self) -> &mut Self::Target {
&mut self.value
}
}
impl<T: fmt::Debug> fmt::Debug for Node<T> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{:?}", unsafe { self.value.as_ref().unwrap_unchecked() })
}
}
impl<T: fmt::Debug, const N: usize> fmt::Debug for CacheList<T, N> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let mut list_repr = f.debug_list();
let mut current = &self.head;
while let Some(node) = current {
unsafe {
list_repr.entry(node.as_ref());
current = &(*node.as_ptr()).next;
}
}
list_repr.finish()
}
}
/// A mutable iterator over the `CacheList`, allowing traversal and modification of elements.
///
/// The iterator supports removing nodes during traversal, which is efficient for
/// filtering elements based on custom conditions.
///
/// # Type Parameters
///
/// - `T`: The type of values stored in the list.
/// - `C`: The maximum number of nodes to cache for reuse.
/// - `L`: The maximum number of nodes to be allocated.
pub struct CacheListIterMut<'a, T: Debug, const C: usize, const L: usize> {
list: &'a mut CacheList<T, C, L>,
current: Option<NonNull<Node<T>>>,
next: Option<NonNull<Node<T>>>,
}
impl<'a, T: Debug, const C: usize, const L: usize> Iterator for CacheListIterMut<'a, T, C, L> {
type Item = &'a mut T;
#[inline]
fn next(&mut self) -> Option<&'a mut T> {
self.current = self.next;
if let Some(node) = self.current {
unsafe {
self.next = (*node.as_ptr()).next;
(*node.as_ptr()).value.as_mut()
}
} else {
None
}
}
}
impl<'a, T: Debug, const C: usize, const L: usize> CacheListIterMut<'a, T, C, L> {
/// Removes the current node in the iteration from the list.
///
/// This method allows for safe removal of elements while iterating, enabling
/// dynamic filtering or adjustment of the list contents.
///
/// # Examples
///
/// ```
/// use crate::CacheList;
///
/// let mut list: CacheList<i32, 10> = CacheList::new();
///
/// list.push(1);
/// list.push(2);
/// list.push(3);
///
/// let mut iter = list.iter_mut();
///
/// while let Some(value) = iter.next() {
/// if *value % 2 == 0 {
/// iter.remove_current();
/// }
/// }
///
/// assert_eq!(list.len(), 2); // Only odd numbers remain.
/// assert_eq!(list.capacity(), 3);
/// ```
pub fn remove_current(&mut self) {
if let Some(current) = self.current {
self.next = self.current.and_then(|mut current| {
let node = unsafe { current.as_mut() };
node.next
});
self.list.remove(current);
self.current = None;
}
}
/// Creates a new iterator starting from the current position of this iterator.
///
/// This method allows for creating a second independent iterator that starts
/// from the current node position of the original iterator.
///
/// # Examples
///
/// ```
/// use crate::CacheList;
/// let mut list: CacheList<i32, 10> = CacheList::new();
///
/// list.push(1);
/// list.push(2);
/// list.push(3);
///
/// let mut iter1 = list.iter_mut();
/// iter1.next(); // Move iter1 forward
///
/// let mut iter2 = iter1.split_at_current();
/// assert_eq!(iter2.next(), Some(&mut 2));
/// ```
pub fn split_at_current(&mut self) -> CacheListIterMut<'_, T, C, L> {
CacheListIterMut {
list: self.list,
current: None,
next: self.next,
}
}
/// Creates a new iterator starting from the next position of this iterator.
///
/// This method allows for creating a second independent iterator that starts
/// from the next node position of the original iterator.
///
/// # Examples
///
/// ```
/// use crate::CacheList;
/// let mut list: CacheList<i32, 10> = CacheList::new();
///
/// list.push(1);
/// list.push(2);
/// list.push(3);
///
/// let mut iter1 = list.iter_mut();
/// iter1.next(); // Move iter1 forward
///
/// let mut iter2 = iter1.split_at_next();
/// assert_eq!(iter2.next(), Some(&mut 3));
/// ```
pub fn split_at_next(&mut self) -> CacheListIterMut<'_, T, C, L> {
let mut iter = CacheListIterMut {
list: self.list,
current: None,
next: self.next,
};
iter.next();
iter
}
/// Returns a mutable reference to the current node's value without advancing the iterator.
///
/// This method allows accessing the current element of the iterator as a mutable reference,
/// enabling modification without moving the iterator forward. If the iterator is not currently
/// pointing to any node (e.g., it has been advanced past the last element), `None` is returned.
///
/// # Returns
///
/// An `Option<&mut T>` that contains a mutable reference to the current element if the iterator
/// is positioned at a valid node, or `None` if the iterator is not pointing to a valid node.
///
/// # Examples
///
/// ```
/// use crate::CacheList;
///
/// let mut list: CacheList<i32, 10> = CacheList::new();
///
/// list.push(1);
/// list.push(2);
/// list.push(3);
///
/// let mut iter = list.iter_mut();
///
/// iter.next(); // Moves to the first element.
///
/// // Access the current element as mutable without advancing the iterator.
/// if let Some(value) = iter.as_mut() {
/// *value *= 10; // Modifies the first element.
/// }
///
/// assert_eq!(list.len(), 3);
///
/// // Verify that the first element was modified.
/// let mut check_iter = list.iter_mut();
/// assert_eq!(check_iter.next(), Some(&mut 10)); // Modified first value.
/// assert_eq!(check_iter.next(), Some(&mut 2)); // Second value remains unchanged.
/// assert_eq!(check_iter.next(), Some(&mut 3)); // Third value remains unchanged.
/// ```
pub fn as_mut(&mut self) -> Option<&mut T> {
if let Some(current) = &mut self.current {
let node = unsafe { current.as_mut() };
node.value.as_mut()
} else {
None
}
}
/// Inserts a new value into the list between the current and next positions of the iterator.
///
/// If the iterator is positioned at a valid node, the new value will be inserted between
/// `self.current` and `self.next`. If `self.current` is `None`, it will insert the value at
/// the tail of the list. If `self.next` is `None`, the new node becomes the new tail of the list.
///
/// # Parameters
/// - `value`: The value to be inserted into the list.
///
/// # Returns
/// - `Option<&mut T>`: A mutable reference to the inserted value, or `None` if insertion fails due
/// to allocation limits.
///
/// # Safety
/// This function assumes the iterator is valid. Unsafe operations are used to directly manipulate
/// the linked nodes and should only be called when the list structure is correct.
///
/// # Examples
///
/// ```
/// use crate::CacheList;
///
/// let mut list: CacheList<i32, 10> = CacheList::new();
/// let mut iter = list.iter_mut();
///
/// iter.insert(1);
/// list.push(3);
///
/// let mut iter = list.iter_mut();
/// iter.next(); // Move to the first element (1)
///
/// // Insert a new value (2) between the current (1) and next (3) positions
/// iter.insert(2);
/// iter.next();
/// iter.insert(4);
/// list.push(5);
///
/// let mut check_iter = list.iter_mut();
/// assert_eq!(check_iter.next(), Some(&mut 1)); // First element
/// assert_eq!(check_iter.next(), Some(&mut 2)); // Inserted element
/// assert_eq!(check_iter.next(), Some(&mut 3)); // Original second element
/// assert_eq!(check_iter.next(), Some(&mut 4)); // Inserted element
/// assert_eq!(check_iter.next(), Some(&mut 5)); // Last element
/// assert_eq!(check_iter.next(), None);
/// ```
pub fn insert(&mut self, value: T) -> Option<&mut T> {
if let Some(current) = &mut self.current {
if let Some(mut new_node) = self.list.allocate_node(value) {
unsafe {
let current_mut = current.as_mut();
let new_node_mut = new_node.as_mut();
new_node_mut.prev = self.current;
new_node_mut.next = self.next;
current_mut.next = Some(new_node);
if let Some(next_node) = &mut self.next {
let next_mut = next_node.as_mut();
next_mut.prev = Some(new_node);
} else {
self.list.tail = Some(new_node);
}
self.current = Some(new_node);
self.list.len += 1;
new_node_mut.value.as_mut()
}
} else {
None
}
} else {
self.list.push(value)
}
}
}
impl<'a, T: Debug, const C: usize, const L: usize> Deref for CacheListIterMut<'a, T, C, L> {
type Target = Option<T>;
fn deref(&self) -> &Self::Target {
if let Some(mut current) = self.current {
let node = unsafe { current.as_mut() };
&node.value
} else {
&None
}
}
}
#[test]
fn test_cachelist() {
let mut list: CacheList<i32, 10> = CacheList::new();
// Push elements to the list
for i in 0..10 {
list.push(i);
}
// Add more elements to test node reuse
for i in 300..400 {
list.push(i);
}
println!("{:?}", list);
// Use the mutable iterator to traverse and remove nodes
let mut iter = list.iter_mut();
while let Some(value) = iter.next() {
if *value % 2 == 0 {
iter.remove_current();
}
}
println!("{:?}", list);
// Continue adding elements to test list behavior
for i in 500..600 {
list.push(i);
}
println!("{:?}", list);
}
#[test]
fn test_cachelist_clone_iterator() {
let mut list: CacheList<i32, 10> = CacheList::new();
// Populate the list
for i in 0..10 {
list.push(i);
}
let mut iter1 = list.iter_mut();
// Move iter1 forward a few steps
iter1.next();
iter1.next();
// Clone iter1 to create iter2 at the current position
let mut iter2 = iter1.split_at_current();
// Use iter2 independently of iter1
if let Some(value) = iter2.next() {
println!("Iter2 next value: {:?}", value); // Should print the next value after iter1's position
}
// Continue using iter1 independently
if let Some(value) = iter1.next() {
println!("Iter1 next value: {:?}", value); // Should print its next value
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment