Array-backed LRU cache with bounded capacity in C
C
#include <stddef.h>
typedef struct { int key, val; } Item;
typedef struct { Item *a; size_t cap, n; } LRU;
int lru_get(LRU *c, int k, int *v) {
for (size_t i = 0; i < c->n; i++) {
if (c->a[i].key != k) continue;
Item hit = c->a[i];
for (size_t j = i; j > 0; j--) c->a[j] = c->a[j - 1];
*v = hit.val;
c->a[0] = hit;
return 1;
}
return 0;
}
void lru_put(LRU *c, int k, int v) {
int old;
if (c->cap == 0) return;
if (lru_get(c, k, &old)) { c->a[0].val = v; return; }
if (c->n < c->cap) c->n++;
for (size_t j = c->n - 1; j > 0; j--) c->a[j] = c->a[j - 1];
c->a[0] = (Item){k, v};
}