import FNV hash function.

rewrite getkeep() for memory saving


git-svn-id: http://opensvn.csie.org/pttbbs/trunk/pttbbs@2544 63ad8ddf-47c3-0310-b6dd-a9e9d9715204

3 files changed, 151 insertions, 20 deletions

diff --git a/include/fnv_hash.h b/include/fnv_hash.h
new file mode 100644
index 00000000..9d8851bd
--- /dev/null
+++ b/include/fnv_hash.h
@@ -0,0 +1,107 @@
+/*
+ * Fowler / Noll / Vo Hash (FNV Hash)
+ * http://www.isthe.com/chongo/tech/comp/fnv/
+ *
+ * This is an implementation of the algorithms posted above.
+ * This file is placed in the public domain by Peter Wemm.
+ *
+ * $FreeBSD: src/sys/sys/fnv_hash.h,v 1.2 2001/03/20 02:10:18 peter Exp $
+ */
+
+typedef unsigned int Fnv32_t;
+typedef unsigned long long Fnv64_t;
+
+#define FNV1_32_INIT ((Fnv32_t) 33554467UL)
+#define FNV1_64_INIT ((Fnv64_t) 0xcbf29ce484222325ULL)
+
+#define FNV_32_PRIME ((Fnv32_t) 0x01000193UL)
+#define FNV_64_PRIME ((Fnv64_t) 0x100000001b3ULL)
+
+static __inline Fnv32_t
+fnv_32_buf(const void *buf, size_t len, Fnv32_t hval)
+{
+	const unsigned char *s = (const unsigned char *)buf;
+
+	while (len-- != 0) {
+		hval *= FNV_32_PRIME;
+		hval ^= *s++;
+	}
+	return hval;
+}
+
+static __inline Fnv32_t
+fnv_32_str(const char *str, Fnv32_t hval)
+{
+	const unsigned char *s = (const unsigned char *)str;
+	Fnv32_t c;
+
+	while ((c = *s++) != 0) {
+		hval *= FNV_32_PRIME;
+		hval ^= c;
+	}
+	return hval;
+}
+
+static __inline Fnv32_t
+fnv1a_32_str(const char *str, Fnv32_t hval)
+{
+	const unsigned char *s = (const unsigned char *)str;
+	Fnv32_t c;
+
+	while ((c = *s++) != 0) {
+		hval ^= c;
+		hval *= FNV_32_PRIME;
+	}
+	return hval;
+}
+
+static __inline Fnv32_t
+fnv1a_32_strcase(const char *str, Fnv32_t hval)
+{
+	const unsigned char *s = (const unsigned char *)str;
+	Fnv32_t c;
+
+	while ((c = *s++) != 0) {
+		hval ^= toupper(c);
+		hval *= FNV_32_PRIME;
+	}
+	return hval;
+}
+
+static __inline Fnv64_t
+fnv_64_buf(const void *buf, size_t len, Fnv64_t hval)
+{
+	const unsigned char *s = (const unsigned char *)buf;
+
+	while (len-- != 0) {
+		hval *= FNV_64_PRIME;
+		hval ^= *s++;
+	}
+	return hval;
+}
+
+static __inline Fnv64_t
+fnv_64_str(const char *str, Fnv64_t hval)
+{
+	const unsigned char *s = (const unsigned char *)str;
+	Fnv64_t c;
+
+	while ((c = *s++) != 0) {
+		hval *= FNV_64_PRIME;
+		hval ^= c;
+	}
+	return hval;
+}
+
+static __inline Fnv64_t
+fnv1a_64_strcase(const char *str, Fnv64_t hval)
+{
+	const unsigned char *s = (const unsigned char *)str;
+	Fnv64_t c;
+
+	while ((c = *s++) != 0) {
+		hval ^= toupper(c);
+		hval *= FNV_64_PRIME;
+	}
+	return hval;
+}
diff --git a/include/pttstruct.h b/include/pttstruct.h
index ce5b5382..ca5ed911 100644
--- a/include/pttstruct.h
+++ b/include/pttstruct.h
@@ -429,10 +429,9 @@ typedef struct crosspost_t {
 #define SORT_BY_SEX   5
 
 typedef struct keeploc_t {
-    char    *key;
+    unsigned int hashkey;
     int     top_ln;
     int     crs_ln;
-    struct  keeploc_t       *next;
 } keeploc_t;
 
 #define VALID_USHM_ENTRY(X) ((X) >= 0 && (X) < USHM_SIZE)
diff --git a/mbbsd/read.c b/mbbsd/read.c
index f376ad2e..58a8678f 100644
--- a/mbbsd/read.c
+++ b/mbbsd/read.c
@@ -1,5 +1,6 @@
 /* $Id$ */
 #include "bbs.h"
+#include "fnv_hash.h"
 
 static fileheader_t *headers = NULL;
 static int      last_line; // PTT: last_line 游標可指的最後一個
@@ -200,29 +201,53 @@ TagPruner(int bid)
 keeploc_t      *
 getkeep(char *s, int def_topline, int def_cursline)
 {
-    static struct keeploc_t *keeplist = NULL;
+    /* 為省記憶體, 且避免 malloc/free 不成對, getkeep 最好不要 malloc,
+     * 只記 s 的 hash 值,
+     * fvn1a-32bit collision 機率約小於十萬分之一 */
+    /* 原本使用 link list, 可是一方面會造成 malloc/free 不成對, 
+     * 一方面 size 小, malloc space overhead 就高, 因此改成 link block,
+     * 以 KEEPSLOT 為一個 block 的 link list.
+     * 只有第一個 block 可能沒滿. */
+#define KEEPSLOT 10
+    struct keepsome {
+	unsigned char used;
+	keeploc_t arr[KEEPSLOT];
+	struct keepsome *next;
+    };
+    static struct keepsome preserv_keepblock;
+    static struct keepsome *keeplist = &preserv_keepblock;
     struct keeploc_t *p;
-    /* TODO board 存 bid, 其他存 hash, 不要 strdup */
-
-    if (def_cursline >= 0)
-	for (p = keeplist; p; p = p->next) {
-	    if (!strcmp(s, p->key)) {
-		if (p->crs_ln < 1)
-		    p->crs_ln = 1;
-		return p;
-	    }
+    unsigned int key=fnv1a_32_str(s, FNV1_32_INIT);
+    int i;
+
+    if (def_cursline >= 0) {
+	struct keepsome *kl=keeplist;
+	while(kl) {
+	    for(i=0; i<kl->used; i++)
+		if(key == kl->arr[i].hashkey) {
+		    p = &kl->arr[i];
+		    if (p->crs_ln < 1)
+			p->crs_ln = 1;
+		    return p;
+		}
+	    kl=kl->next;
 	}
-    else
+    } else
 	def_cursline = -def_cursline;
-    p = (keeploc_t *) malloc(sizeof(keeploc_t));
-    assert(p);
-    p->key = (char *)malloc(strlen(s) + 1);
-    assert(p->key);
-    strcpy(p->key, s);
+
+    if(keeplist->used==KEEPSLOT) {
+	struct keepsome *kl;
+	kl = (struct keepsome*)malloc(sizeof(struct keepsome));
+	memset(kl, 0, sizeof(struct keepsome));
+	kl->next = keeplist;
+	keeplist = kl;
+    }
+    p = &keeplist->arr[keeplist->used];
+    keeplist->used++;
+    p->hashkey = key;
     p->top_ln = def_topline;
     p->crs_ln = def_cursline;
-    p->next = keeplist;
-    return (keeplist = p);
+    return p;
 }
 
 void