Index: /trunk/src/kmk/incdep.c
===================================================================
--- /trunk/src/kmk/incdep.c	(revision 1908)
+++ /trunk/src/kmk/incdep.c	(revision 1909)
@@ -773,5 +773,9 @@
                                                      entry->length,
                                                      entry->hash1,
+#ifdef STRCACHE2_USE_CHAINING
+                                                     1);
+#else
                                                      entry->hash2);
+#endif
   return (const char *)entry->user;
 }
Index: /trunk/src/kmk/strcache2.c
===================================================================
--- /trunk/src/kmk/strcache2.c	(revision 1908)
+++ /trunk/src/kmk/strcache2.c	(revision 1909)
@@ -77,5 +77,5 @@
 /** Finds the closest primary number for power of two value (or something else
  *  useful if not support).   */
-MY_INLINE strcache2_find_prime(unsigned int shift)
+MY_INLINE unsigned int strcache2_find_prime(unsigned int shift)
 {
   switch (shift)
@@ -235,4 +235,5 @@
 strcache2_case_sensitive_hash_2 (const char *str, unsigned int len)
 {
+#ifndef STRCACHE2_USE_CHAINING
   unsigned int hash = 0;
   if (MY_PREDICT_TRUE(len >= 2))
@@ -270,4 +271,7 @@
   hash |= 1;
   return hash;
+#else  /* STRCACHE2_USE_CHAINING */
+  return 1;
+#endif /* STRCACHE2_USE_CHAINING */
 }
 
@@ -318,4 +322,5 @@
 strcache2_case_insensitive_hash_2 (const char *str, unsigned int len)
 {
+#ifndef STRCACHE2_USE_CHAINING
   unsigned int hash = 0;
   if (MY_PREDICT_TRUE(len >= 2))
@@ -357,4 +362,7 @@
   hash |= 1;
   return hash;
+#else  /* STRCACHE2_USE_CHAINING */
+  return 1;
+#endif /* STRCACHE2_USE_CHAINING */
 }
 
@@ -592,8 +600,6 @@
   struct strcache2_entry **src_tab = cache->hash_tab;
   struct strcache2_entry **dst_tab;
-#ifdef STRCACHE2_USE_MASK
-  unsigned int hash_mask;
-#else
-  unsigned int hash_div;
+#ifndef STRCACHE2_USE_MASK
+  unsigned int hash_shift;
 #endif
 
@@ -604,7 +610,7 @@
   cache->hash_mask |= 1;
 #else
-  for (hash_div = 1; (1U << hash_div) < cache->hash_size; hash_div++)
+  for (hash_shift = 1; (1U << hash_shift) < cache->hash_size; hash_shift++)
     /* nothing */;
-  cache->hash_div = strcache2_find_prime(hash_div);
+  cache->hash_div = strcache2_find_prime (hash_shift);
 #endif
   cache->rehash_count <<= 1;
@@ -614,9 +620,4 @@
 
   /* Copy the entries from the old to the new hash table. */
-#ifdef STRCACHE2_USE_MASK
-  hash_mask = cache->hash_mask;
-#else
-  hash_div = cache->hash_div;
-#endif
   while (src-- > 0)
     {
@@ -624,9 +625,8 @@
       if (entry)
         {
-#ifdef STRCACHE2_USE_MASK
-          unsigned int dst = entry->hash1 & hash_mask;
+#ifdef STRCACHE2_USE_CHAINING
+assert(!"todo");
 #else
-          unsigned int dst = entry->hash1 % hash_div;
-#endif
+          unsigned int dst = STRCACHE2_MOD_IT (cache, entry->hash1);
           if (dst_tab[dst])
             {
@@ -637,21 +637,14 @@
                   : strcache2_case_sensitive_hash_2 ((const char *)(entry + 1), entry->length);
               dst += hash2;
-#ifdef STRCACHE2_USE_MASK
-              dst &= hash_mask;
-#else
-              dst %= hash_div;
-#endif
+              dst = STRCACHE2_MOD_IT (cache, dst);
               while (dst_tab[dst])
                 {
                   dst += hash2;
-#ifdef STRCACHE2_USE_MASK
-                  dst &= hash_mask;
-#else
-                  dst %= hash_div;
-#endif
+                  dst = STRCACHE2_MOD_IT (cache, dst);
                 }
             }
 
           dst_tab[dst] = entry;
+#endif
         }
     }
@@ -697,9 +690,21 @@
   entry->length = length;
   entry->hash1 = hash1;
+#ifndef STRCACHE2_USE_CHAINING
   entry->hash2 = hash2;
+#endif
   str_copy = (char *) memcpy (entry + 1, str, length);
   str_copy[length] = '\0';
 
+#ifndef STRCACHE2_USE_CHAINING
   cache->hash_tab[idx] = entry;
+#else  /* STRCACHE2_USE_CHAINING */
+  if ((entry->next = cache->hash_tab[idx]) == 0)
+    cache->hash_tab[idx] = entry;
+  else
+    {
+      cache->hash_tab[idx] = entry;
+      cache->collision_count++;
+    }
+#endif /* STRCACHE2_USE_CHAINING */
   cache->count++;
   if (cache->count >= cache->rehash_count)
@@ -714,6 +719,6 @@
 {
   struct strcache2_entry const *entry;
-  unsigned int hash2;
   unsigned int hash1 = strcache2_case_sensitive_hash_1 (str, length);
+  unsigned int hash2 = 0;
   unsigned int idx;
 
@@ -723,40 +728,44 @@
 
   /* Lookup the entry in the hash table, hoping for an
-     early match. */
-  idx = STRCACHE2_MOD_IT(cache, hash1);
+     early match.  If not found, enter the string at IDX. */
+  idx = STRCACHE2_MOD_IT (cache, hash1);
   entry = cache->hash_tab[idx];
+  if (!entry)
+    return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
   if (strcache2_is_equal (cache, entry, str, length, hash1))
     return (const char *)(entry + 1);
+  cache->collision_1st_count++;
+
+#ifdef STRCACHE2_USE_CHAINING
+  entry = entry->next;
+#else  /* !STRCACHE2_USE_CHAINING */
+  hash2 = strcache2_case_sensitive_hash_2 (str, length);
+  idx += hash2;
+  idx = STRCACHE2_MOD_IT (cache, idx);
+  entry = cache->hash_tab[idx];
+#endif /* !STRCACHE2_USE_CHAINING */
   if (!entry)
-    hash2 = 0;
-  else
-    {
-      cache->collision_1st_count++;
-
-      hash2 = strcache2_case_sensitive_hash_2 (str, length);
+    return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
+  if (strcache2_is_equal (cache, entry, str, length, hash1))
+    return (const char *)(entry + 1);
+  cache->collision_2nd_count++;
+
+  /* (We've established hash2, so we can do a straight loop now.)  */
+  for (;;)
+    {
+#ifdef STRCACHE2_USE_CHAINING
+      entry = entry->next;
+#else  /* !STRCACHE2_USE_CHAINING */
       idx += hash2;
-      idx = STRCACHE2_MOD_IT(cache, idx);
+      idx = STRCACHE2_MOD_IT (cache, idx);
       entry = cache->hash_tab[idx];
+#endif /* !STRCACHE2_USE_CHAINING */
+      if (!entry)
+        return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
       if (strcache2_is_equal (cache, entry, str, length, hash1))
         return (const char *)(entry + 1);
-
-      if (entry)
-        {
-          cache->collision_2nd_count++;
-          do
-            {
-              idx += hash2;
-              idx = STRCACHE2_MOD_IT(cache, idx);
-              entry = cache->hash_tab[idx];
-              cache->collision_3rd_count++;
-              if (strcache2_is_equal (cache, entry, str, length, hash1))
-                return (const char *)(entry + 1);
-            }
-          while (entry);
-        }
-    }
-
-  /* Not found, add it at IDX. */
-  return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
+      cache->collision_3rd_count++;
+    }
+  /* not reached */
 }
 
@@ -785,41 +794,45 @@
 
   /* Lookup the entry in the hash table, hoping for an
-     early match. */
-  idx = STRCACHE2_MOD_IT(cache, hash1);
+     early match.  If not found, enter the string at IDX. */
+  idx = STRCACHE2_MOD_IT (cache, hash1);
   entry = cache->hash_tab[idx];
+  if (!entry)
+    return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
   if (strcache2_is_equal (cache, entry, str, length, hash1))
     return (const char *)(entry + 1);
-  if (entry)
-    {
-      cache->collision_1st_count++;
-
-      if (!hash2)
-        hash2 = cache->case_insensitive
-          ? strcache2_case_insensitive_hash_2 (str, length)
-          : strcache2_case_sensitive_hash_2 (str, length);
+  cache->collision_1st_count++;
+
+#ifdef STRCACHE2_USE_CHAINING
+  entry = entry->next;
+#else  /* !STRCACHE2_USE_CHAINING */
+  if (!hash2)
+      hash2 = strcache2_case_sensitive_hash_2 (str, length);
+  idx += hash2;
+  idx = STRCACHE2_MOD_IT (cache, idx);
+  entry = cache->hash_tab[idx];
+#endif /* !STRCACHE2_USE_CHAINING */
+  if (!entry)
+    return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
+  if (strcache2_is_equal (cache, entry, str, length, hash1))
+    return (const char *)(entry + 1);
+  cache->collision_2nd_count++;
+
+  /* (We've established hash2, so we can do a straight loop now.)  */
+  for (;;)
+    {
+#ifdef STRCACHE2_USE_CHAINING
+      entry = entry->next;
+#else  /* !STRCACHE2_USE_CHAINING */
       idx += hash2;
-      idx = STRCACHE2_MOD_IT(cache, idx);
+      idx = STRCACHE2_MOD_IT (cache, idx);
       entry = cache->hash_tab[idx];
+#endif /* !STRCACHE2_USE_CHAINING */
+      if (!entry)
+        return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
       if (strcache2_is_equal (cache, entry, str, length, hash1))
         return (const char *)(entry + 1);
-
-      if (entry)
-        {
-          cache->collision_2nd_count++;
-          do
-            {
-              idx += hash2;
-              idx = STRCACHE2_MOD_IT(cache, idx);
-              entry = cache->hash_tab[idx];
-              cache->collision_3rd_count++;
-              if (strcache2_is_equal (cache, entry, str, length, hash1))
-                return (const char *)(entry + 1);
-            }
-          while (entry);
-        }
-    }
-
-  /* Not found, add it at IDX. */
-  return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
+      cache->collision_3rd_count++;
+    }
+  /* not reached */
 }
 
