實(shí)現(xiàn)了一個(gè)文件＋mmap的紅黑樹(shù)，歡迎測(cè)試

redor

用于對(duì)需要永久存儲(chǔ) 而且需要查找和排序的int類(lèi)數(shù)據(jù)，好處是減少?gòu)奈募�讀數(shù)據(jù)在內(nèi)存構(gòu)建紅黑樹(shù)的時(shí)間 另外使用mmap保證修改內(nèi)存后磁盤(pán)文件會(huì)同步，無(wú)須手動(dòng)sync和再次寫(xiě)入文件。
一個(gè) mmtree文件里可以構(gòu)件2G個(gè)樹(shù)節(jié)點(diǎn).
可以通過(guò)mmtree_new_tree()生成新的樹(shù).
mmtree_insert()  寫(xiě)入新節(jié)點(diǎn) 如果old返回為非空表示存在該節(jié)點(diǎn)。
mmtree_find() 查找節(jié)點(diǎn)
mmtree_remove() 移除節(jié)點(diǎn)
。。。。

鏈接：
http://hispider.googlecode.com/s ... /src/utils/mmtree.h
http://hispider.googlecode.com/s ... /src/utils/mmtree.c
多線(xiàn)程使用添加這個(gè)文件 并且添加編譯選項(xiàng) -DHAVE_PTHREAD
http://hispider.googlecode.com/s ... /src/utils/mutext.h

應(yīng)某同學(xué)的建議放一個(gè)打包上來(lái)，代碼測(cè)試有問(wèn)題盡快告訴我。

mmtree.h

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

復(fù)制代碼

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

vbs100

先頂了 現(xiàn)在還用不到這么高級(jí)的東東

CGer-Tux

很強(qiáng)大

converse

http://72891.cn/viewthread.php?tid=1069566

redor

你不會(huì)覺(jué)得這倆一樣吧？ 你數(shù)據(jù)結(jié)構(gòu)， 他的那個(gè)ms搞復(fù)雜了，我這個(gè)是為了保存數(shù)據(jù)到磁盤(pán) 而且還能搞到內(nèi)存添加 查找 刪除。用于任何用途應(yīng)該都可以，不僅僅局限cache。
不過(guò)各自都有自己的特點(diǎn)， 呵呵

原帖由 converse 于 2009-9-29 14:12 發(fā)表
http://72891.cn/viewthread.php?tid=1069566

converse

>>我這個(gè)是為了保存數(shù)據(jù)到磁盤(pán) 而且還能搞到內(nèi)存添加 查找 刪除

這些都可以做到,而且key可以使變長(zhǎng)的.

redor

key變成有什么好處？char ＊加一個(gè)長(zhǎng)度？ 我基本不贊同使用char * 作為key， 做之前最好使用相應(yīng)的轉(zhuǎn)換成int，不然效率損傷很大。

原帖由 converse 于 2009-9-29 15:32 發(fā)表
>>我這個(gè)是為了保存數(shù)據(jù)到磁盤(pán) 而且還能搞到內(nèi)存添加 查找 刪除

這些都可以做到,而且key可以使變長(zhǎng)的.

cugb_cat

在連續(xù)空間實(shí)現(xiàn)紅黑樹(shù)，不錯(cuò)。不過(guò)變長(zhǎng)索引還是有必要的吧，畢竟字符串轉(zhuǎn)換成int后，信息量大大減少了。

redor

原帖由 cugb_cat 于 2009-9-29 15:50 發(fā)表
在連續(xù)空間實(shí)現(xiàn)紅黑樹(shù)，不錯(cuò)。不過(guò)變長(zhǎng)索引還是有必要的吧，畢竟字符串轉(zhuǎn)換成int后，信息量大大減少了。

主要看你怎么變int了用hash變int肯定麻煩， 用trie變int就沒(méi)有沖突了，都是一一對(duì)應(yīng)的。

cugb_cat

原帖由 redor 于 2009-9-29 15:55 發(fā)表



主要看你怎么變int了用hash變int肯定麻煩， 用trie變int就沒(méi)有沖突了，都是一一對(duì)應(yīng)的。

還有你這個(gè)封裝對(duì)空間的使用率是個(gè)什么情況？