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

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