source/texk/kpathsea/hash.c

   1 /* hash.c: hash table operations.
   2
   3    Copyright 1994-2000, 2002, 2005, 2008, 2012
   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
  30 static unsigned
  31 hash (hash_table_type table,  const_string key)
  32 {
  33   unsigned n = 0;
  34
  35   /* Our keys aren't often anagrams of each other, so no point in
  36      weighting the characters.  */
  37   while (*key != 0)
  38 #if defined(WIN32)
  39     if (IS_KANJI(key)) {
  40       n = (n + n + (unsigned)(*key++)) % table.size;
  41       n = (n + n + (unsigned)(*key++)) % table.size;
  42     } else
  43 #endif
  44     n = (n + n + TRANSFORM (*key++)) % table.size;
  45
  46   return n;
  47 }
  48
  49 /* Identical has function as above, but does not normalize keys. */
  50 static unsigned
  51 hash_normalized (hash_table_type table,  const_string key)
  52 {
  53   unsigned n = 0;
  54
  55   /* Our keys aren't often anagrams of each other, so no point in
  56      weighting the characters.  */
  57   while (*key != 0)
  58     n = (n + n + (*key++)) % table.size;
  59
  60   return n;
  61 }
  62 \f
  63 hash_table_type
  64 hash_create (unsigned size)
  65 {
  66   /* The was "static ..." since Oct3, 1997 to work around a gcc
  67      optimizer bug for Alpha. That particular optimization bug
  68      should be gone by now (Mar4, 2009).
  69   */
  70   hash_table_type ret;
  71   unsigned b;
  72   ret.buckets = XTALLOC (size, hash_element_type *);
  73   ret.size = size;
  74
  75   /* calloc's zeroes aren't necessarily NULL, so be safe.  */
  76   for (b = 0; b <ret.size; b++)
  77     ret.buckets[b] = NULL;
  78
  79   return ret;
  80 }
  81 \f
  82 /* Whether or not KEY is already in TABLE, insert it and VALUE.  Do not
  83    duplicate the strings, in case they're being purposefully shared.  */
  84
  85 void
  86 hash_insert (hash_table_type *table,
  87              const_string key,
  88              const_string value)
  89 {
  90   unsigned n = hash (*table, key);
  91   hash_element_type *new_elt = XTALLOC1 (hash_element_type);
  92
  93   new_elt->key = key;
  94   new_elt->value = value;
  95   new_elt->next = NULL;
  96
  97   /* Insert the new element at the end of the list.  */
  98   if (!table->buckets[n])
  99     /* first element in bucket is a special case.  */
 100     table->buckets[n] = new_elt;
 101   else
 102     {
 103       hash_element_type *loc = table->buckets[n];
 104       while (loc->next)         /* Find the last element.  */
 105         loc = loc->next;
 106       loc->next = new_elt;      /* Insert the new one after.  */
 107     }
 108 }
 109
 110 /* Same as above, for normalized keys. */
 111 void
 112 hash_insert_normalized (hash_table_type *table,
 113                         const_string key,
 114                         const_string value)
 115 {
 116   unsigned n = hash_normalized (*table, key);
 117   hash_element_type *new_elt = XTALLOC1 (hash_element_type);
 118
 119   new_elt->key = key;
 120   new_elt->value = value;
 121   new_elt->next = NULL;
 122
 123   /* Insert the new element at the end of the list.  */
 124   if (!table->buckets[n])
 125     /* first element in bucket is a special case.  */
 126     table->buckets[n] = new_elt;
 127   else
 128     {
 129       hash_element_type *loc = table->buckets[n];
 130       while (loc->next)         /* Find the last element.  */
 131         loc = loc->next;
 132       loc->next = new_elt;      /* Insert the new one after.  */
 133     }
 134 }
 135 \f
 136 /* Remove a (KEY, VALUE) pair.  */
 137
 138 void
 139 hash_remove (hash_table_type *table,  const_string key,
 140              const_string value)
 141 {
 142   hash_element_type *p;
 143   hash_element_type *q;
 144   unsigned n = hash (*table, key);
 145
 146   /* Find pair.  */
 147   for (q = NULL, p = table->buckets[n]; p != NULL; q = p, p = p->next)
 148     if (FILESTRCASEEQ (key, p->key) && STREQ (value, p->value))
 149       break;
 150   if (p) {
 151     /* We found something, remove it from the chain.  */
 152     if (q) q->next = p->next; else table->buckets[n] = p->next;
 153     /* We cannot dispose of the contents.  */
 154     free (p);
 155   }
 156 }
 157 \f
 158 /* Look up KEY in TABLE, and return NULL-terminated list of all matching
 159    values (not copies), in insertion order.  If none, return NULL.  */
 160
 161 const_string *
 162 hash_lookup (hash_table_type table,  const_string key)
 163 {
 164   hash_element_type *p;
 165   cstr_list_type ret;
 166   unsigned n = hash (table, key);
 167   ret = cstr_list_init ();
 168
 169   /* Look at everything in this bucket.  */
 170   for (p = table.buckets[n]; p != NULL; p = p->next)
 171     if (FILESTRCASEEQ (key, p->key))
 172       cstr_list_add (&ret, p->value);
 173
 174   /* If we found anything, mark end of list with null.  */
 175   if (STR_LIST (ret))
 176     cstr_list_add (&ret, NULL);
 177
 178 #ifdef KPSE_DEBUG
 179 #if defined (KPSE_COMPAT_API)
 180   {
 181   kpathsea kpse = kpse_def;
 182   if (KPATHSEA_DEBUG_P (KPSE_DEBUG_HASH))
 183     {
 184       DEBUGF1 ("hash_lookup(%s) =>", key);
 185       if (!STR_LIST (ret))
 186         fputs (" (nil)\n", stderr);
 187       else
 188         {
 189           const_string *r;
 190           for (r = STR_LIST (ret); *r; r++)
 191             {
 192               putc (' ', stderr);
 193               if (kpse->debug_hash_lookup_int)
 194 #if defined(_WIN64)
 195                 fprintf (stderr, "%I64d", (__int64) *r);
 196 #else
 197                 fprintf (stderr, "%ld", (long) *r);
 198 #endif
 199               else
 200                 fputs (*r, stderr);
 201             }
 202           putc ('\n', stderr);
 203         }
 204       fflush (stderr);
 205     }
 206   }
 207 #endif
 208 #endif
 209
 210   return STR_LIST (ret);
 211 }
 212 \f
 213 #ifdef KPSE_DEBUG
 214 /* We only print nonempty buckets, to decrease output volume.  */
 215
 216 void
 217 hash_print (hash_table_type table,  boolean summary_only)
 218 {
 219   unsigned b;
 220   unsigned total_elements = 0, total_buckets = 0;
 221
 222   for (b = 0; b < table.size; b++) {
 223     hash_element_type *bucket = table.buckets[b];
 224
 225     if (bucket) {
 226       unsigned len = 1;
 227       hash_element_type *tb;
 228
 229       total_buckets++;
 230       if (!summary_only) fprintf (stderr, "%4d ", b);
 231
 232       for (tb = bucket->next; tb != NULL; tb = tb->next)
 233         len++;
 234       if (!summary_only) fprintf (stderr, ":%-5d", len);
 235       total_elements += len;
 236
 237       if (!summary_only) {
 238         for (tb = bucket; tb != NULL; tb = tb->next)
 239           fprintf (stderr, " %s=>%s", tb->key, tb->value);
 240         putc ('\n', stderr);
 241       }
 242     }
 243   }
 244
 245   fprintf (stderr,
 246           "%u buckets, %u nonempty (%u%%); %u entries, average chain %.1f.\n",
 247           table.size,
 248           total_buckets,
 249           100 * total_buckets / table.size,
 250           total_elements,
 251           total_buckets ? total_elements / (double) total_buckets : 0.0);
 252 }
 253 #endif
 254
 255 #if KPATHSEA_CAN_FREE
 256 void
 257 hash_free (hash_table_type table)
 258 {
 259     struct hash_element_struct *p, *q;
 260     p = (struct hash_element_struct *)table.buckets;
 261     while (p != NULL) {
 262         q = p->next;
 263         free ((char *)p->key);
 264         free ((char *)p->value);
 265         free (p);
 266         p = q;
 267     }
 268 }
 269 #endif