Index: trunk/src/kmk/strcache2.c
===================================================================
--- trunk/src/kmk/strcache2.c	(revision 1907)
+++ trunk/src/kmk/strcache2.c	(revision 1908)
@@ -56,7 +56,13 @@
 *******************************************************************************/
 /* The default size of a memory segment (1MB). */
-#define STRCACHE2_SEG_SIZE          (1024U*1024U)
+#define STRCACHE2_SEG_SIZE              (1024U*1024U)
 /* The default hash table shift (hash size give as a power of two). */
-#define STRCACHE2_HASH_SHIFT        16
+#define STRCACHE2_HASH_SHIFT            16
+/** Does the modding / masking of a hash number into an index. */
+#ifdef STRCACHE2_USE_MASK
+# define STRCACHE2_MOD_IT(cache, hash)  ((hash) & (cache)->hash_mask)
+#else
+# define STRCACHE2_MOD_IT(cache, hash)  ((hash) % (cache)->hash_div)
+#endif
 
 
@@ -69,4 +75,36 @@
 
 
+/** 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)
+{
+  switch (shift)
+    {
+      case  5:  return 31;
+      case  6:  return 61;
+      case  7:  return 127;
+      case  8:  return 251;
+      case  9:  return 509;
+      case 10:  return 1021;
+      case 11:  return 2039;
+      case 12:  return 4093;
+      case 13:  return 8191;
+      case 14:  return 16381;
+      case 15:  return 32749;
+      case 16:  return 65521;
+      case 17:  return 131063;
+      case 18:  return 262139;
+      case 19:  return 524269;
+      case 20:  return 1048573;
+      case 21:  return 2097143;
+      case 22:  return 4194301;
+      case 23:  return 8388593;
+
+      default:
+          assert (0);
+          return (1 << shift) - 1;
+    }
+}
+
 static struct strcache2_seg *
 strcache2_new_seg (struct strcache2 *cache, unsigned int minlen)
@@ -105,4 +143,5 @@
 strcache2_case_sensitive_hash_1 (const char *str, unsigned int len)
 {
+#if 1
   /* Note! This implementation is 18% faster than return_STRING_N_HASH_1
            when running the two 100 times over typical kBuild strings that
@@ -144,4 +183,51 @@
     hash = 0;
   return hash;
+#else
+# if 1
+  /* This is SDBM.  This specific form and loop unroll was benchmarked to
+     be 28% faster than return_STRING_N_HASH_1.  (Now the weird thing is
+     that putting the (ch) first in the assignment made it noticably slower.)
+
+     However, it is noticably slower in practice, most likely because of more
+     collisions. Hrmpf.
+     */
+#  define UPDATE_HASH(ch) hash = (hash << 6) + (hash << 16) - hash + (ch)
+  unsigned int hash = 0;
+# else
+ /* This is DJB2.  This specific form/unroll was benchmarked to be 27%
+    fast than return_STRING_N_HASH_1.
+
+    Ditto. 2x Hrmpf */
+#  define UPDATE_HASH(ch) hash = (hash << 5) + hash + (ch)
+  unsigned int hash = 5381;
+# endif
+  while (len >= 4)
+    {
+      UPDATE_HASH (str[0]);
+      UPDATE_HASH (str[1]);
+      UPDATE_HASH (str[2]);
+      UPDATE_HASH (str[3]);
+      str += 4;
+      len -= 4;
+    }
+  switch (len)
+    {
+      default:
+      case 0:
+        return hash;
+      case 1:
+        UPDATE_HASH (str[0]);
+        return hash;
+      case 2:
+        UPDATE_HASH (str[0]);
+        UPDATE_HASH (str[1]);
+        return hash;
+      case 3:
+        UPDATE_HASH (str[0]);
+        UPDATE_HASH (str[1]);
+        UPDATE_HASH (str[2]);
+        return hash;
+    }
+#endif
 }
 
@@ -506,10 +592,20 @@
   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;
+#endif
 
   /* Allocate a new hash table twice the size of the current. */
   cache->hash_size <<= 1;
+#ifdef STRCACHE2_USE_MASK
   cache->hash_mask <<= 1;
   cache->hash_mask |= 1;
