git.sur5r.net Git - openldap/blob - build/unproto/hash.c

   1 /*++
   2 /* NAME
   3 /*      hash 3
   4 /* SUMMARY
   5 /*      compute hash value for string
   6 /* SYNOPSIS
   7 /*      int hash(string, size)
   8 /*      char *string;
   9 /*      int size;
  10 /* DESCRIPTION
  11 /*      This function computes for the given null-terminated string an
  12 /*      integer hash value in the range 0..size-1.
  13 /* SEE ALSO
  14 /* .fi
  15 /*      Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman: Compilers:
  16 /*      principles, techniques and tools; Addison-Wesley, Amsterdam, 1986.
  17 /* AUTHOR(S)
  18 /*      Wietse Venema
  19 /*      Eindhoven University of Technology
  20 /*      Department of Mathematics and Computer Science
  21 /*      Den Dolech 2, P.O. Box 513, 5600 MB Eindhoven, The Netherlands
  22 /*
  23 /*      Originally written by: P. J. Weinberger at Bell Labs.
  24 /* LAST MODIFICATION
  25 /*      92/01/15 21:53:12
  26 /* VERSION/RELEASE
  27 /*      %I
  28 /*--*/
  29
  30 static char hash_sccsid[] = "@(#) hash.c 1.1 92/01/15 21:53:12";
  31
  32 /* hash - hash a string; original author: P. J. Weinberger at Bell Labs. */
  33
  34 int     hash(s, size)
  35 register char *s;
  36 unsigned size;
  37 {
  38     register unsigned long h = 0;
  39     register unsigned long g;
  40
  41     /*
  42      * For a performance comparison with the hash function presented in K&R,
  43      * first edition, see the "Dragon" book by Aho, Sethi and Ullman.
  44      */
  45
  46     while (*s) {
  47         h = (h << 4) + *s++;
  48         if (g = (h & 0xf0000000)) {
  49             h ^= (g >> 24);
  50             h ^= g;
  51         }
  52     }
  53     return (h % size);
  54 }