内核红黑树实验

基础知识

涉及的头文件\include\linux\rbtree.h

红黑树结构体

struct rb_node {
	unsigned long  __rb_parent_color;
	struct rb_node *rb_right;
	struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
    /* The alignment might seem pointless, but allegedly CRIS needs it */

struct rb_root {
	struct rb_node *rb_node;
};

实验代码：

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

#define DEBUG_INFO(format, ...) \
    printk("%s:%d -- "format"\n",__func__,__LINE__, \
    ##__VA_ARGS__)

struct rbtree_private_data {
    struct rb_node node;
    int key;
    int data;
};

//根节点
static struct rb_root mytree = RB_ROOT;


static struct rbtree_private_data * rbtree_search(struct rb_root *root,int search_key){
    struct rb_node *pnode = (root->rb_node);
    while(pnode){
        struct rbtree_private_data *this = container_of(pnode,struct rbtree_private_data,node);
        if(this->key > search_key){
            pnode = pnode->rb_left;
        }else if(this->key < search_key){
            pnode = pnode->rb_right;
        }else{
            DEBUG_INFO("found key = %d",this->key);
            return this;
        }
    }
    DEBUG_INFO("can't find key = %d",search_key);
    return NULL;
}

static int rbtree_insert(struct rb_root *root,struct rbtree_private_data *data){
    struct rb_node **new = &(root->rb_node);
    struct rb_node *parent = NULL;
    while(*new){
        struct rbtree_private_data *this = container_of(*new,struct rbtree_private_data,node);
        parent = *new;
        if(this->key > data->key){
            new = &((*new)->rb_left);
        }else if(this->key < data->key){
            new = &((*new)->rb_right);
        }else{
            DEBUG_INFO("have key = %d",data->key);
            return -1;
        }
    }
    //添加一个新节点
    rb_link_node(&data->node,parent,new);
    rb_insert_color(&data->node,root);
    return 0;
}

static int __init rbtree_init(void){
    int i;
    struct rbtree_private_data *rpd;
    struct rb_node *pnode;
    for(i=0; i<20;i++){
        rpd = kmalloc(sizeof(struct rbtree_private_data),GFP_KERNEL);
        rpd->key = i;
        rpd->data = (i+1) * 5;
        rbtree_insert(&mytree,rpd);
    }
    //遍历红黑树
    for(pnode = rb_first(&mytree);pnode;pnode = rb_next(pnode)){
        DEBUG_INFO("key: %d",rb_entry(pnode,struct rbtree_private_data,node)->key);
    }
    //查找节点
    rpd = rbtree_search(&mytree,5);
    if(rpd != NULL){
        DEBUG_INFO("data = %d",rpd->data);
    }
    DEBUG_INFO("init");
    return 0;
}

static void __exit rbtree_exit(void){
    struct rbtree_private_data *rpd;
    struct rb_node *pnode;
    struct rb_node *pnext;
    pnode = rb_first(&mytree);
    pnext = pnode;

    //释放红黑树
    for(;pnext;){
        pnode = pnext;
        pnext = rb_next(pnext);
        rpd = rb_entry(pnode,struct rbtree_private_data,node);
        if(rpd){
            DEBUG_INFO("free key = %d",rpd->key);
            rb_erase(&rpd->node,&mytree);
            kfree(rpd);
        }
    }
    DEBUG_INFO("exit");
}

module_init(rbtree_init);
module_exit(rbtree_exit);

MODULE_LICENSE("GPL");

Makefile 

modname:=rbtree
obj-m:=$(modname).o
PWD :=$(shell pwd)
MAKE :=make
KERNELDIR = /home/lkmao/running_github/runninglinuxkernel_4.0
CROSS_COMPILE=arm-linux-gnueabi-
ARCH=arm
all:
	$(MAKE) ARCH=$(ARCH) CROSS_COMPILE=$(CROSS_COMPILE) -C $(KERNELDIR) M=$(PWD) modules
	cp $(modname).ko /home/lkmao/running_github/runninglinuxkernel_4.0/kmodules
clean:
	rm -rf $(modname).ko *.o *mod* \.*cmd *odule* .tmp_versions
.PHONY: all clean

实验结果：

加载模块：

 卸载模块：

 

小结