From 3944fd34ec9b7b7bf252c7169a7ebc9b84e95fbf Mon Sep 17 00:00:00 2001 From: kcwu Date: Fri, 25 Feb 2005 10:59:22 +0000 Subject: 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 --- include/fnv_hash.h | 107 ++++++++++++++++++++++++++++++++++++++++++++++++++++ include/pttstruct.h | 3 +- mbbsd/read.c | 61 +++++++++++++++++++++--------- 3 files changed, 151 insertions(+), 20 deletions(-) create mode 100644 include/fnv_hash.h 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; iused; 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 -- cgit v1.2.3