voron

commit 9a9e3101e592116cf8b3d758cdefe4da583f9624
parent f75befe40ebae02606b7fce1e74adc9d1b8c5fda
Author: sin <sin@2f30.org>
Date:   Sun, 21 Jul 2013 14:01:52 +0100

Add simple hash table implementation using open-addressing

Diffstat:
A
include/hash.h
 | 
15
+++++++++++++++
A
kernel/hash.c
 | 
150
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 165 insertions(+), 0 deletions(-)
diff --git a/include/hash.h b/include/hash.h
@@ -0,0 +1,15 @@
+#ifndef __HASH_H
+#define __HASH_H
+
+struct hent_ops {
+	unsigned 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);
+
+#endif
diff --git a/kernel/hash.c b/kernel/hash.c
@@ -0,0 +1,150 @@
+/* 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,
+};
+
+struct hent {
+	void *data;
+	size_t siz;
+	enum hent_state state;
+};
+
+struct htable {
+	struct hent *hent;
+	struct hent_ops *hent_ops;
+	size_t siz;
+};
+
+static spinlock_t htable_lock = SPINLOCK_INIT;
+
+struct htable *
+init_htable(struct hent_ops *hent_ops, size_t n)
+{
+	struct htable *htable;
+	size_t i;
+
+	htable = kmalloc(sizeof(*htable));
+	if (!htable)
+		return NULL;
+	htable->hent = kcalloc(n, sizeof(struct hent));
+	if (!htable->hent) {
+		kfree(htable);
+		return NULL;
+	}
+	for (i = 0; i < n; i++)
+		htable->hent[i].state = UNUSED;
+	htable->siz = n;
+	htable->hent_ops = hent_ops;
+	return htable;
+}
+
+void
+free_htable(struct htable *htable)
+{
+	spinlock_lock(&htable_lock);
+	kfree(htable->hent);
+	kfree(htable);
+	spinlock_unlock(&htable_lock);
+}
+
+/* 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)
+{
+	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;
+		}
+		j++;
+		j %= htable->siz;
+	}
+	spinlock_unlock(&htable_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)
+{
+	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;
+	}
+	spinlock_unlock(&htable_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)
+{
+	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;
+		}
+		j++;
+		j %= htable->siz;
+	}
+	spinlock_unlock(&htable_lock);
+	return -1;
+}