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         if ( !item_valid(xhash, idx, vals_flag) ){    \
 404              PHUPD_SET__(xhash, idx, key, val);       \
 405              break;                                   \
 406         }                                             \
 407         if (cmp_fun(kvs[idx], key)){                  \
 408             PHUPD_UPDATE__(xhash, idx, key, val);     \
 409             break;                                    \
 410         }                                             \
 411                                                       \
 412         again: __attribute__((unused))                \
 413         INCSTAT(xhash->bounces);                      \
 414         idx = ((idx<<2) + idx + 1 + perturb) & mask;  \
 415         perturb >>= PERTURB_SHIFT;                    \
 416     }                                                 \
 417 }
 418
 419 static inline void
 420 set_val(xhash_t *p, xhashidx idx, xhashidx key, xhashidx val)
 421 {
 422     xhashidx *kvs = xhash_kvs(p);
 423     xhashidx *vals = xhash_vals(p);
 424     kvs[idx] = key;
 425     vals[idx] = val;
 426     //XSEGLOG("Seting idx %llu to key: %lx, val: %lx", idx, key, val);
 427 }
 428
 429 void static inline xhash_upd_set(xhash_t *p, xhashidx idx, xhashidx key, xhashidx val)
 430 {
 431     xhashidx *kvs = xhash_kvs(p);
 432     xhashidx *vals = xhash_vals(p);
 433     if (item_dummy(p, idx, true))
 434         p->dummies--;
 435     p->used++;
 436     kvs[idx] = key;
 437     vals[idx] = val;
 438     //XSEGLOG("Seting idx %llu to key: %lx, val: %lx", idx, key, val);
 439 }
 440
 441 static inline void
 442 inc_val(xhash_t *p, xhashidx idx, xhashidx val)
 443 {
 444     xhashidx *vals = xhash_vals(p);
 445     vals[idx] += val;
 446 }
 447
 448 void xhash_insert__(struct xhash *xhash, xhashidx key, xhashidx val)
 449 {
 450     //XSEGLOG("inserting %lx", key);
 451     //fprintf(stderr, "insert: (%lu,%lu)\n", key, val);
 452     #define PHUPD_UPDATE__(_p, _i, _k, _v) set_val(_p, _i, _k, _v)
 453     #define PHUPD_SET__(_p, _i, _k, _v)    xhash_upd_set(_p, _i, _k, _v)
 454     PHASH_UPDATE(xhash, key, val, true)
 455     #undef PHUPD_UPDATE__
 456     #undef PHUPD_SET__
 457 }
 458
 459 int xhash_insert(struct xhash *xhash, xhashidx key, xhashidx val)
 460 {
 461     if (grow_check(xhash))
 462         return -XHASH_ERESIZE;
 463     xhash_insert__(xhash, key, val);
 464     return 0;
 465 }
 466
 467
 468 void xhash_freql_update__(struct xhash *xhash, xhashidx key, xhashidx val)
 469 {
 470     #define PHUPD_UPDATE__(_p, _i, _k, _v) inc_val(_p, _i, _v)
 471     #define PHUPD_SET__(_p, _i, _k, _v)    xhash_upd_set(_p, _i, _k, _v)
 472     PHASH_UPDATE(xhash, key, val, true)
 473     #undef PHUPD_UPDATE__
 474     #undef PHUPD_SET__
 475 }
 476
 477 int xhash_freql_update(struct xhash *xhash, xhashidx key, xhashidx val)
 478 {
 479     if (grow_check(xhash))
 480         return -XHASH_ERESIZE;
 481     xhash_freql_update__(xhash, key, val);
 482     return 0;
 483 }
 484
 485 xhash_t *
 486 xhash_resize(xhash_t *xhash, xhashidx new_size_shift, xhash_t *new)
 487 {
 488     //XSEGLOG("Resizing xhash from %llu to %llu", xhash->size_shift, new_size_shift);
 489     xhashidx i;
 490     int f = !!new;
 491     if (!f)
 492         new = xhash_new__(new_size_shift, xhash->minsize_shift, xhash->type, true);
 493     else
 494         xhash_init__(new, new_size_shift, xhash->minsize_shift, xhash->type, true);
 495
 496     if (!new)
 497             return NULL;
 498
 499     //fprintf(stderr, "resizing: (%lu,%lu,%lu)\n", xhash->size_shift, xhash->used, xhash->dummies);
 500     for (i = 0; i < xhash_size(xhash); i++) {
 501         if (item_valid(xhash, i, true)){
 502             //fprintf(stderr, "rs: inserting (%lu,%lu)\n", item->k, item->v);
 503             xhash_insert__(new, *(xhash_kvs(xhash) + i), *(xhash_vals(xhash) + i));
 504         }
 505     }
 506
 507     if (!f)
 508         xtypes_free(xhash);
 509     return new;
 510 }
 511
 512 /*
 513  * note that his function does not modify the internal structure of the hash
 514  * and thus its safe to use it for updating values during a xhash_iterate()
 515  */
 516 int xhash_update(struct xhash *xhash, xhashidx key, xhashidx val) {
 517
 518     //fprintf(stderr, "update: (%lu,%lu)\n", key, val);
 519     #define PHUPD_UPDATE__(_p, _i, _k, _v) set_val(_p, _i, _k, _v)
 520     #define PHUPD_SET__(_p, _i, _k, _v)    goto again
 521     PHASH_UPDATE(xhash, key, val, true)
 522     #undef PHUPD_UPDATE__
 523     #undef PHUPD_SET__
 524
 525     return 1;
 526 }
 527
 528
 529 int xhash_delete(struct xhash *xhash, xhashidx key)
 530 {
 531     if (shrink_check(xhash))
 532             return -XHASH_ERESIZE;
 533     return xhash_delete__(xhash, key, true);
 534 }
 535
 536 int xhash_lookup__(xhash_t *xhash, xhashidx key, xhashidx *idx_ret, bool vals)
 537 {
 538     //XSEGLOG("looking up %lx", key);
 539     xhash_cmp_fun_t cmp_fun = types_fun[xhash->type].cmp_fun;
 540     xhash_hash_fun_t hash_fun = types_fun[xhash->type].hash_fun;
 541     xhashidx size_shift = xhash->size_shift;
 542     xhashidx size = (1UL)<<size_shift;
 543     xhashidx perturb = hash_fun(key);
 544     xhashidx mask = size-1;
 545     xhashidx idx = hash_fun(key) & mask;
 546     xhashidx *kvs = xhash_kvs(xhash);
 547
 548     INCSTAT(xhash->lookups);
 549     for (;;) {
 550         //XSEGLOG("size %llu, perturb %llu idx %llu mask %llu",
 551         //          size, perturb, idx, mask);
 552         if ( item_unused(xhash, idx, vals) )
 553             return -XHASH_EEXIST;
 554
 555         if ( !item_dummy(xhash, idx, vals) && cmp_fun(kvs[idx],key)){
 556             *idx_ret = idx;
 557             return 0;
 558         }
 559
 560         INCSTAT(xhash->bounces);
 561         idx = ((idx<<2) + idx + 1 + perturb) & mask;
 562         perturb >>= PERTURB_SHIFT;
 563     }
 564 }
 565
 566 int xhash_lookup(struct xhash *xhash, xhashidx key, xhashidx *val)
 567 {
 568     xhashidx idx;
 569     int ret = xhash_lookup__(xhash, key, &idx, true);
 570     if (ret == 0) {
 571         xhashidx *values = xhash_vals(xhash);
 572         *val = values[idx];
 573     }
 574     return ret;
 575 }
 576
 577 //FIXME iteration broken
 578 void
 579 xhash_iter_init(xhash_t *xhash, xhash_iter_t *pi)
 580 {
 581     pi->cnt = pi->loc = 0;
 582 }
 583
 584 int
 585 xhash_iterate__(xhash_t *xhash, bool vals,
 586                 xhash_iter_t *pi, xhashidx *key_ret,  xhashidx *idx_ret)
 587 {
 588     xhashidx idx = pi->loc;
 589     xhashidx size = (xhashidx)1<<xhash->size_shift;
 590     xhashidx *kvs = xhash_kvs(xhash);
 591     INCSTAT(xhash->lookups);
 592     for (;;){
 593         if (xhash->used == pi->cnt || idx >= size)
 594             return 0;
 595
 596         if (item_valid(xhash, idx, vals)){
 597             *key_ret = kvs[idx];
 598             *idx_ret = idx++;
 599             pi->loc = idx;
 600             pi->cnt++;
 601             return 1;
 602         }
 603
 604         idx++;
 605     }
 606 }
 607
 608 int xhash_iterate(xhash_t *xhash, xhash_iter_t *pi, xhashidx *key, xhashidx *val)
 609 {
 610     xhashidx idx;
 611     int ret = xhash_iterate__(xhash, true, pi, key, &idx);
 612     if (ret) {
 613         xhashidx *vals = xhash_vals(xhash);
 614         *val = vals[idx];
 615     }
 616     return ret;
 617 }
 618
 619 void xhash_print(xhash_t *xhash)
 620 {
 621     xhashidx key, val;
 622     xhash_iter_t pi;
 623     int ret;
 624
 625     xhash_iter_init(xhash, &pi);
 626     XSEGLOG("PHASH(%p):\n", xhash);
 627     for (;;){
 628         ret = xhash_iterate(xhash, &pi, &key, &val);
 629         if (!ret){
 630             break;
 631         }
 632         XSEGLOG(" 0x%017lx : 0x%017lx\n", key, val);
 633     }
 634     XSEGLOG("\n");
 635 }
 636
 637 #ifdef PHASH_MAIN
 638 #define BUFLEN 1024
 639 void help()
 640 {
 641     printf("Help:\n"
 642            "  insert : I <key> <val> \n"
 643            "  update : U <key> <val> (->v += val if exists) \n"
 644            "  get    : G <key>       \n"
 645            "  delete : D <key>       \n"
 646            "  size   : S             \n"
 647            "  print  : P             \n");
 648 }
 649
 650 int main(int argc, char **argv)
 651 {
 652     struct xhash *ph;
 653     char *s, buf[BUFLEN];
 654     xhashidx key, val;
 655     int ret;
 656
 657     ph = xhash_new(2, INTEGER);
 658
 659     for (;;){
 660         s = fgets(buf, BUFLEN-1, stdin);
 661         if (s == NULL){
 662             break;
 663         }
 664
 665         switch (*s) {
 666             case 'I':
 667             ret = sscanf(s+1, "%lu %lu", &key, &val);
 668             if (ret == 2){
 669                 xhash_insert(ph, key, val);
 670             }
 671             break;
 672
 673             case 'U':
 674             ret = sscanf(s+1, "%lu %lu", &key, &val);
 675             if (ret == 2){
 676                 xhash_freql_update(ph, key, val);
 677             }
 678             break;
 679
 680             case 'G':
 681             ret = sscanf(s+1, "%lu", &key);
 682             if (ret == 1){
 683                 ret = xhash_lookup(ph, key, &val);
 684                 if (ret){
 685                     printf("%lu\n", val);
 686                 } else {
 687                     printf("<None>\n");
 688                 }
 689             }
 690             break;
 691
 692             case 'D':
 693             ret = sscanf(s+1, "%lu", &key);
 694             if (ret == 1){
 695                 xhash_delete(ph, key);
 696             }
 697             break;
 698
 699             case 'S':
 700             printf("%lu\n", xhash_elements(ph));
 701             break;
 702
 703             case 'P':
 704             xhash_print(ph);
 705             break;
 706
 707             case '#':
 708             break;
 709
 710             default:
 711             help();
 712             break;
 713
 714         }
 715         fflush(stdout);
 716     }
 717
 718     xhash_free(ph);
 719     return 0;
 720 }
 721 #endif
 722
 723 #if 0
 724 /**
 725  * Pset functions
 726  */
 727 pset_t *
 728 pset_new(xhashidx minsize_shift)
 729 {
 730     pset_t *pset;
 731     pset = malloc(sizeof(pset_t));
 732     if (!pset) {
 733         perror("malloc");
 734         exit(1);
 735     }
 736     xhash_init__(&pset->ph_, minsize_shift, false);
 737     return pset;
 738 }
 739
 740 void
 741 pset_init(pset_t *pset, xhashidx minsize_shift)
 742 {
 743     xhash_init__(&pset->ph_, minsize_shift, false);
 744 }
 745
 746 void
 747 pset_free(pset_t *pset)
 748 {
 749     xhash_tfree(&pset->ph_);
 750     free(pset);
 751 }
 752
 753 void
 754 pset_tfree(pset_t *pset)
 755 {
 756     xhash_tfree(&pset->ph_);
 757 }
 758
 759 void
 760 pset_resize(pset_t *pset, xhashidx new_size_shift)
 761 {
 762     pset_t  old;
 763     xhash_cp(&(old.ph_), &pset->ph_);
 764
 765     xhash_resize__(&pset->ph_, new_size_shift, false);
 766     for (xhashidx i = 0; i < pset_size(&old); i++) {
 767         if (item_valid(&(old.ph_), i, false)){
 768             //fprintf(stderr, "rs: inserting (%lu,%lu)\n", item->k, item->v);
 769             pset_insert(pset, old.ph_.kvs[i]);
 770         }
 771     }
 772     free(old.ph_.kvs);
 773 }
 774
 775 void
 776 pset_grow(pset_t *pset)
 777 {
 778     xhashidx new_size_shift = grow_size_shift(&pset->ph_);
 779     pset_resize(pset, new_size_shift);
 780 }
 781
 782 static inline void
 783 pset_grow_check(pset_t *pset)
 784 {
 785     if (grow_check(&pset->ph_))
 786         pset_grow(pset);
 787 }
 788
 789 void static inline pset_upd_set(xhash_t *p, xhashidx idx, xhashidx key)
 790 {
 791     if (item_dummy(p, idx, false))
 792         p->dummies--;
 793     p->used++;
 794     p->kvs[idx] = key;
 795 }
 796
 797 void pset_insert(pset_t *pset, xhashidx key)
 798 {
 799     xhash_t *ph = &pset->ph_;
 800     assert_key(key);
 801     pset_grow_check(pset);
 802     #define PHUPD_UPDATE__(_p, _i, _k, _v) do { } while (0)
 803     #define PHUPD_SET__(_p, _i, _k, _v) pset_upd_set(_p, _i, _k)
 804     PHASH_UPDATE(ph, key, 0xdeadbabe, false)
 805     #undef PHUPD_UPDATE__
 806     #undef PHUPD_SET__
 807 }
 808
 809 void
 810 pset_shrink(pset_t *pset)
 811 {
 812     xhashidx new_size_shift = shrink_size_shift(&pset->ph_);
 813     pset_resize(pset, new_size_shift);
 814 }
 815
 816 int pset_delete(pset_t *pset, xhashidx key)
 817 {
 818     if (pset->ph_.used == 0)
 819         return false;
 820
 821     assert_key(key);
 822     xhashidx size_shift = pset->ph_.size_shift;
 823     xhashidx size = (xhashidx)1<<size_shift;
 824     xhashidx u = pset->ph_.used;
 825     if (4*u < size)
 826         pset_shrink(pset);
 827     return xhash_delete__(&pset->ph_, key, false);
 828 }
 829
 830 bool pset_lookup(pset_t *pset, xhashidx key)
 831 {
 832     xhashidx idx;
 833     return !!xhash_lookup__(&pset->ph_, key, &idx, false);
 834 }
 835
 836 int pset_iterate(pset_t *pset, xhash_iter_t *pi, xhashidx *key)
 837 {
 838     xhashidx idx;
 839     int ret = xhash_iterate__(&pset->ph_, false, pi, key, &idx);
 840     return ret;
 841 }
 842
 843 void pset_print(pset_t *pset)
 844 {
 845     xhashidx key;
 846     int ret;
 847     pset_iter_t pi;
 848
 849     pset_iter_init(pset, &pi);
 850     printf("PSET(%p):\n", pset);
 851     for (;;){
 852         ret = pset_iterate(pset, &pi, &key);
 853         if (!ret){
 854             break;
 855         }
 856         printf(" 0x%017lx\n", key);
 857     }
 858     printf("\n");
 859 }
 860
 861 #if defined(PSET_MAIN)
 862 #define BUFLEN 1024
 863 void help()
 864 {
 865     printf("Help:\n"
 866            "  insert : I <key> <val> \n"
 867            "  get    : G <key>       \n"
 868            "  delete : D <key>       \n"
 869            "  size   : S             \n"
 870            "  print  : P             \n");
 871 }
 872
 873 int main(int argc, char **argv)
 874 {
 875     pset_t *ps;
 876     char *s, buf[BUFLEN];
 877     xhashidx key;
 878     int ret;
 879
 880     ps = pset_new(2);
 881
 882     for (;;){
 883         s = fgets(buf, BUFLEN-1, stdin);
 884         if (s == NULL){
 885             break;
 886         }
 887
 888         switch (*s) {
 889             case 'I':
 890             ret = sscanf(s+1, "%lu", &key);
 891             if (ret == 1){
 892                 pset_insert(ps, key);
 893             }
 894             break;
 895
 896             case 'G':
 897             ret = sscanf(s+1, "%lu", &key);
 898             if (ret == 1){
 899                 ret = pset_lookup(ps, key);
 900                 printf("%lu -> %s\n", key, ret ? "true" : "false");
 901             }
 902             break;
 903
 904             case 'D':
 905             ret = sscanf(s+1, "%lu", &key);
 906             if (ret == 1){
 907                 pset_delete(ps, key);
 908             }
 909             break;
 910
 911             case 'S':
 912             printf("%lu\n", pset_elements(ps));
 913             break;
 914
 915             case 'P':
 916             pset_print(ps);
 917             break;
 918
 919             case '#':
 920             break;
 921
 922             default:
 923             help();
 924             break;
 925
 926         }
 927         fflush(stdout);
 928     }
 929
 930     pset_free(ps);
 931     return 0;
 932 }
 933 #endif
 934
 935 #endif //if 0
 936
 937 #ifdef __KERNEL__
 938 #include <linux/module.h>
 939 #include <xtypes/xhash_exports.h>
 940 #endif
 941
 942 // vim:expandtab:tabstop=8:shiftwidth=4:softtabstop=4