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

diff --git a/lru_cache.h b/lru_cache.h
new file mode 100644
index 0000000..bda2619
--- /dev/null
+++ b/lru_cache.h
@@ -0,0 +1,50 @@
+#ifndef LRU_CACHE_H
+#define LRU_CACHE_H
+
+#include <stddef.h>
+
+struct lru_cache_entry {
+	struct lru_cache_entry *next;
+	struct lru_cache_entry *prev;
+	struct lru_cache_entry *hash_next;
+	unsigned long hash_slot;
+};
+typedef struct lru_cache_entry lru_entry_t;
+
+
+/*
+	A function which, given an entry, returns a pointer to a buffer
+	and a number of bytes to use to generate a hash of the entry.
+*/
+typedef void (lru_hash_feed_fn)(lru_entry_t *, char **, size_t *);
+
+/*
+	A function which compares two entries for equality.
+*/
+typedef int (lru_entry_cmp_fn)(lru_entry_t *, lru_entry_t *);
+
+struct lru_cache_hashslot_ {
+	size_t tally;
+	struct lru_cache_entry *entry;
+};
+
+struct lru_cache {
+	const size_t hash_sz;
+	const size_t capacity;
+
+	lru_hash_feed_fn *feed_fn;
+	lru_entry_cmp_fn *cmp_fn;
+
+	size_t num_entries;
+	struct lru_cache_entry *newest;
+	struct lru_cache_entry *oldest;
+	struct lru_cache_hashslot_ hash[1];
+};
+
+struct lru_cache *lru_cache_new(size_t, size_t, lru_hash_feed_fn *, lru_entry_cmp_fn *);
+void lru_cache_insert(struct lru_cache *, lru_entry_t *, lru_entry_t **);
+void lru_cache_extract(struct lru_cache *, lru_entry_t *);
+lru_entry_t *lru_cache_locate(struct lru_cache *, lru_entry_t *);
+void lru_cache_foreach(struct lru_cache *, void (*)(lru_entry_t *, size_t, void *), void *);
+
+#endif /* LRU_CACHE_H */