# 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
