LRU cache for string keys

Challenge

Implement an LRU cache mapping strings to ints:

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);

On overflow, evict the least-recently-used key. Both get and put count as 'use' on hit.

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. Keys <= 64 bytes.

Output format

See API.

Constraints

Use strdup for key storage. Free on eviction and destroy.

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