about summary refs log tree commit diff
path: root/locale/programs/simple-hash.c
diff options
context:
space:
mode:
authorUlrich Drepper <drepper@redhat.com>2001-11-27 03:47:06 +0000
committerUlrich Drepper <drepper@redhat.com>2001-11-27 03:47:06 +0000
commit8e9b2075ba1d6ce2ab82c2eb2547e2c2ef3ecca8 (patch)
treede7fba86c989c6f7df1d6d7bac078813d0855fa3 /locale/programs/simple-hash.c
parentf4efd06825ba5fec62662be611d94335eff4f8f7 (diff)
downloadglibc-8e9b2075ba1d6ce2ab82c2eb2547e2c2ef3ecca8.tar.gz
glibc-8e9b2075ba1d6ce2ab82c2eb2547e2c2ef3ecca8.tar.xz
glibc-8e9b2075ba1d6ce2ab82c2eb2547e2c2ef3ecca8.zip
Update.
2001-11-21  Bruno Haible  <bruno@clisp.org>

	* charmaps/ISO-8859-16: Swap 0xa5 and 0xab entries.
Diffstat (limited to 'locale/programs/simple-hash.c')
-rw-r--r--locale/programs/simple-hash.c22
1 files changed, 10 insertions, 12 deletions
diff --git a/locale/programs/simple-hash.c b/locale/programs/simple-hash.c
index 35e32ca51e..9056fa0447 100644
--- a/locale/programs/simple-hash.c
+++ b/locale/programs/simple-hash.c
@@ -1,5 +1,5 @@
 /* Implement simple hashing table with string based keys.
-   Copyright (C) 1994, 1995, 1996, 1997, 2000 Free Software Foundation, Inc.
+   Copyright (C) 1994-1997, 2000, 2001 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
    Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, October 1994.
 
@@ -163,9 +163,11 @@ insert_entry_2 (htab, key, keylen, hval, idx, data)
     }
 
   ++htab->filled;
-  if (100 * htab->filled > 90 * htab->size)
+  if (100 * htab->filled > 75 * htab->size)
     {
-      /* Table is filled more than 90%.  Resize the table.  */
+      /* Table is filled more than 75%.  Resize the table.
+	 Experiments have shown that for best performance, this threshold
+	 must lie between 40% and 85%.  */
       unsigned long int old_size = htab->size;
 
       htab->size = next_prime (htab->size * 2);
@@ -346,22 +348,18 @@ compute_hashval (key, keylen)
      size_t keylen;
 {
   size_t cnt;
-  unsigned long int hval, g;
+  unsigned long int hval;
 
   /* Compute the hash value for the given string.  The algorithm
-     is taken from [Aho,Sethi,Ullman].  */
+     is taken from [Aho,Sethi,Ullman], modified to reduce the number of
+     collisions for short strings with very varied bit patterns.
+     See http://www.clisp.org/haible/hashfunc.html.  */
   cnt = 0;
   hval = keylen;
   while (cnt < keylen)
     {
-      hval <<= 4;
+      hval = (hval << 9) | (hval >> (LONGBITS - 9));
       hval += (unsigned long int) *(((char *) key) + cnt++);
-      g = hval & ((unsigned long) 0xf << (LONGBITS - 4));
-      if (g != 0)
-	{
-	  hval ^= g >> (LONGBITS - 8);
-	  hval ^= g;
-	}
     }
   return hval != 0 ? hval : ~((unsigned long) 0);
 }