X-Git-Url: https://code.grnet.gr/git/archipelago/blobdiff_plain/164d158628a64c98b49f4b699a5b8740ef30f4ce..5653127514470efad4407fd8545002d6c283f3c6:/xseg/xtypes/xhash.c

diff --git a/xseg/xtypes/xhash.c b/xseg/xtypes/xhash.c
index 9e444bc..f174a1e 100644
--- a/xseg/xtypes/xhash.c
+++ b/xseg/xtypes/xhash.c
@@ -1,9 +1,3 @@
-//#include <stdio.h>
-//#include <stdlib.h>
-#include <assert.h>
-//#include <unistd.h>
-//#include <stdbool.h>
-
 /* python hash for C
  *  originally by gtsouk@cslab.ece.ntua.gr
  *  -- kkourt@cslab.ece.ntua.gr
@@ -11,8 +5,8 @@
 
 #include <xtypes/xhash.h>
 
-#define UNUSED (~(ul_t)0)      /* this entry was never used */
-#define DUMMY  ((~(ul_t)0)-1)  /* this entry was used, but now its empty */
+#define UNUSED (~(xhashidx)0)      /* this entry was never used */
+#define DUMMY  ((~(xhashidx)0)-1)  /* this entry was used, but now its empty */
 
 //#define VAL_OVERLOAD
 //#define KEY_OVERLOAD
@@ -20,32 +14,90 @@
 
 #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, ul_t idx)
+set_dummy_key(xhash_t *xhash, xhashidx idx)
 {
-    ul_t *kvs = xhash_kvs(xhash);
+    xhashidx *kvs = xhash_kvs(xhash);
     kvs[idx] = DUMMY;
 }
 
 static inline void
-set_dummy_val(xhash_t *xhash, ul_t idx)
+set_dummy_val(xhash_t *xhash, xhashidx idx)
 {
-    ul_t *vals = xhash_vals(xhash);
+    xhashidx *vals = xhash_vals(xhash);
     vals[idx] = DUMMY;
 }
 
 static bool
