『Linux内核红黑树之通用红黑树』Linux内核红黑树+C99弹性结构体封装

rc8523

发个前不久写的东西
『Linux内核红黑树之通用红黑树』
经测试通过暂时没有发现问题，特发出来共享，欢迎拍砖

代码依照优良的Linux编码传统
对于一般返回int的函数， 返回<0是错误，0是正常的情况
对于一般返回指针的函数，返回空指针是错误，非空是正常的情况

下面附件有打包好的，简要介绍一下每一个文件:
1. rbtree.h      从Linux源码扒下来的红黑树代码文件
2. rbtree.c      从Linux源码扒下来的红黑树头文件
3. rbtree_rc.h 封装Linux内核红黑树成为通用红黑树的头文件
4. rbtree_rc.c 实现的封装Linux内核红黑树成为通用红黑树的代码
5. rbtest1.c    对树的测试用例1,  测试各项基本功能
6. rbtest2.c    对树的测试用例2,  进行大量节点的插入，替换，删除操作,
                     曾在vmware,512内存的配置成单核虚拟机，实际电脑2.6GHz双核I3CPU上
                             测试过分配100万节点的插入，替换，删除，几乎都是瞬间完成，这足以说明红黑的强悍效率,
                             可以取消屏幕打印操作试试，因为效率都消耗在打印上了
                             打包的代码文件是10万节点，可以改大试试
                             对红黑不了解的童鞋们去找这方面的资料看看
7. makefile     执行编译创建可执行测试用例的文件

内核红黑树代码某些地方经过略微修改，所以还是有必要帖一下
所有源码文件和头文件还有工程编译makefile文件放在同一目录下
直接执行make命令即可生成测试用例 rbtest1 和 rbtest2
//内核红黑树实现文件
//rbtree.c

1. /*
   
2.   Red Black Trees
   
3.   (C) 1999  Andrea Arcangeli <andrea@suse.de>
   
4.   (C) 2002  David Woodhouse <dwmw2@infradead.org>
   
5.   
   
6.   This program is free software; you can redistribute it and/or modify
   
7.   it under the terms of the GNU General Public License as published by
   
8.   the Free Software Foundation; either version 2 of the License, or
   
9.   (at your option) any later version.
   
10. 
    
11.   This program is distributed in the hope that it will be useful,
    
12.   but WITHOUT ANY WARRANTY; without even the implied warranty of
    
13.   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    
14.   GNU General Public License for more details.
    
15. 
    
16.   You should have received a copy of the GNU General Public License
    
17.   along with this program; if not, write to the Free Software
    
18.   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
    
19. 
    
20.   linux/lib/rbtree.c
    
21. */
    
22. 
    
23. #include "rbtree.h"
    
24. //#include <linux/module.h>
    
25. 
    
26. static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
    
27. {
    
28.         struct rb_node *right = node->rb_right;
    
29.         struct rb_node *parent = rb_parent(node);
    
30. 
    
31.         if ((node->rb_right = right->rb_left))
    
32.                 rb_set_parent(right->rb_left, node);
    
33.         right->rb_left = node;
    
34. 
    
35.         rb_set_parent(right, parent);
    
36. 
    
37.         if (parent)
    
38.         {
    
39.                 if (node == parent->rb_left)
    
40.                         parent->rb_left = right;
    
41.                 else
    
42.                         parent->rb_right = right;
    
43.         }
    
44.         else
    
45.                 root->rb_node = right;
    
46.         rb_set_parent(node, right);
    
47. }
    
48. 
    
49. static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
    
50. {
    
51.         struct rb_node *left = node->rb_left;
    
52.         struct rb_node *parent = rb_parent(node);
    
53. 
    
54.         if ((node->rb_left = left->rb_right))
    
55.                 rb_set_parent(left->rb_right, node);
    
56.         left->rb_right = node;
    
57. 
    
58.         rb_set_parent(left, parent);
    
59. 
    
60.         if (parent)
    
61.         {
    
62.                 if (node == parent->rb_right)
    
63.                         parent->rb_right = left;
    
64.                 else
    
65.                         parent->rb_left = left;
    
66.         }
    
67.         else
    
68.                 root->rb_node = left;
    
69.         rb_set_parent(node, left);
    
70. }
    
71. 
    
72. void rb_insert_color(struct rb_node *node, struct rb_root *root)
    