@@ -829,6 +842,8 @@
 {
   struct strcache2_entry const *entry;
+  unsigned int hash1 = strcache2_case_sensitive_hash_1 (str, length);
+#ifndef STRCACHE2_USE_CHAINING
   unsigned int hash2;
-  unsigned int hash1 = strcache2_case_sensitive_hash_1 (str, length);
+#endif
   unsigned int idx;
 
@@ -839,39 +854,43 @@
   /* Lookup the entry in the hash table, hoping for an
      early match. */
-  idx = STRCACHE2_MOD_IT(cache, hash1);
+  idx = STRCACHE2_MOD_IT (cache, hash1);
   entry = cache->hash_tab[idx];
+  if (!entry)
+    return NULL;
   if (strcache2_is_equal (cache, entry, str, length, hash1))
     return (const char *)(entry + 1);
+  cache->collision_1st_count++;
+
+#ifdef STRCACHE2_USE_CHAINING
+  entry = entry->next;
+#else  /* !STRCACHE2_USE_CHAINING */
+  hash2 = strcache2_case_sensitive_hash_2 (str, length);
+  idx += hash2;
+  idx = STRCACHE2_MOD_IT (cache, idx);
+  entry = cache->hash_tab[idx];
+#endif /* !STRCACHE2_USE_CHAINING */
   if (!entry)
-    hash2 = 0;
-  else
-    {
-      cache->collision_1st_count++;
-
-      hash2 = strcache2_case_sensitive_hash_2 (str, length);
+    return NULL;
+  if (strcache2_is_equal (cache, entry, str, length, hash1))
+    return (const char *)(entry + 1);
+  cache->collision_2nd_count++;
+
+  /* (We've established hash2, so we can do a straight loop now.)  */
+  for (;;)
+    {
+#ifdef STRCACHE2_USE_CHAINING
+      entry = entry->next;
+#else  /* !STRCACHE2_USE_CHAINING */
       idx += hash2;
-      idx = STRCACHE2_MOD_IT(cache, idx);
+      idx = STRCACHE2_MOD_IT (cache, idx);
       entry = cache->hash_tab[idx];
+#endif /* !STRCACHE2_USE_CHAINING */
+      if (!entry)
+        return NULL;
       if (strcache2_is_equal (cache, entry, str, length, hash1))
         return (const char *)(entry + 1);
-
-      if (entry)
-        {
-          cache->collision_2nd_count++;
-          do
-            {
-              idx += hash2;
-              idx = STRCACHE2_MOD_IT(cache, idx);
-              entry = cache->hash_tab[idx];
-              cache->collision_3rd_count++;
-              if (strcache2_is_equal (cache, entry, str, length, hash1))
-                return (const char *)(entry + 1);
-            }
-          while (entry);
-        }
-    }
-
-  /* Not found. */
-  return NULL;
+      cache->collision_3rd_count++;
+    }
+  /* not reached */
 }
 
