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 38uint dtstrhash(uint h, Void_t* args, ssize_t n) 39#else 40uint dtstrhash(h,args,n) 41reg uint h; 42Void_t* args; 43ssize_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