-//#include <stdio.h>
-//#include <stdlib.h>
-//#include <assert.h>
-//#include <unistd.h>
-//#include <stdbool.h>
-
-#define assert(...)
-
/* python hash for C
* originally by gtsouk@cslab.ece.ntua.gr
* -- kkourt@cslab.ece.ntua.gr
#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
#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);
}
-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);
}
#ifdef VAL_OVERLOAD
- assert(vals);
set_dummy_val(xhash, idx);
return;
#elif defined(KEY_OVERLOAD)
#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;
}
-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);
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);
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;
xhash->dummies = xhash->used = 0;
xhash->size_shift = size_shift;
xhash->minsize_shift = minsize_shift;
+ xhash->type = type;
ZEROSTAT(xhash->inserts);
ZEROSTAT(xhash->deletes);
}
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);
- //FIXME this should be << 1 right?
+ 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++;
}
}
-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;
//printf("used: %lu\n", u);
- if (u/2 + u >= ((ul_t)1 << old_size_shift)) {
+ if (u/2 + u >= ((xhashidx)1 << old_size_shift)) {
new_size_shift = old_size_shift + 1;
} else {
new_size_shift = old_size_shift;
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;
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;
}
*/
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);
}
#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 (;;) { \
PHUPD_SET__(xhash, idx, key, val); \
break; \
} \
- if (kvs[idx] == key){ \
+ if (cmp_fun(kvs[idx], key)){ \
PHUPD_UPDATE__(xhash, idx, key, val); \
break; \
} \
}
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)
#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;
}
-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)
#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));
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)
}
-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;
}
}
}
-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)
{
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)
}
}
-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;
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
{
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);
* Pset functions
*/
pset_t *
-pset_new(ul_t minsize_shift)
+pset_new(xhashidx minsize_shift)
{
pset_t *pset;
pset = malloc(sizeof(pset_t));
}
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);
}
}
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]);
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);
}
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--;
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);
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;
{
pset_t *ps;
char *s, buf[BUFLEN];
- ul_t key;
+ xhashidx key;
int ret;
ps = pset_new(2);
#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