PennMUSH Community

Changeset 1051

Show
Ignore:
Timestamp:
07/15/07 11:03:05 (1 year ago)
Author:
shawnw
Message:

New hashtable code

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved

  • 1.8.3/branches/devel/CHANGES.183

    r1049 r1051  
    2020 * Store a pointer to the start of a player's mailbox in objdata 
    2121   instead of the connection struct. 
     22 * Experimental rewrite of hash tables to use the cuckoo hashing 
     23   algorithm, with constant-time lookups even in the worst case. 
     24   (And appears to have generally faster lookup even in normal usage.) 
    2225 
    2326Fixes: 

  • 1.8.3/branches/devel/hdrs/htab.h

    r961 r1051  
    44#define __HTAB_H 
    55 
     6typedef struct hashtable HASHTAB; 
    67 
    7 #define HTAB_UPSCALE   3.25 
    8 #define HTAB_DOWNSCALE 2.0 
    9  
    10 typedef struct hashentry HASHENT; 
    11 /** A hash table entry. 
    12  */ 
    13 struct hashentry { 
    14   struct hashentry *next;       /**< Pointer to next entry */ 
    15   void *data;                   /**< Data for this entry */ 
    16   char *key;                    /**< Key for this entry */ 
     8/** Hash table bucket struct */ 
     9struct hash_bucket { 
     10  const char *key; 
     11  void *data; 
    1712}; 
    1813 
    19 #define HASHENT_SIZE (sizeof(HASHENT)) 
    20  
    21 typedef struct hashtable HASHTAB; 
    2214/** A hash table. 
    2315 */ 
    2416struct hashtable { 
    25   int hashsize;                 /**< Size of hash table */ 
    26   int mask;                     /**< Mask for entries in table */ 
     17  int hashsize;                 /**< Size of buckets array */ 
    2718  int entries;                  /**< Number of entries stored */ 
    28   HASHENT **buckets;            /**< Pointer to pointer to entries */ 
    29   int last_hval;                /**< State for hashfirst & hashnext. */ 
    30   HASHENT *last_entry;          /**< State for hashfirst & hashnext. */ 
    31   int entry_size;               /**< Size of each entry */ 
     19  int hashfunc_offset;          /**< Which pair of hash functions to use */ 
     20  struct hash_bucket *buckets;  /**< Buckets */ 
     21  int last_index;              /**< State for hashfirst & hashnext. */ 
    3222  void (*free_data) (void *);   /**< Function to call on data when deleting 
    3323                                   a entry. */ 
    3424}; 
    3525 
    36 #define get_hashmask(x) hash_getmask(x) 
    37 #define hashinit(x,y, z) hash_init(x,y, z, NULL) 
     26typedef struct hash_bucket HASHENT; 
     27 
     28#define hashinit(tab, size) hash_init((tab), (size), NULL) 
    3829#define hashfind(key,tab) hash_value(hash_find(tab,key)) 
    39 #define hashadd(key,data,tab) hash_add(tab,key,data, 0) 
    40 #define hashadds(key, data, tab, size) hash_add(tab, key, data, size) 
     30#define hashadd(key,data,tab) hash_add(tab,key,data) 
    4131#define hashdelete(key,tab) hash_delete(tab,hash_find(tab,key)) 
    4232#define hashflush(tab, size) hash_flush(tab,size) 
    4333#define hashfree(tab) hash_flush(tab, 0) 
    44 extern int hash_getmask(int *size); 
    45 extern void hash_init(HASHTAB *htab, int size, int data_size, void (*)(void *)); 
    46 extern HASHENT *hash_find(HASHTAB *htab, const char *key); 
    47 extern void *hash_value(HASHENT *entry); 
    48 extern char *hash_key(HASHENT *entry); 
    49 extern void hash_resize(HASHTAB *htab, int size); 
    50 extern int hash_add 
    51   (HASHTAB *htab, const char *key, void *hashdata, int extra_size); 
    52 extern void hash_delete(HASHTAB *htab, HASHENT *entry); 
    53 extern void hash_flush(HASHTAB *htab, int size); 
    54 extern void *hash_firstentry(HASHTAB *htab); 
    55 extern void *hash_nextentry(HASHTAB *htab); 
    56 extern char *hash_firstentry_key(HASHTAB *htab); 
    57 extern char *hash_nextentry_key(HASHTAB *htab); 
    58 extern void hash_stats_header(dbref player); 
    59 extern void hash_stats(dbref player, HASHTAB *htab, const char *hashname); 
     34int hash_getmask(int *size); 
     35void hash_init(HASHTAB *htab, int size, void (*)(void *)); 
     36HASHENT *hash_find(HASHTAB *htab, const char *key); 
     37#define hash_value(entry) (entry) ? (entry)->data : NULL 
     38#define hash_key(entry) (entry) ? (entry)->key : NULL 
     39bool hash_resize(HASHTAB *htab, int size); 
     40bool hash_add(HASHTAB *htab, const char *key, void *hashdata); 
     41void hash_delete(HASHTAB *htab, HASHENT *entry); 
     42void hash_flush(HASHTAB *htab, int size); 
     43void *hash_firstentry(HASHTAB *htab); 
     44void *hash_nextentry(HASHTAB *htab); 
     45const char *hash_firstentry_key(HASHTAB *htab); 
     46const char *hash_nextentry_key(HASHTAB *htab); 
     47void hash_stats_header(dbref player); 
     48void hash_stats(dbref player, HASHTAB *htab, const char *hashname); 
    6049#endif 

  • 1.8.3/branches/devel/src/bsd.c

    r1049 r1051  
    16001600        && !d->ssl 
    16011601#endif 
    1602         ) { 
     1602      ) { 
    16031603      /* If there's more than one pending block, try to send up to 10 
    16041604         at once with writev(). Doesn't work for SSL connections, and 

  • 1.8.3/branches/devel/src/command.c

    r964 r1051  
    636636 
    637637  ptab_init(&ptab_command); 
    638   hashinit(&htab_reserved_aliases, 16, sizeof(COMMAND_INFO)); 
     638  hashinit(&htab_reserved_aliases, 16); 
    639639  command_slab = slab_create("commands", sizeof(COMMAND_INFO)); 
    640640  reserve_aliases(); 

  • 1.8.3/branches/devel/src/db.c

    r935 r1051  
    18021802init_objdata_htab(int size, void (*free_data) (void *)) 
    18031803{ 
    1804   if (size < 128) 
    1805     size = 128; 
    1806   hash_init(&htab_objdata, size, 4, free_data); 
    1807   hashinit(&htab_objdata_keys, 8, 32); 
     1804  if (size < 10) 
     1805    size = 10; 
     1806  hash_init(&htab_objdata, size, free_data); 
     1807  hashinit(&htab_objdata_keys, 8); 
    18081808} 
    18091809 
    …… 
    18291829  hashdelete(keyname, &htab_objdata); 
    18301830  if (data) { 
    1831     if (hashadd(keyname, data, &htab_objdata) < 0) 
     1831    if (!hashadd(keyname, data, &htab_objdata)) 
    18321832      return NULL; 
    18331833    if (hash_find(&htab_objdata_keys, keybase) == NULL) { 

  • 1.8.3/branches/devel/src/flags.c

    r960 r1051  
    798798  FLAGSPACE *flags; 
    799799 
    800   hashinit(&htab_flagspaces, 4, sizeof(FLAGSPACE)); 
    801   flags = (FLAGSPACE *) mush_malloc(sizeof(FLAGSPACE), "flagspace"); 
     800  hashinit(&htab_flagspaces, 4); 
     801  flags = mush_malloc(sizeof(FLAGSPACE), "flagspace"); 
    802802  flags->name = strdup("FLAG"); 
    803803  flags->tab = &ptab_flag; 

  • 1.8.3/branches/devel/src/function.c

    r1003 r1051  
    890890  FUNTAB *ftp; 
    891891 
    892   hashinit(&htab_function, 512, sizeof(FUN)); 
    893   hash_init(&htab_user_function, 32, sizeof(FUN), delete_function); 
     892  hashinit(&htab_function, 512); 
     893  hash_init(&htab_user_function, 32, delete_function); 
    894894  function_slab = slab_create("functions", sizeof(FUN)); 
    895895  for (ftp = flist; ftp->name; ftp++) { 

  • 1.8.3/branches/devel/src/game.c

    r1007 r1051  
    691691  pid_t mypid = -1; 
    692692 
     693  /* initialize random number generator */ 
     694  initialize_mt(); 
     695 
    693696  init_queue(); 
    694697 
    …… 
    757760  /* access file stuff */ 
    758761  read_access_file(); 
    759   /* initialize random number generator */ 
    760   initialize_mt(); 
    761762  /* set up signal handlers for the timer */ 
    762763  init_timer(); 
    …… 
    23312332extern HASHTAB htab_objdata_keys; 
    23322333extern HASHTAB htab_locks; 
     2334extern HASHTAB local_options; 
    23332335extern StrTree atr_names; 
    23342336extern StrTree lock_names; 
    …… 
    23542356  hash_stats(player, &htab_objdata_keys, "ObjDataKeys"); 
    23552357  hash_stats(player, &htab_locks, "@locks"); 
     2358  hash_stats(player, &local_options, "ConfigOpts"); 
    23562359  notify(player, "Prefix Trees:"); 
    23572360  ptab_stats_header(player); 

  • 1.8.3/branches/devel/src/help.c

    r964 r1051  
    8181init_help_files(void) 
    8282{ 
    83   hash_init(&help_files, 8, sizeof(help_file), NULL); 
     83  hashinit(&help_files, 8); 
    8484  help_init = 1; 
    8585} 

  • 1.8.3/branches/devel/src/htab.c

    r967 r1051  
    33 * 
    44 * \brief Hashtable routines. 
    5  * This code is largely ripped out of TinyMUSH 2.2.5, with tweaks 
    6  * to make it Penn-compatible by Trivian. 
    7  * 
    8  * 
     5 * 
     6 * The hash tables here implement open addressing using cuckoo hashing 
     7 * to resolve collisions. This gives an O(1) worse-case performance 
     8 * (As well as best, of course), compared to the worst-case O(N) of 
     9 * chained or linear probing tables. 
     10 *  
     11 * A lookup will require at most X hash functions and string 
     12 * comparisions.  The old tables had, with data used by Penn, 1 hash 
     13 * function and up to 6 or 7 comparisions in the worst case. Best case 
     14 * for both is 1 hash and 1 comparision. Cuckoo hashing comes out 
     15 * ahead when most lookups are successful; true for normal usage in 
     16 * Penn. 
     17 * 
     18 * Insertions are more expensive, but that's okay because we do a lot 
     19 * fewer of those. 
     20 * 
     21 * For details on the technique, see 
     22 * http://citeseer.ist.psu.edu/pagh01cuckoo.html 
     23 * 
     24 * Essentially: Use X hash functions (3 for us), and when inserting, 
     25 * try them in order looking for an empty bucket. If none are found, 
     26 * use one of the full buckets for the new entry, and bump the old one 
     27 * to another one of its possible buckets. Repeat the bumping some 
     28 * bounded number of times (Otherwise the possiblity of an infinite 
     29 * loop arises), and if no empty buckets are found, try rehashing the 
     30 * entire table with a new set of hash functions. If those are 
     31 * exhausted, only then grow the table. 
     32 * 
     33 * Possible to-do: Switch the string tree implementation from using 
     34 * red-black trees to these tables. Talek choose binary trees over 
     35 * hash tables when writing strtree.c because of the better worst-case 
     36 * behavior, which was a good decision at the time. However, O(1) is 
     37 * better than O(log N). 
     38 * 
     39 * At the moment, though, insertions can be fairly costly. The growth 
     40 * factor should be able to be specified -- large for cases where fast 
     41 * inserts are important, small for cases where we want to save save. 
    942 */ 
    1043 
    …… 
    1245#include "copyrite.h" 
    1346#include <string.h> 
     47#include <math.h> 
    1448#ifdef HAVE_STDINT_H 
    1549#include <stdint.h> 
    …… 
    2256#include "confmagic.h" 
    2357 
    24 static HASHENT *hash_new(HASHTAB *htab, const char *key); 
    25 static int hash_val(register const char *k, int mask); 
    26  
    27 /* --------------------------------------------------------------------------- 
    28  * hash_val: Compute hash value of a string for a hash table. 
    29  */ 
    30 /*#define NEW_HASH_FUN /**/ 
    31 #ifdef NEW_HASH_FUN 
    32  
    33 /* This hash function adapted from http://burtleburtle.net/bob/hash/evahash.html */ 
     58/* The Jenkins hash:  http://burtleburtle.net/bob/hash/evahash.html */ 
    3459 
    3560/* The mixing step */ 
    …… 
    4873 
    4974/* The whole new hash function */ 
    50 static int 
    51 hash_val(const char *k, int mask) 
     75static uint32_t 
     76jenkins_hash(const char *k, int len) 
    5277{ 
    5378  uint32_t a, b, c;             /* the internal state */ 
    54   uint32_t len, length;         /* how many key bytes still need mixing */ 
     79  uint32_t length;              /* how many key bytes still need mixing */ 
    5580  static uint32_t initval = 5432;       /* the previous hash, or an arbitrary value */ 
    5681 
    5782  /* Set up the internal state */ 
    58   length = len = strlen(k); 
     83  length = len; 
    5984  a = b = 0x9e3779b9;           /* the golden ratio; an arbitrary value */ 
    6085  c = initval;                  /* variable initialization of internal state */ 
    …… 
    106131  mix(a, b, c); 
    107132   /*-------------------------------------------- report the result */ 
    108   return c & mask; 
    109 } 
    110  
    111  
    112 #else                           /* NEW_HASH_FUN */ 
    113 /** Compute a hash value for mask-style hashing. 
    114  * Given a null key, return 0. Otherwise, add up the numeric value 
    115  * of all the characters and return the sum modulo the size of the 
    116  * hash table. 
    117  * \param key key to hash. 
    118  * \param hashmask hash table size to use as modulus. 
    119  * \return hash value. 
    120  */ 
    121 int 
    122 hash_val(const char *key, int hashmask) 
    123 { 
    124   int hash = 0; 
    125   const char *sp; 
    126  
    127   if (!key || !*key) 
     133  return c; 
     134} 
     135 
     136 
     137/* The Hsieh hash function. See 
     138   http://www.azillionmonkeys.com/qed/hash.html */ 
     139 
     140#undef get16bits 
     141#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \ 
     142  || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__) 
     143#define get16bits(d) (*((const uint16_t *) (d))) 
     144#endif 
     145 
     146#if !defined (get16bits) 
     147#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\ 
     148                       +(uint32_t)(((const uint8_t *)(d))[0]) ) 
     149#endif 
     150 
     151static uint32_t 
     152hsieh_hash(const char *data, int len) 
     153{ 
     154  uint32_t hash, tmp; 
     155  int rem; 
     156 
     157  hash = len; 
     158 
     159  if (len <= 0 || data == NULL) 
    128160    return 0; 
    129   for (sp = key; *sp; sp++) 
    130     hash = (hash << 5) + hash + *sp; 
    131   return (hash & hashmask); 
    132 } 
    133 #endif                          /* NEW_HASH_FUN */ 
    134  
    135 /* ---------------------------------------------------------------------- 
    136  * hash_getmask: Get hash mask for mask-style hashing. 
    137  */ 
    138  
    139 /** Get the hash mask for mask-style hashing. 
    140  * Given the data size, return closest power-of-two less than that size. 
    141  * \param size data size. 
    142  * \return hash mask. 
    143  */ 
    144 int 
    145 hash_getmask(int *size) 
    146 { 
    147   int tsize; 
    148  
    149   if (!size || !*size) 
     161 
     162  rem = len & 3; 
     163  len >>= 2; 
     164 
     165  /* Main loop */ 
     166  for (; len > 0; len--) { 
     167    hash += get16bits(data); 
     168    tmp = (get16bits(data + 2) << 11) ^ hash; 
     169    hash = (hash << 16) ^ tmp; 
     170    data += 2 * sizeof(uint16_t); 
     171    hash += hash >> 11; 
     172  } 
     173 
     174  /* Handle end cases */ 
     175  switch (rem) { 
     176  case 3: 
     177    hash += get16bits(data); 
     178    hash ^= hash << 16; 
     179    hash ^= data[sizeof(uint16_t)] << 18; 
     180    hash += hash >> 11; 
     181    break; 
     182  case 2: 
     183    hash += get16bits(data); 
     184    hash ^= hash << 11; 
     185    hash += hash >> 17; 
     186    break; 
     187  case 1: 
     188    hash += *data; 
     189    hash ^= hash << 10; 
     190    hash += hash >> 1; 
     191  } 
     192 
     193  /* Force "avalanching" of final 127 bits */ 
     194  hash ^= hash << 3; 
     195  hash += hash >> 5; 
     196  hash ^= hash << 4; 
     197  hash += hash >> 17; 
     198  hash ^= hash << 25; 
     199  hash += hash >> 6; 
     200 
     201  return hash; 
     202} 
     203 
     204/* FNV hash: http://isthe.com/chongo/tech/comp/fnv/ */ 
     205/* 
     206 * fnv_32_str - perform a 32 bit Fowler/Noll/Vo hash on a string 
     207 * 
     208 * input: 
     209 *  str - string to hash 
     210 *  hval    - previous hash value or 0 if first call 
     211 * 
     212 * returns: 
     213 *  32 bit hash as a static hash type 
     214 * 
     215 * NOTE: To use the 32 bit FNV-0 historic hash, use FNV0_32_INIT as the hval 
     216 *   argument on the first call to either fnv_32_buf() or fnv_32_str(). 
     217 * 
     218 * NOTE: To use the recommended 32 bit FNV-1 hash, use FNV1_32_INIT as the hval 
     219 *   argument on the first call to either fnv_32_buf() or fnv_32_str(). 
     220 * 
     221 * Modified by Raevnos: Takes length arg, no hval arg, and does array-style 
     222 * iteration of the string. 
     223 */ 
     224#define FNV_32_PRIME ((Fnv32_t)0x01000193) 
     225static inline uint32_t 
     226fnv_hash(const char *str, int len) 
     227{ 
     228  const unsigned char *s = (const unsigned char *) str; 
     229  int n; 
     230  uint32_t hval = 0; 
     231 
     232  /* 
     233   * FNV-1 hash each octet in the buffer 
     234   */ 
     235  for (n = 0; n < len; n++) { 
     236 
     237    /* multiply by the 32 bit FNV magic prime mod 2^32 */ 
     238#if defined(NO_FNV_GCC_OPTIMIZATION) 
     239    hval *= FNV_32_PRIME; 
     240#else 
     241    hval += 
     242      (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24); 
     243#endif 
     244 
     245    /* xor the bottom with the current octet */ 
     246    hval ^= (uint32_t) s[n]; 
     247  } 
     248 
     249  /* return our new hash value */ 
     250  return hval; 
     251} 
     252 
     253/* Silly old Penn hash function. */ 
     254static uint32_t 
     255penn_hash(const char *key, int len) 
     256{ 
     257  uint32_t hash = 0; 
     258  int n; 
     259 
     260  if (!key || !*key || len == 0) 
    150261    return 0; 
    151  
    152   for (tsize = 1; tsize < *size; tsize = tsize << 1) ; 
    153   *size = tsize; 
    154   return tsize - 1; 
     262  for (n = 0; n < len; n++) 
     263    hash = (hash << 5) + hash + key[n]; 
     264  return hash; 
     265} 
     266 
     267typedef uint32_t(*hash_func) (const char *, int); 
     268 
     269hash_func hash_functions[] = { 
     270  hsieh_hash, 
     271  fnv_hash, 
     272  jenkins_hash, 
     273  penn_hash, 
     274  hsieh_hash, 
     275  fnv_hash, 
     276  penn_hash, 
     277  jenkins_hash 
     278}; 
     279 
     280enum { NHASH_TRIES = 3, NHASH_MOD = 8 }; 
     281 
     282/* Return the next prime number after its arg */ 
     283static int 
     284next_prime_after(int val) 
     285{ 
     286  /* Most of the first thousand primes */ 
     287  static int primes[] = { 
     288    7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 
     289    83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 
     290    163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 
     291    241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 
     292    337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 
     293    431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 
     294    521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 
     295    617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 
     296    719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 
     297    823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 
     298    929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 
     299    1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 
     300    1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 
     301    1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 
     302    1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 
     303    1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 
     304    1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 
     305    1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 
     306    1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 
     307    1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 
     308    1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 
     309    1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 
     310    2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 
     311    2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 
     312    2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 
     313    2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 
     314    2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 
     315    2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 
     316    2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 
     317    2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 
     318    2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 
     319    2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 
     320    2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 
     321    3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 
     322    3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 
     323    3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 
     324    3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 
     325    3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 
     326    3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 
     327    3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 
     328    3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 
     329    3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 
     330    3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 
     331    4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 
     332    4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 
     333    4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 
     334    4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 
     335    4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 
     336    4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 
     337    4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 
     338    4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 
     339    4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 
     340    4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 
     341    5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 
     342    5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 
     343    5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 
     344    5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 
     345    5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 
     346    5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 
     347    5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 
     348    5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 
     349    5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 
     350    6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 
     351    6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 
     352    6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 
     353    6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 
     354    6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 
     355    6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 
     356    6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 
     357    6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 
     358    6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 
     359    6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 
     360    7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 
     361    7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 
     362    7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 
     363    7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 
     364    7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 
     365    7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 
     366    7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 
     367    7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 
     368    7919, -1 
     369  }; 
     370  int n; 
     371  int nprimes = sizeof primes / sizeof(int); 
     372 
     373  /* Find the first prime greater than val */ 
     374  primes[nprimes - 1] = val + 1; 
     375  n = 0; 
     376  while (primes[n] < val) 
     377    n += 1; 
     378 
     379  n += 1; 
     380  if (n == nprimes) 
     381    /* Semi-gracefully deal with numbers larger than the table has. 
     382       Should never happen, though. */ 
     383    return val + 1; 
     384  else 
     385    return primes[n]; 
    155386} 
    156387 
    …… 
    161392 */ 
    162393void 
    163 hash_init(HASHTAB *htab, int size, int data_size, void (*free_data) (void *)) 
    164 { 
    165   htab->mask = get_hashmask(&size); 
     394hash_init(HASHTAB *htab, int size, void (*free_data) (void *)) 
     395{ 
     396  size = next_prime_after(size); 
     397  htab->last_index = -1; 
     398  htab->free_data = free_data; 
    166399  htab->hashsize = size; 
    167   htab->entries = 0; 
    168   htab->buckets = mush_calloc(size, sizeof(HASHENT *), "hash_buckets"); 
    169   htab->entry_size = data_size; 
    170   htab->free_data = free_data; 
     400  htab->hashfunc_offset = 0; 
     401  htab->buckets = mush_calloc(size, sizeof(struct hash_bucket), "hash.buckets"); 
    171402} 
    172403 
    …… 
    179410hash_find(HASHTAB *htab, const char *key) 
    180411{ 
    181   int hval, cmp; 
    182   HASHENT *hptr; 
    183  
    184   if (!htab->buckets) 
     412  int len, n; 
     413 
     414  if (!htab->entries) 
    185415    return NULL; 
    186416 
    187   hval = hash_val(key, htab->mask); 
    188   for (hptr = htab->buckets[hval]; hptr != NULL; hptr = hptr->next) { 
    189     cmp = strcmp(key, hptr->key); 
    190     if (cmp == 0) { 
    191       return hptr; 
    192     } else if (cmp < 0) 
    193       break; 
    194   } 
     417  len = strlen(key); 
     418 
     419  for (n = 0; n < NHASH_TRIES; n++) { 
     420    hash_func hash; 
     421    int hval, hashindex = (n + htab->hashfunc_offset) % NHASH_MOD; 
     422    hash = hash_functions[hashindex]; 
     423    hval = hash(key, len) % htab->hashsize; 
     424 
     425    if (htab->buckets[hval].key && strcmp(htab->buckets[hval].key, key) == 0) 
     426      return htab->buckets + hval; 
     427  } 
     428 
    195429  return NULL; 
    196430} 
    197431 
    198 /** Return the value stored in a hash entry. 
    199  * \param entry pointer to a hash table entry. 
    200  * \return generic pointer to the stored value. 
    201  */ 
    202 void * 
    203 hash_value(HASHENT *entry) 
    204 { 
    205   if (entry) 
    206     return entry->data; 
    207   else 
    208     return NULL; 
    209 } 
    210  
    211 /** Return the key stored in a hash entry. 
    212  * \param entry pointer to a hash table entry. 
    213  * \return pointer to the stored key. 
    214  */ 
    215 char * 
    216 hash_key(HASHENT *entry) 
    217 { 
    218   if (entry) 
    219     return entry->key; 
    220   else 
    221     return NULL; 
     432enum { BUMP_LIMIT = 10 }; 
     433 
     434/** Do cuckoo hash cycling */ 
     435static bool 
     436hash_insert(HASHTAB *htab, const char *key, void  *data) 
     437{ 
     438  int loop = 0, n; 
     439  struct hash_bucket bump; 
     440 
     441  bump.key = key; 
     442  bump.data = data; 
     443 
     444  while (loop < BUMP_LIMIT) { 
     445    int hval, keylen; 
     446    struct hash_bucket temp; 
     447 
     448    keylen = strlen(bump.key); 
     449 
     450    /* See if bump has any empty choices and use it */ 
     451    for (n = 0; n < NHASH_TRIES; n++) { 
     452      hash_func hash; 
     453      int hashindex = (n + htab->hashfunc_offset) % NHASH_MOD; 
     454 
     455      hash = hash_functions[hashindex]; 
     456      hval = hash(bump.key, keylen) % htab->hashsize; 
     457      if (htab->buckets[hval].key == NULL) { 
     458        htab->buckets[hval] = bump; 
     459        return true; 
     460      } 
     461    } 
     462 
     463    /* None. Use a random func and bump the existing element */ 
     464    n = htab->hashfunc_offset + get_random_long(0, NHASH_TRIES - 1); 
     465    n %= NHASH_MOD; 
     466    hval = (hash_functions[n])(bump.key, keylen) % htab->hashsize; 
     467    temp = htab->buckets[hval]; 
     468    htab->buckets[hval] = bump; 
     469    bump = temp; 
     470    loop += 1; 
     471  } 
     472 
     473  /* At this point, we've bumped BUMP_LIMIT times. Probably in a 
     474     loop. Find the first empty bucket, add the last bumped to, and 
     475     return failure. */ 
     476  for (n = 0; n < htab->hashsize; n++) 
     477    if (htab->buckets[n].key == NULL) { 
     478      htab->buckets[n] = bump; 
     479      return false; 
     480    } 
     481 
     482  /* Never reached. */ 
     483  return false; 
     484} 
     485 
     486 
     487static int resize_calls = 0, first_offset = -1; 
     488 
     489/** Resize a hash table. 
     490 * \param htab pointer to hashtable. 
     491 * \param primesize new size. 
     492 * \param hashindex Index of first hash function to use 
     493 */ 
     494static bool 
     495real_hash_resize(HASHTAB *htab, int newsize, int hashfunc_offset) 
     496{ 
     497  HASHENT *oldarr; 
     498  int oldsize, oldoffset, i; 
     499 
     500  /* Massive overkill here */ 
     501  if (resize_calls > 150) {    
     502    fputs("Ooops. Too many attempts to resize a hash table.\n", stderr); 
     503    return false; 
     504  } 
     505 
     506  /* If all possible hash function combos have been exhausted, 
     507     grow the array */ 
     508  if (hashfunc_offset == first_offset) { 
     509    int newersize = next_prime_after(floor(newsize * 1.15)); 
     510    first_offset = -1; 
     511    return real_hash_resize(htab, newersize, hashfunc_offset); 
     512  } 
     513 
     514  resize_calls += 1; 
     515 
     516  /* Save the old data we need */ 
     517  oldsize = htab->hashsize; 
     518  oldoffset = htab->hashfunc_offset; 
     519  oldarr = htab->buckets; 
     520 
     521  htab->buckets = mush_calloc(newsize, sizeof(struct hash_bucket), "hash.buckets"); 
     522  htab->hashsize = newsize; 
     523  htab->hashfunc_offset = hashfunc_offset; 
     524  for (i = 0; i < oldsize; i++) { 
     525 
     526    if (oldarr[i].key) { 
     527 
     528      if (!hash_insert(htab, oldarr[i].key, oldarr[i].data)) { 
     529        /* Couldn't fit an element in. Try with different hash functions. */ 
     530        mush_free(htab->buckets, "hash.buckets"); 
     531        htab->buckets = oldarr; 
     532        htab->hashsize = oldsize;   
     533        htab->hashfunc_offset = oldoffset; 
     534        if (first_offset == -1) 
     535          first_offset = hashfunc_offset; 
     536        return 
     537          real_hash_resize(htab, newsize, (hashfunc_offset + 1) % NHASH_MOD); 
     538      } 
     539    } 
     540  } 
     541 
     542  mush_free(oldarr, "hash.buckets"); 
     543  return true; 
    222544} 
    223545 
    …… 
    226548 * \param size new size. 
    227549 */ 
    228 void 
     550bool 
    229551hash_resize(HASHTAB *htab, int size) 
    230552{ 
    231   int i; 
    232   HASHENT **oldarr; 
    233   HASHENT **newarr; 
    234   HASHENT *hent, *nent, *curr, *old; 
    235   int hval; 
    236   int osize; 
    237   int mask; 
    238  
    239   /* We don't want hashes outside these limits */ 
    240   if ((size < (1 << 4)) || (size > (1 << 20))) 
    241     return; 
    242  
    243   /* Save the old data we need */ 
    244   osize = htab->hashsize; 
    245   oldarr = htab->buckets; 
    246  
    247   mask = htab->mask = get_hashmask(&size); 
    248  
    249   if (size == htab->hashsize) 
    250     return; 
    251  
    252   htab->hashsize = size; 
    253   newarr = 
    254     (HASHENT **) mush_calloc(size, sizeof(struct hashentry *), "hash_buckets"); 
    255   htab->buckets = newarr; 
    256  
    257   for (i = 0; i < osize; i++) { 
    258     hent = oldarr[i]; 
    259     while (hent) { 
    260       nent = hent->next; 
    261       hval = hash_val(hent->key, mask); 
    262       for (curr = newarr[hval], old = NULL; curr; old = curr, curr = curr->next) { 
    263         if (strcmp(curr->key, hent->key) > 0) 
    264           break; 
    265       } 
    266       if (old) { 
    267         old->next = hent; 
    268         hent->next = curr; 
    269       } else { 
    270         hent->next = newarr[hval]; 
    271         newarr[hval] = hent; 
    272       } 
    273       hent = nent; 
    274     } 
    275   } 
    276   mush_free(oldarr, "hash_buckets"); 
    277  
    278   return; 
    279 } 
    280  
    281 slab *hashentry_slab; 
    282  
    283 static HASHENT * 
    284 hash_new(HASHTAB *htab, const char *key) 
    285 { 
    286   int hval; 
    287   HASHENT *hptr, *curr, *old; 
    288  
    289   hptr = hash_find(htab, key); 
    290   if (hptr) 
    291     return hptr; 
    292  
    293   if ((double) htab->entries > (htab->hashsize * HTAB_UPSCALE)) 
    294     hash_resize(htab, htab->hashsize << 1); 
    295  
    296   hval = hash_val(key, htab->mask); 
    297   htab->entries++; 
    298   if (!hashentry_slab) { 
    299     hashentry_slab = slab_create("hash table entries", sizeof(HASHENT)); 
    300     slab_set_opt(hashentry_slab, SLAB_HINTLESS_THRESHOLD, 3); 
    301   } 
    302   hptr = slab_malloc(hashentry_slab, htab->buckets[hval]); 
    303   hptr->key = mush_strdup(key, "hash_key"); 
    304   hptr->data = NULL; 
    305  
    306   if (!htab->buckets[hval] || strcmp(key, htab->buckets[hval]->key) < 0) { 
    307     hptr->next = htab->buckets[hval]; 
    308     htab->buckets[hval] = hptr; 
    309     return hptr; 
    310   } 
    311  
    312   /* Insert in sorted order. There's always at least one item in  
    313      the chain already at this point. */ 
    314   old = htab->buckets[hval]; 
    315   for (curr = old->next; curr; old = curr, curr = curr->next) { 
    316     /* Comparison will never be 0 because hash_add checks to see 
    317        if the entry is already present. */ 
    318     if (strcmp(key, curr->key) < 0) {   /* Insert before curr */ 
    319       old->next = hptr; 
    320       hptr->next = curr; 
    321       return hptr; 
    322     } 
    323   } 
    324  
    325   /* If we get here, we reached the end of the chain */ 
    326   old->next = hptr; 
    327   hptr->next = NULL; 
    328  
    329   return hptr; 
     553  if (htab) { 
     554    htab->last_index = -1; 
     555    first_offset = -1; 
     556    resize_calls = 0; 
     557    return real_hash_resize(htab, next_prime_after(size), 
     558                            htab->hashfunc_offset); 
     559  } else 
     560    return false; 
    330561} 
    331562 
    …… 
    335566 * \param hashdata void pointer to data to be stored. 
    336567 * \param extra_size unused. 
    337  * \retval -1 failure. 
    338  * \retval 0 success. 
    339  */ 
    340 int 
    341 hash_add(HASHTAB *htab, const char *key, void *hashdata, 
    342          int extra_size __attribute__ ((__unused__))) 
    343 { 
    344   HASHENT *hptr; 
    345  
    346   if (hash_find(htab, key) != NULL) { 
    347     return -1; 
    348   } 
    349  
    350   hptr = hash_new(htab, key); 
    351  
    352   if (!hptr) 
    353     return -1; 
    354  
    355   hptr->data = hashdata; 
    356   return 0; 
     568 * \retval false failure. 
     569 * \retval true success. 
     570 */ 
     571bool 
     572hash_add(HASHTAB *htab, const char *key, void *hashdata) 
     573{ 
     574  const char *keycopy; 
     575 
     576  if (hash_find(htab, key) != NULL) 
     577    return false; 
     578 
     579  htab->entries += 1; 
     580 
     581  keycopy = mush_strdup(key, "hash.key"); 
     582 
     583  if (!hash_insert(htab, keycopy, hashdata)) { 
     584    first_offset = -1; 
     585    resize_calls = 0; 
     586    if (!real_hash_resize(htab, htab->hashsize, 
     587                          (htab->hashfunc_offset + 1) % NHASH_MOD)) { 
     588      htab->entries -= 1; 
     589      return false; 
     590    } 
     591  } 
     592  return true; 
    357593} 
    358594 
    …… 
    364600hash_delete(HASHTAB *htab, HASHENT *entry) 
    365601{ 
    366   int hval; 
    367   HASHENT *hptr, *last; 
    368  
    369602  if (!entry) 
    370603    return; 
    371604 
    372   hval = hash_val(entry->key, htab->mask); 
    373   last = NULL; 
    374   for (hptr = htab->buckets[hval]; hptr; last = hptr, hptr = hptr->next) { 
    375     if (entry == hptr) { 
    376       if (last == NULL) 
    377         htab->buckets[hval] = hptr->next; 
    378       else 
    379         last->next = hptr->next; 
    380       mush_free(hptr->key, "hash_key"); 
    381       if (htab->free_data) 
    382         htab->free_data(hptr->data); 
    383       slab_free(hashentry_slab, hptr); 
    384       htab->entries--; 
    385       return; 
    386     } 
    387   } 
    388  
    389   if ((double) htab->entries < (htab->hashsize * HTAB_DOWNSCALE)) 
    390     hash_resize(htab, htab->hashsize >> 1); 
     605  if (htab->free_data) 
     606    htab->free_data(entry->data); 
     607  mush_free((void *) entry->key, "hash.key"); 
     608  memset(entry, 0, sizeof *entry); 
     609  htab->entries -= 1; 
    391610} 
    392611 
    …… 
    398617hash_flush(HASHTAB *htab, int size) 
    399618{ 
    400   HASHENT *hent, *thent; 
    401619  int i; 
    402  
    403   if (htab->buckets) { 
     620  struct hash_bucket *resized; 
     621 
     622  if (htab->entries) { 
    404623    for (i = 0; i < htab->hashsize; i++) { 
    405       hent = htab->buckets[i]; 
    406       while (hent != NULL) { 
    407         thent = hent; 
    408         hent = hent->next; 
    409         mush_free(thent->key, "hash_key"); 
     624      if (htab->buckets[i].key) { 
     625        mush_free((void *) htab->buckets[i].key, "hash.key"); 
    410626        if (htab->free_data) 
    411           htab->free_data(thent->data); 
    412         slab_free(hashentry_slab, thent); 
     627          htab->free_data(htab->buckets[i].data); 
    413628      } 
    414       htab->buckets[i] = NULL; 
    415     } 
    416   } 
    417   if (size == 0) { 
    418     mush_free(htab->buckets, "hash_buckets"); 
    419     htab->buckets = NULL; 
    420   } else if (size != htab->hashsize) { 
    421     if (htab->buckets) 
    422       mush_free(htab->buckets, "hash_buckets"); 
    423     hashinit(htab, size, htab->entry_size); 
    424   } else { 
    425     htab->entries = 0; 
    426   } 
     629    } 
     630  } 
     631  htab->entries = 0; 
     632  size = next_prime_after(size); 
     633  resized = mush_realloc(htab->buckets, size, "hash.buckets"); 
     634  if (resized) { 
     635    htab->buckets = resized; 
     636    htab->hashsize = size; 
     637  } 
     638  memset(htab->buckets, 0, sizeof(struct hash_bucket) * htab->hashsize); 
    427639} 
    428640 
    …… 
    436648hash_firstentry(HASHTAB *htab) 
    437649{ 
    438   int hval; 
    439  
    440   for (hval = 0; hval < htab->hashsize; hval++) 
    441     if (htab->buckets[hval]) { 
    442       htab->last_hval = hval; 
    443       htab->last_entry = htab->buckets[hval]; 
    444       return htab->buckets[hval]->data; 
     650  int n; 
     651 
     652  for (n = 0; n < htab->hashsize; n++) 
     653    if (htab->buckets[n].key) { 
     654      htab->last_index = n; 
     655      return htab->buckets[n].data; 
    445656    } 
    446657  return NULL; 
    …… 
    453664 * \return first hash table key. 
    454665 */ 
    455 char * 
     666const char * 
    456667hash_firstentry_key(HASHTAB *htab) 
    457668{ 
    458   int hval; 
    459  
    460   for (hval = 0; hval < htab->hashsize; hval++) 
    461     if (htab->buckets[hval]) { 
    462       htab->last_hval = hval; 
    463       htab->last_entry = htab->buckets[hval]; 
    464       return htab->buckets[hval]->key; 
     669  int n; 
     670 
     671  for (n = 0; n < htab->hashsize; n++) 
     672    if (htab->buckets[n].key) { 
     673      htab->last_index = n; 
     674      return htab->buckets[n].key; 
    465675    } 
    466676  return NULL; 
    …… 
    477687hash_nextentry(HASHTAB *htab) 
    478688{ 
    479   int hval; 
    480   HASHENT *hptr; 
    481  
    482   hval = htab->last_hval; 
    483   hptr = htab->last_entry; 
    484   if (hptr->next) { 
    485     htab->last_entry = hptr->next; 
    486     return hptr->next->data; 
    487   } 
    488   hval++; 
    489   while (hval < htab->hashsize) { 
    490     if (htab->buckets[hval]) { 
    491       htab->last_hval = hval; 
    492       htab->last_entry = htab->buckets[hval]; 
    493       return htab->buckets[hval]->data; 
    494     } 
    495     hval++; 
     689  int n = htab->last_index + 1; 
     690  while (n < htab->hashsize) { 
     691    if (htab->buckets[n].key) { 
     692      htab->last_index = n; 
     693      return htab->buckets[n].data; 
     694    } 
     695    n += 1; 
    496696  } 
    497697  return NULL; 
    …… 
    505705 * \return next hash table key. 
    506706 */ 
    507 char * 
     707const char * 
    508708hash_nextentry_key(HASHTAB *htab) 
    509709{ 
    510   int hval; 
    511   HASHENT *hptr; 
    512  
    513   hval = htab->last_hval; 
    514   hptr = htab->last_entry; 
    515   if (hptr->next) { 
    516     htab->last_entry = hptr->next; 
    517     return hptr->next->key; 
    518   } 
    519   hval++; 
    520   while (hval < htab->hashsize) { 
    521     if (htab->buckets[hval]) { 
    522       htab->last_hval = hval; 
    523       htab->last_entry = htab->buckets[hval]; 
    524       return htab->buckets[hval]->key; 
    525     } 
    526     hval++; 
     710  int n = htab->last_index + 1; 
     711  while (n < htab->hashsize) {