tokyocabinet的内存tree数据结构

hm2462964492

1. #include <stdio.h>
   
2. #include <assert.h>
   
3. #include <stdlib.h>
   
4. #include <stddef.h>
   
5. #include <string.h>
   
6. 
   
7. /* compare keys of two records by lexical order */
   
8. #define TCCMPLEXICAL(TC_rv, TC_aptr, TC_asiz, TC_bptr, TC_bsiz) \
   
9.   do { \
   
10.     (TC_rv) = 0; \
    
11.     int _TC_min = (TC_asiz) < (TC_bsiz) ? (TC_asiz) : (TC_bsiz); \
    
12.     for(int _TC_i = 0; _TC_i < _TC_min; _TC_i++){ \
    
13.       if(((unsigned char *)(TC_aptr))[_TC_i] != ((unsigned char *)(TC_bptr))[_TC_i]){ \
    
14.         (TC_rv) = ((unsigned char *)(TC_aptr))[_TC_i] - ((unsigned char *)(TC_bptr))[_TC_i]; \
    
15.         break; \
    
16.       } \
    
17.     } \
    
18.     if((TC_rv) == 0) (TC_rv) = (TC_asiz) - (TC_bsiz); \
    
19.   } while(false)
    
20. 
    
21. 
    
22. 
    
23. /* Compare keys of two records by lexical order. */
    
24. int tccmplexical(const char *aptr, int asiz, const char *bptr, int bsiz, void *op){
    
25.         assert(aptr && asiz >= 0 && bptr && bsiz >= 0);
    
26.         int rv;
    
27.         TCCMPLEXICAL(rv, aptr, asiz, bptr, bsiz);
    
28.         return rv;
    
29. }
    
30. 
    
31. 
    
32. typedef int (*TCCMP)(const char *aptr, int asiz, const char *bptr, int bsiz, void *op);
    
33. 
    
34. typedef struct _TCTREEREC {              /* type of structure for an element of a tree */
    
35.   int ksiz;                          /* size of the region of the key */
    
36.   int vsiz;                          /* size of the region of the value */
    
37.   char v[255];
    
38.   char k[255];
    
39.   struct _TCTREEREC *left;               /* pointer to the left child */
    
40.   struct _TCTREEREC *right;              /* pointer to the right child */
    
41. } TCTREEREC;
    
42. 
    
43. typedef struct {                         /* type of structure for a tree */
    
44.   TCTREEREC *root;                       /* pointer to the root element */
    
45.   TCTREEREC *cur;                        /* pointer to the current element */
    
46.   unsigned long long rnum;                         /* number of records */
    
47.   unsigned long long msiz;                         /* total size of records */
    
48.   TCCMP cmp;                             /* pointer to the comparison function */
    
49.   void *cmpop;                           /* opaque object for the comparison function */
    
50. } TCTREE;
    
51. 
    
52. 
    
