home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / unix / volume24 / mkid2 / part01 / hash.c < prev    next >
C/C++ Source or Header  |  1991-10-09  |  2KB  |  96 lines
  1. /* Copyright (c) 1986, Greg McGary */
  2. static char sccsid[] = "@(#)hash.c    1.1 86/10/09";
  3.  
  4. char *hashSearch();
  5. int h1str();
  6. int h2str();
  7.  
  8. /*
  9.     Look for `key' in the hash table starting at address `base'.
  10.     `base' is a table containing `nel' elements of size `width'.
  11.     The hashing strategy we use is open addressing.  Apply the
  12.     primary hash function `h1' and the secondary hash function
  13.     `h2' when searching for `key' or an empty slot.  `compar'
  14.     is the comparison function that should be used to compare
  15.     the key with an element of the table.  It is called with two
  16.     arguments.  The first argument is the address of the key, and
  17.     the second argument is the address of the hash table element
  18.     in question.  `compar' should return 0 if the key matches the
  19.     element or the empty slot, and non-zero otherwise.
  20.  
  21.     If a pointer to a long is provided for `probes' we will keep
  22.     a running total of open addressing hash probes.
  23. */
  24. char *
  25. hashSearch(key, base, nel, width, h1, h2, compar, probes)
  26.     char        *key;        /* key to locate */
  27.     char        *base;        /* base of hash table */
  28.     register int    nel;        /* number of elements in table */
  29.     int        width;        /* width of each element */
  30.     unsigned int    (*h1)();    /* primary hash function */
  31.     unsigned int    (*h2)();    /* secondary hash function */
  32.     int        (*compar)();    /* key comparison function */
  33.     long        *probes;
  34. {
  35.     register unsigned int    hash1;
  36.     register unsigned int    hash2;
  37.     register char    *slot;
  38.  
  39.     hash1 = (*h1)(key) % nel;
  40.     slot = &base[hash1 * width];
  41.  
  42.     if (probes)
  43.         (*probes)++;
  44.     if ((*compar)(key, slot) == 0)
  45.         return slot;
  46.  
  47.     hash2 = (*h2)(key);
  48.     for (;;) {
  49.         hash1 = (hash1 + hash2) % nel;
  50.         slot = &base[hash1 * width];
  51.  
  52.         if (probes)
  53.             (*probes)++;
  54.         if ((*compar)(key, slot) == 0)
  55.             return slot;
  56.     }
  57. }
  58.  
  59. #define    ABS(n)        ((n) < 0 ? -(n) : (n))
  60.  
  61. /*
  62.     A Primary hash function for string keys.
  63. */
  64. int
  65. h1str(key)
  66.     register char    *key;
  67. {
  68.     register int    sum;
  69.     register int    s;
  70.  
  71.     for (sum = s = 0; *key; s++)
  72.         sum += ((*key++) << s);
  73.  
  74.     return ABS(sum);
  75. }
  76.  
  77. /*
  78.     A Secondary hash function for string keys.
  79. */
  80. int
  81. h2str(key)
  82.     register char    *key;
  83. {
  84.     register int    sum;
  85.     register int    s;
  86.     char        *keysav;
  87.  
  88.     keysav = key;
  89.     key = &key[strlen(key)];
  90.  
  91.     for (sum = s = 0; key > keysav; s++)
  92.         sum += ((*--key) << s);
  93.  
  94.     return ABS(sum) | 1;
  95. }
  96.