#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)
{
*/
void
-xhash_init__(xhash_t *xhash, xhashidx size_shift, xhashidx minsize_shift, bool vals)
+xhash_init__(xhash_t *xhash, xhashidx size_shift, xhashidx minsize_shift,
+ enum xhash_type type, bool vals)
{
xhashidx nr_items = 1UL << size_shift;
xhashidx *kvs = (xhashidx *) ((char *) xhash + sizeof(struct xhash));
xhash->dummies = xhash->used = 0;
xhash->size_shift = size_shift;
xhash->minsize_shift = minsize_shift;
+ xhash->type = type;
ZEROSTAT(xhash->inserts);
ZEROSTAT(xhash->deletes);
xhash_t *
-xhash_new__(xhashidx size_shift, xhashidx 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) {
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, 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, xhashidx key, bool vals)
{
- xhashidx perturb = key;
+// 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 = key & mask;
+ xhashidx idx = hash_fun(key) & mask;
xhashidx *kvs = xhash_kvs(xhash);
for (;;) {
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++;
}
xhash_t *
-xhash_new(xhashidx 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)
xtypes_free(xhash);
}
-void xhash_init(struct xhash *xhash, xhashidx 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);
}
/*
#define PHASH_UPDATE(xhash, key, val, vals_flag) \
{ \
- xhashidx size = 1UL<<(xhash->size_shift); \
- xhashidx perturb = key; \
- xhashidx mask = size-1; \
- xhashidx idx = key & mask; \
- xhashidx *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 (;;) { \
PHUPD_SET__(xhash, idx, key, val); \
break; \
} \
- if (kvs[idx] == key){ \
+ if (cmp_fun(kvs[idx], key)){ \
PHUPD_UPDATE__(xhash, idx, key, val); \
break; \
} \
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)
p->used++;
kvs[idx] = key;
vals[idx] = val;
+ //XSEGLOG("Seting idx %llu to key: %lx, val: %lx", idx, key, val);
}
static inline void
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)
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;
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 = key & mask;
+ 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;
}
return ret;
}
+//FIXME iteration broken
void
xhash_iter_init(xhash_t *xhash, xhash_iter_t *pi)
{
xhashidx key, val;
int ret;
- ph = xhash_new(2);
+ ph = xhash_new(2, INTEGER);
for (;;){
s = fgets(buf, BUFLEN-1, stdin);
#endif
#endif //if 0
+
+#ifdef __KERNEL__
+#include <linux/module.h>
+#include <xtypes/xhash_exports.h>
+#endif
+
// vim:expandtab:tabstop=8:shiftwidth=4:softtabstop=4
projects / archipelago / blobdiff