add archipelago-dbg package

[archipelago] / xseg / xtypes / xhash.c

diff --git a/xseg/xtypes/xhash.c b/xseg/xtypes/xhash.c
index c7a2a08..f174a1e 100644 (file)
--- a/xseg/xtypes/xhash.c
+++ b/xseg/xtypes/xhash.c
@@ -14,6 +14,64 @@
 
 #define PERTURB_SHIFT 5
 
 
 #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)
 {
 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)
 {
 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; 
     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);
     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);         \
     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);                 \
     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;
     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)
 }
 
 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;
     p->used++;
     kvs[idx] = key;
     vals[idx] = val;

+    //XSEGLOG("Seting idx %llu to key: %lx, val: %lx", idx, key, val);

 }
 
 static inline void
 }
 
 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)
 {
 
 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)
     //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)
 {
 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)
     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)
 {
 
 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;
     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 (;;) {
     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_unused(xhash, idx, vals) )
             return -XHASH_EEXIST;
 

@@ -867,4 +933,10 @@ int main(int argc, char **argv)
 #endif
 
 #endif //if 0
 #endif
 
 #endif //if 0

+
+#ifdef __KERNEL__
+#include <linux/module.h>
+#include <xtypes/xhash_exports.h>
+#endif
+

 // vim:expandtab:tabstop=8:shiftwidth=4:softtabstop=4
 // vim:expandtab:tabstop=8:shiftwidth=4:softtabstop=4