voron

commit a4278f3bfd32165c8bbd453a6a3930f92165bbfa
parent d573437808d978dea443e72ec1b3ddc62475910d
Author: sin <sin@2f30.org>
Date:   Fri, 26 Jul 2013 15:32:59 +0100

Simplify hash table implementation

Forget about the open-addressing based implementation.
Now we've got a hash table with a fixed number of buckets.

In this implementation we allow duplicates.

We still need to constify some of the parameters.

Diffstat:
M
include/hash.h
 | 
16
++++++++--------
M
kernel/hash.c
 | 
205
++++++++++++++++++++++++++++++++++++++-----------------------------------------

2 files changed, 106 insertions(+), 115 deletions(-)
diff --git a/include/hash.h b/include/hash.h
@@ -3,15 +3,15 @@
 
 #include <inttypes.h>
 
-struct hent_ops {
-	unsigned long (*hash)(void *data, size_t siz);
-	int (*cmp)(void *src, void *dst, size_t siz);
+struct hops {
+        long (*hash)(void *data, size_t siz);
+        int (*cmp)(void *src, void *dst, size_t siz);
 };
 
-struct htable *init_htable(struct hent_ops *hent_ops, size_t n);
-void free_htable(struct htable *htable);
-int search_htable(struct htable *htable, void *data, size_t siz);
-int insert_htable(struct htable *htable, void *data, size_t siz);
-int remove_htable(struct htable *htable, void *data, size_t siz);
+struct htable *init_htable(struct hops *ops, size_t siz);
+void free_htable(struct htable *ht);
+long search_htable(struct htable *ht, void *data, size_t siz);
+long insert_htable(struct htable *ht, void *data, size_t siz);
+long remove_htable(struct htable *ht, void *data, size_t siz);
 
 #endif /* __HASH_H */
diff --git a/kernel/hash.c b/kernel/hash.c
@@ -1,148 +1,139 @@
-/* Simple hash table implementation using open-addressing */
 #include <kernel.h>
-#include <mmu.h>
 #include <alloc.h>
 #include <spinlock.h>
 #include <hash.h>
 
-enum hent_state {
-	UNUSED,
-	USED,
-	REMOVED,
-};
+enum { CHAIN_SIZ = 32 };
 
-struct hent {
-	void *data;
-	size_t siz;
-	enum hent_state state;
+struct hentry {
+	struct {
+		void *data;
+		size_t siz;
+	} c[CHAIN_SIZ];
 };
 
 struct htable {
-	struct hent *hent;
-	struct hent_ops *hent_ops;
+	struct hentry *e;
+	struct hops *ops;
 	size_t siz;
 	spinlock_t lock;
 };
 
 struct htable *
-init_htable(struct hent_ops *hent_ops, size_t n)
+init_htable(struct hops *ops, size_t siz)
 {
-	struct htable *htable;
-	size_t i;
+	struct htable *ht;
+	size_t i, j;
+
+	if (!ops || !ops->hash || !ops->cmp || !siz)
+		return NULL;
 
-	htable = kmalloc(sizeof(*htable));
-	if (!htable)
+	ht = kmalloc(sizeof(*ht));
+	if (!ht)
 		return NULL;
-	htable->hent = kcalloc(n, sizeof(struct hent));
-	if (!htable->hent) {
-		kfree(htable);
+	ht->e = kmalloc(siz * sizeof(*ht->e));
+	if (!ht->e) {
+		kfree(ht);
 		return NULL;
 	}
-	for (i = 0; i < n; i++)
-		htable->hent[i].state = UNUSED;
-	htable->siz = n;
-	htable->hent_ops = hent_ops;
-	spinlock_init(&htable->lock);
-	return htable;
+	for (i = 0; i < siz; i++) {
+		for (j = 0; j < CHAIN_SIZ; j++) {
+			ht->e[i].c[j].data = NULL;
+			ht->e[i].c[j].siz = 0;
+		}
+	}
+	ht->siz = siz;
+	ht->ops = ops;
+	spinlock_init(&ht->lock);
+	return ht;
 }
 
 void
-free_htable(struct htable *htable)
+kfree_htable(struct htable *ht)
 {
-	kfree(htable->hent);
-	kfree(htable);
+	kfree(ht->e);
+	kfree(ht);
 }
 
-/* Search the hash table for the given entry.  Returns -1
- * on failure and the index of the entry on success. */
-int
-search_htable(struct htable *htable, void *data, size_t siz)
+long
+search_htable(struct htable *ht, void *data, size_t siz)
 {
-	struct hent *hent;
-	struct hent_ops *ops;
-	size_t idx, i, j;
-
-	spinlock_lock(&htable->lock);
-	ops = htable->hent_ops;
-	idx = ops->hash(data, siz) % htable->siz;
-	j = idx;
-	for (i = 0; i < htable->siz; i++) {
-		hent = &htable->hent[j];
-		if (hent->state == UNUSED) {
-			spinlock_unlock(&htable->lock);
-			return -1;
-		}
-		if (hent->state == USED && !ops->cmp(hent->data, data, siz)) {
-			spinlock_unlock(&htable->lock);
-			return j;
+	struct hentry *e;
+	struct hops *ops;
+	long i;
+	size_t j;
+
+	if (!ht || !data || !siz)
+		return -1;
+
+	spinlock_lock(&ht->lock);
+	ops = ht->ops;
+	i = ops->hash(data, siz) % ht->siz;
+	e = &ht->e[i];
+	for (j = 0; j < CHAIN_SIZ; j++) {
+		if (!e->c[j].data || e->c[j].siz != siz)
+			continue;
+		if (!ops->cmp(e->c[j].data, data, siz)) {
+			spinlock_unlock(&ht->lock);
+			return i;
 		}
-		j++;
-		j %= htable->siz;
 	}
-	spinlock_unlock(&htable->lock);
+	spinlock_unlock(&ht->lock);
 	return -1;
 }
 
-/* Insert the given entry in the hash table.  Ignore duplicates.
- * Return the index on a successful insertion, -1 if the table is full. */
-int
-insert_htable(struct htable *htable, void *data, size_t siz)
+long
+insert_htable(struct htable *ht, void *data, size_t siz)
 {
-	struct hent *hent;
-	struct hent_ops *ops;
-	size_t idx, i, j;
-
-	spinlock_lock(&htable->lock);
-	ops = htable->hent_ops;
-	idx = ops->hash(data, siz) % htable->siz;
-	j = idx;
-	for (i = 0; i < htable->siz; i++) {
-		hent = &htable->hent[j];
-		if (hent->state == USED && !ops->cmp(hent->data, data, siz)) {
-			spinlock_unlock(&htable->lock);
-			return j;
-		}
-		if (hent->state == UNUSED || hent->state == REMOVED) {
-			hent->data = data;
-			hent->siz = siz;
-			hent->state = USED;
-			spinlock_unlock(&htable->lock);
-			return j;
-		}
-		j++;
-		j %= htable->siz;
+	struct hentry *e;
+	struct hops *ops;
+	long i;
+	size_t j;
+
+	if (!ht || !data || !siz)
+		return -1;
+
+	spinlock_lock(&ht->lock);
+	ops = ht->ops;
+	i = ops->hash(data, siz) % ht->siz;
+	e = &ht->e[i];
+	for (j = 0; j < CHAIN_SIZ; j++) {
+		if (e->c[j].data)
+			continue;
+		e->c[j].data = data;
+		e->c[j].siz = siz;
+		spinlock_unlock(&ht->lock);
+		return i;
 	}
-	spinlock_unlock(&htable->lock);
+	spinlock_unlock(&ht->lock);
 	return -1;
 }
 
-/* Remove an entry from the hash table.  Return -1 on failure,
- * and the index of the entry on success. */
-int
-remove_htable(struct htable *htable, void *data, size_t siz)
+long
+remove_htable(struct htable *ht, void *data, size_t siz)
 {
-	struct hent *hent;
-	struct hent_ops *ops;
-	size_t idx, i, j;
-
-	spinlock_lock(&htable->lock);
-	ops = htable->hent_ops;
-	idx = ops->hash(data, siz) % htable->siz;
-	j = idx;
-	for (i = 0; i < htable->siz; i++) {
-		hent = &htable->hent[j];
-		if (hent->state == UNUSED) {
-			spinlock_unlock(&htable->lock);
-			return -1;
-		}
-		if (hent->state == USED && !ops->cmp(hent->data, data, siz)) {
-			hent->state = REMOVED;
-			spinlock_unlock(&htable->lock);
-			return j;
+	struct hentry *e;
+	struct hops *ops;
+	long i;
+	size_t j;
+
+	if (!ht || !data || !siz)
+		return -1;
+
+	spinlock_lock(&ht->lock);
+	ops = ht->ops;
+	i = ops->hash(data, siz) % ht->siz;
+	e = &ht->e[i];
+	for (j = 0; j < CHAIN_SIZ; j++) {
+		if (!e->c[j].data || e->c[j].siz != siz)
+			continue;
+		if (!ops->cmp(e->c[j].data, data, siz)) {
+			e->c[j].data = NULL;
+			e->c[j].siz = 0;
+			spinlock_unlock(&ht->lock);
+			return i;
 		}
-		j++;
-		j %= htable->siz;
 	}
-	spinlock_unlock(&htable->lock);
+	spinlock_unlock(&ht->lock);
 	return -1;
 }