-item_dummy(xhash_t *xhash, ul_t idx, bool vals)
+item_dummy(xhash_t *xhash, xhashidx idx, bool vals)
 {
     bool ret;
-    ul_t *kvs = xhash_kvs(xhash);
+    xhashidx *pvals;
+    xhashidx *kvs = xhash_kvs(xhash);
 
     if (!vals) {
         ret = (kvs[idx] == DUMMY);
     } else {
         #if defined(VAL_OVERLOAD)
-        assert(vals);
-        ul_t *pvals = xhash_vals(xhash);
+        pvals = xhash_vals(xhash);
         ret = (pvals[idx] == DUMMY);
         #elif defined(KEY_OVERLOAD)
         ret = (kvs[idx] == DUMMY);
@@ -55,7 +107,7 @@ item_dummy(xhash_t *xhash, ul_t idx, bool vals)
 
 }
 
-static void set_dummy_item(xhash_t *xhash, ul_t idx, bool vals)
+static void set_dummy_item(xhash_t *xhash, xhashidx idx, bool vals)
 {
     if (!vals) {
         set_dummy_key(xhash, idx);
@@ -63,7 +115,6 @@ static void set_dummy_item(xhash_t *xhash, ul_t idx, bool vals)
     }
 
     #ifdef VAL_OVERLOAD
-    assert(vals);
     set_dummy_val(xhash, idx);
     return;
     #elif defined(KEY_OVERLOAD)
@@ -72,36 +123,35 @@ static void set_dummy_item(xhash_t *xhash, ul_t idx, bool vals)
     #endif
 }
 static inline void
-set_unused_key(xhash_t *xhash, ul_t idx)
+set_unused_key(xhash_t *xhash, xhashidx idx)
 {
-    ul_t *kvs = xhash_kvs(xhash);
+    xhashidx *kvs = xhash_kvs(xhash);
     kvs[idx] = UNUSED;
 }
 
 static inline void
-set_unused_val(xhash_t *xhash, ul_t idx)
+set_unused_val(xhash_t *xhash, xhashidx idx)
 {
-    ul_t *vals = xhash_vals(xhash);
+    xhashidx *vals = xhash_vals(xhash);
     vals[idx] = UNUSED;
 }
 
 static inline bool
-val_unused(xhash_t *xhash, ul_t idx)
+val_unused(xhash_t *xhash, xhashidx idx)
 {
-    ul_t *vals = xhash_vals(xhash);
+    xhashidx *vals = xhash_vals(xhash);
     return vals[idx] == UNUSED;
 }
 
 static bool
-item_unused(xhash_t *xhash, ul_t idx, bool vals)
+item_unused(xhash_t *xhash, xhashidx idx, bool vals)
 {
-    ul_t *kvs = xhash_kvs(xhash);
+    xhashidx *kvs = xhash_kvs(xhash);
     if (!vals) {
         return kvs[idx] == UNUSED;
     }
 
     #if defined(VAL_OVERLOAD)
-    assert(vals);
     return val_unused(xhash, idx);
     #elif defined(KEY_OVERLOAD)
     return kvs[idx] == UNUSED;
@@ -109,25 +159,25 @@ item_unused(xhash_t *xhash, ul_t idx, bool vals)
 
 }
 
-static inline unsigned item_valid(xhash_t *xhash, ul_t idx, bool vals)
+static inline unsigned item_valid(xhash_t *xhash, xhashidx idx, bool vals)
 {
     return !(item_dummy(xhash, idx, vals) || item_unused(xhash, idx, vals));
 }
-
+/*
 static void __attribute__((unused))
-assert_key(ul_t key)
+assert_key(xhashidx key)
 {
     assert((key != UNUSED) && (key != DUMMY));
 }
 
 static void
-assert_val(ul_t val)
+assert_val(xhashidx val)
 {
     assert((val != UNUSED) && (val != DUMMY));
 }
 
 static inline void
-assert_kv(ul_t k, ul_t v)
+assert_kv(xhashidx k, xhashidx v)
 {
     #if defined(KEY_OVERLOAD)
     assert_key(k);
@@ -135,13 +185,15 @@ assert_kv(ul_t k, ul_t v)
     assert_val(v);
     #endif
 }
+*/
 
 void
-xhash_init__(xhash_t *xhash, ul_t size_shift, ul_t minsize_shift, bool vals)
+xhash_init__(xhash_t *xhash, xhashidx size_shift, xhashidx minsize_shift, 
+		enum xhash_type type, bool vals)
 {
-    ul_t nr_items = 1UL << size_shift;
-    ul_t *kvs = (ul_t *) ((char *) xhash + sizeof(struct xhash));
-    ul_t i;
+    xhashidx nr_items = 1UL << size_shift;
+    xhashidx *kvs = (xhashidx *) ((char *) xhash + sizeof(struct xhash));
+    xhashidx i;
 
     XPTRSET(&xhash->kvs, kvs);
 
@@ -154,7 +206,6 @@ xhash_init__(xhash_t *xhash, ul_t size_shift, ul_t minsize_shift, bool vals)
 
     for (i=0; i < nr_items; i++){
         #if defined(VAL_OVERLOAD)
-        assert(vals);
         kvs[nr_items + i] = UNUSED;
         #elif  defined(KEY_OVERLOAD)
         kvs[i] = UNUSED;
@@ -165,6 +216,7 @@ out:
     xhash->dummies = xhash->used = 0;
     xhash->size_shift = size_shift;
     xhash->minsize_shift = minsize_shift;
+    xhash->type = type;
 
     ZEROSTAT(xhash->inserts);
     ZEROSTAT(xhash->deletes);
@@ -173,51 +225,55 @@ out:
 }
 
 static ssize_t
-get_alloc_size(ul_t size_shift, bool vals)
+get_alloc_size(xhashidx size_shift, bool vals)
 {
-    ul_t nr_items = 1UL << size_shift;
-    size_t keys_size = nr_items*sizeof(ul_t);
-    size_t alloc_size = vals ? keys_size<<2 : keys_size;
+    xhashidx nr_items = 1UL << size_shift;
+    size_t keys_size = nr_items*sizeof(xhashidx);
+    size_t alloc_size = vals ? keys_size<<1 : keys_size;
     return sizeof(struct xhash) + alloc_size;
 }
 
 
 xhash_t *
-xhash_new__(ul_t size_shift, ul_t minsize_shift, bool vals) {
+xhash_new__(xhashidx size_shift, xhashidx minsize_shift, 
+		enum xhash_type type, bool vals) 
+{
     struct xhash *xhash;
     xhash = xtypes_malloc(get_alloc_size(size_shift, vals));
     if (!xhash) {
-        perror("malloc");
-        exit(1);
+	XSEGLOG("couldn't malloc\n");
+	return NULL;
     }
 
-    xhash_init__(xhash, size_shift, minsize_shift, vals);
+    xhash_init__(xhash, size_shift, minsize_shift, type, vals);
     
     return xhash;
 }
 
 
 xhash_t *
-xhash_resize__(struct xhash *xhash, ul_t new_size_shift, bool vals)
+xhash_resize__(struct xhash *xhash, xhashidx new_size_shift, bool vals)
 {
-    return xhash_new__(new_size_shift, xhash->minsize_shift, vals);
+    return xhash_new__(new_size_shift, xhash->minsize_shift, xhash->type, vals);
 }
 
 int
-xhash_delete__(xhash_t *xhash, ul_t key, bool vals)
+xhash_delete__(xhash_t *xhash, xhashidx key, bool vals)
 {
-    ul_t perturb = key;
-    ul_t mask = xhash_size(xhash)-1;
-    ul_t idx = key & mask;
-    ul_t *kvs = xhash_kvs(xhash);
+//    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 = hash_fun(key);
+    xhashidx mask = xhash_size(xhash)-1;
+    xhashidx idx = hash_fun(key) & mask;
+    xhashidx *kvs = xhash_kvs(xhash);
 
     for (;;) {
         if ( item_unused(xhash, idx, vals) ){
-            assert(0);
             return -2;
         }
 
-        if ( !item_dummy(xhash, idx, vals) && kvs[idx] == key){
+        if ( !item_dummy(xhash, idx, vals) && cmp_fun(kvs[idx],key)){
             INCSTAT(xhash->deletes);
             set_dummy_item(xhash, idx, vals);
             xhash->dummies++;
@@ -232,15 +288,16 @@ xhash_delete__(xhash_t *xhash, ul_t key, bool vals)
     }
 }
 
-ul_t
-grow_size_shift(xhash_t *xhash)
+xhashidx
+xhash_grow_size_shift(xhash_t *xhash)
 {
-    ul_t old_size_shift = xhash->size_shift;
-    ul_t new_size_shift;
-    ul_t u;
+    xhashidx old_size_shift = xhash->size_shift;
+    xhashidx new_size_shift;
+    xhashidx u;
 
     u = xhash->used;
-    if (u/2 + u >= ((ul_t)1 << old_size_shift)) {
+    //printf("used: %lu\n", u);
+    if (u/2 + u >= ((xhashidx)1 << old_size_shift)) {
         new_size_shift = old_size_shift + 1;
     } else {
         new_size_shift = old_size_shift;
@@ -249,11 +306,11 @@ grow_size_shift(xhash_t *xhash)
     return new_size_shift;
 }
 
-ul_t
-shrink_size_shift(xhash_t *xhash)
+xhashidx
+xhash_shrink_size_shift(xhash_t *xhash)
 {
-    ul_t old_size_shift = xhash->size_shift;
-    ul_t new_size_shift;
+    xhashidx old_size_shift = xhash->size_shift;
+    xhashidx new_size_shift;
     new_size_shift = old_size_shift - 1;
     if (new_size_shift < xhash->minsize_shift) {
         new_size_shift = xhash->minsize_shift;
@@ -264,19 +321,19 @@ shrink_size_shift(xhash_t *xhash)
 static bool
 grow_check(xhash_t *xhash)
 {
-    ul_t size_shift = xhash->size_shift;
-    ul_t u = xhash->used + xhash->dummies;
-    ul_t size = (ul_t)1UL<<size_shift;
+    xhashidx size_shift = xhash->size_shift;
+    xhashidx u = xhash->used + xhash->dummies;
+    xhashidx size = (xhashidx)1UL<<size_shift;
     return ((u/2 + u) >= size) ? true : false;
 }
 
 static bool
 shrink_check(xhash_t *xhash)
 {
-    ul_t size_shift = xhash->size_shift;
-    ul_t size = (ul_t)1<<size_shift;
-    ul_t u = xhash->used;
-    return (4*u < size && size_shift >= xhash->minsize_shift) ? true : false;
+    xhashidx size_shift = xhash->size_shift;
+    xhashidx size = (xhashidx)1<<size_shift;
+    xhashidx u = xhash->used;
+    return (4*u < size && size_shift > xhash->minsize_shift) ? true : false;
 }
 
 
@@ -285,39 +342,39 @@ shrink_check(xhash_t *xhash)
  */
 
 ssize_t 
-xhash_get_alloc_size(ul_t size_shift)
+xhash_get_alloc_size(xhashidx size_shift)
 {
 	return get_alloc_size(size_shift, true);
 }
 
 xhash_t *
-xhash_new(ul_t minsize_shift)
+xhash_new(xhashidx minsize_shift, enum xhash_type type)
 {
-    return xhash_new__(minsize_shift, minsize_shift, true);
+    return xhash_new__(minsize_shift, minsize_shift, type, true);
 }
 
 void xhash_free(struct xhash *xhash)
 {
-    free(xhash);
+    xtypes_free(xhash);
 }
 
-void xhash_init(struct xhash *xhash, ul_t minsize_shift)
+void xhash_init(struct xhash *xhash, xhashidx minsize_shift, enum xhash_type type)
 {
-	xhash_init__(xhash, minsize_shift, minsize_shift, true);
+	xhash_init__(xhash, minsize_shift, minsize_shift, type, true);
 }
 
 /*
 xhash_t *
 xhash_grow(struct xhash *xhash)
 {
-    ul_t new_size_shift = grow_size_shift(xhash);
+    xhashidx new_size_shift = xhash_grow_size_shift(xhash);
     return xhash_resize(xhash, new_size_shift);
 }
 
 xhash_t *
 xhash_shrink(struct xhash *xhash)
 {
-    ul_t new_size_shift = shrink_size_shift(xhash);
+    xhashidx new_size_shift = xhash_shrink_size_shift(xhash);
     return xhash_resize(xhash, new_size_shift);
 }
 
@@ -333,11 +390,13 @@ xhash_grow_check(xhash_t *xhash)
 
 #define PHASH_UPDATE(xhash, key, val, vals_flag)      \
 {                                                     \
-    ul_t size = 1UL<<(xhash->size_shift);             \
-    ul_t perturb = key;                               \
-    ul_t mask = size-1;                               \
-    ul_t idx = key & mask;                            \
-    ul_t *kvs = xhash_kvs(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 = hash_fun(key);                           \
+    xhashidx mask = size-1;                           \
+    xhashidx idx = hash_fun(key) & mask;              \
+    xhashidx *kvs = xhash_kvs(xhash);                 \
                                                       \
     INCSTAT(xhash->inserts);                          \
     for (;;) {                                        \
@@ -345,7 +404,7 @@ xhash_grow_check(xhash_t *xhash)
              PHUPD_SET__(xhash, idx, key, val);       \
              break;                                   \
         }                                             \
-        if (kvs[idx] == key){                  \
+        if (cmp_fun(kvs[idx], key)){                  \
             PHUPD_UPDATE__(xhash, idx, key, val);     \
             break;                                    \
         }                                             \
@@ -358,36 +417,38 @@ xhash_grow_check(xhash_t *xhash)
 }
 
 static inline void
-set_val(xhash_t *p, ul_t idx, ul_t key, ul_t val)
+set_val(xhash_t *p, xhashidx idx, xhashidx key, xhashidx val)
 {
-    ul_t *kvs = xhash_kvs(p);
+    xhashidx *kvs = xhash_kvs(p);
+    xhashidx *vals = xhash_vals(p);
     kvs[idx] = key;
-    ul_t *vals = xhash_vals(p);
     vals[idx] = val;
+    //XSEGLOG("Seting idx %llu to key: %lx, val: %lx", idx, key, val);
 }
 
-void static inline xhash_upd_set(xhash_t *p, ul_t idx, ul_t key, ul_t val)
+void static inline xhash_upd_set(xhash_t *p, xhashidx idx, xhashidx key, xhashidx val)
 {
-    ul_t *kvs = xhash_kvs(p);
+    xhashidx *kvs = xhash_kvs(p);
+    xhashidx *vals = xhash_vals(p);
     if (item_dummy(p, idx, true))
         p->dummies--;
     p->used++;
     kvs[idx] = key;
-    ul_t *vals = xhash_vals(p);
     vals[idx] = val;
+    //XSEGLOG("Seting idx %llu to key: %lx, val: %lx", idx, key, val);
 }
 
 static inline void
-inc_val(xhash_t *p, ul_t idx, ul_t val)
+inc_val(xhash_t *p, xhashidx idx, xhashidx val)
 {
-    ul_t *vals = xhash_vals(p);
+    xhashidx *vals = xhash_vals(p);
     vals[idx] += val;
 }
 
-void xhash_insert__(struct xhash *xhash, ul_t key, ul_t val)
+void xhash_insert__(struct xhash *xhash, xhashidx key, xhashidx val)
 {
+    //XSEGLOG("inserting %lx", key);
     //fprintf(stderr, "insert: (%lu,%lu)\n", key, val);
-    assert_kv(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)
     PHASH_UPDATE(xhash, key, val, true)
@@ -395,7 +456,7 @@ void xhash_insert__(struct xhash *xhash, ul_t key, ul_t val)
     #undef PHUPD_SET__
 }
 
-int xhash_insert(struct xhash *xhash, ul_t key, ul_t val)
+int xhash_insert(struct xhash *xhash, xhashidx key, xhashidx val)
 {
     if (grow_check(xhash))
         return -XHASH_ERESIZE;
@@ -404,10 +465,8 @@ int xhash_insert(struct xhash *xhash, ul_t key, ul_t val)
 }
 
 
-void xhash_freql_update__(struct xhash *xhash, ul_t key, ul_t val)
+void xhash_freql_update__(struct xhash *xhash, xhashidx key, xhashidx val)
 {
-    assert_kv(key, val);
-    assert_val(val);
     #define PHUPD_UPDATE__(_p, _i, _k, _v) inc_val(_p, _i, _v)
     #define PHUPD_SET__(_p, _i, _k, _v)    xhash_upd_set(_p, _i, _k, _v)
     PHASH_UPDATE(xhash, key, val, true)
@@ -415,27 +474,30 @@ void xhash_freql_update__(struct xhash *xhash, ul_t key, ul_t val)
     #undef PHUPD_SET__
 }
 
-int xhash_freql_update(struct xhash *xhash, ul_t key, ul_t val)
+int xhash_freql_update(struct xhash *xhash, xhashidx key, xhashidx val)
 {
-    assert_kv(key, val);
-    assert_val(val);
     if (grow_check(xhash))
         return -XHASH_ERESIZE;
     xhash_freql_update__(xhash, key, val);
     return 0;
 }
 
-int
-xhash_resize(xhash_t *xhash, ul_t new_size_shift, xhash_t *new)
+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)
-        new = xhash_new__(new_size_shift, xhash->minsize_shift, true);
+        new = xhash_new__(new_size_shift, xhash->minsize_shift, xhash->type, true);
     else
-        xhash_init__(new, new_size_shift, xhash->minsize_shift, true);
+        xhash_init__(new, new_size_shift, xhash->minsize_shift, xhash->type, true);
+
+    if (!new)
+	    return NULL;
         
     //fprintf(stderr, "resizing: (%lu,%lu,%lu)\n", xhash->size_shift, xhash->used, xhash->dummies);
-    for (ul_t i = 0; i < xhash_size(xhash); i++) {
+    for (i = 0; i < xhash_size(xhash); i++) {
         if (item_valid(xhash, i, true)){
             //fprintf(stderr, "rs: inserting (%lu,%lu)\n", item->k, item->v);
             xhash_insert__(new, *(xhash_kvs(xhash) + i), *(xhash_vals(xhash) + i));
@@ -444,17 +506,16 @@ xhash_resize(xhash_t *xhash, ul_t new_size_shift, xhash_t *new)
 
     if (!f)
         xtypes_free(xhash);
-    return 0;
+    return new;
 }
 
 /*
  * note that his function does not modify the internal structure of the hash
  * and thus its safe to use it for updating values during a xhash_iterate()
  */
-int xhash_update(struct xhash *xhash, ul_t key, ul_t val) {
+int xhash_update(struct xhash *xhash, xhashidx key, xhashidx val) {
 
     //fprintf(stderr, "update: (%lu,%lu)\n", key, val);
-    assert_kv(key, val);
     #define PHUPD_UPDATE__(_p, _i, _k, _v) set_val(_p, _i, _k, _v)
     #define PHUPD_SET__(_p, _i, _k, _v)    goto again
     PHASH_UPDATE(xhash, key, val, true)
@@ -465,35 +526,33 @@ int xhash_update(struct xhash *xhash, ul_t key, ul_t val) {
 }
 
 
-int xhash_delete(struct xhash *xhash, ul_t key)
+int xhash_delete(struct xhash *xhash, xhashidx key)
 {
-    #if defined(KEY_OVERLOAD)
-    assert_key(key);
-    #endif
     if (shrink_check(xhash))
 	    return -XHASH_ERESIZE;
     return xhash_delete__(xhash, key, true);
 }
 
-int xhash_lookup__(xhash_t *xhash, ul_t key, ul_t *idx_ret, bool vals)
+int xhash_lookup__(xhash_t *xhash, xhashidx key, xhashidx *idx_ret, bool vals)
 {
-    #if defined(KEY_OVERLOAD)
-    assert_key(key);
-    #endif
-
-    ul_t size_shift = xhash->size_shift;
-    ul_t size = (ul_t)1<<size_shift;
-    ul_t perturb = key;
-    ul_t mask = size-1;
-    ul_t idx = key & mask;
-    ul_t *kvs = xhash_kvs(xhash);
+    //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 = (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;
 
-        if ( !item_dummy(xhash, idx, vals) && kvs[idx] == key){
+        if ( !item_dummy(xhash, idx, vals) && cmp_fun(kvs[idx],key)){
             *idx_ret = idx;
             return 0;
         }
@@ -504,17 +563,18 @@ int xhash_lookup__(xhash_t *xhash, ul_t key, ul_t *idx_ret, bool vals)
     }
 }
 
-int xhash_lookup(struct xhash *xhash, ul_t key, ul_t *val)
+int xhash_lookup(struct xhash *xhash, xhashidx key, xhashidx *val)
 {
-    ul_t idx;
+    xhashidx idx;
     int ret = xhash_lookup__(xhash, key, &idx, true);
     if (ret == 0) {
-        ul_t *values = xhash_vals(xhash);
+        xhashidx *values = xhash_vals(xhash);
         *val = values[idx];
     }
     return ret;
 }
 
+//FIXME iteration broken
 void
 xhash_iter_init(xhash_t *xhash, xhash_iter_t *pi)
 {
@@ -523,11 +583,11 @@ xhash_iter_init(xhash_t *xhash, xhash_iter_t *pi)
 
 int
 xhash_iterate__(xhash_t *xhash, bool vals,
-                xhash_iter_t *pi, ul_t *key_ret,  ul_t *idx_ret)
+                xhash_iter_t *pi, xhashidx *key_ret,  xhashidx *idx_ret)
 {
-    ul_t idx = pi->loc;
-    ul_t size = (ul_t)1<<xhash->size_shift;
-    ul_t *kvs = xhash_kvs(xhash);
+    xhashidx idx = pi->loc;
+    xhashidx size = (xhashidx)1<<xhash->size_shift;
+    xhashidx *kvs = xhash_kvs(xhash);
     INCSTAT(xhash->lookups);
     for (;;){
         if (xhash->used == pi->cnt || idx >= size)
@@ -545,12 +605,12 @@ xhash_iterate__(xhash_t *xhash, bool vals,
     }
 }
 
-int xhash_iterate(xhash_t *xhash, xhash_iter_t *pi, ul_t *key, ul_t *val)
+int xhash_iterate(xhash_t *xhash, xhash_iter_t *pi, xhashidx *key, xhashidx *val)
 {
-    ul_t idx;
+    xhashidx idx;
     int ret = xhash_iterate__(xhash, true, pi, key, &idx);
     if (ret) {
-        ul_t *vals = xhash_vals(xhash);
+        xhashidx *vals = xhash_vals(xhash);
         *val = vals[idx];
     }
     return ret;
@@ -558,20 +618,20 @@ int xhash_iterate(xhash_t *xhash, xhash_iter_t *pi, ul_t *key, ul_t *val)
 
 void xhash_print(xhash_t *xhash)
 {
-    ul_t key, val;
+    xhashidx key, val;
     xhash_iter_t pi;
     int ret;
 
     xhash_iter_init(xhash, &pi);
-    printf("PHASH(%p):\n", xhash);
+    XSEGLOG("PHASH(%p):\n", xhash);
     for (;;){
         ret = xhash_iterate(xhash, &pi, &key, &val);
         if (!ret){
             break;
         }
-        printf(" 0x%017lx : 0x%017lx\n", key, val);
+        XSEGLOG(" 0x%017lx : 0x%017lx\n", key, val);
     }
-    printf("\n");
+    XSEGLOG("\n");
 }
 
 #ifdef PHASH_MAIN
@@ -591,10 +651,10 @@ int main(int argc, char **argv)
 {
     struct xhash *ph;
     char *s, buf[BUFLEN];
-    ul_t key, val;
+    xhashidx key, val;
     int ret;
 
-    ph = xhash_new(2);
+    ph = xhash_new(2, INTEGER);
 
     for (;;){
         s = fgets(buf, BUFLEN-1, stdin);
@@ -665,7 +725,7 @@ int main(int argc, char **argv)
  * Pset functions
  */
 pset_t *
-pset_new(ul_t minsize_shift)
+pset_new(xhashidx minsize_shift)
 {
     pset_t *pset;
     pset = malloc(sizeof(pset_t));
@@ -678,7 +738,7 @@ pset_new(ul_t minsize_shift)
 }
 
 void
-pset_init(pset_t *pset, ul_t minsize_shift)
+pset_init(pset_t *pset, xhashidx minsize_shift)
 {
     xhash_init__(&pset->ph_, minsize_shift, false);
 }
@@ -697,13 +757,13 @@ pset_tfree(pset_t *pset)
 }
 
 void
-pset_resize(pset_t *pset, ul_t new_size_shift)
+pset_resize(pset_t *pset, xhashidx new_size_shift)
 {
     pset_t  old;
     xhash_cp(&(old.ph_), &pset->ph_);
 
     xhash_resize__(&pset->ph_, new_size_shift, false);
-    for (ul_t i = 0; i < pset_size(&old); i++) {
+    for (xhashidx i = 0; i < pset_size(&old); i++) {
         if (item_valid(&(old.ph_), i, false)){
             //fprintf(stderr, "rs: inserting (%lu,%lu)\n", item->k, item->v);
             pset_insert(pset, old.ph_.kvs[i]);
@@ -715,7 +775,7 @@ pset_resize(pset_t *pset, ul_t new_size_shift)
 void
 pset_grow(pset_t *pset)
 {
-    ul_t new_size_shift = grow_size_shift(&pset->ph_);
+    xhashidx new_size_shift = grow_size_shift(&pset->ph_);
     pset_resize(pset, new_size_shift);
 }
 
@@ -726,7 +786,7 @@ pset_grow_check(pset_t *pset)
         pset_grow(pset);
 }
 
-void static inline pset_upd_set(xhash_t *p, ul_t idx, ul_t key)
+void static inline pset_upd_set(xhash_t *p, xhashidx idx, xhashidx key)
 {
     if (item_dummy(p, idx, false))
         p->dummies--;
@@ -734,7 +794,7 @@ void static inline pset_upd_set(xhash_t *p, ul_t idx, ul_t key)
     p->kvs[idx] = key;
 }
 
-void pset_insert(pset_t *pset, ul_t key)
+void pset_insert(pset_t *pset, xhashidx key)
 {
     xhash_t *ph = &pset->ph_;
     assert_key(key);
@@ -749,40 +809,40 @@ void pset_insert(pset_t *pset, ul_t key)
 void
 pset_shrink(pset_t *pset)
 {
-    ul_t new_size_shift = shrink_size_shift(&pset->ph_);
+    xhashidx new_size_shift = shrink_size_shift(&pset->ph_);
     pset_resize(pset, new_size_shift);
 }
 
-int pset_delete(pset_t *pset, ul_t key)
+int pset_delete(pset_t *pset, xhashidx key)
 {
     if (pset->ph_.used == 0)
         return false;
 
     assert_key(key);
-    ul_t size_shift = pset->ph_.size_shift;
-    ul_t size = (ul_t)1<<size_shift;
-    ul_t u = pset->ph_.used;
+    xhashidx size_shift = pset->ph_.size_shift;
+    xhashidx size = (xhashidx)1<<size_shift;
+    xhashidx u = pset->ph_.used;
     if (4*u < size)
         pset_shrink(pset);
     return xhash_delete__(&pset->ph_, key, false);
 }
 
-bool pset_lookup(pset_t *pset, ul_t key)
+bool pset_lookup(pset_t *pset, xhashidx key)
 {
-    ul_t idx;
+    xhashidx idx;
     return !!xhash_lookup__(&pset->ph_, key, &idx, false);
 }
 
-int pset_iterate(pset_t *pset, xhash_iter_t *pi, ul_t *key)
+int pset_iterate(pset_t *pset, xhash_iter_t *pi, xhashidx *key)
 {
-    ul_t idx;
+    xhashidx idx;
     int ret = xhash_iterate__(&pset->ph_, false, pi, key, &idx);
     return ret;
 }
 
 void pset_print(pset_t *pset)
 {
-    ul_t key;
+    xhashidx key;
     int ret;
     pset_iter_t pi;
 
@@ -814,7 +874,7 @@ int main(int argc, char **argv)
 {
     pset_t *ps;
     char *s, buf[BUFLEN];
-    ul_t key;
+    xhashidx key;
     int ret;
 
     ps = pset_new(2);
@@ -873,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