git.oblomov.eu Git - mplib/blob - src/texk/kpathsea/hash.c

   1 /* hash.c: hash table operations.
   2
   3    Copyright 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2002, 2005, 2008
   4    Karl Berry & Olaf Weber.
   5
   6    This library is free software; you can redistribute it and/or
   7    modify it under the terms of the GNU Lesser General Public
   8    License as published by the Free Software Foundation; either
   9    version 2.1 of the License, or (at your option) any later version.
  10
  11    This library is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14    Lesser General Public License for more details.
  15
  16    You should have received a copy of the GNU Lesser General Public License
  17    along with this library; if not, see <http://www.gnu.org/licenses/>.  */
  18
  19 #include <kpathsea/config.h>
  20 #include <kpathsea/c-ctype.h>
  21
  22 #include <kpathsea/hash.h>
  23 #include <kpathsea/str-list.h>
  24
  25
  26 /* The hash function.  We go for simplicity here.  */
  27
  28 /* All our hash tables are related to filenames.  */
  29 #ifdef MONOCASE_FILENAMES
  30 #if defined(WIN32) && !defined(__i386_pc_gnu__)
  31 /* This is way faster under Win32. */
  32 #define TRANSFORM(x) ((unsigned)CharLower((LPTSTR)(BYTE)(x)))
  33 #else
  34 #define TRANSFORM(x) (tolower(x))
  35 #endif
  36 #else
  37 #define TRANSFORM(x) (x)
  38 #endif
  39
  40 static unsigned
  41 hash P2C(hash_table_type, table,  const_string, key)
  42 {
  43   unsigned n = 0;
  44
  45   /* Our keys aren't often anagrams of each other, so no point in
  46      weighting the characters.  */
  47   while (*key != 0)
  48     n = (n + n + TRANSFORM (*key++)) % table.size;
  49
  50   return n;
  51 }
  52
  53 /* Identical has function as above, but does not normalize keys. */
  54 static unsigned
  55 hash_normalized P2C(hash_table_type, table,  const_string, key)
  56 {
  57   unsigned n = 0;
  58
  59   /* Our keys aren't often anagrams of each other, so no point in
  60      weighting the characters.  */
  61   while (*key != 0)
  62     n = (n + n + (*key++)) % table.size;
  63
  64   return n;
  65 }
  66 \f
  67 hash_table_type
  68 hash_create P1C(unsigned, size)
  69 {
  70   /* hash_table_type ret; changed into "static ..." to work around gcc
  71      optimizer bug for Alpha.  */
  72   static hash_table_type ret;
  73   unsigned b;
  74   ret.buckets = XTALLOC (size, hash_element_type *);
  75   ret.size = size;
  76
  77   /* calloc's zeroes aren't necessarily NULL, so be safe.  */
  78   for (b = 0; b <ret.size; b++)
  79     ret.buckets[b] = NULL;
  80
  81   return ret;
  82 }
  83 \f
  84 /* Whether or not KEY is already in MAP, insert it and VALUE.  Do not
  85    duplicate the strings, in case they're being purposefully shared.  */
  86
  87 void
  88 hash_insert P3C(hash_table_type *, table,
  89                 const_string, key,
  90                 const_string, value)
  91 {
  92   unsigned n = hash (*table, key);
  93   hash_element_type *new_elt = XTALLOC1 (hash_element_type);
  94
  95   new_elt->key = key;
  96   new_elt->value = value;
  97   new_elt->next = NULL;
  98
  99   /* Insert the new element at the end of the list.  */
 100   if (!table->buckets[n])
 101     /* first element in bucket is a special case.  */
 102     table->buckets[n] = new_elt;
 103   else
 104     {
 105       hash_element_type *loc = table->buckets[n];
 106       while (loc->next)         /* Find the last element.  */
 107         loc = loc->next;
 108       loc->next = new_elt;      /* Insert the new one after.  */
 109     }
 110 }
 111
 112 /* Same as above, for normalized keys. */
 113 void
 114 hash_insert_normalized P3C(hash_table_type *, table,
 115                            const_string, key,
 116                            const_string, value)
 117 {
 118   unsigned n = hash_normalized (*table, key);
 119   hash_element_type *new_elt = XTALLOC1 (hash_element_type);
 120
 121   new_elt->key = key;
 122   new_elt->value = value;
 123   new_elt->next = NULL;
 124
 125   /* Insert the new element at the end of the list.  */
 126   if (!table->buckets[n])
 127     /* first element in bucket is a special case.  */
 128     table->buckets[n] = new_elt;
 129   else
 130     {
 131       hash_element_type *loc = table->buckets[n];
 132       while (loc->next)         /* Find the last element.  */
 133         loc = loc->next;
 134       loc->next = new_elt;      /* Insert the new one after.  */
 135     }
 136 }
 137 \f
 138 /* Remove a (KEY, VALUE) pair.  */
 139
 140 void
 141 hash_remove P3C(hash_table_type *, table,  const_string, key,
 142                 const_string, value)
 143 {
 144   hash_element_type *p;
 145   hash_element_type *q;
 146   unsigned n = hash (*table, key);
 147
 148   /* Find pair.  */
 149   for (q = NULL, p = table->buckets[n]; p != NULL; q = p, p = p->next)
 150     if (FILESTRCASEEQ (key, p->key) && STREQ (value, p->value))
 151       break;
 152   if (p) {
 153     /* We found something, remove it from the chain.  */
 154     if (q) q->next = p->next; else table->buckets[n] = p->next;
 155     /* We cannot dispose of the contents.  */
 156     free (p);
 157   }
 158 }
 159 \f
 160 /* Look up STR in MAP.  Return a (dynamically-allocated) list of the
 161    corresponding strings or NULL if no match.  */
 162
 163 #ifdef KPSE_DEBUG
 164 /* Print the hash values as integers if this is nonzero.  */
 165 boolean kpse_debug_hash_lookup_int = false;
 166 #endif
 167
 168 string *
 169 hash_lookup P2C(hash_table_type, table,  const_string, key)
 170 {
 171   hash_element_type *p;
 172   str_list_type ret;
 173   unsigned n = hash (table, key);
 174   ret = str_list_init ();
 175
 176   /* Look at everything in this bucket.  */
 177   for (p = table.buckets[n]; p != NULL; p = p->next)
 178     if (FILESTRCASEEQ (key, p->key))
 179       /* Cast because the general str_list_type shouldn't force const data.  */
 180       str_list_add (&ret, (string) p->value);
 181
 182   /* If we found anything, mark end of list with null.  */
 183   if (STR_LIST (ret))
 184     str_list_add (&ret, NULL);
 185
 186 #ifdef KPSE_DEBUG
 187   if (KPSE_DEBUG_P (KPSE_DEBUG_HASH))
 188     {
 189       DEBUGF1 ("hash_lookup(%s) =>", key);
 190       if (!STR_LIST (ret))
 191         fputs (" (nil)\n", stderr);
 192       else
 193         {
 194           string *r;
 195           for (r = STR_LIST (ret); *r; r++)
 196             {
 197               putc (' ', stderr);
 198               if (kpse_debug_hash_lookup_int)
 199                 fprintf (stderr, "%ld", (long) *r);
 200               else
 201                 fputs (*r, stderr);
 202             }
 203           putc ('\n', stderr);
 204         }
 205       fflush (stderr);
 206     }
 207 #endif
 208
 209   return STR_LIST (ret);
 210 }
 211 \f
 212 /* We only print nonempty buckets, to decrease output volume.  */
 213
 214 void
 215 hash_print P2C(hash_table_type, table,  boolean, summary_only)
 216 {
 217   unsigned b;
 218   unsigned total_elements = 0, total_buckets = 0;
 219
 220   for (b = 0; b < table.size; b++) {
 221     hash_element_type *bucket = table.buckets[b];
 222
 223     if (bucket) {
 224       unsigned len = 1;
 225       hash_element_type *tb;
 226
 227       total_buckets++;
 228       if (!summary_only) fprintf (stderr, "%4d ", b);
 229
 230       for (tb = bucket->next; tb != NULL; tb = tb->next)
 231         len++;
 232       if (!summary_only) fprintf (stderr, ":%-5d", len);
 233       total_elements += len;
 234
 235       if (!summary_only) {
 236         for (tb = bucket; tb != NULL; tb = tb->next)
 237           fprintf (stderr, " %s=>%s", tb->key, tb->value);
 238         putc ('\n', stderr);
 239       }
 240     }
 241   }
 242
 243   fprintf (stderr,
 244           "%u buckets, %u nonempty (%u%%); %u entries, average chain %.1f.\n",
 245           table.size,
 246           total_buckets,
 247           100 * total_buckets / table.size,
 248           total_elements,
 249           total_buckets ? total_elements / (double) total_buckets : 0.0);
 250 }