@@ -883,48 +902,53 @@
 {
   struct strcache2_entry const *entry;
-  unsigned int hash2;
   unsigned int hash1 = strcache2_case_insensitive_hash_1 (str, length);
+  unsigned int hash2 = 0;
   unsigned int idx;
 
-  assert (cache->case_insensitive);
+  assert (!cache->case_insensitive);
+
   cache->lookup_count++;
 
   /* Lookup the entry in the hash table, hoping for an
-     early match. */
-  idx = STRCACHE2_MOD_IT(cache, hash1);
+     early match.  If not found, enter the string at IDX. */
+  idx = STRCACHE2_MOD_IT (cache, hash1);
   entry = cache->hash_tab[idx];
-  if (strcache2_is_iequal (cache, entry, str, length, hash1))
+  if (!entry)
+    return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
+  if (strcache2_is_equal (cache, entry, str, length, hash1))
     return (const char *)(entry + 1);
+  cache->collision_1st_count++;
+
+#ifdef STRCACHE2_USE_CHAINING
+  entry = entry->next;
+#else  /* !STRCACHE2_USE_CHAINING */
+  hash2 = strcache2_case_insensitive_hash_2 (str, length);
+  idx += hash2;
+  idx = STRCACHE2_MOD_IT (cache, idx);
+  entry = cache->hash_tab[idx];
+#endif /* !STRCACHE2_USE_CHAINING */
   if (!entry)
-    hash2 = 0;
-  else
-    {
-      cache->collision_1st_count++;
-
-      hash2 = strcache2_case_insensitive_hash_2 (str, length);
+    return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
+  if (strcache2_is_equal (cache, entry, str, length, hash1))
+    return (const char *)(entry + 1);
+  cache->collision_2nd_count++;
+
+  /* (We've established hash2, so we can do a straight loop now.)  */
+  for (;;)
+    {
+#ifdef STRCACHE2_USE_CHAINING
+      entry = entry->next;
+#else  /* !STRCACHE2_USE_CHAINING */
       idx += hash2;
-      idx = STRCACHE2_MOD_IT(cache, idx);
+      idx = STRCACHE2_MOD_IT (cache, idx);
       entry = cache->hash_tab[idx];
-      if (strcache2_is_iequal (cache, entry, str, length, hash1))
+#endif /* !STRCACHE2_USE_CHAINING */
+      if (!entry)
+        return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
+      if (strcache2_is_equal (cache, entry, str, length, hash1))
         return (const char *)(entry + 1);
-
-      if (entry)
-        {
-          cache->collision_2nd_count++;
-          do
-            {
-              idx += hash2;
-              idx = STRCACHE2_MOD_IT(cache, idx);
-              entry = cache->hash_tab[idx];
-              cache->collision_3rd_count++;
-              if (strcache2_is_iequal (cache, entry, str, length, hash1))
-                return (const char *)(entry + 1);
-            }
-          while (entry);
-        }
-    }
-
-  /* Not found, add it at IDX. */
-  return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
+      cache->collision_3rd_count++;
+    }
+  /* not reached */
 }
 
