code.grnet.gr Git - archipelago/blob - xseg/xtypes/xhash.c

   1 /* python hash for C
   2  *  originally by gtsouk@cslab.ece.ntua.gr
   3  *  -- kkourt@cslab.ece.ntua.gr
   4  */
   5
   6 #include <xtypes/xhash.h>
   7
   8 #define UNUSED (~(xhashidx)0)      /* this entry was never used */
   9 #define DUMMY  ((~(xhashidx)0)-1)  /* this entry was used, but now its empty */
  10
  11 //#define VAL_OVERLOAD
  12 //#define KEY_OVERLOAD
  13 //#define NO_OVERLOAD /* use separate bitarray -- not implemented */
  14
  15 #define PERTURB_SHIFT 5
  16
  17 static inline xhashidx hash_int(xhashidx key)
  18 {
  19         return key;
  20 }
  21
  22 static inline int cmp_int(xhashidx key1, xhashidx key2)
  23 {
  24         return (key1 == key2);
  25 }
  26
  27 static inline xhashidx hash_string(xhashidx key)
  28 {
  29         //assume a valid NULL terminated string
  30
  31         //function to access key if in container
  32         char *string = (char *) key;
  33         unsigned int i, len = strlen(string);
  34         xhashidx hv = string[0] << 7;
  35         for (i = 1; i <= len; i++) {
  36                 hv = (hv * 1000003) ^ string[i];
  37         }
  38         if (hv == Noxhashidx)
  39                 hv = Noxhashidx -1;
  40
  41         XSEGLOG("String %s (%lx). Hash value: %llu",
  42                         string, string, hv);
  43         return hv;
  44 }
  45
  46 static inline int cmp_string(xhashidx key1, xhashidx key2)
  47 {
  48         char *string1 = (char *) key1;
  49         char *string2 = (char *) key2;
  50         int value = !strcmp(string1, string2);
  51         XSEGLOG("String1 %s (%lx), string2: %s(%lx), r: %d",
  52                         string1, (unsigned long) string1,
  53                         string2, (unsigned long) string2,
  54                         value);
  55
  56         return (value);
  57 }
  58
  59 typedef int (*xhash_cmp_fun_t)(xhashidx key1, xhashidx key2);
  60 typedef xhashidx (*xhash_hash_fun_t)(xhashidx key);
  61
  62 struct types_functions {
  63 //      int (*cmp_fun)(xhashidx key1, xhashidx key2);
  64 //      xhashidx (*hash_fun)(xhashidx key);
  65         xhash_cmp_fun_t cmp_fun;
  66         xhash_hash_fun_t hash_fun;
  67 };
  68
  69 static struct types_functions types_fun[] = {
  70         { .cmp_fun = cmp_int, .hash_fun = hash_int },
  71         { .cmp_fun = cmp_string, .hash_fun = hash_string }
  72 };
  73
  74
  75 static inline void
  76 set_dummy_key(xhash_t *xhash, xhashidx idx)
  77 {
  78     xhashidx *kvs = xhash_kvs(xhash);
  79     kvs[idx] = DUMMY;
  80 }
  81
  82 static inline void
  83 set_dummy_val(xhash_t *xhash, xhashidx idx)
  84 {
  85     xhashidx *vals = xhash_vals(xhash);
  86     vals[idx] = DUMMY;
  87 }
  88
  89 static bool
  90 item_dummy(xhash_t *xhash, xhashidx idx, bool vals)
  91 {
  92     bool ret;
  93     xhashidx *pvals;
  94     xhashidx *kvs = xhash_kvs(xhash);
  95
  96     if (!vals) {
  97         ret = (kvs[idx] == DUMMY);
  98     } else {
  99         #if defined(VAL_OVERLOAD)
 100         pvals = xhash_vals(xhash);
 101         ret = (pvals[idx] == DUMMY);
 102         #elif defined(KEY_OVERLOAD)
 103         ret = (kvs[idx] == DUMMY);
 104         #endif
 105     }
 106     return ret;
 107
 108 }
 109
 110 static void set_dummy_item(xhash_t *xhash, xhashidx idx, bool vals)
 111 {
 112     if (!vals) {
 113         set_dummy_key(xhash, idx);
 114         return;
 115     }
 116
 117     #ifdef VAL_OVERLOAD
 118     set_dummy_val(xhash, idx);
 119     return;
 120     #elif defined(KEY_OVERLOAD)
 121     set_dummy_key(xhash, idx);
 122     return;
 123     #endif
 124 }
 125 static inline void
 126 set_unused_key(xhash_t *xhash, xhashidx idx)
 127 {
 128     xhashidx *kvs = xhash_kvs(xhash);
 129     kvs[idx] = UNUSED;
 130 }
 131
 132 static inline void
 133 set_unused_val(xhash_t *xhash, xhashidx idx)
 134 {
 135     xhashidx *vals = xhash_vals(xhash);
 136     vals[idx] = UNUSED;
 137 }
 138
 139 static inline bool
 140 val_unused(xhash_t *xhash, xhashidx idx)
 141 {
 142     xhashidx *vals = xhash_vals(xhash);
 143     return vals[idx] == UNUSED;
 144 }
 145
 146 static bool
 147 item_unused(xhash_t *xhash, xhashidx idx, bool vals)
 148 {
 149     xhashidx *kvs = xhash_kvs(xhash);
 150     if (!vals) {
 151         return kvs[idx] == UNUSED;
 152     }
 153
 154     #if defined(VAL_OVERLOAD)
 155     return val_unused(xhash, idx);
 156     #elif defined(KEY_OVERLOAD)
 157     return kvs[idx] == UNUSED;
 158     #endif
 159
 160 }
 161
 162 static inline unsigned item_valid(xhash_t *xhash, xhashidx idx, bool vals)
 163 {
 164     return !(item_dummy(xhash, idx, vals) || item_unused(xhash, idx, vals));
 165 }
 166 /*
 167 static void __attribute__((unused))
 168 assert_key(xhashidx key)
 169 {
 170     assert((key != UNUSED) && (key != DUMMY));
 171 }
 172
 173 static void
 174 assert_val(xhashidx val)
 175 {
 176     assert((val != UNUSED) && (val != DUMMY));
 177 }
 178
 179 static inline void
 180 assert_kv(xhashidx k, xhashidx v)
 181 {
 182     #if defined(KEY_OVERLOAD)
 183     assert_key(k);
 184     #elif defined(VAL_OVERLOAD)
 185     assert_val(v);
 186     #endif
 187 }
 188 */
 189
 190 void
 191 xhash_init__(xhash_t *xhash, xhashidx size_shift, xhashidx minsize_shift,
 192                 enum xhash_type type, bool vals)
 193 {
 194     xhashidx nr_items = 1UL << size_shift;
 195     xhashidx *kvs = (xhashidx *) ((char *) xhash + sizeof(struct xhash));
 196     xhashidx i;
 197
 198     XPTRSET(&xhash->kvs, kvs);
 199
 200
 201     if (!vals) {
 202         for (i=0; i < nr_items; i++)
 203             kvs[i] = UNUSED;
 204         goto out;
 205     }
 206
 207     for (i=0; i < nr_items; i++){
 208         #if defined(VAL_OVERLOAD)
 209         kvs[nr_items + i] = UNUSED;
 210         #elif  defined(KEY_OVERLOAD)
 211         kvs[i] = UNUSED;
 212         #endif
 213     }
 214
 215 out:
 216     xhash->dummies = xhash->used = 0;
 217     xhash->size_shift = size_shift;
 218     xhash->minsize_shift = minsize_shift;
 219     xhash->type = type;
 220
 221     ZEROSTAT(xhash->inserts);
 222     ZEROSTAT(xhash->deletes);
 223     ZEROSTAT(xhash->lookups);
 224     ZEROSTAT(xhash->bounces);
 225 }
 226
 227 static ssize_t
 228 get_alloc_size(xhashidx size_shift, bool vals)
 229 {
 230     xhashidx nr_items = 1UL << size_shift;
 231     size_t keys_size = nr_items*sizeof(xhashidx);
 232     size_t alloc_size = vals ? keys_size<<1 : keys_size;
 233     return sizeof(struct xhash) + alloc_size;
 234 }
 235
 236
 237 xhash_t *
 238 xhash_new__(xhashidx size_shift, xhashidx minsize_shift,
 239                 enum xhash_type type, bool vals)
 240 {
 241     struct xhash *xhash;
 242     xhash = xtypes_malloc(get_alloc_size(size_shift, vals));
 243     if (!xhash) {
 244         XSEGLOG("couldn't malloc\n");
 245         return NULL;
 246     }
 247
 248     xhash_init__(xhash, size_shift, minsize_shift, type, vals);
 249
 250     return xhash;
 251 }
 252
 253
 254 xhash_t *
 255 xhash_resize__(struct xhash *xhash, xhashidx new_size_shift, bool vals)
 256 {
 257     return xhash_new__(new_size_shift, xhash->minsize_shift, xhash->type, vals);
 258 }
 259
 260 int
 261 xhash_delete__(xhash_t *xhash, xhashidx key, bool vals)
 262 {
 263     XSEGLOG("Deleting %lx", key);
 264     xhash_cmp_fun_t cmp_fun = types_fun[xhash->type].cmp_fun;
 265     xhash_hash_fun_t hash_fun = types_fun[xhash->type].hash_fun;
 266     xhashidx perturb = hash_fun(key);
 267     xhashidx mask = xhash_size(xhash)-1;
 268     xhashidx idx = hash_fun(key) & mask;
 269     xhashidx *kvs = xhash_kvs(xhash);
 270
 271     for (;;) {
 272         if ( item_unused(xhash, idx, vals) ){
 273             return -2;
 274         }
 275
 276         if ( !item_dummy(xhash, idx, vals) && cmp_fun(kvs[idx],key)){
 277             INCSTAT(xhash->deletes);
 278             set_dummy_item(xhash, idx, vals);
 279             xhash->dummies++;
 280             //fprintf(stderr, "rm: used: %lu\n", xhash->used);
 281             xhash->used--;
 282             return 0;
 283         }
 284
 285         INCSTAT(xhash->bounces);
 286         idx = ((idx<<2) + idx + 1 + perturb) & mask;
 287         perturb >>= PERTURB_SHIFT;
 288     }
 289 }
 290
 291 xhashidx
 292 xhash_grow_size_shift(xhash_t *xhash)
 293 {
 294     xhashidx old_size_shift = xhash->size_shift;
 295     xhashidx new_size_shift;
 296     xhashidx u;
 297
 298     u = xhash->used;
 299     //printf("used: %lu\n", u);
 300     if (u/2 + u >= ((xhashidx)1 << old_size_shift)) {
 301         new_size_shift = old_size_shift + 1;
 302     } else {
 303         new_size_shift = old_size_shift;
 304     }
 305
 306     return new_size_shift;
 307 }
 308
 309 xhashidx
 310 xhash_shrink_size_shift(xhash_t *xhash)
 311 {
 312     xhashidx old_size_shift = xhash->size_shift;
 313     xhashidx new_size_shift;
 314     new_size_shift = old_size_shift - 1;
 315     if (new_size_shift < xhash->minsize_shift) {
 316         new_size_shift = xhash->minsize_shift;
 317     }
 318     return new_size_shift;
 319 }
 320
 321 static bool
 322 grow_check(xhash_t *xhash)
 323 {
 324     xhashidx size_shift = xhash->size_shift;
 325     xhashidx u = xhash->used + xhash->dummies;
 326     xhashidx size = (xhashidx)1UL<<size_shift;
 327     return ((u/2 + u) >= size) ? true : false;
 328 }
 329
 330 static bool
 331 shrink_check(xhash_t *xhash)
 332 {
 333     xhashidx size_shift = xhash->size_shift;
 334     xhashidx size = (xhashidx)1<<size_shift;
 335     xhashidx u = xhash->used;
 336     return (4*u < size && size_shift > xhash->minsize_shift) ? true : false;
 337 }
 338
 339
 340 /**
 341  * Phash functions
 342  */
 343
 344 ssize_t
 345 xhash_get_alloc_size(xhashidx size_shift)
 346 {
 347         return get_alloc_size(size_shift, true);
 348 }
 349
 350 xhash_t *
 351 xhash_new(xhashidx minsize_shift, enum xhash_type type)
 352 {
 353     return xhash_new__(minsize_shift, minsize_shift, type, true);
 354 }
 355
 356 void xhash_free(struct xhash *xhash)
 357 {
 358     xtypes_free(xhash);
 359 }
 360
 361 void xhash_init(struct xhash *xhash, xhashidx minsize_shift, enum xhash_type type)
 362 {
 363         xhash_init__(xhash, minsize_shift, minsize_shift, type, true);
 364 }
 365
 366 /*
 367 xhash_t *
 368 xhash_grow(struct xhash *xhash)
 369 {
 370     xhashidx new_size_shift = xhash_grow_size_shift(xhash);
 371     return xhash_resize(xhash, new_size_shift);
 372 }
 373
 374 xhash_t *
 375 xhash_shrink(struct xhash *xhash)
 376 {
 377     xhashidx new_size_shift = xhash_shrink_size_shift(xhash);
 378     return xhash_resize(xhash, new_size_shift);
 379 }
 380
 381 static inline xhash_t*
 382 xhash_grow_check(xhash_t *xhash)
 383 {
 384     if (grow_check(xhash))
 385         return xhash_grow(xhash);
 386     else
 387         return NULL;
 388 }
 389 */
 390
 391 #define PHASH_UPDATE(xhash, key, val, vals_flag)      \
 392 {                                                     \
 393     xhash_cmp_fun_t cmp_fun = types_fun[xhash->type].cmp_fun;         \
 394     xhash_hash_fun_t hash_fun = types_fun[xhash->type].hash_fun;       \
 395     xhashidx size = 1UL<<(xhash->size_shift);         \
 396     xhashidx perturb = hash_fun(key);                           \
 397     xhashidx mask = size-1;                           \
 398     xhashidx idx = hash_fun(key) & mask;              \
 399     xhashidx *kvs = xhash_kvs(xhash);                 \
 400                                                       \
 401     INCSTAT(xhash->inserts);                          \
 402     for (;;) {                                        \
 403     XSEGLOG("size %llu, perturb %llu idx %llu mask %llu",\
 404                     size, perturb, idx, mask);          \
 405         if ( !item_valid(xhash, idx, vals_flag) ){    \
 406              PHUPD_SET__(xhash, idx, key, val);       \
 407              break;                                   \
 408         }                                             \
 409         if (cmp_fun(kvs[idx], key)){                  \
 410             PHUPD_UPDATE__(xhash, idx, key, val);     \
 411             break;                                    \
 412         }                                             \
 413                                                       \
 414         again: __attribute__((unused))                \
 415         INCSTAT(xhash->bounces);                      \
 416         idx = ((idx<<2) + idx + 1 + perturb) & mask;  \
 417         perturb >>= PERTURB_SHIFT;                    \
 418     }                                                 \
 419 }
 420
 421 static inline void
 422 set_val(xhash_t *p, xhashidx idx, xhashidx key, xhashidx val)
 423 {
 424     xhashidx *kvs = xhash_kvs(p);
 425     xhashidx *vals = xhash_vals(p);
 426     kvs[idx] = key;
 427     vals[idx] = val;
 428     XSEGLOG("Seting idx %llu to key: %lx, val: %lx", idx, key, val);
 429 }
 430
 431 void static inline xhash_upd_set(xhash_t *p, xhashidx idx, xhashidx key, xhashidx val)
 432 {
 433     xhashidx *kvs = xhash_kvs(p);
 434     xhashidx *vals = xhash_vals(p);
 435     if (item_dummy(p, idx, true))
 436         p->dummies--;
 437     p->used++;
 438     kvs[idx] = key;
 439     vals[idx] = val;
 440     XSEGLOG("Seting idx %llu to key: %lx, val: %lx", idx, key, val);
 441 }
 442
 443 static inline void
 444 inc_val(xhash_t *p, xhashidx idx, xhashidx val)
 445 {
 446     xhashidx *vals = xhash_vals(p);
 447     vals[idx] += val;
 448 }
 449
 450 void xhash_insert__(struct xhash *xhash, xhashidx key, xhashidx val)
 451 {
 452     XSEGLOG("inserting %lx", key);
 453     //fprintf(stderr, "insert: (%lu,%lu)\n", key, val);
 454     #define PHUPD_UPDATE__(_p, _i, _k, _v) set_val(_p, _i, _k, _v)
 455     #define PHUPD_SET__(_p, _i, _k, _v)    xhash_upd_set(_p, _i, _k, _v)
 456     PHASH_UPDATE(xhash, key, val, true)
 457     #undef PHUPD_UPDATE__
 458     #undef PHUPD_SET__
 459 }
 460
 461 int xhash_insert(struct xhash *xhash, xhashidx key, xhashidx val)
 462 {
 463     if (grow_check(xhash))
 464         return -XHASH_ERESIZE;
 465     xhash_insert__(xhash, key, val);
 466     return 0;
 467 }
 468
 469
 470 void xhash_freql_update__(struct xhash *xhash, xhashidx key, xhashidx val)
 471 {
 472     #define PHUPD_UPDATE__(_p, _i, _k, _v) inc_val(_p, _i, _v)
 473     #define PHUPD_SET__(_p, _i, _k, _v)    xhash_upd_set(_p, _i, _k, _v)
 474     PHASH_UPDATE(xhash, key, val, true)
 475     #undef PHUPD_UPDATE__
 476     #undef PHUPD_SET__
 477 }
 478
 479 int xhash_freql_update(struct xhash *xhash, xhashidx key, xhashidx val)
 480 {
 481     if (grow_check(xhash))
 482         return -XHASH_ERESIZE;
 483     xhash_freql_update__(xhash, key, val);
 484     return 0;
 485 }
 486
 487 xhash_t *
 488 xhash_resize(xhash_t *xhash, xhashidx new_size_shift, xhash_t *new)
 489 {
 490     XSEGLOG("Resizing xhash from %llu to %llu", xhash->size_shift, new_size_shift);
 491     xhashidx i;
 492     int f = !!new;
 493     if (!f)
 494         new = xhash_new__(new_size_shift, xhash->minsize_shift, xhash->type, true);
 495     else
 496         xhash_init__(new, new_size_shift, xhash->minsize_shift, xhash->type, true);
 497
 498     if (!new)
 499             return NULL;
 500
 501     //fprintf(stderr, "resizing: (%lu,%lu,%lu)\n", xhash->size_shift, xhash->used, xhash->dummies);
 502     for (i = 0; i < xhash_size(xhash); i++) {
 503         if (item_valid(xhash, i, true)){
 504             //fprintf(stderr, "rs: inserting (%lu,%lu)\n", item->k, item->v);
 505             xhash_insert__(new, *(xhash_kvs(xhash) + i), *(xhash_vals(xhash) + i));
 506         }
 507     }
 508
 509     if (!f)
 510         xtypes_free(xhash);
 511     return new;
 512 }
 513
 514 /*
 515  * note that his function does not modify the internal structure of the hash
 516  * and thus its safe to use it for updating values during a xhash_iterate()
 517  */
 518 int xhash_update(struct xhash *xhash, xhashidx key, xhashidx val) {
 519
 520     //fprintf(stderr, "update: (%lu,%lu)\n", key, val);
 521     #define PHUPD_UPDATE__(_p, _i, _k, _v) set_val(_p, _i, _k, _v)
 522     #define PHUPD_SET__(_p, _i, _k, _v)    goto again
 523     PHASH_UPDATE(xhash, key, val, true)
 524     #undef PHUPD_UPDATE__
 525     #undef PHUPD_SET__
 526
 527     return 1;
 528 }
 529
 530
 531 int xhash_delete(struct xhash *xhash, xhashidx key)
 532 {
 533     if (shrink_check(xhash))
 534             return -XHASH_ERESIZE;
 535     return xhash_delete__(xhash, key, true);
 536 }
 537
 538 int xhash_lookup__(xhash_t *xhash, xhashidx key, xhashidx *idx_ret, bool vals)
 539 {
 540     XSEGLOG("looking up %lx", key);
 541     xhash_cmp_fun_t cmp_fun = types_fun[xhash->type].cmp_fun;
 542     xhash_hash_fun_t hash_fun = types_fun[xhash->type].hash_fun;
 543     xhashidx size_shift = xhash->size_shift;
 544     xhashidx size = (1UL)<<size_shift;
 545     xhashidx perturb = hash_fun(key);
 546     xhashidx mask = size-1;
 547     xhashidx idx = hash_fun(key) & mask;
 548     xhashidx *kvs = xhash_kvs(xhash);
 549
 550     INCSTAT(xhash->lookups);
 551     for (;;) {
 552         XSEGLOG("size %llu, perturb %llu idx %llu mask %llu",\
 553                     size, perturb, idx, mask);          \
 554         if ( item_unused(xhash, idx, vals) )
 555             return -XHASH_EEXIST;
 556
 557         if ( !item_dummy(xhash, idx, vals) && cmp_fun(kvs[idx],key)){
 558             *idx_ret = idx;
 559             return 0;
 560         }
 561
 562         INCSTAT(xhash->bounces);
 563         idx = ((idx<<2) + idx + 1 + perturb) & mask;
 564         perturb >>= PERTURB_SHIFT;
 565     }
 566 }
 567
 568 int xhash_lookup(struct xhash *xhash, xhashidx key, xhashidx *val)
 569 {
 570     xhashidx idx;
 571     int ret = xhash_lookup__(xhash, key, &idx, true);
 572     if (ret == 0) {
 573         xhashidx *values = xhash_vals(xhash);
 574         *val = values[idx];
 575     }
 576     return ret;
 577 }
 578
 579 //FIXME iteration broken
 580 void
 581 xhash_iter_init(xhash_t *xhash, xhash_iter_t *pi)
 582 {
 583     pi->cnt = pi->loc = 0;
 584 }
 585
 586 int
 587 xhash_iterate__(xhash_t *xhash, bool vals,
 588                 xhash_iter_t *pi, xhashidx *key_ret,  xhashidx *idx_ret)
 589 {
 590     xhashidx idx = pi->loc;
 591     xhashidx size = (xhashidx)1<<xhash->size_shift;
 592     xhashidx *kvs = xhash_kvs(xhash);
 593     INCSTAT(xhash->lookups);
 594     for (;;){
 595         if (xhash->used == pi->cnt || idx >= size)
 596             return 0;
 597
 598         if (item_valid(xhash, idx, vals)){
 599             *key_ret = kvs[idx];
 600             *idx_ret = idx++;
 601             pi->loc = idx;
 602             pi->cnt++;
 603             return 1;
 604         }
 605
 606         idx++;
 607     }
 608 }
 609
 610 int xhash_iterate(xhash_t *xhash, xhash_iter_t *pi, xhashidx *key, xhashidx *val)
 611 {
 612     xhashidx idx;
 613     int ret = xhash_iterate__(xhash, true, pi, key, &idx);
 614     if (ret) {
 615         xhashidx *vals = xhash_vals(xhash);
 616         *val = vals[idx];
 617     }
 618     return ret;
 619 }
 620
 621 void xhash_print(xhash_t *xhash)
 622 {
 623     xhashidx key, val;
 624     xhash_iter_t pi;
 625     int ret;
 626
 627     xhash_iter_init(xhash, &pi);
 628     XSEGLOG("PHASH(%p):\n", xhash);
 629     for (;;){
 630         ret = xhash_iterate(xhash, &pi, &key, &val);
 631         if (!ret){
 632             break;
 633         }
 634         XSEGLOG(" 0x%017lx : 0x%017lx\n", key, val);
 635     }
 636     XSEGLOG("\n");
 637 }
 638
 639 #ifdef PHASH_MAIN
 640 #define BUFLEN 1024
 641 void help()
 642 {
 643     printf("Help:\n"
 644            "  insert : I <key> <val> \n"
 645            "  update : U <key> <val> (->v += val if exists) \n"
 646            "  get    : G <key>       \n"
 647            "  delete : D <key>       \n"
 648            "  size   : S             \n"
 649            "  print  : P             \n");
 650 }
 651
 652 int main(int argc, char **argv)
 653 {
 654     struct xhash *ph;
 655     char *s, buf[BUFLEN];
 656     xhashidx key, val;
 657     int ret;
 658
 659     ph = xhash_new(2, INTEGER);
 660
 661     for (;;){
 662         s = fgets(buf, BUFLEN-1, stdin);
 663         if (s == NULL){
 664             break;
 665         }
 666
 667         switch (*s) {
 668             case 'I':
 669             ret = sscanf(s+1, "%lu %lu", &key, &val);
 670             if (ret == 2){
 671                 xhash_insert(ph, key, val);
 672             }
 673             break;
 674
 675             case 'U':
 676             ret = sscanf(s+1, "%lu %lu", &key, &val);
 677             if (ret == 2){
 678                 xhash_freql_update(ph, key, val);
 679             }
 680             break;
 681
 682             case 'G':
 683             ret = sscanf(s+1, "%lu", &key);
 684             if (ret == 1){
 685                 ret = xhash_lookup(ph, key, &val);
 686                 if (ret){
 687                     printf("%lu\n", val);
 688                 } else {
 689                     printf("<None>\n");
 690                 }
 691             }
 692             break;
 693
 694             case 'D':
 695             ret = sscanf(s+1, "%lu", &key);
 696             if (ret == 1){
 697                 xhash_delete(ph, key);
 698             }
 699             break;
 700
 701             case 'S':
 702             printf("%lu\n", xhash_elements(ph));
 703             break;
 704
 705             case 'P':
 706             xhash_print(ph);
 707             break;
 708
 709             case '#':
 710             break;
 711
 712             default:
 713             help();
 714             break;
 715
 716         }
 717         fflush(stdout);
 718     }
 719
 720     xhash_free(ph);
 721     return 0;
 722 }
 723 #endif
 724
 725 #if 0
 726 /**
 727  * Pset functions
 728  */
 729 pset_t *
 730 pset_new(xhashidx minsize_shift)
 731 {
 732     pset_t *pset;
 733     pset = malloc(sizeof(pset_t));
 734     if (!pset) {
 735         perror("malloc");
 736         exit(1);
 737     }
 738     xhash_init__(&pset->ph_, minsize_shift, false);
 739     return pset;
 740 }
 741
 742 void
 743 pset_init(pset_t *pset, xhashidx minsize_shift)
 744 {
 745     xhash_init__(&pset->ph_, minsize_shift, false);
 746 }
 747
 748 void
 749 pset_free(pset_t *pset)
 750 {
 751     xhash_tfree(&pset->ph_);
 752     free(pset);
 753 }
 754
 755 void
 756 pset_tfree(pset_t *pset)
 757 {
 758     xhash_tfree(&pset->ph_);
 759 }
 760
 761 void
 762 pset_resize(pset_t *pset, xhashidx new_size_shift)
 763 {
 764     pset_t  old;
 765     xhash_cp(&(old.ph_), &pset->ph_);
 766
 767     xhash_resize__(&pset->ph_, new_size_shift, false);
 768     for (xhashidx i = 0; i < pset_size(&old); i++) {
 769         if (item_valid(&(old.ph_), i, false)){
 770             //fprintf(stderr, "rs: inserting (%lu,%lu)\n", item->k, item->v);
 771             pset_insert(pset, old.ph_.kvs[i]);
 772         }
 773     }
 774     free(old.ph_.kvs);
 775 }
 776
 777 void
 778 pset_grow(pset_t *pset)
 779 {
 780     xhashidx new_size_shift = grow_size_shift(&pset->ph_);
 781     pset_resize(pset, new_size_shift);
 782 }
 783
 784 static inline void
 785 pset_grow_check(pset_t *pset)
 786 {
 787     if (grow_check(&pset->ph_))
 788         pset_grow(pset);
 789 }
 790
 791 void static inline pset_upd_set(xhash_t *p, xhashidx idx, xhashidx key)
 792 {
 793     if (item_dummy(p, idx, false))
 794         p->dummies--;
 795     p->used++;
 796     p->kvs[idx] = key;
 797 }
 798
 799 void pset_insert(pset_t *pset, xhashidx key)
 800 {
 801     xhash_t *ph = &pset->ph_;
 802     assert_key(key);
 803     pset_grow_check(pset);
 804     #define PHUPD_UPDATE__(_p, _i, _k, _v) do { } while (0)
 805     #define PHUPD_SET__(_p, _i, _k, _v) pset_upd_set(_p, _i, _k)
 806     PHASH_UPDATE(ph, key, 0xdeadbabe, false)
 807     #undef PHUPD_UPDATE__
 808     #undef PHUPD_SET__
 809 }
 810
 811 void
 812 pset_shrink(pset_t *pset)
 813 {
 814     xhashidx new_size_shift = shrink_size_shift(&pset->ph_);
 815     pset_resize(pset, new_size_shift);
 816 }
 817
 818 int pset_delete(pset_t *pset, xhashidx key)
 819 {
 820     if (pset->ph_.used == 0)
 821         return false;
 822
 823     assert_key(key);
 824     xhashidx size_shift = pset->ph_.size_shift;
 825     xhashidx size = (xhashidx)1<<size_shift;
 826     xhashidx u = pset->ph_.used;
 827     if (4*u < size)
 828         pset_shrink(pset);
 829     return xhash_delete__(&pset->ph_, key, false);
 830 }
 831
 832 bool pset_lookup(pset_t *pset, xhashidx key)
 833 {
 834     xhashidx idx;
 835     return !!xhash_lookup__(&pset->ph_, key, &idx, false);
 836 }
 837
 838 int pset_iterate(pset_t *pset, xhash_iter_t *pi, xhashidx *key)
 839 {
 840     xhashidx idx;
 841     int ret = xhash_iterate__(&pset->ph_, false, pi, key, &idx);
 842     return ret;
 843 }
 844
 845 void pset_print(pset_t *pset)
 846 {
 847     xhashidx key;
 848     int ret;
 849     pset_iter_t pi;
 850
 851     pset_iter_init(pset, &pi);
 852     printf("PSET(%p):\n", pset);
 853     for (;;){
 854         ret = pset_iterate(pset, &pi, &key);
 855         if (!ret){
 856             break;
 857         }
 858         printf(" 0x%017lx\n", key);
 859     }
 860     printf("\n");
 861 }
 862
 863 #if defined(PSET_MAIN)
 864 #define BUFLEN 1024
 865 void help()
 866 {
 867     printf("Help:\n"
 868            "  insert : I <key> <val> \n"
 869            "  get    : G <key>       \n"
 870            "  delete : D <key>       \n"
 871            "  size   : S             \n"
 872            "  print  : P             \n");
 873 }
 874
 875 int main(int argc, char **argv)
 876 {
 877     pset_t *ps;
 878     char *s, buf[BUFLEN];
 879     xhashidx key;
 880     int ret;
 881
 882     ps = pset_new(2);
 883
 884     for (;;){
 885         s = fgets(buf, BUFLEN-1, stdin);
 886         if (s == NULL){
 887             break;
 888         }
 889
 890         switch (*s) {
 891             case 'I':
 892             ret = sscanf(s+1, "%lu", &key);
 893             if (ret == 1){
 894                 pset_insert(ps, key);
 895             }
 896             break;
 897
 898             case 'G':
 899             ret = sscanf(s+1, "%lu", &key);
 900             if (ret == 1){
 901                 ret = pset_lookup(ps, key);
 902                 printf("%lu -> %s\n", key, ret ? "true" : "false");
 903             }
 904             break;
 905
 906             case 'D':
 907             ret = sscanf(s+1, "%lu", &key);
 908             if (ret == 1){
 909                 pset_delete(ps, key);
 910             }
 911             break;
 912
 913             case 'S':
 914             printf("%lu\n", pset_elements(ps));
 915             break;
 916
 917             case 'P':
 918             pset_print(ps);
 919             break;
 920
 921             case '#':
 922             break;
 923
 924             default:
 925             help();
 926             break;
 927
 928         }
 929         fflush(stdout);
 930     }
 931
 932     pset_free(ps);
 933     return 0;
 934 }
 935 #endif
 936
 937 #endif //if 0
 938
 939 #ifdef __KERNEL__
 940 #include <linux/module.h>
 941 #include <xtypes/xhash_exports.h>
 942 #endif
 943
 944 // vim:expandtab:tabstop=8:shiftwidth=4:softtabstop=4