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 <andrea@SUSE.de> 
  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 */  
  • 1
  • 2
  • 3
  • 下一页

相关内容