X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flibpspp%2Fhash-functions.c;h=ff9ea895cacd66b91e012e26b9add4f5e09f2608;hb=eeedca3fcd959f73ba2c2fd4cbab5bd03ceb4f8d;hp=2318777392b01abeb44d96c8aa890cd1f0bf2bdc;hpb=a1efcf97ca2f75f4be6a0389ff2372c03ed2d4e1;p=pspp
diff --git a/src/libpspp/hash-functions.c b/src/libpspp/hash-functions.c
index 2318777392..ff9ea895ca 100644
--- a/src/libpspp/hash-functions.c
+++ b/src/libpspp/hash-functions.c
@@ -1,5 +1,5 @@
/* PSPP - a program for statistical analysis.
- Copyright (C) 1997-9, 2000, 2008 Free Software Foundation, Inc.
+ Copyright (C) 1997-9, 2000, 2008, 2009, 2010, 2011, 2012, 2019 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
@@ -15,76 +15,175 @@
along with this program. If not, see . */
#include
-#include
-#include
-#include
-#include
-/* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */
-#define FNV_32_PRIME 16777619u
-#define FNV_32_BASIS 2166136261u
+#include "libpspp/hash-functions.h"
-/* Fowler-Noll-Vo 32-bit hash, for bytes. */
-unsigned
-hsh_hash_bytes (const void *buf_, size_t size)
-{
- const unsigned char *buf = (const unsigned char *) buf_;
- unsigned hash;
+#if 0
+/* Enable this code only for testing! Theoretically everything
+ should still work, but very inefficient hash tables will result,
+ meaning that the code will be slow. */
+#warning "HASHING FUNCTIONS ARE DISABLED! EXPECT LOTS OF HASH COLLISIONS!!!"
- assert (buf != NULL);
+#include "libpspp/compiler.h"
- hash = FNV_32_BASIS;
- while (size-- > 0)
- hash = (hash * FNV_32_PRIME) ^ *buf++;
- return hash;
+unsigned int
+hash_bytes (const void *b UNUSED, size_t s UNUSED, unsigned int basis UNUSED)
+{
+ return 0;
}
-/* Fowler-Noll-Vo 32-bit hash, for strings. */
-unsigned
-hsh_hash_string (const char *s_)
+unsigned int
+hash_string (const char *s UNUSED, unsigned int basis UNUSED)
{
- const unsigned char *s = (const unsigned char *) s_;
- unsigned hash;
-
- assert (s != NULL);
+ return 0;
+}
- hash = FNV_32_BASIS;
- while (*s != '\0')
- hash = (hash * FNV_32_PRIME) ^ *s++;
+unsigned int
+hash_int (int i UNUSED, unsigned int basis UNUSED)
+{
+ return 0;
+}
- return hash;
+unsigned int
+hash_double (double d UNUSED, unsigned int basis UNUSED)
+{
+ return 0;
}
-/* Fowler-Noll-Vo 32-bit hash, for case-insensitive strings. */
-unsigned
-hsh_hash_case_string (const char *s_)
+unsigned int
+hash_pointer (const void *p UNUSED, unsigned int basis UNUSED)
{
- const unsigned char *s = (const unsigned char *) s_;
- unsigned hash;
+ return 0;
+}
- assert (s != NULL);
+#else
- hash = FNV_32_BASIS;
- while (*s != '\0')
- hash = (hash * FNV_32_PRIME) ^ toupper (*s++);
+#include
+#include
+#include
+#include
+
+/* Based on http://burtleburtle.net/bob/c/lookup3.c, by Bob
+ Jenkins , as retrieved on April
+ 8, 2009. The license information there says the following:
+ "You can use this free for any purpose. It's in the public
+ domain. It has no warranty." and "You may use this code any
+ way you wish, private, educational, or commercial. It's
+ free." */
+
+#define HASH_ROT(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
+
+#define HASH_MIX(a, b, c) \
+ do \
+ { \
+ a -= c; a ^= HASH_ROT (c, 4); c += b; \
+ b -= a; b ^= HASH_ROT (a, 6); a += c; \
+ c -= b; c ^= HASH_ROT (b, 8); b += a; \
+ a -= c; a ^= HASH_ROT (c, 16); c += b; \
+ b -= a; b ^= HASH_ROT (a, 19); a += c; \
+ c -= b; c ^= HASH_ROT (b, 4); b += a; \
+ } \
+ while (0)
+
+#define HASH_FINAL(a, b, c) \
+ do \
+ { \
+ c ^= b; c -= HASH_ROT (b, 14); \
+ a ^= c; a -= HASH_ROT (c, 11); \
+ b ^= a; b -= HASH_ROT (a, 25); \
+ c ^= b; c -= HASH_ROT (b, 16); \
+ a ^= c; a -= HASH_ROT (c, 4); \
+ b ^= a; b -= HASH_ROT (a, 14); \
+ c ^= b; c -= HASH_ROT (b, 24); \
+ } \
+ while (0)
+
+/* Returns a hash value for the N bytes starting at P, starting
+ from BASIS. */
+unsigned int
+hash_bytes (const void *p_, size_t n, unsigned int basis)
+{
+ const uint8_t *p = p_;
+ uint32_t a, b, c;
+ uint32_t tmp[3];
+
+ a = b = c = 0xdeadbeef + n + basis;
+
+ while (n >= 12)
+ {
+ memcpy (tmp, p, 12);
+ a += tmp[0];
+ b += tmp[1];
+ c += tmp[2];
+ HASH_MIX (a, b, c);
+ n -= 12;
+ p += 12;
+ }
+
+ if (n > 0)
+ {
+ memset (tmp, 0, 12);
+ memcpy (tmp, p, n);
+ a += tmp[0];
+ b += tmp[1];
+ c += tmp[2];
+ }
+
+ HASH_FINAL (a, b, c);
+ return c;
+}
- return hash;
+/* Returns a hash value for null-terminated string S, starting
+ from BASIS. */
+unsigned int
+hash_string (const char *s, unsigned int basis)
+{
+ return hash_bytes (s, strlen (s), basis);
}
-/* Hash for ints. */
-unsigned
-hsh_hash_int (int i)
+/* Returns a hash value for integer X, starting from BASIS. */
+unsigned int
+hash_int (int x, unsigned int basis)
{
- return hsh_hash_bytes (&i, sizeof i);
+ x -= x << 6;
+ x ^= x >> 17;
+ x -= x << 9;
+ x ^= x << 4;
+ x -= x << 3;
+ x ^= x << 10;
+ x ^= x >> 15;
+ return x + basis;
}
-/* Hash for double. */
-unsigned
-hsh_hash_double (double d)
+/* Returns a hash value for double D, starting from BASIS. */
+unsigned int
+hash_double (double d, unsigned int basis)
{
- if (!isnan (d))
- return hsh_hash_bytes (&d, sizeof d);
+ if (sizeof (double) == 8)
+ {
+ uint32_t tmp[2];
+ uint32_t a, b, c;
+
+ a = b = c = 0xdeadbeefU + 8 + basis;
+
+ memcpy (tmp, &d, 8);
+ a += tmp[0];
+ b += tmp[1];
+ HASH_FINAL (a, b, c);
+ return c;
+ }
else
- return 0;
+ return hash_bytes (&d, sizeof d, basis);
}
+
+/* Returns a hash value for pointer P, starting from BASIS. */
+unsigned int
+hash_pointer (const void *p, unsigned int basis)
+{
+ /* Casting to uintptr_t before casting to int suppresses a GCC warning about
+ on 64-bit platforms. */
+ return hash_int ((int) (uintptr_t) p, basis);
+}
+
+#endif