X-Git-Url: http://v3vee.org/palacios/gitweb/gitweb.cgi?a=blobdiff_plain;f=kitten%2Fkernel%2Fhtable.c;fp=kitten%2Fkernel%2Fhtable.c;h=782006078d88cfbe701e098320127f30b747d5c1;hb=66a1a4c7a9edcd7d8bc207aca093d694a6e6b5b2;hp=0000000000000000000000000000000000000000;hpb=f7cf9c19ecb0a589dd45ae0d2c91814bd3c2acc2;p=palacios.git

diff --git a/kitten/kernel/htable.c b/kitten/kernel/htable.c
new file mode 100644
index 0000000..7820060
--- /dev/null
+++ b/kitten/kernel/htable.c
@@ -0,0 +1,121 @@
+/* Copyright (c) 2008, Sandia National Laboratories */
+
+#include <lwk/kernel.h>
+#include <lwk/list.h>
+#include <lwk/htable.h>
+#include <lwk/hash.h>
+
+struct htable {
+	size_t              tbl_order;
+	struct hlist_head * tbl;
+	size_t              obj_key_offset;
+	size_t              obj_link_offset;
+	size_t              num_entries;
+};
+
+static id_t
+obj2key(const struct htable *ht, const void *obj)
+{
+	return *((id_t *)((uintptr_t)obj + ht->obj_key_offset));
+}
+
+static struct hlist_node *
+obj2node(const struct htable *ht, const void *obj)
+{
+	return (struct hlist_node *)((uintptr_t)obj + ht->obj_link_offset);
+}
+
+static void *
+node2obj(const struct htable *ht, const struct hlist_node *node)
+{
+	return (void *)((uintptr_t)node - ht->obj_link_offset);
+}
+
+static id_t
+node2key(const struct htable *ht, const struct hlist_node *node)
+{
+	return obj2key(ht, node2obj(ht, node));
+}
+
+static struct hlist_head *
+key2head(const struct htable *ht, id_t key)
+{
+	return &ht->tbl[hash_long(key, ht->tbl_order)];
+}
+
+static struct hlist_head *
+obj2head(const struct htable *ht, const void *obj)
+{
+	return &ht->tbl[hash_long(obj2key(ht, obj), ht->tbl_order)];
+}
+
+int
+htable_create(size_t tbl_order,
+              size_t obj_key_offset, size_t obj_link_offset, htable_t *tbl)
+{
+	struct htable *ht;
+	size_t tbl_size;
+
+	if (!(ht = kmem_alloc(sizeof(*ht))))
+		return -ENOMEM;
+
+	ht->tbl_order = tbl_order;
+	tbl_size = (1 << tbl_order);
+
+	if (!(ht->tbl = kmem_alloc(tbl_size * sizeof(struct hlist_head))))
+		return -ENOMEM;
+
+	ht->obj_key_offset  = obj_key_offset;
+	ht->obj_link_offset = obj_link_offset;
+	ht->num_entries     = 0;
+
+	*tbl = ht;
+	return 0;
+}
+
+int
+htable_destroy(htable_t tbl)
+{
+	struct htable *ht = tbl;
+	if (ht->num_entries)
+		return -EEXIST;
+	kmem_free(ht->tbl);
+	kmem_free(ht);
+	return 0;
+}
+
+int
+htable_add(htable_t tbl, void *obj)
+{
+	struct htable *ht = tbl;
+	hlist_add_head(obj2node(ht, obj), obj2head(ht, obj));
+	++ht->num_entries;
+	return 0;
+}
+
+int
+htable_del(htable_t tbl, void *obj)
+{
+	struct htable *ht = tbl;
+	struct hlist_node *node;
+	hlist_for_each(node, obj2head(ht, obj)) {
+		if (obj == node2obj(ht, node)) {
+			hlist_del(node);
+			--ht->num_entries;
+			return 0;
+		}
+	}
+	return -ENOENT;
+}
+
+void *
+htable_lookup(htable_t tbl, id_t key)
+{
+	struct htable *ht = tbl;
+	struct hlist_node *node;
+	hlist_for_each(node, key2head(ht, key)) {
+		if (key == node2key(ht, node))
+			return node2obj(ht, node);
+	}
+	return NULL;
+}