Back to index

tetex-bin  3.0
hash.c
Go to the documentation of this file.
00001 /* hash.c: hash table operations.
00002 
00003 Copyright (C) 1994, 95, 96, 97, 98, 99, 2000 Karl Berry & Olaf Weber.
00004 
00005 This library is free software; you can redistribute it and/or
00006 modify it under the terms of the GNU Library General Public
00007 License as published by the Free Software Foundation; either
00008 version 2 of the License, or (at your option) any later version.
00009 
00010 This library is distributed in the hope that it will be useful,
00011 but WITHOUT ANY WARRANTY; without even the implied warranty of
00012 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013 Library General Public License for more details.
00014 
00015 You should have received a copy of the GNU Library General Public
00016 License along with this library; if not, write to the Free Software
00017 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
00018 
00019 #include <kpathsea/config.h>
00020 #include <kpathsea/c-ctype.h>
00021 
00022 #include <kpathsea/hash.h>
00023 #include <kpathsea/str-list.h>
00024 
00025 
00026 /* The hash function.  We go for simplicity here.  */
00027 
00028 /* All our hash tables are related to filenames.  */
00029 #ifdef MONOCASE_FILENAMES
00030 #if defined(WIN32) && !defined(__i386_pc_gnu__)
00031 /* This is way faster under Win32. */
00032 #define TRANSFORM(x) ((unsigned)CharLower((LPTSTR)(BYTE)(x)))
00033 #else
00034 #define TRANSFORM(x) (tolower(x))
00035 #endif
00036 #else
00037 #define TRANSFORM(x) (x)
00038 #endif
00039 
00040 static unsigned
00041 hash P2C(hash_table_type, table,  const_string, key)
00042 {
00043   unsigned n = 0;
00044   
00045   /* Our keys aren't often anagrams of each other, so no point in
00046      weighting the characters.  */
00047   while (*key != 0)
00048     n = (n + n + TRANSFORM (*key++)) % table.size;
00049   
00050   return n;
00051 }
00052 
00053 /* Identical has function as above, but does not normalize keys. */
00054 static unsigned
00055 hash_normalized P2C(hash_table_type, table,  const_string, key)
00056 {
00057   unsigned n = 0;
00058   
00059   /* Our keys aren't often anagrams of each other, so no point in
00060      weighting the characters.  */
00061   while (*key != 0)
00062     n = (n + n + (*key++)) % table.size;
00063   
00064   return n;
00065 }
00066 
00067 hash_table_type
00068 hash_create P1C(unsigned, size) 
00069 {
00070   /* hash_table_type ret; changed into "static ..." to work around gcc
00071      optimizer bug for Alpha.  */
00072   static hash_table_type ret;
00073   unsigned b;
00074   ret.buckets = XTALLOC (size, hash_element_type *);
00075   ret.size = size;
00076   
00077   /* calloc's zeroes aren't necessarily NULL, so be safe.  */
00078   for (b = 0; b <ret.size; b++)
00079     ret.buckets[b] = NULL;
00080     
00081   return ret;
00082 }
00083 
00084 /* Whether or not KEY is already in MAP, insert it and VALUE.  Do not
00085    duplicate the strings, in case they're being purposefully shared.  */
00086 
00087 void
00088 hash_insert P3C(hash_table_type *, table,
00089                 const_string, key,
00090                 const_string, value)
00091 {
00092   unsigned n = hash (*table, key);
00093   hash_element_type *new_elt = XTALLOC1 (hash_element_type);
00094 
00095   new_elt->key = key;
00096   new_elt->value = value;
00097   new_elt->next = NULL;
00098   
00099   /* Insert the new element at the end of the list.  */
00100   if (!table->buckets[n])
00101     /* first element in bucket is a special case.  */
00102     table->buckets[n] = new_elt;
00103   else
00104     {
00105       hash_element_type *loc = table->buckets[n];
00106       while (loc->next)            /* Find the last element.  */
00107         loc = loc->next;
00108       loc->next = new_elt;  /* Insert the new one after.  */
00109     }
00110 }
00111 
00112 /* Same as above, for normalized keys. */
00113 void
00114 hash_insert_normalized P3C(hash_table_type *, table,
00115                            const_string, key,
00116                            const_string, value)
00117 {
00118   unsigned n = hash_normalized (*table, key);
00119   hash_element_type *new_elt = XTALLOC1 (hash_element_type);
00120 
00121   new_elt->key = key;
00122   new_elt->value = value;
00123   new_elt->next = NULL;
00124   
00125   /* Insert the new element at the end of the list.  */
00126   if (!table->buckets[n])
00127     /* first element in bucket is a special case.  */
00128     table->buckets[n] = new_elt;
00129   else
00130     {
00131       hash_element_type *loc = table->buckets[n];
00132       while (loc->next)            /* Find the last element.  */
00133         loc = loc->next;
00134       loc->next = new_elt;  /* Insert the new one after.  */
00135     }
00136 }
00137 
00138 /* Remove a (KEY, VALUE) pair.  */
00139 
00140 void
00141 hash_remove P3C(hash_table_type *, table,  const_string, key,
00142                 const_string, value)
00143 {
00144   hash_element_type *p;
00145   hash_element_type *q;
00146   unsigned n = hash (*table, key);
00147 
00148   /* Find pair.  */
00149   for (q = NULL, p = table->buckets[n]; p != NULL; q = p, p = p->next)
00150     if (FILESTRCASEEQ (key, p->key) && STREQ (value, p->value))
00151       break;
00152   if (p) {
00153     /* We found something, remove it from the chain.  */
00154     if (q) q->next = p->next; else table->buckets[n] = p->next;
00155     /* We cannot dispose of the contents.  */
00156     free (p);
00157   }
00158 }
00159 
00160 /* Look up STR in MAP.  Return a (dynamically-allocated) list of the
00161    corresponding strings or NULL if no match.  */ 
00162 
00163 #ifdef KPSE_DEBUG
00164 /* Print the hash values as integers if this is nonzero.  */
00165 boolean kpse_debug_hash_lookup_int = false; 
00166 #endif
00167 
00168 string *
00169 hash_lookup P2C(hash_table_type, table,  const_string, key)
00170 {
00171   hash_element_type *p;
00172   str_list_type ret;
00173   unsigned n = hash (table, key);
00174   ret = str_list_init ();
00175   
00176   /* Look at everything in this bucket.  */
00177   for (p = table.buckets[n]; p != NULL; p = p->next)
00178     if (FILESTRCASEEQ (key, p->key))
00179       /* Cast because the general str_list_type shouldn't force const data.  */
00180       str_list_add (&ret, (string) p->value);
00181   
00182   /* If we found anything, mark end of list with null.  */
00183   if (STR_LIST (ret))
00184     str_list_add (&ret, NULL);
00185 
00186 #ifdef KPSE_DEBUG
00187   if (KPSE_DEBUG_P (KPSE_DEBUG_HASH))
00188     {
00189       DEBUGF1 ("hash_lookup(%s) =>", key);
00190       if (!STR_LIST (ret))
00191         fputs (" (nil)\n", stderr);
00192       else
00193         {
00194           string *r;
00195           for (r = STR_LIST (ret); *r; r++)
00196             {
00197               putc (' ', stderr);
00198               if (kpse_debug_hash_lookup_int)
00199                 fprintf (stderr, "%ld", (long) *r);
00200               else
00201                 fputs (*r, stderr);
00202             }
00203           putc ('\n', stderr);
00204         }
00205       fflush (stderr);
00206     }
00207 #endif
00208 
00209   return STR_LIST (ret);
00210 }
00211 
00212 /* We only print nonempty buckets, to decrease output volume.  */
00213 
00214 void
00215 hash_print P2C(hash_table_type, table,  boolean, summary_only)
00216 {
00217   unsigned b;
00218   unsigned total_elements = 0, total_buckets = 0;
00219   
00220   for (b = 0; b < table.size; b++) {
00221     hash_element_type *bucket = table.buckets[b];
00222 
00223     if (bucket) {
00224       unsigned len = 1;
00225       hash_element_type *tb;
00226 
00227       total_buckets++;
00228       if (!summary_only) fprintf (stderr, "%4d ", b);
00229 
00230       for (tb = bucket->next; tb != NULL; tb = tb->next)
00231         len++;
00232       if (!summary_only) fprintf (stderr, ":%-5d", len);
00233       total_elements += len;
00234 
00235       if (!summary_only) {
00236         for (tb = bucket; tb != NULL; tb = tb->next)
00237           fprintf (stderr, " %s=>%s", tb->key, tb->value);
00238         putc ('\n', stderr);
00239       }
00240     }
00241   }
00242   
00243   fprintf (stderr,
00244           "%u buckets, %u nonempty (%u%%); %u entries, average chain %.1f.\n",
00245           table.size,
00246           total_buckets,
00247           100 * total_buckets / table.size,
00248           total_elements,
00249           total_buckets ? total_elements / (double) total_buckets : 0.0);
00250 }