Linux内核红黑树使用

我现正在linux kernel 4.4.1中新增一个类sysfs文件系统，取名jefffs,
大名鼎鼎的kobject，自然也被我山寨成了jobject :)
内核中的小知识点、数据结构什么的当然也非常多，需要在开发项目的时候不断总结运用才能融会贯通，现记录一个昨天用到的红黑树。如果要知道原理上这个网站，直接动态观看： http://47.52.149.59/jeff_struction/visualization/RedBlack.html
现直接贴上红黑树测试代码:

  1/*jefffs.h*/  2  3#ifndef __JEFFFS_INTERNAL_H  4#define __JEFFFS_INTERNAL_H  5  6#include <linux/jefffs.h>  7extern int test_rb(void);  8  9struct jeff_node{ 10    atomic_t count; 11    const char *name; 12    struct rb_node rb; 13    unsigned int ino; 14}; 15#endif 16 17 18/*************************************/ 19/* rb.c*/ 20#include <linux/rbtree.h> 21#include <linux/slab.h> 22#include "jefffs.h" 23 24#define rb_to_jn(X) rb_entry((X),struct jeff_node,rb) 25 26int jeff_rb_insert(struct rb_root *root,struct jeff_node *data) 27{ 28    struct rb_node **node = &(root->rb_node); 29    struct rb_node *parent = NULL; 30 31    while(*node){ 32        struct jeff_node *pos = rb_to_jn(*node); 33 34        parent = *node; 35        if(data->ino < pos->ino) 36            node = &(*node)->rb_left; 37        else if(data->ino > pos->ino) 38            node = &(*node)->rb_right; 39        else  40            return -1; 41    } 42    rb_link_node(&data->rb,parent,node); 43    rb_insert_color(&data->rb,root); 44    return 0; 45} 46 47void jeff_print_rbtree(struct rb_root *tree) 48{ 49    struct rb_node *node; 50 51    for(node = rb_first(tree);node;node = rb_next(node)) 52        printk("%d ",(rb_to_jn(node))->ino); 53 54    printk("%s (%d)\n",__func__,__LINE__); 55} 56 57 58struct jeff_node *jeff_rb_search(struct rb_root *root,int ino) 59{ 60    struct rb_node *node = root->rb_node; 61 62    while(node){ 63        struct jeff_node *pos = rb_to_jn(node); 64 65        if(ino < pos->ino) 66            node = node->rb_left; 67        else if(ino > pos->ino) 68            node = node->rb_right; 69        else 70            return pos; 71    } 72    return NULL; 73} 74 75int  jeff_rb_delete(struct rb_root *root,int ino) 76{ 77    struct jeff_node *pos = jeff_rb_search(root,ino); 78 79    if(!pos){ 80        printk("not found jeff_node,can not delete\n"); 81        return -1; 82    } 83    rb_erase(&pos->rb,root); 84 85    return 0; 86} 87 88 89 90int test_rb(void) 91{ 92 93    struct rb_root root = RB_ROOT; 94    struct jeff_node *search = NULL; 95    int i; 96    int retval; 97    char *error; 98 99#define MAX_TEST_NODE (10)100    struct jeff_node *node[MAX_TEST_NODE];101102    for(i = 0;i < MAX_TEST_NODE;i++){103        node[i] = kmalloc(sizeof(struct jeff_node),GFP_KERNEL); 104        if(!node[i]){105            error = "no enough memory\n";106            goto error;107        }108        node[i]->ino = i;109        if(i == 3)110            node[i]->name = "9527";111        retval = jeff_rb_insert(&root,node[i]);112        if(retval)113            goto err_val;114    }115116    jeff_rb_delete(&root,5);117    jeff_print_rbtree(&root);118    search = jeff_rb_search(&root,3);119    if(!search){120        printk("jeff search fail %s(%d)\n",__func__,__LINE__);121        return -1;122    }123    printk("searched name is %s\n",search->name);124125    return 0;126err_val:127    return -1;128error:129    printk("jeff_node %s %s(%d)\n",error,__func__,__LINE__);130    return -ENOMEM;131}

以上代码主函数是test_rb,由其他函数直接调用执行，运行结果如下：