* Add simple hash function for hashing tokens

3 files changed, 57 insertions, 0 deletions

diff --git a/src/filter.c b/src/filter.c
index d1edbb930..ae5852efb 100644
--- a/src/filter.c
+++ b/src/filter.c
@@ -334,3 +334,8 @@ void make_composites (struct worker_task *task)
 {
 	g_hash_table_foreach (task->results, composites_metric_callback, task);
 }
+
+
+/* 
+ * vi:ts=4 
+ */
diff --git a/src/fstring.c b/src/fstring.c
index ad0be7d78..cad7c8710 100644
--- a/src/fstring.c
+++ b/src/fstring.c
@@ -232,3 +232,45 @@ fstrgrow (memory_pool_t *pool, f_str_t *orig, size_t newlen)
 
 	return res;
 }
+
+/*
+ * Return hash value for a string
+ */
+uint32_t
+fstrhash (f_str_t *str)
+{
+	size_t i;
+	uint32_t hval;
+	uint32_t tmp;
+
+	if (str == NULL) {
+		return 0;
+	}
+	hval = str->len;
+
+	for	(i = 0; i < str->len; i++) {
+		/* 
+		 * xor in the current byte against each byte of hval
+		 * (which alone gaurantees that every bit of input will have
+		 * an effect on the output)
+		 */
+		tmp = *(str->begin + i) & 0xFF;
+		tmp = tmp | (tmp << 8) | (tmp << 16) | (tmp << 24);
+		hval ^= tmp;
+
+		/* add some bits out of the middle as low order bits */
+		hval = hval + ((hval >> 12) & 0x0000ffff) ;
+
+		/* swap most and min significative bytes */
+		tmp = (hval << 24) | ((hval >> 24) & 0xff);
+		/* zero most and min significative bytes of hval */
+		hval &= 0x00ffff00;
+		hval |= tmp;
+		/*
+		 * rotate hval 3 bits to the left (thereby making the
+		 * 3rd msb of the above mess the hsb of the output hash)
+		 */
+		hval = (hval << 3) + (hval >> 29);
+	}
+	return hval;
+}
diff --git a/src/fstring.h b/src/fstring.h
index c3087b2c5..6840d9088 100644
--- a/src/fstring.h
+++ b/src/fstring.h
@@ -6,6 +6,11 @@
 #define FSTRING_H
 
 #include <sys/types.h>
+#include "config.h"
+
+#ifdef HAVE_STDINT_H
+#include <stdint.h>
+#endif
 #include "mem_pool.h"
 
 #define update_buf_size(x) (x)->free = (x)->buf->size - ((x)->pos - (x)->buf->begin); (x)->buf->len = (x)->pos - (x)->buf->begin
@@ -83,4 +88,9 @@ f_str_t* fstrgrow (memory_pool_t *pool, f_str_t *orig, size_t newlen);
  */
 #define fstridx(str, pos) *((str)->begin + (pos))
 
+/*
+ * Return fast hash value for fixed string
+ */
+uint32_t fstrhash (f_str_t *str);
+
 #endif