53. TCTREEREC* tctreesplay(TCTREE *tree, const char *kbuf, int ksiz){
    
54.         assert(tree && kbuf && ksiz>=0);
    
55.         TCTREEREC *top = tree->root;
    
56.         if (!top) return NULL;
    
57. 
    
58.         TCCMP cmp = tree->cmp;
    
59.         void *cmpop = tree->cmpop;
    
60.         TCTREEREC ent;
    
61.         ent.left = NULL;
    
62.         ent.right = NULL;
    
63.         TCTREEREC *lrec = &ent;
    
64.         TCTREEREC *rrec = &ent;
    
65. 
    
66.         while (true) {
    
67.             char *dbuf = (char *)top + sizeof(*top);
    
68.         int cv = cmp(kbuf, ksiz, dbuf, top->ksiz, cmpop);
    
69.                 if (cv < 0 ) {
    
70.                   if(!top->left) break;
    
71.                   dbuf = (char *)top->left + sizeof(*top);
    
72.                   cv = cmp(kbuf, ksiz, dbuf, top->left->ksiz, cmpop);
    
73.                   if(cv < 0){
    
74.                         TCTREEREC *swap = top->left;
    
75.                         top->left = swap->right;
    
76.                         swap->right = top;
    
77.                         top = swap;
    
78.                         if(!top->left) break;
    
79.                   }
    
80.                   rrec->left = top;
    
81.                   rrec = top;
    
82.                   top = top->left;
    
83.                 } else if (cv >0 ) {
    
84.                    if(!top->right) break;
    
85.                   dbuf = (char *)top->right + sizeof(*top);
    
86.                   cv = cmp(kbuf, ksiz, dbuf, top->right->ksiz, cmpop);
    
87.                   if(cv > 0){
    
88.                         TCTREEREC *swap = top->right;
    
89.                         top->right = swap->left;
    
90.                         swap->left = top;
    
91.                         top = swap;
    
92.                         if(!top->right) break;
    
93.                   }
    
94.                   lrec->right = top;
    
95.                   lrec = top;
    
96.                   top = top->right;
    
97.                 } else {
    
98.                    break;
    
99.                 }
    
100.         }
     
101. 
     
102. 
     
103.         lrec->right = top->left;
     
104.         rrec->left = top->right;
     
105.         top->left = ent.right;
     
106.         top->right = ent.left;
     
107.         return top;
     
108. }
     
109. 
     
110. 
     
111. /* Store a record into a tree object. */
     
