发布一个mmap的trie_midrmm02_新浪博客
发布一个mmap的trie
(2012-04-13 03:09:22)
转载▼
标签：
杂谈
发布一个mmap的trie 本帖最后由 redor 于 2010-04-13 17:24 编辑
http://libibase.googlecode.com/svn/trunk/devel/utils/mmtrie.h
http://libibase.googlecode.com/svn/trunk/devel/utils/mmtrie.c
附件版本有问题，直接下这个吧 http://libibase.googlecode.com/files/mmtrie.zip
写这个的出发点是吧之前做的trie能写到文件而且能很容易mmap到内存, 可以用于输入法 搜索引擎分词 词表的功能, 共享前缀存储, 支持最大２０亿节点.
简单一点可以当一个hash表使用, 查找的时间复杂度为 N* Log(256) N为字符长度, key可以为二进制的数据, value 必须为int类型, 不能为０, 因为mmtrie_get()/find() 没有结果的情况下为０,
如果需要set value为０的话自己+１, 出来的时候-１就好了.
大概数据结构和使用方法如下:
typedef struct _MMTRIE
{
MMTRSTATE *state;
MMTRNODE *nodes;
void *map;
off_t file_size;
int fd;
void *mutex;
int(*add)(struct _MMTRIE *, char *key, int nkey, int data);
int(*get)(struct _MMTRIE *, char *key, int nkey);
int(*find)(struct _MMTRIE *, char *key, int nkey, int *len);
int(*maxfind)(struct _MMTRIE *, char *key, int nkey, int *len);
int(*radd)(struct _MMTRIE *, char *key, int nkey, int data);
int(*rget)(struct _MMTRIE *, char *key, int nkey);
int(*rfind)(struct _MMTRIE *, char *key, int nkey, int *len);
int(*rmaxfind)(struct _MMTRIE *, char *key, int nkey, int *len);
void (*clean)(struct _MMTRIE *);
}MMTRIE;
MMTRIE *mmtrie_init(char *file);
int mmtrie_add(struct _MMTRIE *, char *key, int nkey, int data);
int mmtrie_get(struct _MMTRIE *, char *key, int nkey);
int mmtrie_find(struct _MMTRIE *, char *key, int nkey, int *len);
int mmtrie_maxfind(st
各位的c语言是怎样入门的呢？
ruct _MMTRIE *, char *key, int nkey, int *len);
int mmtrie_radd(struct _MMTRIE *, char *key, int nkey, int data);
int mmtrie_rget(struct _MMTRIE *, char *key, int nkey);
int mmtrie_rfind(struct _MMTRIE *, char *key, int nkey, int *len);
int mmtrie_rmaxfind(struct _MMTRIE *, char *key, int nkey, int *len);
voidmmtrie_clean(struct _MMTRIE *);
//gcc -o mmtr mmtrie.c -D_DEBUG_MMTRIE && ./mmtr
static char *mmfile = "/tmp/test.mmtrie";
int main()
{
char word, *p = NULL;
MMTRIE *mmtrie = NULL;
int i = 0, n = 0, x = 0;
if((mmtrie = mmtrie_init(mmfile)))
{
p = "abbbxxx"; mmtrie_add(mmtrie, p, strlen(p), 1);fprintf(stdout, "add(%s:%d)\r\n", p, 1);
p = "abb"; mmtrie_add(mmtrie, p, strlen(p), 2);fprintf(stdout, "add(%s:%d)\r\n", p, 2);
p = "abbx"; mmtrie_add(mmtrie, p, strlen(p), 3);fprintf(stdout, "add(%s:%d)\r\n", p, 3);
p = "abbxddd"; mmtrie_add(mmtrie, p, strlen(p), 4);fprintf(stdout, "add(%s:%d)\r\n", p, 4);
p = "abbxdddx"; mmtrie_add(mmtrie, p, strlen(p), 5);fprintf(stdout, "add(%s:%d)\r\n", p, 5);
p = "abbx";x = mmtrie_get(mmtrie, p, strlen(p)); if(x http://www.dj1988.com!= 0)fprintf(stdout, "get(%s:%d)\r\n", p, x);
p = "abbxddddd";x = mmtrie_find(mmtrie, p, strlen(p), &n); if(x != 0){fprintf(stdout, "find(%s => %.*s:%d)\r\n", p, n, p, x);}
p = "abbxddddd";x = mmtrie_maxfind(mmtrie, p, strlen(p), &n); if(x != 0){fprintf(stdout, "maxfind(%s => %.*s:%d)\r\n", p, n, p, x);}
//reverse
p = "asscxxx"; mmtrie_radd(mmtrie, p, strlen(p), 1);fprintf(stdout, "radd(%s:%d)\r\n", p, 1);
p = "adfdsfscxxx"; mmtrie_radd(mmtrie, p, strlen(p), 2);fprintf(stdout, "radd(%s:%d)\r\n", p, 2);
p = "dafdsfscxxx"; mmtrie_radd(mmtrie, p, strlen(p), 3);fprintf(stdout, "radd(%s:%d)\r\n", p, 3);
p = "aeffdsxccc"; mmtrie_radd(mmtrie, p, strlen(p), 4);fprintf(stdout, "radd(%s:%d)\r\n", p, 4);
p = "adsssxxscxxx"; mmtrie_radd(mmtrie, p, strlen(p), 5);fprintf(stdout, "radd(%s:%d)\r\n", p, 5);
p = "dafdsfssddcxxx";x = mmtrie_rget(mmtrie, p, strlen(p)); if(x != 0)fprintf(stdout, "rget(%s:%d)\r\n", p, x);
p = "adsssxxscxxx";x = mmtrie_rfind(mmtrie, p, strlen(p), &n); if(x != 0){fprintf(stdout, "rfind(%s => %s:%d)\r\n", p, p+(strlen(p)-n), x);}
p = "sadfsfsdadfdsfscxxx";x = mmtrie_rmaxfind(mmtrie, p, strlen(p), &n); if(x != 0){fprintf(stdout, "rmaxfind(%s => %s:%d)\r\n", p, p+(strlen(p)-n), x);}
mmtrie->clean(mmtrie);
}
}
[ 本帖最后由 redor 于 2010-1-27 11:55 编辑 ]楼主纯爷们儿原帖由 c/unix 于 2010-1-27 09:07 发表 http://bbs.chinaunix.net/images/common/back.gif
楼主纯爷们儿
谢谢啊! 这话现在怎么听都别扭.... 失去原味了支持LZ。不错http://www.jssxd.com/，支持楼主能给点注释就更完美了,让我们菜鸟也能学习学习,瞻仰瞻仰!哈哈..学习下。好强大 但是不太会用。。。出发点是不是想实现一个数据的存储，如果内存不够大，就利用mmap存到文件当中去。感觉不如直接用数据库快，比如sql-lite等，不过作为研究肯定是值得称赞的 本帖最后由 redor 于 2010-04-12 14:09 编辑
回复 9# w_x_x
mmap是有一个比较好的内存和文件的同步方案, 易于导入, 这个就是一个基于mmap的trie 跟sqllite根本不是一个东西......
用于存储数据的还有一个在这里, http://libibase.googlecode.com/svn/trunk/devel/hibase/src/utils/db.c