73. {
    
74.         struct rb_node *parent, *gparent;
    
75. 
    
76.         while ((parent = rb_parent(node)) && rb_is_red(parent))
    
77.         {
    
78.                 gparent = rb_parent(parent);
    
79. 
    
80.                 if (parent == gparent->rb_left)
    
81.                 {
    
82.                         {
    
83.                                 register struct rb_node *uncle = gparent->rb_right;
    
84.                                 if (uncle && rb_is_red(uncle))
    
85.                                 {
    
86.                                         rb_set_black(uncle);
    
87.                                         rb_set_black(parent);
    
88.                                         rb_set_red(gparent);
    
89.                                         node = gparent;
    
90.                                         continue;
    
91.                                 }
    
92.                         }
    
93. 
    
94.                         if (parent->rb_right == node)
    
95.                         {
    
96.                                 register struct rb_node *tmp;
    
97.                                 __rb_rotate_left(parent, root);
    
98.                                 tmp = parent;
    
99.                                 parent = node;
    
100.                                 node = tmp;
     
101.                         }
     
102. 
     
103.                         rb_set_black(parent);
     
104.                         rb_set_red(gparent);
     
105.                         __rb_rotate_right(gparent, root);
     
106.                 } else {
     
107.                         {
     
108.                                 register struct rb_node *uncle = gparent->rb_left;
     
109.                                 if (uncle && rb_is_red(uncle))
     
110.                                 {
     
111.                                         rb_set_black(uncle);
     
112.                                         rb_set_black(parent);
     
113.                                         rb_set_red(gparent);
     
114.                                         node = gparent;
     
115.                                         continue;
     
116.                                 }
     
117.                         }
     
118. 
     
119.                         if (parent->rb_left == node)
     
120.                         {
     
121.                                 register struct rb_node *tmp;
     
122.                                 __rb_rotate_right(parent, root);
     
123.                                 tmp = parent;
     
124.                                 parent = node;
     
125.                                 node = tmp;
     
126.                         }
     
127. 
     
128.                         rb_set_black(parent);
     
129.                         rb_set_red(gparent);
     
130.                         __rb_rotate_left(gparent, root);
     
131.                 }
     
132.         }
     
133. 
     
134.         rb_set_black(root->rb_node);
     
135. }
     
136. //EXPORT_SYMBOL(rb_insert_color);
     
137. 
     
138. static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
     
139.                              struct rb_root *root)
     
140. {
     
141.         struct rb_node *other;
     
142. 
     
143.         while ((!node || rb_is_black(node)) && node != root->rb_node)
     
144.         {
     
145.                 if (parent->rb_left == node)
     
146.                 {
     
147.                         other = parent->rb_right;
     
148.                         if (rb_is_red(other))
     
149.                         {
     
150.                                 rb_set_black(other);
     
151.                                 rb_set_red(parent);
     
152.                                 __rb_rotate_left(parent, root);
     
153.                                 other = parent->rb_right;
     
154.                         }
     
155.                         if ((!other->rb_left || rb_is_black(other->rb_left)) &&
     
156.                             (!other->rb_right || rb_is_black(other->rb_right)))
     
157.                         {
     
158.                                 rb_set_red(other);
     
159.                                 node = parent;
     
160.                                 parent = rb_parent(node);
     
161.                         }
     
162.                         else
     
163.                         {
     
164.                                 if (!other->rb_right || rb_is_black(other->rb_right))
     
165.                                 {
     
166.                                         rb_set_black(other->rb_left);
     
167.                                         rb_set_red(other);
     
168.                                         __rb_rotate_right(other, root);
     
169.                                         other = parent->rb_right;
     
170.                                 }
     
171.                                 rb_set_color(other, rb_color(parent));
     
172.                                 rb_set_black(parent);
     
173.                                 rb_set_black(other->rb_right);
     
174.                                 __rb_rotate_left(parent, root);
     
175.                                 node = root->rb_node;
     
176.                                 break;
     
177.                         }
     
178.                 }
     
179.                 else
     
180.                 {
     
181.                         other = parent->rb_left;
     
182.                         if (rb_is_red(other))
     
183.                         {
     
184.                                 rb_set_black(other);
     
185.                                 rb_set_red(parent);
     
186.                                 __rb_rotate_right(parent, root);
     
187.                                 other = parent->rb_left;
     
188.                         }
     
189.                         if ((!other->rb_left || rb_is_black(other->rb_left)) &&
     
190.                             (!other->rb_right || rb_is_black(other->rb_right)))
     
191.                         {
     
192.                                 rb_set_red(other);
     
193.                                 node = parent;
     
194.                                 parent = rb_parent(node);
     
195.                         }
     
196.                         else
     
197.                         {
     
198.                                 if (!other->rb_left || rb_is_black(other->rb_left))
     
199.                                 {
     
200.                                         rb_set_black(other->rb_right);
     
201.                                         rb_set_red(other);
     
202.                                         __rb_rotate_left(other, root);
     
203.                                         other = parent->rb_left;
     
204.                                 }
     
205.                                 rb_set_color(other, rb_color(parent));
     
206.                                 rb_set_black(parent);
     
207.                                 rb_set_black(other->rb_left);
     
208.                                 __rb_rotate_right(parent, root);
     
209.                                 node = root->rb_node;
     
210.                                 break;
     
211.                         }
     
212.                 }
     
213.         }
     
214.         if (node)
     
215.                 rb_set_black(node);
     
216. }
     
