You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

1.6 KiB

Title: Generic LRU Cache in C Author: Alessandro Mauri

Generic LRU Cache in C

I've been working on an immediate mode gui library and for the renderer I took inspiration from Casey Muratori's refterm for the font rendering. Doing so I needed to implement a hash map and a LRU cache in top of it, so I did and took the time to write a macro abomination in order to make it type generic.

Well in reality since I made it to store font glyphs it uses uint32_ts for keys but it can be easily extended to use strings since the underlying hash map is type generic as well. So here they are:


/* Declare the cache, hash_u32 and hash_cmp_u32 are ready-made functions in 
 * generic_hash.h */
#include "generic_cache.h"
static inline unsigned int hash(unsigned int code)
	// identity map the ascii range
	return code < 128 ? code : hash_u32(code);
CACHE_DECL(cache, struct font_glyph, hash, hash_cmp_u32)

/* Initialize the cache */
struct cache c = cache_init(); // CACHE_SIZE is constant

/* Searching from in the cache */
const struct font_glyph *r;
unsigned int code = 'F';
if ((r = cache_search(&c, code)) != NULL) {
	// ...

/* Inserting is a bit different, you first find an open (unused) spot and then
 * you provide it to cache_insert() */
struct font_glyph g = {.codepoint = 'a', ...};
unsigned int spot = cache_get(&c);
cache_insert(&c, &g, 'a', spot);