LRU cache for string keys

Challenge

Build a least-recently-used (LRU) cache that maps string keys to int values.

Task

Implement the following API. When the cache is over capacity, evict the least-recently-used key. Both a successful slru_get and a slru_put count as "using" a key (moving it to most-recently-used).

typedef struct slru slru_t;
slru_t *slru_create(int capacity);
int     slru_get(slru_t *c, const char *key, int *out); /* 1=found, 0=missing */
void    slru_put(slru_t *c, const char *key, int value);
void    slru_destroy(slru_t *c);

Input

• capacity: maximum number of entries (capacity > 0).
• key: a NUL-terminated string, up to 64 bytes (the cache keeps its own copy).
• value: the int to store.
• out: where slru_get writes the found value.

Output

• slru_get: 1 and writes the value through out if found; 0 if missing.
• slru_put: nothing; inserts or updates, evicting the LRU key on overflow.

Example

slru_create(2)
slru_put("alpha", 1); slru_put("beta", 2)
slru_get("alpha", &v)   ->   1, v == 1   (alpha now most-recently used)
slru_put("gamma", 3)                      (evicts "beta", the LRU key)
slru_get("beta", &v)    ->   0            (evicted)
slru_put("alpha", 99)                     (update)
slru_get("alpha", &v)   ->   1, v == 99

Edge cases

• Capacity 1.
• Repeated put of an existing key updates the value and counts as a use (no eviction).
• get of a missing key returns 0.

Rules

• Store keys with strdup; free each key on eviction and on destroy. Compare keys with strcmp, not ==.

Why this matters

Real LRU caches in the wild use string keys: URL caches, DNS caches, file path lookups. Combining the data structure with string hashing brings together two big topics.

Input format

capacity > 0; key NUL-terminated (<= 64 bytes); value; out receives the found value.

Output format

slru_get returns 1/0 and writes through out on a hit; slru_put returns nothing.

Constraints

Use strdup for key storage. Free on eviction and destroy. Compare with strcmp.

Starter code

typedef struct slru slru_t;
slru_t *slru_create(int capacity);
int     slru_get(slru_t *c, const char *key, int *out);
void    slru_put(slru_t *c, const char *key, int value);
void    slru_destroy(slru_t *c);

Common mistakes

Forgetting to move-to-front on get; not freeing the strdup'd key on eviction (leak); using == for string compare.

Edge cases to handle

Capacity 1. Repeated put of same key (update, no eviction).

Complexity

O(n) lookup in the simple list version; O(1) with a proper hash map.

Background lessons

• Hashing — turning keys into table indices