217. 
     
218. void rb_erase(struct rb_node *node, struct rb_root *root)
     
219. {
     
220.         struct rb_node *child, *parent;
     
221.         int color;
     
222. 
     
223.         if (!node->rb_left)
     
224.                 child = node->rb_right;
     
225.         else if (!node->rb_right)
     
226.                 child = node->rb_left;
     
227.         else
     
228.         {
     
229.                 struct rb_node *old = node, *left;
     
230. 
     
231.                 node = node->rb_right;
     
232.                 while ((left = node->rb_left) != NULL)
     
233.                         node = left;
     
234. 
     
235.                 if (rb_parent(old)) {
     
236.                         if (rb_parent(old)->rb_left == old)
     
237.                                 rb_parent(old)->rb_left = node;
     
238.                         else
     
239.                                 rb_parent(old)->rb_right = node;
     
240.                 } else
     
241.                         root->rb_node = node;
     
242. 
     
243.                 child = node->rb_right;
     
244.                 parent = rb_parent(node);
     
245.                 color = rb_color(node);
     
246. 
     
247.                 if (parent == old) {
     
248.                         parent = node;
     
249.                 } else {
     
250.                         if (child)
     
251.                                 rb_set_parent(child, parent);
     
252.                         parent->rb_left = child;
     
253. 
     
254.                         node->rb_right = old->rb_right;
     
255.                         rb_set_parent(old->rb_right, node);
     
256.                 }
     
257. 
     
258.                 node->rb_parent_color = old->rb_parent_color;
     
259.                 node->rb_left = old->rb_left;
     
260.                 rb_set_parent(old->rb_left, node);
     
261. 
     
262.                 goto color;
     
263.         }
     
264. 
     
265.         parent = rb_parent(node);
     
266.         color = rb_color(node);
     
267. 
     
268.         if (child)
     
269.                 rb_set_parent(child, parent);
     
270.         if (parent)
     
271.         {
     
272.                 if (parent->rb_left == node)
     
273.                         parent->rb_left = child;
     
274.                 else
     
275.                         parent->rb_right = child;
     
276.         }
     
277.         else
     
278.                 root->rb_node = child;
     
279. 
     
280. color:
     
281.         if (color == RB_BLACK)
     
282.                 __rb_erase_color(child, parent, root);
     
283. }
     
284. //EXPORT_SYMBOL(rb_erase);
     
285. 
     
286. static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data)
     
287. {
     
288.         struct rb_node *parent;
     
289. 
     
290. up:
     
291.         func(node, data);
     
292.         parent = rb_parent(node);
     
293.         if (!parent)
     
294.                 return;
     
295. 
     
296.         if (node == parent->rb_left && parent->rb_right)
     
297.                 func(parent->rb_right, data);
     
298.         else if (parent->rb_left)
     
299.                 func(parent->rb_left, data);
     
300. 
     
301.         node = parent;
     
302.         goto up;
     
303. }
     
304. 
     
305. /*
     
306. * after inserting @node into the tree, update the tree to account for
     
307. * both the new entry and any damage done by rebalance
     
308. */
     
309. void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)
     
310. {
     
311.         if (node->rb_left)
     
312.                 node = node->rb_left;
     
313.         else if (node->rb_right)
     
314.                 node = node->rb_right;
     
315. 
     
316.         rb_augment_path(node, func, data);
     
317. }
     
318. 
     
319. /*
     
320. * before removing the node, find the deepest node on the rebalance path
     
321. * that will still be there after @node gets removed
     
322. */
     
323. struct rb_node *rb_augment_erase_begin(struct rb_node *node)
     
