Linux內核的紅黑樹RB_TREE和FreeBSD 8.0裡面的AVL_TREE比較

Linux內核的紅黑樹RB_TREE和FreeBSD 8.0裡面的AVL_TREE比較之一 RB_TREE

這裡不涉及到avl樹和紅黑樹誰優誰劣，只是談談在兩種實現的一些細節，以及最後給出一些性能比較。

這裡先給出Linux下面的紅黑樹的實現，因為Linux下面的兩個宏定義不好直接使用，原型如下：

1. #define rb_entry(ptr, type, member) container_of(ptr, type, member)   
2.   
3. #ifndef container_of   
4. /** 
5.  * container_of - cast a member of a structure out to the containing structure 
6.  * @ptr:    the pointer to the member. 
7.  * @type:   the type of the container struct this is embedded in. 
8.  * @member: the name of the member within the struct. 
9.  * 
10.  */  
11. #define container_of(ptr, type, member) ({          \   
12.     const typeof(((type *)0)->member) * __mptr = (ptr);  \  
13.     (type *)((char *)__mptr - offsetof(type, member)); })  
14. #endif   
15.   
16. #ifndef offsetof   
17. #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)   
18. #endif  

修改如下：

1. #ifndef offsetof   
2. #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)   
3. #endif   
4.   
5. #ifndef container_of   
6. /** 
7.  * container_of - cast a member of a structure out to the containing structure 
8.  * @ptr:    the pointer to the member. 
9.  * @type:   the type of the container struct this is embedded in. 
10.  * @member: the name of the member within the struct. 
11.  * 
12.  * !!! modify the typeof marco, just use the rb_node 
13.  */  
14. #define container_of(ptr, type, member)         \   
15.     (((char *)ptr) - offsetof(type, member))  
16. #endif   
17.   
18. #define rb_entry(ptr, type, member) container_of(ptr, type, member)  

語義可以認為不變的。

linux的RB_TREE源代碼移植到vc上後，命名為：rb_tree.h， 如下：

