home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / octave-1.1.1p1-src.tgz / tar.out / fsf / octave / kpathsea / hash.c < prev    next >
C/C++ Source or Header  |  1996-09-28  |  4KB  |  132 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. #include <kpathsea/hash.h>
  21. #include <kpathsea/str-list.h>
  22.  
  23.  
  24. /* The hash function.  We go for simplicity here.  */
  25.  
  26. static unsigned
  27. hash P2C(hash_table_type, table,  const_string, key)
  28. {
  29.   unsigned n = 0;
  30.   
  31.   /* Our keys aren't often anagrams of each other, so no point in
  32.      weighting the characters.  */
  33.   while (*key != 0)
  34.     n = (n + n + *key++) % table.size;
  35.   
  36.   return n;
  37. }
  38.  
  39. hash_table_type
  40. hash_create P1C(unsigned, size) 
  41. {
  42.   unsigned b;
  43.   hash_table_type ret;
  44.   ret.buckets = XTALLOC (size, hash_element_type *);
  45.   ret.size = size;
  46.   
  47.   /* calloc's zeroes aren't necessarily NULL, according to ANSI, so be
  48.      safe.  (Not that I know of any exceptions in reality.)  */
  49.   for (b = 0; b <ret.size; b++)
  50.     ret.buckets[b] = NULL;
  51.     
  52.   return ret;
  53. }
  54.  
  55. /* Whether or not KEY is already in MAP, insert it and VALUE.  Do not
  56.    duplicate the strings, in case they're being purposefully shared.  */
  57.  
  58. void
  59. hash_insert P3C(hash_table_type *, table,  const_string, key,
  60.                 const_string, value)
  61. {
  62.   unsigned n = hash (*table, key);
  63.   hash_element_type *head = table->buckets[n];
  64.   
  65.   table->buckets[n] = XTALLOC1 (hash_element_type);
  66.   table->buckets[n]->key = key;
  67.   table->buckets[n]->value = value;
  68.   table->buckets[n]->next = head;
  69. }
  70.  
  71. /* Look up STR in MAP.  Return a (dynamically-allocated) list of the
  72.    corresponding strings or NULL if no match.  */ 
  73.  
  74. string *
  75. hash_lookup P2C(hash_table_type, table,  const_string, key)
  76. {
  77.   hash_element_type *p;
  78.   str_list_type ret;
  79.   unsigned n = hash (table, key);
  80.   ret = str_list_init ();
  81.   
  82.   /* Look at everything in this bucket.  */
  83.   for (p = table.buckets[n]; p != NULL; p = p->next)
  84.     if (STREQ (key, p->key))
  85.       /* Cast because the general str_list_type shouldn't force const data.  */
  86.       str_list_add (&ret, (string) p->value);
  87.   
  88.   /* If we found anything, mark end of list with null.  */
  89.   if (STR_LIST (ret))
  90.     str_list_add (&ret, NULL);
  91.  
  92.   return STR_LIST (ret);
  93. }
  94.  
  95. /* We only print nonempty buckets, to decrease output volume.  */
  96.  
  97. void
  98. hash_print P1C(hash_table_type, table)
  99. {
  100.   unsigned b;
  101.   unsigned total_elements = 0, total_buckets = 0;
  102.   
  103.   for (b = 0; b < table.size; b++)
  104.     {
  105.       hash_element_type *bucket = table.buckets[b];
  106.       
  107.       if (bucket)
  108.         {
  109.           unsigned len = 1;
  110.           hash_element_type *tb;
  111.           
  112.           total_buckets++;
  113.           printf ("%4d ", b);
  114.           
  115.           for (tb = bucket->next; tb != NULL; tb = tb->next)
  116.             len++;
  117.           printf (":%-5d", len);
  118.           total_elements += len;
  119.           
  120.           for (tb = bucket; tb != NULL; tb = tb->next)
  121.             printf (" %s=>%s", tb->key, tb->value);
  122.           
  123.           putchar ('\n');
  124.         }
  125.     }
  126.   
  127.   printf ("%u buckets, %u nonempty (%u%%); %u entries, average chain %.1f.\n",
  128.           table.size, total_buckets, 100 * total_buckets / table.size,
  129.           total_elements,
  130.           total_buckets ? total_elements / (double) total_buckets : 0.0);
  131. }
  132.