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)
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
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
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
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]>
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.
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.
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
19. linux/include/linux/rbtree.h
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...
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.
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;
40. while (n)
41. {
42. page = rb_entry(n, struct page, rb_page_cache);
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. }
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;
62. while (*p)
63. {
64. parent = *p;
65. page = rb_entry(parent, struct page, rb_page_cache);
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. }
75. rb_link_node(node, parent, p);
77. return NULL;
78. }
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. */
94. #ifndef _LINUX_RBTREE_H
95. #define _LINUX_RBTREE_H
97. #define EXPORT_SYMBOL(i)
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. } ;
110. #pragma pack (pop)
111. /* The alignment might seem pointless, but allegedly CRIS needs it */
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. };
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)
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. }
138. #ifndef offsetof
139. #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
140. #endif
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
155. #define RB_ROOT (struct rb_root) { NULL, }
156. #define rb_entry(ptr, type, member) container_of(ptr, type, member)
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))
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. }
170. extern void rb_insert_color(struct rb_node *, struct rb_root *);
171. extern void rb_erase(struct rb_node *, struct rb_root *);
173. typedef void (*rb_augment_f)(struct rb_node *node, void *data);
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);
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 *);
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);
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;
197. *rb_link = node;
198. }
200. #endif /* _LINUX_RBTREE_H */