14887Schin /*********************************************************************** 24887Schin * * 34887Schin * This software is part of the ast package * 4*12068SRoger.Faulkner@Oracle.COM * Copyright (c) 1985-2010 AT&T Intellectual Property * 54887Schin * and is licensed under the * 64887Schin * Common Public License, Version 1.0 * 78462SApril.Chin@Sun.COM * by AT&T Intellectual Property * 84887Schin * * 94887Schin * A copy of the License is available at * 104887Schin * http://www.opensource.org/licenses/cpl1.0.txt * 114887Schin * (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) * 124887Schin * * 134887Schin * Information and Software Systems Research * 144887Schin * AT&T Research * 154887Schin * Florham Park NJ * 164887Schin * * 174887Schin * Glenn Fowler <gsf@research.att.com> * 184887Schin * David Korn <dgk@research.att.com> * 194887Schin * Phong Vo <kpv@research.att.com> * 204887Schin * * 214887Schin ***********************************************************************/ 224887Schin #include "dthdr.h" 234887Schin 244887Schin /* Hashing a string into an unsigned integer. 254887Schin ** The basic method is to continuingly accumulate bytes and multiply 264887Schin ** with some given prime. The length n of the string is added last. 274887Schin ** The recurrent equation is like this: 284887Schin ** h[k] = (h[k-1] + bytes)*prime for 0 <= k < n 294887Schin ** h[n] = (h[n-1] + n)*prime 304887Schin ** The prime is chosen to have a good distribution of 1-bits so that 314887Schin ** the multiplication will distribute the bits in the accumulator well. 324887Schin ** The below code accumulates 2 bytes at a time for speed. 334887Schin ** 344887Schin ** Written by Kiem-Phong Vo (02/28/03) 354887Schin */ 364887Schin 374887Schin #if __STD_C dtstrhash(reg uint h,Void_t * args,reg int n)384887Schinuint dtstrhash(reg uint h, Void_t* args, reg int n) 394887Schin #else 404887Schin uint dtstrhash(h,args,n) 414887Schin reg uint h; 424887Schin Void_t* args; 434887Schin reg int n; 444887Schin #endif 454887Schin { 464887Schin reg unsigned char* s = (unsigned char*)args; 474887Schin 484887Schin if(n <= 0) 494887Schin { for(; *s != 0; s += s[1] ? 2 : 1) 504887Schin h = (h + (s[0]<<8) + s[1])*DT_PRIME; 514887Schin n = s - (unsigned char*)args; 524887Schin } 534887Schin else 544887Schin { reg unsigned char* ends; 554887Schin for(ends = s+n-1; s < ends; s += 2) 564887Schin h = (h + (s[0]<<8) + s[1])*DT_PRIME; 574887Schin if(s <= ends) 584887Schin h = (h + (s[0]<<8))*DT_PRIME; 594887Schin } 604887Schin return (h+n)*DT_PRIME; 614887Schin } 62