324. {
     
325.         struct rb_node *deepest;
     
326. 
     
327.         if (!node->rb_right && !node->rb_left)
     
328.                 deepest = rb_parent(node);
     
329.         else if (!node->rb_right)
     
330.                 deepest = node->rb_left;
     
331.         else if (!node->rb_left)
     
332.                 deepest = node->rb_right;
     
333.         else {
     
334.                 deepest = rb_next(node);
     
335.                 if (deepest->rb_right)
     
336.                         deepest = deepest->rb_right;
     
337.                 else if (rb_parent(deepest) != node)
     
338.                         deepest = rb_parent(deepest);
     
339.         }
     
340. 
     
341.         return deepest;
     
342. }
     
343. 
     
344. /*
     
345. * after removal, update the tree to account for the removed entry
     
346. * and any rebalance damage.
     
347. */
     
348. void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)
     
349. {
     
350.         if (node)
     
351.                 rb_augment_path(node, func, data);
     
352. }
     
353. 
     
354. /*
     
355. * This function returns the first node (in sort order) of the tree.
     
356. */
     
357. struct rb_node *rb_first(const struct rb_root *root)
     
358. {
     
359.         struct rb_node        *n;
     
360. 
     
361.         n = root->rb_node;
     
362.         if (!n)
     
363.                 return NULL;
     
364.         while (n->rb_left)
     
365.                 n = n->rb_left;
     
366.         return n;
     
367. }
     
368. //EXPORT_SYMBOL(rb_first);
     
369. 
     
370. struct rb_node *rb_last(const struct rb_root *root)
     
371. {
     
372.         struct rb_node        *n;
     
373. 
     
374.         n = root->rb_node;
     
375.         if (!n)
     
376.                 return NULL;
     
377.         while (n->rb_right)
     
378.                 n = n->rb_right;
     
379.         return n;
     
380. }
     
381. //EXPORT_SYMBOL(rb_last);
     
382. 
     
383. struct rb_node *rb_next(const struct rb_node *node)
     
384. {
     
385.         struct rb_node *parent;
     
386. 
     
387.         if (rb_parent(node) == node)
     
388.                 return NULL;
     
389. 
     
390.         /* If we have a right-hand child, go down and then left as far
     
391.            as we can. */
     
392.         if (node->rb_right) {
     
393.                 node = node->rb_right;
     
394.                 while (node->rb_left)
     
395.                         node=node->rb_left;
     
396.                 return (struct rb_node *)node;
     
397.         }
     
398. 
     
399.         /* No right-hand children.  Everything down and left is
     
400.            smaller than us, so any 'next' node must be in the general
     
401.            direction of our parent. Go up the tree; any time the
     
402.            ancestor is a right-hand child of its parent, keep going
     
403.            up. First time it's a left-hand child of its parent, said
     
404.            parent is our 'next' node. */
     
405.         while ((parent = rb_parent(node)) && node == parent->rb_right)
     
406.                 node = parent;
     
407. 
     
408.         return parent;
     
409. }
     
410. //EXPORT_SYMBOL(rb_next);
     
411. 
     
412. struct rb_node *rb_prev(const struct rb_node *node)
     
413. {
     
414.         struct rb_node *parent;
     
415. 
     
416.         if (rb_parent(node) == node)
     
417.                 return NULL;
     
418. 
     
419.         /* If we have a left-hand child, go down and then right as far
     
420.            as we can. */
     
421.         if (node->rb_left) {
     
422.                 node = node->rb_left;
     
423.                 while (node->rb_right)
     
424.                         node=node->rb_right;
     
425.                 return (struct rb_node *)node;
     
426.         }
     
427. 
     
428.         /* No left-hand children. Go up till we find an ancestor which
     
429.            is a right-hand child of its parent */
     
430.         while ((parent = rb_parent(node)) && node == parent->rb_left)
     
431.                 node = parent;
     
432. 
     
433.         return parent;
     
434. }
     
435. //EXPORT_SYMBOL(rb_prev);
     
436. 
     
437. void rb_replace_node(struct rb_node *victim, struct rb_node *new,
     
438.                      struct rb_root *root)
     
439. {
     
440.         struct rb_node *parent = rb_parent(victim);
     
441. 
     
442.         /* Set the surrounding nodes to point to the replacement */
     
443.         if (parent) {
     
444.                 if (victim == parent->rb_left)
     
445.                         parent->rb_left = new;
     
446.                 else
     
447.                         parent->rb_right = new;
     
448.         } else {
     
449.                 root->rb_node = new;
     
450.         }
     
451.         if (victim->rb_left)
     
452.                 rb_set_parent(victim->rb_left, new);
     
453.         if (victim->rb_right)
     
454.                 rb_set_parent(victim->rb_right, new);
     
455. 
     
456.         /* Copy the pointers/colour from the victim to the replacement */
     
457.         *new = *victim;
     
458. }
     