+#else
+  for (hash_div = 1; (1U << hash_div) < cache->hash_size; hash_div++)
+    /* nothing */;
+  cache->hash_div = strcache2_find_prime(hash_div);
+#endif
   cache->rehash_count <<= 1;
   cache->hash_tab = dst_tab = (struct strcache2_entry **)
@@ -518,5 +614,9 @@
 
   /* 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)
     {
@@ -524,5 +624,9 @@
       if (entry)
         {
+#ifdef STRCACHE2_USE_MASK
           unsigned int dst = entry->hash1 & hash_mask;
+#else
+          unsigned int dst = entry->hash1 % hash_div;
+#endif
           if (dst_tab[dst])
             {
@@ -533,9 +637,17 @@
                   : 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
               while (dst_tab[dst])
                 {
                   dst += hash2;
+#ifdef STRCACHE2_USE_MASK
                   dst &= hash_mask;
+#else
+                  dst %= hash_div;
+#endif
                 }
             }
@@ -612,5 +724,5 @@
   /* Lookup the entry in the hash table, hoping for an
      early match. */
-  idx = hash1 & cache->hash_mask;
+  idx = STRCACHE2_MOD_IT(cache, hash1);
   entry = cache->hash_tab[idx];
   if (strcache2_is_equal (cache, entry, str, length, hash1))
@@ -624,5 +736,5 @@
       hash2 = strcache2_case_sensitive_hash_2 (str, length);
       idx += hash2;
-      idx &= cache->hash_mask;
+      idx = STRCACHE2_MOD_IT(cache, idx);
       entry = cache->hash_tab[idx];
       if (strcache2_is_equal (cache, entry, str, length, hash1))
