home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / unixtex-6.1b-src.tgz / tar.out / contrib / unixtex / kpathsea / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-09-28  |  4.6 KB  |  172 lines
  1. /* hash.c: hash table operations.
  2.  
  3. Copyright (C) 1994 Karl Berry.
  4.  
  5. This program is free software; you can redistribute it and/or modify
  6. it under the terms of the GNU General Public License as published by
  7. the Free Software Foundation; either version 2, or (at your option)
  8. any later version.
  9.  
  10. This program is distributed in the hope that it will be useful,
  11. but WITHOUT ANY WARRANTY; without even the implied warranty of
  12. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13. GNU General Public License for more details.
  14.  
  15. You should have received a copy of the GNU General Public License
  16. along with this program; if not, write to the Free Software
  17. Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  18.  
  19. #include <kpathsea/config.h>
  20.  
  21. #include <kpathsea/hash.h>
  22. #include <kpathsea/str-list.h>
  23.  
  24.  
  25. /* The hash function.  We go for simplicity here.  */
  26.  
  27. static unsigned
  28. hash P2C(hash_table_type, table,  const_string, key)
  29. {
  30.   unsigned n = 0;
  31.   
  32.   /* Our keys aren't often anagrams of each other, so no point in
  33.      weighting the characters.  */
  34.   while (*key != 0)
  35.     n = (n + n + *key++) % table.size;
  36.   
  37.   return n;
  38. }
  39.  
  40. hash_table_type
  41. hash_create P1C(unsigned, size) 
  42. {
  43.   unsigned b;
  44.   hash_table_type ret;
  45.   ret.buckets = XTALLOC (size, hash_element_type *);
  46.   ret.size = size;
  47.   
  48.   /* calloc's zeroes aren't necessarily NULL, according to ANSI, so be
  49.      safe.  (Not that I know of any exceptions in reality.)  */
  50.   for (b = 0; b <ret.size; b++)
  51.     ret.buckets[b] = NULL;
  52.     
  53.   return ret;
  54. }
  55.  
  56. /* Whether or not KEY is already in MAP, insert it and VALUE.  Do not
  57.    duplicate the strings, in case they're being purposefully shared.  */
  58.  
  59. void
  60. hash_insert P3C(hash_table_type *, table,  const_string, key,
  61.                 const_string, value)
  62. {
  63.   unsigned n = hash (*table, key);
  64.   hash_element_type *new_elt = XTALLOC1 (hash_element_type);
  65.  
  66.   new_elt->key = key;
  67.   new_elt->value = value;
  68.   new_elt->next = NULL;
  69.   
  70.   /* Insert the new element at the end of the list.  */
  71.   if (!table->buckets[n])
  72.     /* first element in bucket is a special case.  */
  73.     table->buckets[n] = new_elt;
  74.   else
  75.     {
  76.       hash_element_type *loc = table->buckets[n];
  77.       while (loc->next)        /* Find the last element.  */
  78.         loc = loc->next;
  79.       loc->next = new_elt;    /* Insert the new one after.  */
  80.     }
  81. }
  82.  
  83. /* Look up STR in MAP.  Return a (dynamically-allocated) list of the
  84.    corresponding strings or NULL if no match.  */ 
  85.  
  86. #ifdef DEBUG
  87. /* Print the hash values as integers if this is nonzero.  */
  88. boolean kpse_debug_hash_lookup_int = false; 
  89. #endif
  90.  
  91. string *
  92. hash_lookup P2C(hash_table_type, table,  const_string, key)
  93. {
  94.   hash_element_type *p;
  95.   str_list_type ret;
  96.   unsigned n = hash (table, key);
  97.   ret = str_list_init ();
  98.   
  99.   /* Look at everything in this bucket.  */
  100.   for (p = table.buckets[n]; p != NULL; p = p->next)
  101.     if (STREQ (key, p->key))
  102.       /* Cast because the general str_list_type shouldn't force const data.  */
  103.       str_list_add (&ret, (string) p->value);
  104.   
  105.   /* If we found anything, mark end of list with null.  */
  106.   if (STR_LIST (ret))
  107.     str_list_add (&ret, NULL);
  108.  
  109. #ifdef DEBUG
  110.   if (KPSE_DEBUG_P (KPSE_DEBUG_HASH))
  111.     {
  112.       DEBUGF1 ("hash_lookup(%s) =>", key);
  113.       if (!STR_LIST (ret))
  114.         fputs (" (null)\n", stderr);
  115.       else
  116.         {
  117.           string *r;
  118.           for (r = STR_LIST (ret); *r; r++)
  119.             {
  120.               putc (' ', stderr);
  121.               if (kpse_debug_hash_lookup_int)
  122.                 fprintf (stderr, "%ld", (long) *r);
  123.               else
  124.                 fputs (*r, stderr);
  125.             }
  126.           putc ('\n', stderr);
  127.         }
  128.       fflush (stderr);
  129.     }
  130. #endif
  131.  
  132.   return STR_LIST (ret);
  133. }
  134.  
  135. /* We only print nonempty buckets, to decrease output volume.  */
  136.  
  137. void
  138. hash_print P1C(hash_table_type, table)
  139. {
  140.   unsigned b;
  141.   unsigned total_elements = 0, total_buckets = 0;
  142.   
  143.   for (b = 0; b < table.size; b++)
  144.     {
  145.       hash_element_type *bucket = table.buckets[b];
  146.       
  147.       if (bucket)
  148.         {
  149.           unsigned len = 1;
  150.           hash_element_type *tb;
  151.           
  152.           total_buckets++;
  153.           printf ("%4d ", b);
  154.           
  155.           for (tb = bucket->next; tb != NULL; tb = tb->next)
  156.             len++;
  157.           printf (":%-5d", len);
  158.           total_elements += len;
  159.           
  160.           for (tb = bucket; tb != NULL; tb = tb->next)
  161.             printf (" %s=>%s", tb->key, tb->value);
  162.           
  163.           putchar ('\n');
  164.         }
  165.     }
  166.   
  167.   printf ("%u buckets, %u nonempty (%u%%); %u entries, average chain %.1f.\n",
  168.           table.size, total_buckets, 100 * total_buckets / table.size,
  169.           total_elements,
  170.           total_buckets ? total_elements / (double) total_buckets : 0.0);
  171. }
  172.