免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
1234下一页
最近访问板块 发新帖
查看: 19189 | 回复: 37

[C] 实现了一个文件+mmap的红黑树,欢迎测试 [复制链接]

论坛徽章:
0
发表于 2009-09-29 11:38 |显示全部楼层
用于对需要永久存储 而且需要查找和排序的int类数据,好处是减少从文件读数据在内存构建红黑树的时间 另外使用mmap保证修改内存后磁盘文件会同步,无须手动sync和再次写入文件。
一个 mmtree文件里可以构件2G个树节点.
可以通过mmtree_new_tree()生成新的树.
mmtree_insert()  写入新节点 如果old返回为非空表示存在该节点。
mmtree_find() 查找节点
mmtree_remove() 移除节点
。。。。

链接:
http://hispider.googlecode.com/s ... /src/utils/mmtree.h
http://hispider.googlecode.com/s ... /src/utils/mmtree.c
多线程使用添加这个文件 并且添加编译选项 -DHAVE_PTHREAD
http://hispider.googlecode.com/s ... /src/utils/mutext.h

应某同学的建议放一个打包上来,代码测试有问题尽快告诉我。

mmtree.h

  1. #ifndef _MMTREE_H
  2. #define _MMTREE_H
  3. #define MMTREE_INCRE_NUM   10000
  4. typedef struct _MTNODE
  5. {
  6.     int data;
  7.     int key;
  8.     int left;
  9.     int right;
  10.     int parent;
  11.     int color;
  12. }MTNODE;
  13. typedef struct _MTSTATE
  14. {
  15.     int left;
  16.     int current;
  17.     int total;
  18.     int qleft;
  19.     int qfirst;
  20.     int qlast;
  21. }MTSTATE;
  22. typedef struct _MMTREE
  23. {
  24.     off_t size;
  25.     void *start;
  26.     MTSTATE *state;
  27.     MTNODE *map;
  28.     int fd;
  29.     void *mutex;
  30. }MMTREE;
  31. void *mmtree_init(char *file);
  32. int mmtree_new_tree(void *mmtree, int key, int data);
  33. int mmtree_insert(void *mmtree, int *prootid, int key, int data, int *old);
  34. int mmtree_get(void *mmtree, int nodeid, int *key, int *data);
  35. int mmtree_find(void *mmtree, int rootid, int key, int *data);
  36. int mmtree_min(void *mmtree, int rootid, int *key, int *data);
  37. int mmtree_max(void *mmtree, int rootid, int *key, int *data);
  38. int mmtree_next(void *mmtree, int rootid, int nodeid, int *key, int *data);
  39. int mmtree_prev(void *mmtree, int rootid, int nodeid, int *key, int *data);
  40. int mmtree_set_data(void *mmtree, int nodeid, int data);
  41. void mmtree_view_tree(void *mmtree, int rootid, FILE *fp);
  42. void mmtree_remove(void *mmtree, int *prootid, int nodeid, int *key, int *data);
  43. void mmtree_remove_tree(void *mmtree, int rootid);
  44. void mmtree_close(void *mmtree);
  45. #endif
复制代码

[ 本帖最后由 redor 于 2009-9-29 15:53 编辑 ]

mmtree.zip

5.35 KB, 下载次数: 257

论坛徽章:
1
寅虎
日期:2014-11-30 21:25:54
发表于 2009-09-29 12:04 |显示全部楼层
先顶了 现在还用不到这么高级的东东

论坛徽章:
0
发表于 2009-09-29 13:34 |显示全部楼层
很强大

论坛徽章:
0
发表于 2009-09-29 14:12 |显示全部楼层

论坛徽章:
0
发表于 2009-09-29 15:21 |显示全部楼层
你不会觉得这俩一样吧? 你数据结构, 他的那个ms搞复杂了,我这个是为了保存数据到磁盘 而且还能搞到内存添加 查找 删除。用于任何用途应该都可以,不仅仅局限cache。
不过各自都有自己的特点, 呵呵


原帖由 converse 于 2009-9-29 14:12 发表
http://bbs.chinaunix.net/viewthread.php?tid=1069566

论坛徽章:
0
发表于 2009-09-29 15:32 |显示全部楼层
>>我这个是为了保存数据到磁盘 而且还能搞到内存添加 查找 删除

这些都可以做到,而且key可以使变长的.

论坛徽章:
0
发表于 2009-09-29 15:37 |显示全部楼层
key变成有什么好处?char *加一个长度? 我基本不赞同使用char * 作为key, 做之前最好使用相应的转换成int,不然效率损伤很大。

原帖由 converse 于 2009-9-29 15:32 发表
>>我这个是为了保存数据到磁盘 而且还能搞到内存添加 查找 删除

这些都可以做到,而且key可以使变长的.

论坛徽章:
0
发表于 2009-09-29 15:50 |显示全部楼层
在连续空间实现红黑树,不错。不过变长索引还是有必要的吧,毕竟字符串转换成int后,信息量大大减少了。

论坛徽章:
0
发表于 2009-09-29 15:55 |显示全部楼层
原帖由 cugb_cat 于 2009-9-29 15:50 发表
在连续空间实现红黑树,不错。不过变长索引还是有必要的吧,毕竟字符串转换成int后,信息量大大减少了。



主要看你怎么变int了用hash变int肯定麻烦, 用trie变int就没有冲突了,都是一一对应的。

论坛徽章:
0
发表于 2009-09-29 16:07 |显示全部楼层
原帖由 redor 于 2009-9-29 15:55 发表



主要看你怎么变int了用hash变int肯定麻烦, 用trie变int就没有冲突了,都是一一对应的。

还有你这个封装对空间的使用率是个什么情况?
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

DTCC2020中国数据库技术大会 限时8.5折

【架构革新 高效可控】2020年8月17日~19日第十一届中国数据库技术大会将在北京隆重召开。

大会设置2大主会场,20+技术专场,将邀请超百位行业专家,重点围绕数据架构、AI与大数据、传统企业数据库实践和国产开源数据库等内容展开分享和探讨,为广大数据领域从业人士提供一场年度盛会和交流平台。

http://dtcc.it168.com


大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP