summaryrefslogtreecommitdiffstats
path: root/src/kmk/strcache2.h
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-11 08:21:29 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-11 08:21:29 +0000
commit29cd838eab01ed7110f3ccb2e8c6a35c8a31dbcc (patch)
tree63ef546b10a81d461e5cf5ed9e98a68cd7dee1aa /src/kmk/strcache2.h
parentInitial commit. (diff)
downloadkbuild-29cd838eab01ed7110f3ccb2e8c6a35c8a31dbcc.tar.xz
kbuild-29cd838eab01ed7110f3ccb2e8c6a35c8a31dbcc.zip
Adding upstream version 1:0.1.9998svn3589+dfsg.upstream/1%0.1.9998svn3589+dfsg
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/kmk/strcache2.h')
-rw-r--r--src/kmk/strcache2.h182
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
+