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