Implementing your own policy

PaperCache makes it easy to implement your own eviction policies. Here, we describe how to add a custom eviction policy to PaperCache by implementing the

LRU

eviction policy.

Add our new policy as an enum entry in paper-cache/src/policy.rs , following existing examples.
Add the file
lru_stack.rs
to paper-cache/src/worker/policy/policy_stack/ .
Create a struct to hold the state of the custom eviction policy. In this case, we will hold all the keys in LRU order in a HashList (i.e., doubly-linked list + hash table for O(1) operations) from the kwik library:
1234567
```
use kwik::collections::HashList;
use crate::{HashedKey, NoHasher};

#[derive(Default)]
pub struct LruStack {
    stack: HashList<HashedKey, NoHasher>,
}
```
We disable hashing in the HashList as the keys are pre-hashed by the cache.

Implement the PolicyStack trait for our new struct:

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354

use crate::{
    policy::PaperPolicy,
    object::ObjectSize,
    worker::policy::policy_stack::PolicyStack,
};

impl PolicyStack for LruStack {
    /// A utility function used internally by PaperCache.
    fn is_policy(&self, policy: PaperPolicy) -> bool {
        matches!(policy, PaperPolicy::Lru)
    }

    /// Returns the number of keys in the stack.
    fn len(&self) -> usize {
        self.stack.len()
    }

    /// Checks if the supplied key exists in the stack.
    fn contains(&self, key: HashedKey) -> bool {
        self.stack.contains(&key)
    }

    /// Inserts a new key into the stack. Be sure to not have duplicate keys
    /// and do not perform any evictions here. In the case of LRU, we do not
    /// need to use the object size, though in other policies it may be required.
    fn insert(&mut self, key: HashedKey, _: ObjectSize) {
        if self.stack.contains(&key) {
            return self.update(key);
        }

        self.stack.push_front(key);
    }

    /// Updates an existing key in the stack. In this case, move the key
    /// to the front of the stack.
    fn update(&mut self, key: HashedKey) {
        self.stack.move_front(&key);
    }

    /// Remove the supplied key from the stack.
    fn remove(&mut self, key: HashedKey) {
        self.stack.remove(&key);
    }

    /// Clear the stack.
    fn clear(&mut self) {
        self.stack.clear();
    }

    /// Perform one eviction from the stack.
    fn evict_one(&mut self) -> Option<HashedKey> {
        self.stack.pop_back()
    }
}

Although not strictly necessary, adding tests to ensure your stack is working correctly is a good idea here (you can find how to do this in existing examples in other policy implementations).

Add our new policy to the
init_policy_stack
function in paper-cache/src/worker/policy/policy_stack/mod.rs .

Our new policy is now implemented in PaperCache!