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

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