Linux内核红黑树使用

我现正在linux kernel 4.4.1中新增一个类sysfs文件系统,取名jefffs,

大名鼎鼎的kobject,自然也被我山寨成了jobject :)

内核中的小知识点、数据结构什么的当然也非常多,需要在开发项目的时候不断总结运用才能融会贯通,现记录一个昨天用到的红黑树。如果要知道原理上这个网站,直接动态观看: http://47.52.149.59/jeff_struction/visualization/RedBlack.html

现直接贴上红黑树测试代码:

/*jefffs.h*/

#ifndef __JEFFFS_INTERNAL_H
#define __JEFFFS_INTERNAL_H

#include <linux/jefffs.h>
extern int test_rb(void);

struct jeff_node{
    atomic_t count;
    const char *name;
    struct rb_node rb;
    unsigned int ino;
};
#endif


/*************************************/
/* rb.c*/
#include <linux/rbtree.h>
#include <linux/slab.h>
#include "jefffs.h"

#define rb_to_jn(X) rb_entry((X),struct jeff_node,rb)

int jeff_rb_insert(struct rb_root *root,struct jeff_node *data)
{
    struct rb_node **node = &(root->rb_node);
    struct rb_node *parent = NULL;

    while(*node){
        struct jeff_node *pos = rb_to_jn(*node);

        parent = *node;
        if(data->ino < pos->ino)
            node = &(*node)->rb_left;
        else if(data->ino > pos->ino)
            node = &(*node)->rb_right;
        else 
            return -1;
    }
    rb_link_node(&data->rb,parent,node);
    rb_insert_color(&data->rb,root);
    return 0;
}

void jeff_print_rbtree(struct rb_root *tree)
{
    struct rb_node *node;

    for(node = rb_first(tree);node;node = rb_next(node))
        printk("%d ",(rb_to_jn(node))->ino);

    printk("%s (%d)\n",__func__,__LINE__);
}


struct jeff_node *jeff_rb_search(struct rb_root *root,int ino)
{
    struct rb_node *node = root->rb_node;

    while(node){
        struct jeff_node *pos = rb_to_jn(node);

        if(ino < pos->ino)
            node = node->rb_left;
        else if(ino > pos->ino)
            node = node->rb_right;
        else
            return pos;
    }
    return NULL;
}

int  jeff_rb_delete(struct rb_root *root,int ino)
{
    struct jeff_node *pos = jeff_rb_search(root,ino);

    if(!pos){
        printk("not found jeff_node,can not delete\n");
        return -1;
    }
    rb_erase(&pos->rb,root);

    return 0;
}



int test_rb(void)
{

    struct rb_root root = RB_ROOT;
    struct jeff_node *search = NULL;
    int i;
    int retval;
    char *error;

#define MAX_TEST_NODE (10)
    struct jeff_node *node[MAX_TEST_NODE];

    for(i = 0;i < MAX_TEST_NODE;i++){
        node[i] = kmalloc(sizeof(struct jeff_node),GFP_KERNEL); 
        if(!node[i]){
            error = "no enough memory\n";
            goto error;
        }
        node[i]->ino = i;
        if(i == 3)
            node[i]->name = "9527";
        retval = jeff_rb_insert(&root,node[i]);
        if(retval)
            goto err_val;
    }

    jeff_rb_delete(&root,5);
    jeff_print_rbtree(&root);
    search = jeff_rb_search(&root,3);
    if(!search){
        printk("jeff search fail %s(%d)\n",__func__,__LINE__);
        return -1;
    }
    printk("searched name is %s\n",search->name);

    return 0;
err_val:
    return -1;
error:
    printk("jeff_node %s %s(%d)\n",error,__func__,__LINE__);
    return -ENOMEM;
}

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

(完)

原文发布于微信公众号 - 相遇Linux(LinuxJeff)

原文发表时间:2018-08-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券