@@ -940,5 +964,5 @@
   unsigned correct_hash;
 
-  assert (cache->case_insensitive);
+  assert (!cache->case_insensitive);
   correct_hash = strcache2_case_insensitive_hash_1 (str, length);
   MY_ASSERT_MSG (hash1 == correct_hash, ("%#x != %#x\n", hash1, correct_hash));
@@ -953,51 +977,59 @@
 
   /* Lookup the entry in the hash table, hoping for an
-     early match. */
-  idx = STRCACHE2_MOD_IT(cache, hash1);
+     early match.  If not found, enter the string at IDX. */
+  idx = STRCACHE2_MOD_IT (cache, hash1);
   entry = cache->hash_tab[idx];
-  if (strcache2_is_iequal (cache, entry, str, length, hash1))
+  if (!entry)
+    return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
+  if (strcache2_is_equal (cache, entry, str, length, hash1))
     return (const char *)(entry + 1);
-  if (entry)
-    {
-      cache->collision_1st_count++;
-
-      if (!hash2)
-        hash2 = strcache2_case_insensitive_hash_2 (str, length);
+  cache->collision_1st_count++;
+
+#ifdef STRCACHE2_USE_CHAINING
+  entry = entry->next;
+#else  /* !STRCACHE2_USE_CHAINING */
+  if (!hash2)
+      hash2 = strcache2_case_insensitive_hash_2 (str, length);
+  idx += hash2;
+  idx = STRCACHE2_MOD_IT (cache, idx);
+  entry = cache->hash_tab[idx];
+#endif /* !STRCACHE2_USE_CHAINING */
+  if (!entry)
+    return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
+  if (strcache2_is_equal (cache, entry, str, length, hash1))
+    return (const char *)(entry + 1);
+  cache->collision_2nd_count++;
+
+  /* (We've established hash2, so we can do a straight loop now.)  */
+  for (;;)
+    {
+#ifdef STRCACHE2_USE_CHAINING
+      entry = entry->next;
+#else  /* !STRCACHE2_USE_CHAINING */
       idx += hash2;
-      idx = STRCACHE2_MOD_IT(cache, idx);
+      idx = STRCACHE2_MOD_IT (cache, idx);
       entry = cache->hash_tab[idx];
-      if (strcache2_is_iequal (cache, entry, str, length, hash1))
+#endif /* !STRCACHE2_USE_CHAINING */
+      if (!entry)
+        return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
+      if (strcache2_is_equal (cache, entry, str, length, hash1))
         return (const char *)(entry + 1);
-
-      if (entry)
-        {
-          cache->collision_2nd_count++;
-          do
-            {
-              idx += hash2;
-              idx = STRCACHE2_MOD_IT(cache, idx);
-              entry = cache->hash_tab[idx];
-              cache->collision_3rd_count++;
-              if (strcache2_is_iequal (cache, entry, str, length, hash1))
-                return (const char *)(entry + 1);
-            }
-          while (entry);
-        }
-    }
-
-  /* Not found, add it at IDX. */
-  return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
+      cache->collision_3rd_count++;
+    }
+  /* not reached */
 }
 
 /* The public lookup (case insensitive) string interface. */
 const char *
