home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / lucid / lemacs-19.6 / src / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-12-13  |  11.0 KB  |  465 lines
  1. /* Hash tables.
  2.    Copyright (C) 1992 Free Software Foundation, Inc.
  3.  
  4. This file is part of GNU Emacs.
  5.  
  6. GNU Emacs is free software; you can redistribute it and/or modify
  7. it under the terms of the GNU General Public License as published by
  8. the Free Software Foundation; either version 2, or (at your option)
  9. any later version.
  10.  
  11. GNU Emacs is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with GNU Emacs; see the file COPYING.  If not, write to
  18. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19.  
  20. #include <string.h>
  21. #include "hash.h"
  22.  
  23. #ifdef emacs
  24. #include "config.h"
  25. #include "lisp.h"
  26. extern Lisp_Object Qnil;
  27. extern char *elisp_hvector_malloc();
  28. extern void elisp_hvector_free();
  29. #define NULL_ENTRY ((void *) Qnil)
  30. #else
  31. #define NULL_ENTRY ((void *) 1)
  32. #endif
  33.  
  34. #define MAXPRIME 62
  35.  
  36. static int 
  37. primes []={
  38.   29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 
  39.   761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 
  40.   8419, 10103, 12143, 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361, 
  41.   62851, 75431, 90523, 108631, 130363, 156437, 187751, 225307, 270371, 324449, 
  42.   389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263, 1674319,
  43.   2009191, 2411033, 2893249
  44. };
  45.  
  46. /* strings code */
  47.  
  48. /* from base/generic-hash.cc, and hence from Dragon book, p436 */
  49. static unsigned long
  50. string_hash (x)
  51.      char *x;
  52. { 
  53.   unsigned int h = 0;
  54.   unsigned int g;
  55.  
  56.   if (!x) return 0;
  57.  
  58.   while (*x != 0)
  59.   {
  60.     h = (h << 4) + *x++;
  61.     if ((g = h & 0xf0000000) != 0)
  62.       h = (h ^ (g >> 24)) ^ g;
  63.   }
  64.  
  65.   return h;
  66. }
  67.  
  68. static int 
  69. string_eq (st1, st2)
  70.      char *st1, *st2;
  71. {
  72.   if (!st1)
  73.     return (st2)?0:1;
  74.   else if (!st2)
  75.     return 0;
  76.   else
  77.     return !strcmp (st1, st2);
  78. }
  79.  
  80.  
  81. static unsigned int 
  82. prime_size (size)
  83.      unsigned int size;
  84. {
  85.   unsigned int i;
  86.   for (i = 0; i < MAXPRIME; i++)
  87.     if (size <= primes [i]) return primes [i];
  88.   return primes [MAXPRIME - 1];
  89. }
  90.  
  91. static void 
  92. rehash (/* hentry *harray, c_hashtable ht, unsigned int size */);
  93.  
  94. #define KEYS_DIFFER_P(old, new, testfun) \
  95.   ((testfun)?(((old) == (new))?0:(!(testfun ((old), new)))):((old) != (new)))
  96.  
  97. void *
  98. gethash (key, hash, ret_value)
  99.      void *key; c_hashtable hash; void **ret_value;
  100. {
  101.   hentry *harray = hash->harray;
  102.   int (*test_function)() = hash->test_function;
  103.   unsigned int hsize = hash->size;
  104.   unsigned int hcode_initial = 
  105.     (hash->hash_function)?(hash->hash_function(key)):((unsigned long) key);
  106.   unsigned int hcode = hcode_initial % hsize;
  107.   hentry *e = &harray [hcode];
  108.   void *e_key = e->key;
  109.  
  110.   if (!key) 
  111.     {
  112.       *ret_value = hash->zero_entry;
  113.       return (void *) hash->zero_set;
  114.     }
  115.     
  116.   if ((e_key)?
  117.       (KEYS_DIFFER_P (e_key, key, test_function)):
  118.       (e->contents == NULL_ENTRY))
  119.     {
  120.       unsigned int h2 = hsize - 2;
  121.       unsigned int incr = 1 + (hcode_initial % h2);
  122.       do
  123.         {
  124.           hcode = hcode + incr;
  125.           if (hcode >= hsize) hcode = hcode - hsize;
  126.           e = &harray [hcode];
  127.           e_key = e->key;
  128.         } 
  129.       while ((e_key)?
  130.              (KEYS_DIFFER_P (e_key, key, test_function)):
  131.              (e->contents == NULL_ENTRY));
  132.     }
  133.  
  134.   *ret_value = e->contents;
  135.   return e->key;
  136. }
  137.  
  138. void 
  139. clrhash (hash)
  140.      c_hashtable hash;
  141. {
  142.   memset (hash->harray, 0, sizeof (hentry) * hash->size);
  143.   hash->zero_entry = 0;
  144.   hash->zero_set = 0;
  145.   hash->fullness = 0;
  146. }
  147.  
  148. void
  149. free_hashtable (hash)
  150.      c_hashtable hash;
  151. {
  152. #ifdef emacs
  153.   if (hash->elisp_table) return;
  154. #endif
  155.   xfree (hash->harray);
  156.   xfree (hash);
  157. }
  158.  
  159. c_hashtable
  160. make_hashtable (hsize)
  161.      unsigned int hsize;
  162. {
  163.   c_hashtable res = (c_hashtable) xmalloc (sizeof (struct _C_hashtable));
  164.   memset (res, 0, sizeof (struct _C_hashtable));
  165.   res->size = prime_size ((13 * hsize) / 10);
  166.   res->harray = (hentry *) xmalloc (sizeof (hentry) * res->size);
  167.   clrhash (res);
  168.   return res;
  169. }
  170.  
  171. c_hashtable
  172. make_general_hashtable (unsigned int hsize,
  173.             unsigned long (*hash_function)(),
  174.             int (*test_function)())
  175. {
  176.   c_hashtable res = (c_hashtable) xmalloc (sizeof (struct _C_hashtable));
  177.   memset (res, 0, sizeof (struct _C_hashtable));
  178.   res->size = prime_size ((13 * hsize) / 10);
  179.   res->harray = (hentry *) xmalloc (sizeof (hentry) * res->size);
  180.   res->hash_function = hash_function;
  181.   res->test_function = test_function;
  182.   clrhash (res);
  183.   return res;
  184. }
  185.  
  186. c_hashtable 
  187. make_strings_hashtable (hsize)
  188.      unsigned int hsize;
  189. {
  190.   return make_general_hashtable (hsize, string_hash, string_eq);
  191. }
  192.  
  193. #ifdef emacs
  194. unsigned int
  195. compute_harray_size (hsize)
  196.      unsigned int hsize;
  197. {
  198.   return prime_size ((13 * hsize) / 10);
  199. }
  200. #endif
  201.  
  202. void
  203. copy_hash (dest, src)
  204.      c_hashtable dest; c_hashtable src;
  205. {
  206. #ifdef emacs
  207.   /* if these are not the same, then we are losing here */
  208.   if ( ((dest->elisp_table)?1:0) != ((src->elisp_table)?1:0) )
  209.     {
  210.       extern void error ();
  211.       error ("Incompatible hashtable types to copy_hash.");
  212.       return;
  213.     }
  214. #endif
  215.  
  216.   if (dest->size != src->size)
  217.     {
  218. #ifdef emacs
  219.       if (dest->elisp_table) 
  220.         elisp_hvector_free (dest->harray, dest->elisp_table);
  221.       else
  222. #endif
  223.         xfree (dest->harray);
  224.  
  225.       dest->size = src->size;
  226. #ifdef emacs
  227.       if (dest->elisp_table)
  228.         dest->harray = 
  229.           (hentry *) elisp_hvector_malloc
  230.             (sizeof (hentry) * dest->size, dest->elisp_table);
  231.       else
  232. #endif
  233.         dest->harray = 
  234.           (hentry *) 
  235.             xmalloc (sizeof (hentry) * dest->size);
  236.     }
  237.   dest->fullness = src->fullness;
  238.   dest->zero_entry = src->zero_entry;
  239.   dest->zero_set = src->zero_set;
  240.   dest->hash_function = src->hash_function;
  241.   dest->test_function = src->test_function;
  242.   memcpy (dest->harray, src->harray, sizeof (hentry) * dest->size);
  243. }
  244.   
  245. static void
  246. grow_hashtable (hash, new_size)
  247.      c_hashtable hash; unsigned int new_size;
  248. {
  249.   unsigned int old_hsize = hash->size;
  250.   hentry *old_harray = hash->harray;
  251.   unsigned int new_hsize = prime_size (new_size);
  252.   hentry *new_harray;
  253.  
  254. #ifdef emacs
  255.   if (hash->elisp_table)
  256.     new_harray = 
  257.       (hentry *) elisp_hvector_malloc
  258.         (sizeof (hentry) * new_hsize, hash->elisp_table);
  259.   else
  260. #endif
  261.     new_harray =
  262.       (hentry *) xmalloc (sizeof (hentry) * new_hsize);
  263.  
  264.   hash->size = new_hsize;
  265.   hash->harray = new_harray;
  266.  
  267.   /* do the rehash on the "grown" table */
  268.   {
  269.     int old_zero_set = hash->zero_set;
  270.     void *old_zero_entry = hash->zero_entry;
  271.     clrhash (hash);
  272.     hash->zero_set = old_zero_set;
  273.     hash->zero_entry = old_zero_entry;
  274.     rehash (old_harray, hash, old_hsize);
  275.   }
  276.  
  277. #ifdef emacs
  278.   if (hash->elisp_table) 
  279.     elisp_hvector_free (old_harray, hash->elisp_table);
  280.   else
  281. #endif
  282.     xfree (old_harray);
  283. }
  284.  
  285. void 
  286. puthash (key, cont, hash)
  287.      void *key; void *cont; c_hashtable hash;
  288. {
  289.   unsigned int hsize = hash->size;
  290.   int (*test_function)() = hash->test_function;
  291.   unsigned int fullness = hash->fullness;
  292.   hentry *harray;
  293.   void *e_key;
  294.   hentry *e;
  295.   unsigned int hcode_initial = 
  296.     (hash->hash_function)?(hash->hash_function(key)):((unsigned long) key);
  297.   unsigned int hcode;
  298.   unsigned int incr = 0;
  299.   unsigned int h2;
  300.   void *oldcontents;
  301.  
  302.   if (!key) 
  303.     {
  304.       hash->zero_entry = cont;      
  305.       hash->zero_set = 1;
  306.       return;
  307.     }
  308.  
  309.   if (hsize < (1 + ((13 * fullness) / 10)))
  310.     {
  311.       grow_hashtable (hash, hsize + 1);
  312.       hsize = hash->size;
  313.       fullness = hash->fullness;
  314.     }
  315.  
  316.   harray= hash->harray;
  317.   h2 = hsize - 2;
  318.  
  319.   hcode = hcode_initial % hsize;
  320.   
  321.   e_key = harray [hcode].key;
  322.   if (e_key && (KEYS_DIFFER_P (e_key, key, test_function)))
  323.     {
  324.       h2 = hsize - 2;
  325.       incr = 1 + (hcode_initial % h2);
  326.       do
  327.         {
  328.           hcode = hcode + incr;
  329.           if (hcode >= hsize) hcode = hcode - hsize;
  330.           e_key = harray [hcode].key;
  331.         } 
  332.       while (e_key && (KEYS_DIFFER_P (e_key, key, test_function)));
  333.     }
  334.   oldcontents = harray [hcode].contents;
  335.   harray [hcode].key = (void *) key;
  336.   harray [hcode].contents = (void *) cont;
  337.   /* if the entry that we used was a deleted entry,
  338.      check for a non deleted entry of the same key,
  339.      then delete it */
  340.   if (!e_key && (oldcontents == NULL_ENTRY))
  341.     {
  342.       if (!incr) incr = 1 + ((unsigned long) key % h2);
  343.  
  344.       do
  345.         {
  346.           hcode = hcode + incr;
  347.           if (hcode >= hsize) hcode = hcode - hsize;
  348.           e = &harray [hcode];
  349.           e_key = e->key;
  350.         }
  351.       while ((e_key)?
  352.              (KEYS_DIFFER_P (e_key, key, test_function)):
  353.              (e->contents == NULL_ENTRY));
  354.  
  355.       if (e_key)
  356.         {
  357.           e->key = 0;
  358.           e->contents = NULL_ENTRY;
  359.         }
  360.     }
  361.  
  362.   /* only increment the fullness when we used up a new hentry */
  363.   if (!e_key || (KEYS_DIFFER_P (e_key, key, test_function)))
  364.     hash->fullness++;
  365. }
  366.  
  367. static void
  368. rehash (harray, hash, size)
  369.      hentry *harray; c_hashtable hash; unsigned int size;
  370. {
  371.   hentry *limit = harray + size;
  372.   hentry *e;
  373.   for (e = harray; e < limit; e++) 
  374.     if (e->key) puthash (e->key, e->contents, hash);
  375. }
  376.  
  377. void 
  378. remhash (key, hash)
  379.      void *key; c_hashtable hash;
  380. {
  381.   hentry *harray = hash->harray;
  382.   int (*test_function)() = hash->test_function;
  383.   unsigned int hsize = hash->size;
  384.   unsigned int hcode_initial = 
  385.     (hash->hash_function)?(hash->hash_function(key)):((unsigned long) key);
  386.   unsigned int hcode = hcode_initial % hsize;
  387.   hentry *e = &harray [hcode];
  388.   void *e_key = e->key;
  389.  
  390.   if (!key) 
  391.     {
  392.       hash->zero_entry = 0;
  393.       hash->zero_set = 0;
  394.       return;
  395.     }
  396.  
  397.   if ((e_key)?
  398.       (KEYS_DIFFER_P (e_key, key, test_function)):
  399.       (e->contents == NULL_ENTRY))
  400.     {
  401.       unsigned int h2 = hsize - 2;
  402.       unsigned int incr = 1 + (hcode_initial % h2);
  403.       do
  404.         {
  405.           hcode = hcode + incr;
  406.           if (hcode >= hsize) hcode = hcode - hsize;
  407.           e = &harray [hcode];
  408.           e_key = e->key;
  409.         }
  410.       while ((e_key)?
  411.              (KEYS_DIFFER_P (e_key, key, test_function)):
  412.              (e->contents == NULL_ENTRY));
  413.     }
  414.   if (e_key)
  415.     {
  416.       e->key = 0;
  417.       e->contents = NULL_ENTRY;
  418. /* This seems to break the world and I don't understand why. 
  419.    Keymaps need a correct count of how many items are really in
  420.    the table, taking remhash into account, but it looks like I
  421.    have to do it by hand in the keymap code.  -jwz
  422.  
  423.       hash->fullness--;
  424.  */
  425.     }
  426. }
  427.  
  428. void 
  429. maphash (mf, hash, arg)
  430.      maphash_function mf; c_hashtable hash; void *arg;
  431. {
  432.   hentry *e;
  433.   hentry *limit;
  434.   
  435.   if (hash->zero_set) (*mf) (0, hash->zero_entry, arg);
  436.  
  437.   for (e = hash->harray, limit = e + hash->size; e < limit; e++)
  438.     if (e->key) (*mf) (e->key, e->contents, arg);
  439. }
  440.  
  441.  
  442. void 
  443. map_remhash (predicate, hash, arg)
  444.      remhash_predicate predicate; 
  445.      c_hashtable hash; 
  446.      void *arg;
  447. {
  448.   hentry *e;
  449.   hentry *limit;
  450.   
  451.   if (hash->zero_set && ((*predicate) (0, hash->zero_entry, arg)))
  452.     {
  453.       hash->zero_set = 0;
  454.       hash->zero_entry = 0;
  455.     }
  456.  
  457.   for (e = hash->harray, limit = e + hash->size; e < limit; e++)
  458.     if ((*predicate) (e->key, e->contents, arg))
  459.       {
  460.         e->key = 0;
  461.         e->contents = NULL_ENTRY;
  462.       }
  463. }
  464.  
  465.