home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / gettext-0.10.24-src.tgz / tar.out / fsf / gettext / lib / hash.c < prev    next >
C/C++ Source or Header  |  1996-09-28  |  8KB  |  374 lines
  1. /* hash - implement simple hashing table with string based keys.
  2.    Copyright (C) 1994, 1995 Free Software Foundation, Inc.
  3.    Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, October 1994.
  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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  18.  
  19. #ifdef HAVE_CONFIG_H
  20. # include <config.h>
  21. #endif
  22.  
  23. #include <stdio.h>
  24. #include <sys/types.h>
  25.  
  26. #if HAVE_OBSTACK
  27. # include <obstack.h>
  28. #else
  29. # include "obstack.h"
  30. #endif
  31.  
  32. #ifdef HAVE_VALUES_H
  33. # include <values.h>
  34. #endif
  35.  
  36. #include "system.h"
  37. #include "hash.h"
  38.  
  39. #define obstack_chunk_alloc xmalloc
  40. #define obstack_chunk_free free
  41. extern void free (void *);
  42.  
  43. #ifndef BITSPERBYTE
  44. # define BITSPERBYTE 8
  45. #endif
  46.  
  47. #ifndef    LONGBITS
  48. # define LONGBITS (sizeof (long) * BITSPERBYTE)
  49. #endif
  50.  
  51. #ifndef bcopy
  52. # define bcopy(s, d, n)    memcpy ((d), (s), (n))
  53. #endif
  54.  
  55. void *xmalloc PARAMS ((size_t __n));
  56.  
  57. typedef struct hash_entry
  58. {
  59.   unsigned long used;
  60.   const char *key;
  61.   void *data;
  62.   struct hash_entry *next;
  63. }
  64. hash_entry;
  65.  
  66. /* Prototypes for local functions.  */
  67. static void insert_entry_2 PARAMS ((hash_table *htab, const char *key,
  68.                     unsigned long hval, size_t idx,
  69.                     void *data));
  70. static size_t lookup PARAMS ((hash_table *htab, const char *key, size_t keylen,
  71.                   unsigned long hval));
  72. static size_t lookup_2 PARAMS ((hash_table *htab, const char *key,
  73.                 unsigned long hval));
  74. static unsigned long compute_hashval PARAMS ((const char *key, size_t keylen));
  75. static int is_prime PARAMS ((unsigned long candidate));
  76.  
  77.  
  78. int
  79. init_hash (htab, init_size)
  80.      hash_table *htab;
  81.      unsigned long init_size;
  82. {
  83.   /* We need the size to be a prime.  */
  84.   init_size = next_prime (init_size);
  85.  
  86.   /* Initialize the data structure.  */
  87.   htab->size = init_size;
  88.   htab->filled = 0;
  89.   htab->first = NULL;
  90.   htab->table = (void *) xmalloc ((init_size + 1) * sizeof (hash_entry));
  91.   if (htab->table == NULL)
  92.     return -1;
  93.  
  94.   memset (htab->table, '\0', (init_size + 1) * sizeof (hash_entry));
  95.   obstack_init (&htab->mem_pool);
  96.  
  97.   return 0;
  98. }
  99.  
  100.  
  101. int
  102. delete_hash (htab)
  103.      hash_table *htab;
  104. {
  105.   free (htab->table);
  106.   obstack_free (&htab->mem_pool, NULL);
  107.   return 0;
  108. }
  109.  
  110.  
  111. int
  112. insert_entry (htab, key, keylen, data)
  113.      hash_table *htab;
  114.      const char *key;
  115.      size_t keylen;
  116.      void *data;
  117. {
  118.   unsigned long hval = compute_hashval (key, keylen);
  119.   hash_entry *table = (hash_entry *) htab->table;
  120.   size_t idx = lookup (htab, key, keylen, hval);
  121.  
  122.   if (table[idx].used)
  123.     /* We don't want to overwrite the old value.  */
  124.     return -1;
  125.   else
  126.     {
  127.       /* An empty bucket has been found.  */
  128.       insert_entry_2 (htab, obstack_copy0 (&htab->mem_pool, key, keylen),
  129.               hval, idx, data);
  130.       return 0;
  131.     }
  132. }
  133.  
  134. static void
  135. insert_entry_2 (htab, key, hval, idx, data)
  136.      hash_table *htab;
  137.      const char *key;
  138.      unsigned long hval;
  139.      size_t idx;
  140.      void *data;
  141. {
  142.   hash_entry *table = (hash_entry *) htab->table;
  143.  
  144.   table[idx].used = hval;
  145.   table[idx].key = key;
  146.   table[idx].data = data;
  147.  
  148.       /* List the new value in the list.  */
  149.   if ((hash_entry *) htab->first == NULL)
  150.     {
  151.       table[idx].next = &table[idx];
  152.       *(hash_entry **) &htab->first = &table[idx];
  153.     }
  154.   else
  155.     {
  156.       table[idx].next = ((hash_entry *) htab->first)->next;
  157.       ((hash_entry *) htab->first)->next = &table[idx];
  158.       *(hash_entry **) &htab->first = &table[idx];
  159.     }
  160.  
  161.   ++htab->filled;
  162.   if (100 * htab->filled > 90 * htab->size)
  163.     {
  164.       /* Table is filled more than 90%.  Resize the table.  */
  165.       unsigned long old_size = htab->size;
  166.  
  167.       htab->size = next_prime (htab->size * 2);
  168.       htab->filled = 0;
  169.       htab->first = NULL;
  170.       htab->table = (void *) xmalloc ((1 + htab->size)
  171.                       * sizeof (hash_entry));
  172.       memset (htab->table, '\0', (1 + htab->size) * sizeof (hash_entry));
  173.  
  174.       for (idx = 1; idx <= old_size; ++idx)
  175.     if (table[idx].used)
  176.       insert_entry_2 (htab, table[idx].key, table[idx].used,
  177.               lookup_2 (htab, table[idx].key, table[idx].used),
  178.               table[idx].data);
  179.  
  180.       free (table);
  181.     }
  182. }
  183.  
  184.  
  185. int
  186. find_entry (htab, key, keylen, result)
  187.      hash_table *htab;
  188.      const char *key;
  189.      size_t keylen;
  190.      void **result;
  191. {
  192.   hash_entry *table = (hash_entry *) htab->table;
  193.   size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
  194.  
  195.   if (table[idx].used == 0)
  196.     return -1;
  197.  
  198.   *result = table[idx].data;
  199.   return 0;
  200. }
  201.  
  202.  
  203. int
  204. iterate_table (htab, ptr, key, data)
  205.      hash_table *htab;
  206.      void **ptr;
  207.      const void **key;
  208.      void **data;
  209. {
  210.   if (*ptr == NULL)
  211.     {
  212.       if (htab->first == NULL)
  213.     return -1;
  214.       *ptr = (void *) ((hash_entry *) htab->first)->next;
  215.     }
  216.   else
  217.     {
  218.       if (*ptr == htab->first)
  219.     return -1;
  220.       *ptr = (void *) (((hash_entry *) *ptr)->next);
  221.     }
  222.  
  223.   *key = ((hash_entry *) *ptr)->key;
  224.   *data = ((hash_entry *) *ptr)->data;
  225.   return 0;
  226. }
  227.  
  228.  
  229. static size_t
  230. lookup (htab, key, keylen, hval)
  231.      hash_table *htab;
  232.      const char *key;
  233.      size_t keylen;
  234.      unsigned long hval;
  235. {
  236.   unsigned long hash;
  237.   size_t idx;
  238.   hash_entry *table = (hash_entry *) htab->table;
  239.  
  240.   /* First hash function: simply take the modul but prevent zero.  */
  241.   hash = 1 + hval % htab->size;
  242.  
  243.   idx = hash;
  244.  
  245.   if (table[idx].used)
  246.     {
  247.       if (table[idx].used == hval && table[idx].key[keylen] == '\0'
  248.       && strncmp (key, table[idx].key, keylen) == 0)
  249.     return idx;
  250.  
  251.       /* Second hash function as suggested in [Knuth].  */
  252.       hash = 1 + hval % (htab->size - 2);
  253.  
  254.       do
  255.     {
  256.       if (idx <= hash)
  257.         idx = htab->size + idx - hash;
  258.       else
  259.         idx -= hash;
  260.  
  261.       /* If entry is found use it.  */
  262.       if (table[idx].used == hval && table[idx].key[keylen] == '\0'
  263.           && strncmp (key, table[idx].key, keylen) == 0)
  264.         return idx;
  265.     }
  266.       while (table[idx].used);
  267.     }
  268.   return idx;
  269. }
  270.  
  271.  
  272. /* References:
  273.    [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
  274.    [Knuth]          The Art of Computer Programming, part3 (6.4) */
  275.  
  276. static size_t
  277. lookup_2 (htab, key, hval)
  278.      hash_table *htab;
  279.      const char *key;
  280.      unsigned long hval;
  281. {
  282.   unsigned long hash;
  283.   size_t idx;
  284.   hash_entry *table = (hash_entry *) htab->table;
  285.  
  286.   /* First hash function: simply take the modul but prevent zero.  */
  287.   hash = 1 + hval % htab->size;
  288.  
  289.   idx = hash;
  290.  
  291.   if (table[idx].used)
  292.     {
  293.       if (table[idx].used == hval && strcmp (key, table[idx].key) == 0)
  294.     return idx;
  295.  
  296.       /* Second hash function as suggested in [Knuth].  */
  297.       hash = 1 + hval % (htab->size - 2);
  298.  
  299.       do
  300.     {
  301.       if (idx <= hash)
  302.         idx = htab->size + idx - hash;
  303.       else
  304.         idx -= hash;
  305.  
  306.       /* If entry is found use it.  */
  307.       if (table[idx].used == hval && strcmp (key, table[idx].key) == 0)
  308.         return idx;
  309.     }
  310.       while (table[idx].used);
  311.     }
  312.   return idx;
  313. }
  314.  
  315.  
  316. static unsigned long
  317. compute_hashval (key, keylen)
  318.      const char *key;
  319.      size_t keylen;
  320. {
  321.   size_t cnt;
  322.   unsigned long hval, g;
  323.  
  324.   /* Compute the hash value for the given string.  The algorithm
  325.      is taken from [Aho,Sethi,Ullman].  */
  326.   cnt = 0;
  327.   hval = keylen;
  328.   while (cnt < keylen)
  329.     {
  330.       hval <<= 4;
  331.       hval += key[cnt++];
  332.       g = hval & ((unsigned long) 0xf << (LONGBITS - 4));
  333.       if (g != 0)
  334.     {
  335.       hval ^= g >> (LONGBITS - 8);
  336.       hval ^= g;
  337.     }
  338.     }
  339.   return hval != 0 ? hval : ~((unsigned long) 0);
  340. }
  341.  
  342.  
  343. unsigned long
  344. next_prime (seed)
  345.      unsigned long seed;
  346. {
  347.   /* Make it definitely odd.  */
  348.   seed |= 1;
  349.  
  350.   while (!is_prime (seed))
  351.     seed += 2;
  352.  
  353.   return seed;
  354. }
  355.  
  356.  
  357. static int
  358. is_prime (candidate)
  359.      unsigned long candidate;
  360. {
  361.   /* No even number and none less than 10 will be passed here.  */
  362.   unsigned long divn = 3;
  363.   unsigned long sq = divn * divn;
  364.  
  365.   while (sq < candidate && candidate % divn != 0)
  366.     {
  367.       ++divn;
  368.       sq += 4 * divn;
  369.       ++divn;
  370.     }
  371.  
  372.   return candidate % divn != 0;
  373. }
  374.