home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / database / avl / hashpjw.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-12-31  |  2.0 KB  |  67 lines
  1. /****************************************************************************
  2. *
  3. *                    Copyright (C) 1991 Kendall Bennett.
  4. *                            All rights reserved.
  5. *
  6. * Filename:        $RCSfile: hashpjw.c $
  7. * Version:        $Revision: 1.3 $
  8. *
  9. * Language:        ANSI C
  10. * Environment:    any
  11. *
  12. * Description:    Hash function for strings. Provides better hashing than does
  13. *                hash_add().
  14. *
  15. * $Id: hashpjw.c 1.3 91/12/31 19:40:11 kjb Exp $
  16. *
  17. * Revision History:
  18. * -----------------
  19. *
  20. * $Log:    hashpjw.c $
  21. * Revision 1.3  91/12/31  19:40:11  kjb
  22. * Modified include file directories.
  23. * 
  24. * Revision 1.2  91/09/01  16:48:39  ROOT_DOS
  25. * Changed inlclude file search to search current directory
  26. * 
  27. * Revision 1.1  91/08/16  13:15:21  ROOT_DOS
  28. * Initial revision
  29. * 
  30. ****************************************************************************/
  31.  
  32. #include "debug.h"
  33. #include "hash.h"
  34.  
  35. #define    NBITS_IN_UNSIGNED        ( NBITS(unsigned int) )
  36. #define SEVENTY_FIVE_PERCENT    ((int)(NBITS_IN_UNSIGNED * .75))
  37. #define    TWELVE_PERCENT            ((int)(NBITS_IN_UNSIGNED * .125))
  38. #define    HIGH_BITS                ( ~( (unsigned)(~0) >> TWELVE_PERCENT) )
  39.  
  40. PUBLIC unsigned hash_pjw(unsigned char *name)
  41. /****************************************************************************
  42. *
  43. * Function:        hash_pjw
  44. * Parameters:    name    - String to hash
  45. * Returns:        hash value for the string
  46. *
  47. * Description:    This hash function uses a shift-and-XOR strategy to
  48. *                randomise the input key. The main iteration of the loop
  49. *                shifts the accumulated hash value to the left by a few
  50. *                bits and adds in the current character. When the number
  51. *                gets too large, it is randomised by XORing it with a
  52. *                shifted version of itself.
  53. *
  54. ****************************************************************************/
  55. {
  56.     unsigned    h = 0;            /* The hash value */
  57.     unsigned    g;
  58.  
  59.     for (; *name; name++) {
  60.         h = (h << TWELVE_PERCENT) + *name;
  61.         if ( (g = h & HIGH_BITS) != 0)
  62.             h = (h ^ (g >> SEVENTY_FIVE_PERCENT)) & ~HIGH_BITS;
  63.         }
  64.  
  65.     return h;
  66. }
  67.