112. void tctreeput(TCTREE *tree, const char *kbuf, int ksiz, const char *vbuf, int vsiz){
     
113.   assert(tree && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
     
114.   TCTREEREC *top = tctreesplay(tree, kbuf, ksiz);
     
115.   if (!top){
     
116.      TCTREEREC *rec;
     
117.          rec = (TCTREEREC *)malloc(sizeof(*rec) + ksiz + vsiz + 1);
     
118.          char *dbuf = (char *)rec + sizeof(*rec);
     
119.      memcpy(dbuf, kbuf, ksiz);
     
120.      dbuf[ksiz] = '\0';
     
121.      rec->ksiz = ksiz;
     
122.      memcpy(dbuf + ksiz, vbuf, vsiz);
     
123.      dbuf[ksiz+vsiz] = '\0';
     
124.      rec->vsiz = vsiz;
     
125.      rec->left = NULL;
     
126.      rec->right = NULL;
     
127.          memcpy(rec->k, kbuf, ksiz);
     
128.          memcpy(rec->v, vbuf, vsiz);
     
129.      tree->root = rec;
     
130.      tree->rnum = 1;
     
131.      tree->msiz = ksiz + vsiz;
     
132.      return;
     
133.   }
     
134. 
     
135.   char *dbuf = (char *)top + sizeof(*top);
     
136.   int cv = tree->cmp(kbuf, ksiz, dbuf, top->ksiz, tree->cmpop);
     
137.    if(cv < 0){
     
138.             TCTREEREC *rec;
     
139.          rec = (TCTREEREC *)malloc(sizeof(*rec) + ksiz + vsiz + 1);
     
140.          char *dbuf = (char *)rec + sizeof(*rec);
     
141.      memcpy(dbuf, kbuf, ksiz);
     
142.      dbuf[ksiz] = '\0';
     
143.      rec->ksiz = ksiz;
     
144.      memcpy(dbuf + ksiz, vbuf, vsiz);
     
145.      dbuf[ksiz+vsiz] = '\0';
     
146.      rec->vsiz = vsiz;
     
147.          memcpy(rec->k, kbuf, ksiz);
     
148.          memcpy(rec->v, vbuf, vsiz);
     
149.          rec->left = top->left;
     
150.      rec->right = top;
     
151.      top->left = NULL;
     
152.      tree->rnum++;
     
153.      tree->msiz += ksiz + vsiz;
     
154.      tree->root = rec;
     
155.    } else if (cv>0) {
     
156.      TCTREEREC *rec;
     
157.          rec = (TCTREEREC *)malloc(sizeof(*rec) + ksiz + vsiz + 1);
     
158.          char *dbuf = (char *)rec + sizeof(*rec);
     
159.      memcpy(dbuf, kbuf, ksiz);
     
160.      dbuf[ksiz] = '\0';
     
161.      rec->ksiz = ksiz;
     
162.      memcpy(dbuf + ksiz, vbuf, vsiz);
     
163.      dbuf[ksiz+vsiz] = '\0';
     
164.      rec->vsiz = vsiz;
     
165.          memcpy(rec->k, kbuf, ksiz);
     
166.          memcpy(rec->v, vbuf, vsiz);
     
167.          rec->left = top;
     
168.      rec->right = top->right;
     
169.      top->right = NULL;
     
170.      tree->rnum++;
     
171.      tree->msiz += ksiz + vsiz;
     
172.      tree->root = rec;
     
173.    } else {
     
174.        tree->msiz += vsiz - top->vsiz;
     
175.            if(vsiz > top->vsiz){
     
176.                   TCTREEREC *old = top;
     
177.                   top = (TCTREEREC *)realloc(top,sizeof(*top) + ksiz + vsiz + 1);
     
178.                   if(top != old){
     
179.                         if(tree->cur == old) tree->cur = top;
     
180.                         dbuf = (char *)top + sizeof(*top);
     
181.                   }
     
182.                 }
     
183.                 memcpy(dbuf + ksiz, vbuf, vsiz);
     
184. 
     
185.                 dbuf[ksiz+vsiz] = '\0';
     
186.                 top->vsiz = vsiz;
     
187.                 tree->root = top;
     
188.    }
     
189. }
     
190. 
     
191. 
     
192. 
     
193. 
     
194. /* Create a tree object with specifying the custom comparison function. */
     
195. TCTREE *tctreenew2(TCCMP cmp, void *cmpop){
     
196.   assert(cmp);
     
197.   TCTREE *tree;
     
198.   tree = (TCTREE *)malloc(sizeof(*tree));
     
199.   tree->root = NULL;
     
200.   tree->cur = NULL;
     
201.   tree->rnum = 0;
     
202.   tree->msiz = 0;
     
203.   tree->cmp = cmp;
     
204.   tree->cmpop = cmpop;
     
205.   return tree;
     
206. }
     
207. 
     
208. int main(void)
     
209. {
     
210.         TCTREE * tree = tctreenew2(tccmplexical, NULL);
     
211.        
     
212.         tctreeput(tree,"F", 1,"fff", 3);
     
213.         tctreeput(tree,"D", 1,"ddd", 3);
     
214.         tctreeput(tree,"E", 1,"eee", 3);
     
215.         tctreeput(tree,"H", 1,"hhh", 3);
     
216.         tctreeput(tree,"G", 1,"ggg", 3);
     
217.         tctreeput(tree,"B", 1,"bbb", 3);
     
218.         tctreeput(tree,"C", 1,"ccc", 3);
     
219.         tctreeput(tree,"I", 1,"iii", 3);
     
220. 
     
221. 
     
222.         /*
     
223. 
     
224.         tctreeput(tree,"N", 1,"nnn", 3);
     
225.         tctreeput(tree,"M", 1,"mmm", 3);
     
226.         tctreeput(tree,"L", 1,"lll", 3);
     
227.         tctreeput(tree,"K", 1,"kkk", 3);
     
228.         tctreeput(tree,"J", 1,"jjj", 3);
     
229.         tctreeput(tree,"I", 1,"iii", 3);
     
230.         tctreeput(tree,"H", 1,"hhh", 3);
     
231.         tctreeput(tree,"G", 1,"ggg", 3);
     
232. */
     
233.        
     
234. 
     
235.          system("pause");
     
236.      return 0;
     
237. }
     

复制代码

求大神解读一下这是种什么样的二叉排序树吧，它是如何进行存储排序的，程序可以在vc2008下运行

vbs100

splay树 伸展树

hm2462964492

是的 书本上好像没有介绍这个树