FIFO (First-In, First-Out)

Feature: policy-fifo

Goal

Evict the oldest inserted resident entry when the cache is full.

Core Data Structures

Typical O(1) FIFO implementation:

• HashMap<K, V> for key lookup and storage
• VecDeque<K> (or ring buffer) to track insertion order

In cachekit, FIFO is implemented in src/policy/fifo/ with:

• a key/value map plus an insertion-order queue
• lazy stale entry handling (queue entries can become stale if the key is removed/updated)

Operations

insert(key, value)

• If key already exists: update the stored value, do not change insertion order.
• If cache is at capacity: evict from the front of the queue until a live key is found.
• Insert the new key/value and push the key to the back of the queue.

get(key)

• Lookup only; FIFO does not reorder on access.

pop_oldest()

• Pop from queue front until you find a key still present in the map; remove it from the map and return it.

Complexity & Overhead

• Lookup: O(1)
• Insert: O(1) amortized; eviction may skip stale queue entries
• Memory: HashMap + queue of keys

Edge Cases / Implementation Notes

• Stale keys: if you support remove(key) (or “update” that replaces storage), you must reconcile the queue.
  • Eager cleanup requires O(n) removal from the middle of a VecDeque.
  • Lazy cleanup keeps hot path O(1) and pays cleanup during eviction.
• Duplicate keys in queue: if your update path pushes keys again, you must handle duplicates on eviction; the repo implementation avoids changing order on update.

References

• Wikipedia: https://en.wikipedia.org/wiki/Cache_replacement_policies