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