X-Git-Url: http://git.squeep.com/?p=fb-resolver;a=blobdiff_plain;f=lru_cache.c;fp=lru_cache.c;h=65b7e6f758753cfe3fe0d7fb6b3f52463dc65627;hp=0000000000000000000000000000000000000000;hb=a92970088391362908dfaf949dae799b1525d97e;hpb=aab2bd46dd8d69b34ec9375f47fa12af77a3a7c6

diff --git a/lru_cache.c b/lru_cache.c
new file mode 100644
index 0000000..65b7e6f
--- /dev/null
+++ b/lru_cache.c
@@ -0,0 +1,186 @@
+/*
+	LRU Cache
+
+	A simple base struct for maintaining a least-recently-used cache of
+	entries.
+
+	Entries are pushed onto the front of a deque, overflows are popped
+	off the back.  A hash table indexes the entries for lookup.
+
+	Use a lru_entry_t as the first member of the struct you want to
+	cache, and swaddle these routines with casts.
+
+*/
+#include "lru_cache.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+static inline unsigned long hash_(struct lru_cache_entry *, lru_hash_feed_fn *);
+
+
+/*	lru_cache_new
+	Allocate and initialize a new LRU Cache.
+
+	hash_sz - size of the hash table (this ought to be prime)
+	capacity - retain only this many entries in queue (0 for unlimited)
+	feed - function which provides a buffer for an entry, to generate hash from
+	cmp - function for comparing two entries
+*/
+struct lru_cache *
+lru_cache_new(size_t hash_sz,
+              size_t capacity,
+              lru_hash_feed_fn *feed,
+              lru_entry_cmp_fn *cmp)
+{
+	struct lru_cache *c;
+	size_t sz = sizeof *c + (hash_sz - 1) * sizeof *c->hash;
+	/* hash_sz - 1 because of old-style flexible array */
+
+	c = malloc(sz);
+	if (c == NULL)
+		return NULL;
+
+	*((size_t *)&(c->hash_sz)) = hash_sz;
+	*((size_t *)&(c->capacity)) = capacity;
+
+	c->feed_fn = feed;
+	c->cmp_fn = cmp;
+
+	c->num_entries = 0;
+	c->newest = NULL;
+	c->oldest = NULL;
+
+	memset(c->hash, 0, hash_sz * sizeof *c->hash);
+
+	return c;
+}
+
+
+/*	lru_cache_insert
+	Insert an entry into the front of the queue.
+
+	cache - the cache to use
+	e - the entry to insert
+	overflow - will be set to the entry which was removed if cache is at capacity
+*/
+void
+lru_cache_insert(struct lru_cache *cache, struct lru_cache_entry *e, struct lru_cache_entry **overflow)
+{
+	*overflow = NULL;
+	if (cache->capacity && cache->num_entries == cache->capacity) {
+		*overflow = cache->oldest;
+		lru_cache_extract(cache, *overflow);
+	}
+
+	e->hash_slot = hash_(e, cache->feed_fn) % cache->hash_sz;
+
+	e->hash_next = cache->hash[e->hash_slot].entry;
+	cache->hash[e->hash_slot].entry = e;
+	cache->hash[e->hash_slot].tally++;
+
+	e->prev = NULL;
+	e->next = cache->newest;
+	if (cache->newest)
+		cache->newest->prev = e;
+	else
+		cache->oldest = e;
+	cache->newest = e;
+
+	cache->num_entries++;
+}
+
+
+/*	lru_cache_locate
+	Return the first entry for which cache->cmp_fn equates to the provided
+	entry to match.
+*/
+struct lru_cache_entry *
+lru_cache_locate(struct lru_cache *cache, struct lru_cache_entry *match)
+{
+	struct lru_cache_entry *e;
+	unsigned long hash;
+
+	hash = hash_(match, cache->feed_fn) % cache->hash_sz;
+
+	for (e = cache->hash[hash].entry; e; e = e->hash_next)
+		if (cache->cmp_fn(match, e) == 0)
+			break;
+
+	return e;
+}
+
+
+/*	lru_cache_extract
+	Remove an entry from the cache.
+*/
+void
+lru_cache_extract(struct lru_cache *cache, struct lru_cache_entry *e)
+{
+	/* remove from hash list */
+	if (cache->hash[e->hash_slot].entry == e) {
+		cache->hash[e->hash_slot].entry = e->hash_next;
+	} else {
+		struct lru_cache_entry *hp;
+
+		for (hp = cache->hash[e->hash_slot].entry; hp; hp = hp->hash_next)
+			if (hp->hash_next == e) {
+				hp->hash_next = e->hash_next;
+				break;
+			}
+
+		if (hp) {
+			hp->hash_next = e->hash_next;
+		}
+	}
+	cache->hash[e->hash_slot].tally--;
+
+	/* remove from queue */
+	if (cache->newest == e)
+		cache->newest = e->next;
+	if (cache->oldest == e)
+		cache->oldest = e->prev;
+	if (e->prev)
+		e->prev->next = e->next;
+	if (e->next)
+		e->next->prev = e->prev;
+
+	cache->num_entries--;
+}
+
+
+/*	lru_cache_foreach
+	Calls fn(entry, index, data) for each entry in cache, from newest to oldest.
+*/
+void
+lru_cache_foreach(struct lru_cache *cache, void (*fn)(lru_entry_t *, size_t, void *), void *data)
+{
+	struct lru_cache_entry *e;
+	size_t i;
+
+	for (i = 0, e = cache->newest; e; e = e->next, i++)
+		fn(e, i, data);
+}
+
+
+/*	hash_
+	djbx33x
+	The hash used for lookup table.  Is best at lowercase strings, but should
+	be non-pathological for most inputs.
+*/
+static
+inline
+unsigned long
+hash_(struct lru_cache_entry *e, lru_hash_feed_fn *feed_fn)
+{
+	unsigned long hash = 5381;
+	char *buf;
+	size_t len;
+
+	feed_fn(e, &buf, &len);
+
+	while (len--)
+		hash = ((hash << 5) + hash) ^ *buf++;
+
+	return hash;
+}