git » libfiu » commit 2d6f6e7

diff --git a/libfiu/hash.c b/libfiu/hash.c
index ee6b5c1..e8b037d 100644
--- a/libfiu/hash.c
+++ b/libfiu/hash.c
@@ -4,6 +4,8 @@
  *
  * Takes \0-terminated strings as keys, and void * as values.
  * It is tuned for a small number of elements (< 1000).
+ *
+ * It is NOT thread-safe.
  */
 
 #include <sys/types.h>		/* for size_t */
@@ -12,6 +14,7 @@
 #include <stdlib.h>		/* for malloc() */
 #include <string.h>		/* for memcpy()/memcmp() */
 #include <stdio.h>		/* snprintf() */
+#include <pthread.h>		/* read-write locks */
 #include "hash.h"
 
 /* MurmurHash2, by Austin Appleby. The one we use.
@@ -84,6 +87,12 @@ struct hash {
 /* Minimum table size. */
 #define MIN_SIZE 10
 
+/* Dumb destructor, used to simplify the code when no destructor is given. */
+static void dumb_destructor(void *value)
+{
+	return;
+}
+
 struct hash *hash_create(void (*destructor)(void *))
 {
 	struct hash *h = malloc(sizeof(struct hash));
@@ -100,6 +109,10 @@ struct hash *hash_create(void (*destructor)(void *))
 
 	h->table_size = MIN_SIZE;
 	h->nentries = 0;
+
+	if (destructor == NULL)
+		destructor = dumb_destructor;
+
 	h->destructor = destructor;
 
 	return h;
@@ -107,7 +120,7 @@ struct hash *hash_create(void (*destructor)(void *))
 
 void hash_free(struct hash *h)
 {
-	int i;
+	size_t i;
 	struct entry *entry;
 
 	for (i = 0; i < h->table_size; i++) {
@@ -264,3 +277,171 @@ bool hash_del(struct hash *h, const char *key)
 
 }
 
+/* Generic, simple cache.
+ *
+ * It is implemented using a hash table and manipulating it directly when
+ * needed.
+ *
+ * It favours reads over writes, and it's very basic.
+ * It IS thread-safe.
+ */
+
+struct cache {
+	struct hash *hash;
+	size_t size;
+	pthread_rwlock_t lock;
+};
+
+struct cache *cache_create()
+{
+	struct cache *c;
+
+	c = malloc(sizeof(struct cache));
+	if (c == NULL)
+		return NULL;
+
+	c->hash = hash_create(NULL);
+	if (c->hash == NULL) {
+		free(c);
+		return NULL;
+	}
+
+	pthread_rwlock_init(&c->lock, NULL);
+
+	return c;
+}
+
+void cache_free(struct cache *c)
+{
+	hash_free(c->hash);
+	pthread_rwlock_destroy(&c->lock);
+	free(c);
+}
+
+/* Internal non-locking version of cache_invalidate(). */
+static void _cache_invalidate(struct cache *c)
+{
+	size_t i;
+	struct entry *entry;
+
+	for (i = 0; i < c->hash->table_size; i++) {
+		entry = c->hash->entries + i;
+		if (entry->in_use == IN_USE) {
+			free(entry->key);
+			entry->key = NULL;
+			entry->value = NULL;
+			entry->in_use = NEVER;
+		}
+	}
+}
+
+bool cache_invalidate(struct cache *c)
+{
+	pthread_rwlock_wrlock(&c->lock);
+	_cache_invalidate(c);
+	pthread_rwlock_unlock(&c->lock);
+
+	return true;
+}
+
+bool cache_resize(struct cache *c, size_t new_size)
+{
+	pthread_rwlock_wrlock(&c->lock);
+	if (new_size > c->size) {
+		if (resize_table(c->hash, new_size)) {
+			c->size = new_size;
+			goto success;
+		}
+	} else {
+		/* TODO: Implement shrinking. We just invalidate everything
+		 * for now, and then resize. */
+		_cache_invalidate(c);
+
+		if (resize_table(c->hash, new_size)) {
+			c->size = new_size;
+			goto success;
+		}
+	}
+
+	pthread_rwlock_unlock(&c->lock);
+	return false;
+
+success:
+	pthread_rwlock_unlock(&c->lock);
+	return true;
+}
+
+struct entry *entry_for_key(struct cache *c, const char *key)
+{
+	size_t pos;
+	struct entry *entry;
+
+	pos = murmurhash2(key, strlen(key)) % c->hash->table_size;
+
+	entry = c->hash->entries + pos;
+
+	return entry;
+}
+
+bool cache_get(struct cache *c, const char *key, void **value)
+{
+	pthread_rwlock_rdlock(&c->lock);
+	struct entry *e = entry_for_key(c, key);
+
+	*value = NULL;
+
+	if (e->in_use != IN_USE)
+		goto miss;
+
+	if (strcmp(key, e->key) == 0) {
+		*value = e->value;
+		goto hit;
+	} else {
+		goto miss;
+	}
+
+hit:
+	pthread_rwlock_unlock(&c->lock);
+	return true;
+
+miss:
+	pthread_rwlock_unlock(&c->lock);
+	return false;
+}
+
+
+bool cache_set(struct cache *c, const char *key, void *value)
+{
+	pthread_rwlock_wrlock(&c->lock);
+	struct entry *e = entry_for_key(c, key);
+
+	if (e->in_use == IN_USE)
+		free(e->key);
+
+	e->in_use = IN_USE;
+
+	e->key = strdup(key);
+	e->value = value;
+
+	pthread_rwlock_unlock(&c->lock);
+	return true;
+}
+
+bool cache_del(struct cache *c, const char *key)
+{
+	pthread_rwlock_wrlock(&c->lock);
+	struct entry *e = entry_for_key(c, key);
+
+	if (e->in_use == IN_USE && strcmp(e->key, key) == 0) {
+		free(e->key);
+		e->key = NULL;
+		e->value = NULL;
+		e->in_use = REMOVED;
+		pthread_rwlock_unlock(&c->lock);
+		return true;
+	}
+
+	pthread_rwlock_unlock(&c->lock);
+	return false;
+}
+
diff --git a/libfiu/hash.h b/libfiu/hash.h
index 194105c..edd5f6d 100644
--- a/libfiu/hash.h
+++ b/libfiu/hash.h
@@ -16,5 +16,19 @@ void *hash_get(hash_t *h, const char *key);
 bool hash_set(hash_t *h, const char *key, void *value);
 bool hash_del(hash_t *h, const char *key);
 
+
+/* Generic cache. */
+
+typedef struct cache cache_t;
+
+cache_t *cache_create();
+bool cache_resize(struct cache *c, size_t new_size);
+void cache_free(cache_t *c);
+
+bool cache_get(cache_t *c, const char *key, void **value);
+bool cache_set(cache_t *c, const char *key, void *value);
+bool cache_del(cache_t *c, const char *key);
+bool cache_invalidate(cache_t *c);
+
 #endif
 
diff --git a/libfiu/wtable.c b/libfiu/wtable.c
index 2cce744..bf77878 100644
--- a/libfiu/wtable.c
+++ b/libfiu/wtable.c
@@ -45,6 +45,9 @@ struct wtable {
 	size_t ws_size;
 	size_t ws_used_count;
 
+	/* And we keep a cache of lookups into the wildcards array. */
+	cache_t *wcache;
+
 	void (*destructor)(void *);
 };
 
@@ -60,6 +63,7 @@ struct wtable *wtable_create(void (*destructor)(void *))
 		return NULL;
 
 	t->wildcards = NULL;
+	t->wcache = NULL;
 
 	t->finals = hash_create(destructor);
 	if (t->finals == NULL)
@@ -71,6 +75,10 @@ struct wtable *wtable_create(void (*destructor)(void *))
 
 	memset(t->wildcards, 0, sizeof(struct wentry) * MIN_SIZE);
 
+	t->wcache = cache_create();
+	if (t->wcache == NULL)
+		goto error;
+
 	t->ws_size = MIN_SIZE;
 	t->ws_used_count = 0;
 	t->destructor = destructor;
@@ -80,6 +88,8 @@ struct wtable *wtable_create(void (*destructor)(void *))
 error:
 	if (t->finals)
 		hash_free(t->finals);
+	if (t->wcache)
+		cache_free(t->wcache);
 	free(t->wildcards);
 	free(t);
 	return NULL;
@@ -91,6 +101,7 @@ void wtable_free(struct wtable *t)
 	struct wentry *entry;
 
 	hash_free(t->finals);
+	cache_free(t->wcache);
 
 	for (i = 0; i < t->ws_size; i++) {
 		entry = t->wildcards + i;
@@ -198,10 +209,19 @@ void *wtable_get(struct wtable *t, const char *key)
 	if (value)
 		return value;
 
-	/* And then a wildcards one. */
+	/* Then see if we can find it in the wcache */
+	if (cache_get(t->wcache, key, &value))
+		return value;
+
+	/* And then walk the wildcards array. */
 	entry = wildcards_find_entry(t, key, false, NULL);
-	if (entry)
+	if (entry) {
+		cache_set(t->wcache, key, entry->value);
 		return entry->value;
+	}
+
+	/* Cache the negative result as well. */
+	cache_set(t->wcache, key, NULL);
 
 	return NULL;
 }
@@ -271,6 +291,10 @@ static bool resize_table(struct wtable *t, size_t new_size)
 
 	free(old_wildcards);
 
+	/* Keep the cache the same size as our table, which works reasonably
+	 * well in practise */
+	cache_resize(t->wcache, new_size);
+
 	return true;
 }
 
@@ -321,6 +345,11 @@ bool wtable_del(struct wtable *t, const char *key)
 				return false;
 		}
 
+		/* Invalidate the cache. We could be smart and walk it,
+		 * removing only the positive hits, but it's also more
+		 * expensive */
+		cache_invalidate(t->wcache);
+
 		return true;
 	} else {
 		return hash_del(t->finals, key);