home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: Product / Product.zip / ISPSRC.ZIP / hash.c < prev    next >
C/C++ Source or Header  |  1992-08-14  |  3KB  |  101 lines
  1. /* -*- Mode:Text -*- */
  2. #ifndef lint
  3. static char Rcs_Id[] =
  4.     "$Id: hash.c,v 1.12 91/07/11 19:52:07 geoff Exp $";
  5. #endif
  6.  
  7. /*
  8.  * hash.c - a simple hash function for ispell
  9.  *
  10.  * Pace Willisson, 1983
  11.  *
  12.  * Copyright 1987, 1988, 1989, by Geoff Kuenning, Manhattan Beach, CA
  13.  * Permission for non-profit use is hereby granted.
  14.  * All other rights reserved.
  15.  * See "version.h" for a more complete copyright notice.
  16.  */
  17.  
  18. /*
  19.  * $Log:    hash.c,v $
  20.  * Revision 1.12  91/07/11  19:52:07  geoff
  21.  * Remove the include of stdio.h, since ispell.h now does this.
  22.  * 
  23.  * Revision 1.11  91/01/27  00:43:34  geoff
  24.  * Replace the old hashing algorithm with a new one based on that developed
  25.  * by Ian Dall.  (The difference between Ian's algorithm and mine is twofold:
  26.  * he shifted by 3, while I found 5 to be better, and I do the shift in a
  27.  * single C statement while he did it in 1-bit steps).
  28.  * 
  29.  * Revision 1.10  90/12/31  00:59:13  geoff
  30.  * Reformat to follow a consistent convention throughout ispell
  31.  * 
  32.  * Revision 1.9  89/06/09  15:53:05  geoff
  33.  * Add support for the internal "character" type, ichar_t.
  34.  * 
  35.  * Revision 1.8  89/04/28  01:08:41  geoff
  36.  * Change Header to Id;  nobody cares about my pathnames.
  37.  * 
  38.  * Revision 1.7  89/04/03  01:55:17  geoff
  39.  * Add support for string characters.
  40.  * 
  41.  * Revision 1.6  88/12/26  02:25:50  geoff
  42.  * Add a copyright notice.
  43.  * 
  44.  * Revision 1.5  88/04/30  22:12:23  geoff
  45.  * Fix some lint complaints.
  46.  * 
  47.  * Revision 1.4  88/02/20  23:11:22  geoff
  48.  * If CAPITALIZATION is enabled, force all strings to uppercase while
  49.  * hashing them.
  50.  * 
  51.  * Revision 1.3  87/03/27  17:20:36  geoff
  52.  * Do the final modulus calculation with a long to avoid overflows.
  53.  * 
  54.  * Revision 1.2  87/01/17  13:11:39  geoff
  55.  * Add RCS ID keywords
  56.  * 
  57.  */
  58.  
  59. #include "config.h"
  60. #include "ispell.h"
  61.  
  62. /*
  63.  * The following hash algorithm is due to Ian Dall, with slight modifications
  64.  * by Geoff Kuenning to reflect the results of testing with the English
  65.  * dictionaries actually distributed with ispell.
  66.  */
  67. #define HASHSHIFT   5
  68.  
  69. #ifdef CAPITALIZATION
  70. #define HASHUPPER(c)    mytoupper(c)
  71. #else /* CAPITALIZATION */
  72. #define HASHUPPER(c)    c
  73. #endif /* CAPITALIZATION */
  74.  
  75. hash (s, hashtblsize)
  76.     register ichar_t *    s;
  77.     register        hashtblsize;
  78.     {
  79.     register long    h = 0;
  80.     register int    i;
  81.  
  82. #ifdef ICHAR_IS_CHAR
  83.     for (i = 4;  i--  &&  *s != 0;  )
  84.     h = (h << 8) | HASHUPPER (*s++);
  85. #else /* ICHAR_IS_CHAR */
  86.     for (i = 2;  i--  &&  *s != 0;  )
  87.     h = (h << 16) | HASHUPPER (*s++);
  88. #endif /* ICHAR_IS_CHAR */
  89.     while (*s != 0)
  90.     {
  91.     /*
  92.      * We have to do circular shifts the hard way, since C doesn't
  93.      * have them even though the hardware probably does.  Oh, well.
  94.      */
  95.     h = (h << HASHSHIFT)
  96.       | ((h >> (32 - HASHSHIFT)) & ((1 << HASHSHIFT) - 1));
  97.     h ^= HASHUPPER (*s++);
  98.     }
  99.     return (unsigned long) h % hashtblsize;
  100.     }
  101.