X-Git-Url: https://code.grnet.gr/git/archipelago/blobdiff_plain/8a1b5a0d4f1b3f157832a2d6d19f1bcc027f5af9..5653127514470efad4407fd8545002d6c283f3c6:/xseg/xtypes/xhash.c?ds=sidebyside

diff --git a/xseg/xtypes/xhash.c b/xseg/xtypes/xhash.c
index c7a2a08..f174a1e 100644
--- a/xseg/xtypes/xhash.c
+++ b/xseg/xtypes/xhash.c
@@ -14,6 +14,64 @@
 
 #define PERTURB_SHIFT 5
 
+static inline xhashidx hash_int(xhashidx key)
+{
+	return key;
+}
+
+static inline int cmp_int(xhashidx key1, xhashidx key2)
+{
+	return (key1 == key2);
+}
+
+static inline xhashidx hash_string(xhashidx key) 
+{
+	//assume a valid NULL terminated string
+	
+	//function to access key if in container
+	char *string = (char *) key;
+	unsigned int i, len = strlen(string);
+	xhashidx hv = string[0] << 7;
+	for (i = 1; i <= len; i++) {
+		hv = (hv * 1000003) ^ string[i];
+	}
+	if (hv == Noxhashidx)
+		hv = Noxhashidx -1;
+
+//	XSEGLOG("String %s (%lx). Hash value: %llu",
+//			string, string, hv);
+	return hv; 
+}
+
+static inline int cmp_string(xhashidx key1, xhashidx key2)
+{
+	char *string1 = (char *) key1;
+	char *string2 = (char *) key2;
+	int value = !strcmp(string1, string2);
+//	XSEGLOG("String1 %s (%lx), string2: %s(%lx), r: %d",
+//			string1, (unsigned long) string1,
+//			string2, (unsigned long) string2,
+//			value);
+
+	return (value);
+}
+
+typedef int (*xhash_cmp_fun_t)(xhashidx key1, xhashidx key2);
+typedef xhashidx (*xhash_hash_fun_t)(xhashidx key);
+
+struct types_functions {
+//	int (*cmp_fun)(xhashidx key1, xhashidx key2);
+//	xhashidx (*hash_fun)(xhashidx key);
+	xhash_cmp_fun_t cmp_fun;
+	xhash_hash_fun_t hash_fun;
+};
+
+static struct types_functions types_fun[] = {
+	{ .cmp_fun = cmp_int, .hash_fun = hash_int },
+	{ .cmp_fun = cmp_string, .hash_fun = hash_string }
+};
+
+
 static inline void
 set_dummy_key(xhash_t *xhash, xhashidx idx)
 {
@@ -202,9 +260,10 @@ xhash_resize__(struct xhash *xhash, xhashidx new_size_shift, bool vals)
 int
 xhash_delete__(xhash_t *xhash, xhashidx key, bool vals)
 {
+//    XSEGLOG("Deleting %lx", key);
     xhash_cmp_fun_t cmp_fun = types_fun[xhash->type].cmp_fun;
     xhash_hash_fun_t hash_fun = types_fun[xhash->type].hash_fun; 
-    xhashidx perturb = key;
+    xhashidx perturb = hash_fun(key);
     xhashidx mask = xhash_size(xhash)-1;
     xhashidx idx = hash_fun(key) & mask;
     xhashidx *kvs = xhash_kvs(xhash);
@@ -334,7 +393,7 @@ xhash_grow_check(xhash_t *xhash)
     xhash_cmp_fun_t cmp_fun = types_fun[xhash->type].cmp_fun;         \
     xhash_hash_fun_t hash_fun = types_fun[xhash->type].hash_fun;       \
     xhashidx size = 1UL<<(xhash->size_shift);         \
-    xhashidx perturb = key;                           \
+    xhashidx perturb = hash_fun(key);                           \
     xhashidx mask = size-1;                           \
     xhashidx idx = hash_fun(key) & mask;              \
     xhashidx *kvs = xhash_kvs(xhash);                 \
@@ -364,6 +423,7 @@ set_val(xhash_t *p, xhashidx idx, xhashidx key, xhashidx val)
     xhashidx *vals = xhash_vals(p);
     kvs[idx] = key;
     vals[idx] = val;
+    //XSEGLOG("Seting idx %llu to key: %lx, val: %lx", idx, key, val);
 }
 
 void static inline xhash_upd_set(xhash_t *p, xhashidx idx, xhashidx key, xhashidx val)
@@ -375,6 +435,7 @@ void static inline xhash_upd_set(xhash_t *p, xhashidx idx, xhashidx key, xhashid
     p->used++;
     kvs[idx] = key;
     vals[idx] = val;
+    //XSEGLOG("Seting idx %llu to key: %lx, val: %lx", idx, key, val);
 }
 
 static inline void
@@ -386,6 +447,7 @@ inc_val(xhash_t *p, xhashidx idx, xhashidx val)
 
 void xhash_insert__(struct xhash *xhash, xhashidx key, xhashidx val)
 {
+    //XSEGLOG("inserting %lx", key);
     //fprintf(stderr, "insert: (%lu,%lu)\n", key, val);
     #define PHUPD_UPDATE__(_p, _i, _k, _v) set_val(_p, _i, _k, _v)
     #define PHUPD_SET__(_p, _i, _k, _v)    xhash_upd_set(_p, _i, _k, _v)
@@ -423,6 +485,7 @@ int xhash_freql_update(struct xhash *xhash, xhashidx key, xhashidx val)
 xhash_t *
 xhash_resize(xhash_t *xhash, xhashidx new_size_shift, xhash_t *new)
 {
+    //XSEGLOG("Resizing xhash from %llu to %llu", xhash->size_shift, new_size_shift);
     xhashidx i;
     int f = !!new;
     if (!f)
@@ -472,17 +535,20 @@ int xhash_delete(struct xhash *xhash, xhashidx key)
 
 int xhash_lookup__(xhash_t *xhash, xhashidx key, xhashidx *idx_ret, bool vals)
 {
+    //XSEGLOG("looking up %lx", key);
     xhash_cmp_fun_t cmp_fun = types_fun[xhash->type].cmp_fun;
     xhash_hash_fun_t hash_fun = types_fun[xhash->type].hash_fun; 
     xhashidx size_shift = xhash->size_shift;
-    xhashidx size = (xhashidx)1<<size_shift;
-    xhashidx perturb = key;
+    xhashidx size = (1UL)<<size_shift;
+    xhashidx perturb = hash_fun(key);
     xhashidx mask = size-1;
     xhashidx idx = hash_fun(key) & mask;
     xhashidx *kvs = xhash_kvs(xhash);
 
     INCSTAT(xhash->lookups);
     for (;;) {
+	//XSEGLOG("size %llu, perturb %llu idx %llu mask %llu",
+	//	    size, perturb, idx, mask);		
         if ( item_unused(xhash, idx, vals) )
             return -XHASH_EEXIST;
 
@@ -867,4 +933,10 @@ int main(int argc, char **argv)
 #endif
 
 #endif //if 0
+
+#ifdef __KERNEL__
+#include <linux/module.h>
+#include <xtypes/xhash_exports.h>
+#endif
+
 // vim:expandtab:tabstop=8:shiftwidth=4:softtabstop=4