This is the mail archive of the gdb-patches@sources.redhat.com mailing list for the GDB project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

[RFA]: Small bcache hashing cleanup



This patch does 4 things.

1. Adds a little info to the comment about whose hash it is.
2. Changes what appear to be random, arbitrary numbers in the hash
function into defines with names that show they aren't arbitrary, but specifically
chosen.
3. Updates the hash function to fix a problem the authors noticed in the
first version of the hash (the reference code they provided had
forgotten to initialize the hash value to the right number).
4. Fixes the indenting, since it was completely wrong.

I consider the whole thing a cleanup patch, which is why i didn't
split the indenting into a seperate patch. Fixing the init problem amounts to less than one
line of code.

Though, it should be noted, with the proper initialization of the hash to that value, we
improve our max chainlength in the bcache's hash by 2-3 (gdb without
the patch = max chainlength of 13 debugging gdb, gdb with the patch =
max chainlength of 11 debugging gdb. no change in average/minimum length)

This patch has been sitting in my tree forever (along with some other
changes i'll be submitting soon), so i figured i'd send
it in.



Index: bcache.c
===================================================================
RCS file: /cvs/src/src/gdb/bcache.c,v
retrieving revision 1.4
diff -c -3 -p -r1.4 bcache.c
*** bcache.c	2000/06/05 20:49:53	1.4
--- bcache.c	2000/12/08 05:01:18
***************
*** 28,51 ****
  #include "bcache.h"
  #include "gdb_string.h"		/* For memcpy declaration */
  
! /* The old hash function was stolen from SDBM. This is what DB 3.0 uses now,
   * and is better than the old one. 
   */
  
  unsigned long
  hash(void *addr, int length)
  {
! 		const unsigned char *k, *e;
! 		unsigned long h;
! 		
! 		k = (const unsigned char *)addr;
! 		e = k+length;
! 		for (h=0; k< e;++k)
! 		{
! 				h *=16777619;
! 				h ^= *k;
! 		}
! 		return (h);
  }
  
  /* Growing the bcache's hash table.  */
--- 28,55 ----
  #include "bcache.h"
  #include "gdb_string.h"		/* For memcpy declaration */
  
! /* The old hash function was stolen from SDBM. This is what DB 3.1 uses now,
   * and is better than the old one. 
+  * It's the Foller/Noll/Vo hash code, for those who care.
   */
+ #define FNV0_32_INIT (0) /* To use FNV-0, not recommended */
+ #define FNV1_32_INIT (0x811c9dc5) 
+ #define FNV_32_PRIME (0x01000193)
  
  unsigned long
  hash(void *addr, int length)
  {
!   const unsigned char *k, *e;
!   unsigned long h=FNV1_32_INIT;
!   
!   k = (const unsigned char *)addr;
!   e = k+length;
!   for (; k< e;++k)
!     {
!       h *= FNV_32_PRIME;
!       h ^= *k;
!     }
!   return (h);
  }
  
  /* Growing the bcache's hash table.  */


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]