home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / octa21fs.zip / octave / kpathsea / hash.c < prev    next >
C/C++ Source or Header  |  2000-01-15  |  6KB  |  204 lines
  1. /* hash.c: hash table operations.
  2.  
  3. Copyright (C) 1994, 95, 96, 97 Karl Berry & Olaf Weber.
  4.  
  5. This library is free software; you can redistribute it and/or
  6. modify it under the terms of the GNU Library General Public
  7. License as published by the Free Software Foundation; either
  8. version 2 of the License, or (at your option) any later version.
  9.  
  10. This library 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 GNU
  13. Library General Public License for more details.
  14.  
  15. You should have received a copy of the GNU Library General Public
  16. License along with this library; if not, write to the Free Software
  17. Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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. /* All our hash tables are related to filenames.  */
  28. #ifdef MONOCASE_FILENAMES
  29. #define TRANSFORM(x) toupper (x)
  30. #else
  31. #define TRANSFORM(x) (x)
  32. #endif
  33.  
  34. static unsigned
  35. hash P2C(hash_table_type, table,  const_string, key)
  36. {
  37.   unsigned n = 0;
  38.   
  39.   /* Our keys aren't often anagrams of each other, so no point in
  40.      weighting the characters.  */
  41.   while (*key != 0)
  42.     n = (n + n + TRANSFORM (*key++)) % table.size;
  43.   
  44.   return n;
  45. }
  46.  
  47. hash_table_type
  48. hash_create P1C(unsigned, size) 
  49. {
  50.   /* hash_table_type ret; changed into "static ..." to work around gcc
  51.      optimizer bug for Alpha.  */
  52.   static hash_table_type ret;
  53.   unsigned b;
  54.   ret.buckets = XTALLOC (size, hash_element_type *);
  55.   ret.size = size;
  56.   
  57.   /* calloc's zeroes aren't necessarily NULL, so be safe.  */
  58.   for (b = 0; b <ret.size; b++)
  59.     ret.buckets[b] = NULL;
  60.     
  61.   return ret;
  62. }
  63.  
  64. /* Whether or not KEY is already in MAP, insert it and VALUE.  Do not
  65.    duplicate the strings, in case they're being purposefully shared.  */
  66.  
  67. void
  68. hash_insert P3C(hash_table_type *, table,  const_string, key,
  69.                 const_string, value)
  70. {
  71.   unsigned n = hash (*table, key);
  72.   hash_element_type *new_elt = XTALLOC1 (hash_element_type);
  73.  
  74.   new_elt->key = key;
  75.   new_elt->value = value;
  76.   new_elt->next = NULL;
  77.   
  78.   /* Insert the new element at the end of the list.  */
  79.   if (!table->buckets[n])
  80.     /* first element in bucket is a special case.  */
  81.     table->buckets[n] = new_elt;
  82.   else
  83.     {
  84.       hash_element_type *loc = table->buckets[n];
  85.       while (loc->next)        /* Find the last element.  */
  86.         loc = loc->next;
  87.       loc->next = new_elt;    /* Insert the new one after.  */
  88.     }
  89. }
  90.  
  91. /* Remove a (KEY, VALUE) pair.  */
  92.  
  93. void
  94. hash_remove P3C(hash_table_type *, table,  const_string, key,
  95.                 const_string, value)
  96. {
  97.   hash_element_type *p;
  98.   hash_element_type *q;
  99.   unsigned n = hash (*table, key);
  100.  
  101.   /* Find pair.  */
  102.   for (q = NULL, p = table->buckets[n]; p != NULL; q = p, p = p->next)
  103.     if (FILESTRCASEEQ (key, p->key) && STREQ (value, p->value))
  104.       break;
  105.   if (p) {
  106.     /* We found something, remove it from the chain.  */
  107.     if (q) q->next = p->next; else table->buckets[n] = p->next;
  108.     /* We cannot dispose of the contents.  */
  109.     free (p);
  110.   }
  111. }
  112.  
  113. /* Look up STR in MAP.  Return a (dynamically-allocated) list of the
  114.    corresponding strings or NULL if no match.  */ 
  115.  
  116. #ifdef KPSE_DEBUG
  117. /* Print the hash values as integers if this is nonzero.  */
  118. boolean kpse_debug_hash_lookup_int = false; 
  119. #endif
  120.  
  121. string *
  122. hash_lookup P2C(hash_table_type, table,  const_string, key)
  123. {
  124.   hash_element_type *p;
  125.   str_list_type ret;
  126.   unsigned n = hash (table, key);
  127.   ret = str_list_init ();
  128.   
  129.   /* Look at everything in this bucket.  */
  130.   for (p = table.buckets[n]; p != NULL; p = p->next)
  131.     if (FILESTRCASEEQ (key, p->key))
  132.       /* Cast because the general str_list_type shouldn't force const data.  */
  133.       str_list_add (&ret, (string) p->value);
  134.   
  135.   /* If we found anything, mark end of list with null.  */
  136.   if (STR_LIST (ret))
  137.     str_list_add (&ret, NULL);
  138.  
  139. #ifdef KPSE_DEBUG
  140.   if (KPSE_DEBUG_P (KPSE_DEBUG_HASH))
  141.     {
  142.       DEBUGF1 ("hash_lookup(%s) =>", key);
  143.       if (!STR_LIST (ret))
  144.         fputs (" (nil)\n", stderr);
  145.       else
  146.         {
  147.           string *r;
  148.           for (r = STR_LIST (ret); *r; r++)
  149.             {
  150.               putc (' ', stderr);
  151.               if (kpse_debug_hash_lookup_int)
  152.                 fprintf (stderr, "%ld", (long) *r);
  153.               else
  154.                 fputs (*r, stderr);
  155.             }
  156.           putc ('\n', stderr);
  157.         }
  158.       fflush (stderr);
  159.     }
  160. #endif
  161.  
  162.   return STR_LIST (ret);
  163. }
  164.  
  165. /* We only print nonempty buckets, to decrease output volume.  */
  166.  
  167. void
  168. hash_print P2C(hash_table_type, table,  boolean, summary_only)
  169. {
  170.   unsigned b;
  171.   unsigned total_elements = 0, total_buckets = 0;
  172.   
  173.   for (b = 0; b < table.size; b++) {
  174.     hash_element_type *bucket = table.buckets[b];
  175.  
  176.     if (bucket) {
  177.       unsigned len = 1;
  178.       hash_element_type *tb;
  179.  
  180.       total_buckets++;
  181.       if (!summary_only) fprintf (stderr, "%4d ", b);
  182.  
  183.       for (tb = bucket->next; tb != NULL; tb = tb->next)
  184.         len++;
  185.       if (!summary_only) fprintf (stderr, ":%-5d", len);
  186.       total_elements += len;
  187.  
  188.       if (!summary_only) {
  189.         for (tb = bucket; tb != NULL; tb = tb->next)
  190.           fprintf (stderr, " %s=>%s", tb->key, tb->value);
  191.         putc ('\n', stderr);
  192.       }
  193.     }
  194.   }
  195.   
  196.   fprintf (stderr,
  197.           "%u buckets, %u nonempty (%u%%); %u entries, average chain %.1f.\n",
  198.           table.size,
  199.           total_buckets,
  200.           100 * total_buckets / table.size,
  201.           total_elements,
  202.           total_buckets ? total_elements / (double) total_buckets : 0.0);
  203. }
  204.