-strcache2_lookup (struct strcache2 *cache, const char *str, unsigned int length)
+strcache2_ilookup (struct strcache2 *cache, const char *str, unsigned int length)
 {
   struct strcache2_entry const *entry;
+  unsigned int hash1 = strcache2_case_insensitive_hash_1 (str, length);
+#ifndef STRCACHE2_USE_CHAINING
   unsigned int hash2;
-  unsigned int hash1 = strcache2_case_insensitive_hash_1 (str, length);
+#endif
   unsigned int idx;
 
-  assert (cache->case_insensitive);
+  assert (!cache->case_insensitive);
 
   cache->lookup_count++;
@@ -1005,39 +1037,43 @@
   /* Lookup the entry in the hash table, hoping for an
      early match. */
-  idx = STRCACHE2_MOD_IT(cache, hash1);
+  idx = STRCACHE2_MOD_IT (cache, hash1);
   entry = cache->hash_tab[idx];
-  if (strcache2_is_iequal (cache, entry, str, length, hash1))
+  if (!entry)
+    return NULL;
+  if (strcache2_is_equal (cache, entry, str, length, hash1))
     return (const char *)(entry + 1);
+  cache->collision_1st_count++;
+
+#ifdef STRCACHE2_USE_CHAINING
+  entry = entry->next;
+#else  /* !STRCACHE2_USE_CHAINING */
+  hash2 = strcache2_case_insensitive_hash_2 (str, length);
+  idx += hash2;
+  idx = STRCACHE2_MOD_IT (cache, idx);
+  entry = cache->hash_tab[idx];
+#endif /* !STRCACHE2_USE_CHAINING */
   if (!entry)
-    hash2 = 0;
-  else
-    {
-      cache->collision_1st_count++;
-
-      hash2 = strcache2_case_insensitive_hash_2 (str, length);
+    return NULL;
+  if (strcache2_is_equal (cache, entry, str, length, hash1))
+    return (const char *)(entry + 1);
+  cache->collision_2nd_count++;
+
+  /* (We've established hash2, so we can do a straight loop now.)  */
+  for (;;)
+    {
+#ifdef STRCACHE2_USE_CHAINING
+      entry = entry->next;
+#else  /* !STRCACHE2_USE_CHAINING */
       idx += hash2;
-      idx = STRCACHE2_MOD_IT(cache, idx);
+      idx = STRCACHE2_MOD_IT (cache, idx);
       entry = cache->hash_tab[idx];
-      if (strcache2_is_iequal (cache, entry, str, length, hash1))
+#endif /* !STRCACHE2_USE_CHAINING */
+      if (!entry)
+        return NULL;
+      if (strcache2_is_equal (cache, entry, str, length, hash1))
         return (const char *)(entry + 1);
-
-      if (entry)
-        {
-          cache->collision_2nd_count++;
-          do
-            {
-              idx += hash2;
-              idx = STRCACHE2_MOD_IT(cache, idx);
-              entry = cache->hash_tab[idx];
-              cache->collision_3rd_count++;
-              if (strcache2_is_iequal (cache, entry, str, length, hash1))
-                return (const char *)(entry + 1);
-            }
-          while (entry);
-        }
-    }
-
-  /* Not found. */
-  return NULL;
+      cache->collision_3rd_count++;
+    }
+  /* not reached */
 }
 
