Adding upstream version 1:0.1.9998svn3589+dfsg.upstream/1%0.1.9998svn3589+dfsg

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 182 insertions, 0 deletions

diff --git a/src/kmk/strcache2.h b/src/kmk/strcache2.h
new file mode 100644
index 0000000..8ef8650
--- /dev/null
+++ b/src/kmk/strcache2.h
@@ -0,0 +1,182 @@
+/* $Id: strcache2.h 2413 2010-09-11 17:43:04Z bird $ */
+/** @file
+ * strcache - New string cache.
+ */
+
+/*
+ * Copyright (c) 2006-2010 knut st. osmundsen <bird-kBuild-spamx@anduin.net>
+ *
+ * This file is part of kBuild.
+ *
+ * kBuild is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * kBuild is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with kBuild.  If not, see <http://www.gnu.org/licenses/>
+ *
+ */
+
+#ifndef ___strcache2_h
+#define ___strcache2_h
+
+#ifndef CHAR_BIT
+# error "include after make.h!"
+#endif
+
+#define STRCACHE2_USE_MASK 1
+
+/* string cache memory segment. */
+struct strcache2_seg
+{
+    struct strcache2_seg *next;         /* The next cache segment. */
+    char *start;                        /* The first byte in the segment. */
+    size_t size;                        /* The size of the segment. */
+    size_t avail;                       /* The number of available bytes. */
+    char *cursor;                       /* Allocation cursor. */
+};
+
+/* string cache hash table entry. */
+struct strcache2_entry
+{
+    struct strcache2_entry *next;       /* Collision chain. */
+    void *user;
+    unsigned int hash;
+    unsigned int length;
+};
+
+/* The entry alignment, cacheline size if it's known & sensible.
+
+   On x86/AMD64 we assume a 64-byte cacheline size.  As it is difficult to
+   guess other right now, these default 16 chars as that shouldn't cause
+   much trouble, even if it not the most optimial value.  Override, or modify
+   for other platforms.  */
+#ifndef STRCACHE2_ENTRY_ALIGN_SHIFT
+# if defined (__i386__) || defined(__x86_64__)
+#  define STRCACHE2_ENTRY_ALIGN_SHIFT    6
+# else
+#  define STRCACHE2_ENTRY_ALIGN_SHIFT    4
+# endif
+#endif
+#define STRCACHE2_ENTRY_ALIGNMENT       (1 << STRCACHE2_ENTRY_ALIGN_SHIFT)
+
+
+struct strcache2
+{
+    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. */
+    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 collision_count;       /* Number of entries in chains. */
+    unsigned int rehash_count;          /* When to rehash the table. */
+    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. */
+    struct strcache2 *next;             /* The next string cache. */
+    const char *name;                   /* Cache name. */
+};
+
+
+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_iadd (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 hash);
+const char *strcache2_iadd_hashed (struct strcache2 *cache, const char *str,
+                                   unsigned int length, unsigned int hash);
+const char *strcache2_lookup (struct strcache2 *cache, const char *str, unsigned int length);
+const char *strcache2_ilookup (struct strcache2 *cache, const char *str, unsigned int length);
+#ifdef HAVE_CASE_INSENSITIVE_FS
+# define strcache2_add_file         strcache2_iadd
+# define strcache2_add_hashed_file  strcache2_iadd_hashed
+# define strcache2_lookup_file      strcache2_ilookup
+#else
+# define strcache2_add_file         strcache2_add
+# define strcache2_add_hashed_file  strcache2_add_hashed
+# define strcache2_lookup_file      strcache2_lookup
+#endif
+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. */
+MY_INLINE struct strcache2_entry const *
+strcache2_get_entry (struct strcache2 *cache, const char *str)
+{
+#ifndef NDEBUG
+  strcache2_verify_entry (cache, str);
+#endif
+  return (struct strcache2_entry const *)str - 1;
+}
+
+/* Get the string length. */
+MY_INLINE unsigned int
+strcache2_get_len (struct strcache2 *cache, const char *str)
+{
+  return strcache2_get_entry (cache, str)->length;
+}
+
+/* Get the first hash value for the string. */
+MY_INLINE unsigned int
+strcache2_get_hash (struct strcache2 *cache, const char *str)
+{
+  return strcache2_get_entry (cache, str)->hash;
+}
+
+/* Calc the pointer hash value for the string.
+
+   This takes the string address, shift out the bits that are always zero
+   due to alignment, and then returns the unsigned integer value of it.
+
+   The results from using this is generally better than for any of the
+   other hash values.  It is also sligtly faster code as it does not
+   involve any memory accesses, just a right SHIFT and an optional AND. */
+MY_INLINE unsigned int
+strcache2_calc_ptr_hash (struct strcache2 *cache, const char *str)
+{
+  (void)cache;
+  return (size_t)str >> STRCACHE2_ENTRY_ALIGN_SHIFT;
+}
+
+/* Get the user value for the string. */
+MY_INLINE void *
+strcache2_get_user_val (struct strcache2 *cache, const char *str)
+{
+  return strcache2_get_entry (cache, str)->user;
+}
+
+/* Get the user value for the string. */
+MY_INLINE void
+strcache2_set_user_val (struct strcache2 *cache, const char *str, void *value)
+{
+  struct strcache2_entry *entry = (struct strcache2_entry *)str - 1;
+#ifndef NDEBUG
+  strcache2_verify_entry (cache, str);
+#endif
+  entry->user = value;
+}
+
+#endif
+