From 0953f929bc024a9107869a40516b89932d5482e0 Mon Sep 17 00:00:00 2001
From: Rusty Russell <rusty@rustcorp.com.au>
Date: Mon, 28 Jul 2008 13:02:22 +1000
Subject: [PATCH] Move hash into ccan/ dir

---
 {hash => ccan/hash}/_info.c    |  2 ++
 {hash => ccan/hash}/hash.c     |  0
 {hash => ccan/hash}/hash.h     | 35 +++++++++++++++++++++++++-----
 {hash => ccan/hash}/test/run.c | 39 +++++++++++++++++++++++++++++++++-
 4 files changed, 70 insertions(+), 6 deletions(-)
 rename {hash => ccan/hash}/_info.c (96%)
 rename {hash => ccan/hash}/hash.c (100%)
 rename {hash => ccan/hash}/hash.h (80%)
 rename {hash => ccan/hash}/test/run.c (82%)

diff --git a/hash/_info.c b/ccan/hash/_info.c
similarity index 96%
rename from hash/_info.c
rename to ccan/hash/_info.c
index 66b9fc0d..9ce4e3ac 100644
--- a/hash/_info.c
+++ b/ccan/hash/_info.c
@@ -1,3 +1,5 @@
+#include <string.h>
+
 /**
  * hash - routines for hashing bytes
  *
diff --git a/hash/hash.c b/ccan/hash/hash.c
similarity index 100%
rename from hash/hash.c
rename to ccan/hash/hash.c
diff --git a/hash/hash.h b/ccan/hash/hash.h
similarity index 80%
rename from hash/hash.h
rename to ccan/hash/hash.h
index cbc052af..f0de4719 100644
--- a/hash/hash.h
+++ b/ccan/hash/hash.h
@@ -59,9 +59,9 @@
  * a 32-bit hash.
  *
  * This hash will have the same results on different machines, so can
- * be used for external hashes (ie. not hashes sent across the network
- * or saved to disk).  The results will not change in future versions
- * of this package.
+ * be used for external hashes (ie. hashes sent across the network or
+ * saved to disk).  The results will not change in future versions of
+ * this module.
  *
  * Example:
  *	#include "hash/hash.h"
@@ -97,6 +97,31 @@
  */
 uint32_t hash_u32(const uint32_t *key, size_t num, uint32_t base);
 
+/**
+ * hash_string - very fast hash of an ascii string
+ * @str: the nul-terminated string
+ *
+ * The string is hashed, using a hash function optimized for ASCII and
+ * similar strings.  It's weaker than the other hash functions.
+ *
+ * This hash may have different results on different machines, so is
+ * only useful for internal hashes (ie. not hashes sent across the
+ * network or saved to disk).  The results will be different from the
+ * other hash functions in this module, too.
+ */
+static inline uint32_t hash_string(const char *string)
+{
+	/* This is Karl Nelson <kenelson@ece.ucdavis.edu>'s X31 hash.
+	 * It's a little faster than the (much better) lookup3 hash(): 56ns vs
+	 * 84ns on my 2GHz Intel Core Duo 2 laptop for a 10 char string. */
+	uint32_t ret;
+
+	for (ret = 0; *string; string++)
+		ret = (ret << 5) - ret + *string;
+
+	return ret;
+}
+
 /* Our underlying operations. */
 uint32_t hash_any(const void *key, size_t length, uint32_t base);
 uint32_t hash_any_stable(const void *key, size_t length, uint32_t base);
@@ -153,7 +178,7 @@ static inline uint32_t hash_pointer(const void *p, uint32_t base)
 		} u;
 		u.p = p;
 		return hash_u32(u.u32, sizeof(p) / sizeof(uint32_t), base);
-	}
-	return hash(&p, 1, base);
+	} else
+		return hash(&p, 1, base);
 }
 #endif /* HASH_H */
diff --git a/hash/test/run.c b/ccan/hash/test/run.c
similarity index 82%
rename from hash/test/run.c
rename to ccan/hash/test/run.c
index 89ab0a9d..a10e723e 100644
--- a/hash/test/run.c
+++ b/ccan/hash/test/run.c
@@ -17,7 +17,7 @@ int main(int argc, char *argv[])
 	for (i = 0; i < ARRAY_WORDS; i++)
 		array[i] = i;
 
-	plan_tests(53);
+	plan_tests(55);
 
 	/* hash_stable is guaranteed. */
 	ok1(hash_stable(array, ARRAY_WORDS, 0) == 0x13305f8c);
@@ -111,5 +111,42 @@ int main(int argc, char *argv[])
 		diag("hash_pointer byte %i, range %u-%u", i, lowest, highest);
 	}
 
+	/* String hash: weak, so only test bottom byte */
+	for (i = 0; i < 1; i++) {
+		unsigned int num = 0, cursor, lowest = -1U, highest = 0;
+		char p[5];
+
+		memset(results, 0, sizeof(results));
+
+		memset(p, 'A', sizeof(p));
+		p[sizeof(p)-1] = '\0';
+
+		for (;;) {
+			for (cursor = 0; cursor < sizeof(p)-1; cursor++) {
+				p[cursor]++;
+				if (p[cursor] <= 'z')
+					break;
+				p[cursor] = 'A';
+			}
+			if (cursor == sizeof(p)-1)
+				break;
+
+			results[(hash_string(p) >> i*8)&0xFF]++;
+			num++;
+		}
+
+		for (j = 0; j < 256; j++) {
+			if (results[j] < lowest)
+				lowest = results[j];
+			if (results[j] > highest)
+				highest = results[j];
+		}
+		/* Expect within 20% */
+		ok(lowest > 35000, "hash_pointer byte %i lowest %i", i, lowest);
+		ok(highest < 53000, "hash_pointer byte %i highest %i",
+		   i, highest);
+		diag("hash_pointer byte %i, range %u-%u", i, lowest, highest);
+	}
+
 	return exit_status();
 }
-- 
2.39.2