Linux内核中红黑树

序言

在看这篇文章之前，建议先看看 编写一个简单的Linux内核模块

定义数据结构

struct mytype {
    struct rb_node rb_node;
    int key;
    int num;
};

其中rb_node类型的rb_node就是红黑树的一个节点

初始化根节点

struct rb_root mytree = RB_ROOT;

初始化根节点的重点词是初始化，它的目的是为了分配一个地址。
这句话的意思你可以琢磨下为什么我这么说，也可以这么想，有没有其他方式可以省略这个初始化，比如初始化一个类型为struct mytype类型的对象。

查找

struct mytype *my_search(struct rb_root *root, int new) {
    struct rb_node *node = root->rb_node;
    while (node) {
        struct mytype *data = rb_entry(node,struct mytype, rb_node);
        if (data->key > new)
            node = node->rb_left;
        else if (data->key < new)
            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;
    while (*new) {
        struct mytype *this = rb_entry(*new,struct mytype, rb_node);
        parent = *new;
        if (this->key > data->key)
            new = &((*new)->rb_left);
        else if (this->key < data->key) {
            new = &((*new)->rb_right);
        } else {
            return -1;
        }
    }
    rb_link_node(&data->rb_node, parent, new);
    rb_insert_color(&data->rb_node, root);
    return 0;
}

遍历

static void my_traversal(struct rb_root *root)
{
    struct rb_node *node;
    for (node = rb_first(root); node != NULL; node = rb_next(node)) {
        printk("key=%d,num=%d\n", rb_entry(node,
        struct mytype, rb_node)->key, rb_entry(node,
        struct mytype, rb_node)->num);
    }
}

全部代码

全部代码分为两个文件

• rbtree.c

#include <linux/init.h>
#include <linux/module.h>
#include <linux/init.h>
#include <linux/list.h>
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/slab.h>
#include <linux/mm.h>
#include <linux/rbtree.h>

struct mytype {
    struct rb_node rb_node;
    int key;
    int num;
};

struct rb_root mytree = RB_ROOT;

struct mytype *my_search(struct rb_root *root, int new) {
    struct rb_node *node = root->rb_node;
    while (node) {
        struct mytype *data = rb_entry(node,struct mytype, rb_node);
        if (data->key > new)
            node = node->rb_left;
        else if (data->key < new)
            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;
    while (*new) {
        struct mytype *this = rb_entry(*new,struct mytype, rb_node);
        parent = *new;
        if (this->key > data->key)
            new = &((*new)->rb_left);
        else if (this->key < data->key) {
            new = &((*new)->rb_right);
        } else {
            return -1;
        }
    }
    rb_link_node(&data->rb_node, parent, new);
    rb_insert_color(&data->rb_node, root);
    return 0;
}

static void my_traversal(struct rb_root *root)
{
    struct rb_node *node;
    for (node = rb_first(root); node != NULL; node = rb_next(node)) {
        printk("key=%d,num=%d\n", rb_entry(node,
        struct mytype, rb_node)->key, rb_entry(node,
        struct mytype, rb_node)->num);
    }
}


static int __init

rbtree_init(void) {
    printk(KERN_INFO
    "rbtree enter\n");
    int i;
    struct mytype *data;
    struct rb_node *node;
    for (i = 0; i < 20; i += 2) {
        data = kmalloc(sizeof(struct mytype), GFP_KERNEL);
        data->key = i;
        data->num = 1;
        my_insert(&mytree, data);
    }
    my_traversal(&mytree);
    return 0;
}

module_init(rbtree_init);

static void __exit

rbtree_exit(void) {
    printk(KERN_INFO
    "rbtree exit\n");
    struct mytype *data;
    struct rb_node *node;
    for (node = rb_first(&mytree); node; node = rb_next(node)) {
        data = rb_entry(node,
        struct mytype, rb_node);
        if (data) {
            rb_erase(&data->rb_node, &mytree);
            kfree(data);
        }
    }
}

module_exit(rbtree_exit);

MODULE_AUTHOR("fukaiqiang");//作者
MODULE_LICENSE("GPL v2");//模块许可证声明,一般用GPL v2
MODULE_DESCRIPTION("A simple rbtree module");//模块描述
MODULE_ALIAS("hw"); //别名

• Makefile

KVERS = $(shell uname -r)

obj-m := rbtree.o

all:
    make -C /lib/modules/$(KVERS)/build M=$(PWD) modules

clean:
    make -C /lib/modules/$(KVERS)/build M=$(PWD) clean
    rm -rf *.ko;

copy这里的内容到clion后需要修改格式，把命令前的空格替换为一个Tab

编译运行查看日志

• make && sudo insmod rbtree.ko && dmesg

[1238217.030890] rbtree enter
[1238217.030893] key=0,num=1
[1238217.030894] key=2,num=1
[1238217.030894] key=4,num=1
[1238217.030895] key=6,num=1
[1238217.030895] key=8,num=1
[1238217.030895] key=10,num=1
[1238217.030896] key=12,num=1
[1238217.030896] key=14,num=1
[1238217.030897] key=16,num=1
[1238217.030897] key=18,num=1

• sudo rmmod rbtree && dmesg

[1238488.545333] rbtree exit

参考

奔跑吧Linux内核入门篇