459. //EXPORT_SYMBOL(rb_replace_node);
     

复制代码

//内核红黑树头文件
//rbtree.h

1. #ifndef        _LINUX_RBTREE_H
   
2. #define        _LINUX_RBTREE_H
   
3. 
   
4. //#include <linux/kernel.h>
   
5. //#include <linux/stddef.h>
   
6. #include <stddef.h>
   
7. 
   
8. struct rb_node
   
9. {
   
10.         unsigned long  rb_parent_color;
    
11. #define        RB_RED                0
    
12. #define        RB_BLACK        1
    
13.         struct rb_node *rb_right;
    
14.         struct rb_node *rb_left;
    
15. } __attribute__((aligned(sizeof(long))));
    
16.     /* The alignment might seem pointless, but allegedly CRIS needs it */
    
17. 
    
18. struct rb_root
    
19. {
    
20.         struct rb_node *rb_node;
    
21. };
    
22. 
    
23. 
    
24. #define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
    
25. #define rb_color(r)   ((r)->rb_parent_color & 1)
    
26. #define rb_is_red(r)   (!rb_color(r))
    
27. #define rb_is_black(r) rb_color(r)
    
28. #define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
    
29. #define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)
    
30. 
    
31. static
    
32. inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
    
33. {
    
34.         rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
    
35. }
    
36. static
    
37. inline void rb_set_color(struct rb_node *rb, int color)
    
38. {
    
39.         rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
    
40. }
    
41. 
    
42. /**********************************************************/
    
43. #ifndef offsetof
    
44. #define offsetof(type, member) \
    
45.         (size_t)&(((type *)0)->member)
    
46. #endif
    
47. 
    
48. #ifndef container_of
    
49. #define container_of(ptr, type, member)  \
    
50.         ({\
    
51.                 const typeof(((type *)0)->member) * __mptr = (ptr);\
    
52.                 (type *)((char *)__mptr - offsetof(type, member)); \
    
53.         })
    
54. #endif
    
55. /**********************************************************/
    
56. 
    
57. #define RB_ROOT        (struct rb_root) { NULL, }
    
58. #define        rb_entry(ptr, type, member) container_of(ptr, type, member)
    
59. 
    
60. #define RB_EMPTY_ROOT(root)        ((root)->rb_node == NULL)
    
61. #define RB_EMPTY_NODE(node)        (rb_parent(node) == node)
    
62. #define RB_CLEAR_NODE(node)        (rb_set_parent(node, node))
    
63. 
    
64. extern void rb_insert_color(struct rb_node *, struct rb_root *);
    
65. extern void rb_erase(struct rb_node *, struct rb_root *);
    
66. 
    
67. typedef void (*rb_augment_f)(struct rb_node *node, void *data);
    
68. 
    
69. extern void rb_augment_insert(struct rb_node *node,
    
70.                               rb_augment_f func, void *data);
    
71. extern struct rb_node *rb_augment_erase_begin(struct rb_node *node);
    
72. extern void rb_augment_erase_end(struct rb_node *node,
    
73.                                  rb_augment_f func, void *data);
    
74. 
    
75. /* Find logical next and previous nodes in a tree */
    
76. extern struct rb_node *rb_next(const struct rb_node *);
    
77. extern struct rb_node *rb_prev(const struct rb_node *);
    
78. extern struct rb_node *rb_first(const struct rb_root *);
    
79. extern struct rb_node *rb_last(const struct rb_root *);
    
80. 
    
81. /* Fast replacement of a single node without remove/rebalance/add/rebalance */
    
82. extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
    
83.                             struct rb_root *root);
    
84. 
    
85. static
    
86. inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
    
87.                                 struct rb_node ** rb_link)
    
88. {
    
89.         node->rb_parent_color = (unsigned long )parent;
    
90.         node->rb_left = node->rb_right = NULL;
    
91. 
    
92.         *rb_link = node;
    
93. }
    
94. 
    
95. #endif        /* _LINUX_RBTREE_H */
    

复制代码

//头文件
//rbtree_rc.h

1. #ifndef __RCYH_RBTREE_RC_H__
   
2. #define __RCYH_RBTREE_RC_H__
   
3. 
   
4. #include "rbtree.h"
   
5. 
   
6. struct rb_data
   
7. {
   
8.         signed   long key;
   
9.         unsigned long size;
   
10.         unsigned char data[];
    
11. };
    
12. 
    
13. struct container
    
14. {
    
15.         struct rb_node rb_node;
    
16.         struct rb_data rb_data;
    
17. };
    
