initial overhaul of resolver

[fb-resolver] / lru_cache.h

diff --git a/lru_cache.h b/lru_cache.h
new file mode 100644 (file)
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 */