@@ -635,5 +747,5 @@
             {
               idx += hash2;
-              idx &= cache->hash_mask;
+              idx = STRCACHE2_MOD_IT(cache, idx);
               entry = cache->hash_tab[idx];
               cache->collision_3rd_count++;
@@ -674,5 +786,5 @@
   /* Lookup the entry in the hash table, hoping for an
      early match. */
-  idx = hash1 & cache->hash_mask;
+  idx = STRCACHE2_MOD_IT(cache, hash1);
   entry = cache->hash_tab[idx];
   if (strcache2_is_equal (cache, entry, str, length, hash1))
@@ -687,5 +799,5 @@
           : strcache2_case_sensitive_hash_2 (str, length);
       idx += hash2;
-      idx &= cache->hash_mask;
+      idx = STRCACHE2_MOD_IT(cache, idx);
       entry = cache->hash_tab[idx];
       if (strcache2_is_equal (cache, entry, str, length, hash1))
@@ -698,5 +810,5 @@
             {
               idx += hash2;
-              idx &= cache->hash_mask;
+              idx = STRCACHE2_MOD_IT(cache, idx);
               entry = cache->hash_tab[idx];
               cache->collision_3rd_count++;
@@ -727,5 +839,5 @@
   /* Lookup the entry in the hash table, hoping for an
      early match. */
-  idx = hash1 & cache->hash_mask;
+  idx = STRCACHE2_MOD_IT(cache, hash1);
   entry = cache->hash_tab[idx];
   if (strcache2_is_equal (cache, entry, str, length, hash1))
@@ -739,5 +851,5 @@
       hash2 = strcache2_case_sensitive_hash_2 (str, length);
       idx += hash2;
-      idx &= cache->hash_mask;
+      idx = STRCACHE2_MOD_IT(cache, idx);
       entry = cache->hash_tab[idx];
       if (strcache2_is_equal (cache, entry, str, length, hash1))
@@ -750,5 +862,5 @@
             {
               idx += hash2;
-              idx &= cache->hash_mask;
+              idx = STRCACHE2_MOD_IT(cache, idx);
               entry = cache->hash_tab[idx];
               cache->collision_3rd_count++;
@@ -780,5 +892,5 @@
   /* Lookup the entry in the hash table, hoping for an
      early match. */
-  idx = hash1 & cache->hash_mask;
+  idx = STRCACHE2_MOD_IT(cache, hash1);
   entry = cache->hash_tab[idx];
   if (strcache2_is_iequal (cache, entry, str, length, hash1))
@@ -792,5 +904,5 @@
       hash2 = strcache2_case_insensitive_hash_2 (str, length);
       idx += hash2;
-      idx &= cache->hash_mask;
+      idx = STRCACHE2_MOD_IT(cache, idx);
       entry = cache->hash_tab[idx];
       if (strcache2_is_iequal (cache, entry, str, length, hash1))
@@ -803,5 +915,5 @@
             {
               idx += hash2;
-              idx &= cache->hash_mask;
+              idx = STRCACHE2_MOD_IT(cache, idx);
               entry = cache->hash_tab[idx];
               cache->collision_3rd_count++;
@@ -842,5 +954,5 @@
   /* Lookup the entry in the hash table, hoping for an
      early match. */
-  idx = hash1 & cache->hash_mask;
+  idx = STRCACHE2_MOD_IT(cache, hash1);
   entry = cache->hash_tab[idx];
   if (strcache2_is_iequal (cache, entry, str, length, hash1))
@@ -853,5 +965,5 @@
         hash2 = strcache2_case_insensitive_hash_2 (str, length);
       idx += hash2;
-      idx &= cache->hash_mask;
+      idx = STRCACHE2_MOD_IT(cache, idx);
       entry = cache->hash_tab[idx];
       if (strcache2_is_iequal (cache, entry, str, length, hash1))
@@ -864,5 +976,5 @@
             {
               idx += hash2;
-              idx &= cache->hash_mask;
+              idx = STRCACHE2_MOD_IT(cache, idx);
               entry = cache->hash_tab[idx];
               cache->collision_3rd_count++;
@@ -893,5 +1005,5 @@
   /* Lookup the entry in the hash table, hoping for an
      early match. */
-  idx = hash1 & cache->hash_mask;
+  idx = STRCACHE2_MOD_IT(cache, hash1);
   entry = cache->hash_tab[idx];
   if (strcache2_is_iequal (cache, entry, str, length, hash1))
@@ -905,5 +1017,5 @@
       hash2 = strcache2_case_insensitive_hash_2 (str, length);
       idx += hash2;
-      idx &= cache->hash_mask;
+      idx = STRCACHE2_MOD_IT(cache, idx);
       entry = cache->hash_tab[idx];
       if (strcache2_is_iequal (cache, entry, str, length, hash1))
@@ -916,5 +1028,5 @@
             {
               idx += hash2;
-              idx &= cache->hash_mask;
+              idx = STRCACHE2_MOD_IT(cache, idx);
               entry = cache->hash_tab[idx];
               cache->collision_3rd_count++;
@@ -1064,5 +1176,9 @@
   /* init the structure. */
   cache->case_insensitive = case_insensitive;
+#ifdef STRCACHE2_USE_MASK
   cache->hash_mask = (1U << hash_shift) - 1U;
+#else
+  cache->hash_div = strcache2_find_prime(hash_shift);
+#endif
   cache->count = 0;
   cache->lookup_count = 0;
@@ -1181,6 +1297,11 @@
     }
 
+#ifdef STRCACHE2_USE_MASK
   printf (_("%s  hash size = %u  mask = %#x  rehashed %u times  lookups = %lu\n"),
           prefix, cache->hash_size, cache->hash_mask, rehashes, cache->lookup_count);
+#else
+  printf (_("%s  hash size = %u  div = %#x  rehashed %u times  lookups = %lu\n"),
+          prefix, cache->hash_size, cache->hash_div, rehashes, cache->lookup_count);
+#endif
   printf (_("%s  hash collisions 1st = %lu (%u%%)  2nd = %lu (%u%%)  3rd = %lu (%u%%)\n"),
           prefix,
Index: trunk/src/kmk/strcache2.h
===================================================================
--- trunk/src/kmk/strcache2.h	(revision 1907)
+++ trunk/src/kmk/strcache2.h	(revision 1908)
@@ -31,4 +31,6 @@
 # error "include after make.h!"
 #endif
+
+#define STRCACHE2_USE_MASK 1
 
 /* string cache memory segment. */
@@ -71,5 +73,9 @@
     struct strcache2_entry **hash_tab;  /* The hash table. */
     int case_insensitive;               /* case insensitive or not. */
+#ifdef STRCACHE2_USE_MASK
     unsigned int hash_mask;             /* The AND mask matching hash_size.*/
+#else
+    unsigned int hash_div;              /* The number (prime) to mod by. */
+#endif
     unsigned long lookup_count;         /* The number of lookups. */
     unsigned long collision_1st_count;  /* The number of 1st level collisions. */