18. 
    
19. /*
    
20. * Initializing rbtree root
    
21. */
    
22. extern void
    
23. init_rbtree(struct rb_root *root);
    
24. 
    
25. /*
    
26. * Search key node from rbtree
    
27. */
    
28. extern struct container *
    
29. container_search(struct rb_root *root, int key);
    
30. 
    
31. /*
    
32. * Insert key node into rbtree
    
33. */
    
34. extern int
    
35. container_insert(struct rb_root *root, struct container *cont);
    
36. 
    
37. /*
    
38. * Delete the key node from rbtree
    
39. *     delete node from rbtree, return node pointer
    
40. */
    
41. extern struct container *
    
42. container_delete(struct rb_root *root, int key);
    
43. 
    
44. /*
    
45. * Replace the key node from rbtree for new container
    
46. *    replace node from rbtree, return old node pointer
    
47. */
    
48. struct container *
    
49. container_replace(struct rb_root *root, int key, struct container *con);
    
50. 
    
51. #endif /* __RCYH_RBTREE_RC_H__ */
    

复制代码

//封装的红黑树插入，查找，删除，替换实现文件
//rbtree_rc.c

1. #include "rbtree_rc.h"
   
2. #include <stddef.h>
   
3. 
   
4. /*
   
5. * Initializing rbtree root
   
6. */
   
7. void init_rbtree(struct rb_root *root)
   
8. {
   
9.         *root = RB_ROOT;
   
10. }
    
11. 
    
12. /*
    
13. * Search key node from rbtree
    
14. */
    
15. struct container *container_search(struct rb_root *root, int key)
    
16. {
    
17.         struct rb_node *node = root->rb_node;
    
18.        
    
19.         while (node)
    
20.         {
    
21.                 struct container *this = rb_entry(node, struct container, rb_node);
    
22.                
    
23.                 int result = key - this->rb_data.key;
    
24.                
    
25.                 if (result < 0)
    
26.                         node = node->rb_left;
    
27.                 else if (result > 0)
    
28.                         node = node->rb_right;
    
29.                 else
    
30.                         return this;
    
31.         }
    
32.         return 0;
    
33. }
    
34. 
    
35. /*
    
36. * Insert key node into rbtree
    
37. */
    
38. int container_insert(struct rb_root *root, struct container *cont)
    
39. {
    
40.         struct rb_node **new = &(root->rb_node);
    
41.         struct rb_node  *parent = 0;
    
42.                
    
43.         /* Figure out where to put new node */
    
44.         while (*new)
    
45.         {
    
46.                 struct container *this = rb_entry(*new, struct container, rb_node);
    
47.                
    
48.                 int result = cont->rb_data.key - this->rb_data.key;
    
49.                
    
50.                 parent = *new;
    
51.                
    
52.                 if (result < 0)
    
53.                         new = &((*new)->rb_left);
    
54.                 else if (result > 0)
    
55.                         new = &((*new)->rb_right);
    
56.                 else
    
57.                         return -1; // the key is already exists
    
58.         }
    
59. 
    
60.         /* Add new node and rebalance tree. */
    
61.         rb_link_node(&(cont->rb_node), parent, new);
    
62.         rb_insert_color(&(cont->rb_node), root);
    
63. 
    
64.         return 0;
    
65. }
    
66. 
    
67. /*
    
68. * Delete the key node from rbtree
    
69. *     delete node from rbtree, return node pointer
    
70. */
    
71. struct container *container_delete(struct rb_root *root, int key)
    
72. {
    
73.         struct container *find = container_search(root, key);
    
74.         if (!find)
    
75.                 return 0;
    
76.         rb_erase(&find->rb_node, root);
    
77.         return find;
    
78. }
    
79. 
    
80. /*
    
81. * Replace the key node from rbtree for new container
    
82. *    replace node from rbtree, return old node pointer
    
83. */
    
84. struct container * container_replace(struct rb_root *root, int key, struct container *con)
    
85. {
    
86.         struct container *find = container_search(root, key);
    
87.         if (!find)
    
88.                 return 0;
    
89.         rb_replace_node(&(find->rb_node), &con->rb_node, root);
    
90.         return find;
    
91. }
    

复制代码

一个帖子发不下说是超了， 下面跟一个， 是两个测试用例的源码

rc8523

以下是两个测试代码
//rbtest1.c

1. #include "rbtree_rc.h"
   
2. #include <stdio.h>
   
3. #include <string.h>
   
4. #include <stdlib.h>
   
5. 
   
6. int
   
7. main(void)
   
