Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
a LRU cache in C using uthash
#include <string.h>
#include <uthash.h>
// this is an example of how to do a LRU cache in C using uthash
// http://uthash.sourceforge.net/
// by Jehiah Czebotar 2011 - jehiah@gmail.com
// this code is in the public domain http://unlicense.org/
#define MAX_CACHE_SIZE 100000
struct CacheEntry {
char *key;
char *value;
UT_hash_handle hh;
};
struct CacheEntry *cache = NULL;
char *value find_in_cache(char *key)
{
struct CacheEntry *entry;
HASH_FIND_STR(cache, key, entry)
if (entry) {
// remove it (so the subsequent add will throw it on the front of the list)
HASH_DELETE(hh, cache, entry);
HASH_ADD_KEYPTR(hh, cache, entry->key, strlen(entry->key), entry);
return entry->value;
}
return NULL;
}
void add_to_cache(char *key, char *value)
{
struct CacheEntry *entry, *tmp_entry;
entry = malloc(sizeof(struct CacheEntry));
entry->key = strdup(key);
entry->value = strdup(value);
HASH_ADD_KEYPTR(hh, cache, entry->key, strlen(entry->key), entry);
// prune the cache to MAX_CACHE_SIZE
if (HASH_COUNT(cache) >= MAX_CACHE_SIZE) {
HASH_ITER(hh, cache, entry, tmp_entry) {
// prune the first entry (loop is based on insertion order so this deletes the oldest item)
HASH_DELETE(hh, cache, entry);
free(entry->key);
free(entry->value);
free(entry);
break;
}
}
}
@lericson
Copy link

lericson commented Aug 28, 2011

ISTM that when the cache is full, the behavior will be that the next add should clear the entire cache, no? Considering that the add function deletes from the hash without restriction to number of entries at all.

@jehiah
Copy link
Author

jehiah commented Aug 28, 2011

@lericson Line 47 has a break; which means that when the cache is full, it will only delete a single entry from the cache (which is all you need since you are only adding one item)

@lericson
Copy link

lericson commented Aug 28, 2011

Oh hey, completely missed that.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment