Changeset 1870 in kBuild for trunk/src/kmk

Timestamp:

Oct 16, 2008 11:15:30 PM (16 years ago)

Author:

bird

Message:

kmk: replaced strcache with strcacahe2.

Location:

trunk/src/kmk

Files:

• Makefile.am (modified) (1 diff)
• Makefile.kmk (modified) (1 diff)
• expand.c (modified) (1 diff)
• incdep.c (modified) (1 diff)
• make.h (modified) (2 diffs)
• strcache.c (modified) (3 diffs)
• strcache2.c (modified) (27 diffs)
• strcache2.h (modified) (3 diffs)

trunk/src/kmk/Makefile.am

@@ -110 +110 @@
         -DCONFIG_WITH_2ND_TARGET_EXPANSION \
         -DCONFIG_WITH_ALLOC_CACHES \
+        -DCONFIG_WITH_STRCACHE2 \
         \
         -DKMK \

trunk/src/kmk/Makefile.kmk

@@ -140 +140 @@
         CONFIG_WITH_2ND_TARGET_EXPANSION \
         CONFIG_WITH_ALLOC_CACHES \
+        CONFIG_WITH_STRCACHE2 \
         \
         KMK \

trunk/src/kmk/expand.c

@@ -990 +990 @@
   variable_buffer = 0;
 
+  assert (v->length == strlen (v->name));
   val = variable_append (v->name, strlen (v->name), current_variable_set_list);
   variable_buffer_output (val, "", 1);

trunk/src/kmk/incdep.c

@@ -850 +850 @@
       entry->str[len] = '\0';
       entry->length = len;
-      strcache_prehash_str (entry->str, &entry->hash1, &entry->hash2);
+      strcache_prehash_str (entry->str, len, &entry->hash1, &entry->hash2);
 
       ret = (const char *)entry;

trunk/src/kmk/make.h

@@ -586 +586 @@
 void strcache_init (void);
 void strcache_print_stats (const char *prefix);
+#ifndef CONFIG_WITH_STRCACHE2
 int strcache_iscached (const char *str);
 const char *strcache_add (const char *str);
 const char *strcache_add_len (const char *str, int len);
 int strcache_setbufsize (int size);
-#ifdef CONFIG_WITH_INCLUDEDEP
+# ifdef CONFIG_WITH_INCLUDEDEP
 const char *strcache_add_prehashed (const char *str, int len,
                                     unsigned long hash1, unsigned long hash2);
-void strcache_prehash_str (const char *str, unsigned long *hash1p,
+void strcache_prehash_str (const char *str, unsigned int len, unsigned long *hash1p,
                            unsigned long *hash2p);
 #endif
@@ -633 +634 @@
 }
 
-#endif
+# endif /* CONFIG_WITH_VALUE_LENGTH*/
+
+#else  /* CONFIG_WITH_STRCACHE2 */
+
+# include "strcache2.h"
+extern struct strcache2 file_strcache;
+
+# define strcache_iscached(str)     strcache2_is_cached(&file_strcache, str)
+# define strcache_add(str)          strcache2_add(&file_strcache, str, strlen (str))
+# define strcache_add_len(str, len) strcache2_add(&file_strcache, str, len)
+# ifdef CONFIG_WITH_INCLUDEDEP
+#  define strcache_add_prehashed(str, len, hash1, hash2) \
+    strcache2_add_hashed(&file_strcache, str, len, hash1, hash2)
+#  ifdef HAVE_CASE_INSENSITIVE_FS
+#   define strcache_prehash_str(str, length, hash1p, hash2p) \
+     do { *(hash1p) = strcache2_hash_istr (str, length, (hash2p)); } while (0)
+#  else
+#   define strcache_prehash_str(str, length, hash1p, hash2p) \
+     do { *(hash1p) = strcache2_hash_str (str, length, (hash2p)); } while (0)
+#  endif
+# endif /* CONFIG_WITH_INCLUDEDEP */
+# ifdef CONFIG_WITH_VALUE_LENGTH
+#  define strcache_get_len(str)     strcache2_get_len(&file_strcache, str)
+#  define strcache_get_hash1(str)   strcache2_get_hash1(&file_strcache, str)
+#  define strcache_get_hash2(str)   strcache2_get_hash2(&file_strcache, str)
+# endif /* CONFIG_WITH_VALUE_LENGTH */
+
+#endif /* CONFIG_WITH_STRCACHE2 */
 
 #ifdef  HAVE_VFORK_H