8. {
   
9.         struct rb_root mytree = RB_ROOT;
   
10.         struct container * pc;
    
11.         int ret;
    
12.         int size = 100;
    
13.         int find, erase, replace;
    
14.         printf("rbtest go ... \n");
    
15.        
    
16.         /*
    
17.          * 插入测试
    
18.          */
    
19.         pc = calloc(sizeof(struct container) + size, 1);
    
20.         strcat((char*)&pc->rb_data.data, "hello world 1");
    
21.         pc -> rb_data.key = 1;
    
22.         pc -> rb_data.size = size;
    
23.         ret = container_insert(&mytree, pc);
    
24.         printf("insert 1 ret = %d\n", ret);
    
25. 
    
26.         pc = calloc(sizeof(struct container) + size, 1);
    
27.         strcat((char*)&pc->rb_data.data, "hello world 2");
    
28.         pc -> rb_data.key = 2;
    
29.         pc -> rb_data.size = size;
    
30.         ret = container_insert(&mytree, pc);
    
31.         printf("insert 2 ret = %d\n", ret);
    
32.        
    
33.         pc = calloc(sizeof(struct container) + size, 1);
    
34.         strcat((char*)&pc->rb_data.data, "hello world 4");
    
35.         pc -> rb_data.key = 4;
    
36.         pc -> rb_data.size = size;
    
37.         ret = container_insert(&mytree, pc);
    
38.         printf("insert 4 ret = %d\n", ret);
    
39.        
    
40.         pc = calloc(sizeof(struct container) + size, 1);
    
41.         strcat((char*)&pc->rb_data.data, "hello world 3");
    
42.         pc -> rb_data.key = 3;
    
43.         pc -> rb_data.size = size;
    
44.         ret = container_insert(&mytree, pc);
    
45.         printf("insert 3 ret = %d\n", ret);
    
46.         /********************************************************/
    
47.        
    
48.         /*
    
49.          * 查找测试
    
50.          */
    
51.         find = 6;
    
52.         printf("find key %d\n", find);
    
53.         pc = container_search(&mytree, find);
    
54.         if (pc != 0)
    
55.                 printf("key %d pc data: %s\n", find, (char*)pc->rb_data.data);
    
56.         else
    
57.                 printf("no find %d\n", find);
    
58.        
    
59.         find = 3;
    
60.         printf("find key %d\n", find);
    
61.         pc = container_search(&mytree, find);
    
62.         if (pc != 0)
    
63.                 printf("find key %d data: %s\n", find, (char*)pc->rb_data.data);
    
64.         else
    
65.                 printf("no find %d\n", find);
    
66.         /********************************************************/
    
67.        
    
68.         /*
    
69.          * 节点删除测试
    
70.          */
    
71.         erase = 3;
    
72.         printf("erase key %d\n", erase);
    
73.         pc = container_delete(&mytree, erase);
    
74.         if (pc != 0) {
    
75.                 printf("erase key %d data: %s\n", find, (char*)pc->rb_data.data);
    
76.                 free(pc);
    
77.         }
    
78.         else
    
79.                 printf("no erase %d\n", find);
    
80.        
    
81.         find = 3;
    
82.         printf("find key %d\n", find);
    
83.         pc = container_search(&mytree, find);
    
84.         if (pc != 0)
    
85.                 printf("find key %d data: %s\n", find, (char*)pc->rb_data.data);
    
86.         else
    
87.                 printf("no find %d\n", find);
    
88.         /********************************************************/
    
89.        
    
90.         /*
    
91.          * 节点更新替换测试
    
92.          */
    
93.         replace = 2;
    
94.         printf("replace key %d\n", replace);
    
95.         pc = calloc(sizeof(struct container) + size, 1);
    
96.         strcat((char*)&pc->rb_data.data, "this is replace key 2");
    
97.         pc -> rb_data.key = replace;
    
98.         pc -> rb_data.size = size;
    
99.         pc = container_replace(&mytree, replace, pc);
    
100.         if (pc != 0)
     
101.         {
     
102.                 printf("replace key %d ret = %p, data: %s\n", replace, pc, (char*)pc->rb_data.data);
     
103.                 free(pc);
     
104.         }
     
105.         else
     
106.         {
     
107.                 printf("replace key %d failed\n", replace);       
     
108.         }
     
109.        
     
110.         find = 2;
     
111.         printf("find key %d\n", find);
     
112.         pc = container_search(&mytree, find);
     
113.         if (pc != 0)
     
114.                 printf("find key %d data: %s\n", find, (char*)pc->rb_data.data);
     
115.         else
     
116.                 printf("no find %d\n", find);
     
117.         /********************************************************/
     
118.        
     
119.         printf("rbtest end\n");
     
120.                
     
121.         return 0;
     
122. }
     

