内核中rbtree的API简单使用备忘:一个rbtree根,向其中插入结点,遍历之,删除节点,再遍历之。
系统环境:ubuntu-10.04/linux-2.6.32-38-generic
代码:
-
#include <linux/init.h>
-
#include <linux/module.h>
-
#include <linux/kernel.h>
-
-
#include <linux/rbtree.h>
-
-
MODULE_LICENSE("GPL");
-
MODULE_AUTHOR("zl");
-
MODULE_DESCRIPTION("rbtree test");
-
-
struct mytype {
-
struct rb_node node;
-
char *keystring;
-
};
-
-
struct rb_root mytree = RB_ROOT;
-
-
/** Same as binary sort tree**/
-
struct mytype *my_search(struct rb_root *root, char *string)
-
{
-
struct rb_node *node = root->rb_node;
-
while (node) {
-
struct mytype *data = container_of(node, struct mytype, node);
-
int result;
-
-
result = strcmp(string, data->keystring);
-
-
if (result < 0)
-
node = node->rb_left;
-
else if (result > 0)
-
node = node->rb_right;
-
else
-
return data;
-
}
-
return NULL;
-
}
-
-
int my_insert(struct rb_root *root, struct mytype *data)
-
{
-
struct rb_node **new = &(root->rb_node), *parent = NULL;
-
-
/* Figure out where to put new node */
-
while (*new) {
-
struct mytype *this = container_of(*new, struct mytype, node);
-
int result = strcmp(data->keystring, this->keystring);
-
-
parent = *new;
-
if (result < 0)
-
new = &((*new)->rb_left);
-
else if (result > 0)
-
new = &((*new)->rb_right);
-
else
-
return 0;
-
}
-
-
/* Add new node and rebalance tree. */
-
rb_link_node(&(data->node), parent, new);
-
#if 1
-
rb_insert_color(&(data->node), root);
-
#endif
-
return 1;
-
}
-
-
#if 0
-
/** remove **/
-
struct mytype *data = mysearch(mytree, "walrus");
-
-
if (data) {
-
rb_erase(data->node, mytree);
-
myfree(data);
-
}
-
#endif
-
-
#if 0
-
void rb_replace_node(struct rb_node *old, struct rb_node *new,
-
struct rb_root *tree);
-
#endif
-
-
#if 0
-
struct rb_node *rb_first(struct rb_root *tree);
-
struct rb_node *rb_last(struct rb_root *tree);
-
struct rb_node *rb_next(struct rb_node *node);
-
struct rb_node *rb_prev(struct rb_node *node);
-
#endif
-
-
char *array[] = {
-
"aaaaa",
-
"bbb",
-
"333",
-
"c",
-
"dddd",
-
"111",
-
"eeeeeeeee",
-
"ffffghi",
-
"222",
-
"gggabcd",
-
"12345"
-
"abcdefg"
-
};
-
-
#define TAB_SIZE(array) (sizeof(array)/sizeof(array[0]))
-
-
static int __init rbtree_init(void)
-
{
-
struct rb_node *node;
-
struct mytype *mynode;
-
int i;
-
-
for(i = 0; i < TAB_SIZE(array); i++)
-
{
-
mynode = kmalloc(sizeof(struct mytype), GFP_KERNEL);
-
mynode->keystring = (char *)array[i];
-
printk("kerstring is %s\n", mynode->keystring);
-
my_insert(&mytree, mynode);
-
}
-
-
printk("*********** 升序 ****************************\n");
-
i = 0;
-
for(node = rb_first(&mytree); node; node = rb_next(node))
-
{
-
printk("i = %d, key = %s\n", i, (rb_entry(node, struct mytype, node))->keystring);
-
i++;
-
}
-
printk("------------降序---------------------------\n");
-
i = 0;
-
for(node = rb_last(&mytree); node; node = rb_prev(node))
-
{
-
printk("i = %d, key = %s\n", i, (rb_entry(node, struct mytype, node))->keystring);
-
i++;
-
}
-
-
printk("------------删除后升序---------------------------\n");
-
mynode = my_search(&mytree, "eeeeeeeee");
-
if(mynode)
-
{
-
rb_erase(&(mynode->node), &mytree);
-
kfree(mynode);
-
printk("Erased eeeeeeeee node !\n");
-
}
-
-
for(node = rb_first(&mytree); node; node = rb_next(node))
-
{
-
printk("i = %d, key = %s\n", i, (rb_entry(node, struct mytype, node))->keystring);
-
i++;
-
}
-
-
return 0;
-
}
-
-
static void __exit rbtree_exit(void)
-
{
-
printk("exit !\n");
-
}
-
-
module_init(rbtree_init);
-
module_exit(rbtree_exit);
Makefile:
-
obj-m = myrbtree.o
-
-
#KERNELS = /media/STUDY/linux/kernel/my2440-2.6.36
-
-
KERNELS = /lib/modules/$(shell uname -r)/build/
-
-
default:
-
-
make -C $(KERNELS) M=$(shell pwd) modules
-
-
.PHONY:clean
-
-
clean:
-
-
make -C $(KERNELS) M=$(shell pwd) clean
编译,运行,及查看运行结果:符合预期
make clean;make;sudo rmmod myrbtree;sudo insmod myrbtree.ko ;dmesg
阅读(3801) | 评论(0) | 转发(1) |