trunk/src/kmk/strcache.c

@@ -16 +16 @@
 
 #include "make.h"
+#ifndef CONFIG_WITH_STRCACHE2
 
 #include <assert.h>
 
 #include "hash.h"
+
 
 /* The size (in bytes) of each cache buffer.
@@ -381 +383 @@
 /* Performs the prehashing for use with strcache_add_prehashed(). */
 void
-strcache_prehash_str (const char *str, unsigned long *hash1p,
+strcache_prehash_str (const char *str, unsigned int len, unsigned long *hash1p,
                       unsigned long *hash2p)
 {
+  (void)len;
   *hash1p = str_hash_1 (str);
   *hash2p = str_hash_2 (str);
@@ -460 +463 @@
   hash_print_stats (&strings, stdout);
 }
+
+#else /* CONFIG_WITH_STRCACHE2 */
+
+#include "strcache2.h"
+
+/* The file string cache. */
+struct strcache2 file_strcache;
+
+void strcache_init (void)
+{
+  strcache2_init(&file_strcache,
+                 "file",        /* name */
+                 65536,         /* hash size */
+                 0,             /* default segment size*/
+#ifdef HAVE_CASE_INSENSITIVE_FS
+                 1,             /* case insensitive */
+#else
+                 0,             /* case insensitive */
+#endif
+                 0);            /* thread safe */
+}
+
+void
+strcache_print_stats (const char *prefix)
+{
+  strcache2_print_stats (&file_strcache, prefix);
+}
+
+
+#endif /* CONFIG_WITH_STRCACHE2 */

trunk/src/kmk/strcache2.c

@@ -56 +56 @@
 *******************************************************************************/
 /* The default size of a memory segment (1MB). */
-#define STRCACHE2_SEG_SIZE            (1024U*1024U)
-/* The initial hash table size (number of entries). Power of two. */
-#define STRCACHE2_INITIAL_SIZE        0x10000U
-
-
-/*******************************************************************************
-*   Global Variables                                                           *
-*******************************************************************************/
-/* the deleted filler hash table entry. */
-static struct strcache2_entry deleted_entry;
+#define STRCACHE2_SEG_SIZE          (1024U*1024U)
+/* The default hash table shift (hash size give as a power of two). */
+#define STRCACHE2_HASH_SHIFT        16
+
+
 
 
@@ -74 +69 @@
   size_t size;
 
-  size = STRCACHE2_SEG_SIZE;
+  size = cache->def_seg_size;
   if (size < (size_t)minlen + sizeof (struct strcache2_seg))
     {
@@ -99 +94 @@
     {
       unsigned int ch0 = *str++;
-      hash = len--;
+      hash = 0;
+      len--;
       while (len >= 2)
         {
@@ -137 +133 @@
     {
       unsigned int ch0 = *str++;
-      hash = len--;
+      hash = 0;
+      len--;
       while (len >= 2)
         {
@@ -164 +161 @@
     }
   else
-    hash = 0;
-  return hash | 1;
+    hash = 1;
+  hash |= 1;
+  return hash;
 }
 
@@ -176 +174 @@
       unsigned int ch0 = *str++;
       ch0 = tolower (ch0);
-      hash = len--;
+      hash = 0;
+      len--;
       while (len >= 2)
         {
@@ -218 +217 @@
       unsigned int ch0 = *str++;
       ch0 = tolower (ch0);
-      hash = len--;
+      hash = 0;
+      len--;
       while (len >= 2)
         {
@@ -248 +248 @@
     }
   else
-    hash = 0;
+    hash = 1;
+  hash |= 1;
   return hash;
 }
@@ -258 +259 @@
   /* the simple stuff first. */
   if (   entry == NULL
-      || entry == &deleted_entry
       || entry->hash1 != hash1
       || entry->length != length)
@@ -264 +264 @@
 
   return !cache->case_insensitive
-    ? memcmp (cache + 1, str, length) == 0
+    ? memcmp (entry + 1, str, length) == 0
 #if defined(_MSC_VER) || defined(__OS2__)
-    : _memicmp (cache + 1, str, length) == 0
+    : _memicmp (entry + 1, str, length) == 0
 #else
-    : strncasecmp ((const char *)(cache + 1), str, length) == 0
+    : strncasecmp ((const char *)(entry + 1), str, length) == 0
 #endif
     ;
@@ -276 +276 @@
 strcache2_rehash (struct strcache2 *cache)
 {
-  /* TODO */
-  struct strcache2 **ptr = (struct strcache2 **)1;
-  assert(0);
-  *ptr = cache;
+  unsigned int src = cache->hash_size;
+  struct strcache2_entry **src_tab = cache->hash_tab;
+  struct strcache2_entry **dst_tab;
+  unsigned int hash_mask;
+
+  /* Allocate a new hash table twice the size of the current. */
+  cache->hash_size <<= 1;
+  cache->hash_mask <<= 1;
+  cache->hash_mask |= 1;
+  cache->rehash_count <<= 1;
+  cache->hash_tab = dst_tab = (struct strcache2_entry **)
+    xmalloc (cache->hash_size * sizeof (struct strcache2_entry *));
+  memset (dst_tab, '\0', cache->hash_size * sizeof (struct strcache2_entry *));
+
+  /* Copy the entries from the old to the new hash table. */
+  hash_mask = cache->hash_mask;
+  while (src-- > 0)
+    {
+      struct strcache2_entry *entry = src_tab[src];
+      if (entry)
+        {
+          unsigned int dst = entry->hash1 & hash_mask;
+          if (dst_tab[dst])
+            {
+              unsigned int hash2 = entry->hash2;
+              if (!hash2)
+                entry->hash2 = hash2 = cache->case_insensitive
+                  ? strcache2_case_insensitive_hash_2 ((const char *)(entry + 1), entry->length)
+                  : strcache2_case_sensitive_hash_2 ((const char *)(entry + 1), entry->length);
+              dst += hash2;
+              dst &= hash_mask;
+              while (dst_tab[dst])
+                {
+                  dst += hash2;
+                  dst &= hash_mask;
+                }
+            }
+
+          dst_tab[dst] = entry;
+        }
+    }
+
+  /* That's it, just free the old table and we're done. */
+  free (src_tab);
 }
 
@@ -344 +384 @@
   /* Lookup the entry in the hash table, hoping for an
      early match. */
-
-  idx = hash1 / cache->hash_size;
+  idx = hash1 & cache->hash_mask;
   entry = cache->hash_tab[idx];
   if (strcache2_is_equal (cache, entry, str, length, hash1))
@@ -353 +392 @@
   else
     {
-      unsigned int deleted_idx = entry == &deleted_entry ? idx : ~0U;
-      cache->collision_count++;
+      cache->collision_1st_count++;
 
       hash2 = cache->case_insensitive
@@ -360 +398 @@
         : strcache2_case_sensitive_hash_2 (str, length);
       idx += hash2;
-      idx /= cache->hash_size;
+      idx &= cache->hash_mask;
       entry = cache->hash_tab[idx];
       if (strcache2_is_equal (cache, entry, str, length, hash1))
@@ -367 +405 @@
       if (entry)
         {
+          cache->collision_2nd_count++;
           do
             {
-              if (deleted_idx == ~0U && entry == &deleted_entry)
-                deleted_idx = idx;
-
               idx += hash2;
-              idx /= cache->hash_size;
+              idx &= cache->hash_mask;
               entry = cache->hash_tab[idx];
+              cache->collision_3rd_count++;
               if (strcache2_is_equal (cache, entry, str, length, hash1))
                 return (const char *)(entry + 1);
@@ -380 +417 @@
           while (entry);
         }
-      if (deleted_idx != ~0U)
-        idx = deleted_idx;
+    }
+
+  /* Not found, add it at IDX. */
+  return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
+}
+
+/* The public add/lookup string interface for prehashed strings.
+   Use strcache2_hash_str to calculate the hash of a string. */
+const char *
+strcache2_add_hashed (struct strcache2 *cache, const char *str, unsigned int length,
+                      unsigned int hash1, unsigned int hash2)
+{
+  struct strcache2_entry const *entry;
+  unsigned int idx;
+#ifndef NDEBUG
+  unsigned correct_hash;
+
+  correct_hash = cache->case_insensitive
+               ? strcache2_case_insensitive_hash_1 (str, length)
+               : strcache2_case_sensitive_hash_1 (str, length);
+  MY_ASSERT_MSG (hash1 == correct_hash, ("%#x != %#x\n", hash1, correct_hash));
+  if (hash2)
+    {
+      correct_hash = cache->case_insensitive
+                   ? strcache2_case_insensitive_hash_2 (str, length)
+                   : strcache2_case_sensitive_hash_2 (str, length);
+      MY_ASSERT_MSG (hash2 == correct_hash, ("%#x != %#x\n", hash2, correct_hash));
+    }
+#endif /* NDEBUG */
+
+  cache->lookup_count++;
+
+  /* Lookup the entry in the hash table, hoping for an
+     early match. */
+  idx = hash1 & cache->hash_mask;
+  entry = cache->hash_tab[idx];
+  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);
+      idx += hash2;
+      idx &= cache->hash_mask;
+      entry = cache->hash_tab[idx];
+      if (strcache2_is_equal (cache, entry, str, length, hash1))
+        return (const char *)(entry + 1);
+
+      if (entry)
+        {
+          cache->collision_2nd_count++;
+          do
+            {
+              idx += hash2;
+              idx &= cache->hash_mask;
+              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);
+        }
     }
 
@@ -393 +494 @@
 {
   /* Check mandatory alignment first. */
-
   if (!((size_t)str & (sizeof (void *) - 1)))
     {
       /* Check the segment list and consider the question answered if the
          string is within one of them. (Could check it more thoroughly...) */
-
       struct strcache2_seg const *seg;
-      for (seg = cache->seg_head; seg; seg++)
+      for (seg = cache->seg_head; seg; seg = seg->next)
         if ((size_t)(str - seg->start) < seg->size)
             return 1;
@@ -451 +550 @@
         ? strcache2_case_insensitive_hash_2 (str, entry->length)
         : strcache2_case_sensitive_hash_2 (str, entry->length);
-      if (hash != entry->hash1)
+      if (hash != entry->hash2)
         {
           fprintf (stderr,
@@ -475 +574 @@
 }
 
+/* Calculates the case sensitive hash values of the string.
+   The first hash is returned, the other is put at HASH2P. */
+unsigned int strcache2_hash_str (const char *str, unsigned int length, unsigned int *hash2p)
+{
+  *hash2p = strcache2_case_sensitive_hash_2 (str, length);
+  return    strcache2_case_sensitive_hash_1 (str, length);
+}
+
+/* Calculates the case insensitive hash values of the string.
+   The first hash is returned, the other is put at HASH2P. */
+unsigned int strcache2_hash_istr (const char *str, unsigned int length, unsigned int *hash2p)
+{
+  *hash2p = strcache2_case_insensitive_hash_2 (str, length);
+  return    strcache2_case_insensitive_hash_1 (str, length);
+}
+
+
 /* List of initialized string caches. */
 static struct strcache2 *strcache_head;
@@ -480 +596 @@
 /* Initalizes a new cache. */
 void
-strcache2_init (struct strcache2 *cache, const char *name,
-                int case_insensitive, int thread_safe)
-{
+strcache2_init (struct strcache2 *cache, const char *name, unsigned int size,
+                unsigned int def_seg_size, int case_insensitive, int thread_safe)
+{
+  unsigned hash_shift;
   assert (!thread_safe);
 
+  /* calc the size as a power of two */
+  if (!size)
+    hash_shift = STRCACHE2_HASH_SHIFT;
+  else
+    {
+      assert (size <= (~0U / 2 + 1));
+      for (hash_shift = 8; (1U << hash_shift) < size; hash_shift++)
+        /* nothing */;
+    }
+
+  /* adjust the default segment size */
+  if (!def_seg_size)
+    def_seg_size = STRCACHE2_SEG_SIZE;
+  else if (def_seg_size < sizeof (struct strcache2_seg) * 10)
+    def_seg_size = sizeof (struct strcache2_seg) * 10;
+  else if ((def_seg_size & 0xfff) < 0xf00)
+    def_seg_size = ((def_seg_size + 0xfff) & ~0xfffU);
+
+
+  /* init the structure. */
   cache->case_insensitive = case_insensitive;
-  cache->hash_size = STRCACHE2_INITIAL_SIZE;
+  cache->hash_mask = (1U << hash_shift) - 1U;
   cache->count = 0;
-  cache->rehash_count = STRCACHE2_INITIAL_SIZE / 4 * 3;
-  cache->collision_count = 0;
   cache->lookup_count = 0;
+  cache->collision_1st_count = 0;
+  cache->collision_2nd_count = 0;
+  cache->collision_3rd_count = 0;
+  cache->rehash_count = (1U << hash_shift) / 4 * 3;   /* rehash at 75% */
+  cache->init_size = 1U << hash_shift;
+  cache->hash_size = 1U << hash_shift;
+  cache->def_seg_size = def_seg_size;
   cache->lock = NULL;
-  cache->seg_head = NULL;
   cache->name = name;
 
+  /* allocate the hash table and first segment. */
   cache->hash_tab = (struct strcache2_entry **)
-    xmalloc (STRCACHE2_INITIAL_SIZE * sizeof (struct strcache2_entry *));
-  memset (cache->hash_tab, '\0', STRCACHE2_INITIAL_SIZE * sizeof (struct strcache2_entry *));
+    xmalloc (cache->init_size * sizeof (struct strcache2_entry *));
+  memset (cache->hash_tab, '\0', cache->init_size * sizeof (struct strcache2_entry *));
   strcache2_new_seg (cache, 0);
 
@@ -512 +654 @@
 {
   /* unlink it */
-
   if (strcache_head == cache)
     strcache_head = cache->next;
@@ -525 +666 @@
 
   /* free the memory segments */
-
   do
     {
@@ -535 +675 @@
 
   /* free the hash and clear the structure. */
-
   free (cache->hash_tab);
   memset (cache, '\0', sizeof (struct strcache2));
 }
 
-
+/* Print statistics a string cache. */
 void
 strcache2_print_stats (struct strcache2 *cache, const char *prefix)
@@ -560 +699 @@
 
   /* Segment statistics. */
-
   for (seg = cache->seg_head; seg; seg = seg->next)
     {
@@ -570 +708 @@
     }
   seg_avg_bytes = seg_total_bytes / seg_count;
-  printf (_("%s %u segments: total = %lu / max = %lu / avg = %lu / def = %u  avail = %lu\n"),
+  printf (_("%s  %u segments: total = %lu / max = %lu / avg = %lu / def = %u  avail = %lu\n"),
           prefix, seg_count, seg_total_bytes, seg_max_bytes, seg_avg_bytes,
-          STRCACHE2_SEG_SIZE, seg_avail_bytes);
+          cache->def_seg_size, seg_avail_bytes);
 
   /* String statistics. */
-
   idx = cache->hash_size;
   while (idx-- > 0)
     {
       struct strcache2_entry const *entry = cache->hash_tab[idx];
-      if (entry && entry != &deleted_entry)
+      if (entry)
         {
           unsigned int length = entry->length;
@@ -591 +728 @@
     }
   str_avg_len = cache->count ? str_total_len / cache->count : 0;
-  printf (_("%s %u strings: total len = %lu / max = %ul / avg = %ul / min = %ul\n"),
+  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);
 
   /* Hash statistics. */
-
-  idx = STRCACHE2_INITIAL_SIZE;
+  idx = cache->init_size;
   rehashes = 0;
   while (idx < cache->hash_size)
@@ -604 +740 @@
     }
 
-  printf (_("%s hash size = %u  lookups / collisions = %lu / %lu (%u%%)  %u rehashes\n"),
-          prefix, cache->hash_size, cache->lookup_count, cache->collision_count,
-          (unsigned int)((float)cache->collision_count / cache->lookup_count),
-          rehashes);
-
+  printf (_("%s  hash size = %u  mask = %#x  rehashed %u times  lookups = %lu\n"),
+          prefix, cache->hash_size, cache->hash_mask, rehashes, cache->lookup_count);
+  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));
 }
 

trunk/src/kmk/strcache2.h

@@ -51 +51 @@
     struct strcache2_entry **hash_tab;  /* The hash table. */
     int case_insensitive;               /* case insensitive or not. */
-    unsigned int hash_size;             /* The hash table size. */
+    unsigned int hash_mask;             /* The AND mask matching hash_size.*/
+    unsigned long lookup_count;         /* The number of lookups. */
+    unsigned long collision_1st_count;  /* The number of 1st level collisions. */
+    unsigned long collision_2nd_count;  /* The number of 2nd level collisions. */
+    unsigned long collision_3rd_count;  /* The number of 3rd level collisions. */
     unsigned int count;                 /* Number entries in the cache. */
     unsigned int rehash_count;          /* When to rehash the table. */
-    unsigned long collision_count;      /* The number of collisions. */
-    unsigned long lookup_count;         /* The number of lookups. */
+    unsigned int init_size;             /* The initial hash table size. */
+    unsigned int hash_size;             /* The hash table size. */
+    unsigned int def_seg_size;          /* The default segment size. */
     void *lock;                         /* The lock handle. */
     struct strcache2_seg *seg_head;     /* The memory segment list. */
@@ -63 +68 @@
 
 
-void strcache2_init (struct strcache2 *cache, const char *name, int case_insensitive, int thread_safe);
+void strcache2_init (struct strcache2 *cache, const char *name, unsigned int size,
+                     unsigned int def_seg_size, int case_insensitive, int thread_safe);
 void strcache2_term (struct strcache2 *cache);
 void strcache2_print_stats (struct strcache2 *cache, const char *prefix);
 void strcache2_print_stats_all (const char *prefix);
 const char *strcache2_add (struct strcache2 *cache, const char *str, unsigned int length);
+const char *strcache2_add_hashed (struct strcache2 *cache, const char *str, unsigned int length,
+                                  unsigned int hash1, unsigned int hash2);
+int strcache2_is_cached (struct strcache2 *cache, const char *str);
 int strcache2_verify_entry (struct strcache2 *cache, const char *str);
 unsigned int strcache2_get_hash2_fallback (struct strcache2 *cache, const char *str);
+unsigned int strcache2_hash_str (const char *str, unsigned int length, unsigned int *hash2p);
+unsigned int strcache2_hash_istr (const char *str, unsigned int length, unsigned int *hash2p);
 
 /* Get the hash table entry pointer. */
@@ -100 +111 @@
 {
   unsigned int hash2 = strcache2_get_entry (cache, str)->hash2;
-  if (hash2)
+  if (!hash2)
     hash2 = strcache2_get_hash2_fallback (cache, str);
   return hash2;