--- /dev/null
+/*
+ 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;
+}