hash.c

   1 /* A hash class.
   2  * By Richard W.M. Jones <rich@annexia.org>
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Library General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public
  15  * License along with this library; if not, write to the Free
  16  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17  *
  18  * $Id: hash.c,v 1.4 2002/11/26 19:47:29 rich Exp $
  19  */
  20
  21 #include "config.h"
  22
  23 #ifdef HAVE_STRING_H
  24 #include <string.h>
  25 #endif
  26
  27 #include <pstring.h>
  28 #include <vector.h>
  29 #include <hash.h>
  30
  31 struct hash
  32 {
  33   pool pool;
  34   size_t key_size;
  35   size_t value_size;
  36   vector buckets;
  37 };
  38
  39 struct sash
  40 {
  41   pool pool;
  42   vector buckets;
  43 };
  44
  45 struct shash
  46 {
  47   pool pool;
  48   size_t value_size;
  49   vector buckets;
  50 };
  51
  52 #define HASH_NR_BUCKETS 32
  53
  54 /* This is the hashing function -- the same one as used by Perl. */
  55 static inline unsigned
  56 HASH (const void *key, size_t key_size, int nr_buckets)
  57 {
  58   unsigned h = 0;
  59   const char *s = (const char *) key;
  60
  61   while (key_size--)
  62     h = h * 33 + *s++;
  63
  64   return h & (nr_buckets - 1);
  65 }
  66
  67 /*----- HASHes -----*/
  68
  69 struct hash_bucket_entry
  70 {
  71   void *key;
  72   void *value;
  73 };
  74
  75 hash
  76 _hash_new (pool pool, size_t key_size, size_t value_size)
  77 {
  78   hash h;
  79   vector null = 0;
  80
  81   h = pmalloc (pool, sizeof *h);
  82   h->pool = pool;
  83   h->key_size = key_size;
  84   h->value_size = value_size;
  85   h->buckets = new_vector (pool, sizeof (vector));
  86   vector_fill (h->buckets, null, HASH_NR_BUCKETS);
  87
  88   return h;
  89 }
  90
  91 /* NB. This only copies the hash, NOT the structures or whatever
  92  * which might be pointed to by keys/values in the hash. Beware.
  93  */
  94 hash
  95 copy_hash (pool pool, hash h)
  96 {
  97   hash new_h;
  98   int b, i;
  99
 100   new_h = pmalloc (pool, sizeof *new_h);
 101   new_h->pool = pool;
 102   new_h->key_size = h->key_size;
 103   new_h->value_size = h->value_size;
 104   new_h->buckets = copy_vector (pool, h->buckets);
 105
 106   /* Copy the buckets. */
 107   for (b = 0; b < vector_size (new_h->buckets); ++b)
 108     {
 109       vector v;
 110
 111       vector_get (new_h->buckets, b, v);
 112
 113       if (v)
 114         {
 115           v = copy_vector (pool, v);
 116           vector_replace (new_h->buckets, b, v);
 117
 118           /* Copy the keys/values in this vector. */
 119           for (i = 0; i < vector_size (v); ++i)
 120             {
 121               struct hash_bucket_entry entry;
 122
 123               vector_get (v, i, entry);
 124               entry.key = pmemdup (pool, entry.key, h->key_size);
 125               entry.value = pmemdup (pool, entry.value, h->value_size);
 126               vector_replace (v, i, entry);
 127             }
 128         }
 129     }
 130
 131   return new_h;
 132 }
 133
 134 int
 135 _hash_get (hash h, const void *key, void *value)
 136 {
 137   const void *ptr;
 138
 139   ptr = _hash_get_ptr (h, key);
 140   if (ptr == 0) return 0;
 141
 142   if (value) memcpy (value, ptr, h->value_size);
 143   return 1;
 144 }
 145
 146 const void *
 147 _hash_get_ptr (hash h, const void *key)
 148 {
 149   int b, i;
 150   vector bucket;
 151
 152   /* Find the appropriate bucket. */
 153   b = HASH (key, h->key_size, vector_size (h->buckets));
 154   vector_get (h->buckets, b, bucket);
 155
 156   if (bucket == 0)
 157     return 0;
 158
 159   /* Search this bucket linearly. */
 160   for (i = 0; i < vector_size (bucket); ++i)
 161     {
 162       struct hash_bucket_entry entry;
 163
 164       vector_get (bucket, i, entry);
 165       if (memcmp (entry.key, key, h->key_size) == 0)
 166         return entry.value;
 167     }
 168
 169   return 0;
 170 }
 171
 172 int
 173 _hash_insert (hash h, const void *key, const void *value)
 174 {
 175   int b, i;
 176   vector bucket;
 177   struct hash_bucket_entry entry;
 178
 179   /* Find the appropriate bucket. */
 180   b = HASH (key, h->key_size, vector_size (h->buckets));
 181   vector_get (h->buckets, b, bucket);
 182
 183   /* If there is no bucket there, we have to allocate a fresh vector. */
 184   if (bucket == 0)
 185     {
 186       bucket = new_vector (h->pool, struct hash_bucket_entry);
 187       vector_replace (h->buckets, b, bucket);
 188     }
 189
 190   /* Search this bucket linearly. */
 191   for (i = 0; i < vector_size (bucket); ++i)
 192     {
 193       vector_get (bucket, i, entry);
 194       if (memcmp (entry.key, key, h->key_size) == 0)
 195         {
 196           memcpy (entry.value, value, h->value_size);
 197           /*entry.value = pmemdup (h->pool, value, h->value_size);*/
 198
 199           /* Replace this entry. */
 200           vector_replace (bucket, i, entry);
 201
 202           return 1;
 203         }
 204     }
 205
 206   /* Append to this bucket. */
 207   entry.key = pmemdup (h->pool, key, h->key_size);
 208   entry.value = pmemdup (h->pool, value, h->value_size);
 209
 210   vector_push_back (bucket, entry);
 211   return 0;
 212 }
 213
 214 int
 215 _hash_erase (hash h, const void *key)
 216 {
 217   int b, i;
 218   vector bucket;
 219   struct hash_bucket_entry entry;
 220
 221   /* Find the appropriate bucket. */
 222   b = HASH (key, h->key_size, vector_size (h->buckets));
 223   vector_get (h->buckets, b, bucket);
 224
 225   if (bucket == 0) return 0;
 226
 227   /* Search this bucket linearly. */
 228   for (i = 0; i < vector_size (bucket); ++i)
 229     {
 230       vector_get (bucket, i, entry);
 231       if (memcmp (entry.key, key, h->key_size) == 0)
 232         {
 233           /* Remove this entry. */
 234           vector_erase (bucket, i);
 235
 236           return 1;
 237         }
 238     }
 239
 240   return 0;
 241 }
 242
 243 inline vector
 244 hash_keys_in_pool (hash h, pool p)
 245 {
 246   int i, j;
 247   vector bucket, keys;
 248   struct hash_bucket_entry entry;
 249
 250   keys = _vector_new (p, h->key_size);
 251
 252   for (i = 0; i < vector_size (h->buckets); ++i)
 253     {
 254       vector_get (h->buckets, i, bucket);
 255
 256       if (bucket)
 257         for (j = 0; j < vector_size (bucket); ++j)
 258           {
 259             vector_get (bucket, j, entry);
 260             _vector_push_back (keys, entry.key);
 261           }
 262     }
 263
 264   return keys;
 265 }
 266
 267 vector
 268 hash_keys (hash h)
 269 {
 270   return hash_keys_in_pool (h, h->pool);
 271 }
 272
 273 inline vector
 274 hash_values_in_pool (hash h, pool p)
 275 {
 276   int i, j;
 277   vector bucket, values;
 278   struct hash_bucket_entry entry;
 279
 280   values = _vector_new (p, h->value_size);
 281
 282   for (i = 0; i < vector_size (h->buckets); ++i)
 283     {
 284       vector_get (h->buckets, i, bucket);
 285
 286       if (bucket)
 287         for (j = 0; j < vector_size (bucket); ++j)
 288           {
 289             vector_get (bucket, j, entry);
 290             _vector_push_back (values, entry.value);
 291           }
 292     }
 293
 294   return values;
 295 }
 296
 297 vector
 298 hash_values (hash h)
 299 {
 300   return hash_values_in_pool (h, h->pool);
 301 }
 302
 303 int
 304 hash_size (hash h)
 305 {
 306   vector bucket;
 307   int n = 0, i;
 308
 309   for (i = 0; i < vector_size (h->buckets); ++i)
 310     {
 311       vector_get (h->buckets, i, bucket);
 312       n += bucket ? vector_size (bucket) : 0;
 313     }
 314
 315   return n;
 316 }
 317
 318 int
 319 hash_get_buckets_used (hash h)
 320 {
 321   vector bucket;
 322   int n = 0, i;
 323
 324   for (i = 0; i < vector_size (h->buckets); ++i)
 325     {
 326       vector_get (h->buckets, i, bucket);
 327       n += bucket ? 1 : 0;
 328     }
 329
 330   return n;
 331 }
 332
 333 int
 334 hash_get_buckets_allocated (hash h)
 335 {
 336   return vector_size (h->buckets);
 337 }
 338
 339 void
 340 hash_set_buckets_allocated (hash h, int new_size)
 341 {
 342   vector null = 0;
 343
 344   /* The user has been warned not to call this after elements have been
 345    * inserted into the hash, and to make NEW_SIZE a power of 2.
 346    */
 347   if (vector_size (h->buckets) > new_size)
 348     vector_erase_range (h->buckets, new_size, vector_size (h->buckets));
 349   else if (vector_size (h->buckets) < new_size)
 350     vector_fill (h->buckets, null, new_size - vector_size (h->buckets));
 351 }
 352
 353 /*----- SASHes -----*/
 354
 355 struct sash_bucket_entry
 356 {
 357   char *key;
 358   char *value;
 359   int value_allocated;
 360 };
 361
 362 sash
 363 new_sash (pool pool)
 364 {
 365   sash h;
 366   vector null = 0;
 367
 368   h = pmalloc (pool, sizeof *h);
 369   h->pool = pool;
 370   h->buckets = new_vector (pool, sizeof (vector));
 371   vector_fill (h->buckets, null, HASH_NR_BUCKETS);
 372
 373   return h;
 374 }
 375
 376 /* NB. Unlike copy_hash, this does copy the strings into the new
 377  * pool. So a copy_sash is really a deep copy of the string hash and the
 378  * strings.
 379  */
 380 sash
 381 copy_sash (pool pool, sash h)
 382 {
 383   sash new_h;
 384   int b, i;
 385
 386   new_h = pmalloc (pool, sizeof *new_h);
 387   new_h->pool = pool;
 388   new_h->buckets = copy_vector (pool, h->buckets);
 389
 390   /* Copy the buckets. */
 391   for (b = 0; b < vector_size (new_h->buckets); ++b)
 392     {
 393       vector v;
 394
 395       vector_get (new_h->buckets, b, v);
 396
 397       if (v)
 398         {
 399           v = copy_vector (pool, v);
 400           vector_replace (new_h->buckets, b, v);
 401
 402           /* Copy the string keys/values in this vector. */
 403           for (i = 0; i < vector_size (v); ++i)
 404             {
 405               struct sash_bucket_entry entry;
 406
 407               vector_get (v, i, entry);
 408               entry.key = pstrdup (pool, entry.key);
 409               entry.value = pstrdup (pool, entry.value);
 410               vector_replace (v, i, entry);
 411             }
 412         }
 413     }
 414
 415   return new_h;
 416 }
 417
 418 int
 419 _sash_get (sash h, const char *key, const char **ptr)
 420 {
 421   int b, i;
 422   vector bucket;
 423
 424   /* Find the appropriate bucket. */
 425   b = HASH (key, strlen (key), vector_size (h->buckets));
 426   vector_get (h->buckets, b, bucket);
 427
 428   if (bucket == 0)
 429     {
 430       if (ptr) *ptr = 0;
 431       return 0;
 432     }
 433
 434   /* Search this bucket linearly. */
 435   for (i = 0; i < vector_size (bucket); ++i)
 436     {
 437       struct sash_bucket_entry entry;
 438
 439       vector_get (bucket, i, entry);
 440       if (strcmp (entry.key, key) == 0)
 441         {
 442           if (ptr) *ptr = entry.value;
 443           return 1;
 444         }
 445     }
 446
 447   if (ptr) *ptr = 0;
 448   return 0;
 449 }
 450
 451 int
 452 sash_insert (sash h, const char *key, const char *value)
 453 {
 454   int b, i, len = strlen (value);
 455   vector bucket;
 456   struct sash_bucket_entry entry;
 457
 458   /* Find the appropriate bucket. */
 459   b = HASH (key, strlen (key), vector_size (h->buckets));
 460   vector_get (h->buckets, b, bucket);
 461
 462   /* If there is no bucket there, we have to allocate a fresh vector. */
 463   if (bucket == 0)
 464     {
 465       bucket = new_vector (h->pool, struct sash_bucket_entry);
 466       vector_replace (h->buckets, b, bucket);
 467     }
 468
 469   /* Search this bucket linearly. */
 470   for (i = 0; i < vector_size (bucket); ++i)
 471     {
 472       vector_get (bucket, i, entry);
 473       if (strcmp (entry.key, key) == 0)
 474         {
 475           /* To avoid unnecessarily allocating more memory, we try to
 476            * be clever here. If the existing allocation is large enough
 477            * to store the new string, use it. Otherwise reallocate it
 478            * to make it bigger.
 479            */
 480           if (len < entry.value_allocated)
 481             memcpy (entry.value, value, len + 1);
 482           else
 483             {
 484               entry.value = prealloc (h->pool, entry.value, len + 1);
 485               memcpy (entry.value, value, len + 1);
 486               entry.value_allocated = len + 1;
 487             }
 488
 489           /* Replace this entry. */
 490           vector_replace (bucket, i, entry);
 491
 492           return 1;
 493         }
 494     }
 495
 496   /* Append to this bucket. */
 497   entry.key = pstrdup (h->pool, key);
 498   entry.value = pstrdup (h->pool, value);
 499   entry.value_allocated = len + 1;
 500
 501   vector_push_back (bucket, entry);
 502   return 0;
 503 }
 504
 505 int
 506 sash_erase (sash h, const char *key)
 507 {
 508   int b, i;
 509   vector bucket;
 510   struct sash_bucket_entry entry;
 511
 512   /* Find the appropriate bucket. */
 513   b = HASH (key, strlen (key), vector_size (h->buckets));
 514   vector_get (h->buckets, b, bucket);
 515
 516   if (bucket == 0) return 0;
 517
 518   /* Search this bucket linearly. */
 519   for (i = 0; i < vector_size (bucket); ++i)
 520     {
 521       vector_get (bucket, i, entry);
 522       if (strcmp (entry.key, key) == 0)
 523         {
 524           /* Remove this entry. */
 525           vector_erase (bucket, i);
 526
 527           return 1;
 528         }
 529     }
 530
 531   return 0;
 532 }
 533
 534 inline vector
 535 sash_keys_in_pool (sash h, pool p)
 536 {
 537   int i, j;
 538   vector bucket, keys;
 539   struct sash_bucket_entry entry;
 540
 541   keys = new_vector (p, char *);
 542
 543   for (i = 0; i < vector_size (h->buckets); ++i)
 544     {
 545       vector_get (h->buckets, i, bucket);
 546
 547       if (bucket)
 548         for (j = 0; j < vector_size (bucket); ++j)
 549           {
 550             char *key;
 551
 552             vector_get (bucket, j, entry);
 553             key = pstrdup (p, entry.key);
 554             vector_push_back (keys, key);
 555           }
 556     }
 557
 558   return keys;
 559 }
 560
 561 vector
 562 sash_keys (sash h)
 563 {
 564   return sash_keys_in_pool (h, h->pool);
 565 }
 566
 567 inline vector
 568 sash_values_in_pool (sash h, pool p)
 569 {
 570   int i, j;
 571   vector bucket, values;
 572   struct sash_bucket_entry entry;
 573
 574   values = new_vector (p, char *);
 575
 576   for (i = 0; i < vector_size (h->buckets); ++i)
 577     {
 578       vector_get (h->buckets, i, bucket);
 579
 580       if (bucket)
 581         for (j = 0; j < vector_size (bucket); ++j)
 582           {
 583             char *value;
 584
 585             vector_get (bucket, j, entry);
 586             value = pstrdup (p, entry.value);
 587             vector_push_back (values, value);
 588           }
 589     }
 590
 591   return values;
 592 }
 593
 594 vector
 595 sash_values (sash h)
 596 {
 597   return sash_values_in_pool (h, h->pool);
 598 }
 599
 600 int
 601 sash_size (sash h)
 602 {
 603   vector bucket;
 604   int n = 0, i;
 605
 606   for (i = 0; i < vector_size (h->buckets); ++i)
 607     {
 608       vector_get (h->buckets, i, bucket);
 609       n += bucket ? vector_size (bucket) : 0;
 610     }
 611
 612   return n;
 613 }
 614
 615 int
 616 sash_get_buckets_used (sash h)
 617 {
 618   vector bucket;
 619   int n = 0, i;
 620
 621   for (i = 0; i < vector_size (h->buckets); ++i)
 622     {
 623       vector_get (h->buckets, i, bucket);
 624       n += bucket ? 1 : 0;
 625     }
 626
 627   return n;
 628 }
 629
 630 int
 631 sash_get_buckets_allocated (sash h)
 632 {
 633   return vector_size (h->buckets);
 634 }
 635
 636 void
 637 sash_set_buckets_allocated (sash h, int new_size)
 638 {
 639   vector null = 0;
 640
 641   /* The user has been warned not to call this after elements have been
 642    * inserted into the sash, and to make NEW_SIZE a power of 2.
 643    */
 644   if (vector_size (h->buckets) > new_size)
 645     vector_erase_range (h->buckets, new_size, vector_size (h->buckets));
 646   else if (vector_size (h->buckets) < new_size)
 647     vector_fill (h->buckets, null, new_size - vector_size (h->buckets));
 648 }
 649
 650 /*----- SHASHes -----*/
 651
 652 struct shash_bucket_entry
 653 {
 654   char *key;
 655   void *value;
 656 };
 657
 658 shash
 659 _shash_new (pool pool, size_t value_size)
 660 {
 661   shash h;
 662   vector null = 0;
 663
 664   h = pmalloc (pool, sizeof *h);
 665   h->pool = pool;
 666   h->value_size = value_size;
 667   h->buckets = new_vector (pool, sizeof (vector));
 668   vector_fill (h->buckets, null, HASH_NR_BUCKETS);
 669
 670   return h;
 671 }
 672
 673 /* NB. Unlike copy_hash, this does copy the strings into the new
 674  * pool. So a copy_shash is really a deep copy of the shash and the
 675  * strings.
 676  */
 677 shash
 678 copy_shash (pool pool, shash h)
 679 {
 680   shash new_h;
 681   int b, i;
 682
 683   new_h = pmalloc (pool, sizeof *new_h);
 684   new_h->pool = pool;
 685   new_h->value_size = h->value_size;
 686   new_h->buckets = copy_vector (pool, h->buckets);
 687
 688   /* Copy the buckets. */
 689   for (b = 0; b < vector_size (new_h->buckets); ++b)
 690     {
 691       vector v;
 692
 693       vector_get (new_h->buckets, b, v);
 694
 695       if (v)
 696         {
 697           v = copy_vector (pool, v);
 698           vector_replace (new_h->buckets, b, v);
 699
 700           /* Copy the string keys in this vector. */
 701           for (i = 0; i < vector_size (v); ++i)
 702             {
 703               struct shash_bucket_entry entry;
 704
 705               vector_get (v, i, entry);
 706               entry.key = pstrdup (pool, entry.key);
 707               entry.value = pmemdup (pool, entry.value, h->value_size);
 708               vector_replace (v, i, entry);
 709             }
 710         }
 711     }
 712
 713   return new_h;
 714 }
 715
 716 int
 717 _shash_get (shash h, const char *key, void *value)
 718 {
 719   const void *ptr;
 720
 721   ptr = _shash_get_ptr (h, key);
 722   if (ptr == 0) return 0;
 723
 724   if (value) memcpy (value, ptr, h->value_size);
 725   return 1;
 726 }
 727
 728 const void *
 729 _shash_get_ptr (shash h, const char *key)
 730 {
 731   int b, i;
 732   vector bucket;
 733
 734   /* Find the appropriate bucket. */
 735   b = HASH (key, strlen (key), vector_size (h->buckets));
 736   vector_get (h->buckets, b, bucket);
 737
 738   if (bucket == 0)
 739     return 0;
 740
 741   /* Search this bucket linearly. */
 742   for (i = 0; i < vector_size (bucket); ++i)
 743     {
 744       struct shash_bucket_entry entry;
 745
 746       vector_get (bucket, i, entry);
 747       if (strcmp (entry.key, key) == 0)
 748         return entry.value;
 749     }
 750
 751   return 0;
 752 }
 753
 754 int
 755 _shash_insert (shash h, const char *key, const void *value)
 756 {
 757   int b, i;
 758   vector bucket;
 759   struct shash_bucket_entry entry;
 760
 761   /* Find the appropriate bucket. */
 762   b = HASH (key, strlen (key), vector_size (h->buckets));
 763   vector_get (h->buckets, b, bucket);
 764
 765   /* If there is no bucket there, we have to allocate a fresh vector. */
 766   if (bucket == 0)
 767     {
 768       bucket = new_vector (h->pool, struct shash_bucket_entry);
 769       vector_replace (h->buckets, b, bucket);
 770     }
 771
 772   /* Search this bucket linearly. */
 773   for (i = 0; i < vector_size (bucket); ++i)
 774     {
 775       vector_get (bucket, i, entry);
 776       if (strcmp (entry.key, key) == 0)
 777         {
 778           memcpy (entry.value, value, h->value_size);
 779           /*entry.value = pmemdup (h->pool, value, h->value_size);*/
 780
 781           /* Replace this entry. */
 782           vector_replace (bucket, i, entry);
 783
 784           return 1;
 785         }
 786     }
 787
 788   /* Append to this bucket. */
 789   entry.key = pstrdup (h->pool, key);
 790   entry.value = pmemdup (h->pool, value, h->value_size);
 791
 792   vector_push_back (bucket, entry);
 793   return 0;
 794 }
 795
 796 int
 797 shash_erase (shash h, const char *key)
 798 {
 799   int b, i;
 800   vector bucket;
 801   struct shash_bucket_entry entry;
 802
 803   /* Find the appropriate bucket. */
 804   b = HASH (key, strlen (key), vector_size (h->buckets));
 805   vector_get (h->buckets, b, bucket);
 806
 807   if (bucket == 0) return 0;
 808
 809   /* Search this bucket linearly. */
 810   for (i = 0; i < vector_size (bucket); ++i)
 811     {
 812       vector_get (bucket, i, entry);
 813       if (strcmp (entry.key, key) == 0)
 814         {
 815           /* Remove this entry. */
 816           vector_erase (bucket, i);
 817
 818           return 1;
 819         }
 820     }
 821
 822   return 0;
 823 }
 824
 825 inline vector
 826 shash_keys_in_pool (shash h, pool p)
 827 {
 828   int i, j;
 829   vector bucket, keys;
 830   struct shash_bucket_entry entry;
 831
 832   keys = new_vector (p, char *);
 833
 834   for (i = 0; i < vector_size (h->buckets); ++i)
 835     {
 836       vector_get (h->buckets, i, bucket);
 837
 838       if (bucket)
 839         for (j = 0; j < vector_size (bucket); ++j)
 840           {
 841             char *key;
 842
 843             vector_get (bucket, j, entry);
 844             key = pstrdup (p, entry.key);
 845             vector_push_back (keys, key);
 846           }
 847     }
 848
 849   return keys;
 850 }
 851
 852 vector
 853 shash_keys (shash h)
 854 {
 855   return shash_keys_in_pool (h, h->pool);
 856 }
 857
 858 inline vector
 859 shash_values_in_pool (shash h, pool p)
 860 {
 861   int i, j;
 862   vector bucket, values;
 863   struct shash_bucket_entry entry;
 864
 865   values = _vector_new (p, h->value_size);
 866
 867   for (i = 0; i < vector_size (h->buckets); ++i)
 868     {
 869       vector_get (h->buckets, i, bucket);
 870
 871       if (bucket)
 872         for (j = 0; j < vector_size (bucket); ++j)
 873           {
 874             vector_get (bucket, j, entry);
 875             _vector_push_back (values, entry.value);
 876           }
 877     }
 878
 879   return values;
 880 }
 881
 882 vector
 883 shash_values (shash h)
 884 {
 885   return shash_values_in_pool (h, h->pool);
 886 }
 887
 888 int
 889 shash_size (shash h)
 890 {
 891   vector bucket;
 892   int n = 0, i;
 893
 894   for (i = 0; i < vector_size (h->buckets); ++i)
 895     {
 896       vector_get (h->buckets, i, bucket);
 897       n += bucket ? vector_size (bucket) : 0;
 898     }
 899
 900   return n;
 901 }
 902
 903 int
 904 shash_get_buckets_used (shash h)
 905 {
 906   vector bucket;
 907   int n = 0, i;
 908
 909   for (i = 0; i < vector_size (h->buckets); ++i)
 910     {
 911       vector_get (h->buckets, i, bucket);
 912       n += bucket ? 1 : 0;
 913     }
 914
 915   return n;
 916 }
 917
 918 int
 919 shash_get_buckets_allocated (shash h)
 920 {
 921   return vector_size (h->buckets);
 922 }
 923
 924 void
 925 shash_set_buckets_allocated (shash h, int new_size)
 926 {
 927   vector null = 0;
 928
 929   /* The user has been warned not to call this after elements have been
 930    * inserted into the shash, and to make NEW_SIZE a power of 2.
 931    */
 932   if (vector_size (h->buckets) > new_size)
 933     vector_erase_range (h->buckets, new_size, vector_size (h->buckets));
 934   else if (vector_size (h->buckets) < new_size)
 935     vector_fill (h->buckets, null, new_size - vector_size (h->buckets));
 936 }