Lines
95.82 %
Functions
58.5 %
Branches
100 %
use std::collections::HashSet;
use std::fmt::Debug;
use std::marker::PhantomData;
pub struct LruCache<Key, Value> {
nodes: Vec<Node<Key, Value>>,
head: Option<NodeId>,
tail: Option<NodeId>,
vacant: Option<NodeId>,
sequence: usize,
length: usize,
}
impl<Key, Value> LruCache<Key, Value> {
pub fn new(capacity: usize) -> Self {
Self {
nodes: Vec::with_capacity(capacity),
head: None,
tail: None,
vacant: None,
sequence: 0,
length: 0,
pub const fn len(&self) -> usize {
self.length
pub const fn sequence(&self) -> usize {
self.sequence
pub const fn head(&self) -> Option<NodeId> {
self.head
pub const fn tail(&self) -> Option<NodeId> {
self.tail
pub const fn iter(&self) -> Iter<'_, Key, Value> {
Iter {
cache: self,
node: IterState::BeforeHead,
pub fn get(&mut self, node: NodeId) -> &Node<Key, Value> {
self.touch(node);
&self.nodes[node.as_usize()]
pub fn get_without_touch(&self, node: NodeId) -> &Node<Key, Value> {
pub fn get_mut(&mut self, node: NodeId) -> &mut Node<Key, Value> {
&mut self.nodes[node.as_usize()]
pub fn push(&mut self, key: Key, value: Value) -> (NodeId, Option<Removed<Key, Value>>) {
let (node, result) = if self.head.is_some() {
self.push_front(key, value)
} else {
// First node of the list.
self.allocate_node(key, value)
};
(
node,
result.map(|(key, value)| Removed::Evicted(key, value)),
)
pub fn touch(&mut self, node_index: NodeId) {
if self.head == Some(node_index) {
// No-op.
return;
self.sequence += 1;
// An entry already exists. Reuse the node.
self.nodes[node_index.as_usize()].last_accessed = self.sequence;
// Update the next pointer to the current head.
let mut next = self.head;
std::mem::swap(&mut next, &mut self.nodes[node_index.as_usize()].next);
// Get and clear the previous node, as this node is going to be the new
// head.
let previous = self.nodes[node_index.as_usize()].previous.take().unwrap();
// Update the previous pointer's next to the previous next value.
self.nodes[previous.as_usize()].next = next;
if self.tail == Some(node_index) {
// If this is the tail, update the tail to the previous node.
self.tail = Some(previous);
// Otherwise, we need to update the next node's previous to point to
// this node's former previous.
self.nodes[next.unwrap().as_usize()].previous = Some(previous);
// Move this node to the front
self.nodes[self.head.unwrap().as_usize()].previous = Some(node_index);
self.head = Some(node_index);
fn push_front(&mut self, key: Key, value: Value) -> (NodeId, Option<(Key, Value)>) {
let (node, removed) = self.allocate_node(key, value);
let mut entry = &mut self.nodes[node.as_usize()];
entry.last_accessed = self.sequence;
entry.next = Some(self.head.unwrap());
let mut previous_head = &mut self.nodes[self.head.unwrap().as_usize()];
debug_assert!(previous_head.previous.is_none());
previous_head.previous = Some(node);
self.head = Some(node);
(node, removed)
fn allocate_node(&mut self, key: Key, value: Value) -> (NodeId, Option<(Key, Value)>) {
if let Some(vacant) = self.vacant {
// Pull a node off the vacant list.
self.vacant = self.nodes[vacant.as_usize()].next;
self.nodes[vacant.as_usize()].next = None;
self.nodes[vacant.as_usize()].entry = Entry::Occupied { key, value };
self.length += 1;
if self.head.is_none() {
self.head = Some(vacant);
self.tail = Some(vacant);
(vacant, None)
} else if self.nodes.len() == self.nodes.capacity() {
// Expire the least recently used key (tail).
let index = self.tail.unwrap();
self.tail = self.nodes[index.as_usize()].previous;
if let Some(previous) = self.tail {
self.nodes[previous.as_usize()].next = None;
self.nodes[index.as_usize()].previous = None;
let mut entry = Entry::Occupied { key, value };
std::mem::swap(&mut entry, &mut self.nodes[index.as_usize()].entry);
(index, entry.into())
// We have capacity to fill.
let index = NodeId(self.nodes.len() as u32);
self.nodes.push(Node {
last_accessed: self.sequence,
previous: None,
next: None,
entry: Entry::Occupied { key, value },
});
self.head = Some(index);
self.tail = Some(index);
(index, None)
pub fn remove(&mut self, node: NodeId) -> ((Key, Value), Option<NodeId>, Option<NodeId>) {
self.length -= 1;
let removed = self.nodes[node.as_usize()].entry.evict();
let mut next = self.vacant;
std::mem::swap(&mut next, &mut self.nodes[node.as_usize()].next);
let previous = self.nodes[node.as_usize()].previous.take();
if let Some(previous) = previous {
if let Some(next) = next {
self.nodes[next.as_usize()].previous = previous;
if self.tail == Some(node) {
self.tail = previous;
if self.head == Some(node) {
self.head = next;
self.vacant = Some(node);
(removed, next, previous)
impl<Key, Value> Debug for LruCache<Key, Value>
where
Key: Debug,
Value: Debug,
{
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
let mut list = f.debug_list();
if let Some(head) = self.head {
let mut seen_nodes = HashSet::new();
let mut current_node = head;
let mut end_found = false;
while seen_nodes.insert(current_node) {
let node = &self.nodes[current_node.as_usize()];
list.entry(node);
current_node = if let Some(next) = node.next {
next
end_found = true;
break;
assert!(end_found, "cycle detected");
list.finish()
#[derive(Debug)]
enum Entry<Key, Value> {
Occupied { key: Key, value: Value },
Vacant,
impl<Key, Value> Entry<Key, Value> {
fn evict(&mut self) -> (Key, Value) {
let mut entry = Self::Vacant;
std::mem::swap(&mut entry, self);
match entry {
Self::Occupied { key, value } => (key, value),
Self::Vacant => unreachable!("evict called on a vacant entry"),
impl<Key, Value> From<Entry<Key, Value>> for Option<(Key, Value)> {
fn from(entry: Entry<Key, Value>) -> Self {
Entry::Occupied { key, value } => Some((key, value)),
Entry::Vacant => None,
pub struct Node<Key, Value> {
entry: Entry<Key, Value>,
previous: Option<NodeId>,
next: Option<NodeId>,
last_accessed: usize,
impl<Key, Value> Debug for Node<Key, Value>
let mut debug = f.debug_struct("Node");
if let Entry::Occupied { key, value } = &self.entry {
debug.field("key", key);
debug.field("value", value);
debug.field("last_accessed", &self.last_accessed);
debug.finish()
impl<Key, Value> Node<Key, Value> {
pub const fn last_accessed(&self) -> usize {
self.last_accessed
pub fn key(&self) -> &Key {
match &self.entry {
Entry::Occupied { key, .. } => key,
Entry::Vacant => unreachable!("EntryRef can't be made against Vacant"),
pub fn value(&self) -> &Value {
Entry::Occupied { value, .. } => value,
pub fn value_mut(&mut self) -> &mut Value {
match &mut self.entry {
pub fn replace_value(&mut self, mut new_value: Value) -> Value {
Entry::Occupied { value, .. } => {
std::mem::swap(value, &mut new_value);
new_value
/// A reference to an entry in a Least Recently Used map.
pub struct EntryRef<'a, Cache, Key, Value>
Cache: EntryCache<Key, Value>,
cache: &'a mut Cache,
node: NodeId,
accessed: bool,
_phantom: PhantomData<(Key, Value)>,
pub trait EntryCache<Key, Value> {
fn cache(&self) -> &LruCache<Key, Value>;
fn cache_mut(&mut self) -> &mut LruCache<Key, Value>;
fn remove(&mut self, node: NodeId) -> ((Key, Value), Option<NodeId>, Option<NodeId>);
#[derive(Debug, Clone, Copy, Eq, PartialEq, Hash)]
#[repr(transparent)]
pub struct NodeId(u32);
impl NodeId {
const fn as_usize(self) -> usize {
self.0 as usize
impl<'a, Cache, Key, Value> EntryRef<'a, Cache, Key, Value>
pub(crate) fn new(cache: &'a mut Cache, node: NodeId) -> Self {
cache,
accessed: false,
_phantom: PhantomData,
/// Returns the key of this entry.
#[must_use]
self.cache.cache().get_without_touch(self.node).key()
/// Returns the value of this entry.
///
/// This function touches the key, making it the most recently used key.
/// This function only touches the key once. Subsequent calls will return
/// the value without touching the key. This remains true until
/// `move_next()` or `move_previous()` are invoked.
pub fn value(&mut self) -> &Value {
if !self.accessed {
self.accessed = true;
self.touch();
self.cache.cache_mut().get(self.node).value()
/// Touches this key, making it the most recently used key.
pub fn touch(&mut self) {
self.cache.cache_mut().touch(self.node);
/// This function does not touch the key, preserving its current position in
/// the lru cache.
pub fn peek_value(&self) -> &Value {
self.cache.cache().get_without_touch(self.node).value()
/// Returns the number of changes to the cache since this key was last
/// touched.
pub fn staleness(&self) -> usize {
self.cache.cache().sequence().wrapping_sub(
self.cache
.cache()
.get_without_touch(self.node)
.last_accessed,
/// Returns an iterator over the least-recently used keys beginning with the
/// current entry.
pub fn iter(&self) -> Iter<'_, Key, Value> {
cache: self.cache.cache(),
node: IterState::StartingAt(self.node),
/// Updates this reference to point to the next least recently used key in
/// the list. Returns true if a next entry was found, or returns false if
/// the entry is the last entry in the list.
pub fn move_next(&mut self) -> bool {
if let Some(next) = self.cache.cache().get_without_touch(self.node).next {
self.node = next;
self.accessed = false;
true
false
/// Updates this reference to point to the next most recently used key in
/// the list. Returns true if a previous entry was found, or returns false
/// if the entry is the first entry in the list.
pub fn move_previous(&mut self) -> bool {
if let Some(previous) = self.cache.cache().get_without_touch(self.node).previous {
self.node = previous;
fn remove_with_direction(mut self, move_next: bool) -> ((Key, Value), Option<Self>) {
let (removed, next, previous) = self.cache.remove(self.node);
let new_self = match (move_next, next, previous) {
(true, Some(next), _) => {
Some(self)
(false, _, Some(previous)) => {
_ => None,
(removed, new_self)
/// Removes and returns the current entry's key and value.
pub fn take(self) -> (Key, Value) {
let (removed, _) = self.remove_with_direction(true);
removed
/// Removes and returns the current entry's key and value. If this was not
/// the last entry, the next entry's [`EntryRef`] will be returned.
pub fn take_and_move_next(self) -> ((Key, Value), Option<Self>) {
self.remove_with_direction(true)
/// the first entry, the previous entry's [`EntryRef`] will be returned.
pub fn take_and_move_previous(self) -> ((Key, Value), Option<Self>) {
self.remove_with_direction(false)
/// Removes the current entry. If this was not the last entry, the next
/// entry's [`EntryRef`] will be returned.
pub fn remove_moving_next(self) -> Option<Self> {
let (_, new_self) = self.take_and_move_next();
new_self
/// Removes the current entry. If this was not the first entry, the previous
pub fn remove_moving_previous(self) -> Option<Self> {
let (_, new_self) = self.take_and_move_previous();
/// A removed value or entry.
#[derive(Debug, Eq, PartialEq)]
pub enum Removed<Key, Value> {
/// The previously stored value for the key that was written to.
PreviousValue(Value),
/// An entry was evicted to make room for the key that was written to.
Evicted(Key, Value),
/// A double-ended iterator over a cache's keys and values in order from most
/// recently touched to least recently touched.
pub struct Iter<'a, Key, Value> {
cache: &'a LruCache<Key, Value>,
node: IterState,
enum IterState {
BeforeHead,
AfterTail,
StartingAt(NodeId),
Node(NodeId),
impl<'a, Key, Value> Iterator for Iter<'a, Key, Value> {
type Item = (&'a Key, &'a Value);
fn next(&mut self) -> Option<Self::Item> {
let next_node = match self.node {
IterState::BeforeHead => self.cache.head,
IterState::StartingAt(node) => Some(node),
IterState::Node(node) => self.cache.nodes[node.as_usize()].next,
IterState::AfterTail => None,
if let Some(node_id) = next_node {
let node = &self.cache.nodes[node_id.as_usize()];
self.node = IterState::Node(node_id);
Some((node.key(), node.value()))
self.node = IterState::AfterTail;
None
impl<'a, Key, Value> DoubleEndedIterator for Iter<'a, Key, Value> {
fn next_back(&mut self) -> Option<Self::Item> {
let previous_node = match self.node {
IterState::BeforeHead => None,
IterState::StartingAt(node) | IterState::Node(node) => {
self.cache.nodes[node.as_usize()].previous
IterState::AfterTail => self.cache.tail,
if let Some(node_id) = previous_node {
self.node = IterState::BeforeHead;
pub struct IntoIter<Key, Value> {
cache: LruCache<Key, Value>,
impl<Key, Value> From<LruCache<Key, Value>> for IntoIter<Key, Value> {
fn from(cache: LruCache<Key, Value>) -> Self {
Self { cache }
impl<Key, Value> Iterator for IntoIter<Key, Value> {
type Item = (Key, Value);
self.cache.head().map(|node| {
let (removed, ..) = self.cache.remove(node);
})