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