Changeset 198 for cpp/frams

Timestamp:

03/25/14 18:49:56 (11 years ago)

Author:

Maciej Komosinski

Message:

Hashing function for strings

Location:

cpp/frams/util

Files:

• sstring.cpp (modified) (1 diff)
• sstring.h (modified) (2 diffs)

cpp/frams/util/sstring.cpp

@@ -107 +107 @@
 txt=(char*)realloc(txt,needed+1);
 size=needed;
+}
+
+//////////////////////////////////////////////////
+// to be moved somewhere else?
+// public domain source: http://isthe.com/chongo/src/fnv
+typedef unsigned long Fnv32_t;
+
+#define FNV_32_PRIME ((Fnv32_t)0x01000193)
+
+Fnv32_t fnv_32_buf(void *buf, size_t len, Fnv32_t hval)
+{
+    unsigned char *bp = (unsigned char *)buf;   /* start of buffer */
+    unsigned char *be = bp + len;               /* beyond end of buffer */
+
+    while (bp < be) {
+
+        /* multiply by the 32 bit FNV magic prime mod 2^32 */
+#if defined(NO_FNV_GCC_OPTIMIZATION)
+        hval *= FNV_32_PRIME;
+#else
+        hval += (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24);
+#endif
+
+        /* xor the bottom with the current octet */
+        hval ^= (Fnv32_t)*bp++;
+    }
+
+    /* return our new hash value */
+    return hval;
+}
+//////////////////////////////////////////////////
+
+unsigned long SBuf::hash() const
+{
+return fnv_32_buf(txt,used,FNV_32_PRIME);
 }
 

cpp/frams/util/sstring.h

@@ -47 +47 @@
 SBuf();
 ~SBuf();
+unsigned long hash() const; // 32-bit FNV-1 hash -> http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash
 };
 
@@ -174 +175 @@
 int startsWith(const char *pattern) const;
 char charAt(int pos) const {return buf->txt[pos];}
+unsigned long hash() const {return buf->hash();}
 
 static SString valueOf(int);