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

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