X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Fhash.c;h=9961612ccf0ec2f5b24e61c2dd2650e9250cfc16;hb=ccf2f45c091ce1555b4e2a36186c501675c18a59;hp=f6bad64b8889dbc2b3bf860924f8fc21d470489a;hpb=2bfc3a138f308ffb38634a92b23bdc7b62592324;p=pspp-builds.git

diff --git a/src/hash.c b/src/hash.c
index f6bad64b..9961612c 100644
--- a/src/hash.c
+++ b/src/hash.c
@@ -18,12 +18,12 @@
    02111-1307, USA. */
 
 #include <config.h>
+#include "hash.h"
 #include <assert.h>
 #include <limits.h>
 #include <stdlib.h>
 #include "algorithm.h"
 #include "alloc.h"
-#include "hash.h"
 #include "misc.h"
 #include "str.h"
 
@@ -76,43 +76,39 @@ next_power_of_2 (size_t x)
     }
 }
 
-/* Colin Plumb's "one-at-a-time" hash, for bytes. */
+/* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */
+#define FNV_32_PRIME 16777619u
+#define FNV_32_BASIS 2166136261u
+
+/* Fowler-Noll-Vo 32-bit hash, for bytes. */
 unsigned
 hsh_hash_bytes (const void *buf_, size_t size)
 {
   const unsigned char *buf = buf_;
-  unsigned hash = 0;
+  unsigned hash;
 
   assert (buf != NULL);
-  while (size-- > 0) 
-    {
-      hash += *buf++;
-      hash += (hash << 10);
-      hash ^= (hash >> 6);
-    } 
-  hash += (hash << 3);
-  hash ^= (hash >> 11);
-  hash += (hash << 15);
+
+  hash = FNV_32_BASIS;
+  while (size-- > 0)
+    hash = (hash * FNV_32_PRIME) ^ *buf++;
+
   return hash;
 } 
 
-/* Colin Plumb's "one-at-a-time" hash, for strings. */
+/* Fowler-Noll-Vo 32-bit hash, for strings. */
 unsigned
 hsh_hash_string (const char *s_) 
 {
   const unsigned char *s = s_;
-  unsigned hash = 0;
+  unsigned hash;
 
   assert (s != NULL);
-  while (*s != '\0') 
-    {
-      hash += *s++;
-      hash += (hash << 10);
-      hash ^= (hash >> 6);
-    } 
-  hash += (hash << 3);
-  hash ^= (hash >> 11);
-  hash += (hash << 15);
+
+  hash = FNV_32_BASIS;
+  while (*s != '\0')
+    hash = (hash * FNV_32_PRIME) ^ *s++;
+
   return hash;
 }
 
@@ -233,7 +229,7 @@ hsh_rehash (struct hsh_table *h, size_t new_size)
 /* A "algo_predicate_func" that returns nonzero if DATA points
    to a non-null void. */
 static int
-not_null (const void *data_, void *aux unused) 
+not_null (const void *data_, void *aux UNUSED) 
 {
   void *const *data = data_;
 
@@ -259,7 +255,7 @@ hsh_data (struct hsh_table *h)
 
 /* Dereferences void ** pointers and passes them to the hash
    comparison function. */
-int
+static int
 comparison_helper (const void *a_, const void *b_, void *h_) 
 {
   void *const *a = a_;