相信大家都知道红黑树是什么吧,但是呢......如果你确实不知道,你不该穿越到这儿的,你应该去这里,这里,还有这里看看,然后再来这里看看,最后如果大爷您赏脸,再来看看我吧 :-) 废话少说,直接入正题吧,Linux 内核为我们实现了简洁高效但是......却不那么容易使用的红黑树,如何在你的 C 程序里面使用内核开发者为我们实现的红黑树呢,别急别急,本文将一一为您呈现。 Linux 内核红黑树的实现代码位于:lib/rbtree.c,同时头文件在 include/linux/rbtree.h 中,内核中很多模块都使用了红黑树,详细介绍参见内核文档 Documentation/rbtree.txt。 内核中红黑树定义如下: struct rb_node { unsigned long rb_parent_color; #define RB_RED 0 #define RB_BLACK 1 struct rb_node *rb_right; struct rb_node *rb_left; } __attribute__((aligned(sizeof(long)))); struct rb_root { struct rb_node *rb_node; }; 在使用内核的红黑树时,需将 struct rb_node 结构包含在自己的数据结构中,比如: struct mynode { struct rb_node node; char *string; /*more stuff of your structure hereby*/ }; 可以通过container_of宏获取包含了 rb_node 结构的起始地址,也可以通过rb_entry(node, type, member),其实:
#define rb_entry(ptr, type, member) container_of(ptr, type, member)
container_of 中使用了offsetof宏,它们都是内核中常见的宏,其定义如下: #if defined(container_of) #undef container_of #define container_of(ptr, type, member) ({ const typeof( ((type *)0)->member ) *__mptr = (ptr); (type *)( (char *)__mptr - offsetof(type,member) );}) #endif #if defined(offsetof) #undef offsetof #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) #endif 如果对上面两个宏的意思不理解,可以在本文后面留言 :-) 为了使用内核提供的红黑树,你需要自己实现插入和查找函数,如下: struct mynode *my_search(struct rb_root *root, char *string) { struct rb_node *node = root->rb_node; while (node) { struct mynode *data = container_of(node, struct mynode, node); int result; result = strcmp(string, data->string); if (result < 0) node = node->rb_left; else if (result > 0) node = node->rb_right; else return data; } return NULL; } 释放某一节点空间: void my_free(struct mynode *node) { if (node != NULL) { if (node->string != NULL) { free(node->string); node->string = NULL; } free(node); node = NULL; } } 综合上面的代码: #define NUM_NODES 32 int main() { struct mynode *mn[NUM_NODES]; /* *insert */ int i = 0; for (; i < NUM_NODES; i++) { mn[i] = (struct mynode *)malloc(sizeof(struct mynode)); mn[i]->string = (char *)malloc(sizeof(char) * 4); sprintf(mn[i]->string, "%d", i); my_insert(&mytree, mn[i]); } /* *search */ struct rb_node *node; for (node = rb_first(&mytree); node; node = rb_next(node)) printf("key = %s\n", rb_entry(node, struct mynode, node)->string); /* *delete */ printf("delete node 20: \n"); struct mynode *data = my_search(&mytree, "20"); if (data) { rb_erase(&data->node, &mytree); my_free(data); } /* *delete again*/ printf("delete node 10: \n"); data = my_search(&mytree, "10"); if (data) { rb_erase(&data->node, &mytree); my_free(data); } /* *delete once again*/ printf("delete node 15: \n"); data = my_search(&mytree, "15"); if (data) { rb_erase(&data->node, &mytree); my_free(data); } /* *search again*/ printf("search again:\n"); for (node = rb_first(&mytree); node; node = rb_next(node)) printf("key = %s\n", rb_entry(node, struct mynode, node)->string); return 0; } 完整代码请移步我的github:https://github.com/forhappy/rbtree
|
|