免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
1234下一页
最近访问板块 发新帖
查看: 19049 | 回复: 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就没有冲突了,都是一一对应的。

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

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会,7折限时优惠重磅来袭!
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。

限时七折期:2019年8月31日前


----------------------------------------

大会官网>>
  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP