kernel中的rbtree接口

内核中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