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.
51 lines
1.6 KiB
51 lines
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][rt] 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_t`s 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:
|
|
|
|
- [hash map][hm]
|
|
- [LRU cache][ch]
|
|
|
|
Usage:
|
|
|
|
```
|
|
/* 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);
|
|
|
|
```
|
|
|
|
[rt]: https://github.com/cmuratori/refterm
|
|
[hm]: https://git.alemauri.eu/alema/ugui/src/branch/master/text_rendering/generic_hash.h
|
|
[ch]: https://git.alemauri.eu/alema/ugui/src/branch/master/text_rendering/generic_cache.h
|
|
|