initial overhaul of resolver

[fb-resolver] / lru_cache.c

diff --git a/lru_cache.c b/lru_cache.c
new file mode 100644 (file)
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;
+}