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