LRU Cache (C)
Source: LeetCode #146
Topics: data structures, caching
Problem
Implement a fixed-capacity Least-Recently-Used cache of int -> int over
caller-provided storage (no allocation):
typedef struct LRUNode { int key, val; struct LRUNode *prev, *next; int used; } LRUNode;
typedef struct { LRUNode *nodes; size_t cap; size_t count; LRUNode head, tail; } LRU;
void lru_init(LRU *c, LRUNode *storage, size_t cap); // storage holds cap slots
bool lru_get(LRU *c, int key, int *out); // true + *out if present; marks MRU
void lru_put(LRU *c, int key, int val); // insert/update; evict LRU when full
size_t lru_len(const LRU *c);
- The caller owns the
LRUNode storage[cap] array; you never call malloc.
lru_get returns the value and refreshes recency, or false.lru_put inserts or updates and refreshes recency; when over capacity, evict
the least-recently-used entry.- A zero-capacity cache stores nothing.
A doubly-linked list with embedded sentinels (most-recent after head,
least-recent before tail) plus a linear scan for lookup is one clean approach.
Grading
Your lru.c is compiled together with a trusted tests.c (which #includes it)
via cc -std=c11 -O2. The tests print TAP output. Only lru.c is yours to edit.
Sign in to submit your solution.