1 /***********************************************************************
2 * *
3 * This software is part of the ast package *
4 * Copyright (c) 1985-2011 AT&T Intellectual Property *
5 * and is licensed under the *
6 * Eclipse Public License, Version 1.0 *
7 * by AT&T Intellectual Property *
8 * *
9 * A copy of the License is available at *
10 * http://www.eclipse.org/org/documents/epl-v10.html *
11 * (with md5 checksum b35adb5213ca9657e911e9befb180842) *
12 * *
13 * Information and Software Systems Research *
14 * AT&T Research *
15 * Florham Park NJ *
16 * *
17 * Glenn Fowler <gsf@research.att.com> *
18 * David Korn <dgk@research.att.com> *
19 * Phong Vo <kpv@research.att.com> *
20 * *
21 ***********************************************************************/
22 #include "dthdr.h"
23
24 /* Hashing a string into an unsigned integer.
25 ** The basic method is to continuingly accumulate bytes and multiply
26 ** with some given prime. The length n of the string is added last.
27 ** The recurrent equation is like this:
28 ** h[k] = (h[k-1] + bytes)*prime for 0 <= k < n
29 ** h[n] = (h[n-1] + n)*prime
30 ** The prime is chosen to have a good distribution of 1-bits so that
31 ** the multiplication will distribute the bits in the accumulator well.
32 ** The below code accumulates 2 bytes at a time for speed.
33 **
34 ** Written by Kiem-Phong Vo (02/28/03)
35 */
36
37 #if __STD_C
dtstrhash(uint h,Void_t * args,ssize_t n)38 uint dtstrhash(uint h, Void_t* args, ssize_t n)
39 #else
40 uint dtstrhash(h,args,n)
41 reg uint h;
42 Void_t* args;
43 ssize_t n;
44 #endif
45 {
46 unsigned char *s = (unsigned char*)args;
47
48 if(n <= 0)
49 { for(; *s != 0; s += s[1] ? 2 : 1)
50 h = (h + (s[0]<<8) + s[1])*DT_PRIME;
51 n = s - (unsigned char*)args;
52 }
53 else
54 { unsigned char* ends;
55 for(ends = s+n-1; s < ends; s += 2)
56 h = (h + (s[0]<<8) + s[1])*DT_PRIME;
57 if(s <= ends)
58 h = (h + (s[0]<<8))*DT_PRIME;
59 }
60 return (h+n)*DT_PRIME;
61 }
62