Implement an LRU cache.
#include <stdbool.h>
#include <string.h>
/* fixed capacity, keys 0..MAX_KEY-1, O(1) get/put using an index table + doubly linked list */
#define CAPACITY 4
#define MAX_KEY 1024
typedef struct { int key, val, prev, next; } entry_t; /* links are indexes into the pool */
typedef struct {
entry_t e[CAPACITY];
int where[MAX_KEY]; /* key -> slot index, or -1 */
int head, tail, used; /* head = most recent, tail = least recent */
} lru_t;
void lru_init(lru_t *c) { memset(c->where, -1, sizeof c->where); c->head = c->tail = -1; c->used = 0; }
static void unlink_e(lru_t *c, int i)
{
entry_t *x = &c->e[i];
if (x->prev >= 0) c->e[x->prev].next = x->next; else c->head = x->next;
if (x->next >= 0) c->e[x->next].prev = x->prev; else c->tail = x->prev;
}
static void push_front_e(lru_t *c, int i)
{
c->e[i].prev = -1; c->e[i].next = c->head;
if (c->head >= 0) c->e[c->head].prev = i; else c->tail = i;
c->head = i;
}
bool lru_get(lru_t *c, int key, int *val)
{
int i = c->where[key];
if (i < 0) return false;
unlink_e(c, i); push_front_e(c, i); /* mark as most recently used */
*val = c->e[i].val;
return true;
}
void lru_put(lru_t *c, int key, int val)
{
int i = c->where[key];
if (i >= 0) { c->e[i].val = val; unlink_e(c, i); push_front_e(c, i); return; }
if (c->used < CAPACITY) i = c->used++;
else { i = c->tail; c->where[c->e[i].key] = -1; unlink_e(c, i); } /* evict LRU */
c->e[i].key = key; c->e[i].val = val; c->where[key] = i;
push_front_e(c, i);
}
Points: a hash map (here a direct index table, since keys are small) finds an entry in O(1), and a doubly linked list keeps entries in recency order: move to front on every access, evict from the tail when full. With arbitrary keys, replace where[] with a hash table. Using indexes into a fixed pool instead of pointers makes it allocation-free for embedded use. Real uses: page caches, DNS caches, a cache of decoded fonts/images on a display device.