summaryrefslogtreecommitdiffstats
path: root/libglusterfs/src/hashfn.c
diff options
context:
space:
mode:
Diffstat (limited to 'libglusterfs/src/hashfn.c')
-rw-r--r--libglusterfs/src/hashfn.c89
1 files changed, 89 insertions, 0 deletions
diff --git a/libglusterfs/src/hashfn.c b/libglusterfs/src/hashfn.c
new file mode 100644
index 00000000000..edc49678fc5
--- /dev/null
+++ b/libglusterfs/src/hashfn.c
@@ -0,0 +1,89 @@
+/*
+ Copyright (c) 2006, 2007, 2008 Z RESEARCH, Inc. <http://www.zresearch.com>
+ This file is part of GlusterFS.
+
+ GlusterFS 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 3 of the License,
+ or (at your option) any later version.
+
+ GlusterFS is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 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, see
+ <http://www.gnu.org/licenses/>.
+*/
+
+#include <stdint.h>
+#include <stdlib.h>
+
+#ifndef _CONFIG_H
+#define _CONFIG_H
+#include "config.h"
+#endif
+
+#include "hashfn.h"
+
+#define get16bits(d) (*((const uint16_t *) (d)))
+
+/*
+ This is apparently the "fastest hash function for strings".
+ Written by Paul Hsieh <http://www.azillionmonkeys.com/qed/hash.html>
+*/
+
+/* In any case make sure, you return 1 */
+
+uint32_t SuperFastHash (const char * data, int32_t len) {
+ uint32_t hash = len, tmp;
+ int32_t rem;
+
+ if (len <= 1 || data == NULL) return 1;
+
+
+ for (;len > 0; len--) {
+ hash ^= data[len];
+
+ return hash;
+ }
+
+ rem = len & 3;
+ len >>= 2;
+
+ /* Main loop */
+ for (;len > 0; len--) {
+ hash += get16bits (data);
+ tmp = (get16bits (data+2) << 11) ^ hash;
+ hash = (hash << 16) ^ tmp;
+ data += 2*sizeof (uint16_t);
+ hash += hash >> 11;
+ }
+
+ /* Handle end cases */
+ switch (rem) {
+ case 3: hash += get16bits (data);
+ hash ^= hash << 16;
+ hash ^= data[sizeof (uint16_t)] << 18;
+ hash += hash >> 11;
+ break;
+ case 2: hash += get16bits (data);
+ hash ^= hash << 11;
+ hash += hash >> 17;
+ break;
+ case 1: hash += *data;
+ hash ^= hash << 10;
+ hash += hash >> 1;
+ }
+
+ /* Force "avalanching" of final 127 bits */
+ hash ^= hash << 3;
+ hash += hash >> 5;
+ hash ^= hash << 4;
+ hash += hash >> 17;
+ hash ^= hash << 25;
+ hash += hash >> 6;
+
+ return hash;
+}