@@ -1100,4 +1136,5 @@
     }
 
+#ifndef STRCACHE2_USE_CHAINING
   if (entry->hash2)
     {
@@ -1113,8 +1150,10 @@
         }
     }
+#endif
 
   return 0;
 }
 
+#ifndef STRCACHE2_USE_CHAINING
 /* Fallback for calculating and returning the 2nd hash. */
 unsigned int
@@ -1128,4 +1167,5 @@
   return hash2;
 }
+#endif /* !STRCACHE2_USE_CHAINING */
 
 /* Calculates the case sensitive hash values of the string.
@@ -1133,5 +1173,9 @@
 unsigned int strcache2_hash_str (const char *str, unsigned int length, unsigned int *hash2p)
 {
+#ifndef STRCACHE2_USE_CHAINING
   *hash2p = strcache2_case_sensitive_hash_2 (str, length);
+#else
+  *hash2p = 1;
+#endif
   return    strcache2_case_sensitive_hash_1 (str, length);
 }
@@ -1141,5 +1185,9 @@
 unsigned int strcache2_hash_istr (const char *str, unsigned int length, unsigned int *hash2p)
 {
+#ifndef STRCACHE2_USE_CHAINING
   *hash2p = strcache2_case_insensitive_hash_2 (str, length);
+#else
+  *hash2p = 1;
+#endif
   return    strcache2_case_insensitive_hash_1 (str, length);
 }
@@ -1182,4 +1230,7 @@
 #endif
   cache->count = 0;
+#ifdef STRCACHE2_USE_CHAINING
+  cache->collision_count = 0;
+#endif
   cache->lookup_count = 0;
   cache->collision_1st_count = 0;
@@ -1246,4 +1297,5 @@
   unsigned long seg_max_bytes = 0;
   struct strcache2_seg *seg;
+  unsigned int  str_count = 0;
   unsigned long str_total_len = 0;
   unsigned int  str_avg_len;
@@ -1252,4 +1304,7 @@
   unsigned int  idx;
   unsigned int  rehashes;
+#ifdef STRCACHE2_USE_CHAINING
+  unsigned int  chain_depths[32];
+#endif
 
   printf (_("\n%s strcache2: %s\n"), prefix, cache->name);
@@ -1270,9 +1325,17 @@
 
   /* String statistics. */
+#ifdef STRCACHE2_USE_CHAINING
+  memset (chain_depths, '\0', sizeof (chain_depths));
+#endif
   idx = cache->hash_size;
   while (idx-- > 0)
     {
       struct strcache2_entry const *entry = cache->hash_tab[idx];
+#ifdef STRCACHE2_USE_CHAINING
+      unsigned int depth = 0;
+      for (; entry != 0; entry = entry->next, depth++)
+#else
       if (entry)
+#endif
         {
           unsigned int length = entry->length;
@@ -1282,9 +1345,16 @@
           if (length < str_min_len)
             str_min_len = length;
-        }
+          str_count++;
+        }
+#ifdef STRCACHE2_USE_CHAINING
+      chain_depths[depth >= 32 ? 31 : depth]++;
+#endif
     }
   str_avg_len = cache->count ? str_total_len / cache->count : 0;
   printf (_("%s  %u strings: total len = %lu / max = %u / avg = %u / min = %u\n"),
           prefix, cache->count, str_total_len, str_max_len, str_avg_len, str_min_len);
