1 /*********************************************************************** 2 * * 3 * This software is part of the ast package * 4 * Copyright (c) 1985-2007 AT&T Knowledge Ventures * 5 * and is licensed under the * 6 * Common Public License, Version 1.0 * 7 * by AT&T Knowledge Ventures * 8 * * 9 * A copy of the License is available at * 10 * http://www.opensource.org/licenses/cpl1.0.txt * 11 * (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) * 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 38 uint dtstrhash(reg uint h, Void_t* args, reg int n) 39 #else 40 uint dtstrhash(h,args,n) 41 reg uint h; 42 Void_t* args; 43 reg int n; 44 #endif 45 { 46 reg 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 { reg 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