[frontierkernel-commits] Frontier/Common/source langhash.c,1.4.2.3,1.4.2.4

[Andre R. <and...@us...>]

Update of /cvsroot/frontierkernel/Frontier/Common/source
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv20622

Modified Files:
      Tag: New_Tables_Experiment-branch
	langhash.c 
Log Message:
Switched to Paul Hsieh's SuperFastHash algorithm for hashing, although because we need to lower-case the string on the fly, it may not be superfast anymore.

Index: langhash.c
===================================================================
RCS file: /cvsroot/frontierkernel/Frontier/Common/source/langhash.c,v
retrieving revision 1.4.2.3
retrieving revision 1.4.2.4
diff -C2 -d -r1.4.2.3 -r1.4.2.4
*** langhash.c	11 Nov 2004 14:52:59 -0000	1.4.2.3
--- langhash.c	11 Nov 2004 16:54:01 -0000	1.4.2.4
***************
*** 1114,1144 ****
  #ifdef flv10tables
  
! 	unsigned long hashfunction (const bigstring bs) {
! 		
  		/*
! 		2004-11-10 aradke: New hash function with wider spread, inspired by K&R "Programming in C".
! 		
! 		We loop from the end to the beginning of the string so that the multiplication
! 		will magnify the difference between two strings that differ only in the last
! 		position, e.g. consecutively numbered items.
! 		
! 		The return value is unsigned long because we expect to switch to a variable number
! 		of buckets on a per-table basis soon. When we get there, we will switch to returning
! 		hashval un-mod-ed, so it can be saved with the hashkey in the node and be re-used
! 		for when we need to re-bucket all items.
  		*/
  
! 		register unsigned long hashval = 0;
! 		register ptrstring pend;
! 		register ptrstring p;
! 		
! 		pend = (ptrstring) bs;
  		
! 		p = pend + stringlength (bs);
  		
! 		while (p > pend)
! 			hashval = 31 * hashval + (unsigned long) getlower (*p--);
  
! 		return (hashval);
  		} /*hashfunction*/
  
--- 1114,1192 ----
  #ifdef flv10tables
  
! 	#undef getshort
! 	
! 	#ifdef MACVERSION
! 		#define getshort(d) (((getlower ((d)[0])) << 8UL) + (getlower ((d)[1])))
! 	#endif
! 	
! 	#ifdef WIN95VERSION
! 		#define getshort(d) (((getlower ((d)[1])) << 8UL) + (getlower ((d)[0])))
! 	#endif
! 	
! 	
! 	unsigned long hashfunction (const bigstring bskey) {
! 	
  		/*
! 		2004-11-11 aradke: adaptation of Paul Hsieh's "SuperFastHash" algorithm,
! 		see http://www.azillionmonkeys.com/qed/hash.html for details.
! 		the main difference is that we need to lower-case the key on the fly.
  		*/
  
! 		unsigned long hash;
! 		int i, rem;
! 		const unsigned char *pkey = stringbaseaddress (bskey);
! 		int len = stringlength (bskey);
! 
! 		if (len == 0)
! 			return (0);
! 
! 		hash = (unsigned long) len; /*avoid 0 -> 0 trap*/
  		
! 		rem = len & 3;
! 		len >>= 2;
! 
! 		for (i=0; i < len; i++) { /*main loop*/
! 
! 			hash += getshort (pkey);
! 
! 			pkey += 2 * sizeof (char);
! 
! 			hash ^= hash << 16;
! 
! 			hash ^= getshort (pkey) << 11;
! 
! 			pkey += 2 * sizeof (char);
! 
! 			hash += hash >> 11;
! 			} /*for*/
! 
  		
! 		switch (rem) { /*handle end cases*/
  
! 			case 3: hash += getshort (pkey);
! 					hash ^= hash << 16;
! 					hash ^= pkey[2 * sizeof (char)] << 18;
! 					hash += hash >> 11;
! 					break;
! 
! 			case 2: hash += getshort (pkey);
! 					hash ^= hash << 11;
! 					hash += hash >> 17;
! 					break;
! 
! 			case 1: hash += *pkey;
! 					hash ^= hash << 10;
! 					hash += hash >> 1;
! 					
! 			} /*switch*/
! 
! 		/* Force "avalanching" of final 127 bits */
! 		hash ^= hash << 3;
! 		hash += hash >> 5;
! 		hash ^= hash << 2;
! 		hash += hash >> 15;
! 		hash ^= hash << 10;
! 
! 		return (hash);
  		} /*hashfunction*/