Linux内核中的红黑树

boqrviking

我对这方面还不是弄得很好!
但是还是谢谢了!

HbbT

今天也在学习RBTree，根据内核里面的代码（比较懒，结构体和变量名都是内核copy的。：）），写了个测试代码，分享给大家。

#include "rbtree.h"

struct rb_root        key_user_tree;

struct key_user {
    struct rb_node                node;
    int                        key;               
};

struct key_user root_key_user;

struct key_user * RBTreeInsert(INT32 key)
{
    struct key_user *candidate = NULL, *user;
    struct rb_node *parent = NULL;
    struct rb_node **p;
   
    p = &key_user_tree.rb_node;
   
    while (*p) {
        parent = *p;
        user = rb_entry(parent, struct key_user, node);
        
        if (key < user->key)
            p = &(*p)->rb_left;
        else if (key > user->key)
            p = &(*p)->rb_right;
        else
        {
            printf("RBTreeInsert : exist");
            return NULL;
        }
    }   
   
    candidate = (struct key_user *)malloc( sizeof(struct key_user) );
    if ( NULL == candidate )
    {
        return NULL;
    }
   
    candidate->key = key;
    rb_link_node(&candidate->node, parent, p);
    rb_insert_color(&candidate->node, &key_user_tree);   
   
    return candidate;
}


struct key_user * RBTreeSerach(INT32 key)
{
    struct key_user *user;
    struct rb_node *parent = NULL;
    struct rb_node **p;
   
    p = &key_user_tree.rb_node;
   
    while (*p) {
        parent = *p;
        user = rb_entry(parent, struct key_user, node);
        
        if (key < user->key)
            p = &(*p)->rb_left;
        else if (key > user->key)
            p = &(*p)->rb_right;
        else
        {                       
            return user;
        }
    }   
   
    printf("RBTreeSerach : NULL");
    return NULL;
}

void BRTreeErase( struct key_user *user )
{
    rb_erase(&user->node, &key_user_tree);
   
    free (user );
}

void RBTreeTest()
{
    struct key_user *user;
   
    root_key_user.key = 0;
   
    rb_link_node(&root_key_user.node,
        NULL,
        &key_user_tree.rb_node);
   
    rb_insert_color(&root_key_user.node,
        &key_user_tree);   
   
    if ( NULL == RBTreeInsert( 1 ) )
    {
        printf("RBTreeTest : insert 1 ok");
    }
   
    if ( NULL == RBTreeInsert( 2 ) )
    {
        printf("RBTreeTest : insert 2 ok");
    }
   
    if ( NULL == RBTreeInsert( 1 ) )
    {
        printf("RBTreeTest : insert 1 exist");
    }   
   
    user = RBTreeSerach( 1 );
    if ( NULL != user )
    {
        BRTreeErase( user );
        printf("RBTreeTest : 1 find and delete");
    }
   
    user = RBTreeSerach( 1 );
    if ( NULL != user )
    {
        BRTreeErase( user );
    }
    else
    {
        printf("RBTreeTest : can't find");
    }
   
    user = RBTreeSerach( 2 );
    if ( NULL != user )
    {
        BRTreeErase( user );
        printf("RBTreeTest : 2 find and delete");
    }
}

[ 本帖最后由 HbbT 于 2009-2-4 13:09 编辑 ]

fly6

qos的htb也使用了红黑树

juruqiang

:wink:

rc8523

学习学习

tinysrc

好文啊，要顶

crazyhadoop

不错，又看到了。学习一下。

c04n05

这个之前学过。现在忘了。
刚好来复习一下。{:3_193:}

duanjigang

今天也在学习RBTree，根据内核里面的代码（比较懒，结构体和变量名都是内核copy的。：）），写了个测试代码 ...
HbbT 发表于 2009-02-04 13:07

这段代码是不是判断写错了？赫赫:wink:

1. 
   
2. if ( NULL == RBTreeInsert( 1 ) )
   
3. {
   
4.                 printf("RBTreeTest : insert 1 ok\n");
   
5. }
   
6. 
   
7. if ( NULL == RBTreeInsert( 2 ) )
   
8.   {
   
9.                 printf("RBTreeTest : insert 2 ok\n");
   
10.   }
    

复制代码

是不是应该这样写:

1. 
   
2. if ( NULL != RBTreeInsert( 1 ) )
   
3.         {
   
4.                 printf("RBTreeTest : insert 1 ok\n");
   
5.         }
   
6. 
   
7.         if ( NULL != RBTreeInsert( 2 ) )
   
8.         {
   
9.                 printf("RBTreeTest : insert 2 ok\n");
   
10.         }
    

复制代码

ogred3d

没看明白，要慢慢琢磨了。