复制代码

//rbtest2.c
//符号的含义
//+ 插入
//- 删除
//@ 替换
//^ 查询

1. #include "rbtree_rc.h"
   
2. #include <stdio.h>
   
3. #include <string.h>
   
4. #include <stdlib.h>
   
5. 
   
6. int
   
7. main(void)
   
8. {
   
9.         struct rb_root mytree;
   
10.         struct container * pc;
    
11.         int ret;
    
12.         int size = sizeof(int);
    
13.         int find, erase, replace;
    
14.        
    
15.         const int max = 1000000;
    
16.         int i, rd;
    
17.        
    
18.         printf("rbtest go ... \n");
    
19.        
    
20.         init_rbtree(&mytree);
    
21.        
    
22.         for (i = 0; i < max; ++i)
    
23.         {
    
24.                 rd = rand() % max;
    
25.                
    
26.                 // container 创建
    
27.                 pc = calloc(sizeof(struct container) + size, 1);
    
28.                 pc -> rb_data.key = i;
    
29.                 *(int*)&pc -> rb_data.data = rd;
    
30.                 pc -> rb_data.size = size;
    
31.                
    
32.                 // 插入
    
33.                 ret = container_insert(&mytree, pc);               
    
34.                 if (ret < 0)
    
35.                         printf("failed + insert key: %d, data: %d\n", i, rd);
    
36.                 else
    
37.                         printf("successful + insert  key: %d, data: %d\n", i, rd);
    
38.                
    
39.                 // 查找                       
    
40.                 pc = container_search(&mytree, i);
    
41.                 if (pc != 0)
    
42.                         printf("successful ^ search  key: %d, data: %d\n", i, *(int*)&pc->rb_data.data);
    
43.                 else
    
44.                         printf("failed ^ search no key %d\n", i);
    
45.                
    
46.                 // 替换某些节点
    
47.                 if (i % 20 == 0)
    
48.                 {
    
49.                         pc = calloc(sizeof(struct container) + size, 1);
    
50.                         pc -> rb_data.key = i;
    
51.                         *(int*)&pc -> rb_data.data = rand() % max;
    
52.                         pc -> rb_data.size = size;
    
53.                         pc = container_replace(&mytree, i, pc);
    
54.                         if (pc != 0)
    
55.                         {
    
56.                                 printf("successful @ replace key: %d, old data: %d, new data: %d\n",
    
57.                                                 i, *(int*)&pc->rb_data.data,
    
58.                                                 *(int*)&container_search(&mytree, i)->rb_data.data
    
59.                                                 );
    
60.                                 free(pc);
    
61.                         }
    
62.                         else
    
63.                         {
    
64.                                 printf("failed @ replace key: %d failed\n", i);       
    
65.                         }       
    
66.                 }
    
67.                
    
68.                 // 删除某些节点
    
69.                 if (i % 10 == 0)
    
70.                 {
    
71.                         pc = container_delete(&mytree, i);
    
72.                         if (pc == 0)
    
73.                         {
    
74.                                 printf("failed - delete key: %d\n", i);
    
75.                         }
    
76.                         else
    
77.                         {
    
78.                                 printf("successful - delete  key: %d, data: %d\n", i, *(int*)&pc->rb_data.data);
    
79.                                 free(pc);
    
80.                         }
    
81.                 }
    
82.         }
    
83. 
    
84.         printf("rbtest end\n");
    
85.                
    
86.         return 0;
    
87. }
    

复制代码

以下是简单的编译文件 makefile
//makefile

1. CC = gcc
   
2. 
   
3. HEAD = rbtree.h rbtree_rc.h
   
4. SRC = rbtree.c
   
5. DST = rbtest
   
6. 
   
7. MACRO = -Wall
   
8. 
   
9. # nothing:
   
10. #         @echo missing make tag
    
11. 
    
12. all: rbtest1 rbtest2
    
13. 
    
14. rbtest1: $(HEAD) $(SRC) rbtree_rc.c rbtest1.c
    
15.         $(CC) $(SRC) rbtree_rc.c rbtest1.c -o $@
    
16. 
    
17. rbtest2: $(HEAD) $(SRC) rbtree_rc.c rbtest2.c
    
18.         $(CC) $(SRC) rbtree_rc.c rbtest2.c -o $@
    
19. 
    
20. clean:
    
21.         rm -rf rbtest1 rbtest2
    

复制代码