Linux內(nèi)核中的紅黑樹

boqrviking

我對這方面還不是弄得很好!
但是還是謝謝了!

HbbT

今天也在學(xué)習(xí)RBTree，根據(jù)內(nèi)核里面的代碼（比較懶，結(jié)構(gòu)體和變量名都是內(nèi)核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

學(xué)習(xí)學(xué)習(xí)

tinysrc

好文啊，要頂

crazyhadoop

不錯，又看到了。學(xué)習(xí)一下。

c04n05

這個之前學(xué)過。現(xiàn)在忘了。
剛好來復(fù)習(xí)一下。{:3_193:}

duanjigang

今天也在學(xué)習(xí)RBTree，根據(jù)內(nèi)核里面的代碼（比較懶，結(jié)構(gòu)體和變量名都是內(nèi)核copy的。：）），寫了個測試代碼 ...
HbbT 發(fā)表于 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.   }
    

復(fù)制代碼

是不是應(yīng)該這樣寫:

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.         }
    

復(fù)制代碼

ogred3d

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