1. /* 
2.   Red Black Trees 
3.   (C) 1999  Andrea Arcangeli <[email protected]> 
4.    
5.   This program is free software; you can redistribute it and/or modify 
6.   it under the terms of the GNU General Public License as published by 
7.   the Free Software Foundation; either version 2 of the License, or 
8.   (at your option) any later version. 
9.  
10.   This program is distributed in the hope that it will be useful, 
11.   but WITHOUT ANY WARRANTY; without even the implied warranty of 
12.   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
13.   GNU General Public License for more details. 
14.  
15.   You should have received a copy of the GNU General Public License 
16.   along with this program; if not, write to the Free Software 
17.   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA 
18.  
19.   linux/include/linux/rbtree.h 
20.  
21.   To use rbtrees you'll have to implement your own insert and search cores. 
22.   This will avoid us to use callbacks and to drop drammatically performances. 
23.   I know it's not the cleaner way,  but in C (not in C++) to get 
24.   performances and genericity... 
25.  
26.   Some example of insert and search follows here. The search is a plain 
27.   normal search over an ordered tree. The insert instead must be implemented 
28.   in two steps: First, the code must insert the element in order as a red leaf 
29.   in the tree, and then the support library function rb_insert_color() must 
30.   be called. Such function will do the not trivial work to rebalance the 
31.   rbtree, if necessary. 
32.  
33. ----------------------------------------------------------------------- 
34. static inline struct page * rb_search_page_cache(struct inode * inode, 
35.                          unsigned long offset) 
36. { 
37.     struct rb_node * n = inode->i_rb_page_cache.rb_node; 
38.     struct page * page; 
39.  
40.     while (n) 
41.     { 
42.         page = rb_entry(n, struct page, rb_page_cache); 
43.  
44.         if (offset < page->offset) 
45.             n = n->rb_left; 
46.         else if (offset > page->offset) 
47.             n = n->rb_right; 
48.         else 
49.             return page; 
50.     } 
51.     return NULL; 
52. } 
53.  
54. static inline struct page * __rb_insert_page_cache(struct inode * inode, 
55.                            unsigned long offset, 
56.                            struct rb_node * node) 
57. { 
58.     struct rb_node ** p = &inode->i_rb_page_cache.rb_node; 
59.     struct rb_node * parent = NULL; 
60.     struct page * page; 
61.  
62.     while (*p) 
63.     { 
64.         parent = *p; 
65.         page = rb_entry(parent, struct page, rb_page_cache); 
66.  
67.         if (offset < page->offset) 
68.             p = &(*p)->rb_left; 
69.         else if (offset > page->offset) 
70.             p = &(*p)->rb_right; 
71.         else 
72.             return page; 
73.     } 
74.  
75.     rb_link_node(node, parent, p); 
76.  
77.     return NULL; 
78. } 
79.  
80. static inline struct page * rb_insert_page_cache(struct inode * inode, 
81.                          unsigned long offset, 
82.                          struct rb_node * node) 
83. { 
84.     struct page * ret; 
85.     if ((ret = __rb_insert_page_cache(inode, offset, node))) 
86.         goto out; 
87.     rb_insert_color(node, &inode->i_rb_page_cache); 
88.  out: 
89.     return ret; 
90. } 
91. ----------------------------------------------------------------------- 
92. */  
93.   
94. #ifndef _LINUX_RBTREE_H   
95. #define _LINUX_RBTREE_H   
96.   
97. #define EXPORT_SYMBOL(i)   
98.   
99. #pragma pack (push)   
100. #pragma pack(4)   
101. struct rb_node  
102. {  
103.     unsigned long  rb_parent_color;  
104. #define RB_RED      0   
105. #define RB_BLACK    1   
106.     struct rb_node *rb_right;  
107.     struct rb_node *rb_left;  
108. } ;  
109.   
110. #pragma pack (pop)   
111.     /* The alignment might seem pointless, but allegedly CRIS needs it */  
112.   
113. struct rb_root  
114. {  
115.     struct  rb_node *rb_node;  
116.     int     (*cmp)(void *src, void *dst);  
117.     void    (*insert)(struct rb_root *root, void *ins);  
118.     void    (*remove)(struct rb_root *root, void *del);  
119. };  
120.   
121.   
122. #define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))   
123. #define rb_color(r)   ((r)->rb_parent_color & 1)   
124. #define rb_is_red(r)   (!rb_color(r))   
125. #define rb_is_black(r) rb_color(r)   
126. #define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)   
127. #define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)   
128.   
129. static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)  
130. {  
131.     rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;  
132. }  
133. static inline void rb_set_color(struct rb_node *rb, int color)  
134. {  
135.     rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;  
136. }  
137.   
138. #ifndef offsetof   
139. #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)   
140. #endif   
141.   
142. #ifndef container_of   
143. /** 
144.  * container_of - cast a member of a structure out to the containing structure 
145.  * @ptr:    the pointer to the member. 
146.  * @type:   the type of the container struct this is embedded in. 
147.  * @member: the name of the member within the struct. 
148.  * 
149.  * !!! modify the typeof marco, just use the rb_node 
150.  */  
151. #define container_of(ptr, type, member)         \   
152.     (((char *)ptr) - offsetof(type, member))  
153. #endif   
154.   
155. #define RB_ROOT (struct rb_root) { NULL, }   
156. #define rb_entry(ptr, type, member) container_of(ptr, type, member)   
157.   
158. #define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)   
159. #define RB_EMPTY_NODE(node) (rb_parent(node) == node)   
160. #define RB_CLEAR_NODE(node) (rb_set_parent(node, node))   
161.   
162. static inline void rb_init_node(struct rb_node *rb)  
163. {  
164.     rb->rb_parent_color = 0;  
165.     rb->rb_right = NULL;  
166.     rb->rb_left = NULL;  
167.     RB_CLEAR_NODE(rb);  
168. }  
169.   
170. extern void rb_insert_color(struct rb_node *, struct rb_root *);  
171. extern void rb_erase(struct rb_node *, struct rb_root *);  
172.   
173. typedef void (*rb_augment_f)(struct rb_node *node, void *data);  
174.   
175. extern void rb_augment_insert(struct rb_node *node,  
176.                   rb_augment_f func, void *data);  
177. extern struct rb_node *rb_augment_erase_begin(struct rb_node *node);  
178. extern void rb_augment_erase_end(struct rb_node *node,  
179.                  rb_augment_f func, void *data);  
180.   
181. /* Find logical next and previous nodes in a tree */  
182. extern struct rb_node *rb_next(const struct rb_node *);  
183. extern struct rb_node *rb_prev(const struct rb_node *);  
184. extern struct rb_node *rb_first(const struct rb_root *);  
185. extern struct rb_node *rb_last(const struct rb_root *);  
186.   
187. /* Fast replacement of a single node without remove/rebalance/add/rebalance */  
188. extern void rb_replace_node(struct rb_node *victim, struct rb_node *new_node_node,   
189.                 struct rb_root *root);  
190.   
191. static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,  
192.                 struct rb_node ** rb_link)  
193. {  
194.     node->rb_parent_color = (unsigned long )parent;  
195.     node->rb_left = node->rb_right = NULL;  
196.   
197.     *rb_link = node;  
198. }  
199.   
200. #endif  /* _LINUX_RBTREE_H */