X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fhash-pjw.c;h=18f9f01bc9391c230cc2ab04342a68544d0f1a5f;hb=1276a2c5f24c0c932426aca9c899fa524d2443f2;hp=0a14b3e7af9b1f28008b253b3a44827fbf38fa77;hpb=ab352daed97372060cc038c30f2b6394d8ff1c54;p=gnulib.git

diff --git a/lib/hash-pjw.c b/lib/hash-pjw.c
index 0a14b3e7a..18f9f01bc 100644
--- a/lib/hash-pjw.c
+++ b/lib/hash-pjw.c
@@ -1,10 +1,11 @@
 /* hash-pjw.c -- compute a hash value from a NUL-terminated string.
-   Copyright 2001, 2003 Free Software Foundation, Inc.
 
-   This program is free software; you can redistribute it and/or modify
+   Copyright (C) 2001, 2003, 2006, 2009-2014 Free Software Foundation, Inc.
+
+   This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
-   the Free Software Foundation; either version 2, or (at your option)
-   any later version.
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
 
    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
@@ -12,34 +13,28 @@
    GNU General Public License for more details.
 
    You should have received a copy of the GNU General Public License
-   along with this program; if not, write to the Free Software Foundation,
-   Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
 
-#if HAVE_CONFIG_H
-# include <config.h>
-#endif
+#include <config.h>
 
 #include "hash-pjw.h"
 
+#include <limits.h>
+
+#define SIZE_BITS (sizeof (size_t) * CHAR_BIT)
+
 /* A hash function for NUL-terminated char* strings using
-   the method described in Aho, Sethi, & Ullman, p 436.
-   Note that this hash function produces a lot of collisions when used
-   with short strings with very varied bit patterns.
+   the method described by Bruno Haible.
    See http://www.haible.de/bruno/hashfunc.html.  */
 
-unsigned int
-hash_pjw (const void *x, unsigned int tablesize)
+size_t
+hash_pjw (const void *x, size_t tablesize)
 {
-  const char *s = x;
-  unsigned int h = 0;
-  unsigned int g;
-
-  while (*s != 0)
-    {
-      h = (h << 4) + *s++;
-      if ((g = h & (unsigned int) 0xf0000000) != 0)
-        h = (h ^ (g >> 24)) ^ g;
-    }
-
-  return (h % tablesize);
+  const char *s;
+  size_t h = 0;
+
+  for (s = x; *s; s++)
+    h = *s + ((h << 9) | (h >> (SIZE_BITS - 9)));
+
+  return h % tablesize;
 }