+  if (str_count != cache->count)
+    printf (_("%s  string count mismatch! cache->count=%u, actual count is %u\n"), prefix,
+            cache->count, str_count);
 
   /* Hash statistics. */
@@ -1306,7 +1376,27 @@
   printf (_("%s  hash collisions 1st = %lu (%u%%)  2nd = %lu (%u%%)  3rd = %lu (%u%%)\n"),
           prefix,
-          cache->collision_1st_count, (unsigned int)((float)cache->collision_1st_count * 100 / cache->lookup_count),
-          cache->collision_2nd_count, (unsigned int)((float)cache->collision_2nd_count * 100 / cache->lookup_count),
-          cache->collision_3rd_count, (unsigned int)((float)cache->collision_3rd_count * 100 / cache->lookup_count));
+          cache->collision_1st_count, (unsigned int)((100.0 * cache->collision_1st_count) / cache->lookup_count),
+          cache->collision_2nd_count, (unsigned int)((100.0 * cache->collision_2nd_count) / cache->lookup_count),
+          cache->collision_3rd_count, (unsigned int)((100.0 * cache->collision_3rd_count) / cache->lookup_count));
+#ifdef STRCACHE2_USE_CHAINING
+  printf (_("%s  hash insert collisions = %u (%u%%)\n"),
+          prefix, cache->collision_count,(unsigned int)((100.0 * cache->collision_count) / cache->count));
+  printf (_("%s  %5u (%u%%) empty hash table slots\n"),
+          prefix, chain_depths[0],       (unsigned int)((100.0 * chain_depths[0])  / cache->hash_size));
+  printf (_("%s  %5u (%u%%) in used hash table slots\n"),
+          prefix, chain_depths[1],       (unsigned int)((100.0 * chain_depths[1])  / cache->hash_size));
+  for (idx = 2; idx < 32; idx++)
+    {
+      unsigned strs_at_this_depth = chain_depths[idx];
+      unsigned i;
+      for (i = idx + 1; i < 32; i++)
+        strs_at_this_depth += chain_depths[i];
+      if (strs_at_this_depth)
+        printf (_("%s  %5u (%2u%%) with %u string%s chained on; %5u (%2u%%) strings at depth %u.\n"),
+                prefix, chain_depths[idx], (unsigned int)((100.0 * chain_depths[idx]) / (cache->count - cache->collision_count)),
+                idx - 1, idx == 2 ? " " : "s",
+                strs_at_this_depth,        (unsigned int)((100.0 * strs_at_this_depth) / cache->count), idx - 1);
+    }
+#endif
 }
 
Index: /trunk/src/kmk/strcache2.h
===================================================================
--- /trunk/src/kmk/strcache2.h	(revision 1908)
+++ /trunk/src/kmk/strcache2.h	(revision 1909)
@@ -33,4 +33,5 @@
 
 #define STRCACHE2_USE_MASK 1
+#define STRCACHE2_USE_CHAINING 1
 
 /* string cache memory segment. */
@@ -47,7 +48,12 @@
 struct strcache2_entry
 {
+#ifdef STRCACHE2_USE_CHAINING
+    struct strcache2_entry *next;       /* Collision chain. */
+#endif
     void *user;
     unsigned int hash1;
+#ifndef STRCACHE2_USE_CHAINING
     unsigned int hash2;
+#endif
     unsigned int length;
 };
@@ -83,4 +89,7 @@
     unsigned long collision_3rd_count;  /* The number of 3rd level collisions. */
     unsigned int count;                 /* Number entries in the cache. */
+#ifdef STRCACHE2_USE_CHAINING
+    unsigned int collision_count;       /* Number of entries in chains. */
+#endif
     unsigned int rehash_count;          /* When to rehash the table. */
     unsigned int init_size;             /* The initial hash table size. */
@@ -146,4 +155,5 @@
 }
 
+#ifndef STRCACHE2_USE_CHAINING
 /* Get the second hash value for the string. */
 MY_INLINE unsigned int
@@ -155,4 +165,5 @@
   return hash2;
 }
+#endif
 
 /* Get the pointer hash value for the string.
