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, 0 insertions, 269 deletions
diff --git a/Build/source/texk/kpathsea/hash.c b/Build/source/texk/kpathsea/hash.c
deleted file mode 100644
index bfae7eb2ee9..00000000000
--- a/Build/source/texk/kpathsea/hash.c
+++ /dev/null
@@ -1,269 +0,0 @@
-/* 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