summaryrefslogtreecommitdiff
path: root/Build/source/texk/kpathsea/hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/texk/kpathsea/hash.c')
-rw-r--r--Build/source/texk/kpathsea/hash.c269
1 files changed, 269 insertions, 0 deletions
diff --git a/Build/source/texk/kpathsea/hash.c b/Build/source/texk/kpathsea/hash.c
new file mode 100644
index 00000000000..bfae7eb2ee9
--- /dev/null
+++ b/Build/source/texk/kpathsea/hash.c
@@ -0,0 +1,269 @@
+/* hash.c: hash table operations.
+
+ Copyright 1994-2000, 2002, 2005, 2008, 2012, 2016, 2017-2019
+ Karl Berry & Olaf Weber.
+
+ This library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ This library 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
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with this library; if not, see <http://www.gnu.org/licenses/>. */
+
+#include <kpathsea/config.h>
+#include <kpathsea/c-ctype.h>
+
+#include <kpathsea/hash.h>
+#include <kpathsea/str-list.h>
+
+
+/* The hash function. We go for simplicity here. */
+
+/* All our hash tables are related to filenames. */
+
+static unsigned
+hash (hash_table_type table, const_string key)
+{
+ unsigned n = 0;
+
+ /* Our keys aren't often anagrams of each other, so no point in
+ weighting the characters. */
+ while (*key != 0)
+#if defined (WIN32) && defined (KPSE_COMPAT_API)
+ if (IS_KANJI(key)) {
+ n = (n + n + (unsigned)(*key++)) % table.size;
+ n = (n + n + (unsigned)(*key++)) % table.size;
+ } else
+#endif
+ n = (n + n + TRANSFORM (*key++)) % table.size;
+
+ return n;
+}
+
+/* Identical hash function as above, but does not normalize keys. */
+static unsigned
+hash_normalized (hash_table_type table, const_string key)
+{
+ unsigned n = 0;
+
+ /* Our keys aren't often anagrams of each other, so no point in
+ weighting the characters. */
+ while (*key != 0)
+ n = (n + n + (*key++)) % table.size;
+
+ return n;
+}
+
+hash_table_type
+hash_create (unsigned size)
+{
+ /* There was "static ..." since Oct3, 1997 to work around a gcc
+ optimizer bug for Alpha. That particular optimization bug
+ should be gone by now (Mar4, 2009).
+ */
+ hash_table_type ret;
+ unsigned b;
+ ret.buckets = XTALLOC (size, hash_element_type *);
+ ret.size = size;
+
+ /* calloc's zeroes aren't necessarily NULL, so be safe. */
+ for (b = 0; b <ret.size; b++)
+ ret.buckets[b] = NULL;
+
+ return ret;
+}
+
+/* Whether or not KEY is already in TABLE, insert it and VALUE. Do not
+ duplicate the strings, in case they're being purposefully shared. */
+
+void
+hash_insert (hash_table_type *table,
+ const_string key,
+ const_string value)
+{
+ unsigned n = hash (*table, key);
+ hash_element_type *new_elt = XTALLOC1 (hash_element_type);
+
+ new_elt->key = key;
+ new_elt->value = value;
+ new_elt->next = NULL;
+
+ /* Insert the new element at the end of the list. */
+ if (!table->buckets[n])
+ /* first element in bucket is a special case. */
+ table->buckets[n] = new_elt;
+ else
+ {
+ hash_element_type *loc = table->buckets[n];
+ while (loc->next) /* Find the last element. */
+ loc = loc->next;
+ loc->next = new_elt; /* Insert the new one after. */
+ }
+}
+
+/* Same as above, for normalized keys. */
+void
+hash_insert_normalized (hash_table_type *table,
+ const_string key,
+ const_string value)
+{
+ unsigned n = hash_normalized (*table, key);
+ hash_element_type *new_elt = XTALLOC1 (hash_element_type);
+
+ new_elt->key = key;
+ new_elt->value = value;
+ new_elt->next = NULL;
+
+ /* Insert the new element at the end of the list. */
+ if (!table->buckets[n])
+ /* first element in bucket is a special case. */
+ table->buckets[n] = new_elt;
+ else
+ {
+ hash_element_type *loc = table->buckets[n];
+ while (loc->next) /* Find the last element. */
+ loc = loc->next;
+ loc->next = new_elt; /* Insert the new one after. */
+ }
+}
+
+/* Remove a (KEY, VALUE) pair. */
+
+void
+hash_remove (hash_table_type *table, const_string key,
+ const_string value)
+{
+ hash_element_type *p;
+ hash_element_type *q;
+ unsigned n = hash (*table, key);
+
+ /* Find pair. */
+ for (q = NULL, p = table->buckets[n]; p != NULL; q = p, p = p->next)
+ if (FILESTRCASEEQ (key, p->key) && STREQ (value, p->value))
+ break;
+ if (p) {
+ /* We found something, remove it from the chain. */
+ if (q) q->next = p->next; else table->buckets[n] = p->next;
+ /* We cannot dispose of the contents. */
+ free (p);
+ }
+}
+
+/* Look up KEY in TABLE, and return NULL-terminated list of all matching
+ values (not copies), in insertion order. If none, return NULL. */
+
+const_string *
+hash_lookup (hash_table_type table, const_string key)
+{
+ hash_element_type *p;
+ cstr_list_type ret;
+ unsigned n = hash (table, key);
+ ret = cstr_list_init ();
+
+ /* Look at everything in this bucket. */
+ for (p = table.buckets[n]; p != NULL; p = p->next)
+ if (FILESTRCASEEQ (key, p->key))
+ cstr_list_add (&ret, p->value);
+
+ /* If we found anything, mark end of list with null. */
+ if (STR_LIST (ret))
+ cstr_list_add (&ret, NULL);
+
+#ifdef KPSE_DEBUG
+#if defined (KPSE_COMPAT_API)
+ {
+ kpathsea kpse = kpse_def;
+ if (KPATHSEA_DEBUG_P (KPSE_DEBUG_HASH))
+ {
+ DEBUGF1 ("hash_lookup(%s) =>", key);
+ if (!STR_LIST (ret))
+ fputs (" (nil)\n", stderr);
+ else
+ {
+ const_string *r;
+ for (r = STR_LIST (ret); *r; r++)
+ {
+ putc (' ', stderr);
+ if (kpse->debug_hash_lookup_int)
+#if defined(_WIN64)
+ fprintf (stderr, "%I64d", (__int64) *r);
+#else
+ fprintf (stderr, "%ld", (long) *r);
+#endif
+ else
+ fputs (*r, stderr);
+ }
+ putc ('\n', stderr);
+ }
+ fflush (stderr);
+ }
+ }
+#endif
+#endif
+
+ return STR_LIST (ret);
+}
+
+#ifdef KPSE_DEBUG
+/* We only print nonempty buckets, to decrease output volume. */
+
+void
+hash_print (hash_table_type table, boolean summary_only)
+{
+ unsigned b;
+ unsigned total_elements = 0, total_buckets = 0;
+
+ for (b = 0; b < table.size; b++) {
+ hash_element_type *bucket = table.buckets[b];
+
+ if (bucket) {
+ unsigned len = 1;
+ hash_element_type *tb;
+
+ total_buckets++;
+ if (!summary_only) fprintf (stderr, "%4d ", b);
+
+ for (tb = bucket->next; tb != NULL; tb = tb->next)
+ len++;
+ if (!summary_only) fprintf (stderr, ":%-5d", len);
+ total_elements += len;
+
+ if (!summary_only) {
+ for (tb = bucket; tb != NULL; tb = tb->next)
+ fprintf (stderr, " %s=>%s", tb->key, tb->value);
+ putc ('\n', stderr);
+ }
+ }
+ }
+
+ fprintf (stderr,
+ "%u buckets, %u nonempty (%u%%); %u entries, average chain %.1f.\n",
+ table.size,
+ total_buckets,
+ 100 * total_buckets / table.size,
+ total_elements,
+ total_buckets ? total_elements / (double) total_buckets : 0.0);
+}
+#endif
+
+#if KPATHSEA_CAN_FREE
+void
+hash_free (hash_table_type table)
+{
+ struct hash_element_struct *p, *q;
+ p = (struct hash_element_struct *)table.buckets;
+ while (p != NULL) {
+ q = p->next;
+ free ((char *)p->key);
+ free ((char *)p->value);
+ free (p);
+ p = q;
+ }
+}
+#endif