Clock Ring (Second-Chance)

What It Is

The Clock policy maintains a circular set of slots and a moving “hand”. Each slot has a reference bit.

This is a general-purpose DS for:

• Clock / second-chance eviction
• CAR/CLOCK-Pro style variants (with extra status bits)

Core Types

• slots: Vec<SlotMeta> (dense)
• hand: usize
• index: HashMap<K, usize> (key → slot)

Minimal SlotMeta:

• key: K (or empty)
• referenced: bool
• occupied: bool

Operations

touch(key)

• Find slot via index; set referenced = true.

insert(key, value)

• If key exists: update value + referenced = true.
• Else: find a free slot or evict:
  • Loop: if referenced set → clear it and advance; else evict this slot.

evict_one() -> K

• Advance hand until a victim is found; return victim key.

Complexity

• O(1) amortized for eviction; worst-case can scan many slots if all are referenced.

Implementation Notes

• Use a dense array of slots for locality; avoid linked lists.
• For predictable performance, consider limiting scan length or adding an epoch-based reference reset (NRU-like).