内核红黑树使用范例

蔚落 2022-08-06 08:29 126阅读 0赞

# [内核红黑树使用范例][Link 1] #

内核中的红黑树只是提供了一个管理机制，并没有提供具体的使用接口。需要使用者根据自己的使用环境去定义和实现自己的关键字（char，uchar, int, uint等类型）操作。这样可以更加灵活。

像内核中的链表，hash表的代码都是这种思想。

![复制代码][copycode.gif]

1 struct mytype
      2 {  
      3     int num;  
      4 
      5     struct rb_node my_node;  
      6 };  
      7 
      8 struct mytype *my_find(struct rb_root *root, int num)  
      9 {  
     10     struct rb_node *node = root->rb_node;  
     11 
     12     while (node) {  
     13         struct mytype *data = rb_entry(node, struct mytype, my_node);
     14 
     15         if (num < data->num)  
     16             node = node->rb_left;  
     17         else if (num > data->num)  
     18             node = node->rb_right;  
     19         else  
     20             return data;  
     21     }  
     22 
     23     return NULL;  
     24 }  
     25 
     26 
     27 int my_insert(struct rb_root *root,  struct mytype *data)  
     28 {  
     29     struct rb_node  *parent = NULL;
     30     struct rb_node **tmp = &(root->rb_node); 
     31 
     32     /* Figure out where to put new node */  
     33     while (*tmp) {  
     34         struct mytype *this = rb_entry(*tmp, struct mytype, my_node);  
     35 
     36         parent = *tmp;  
     37         if (data->num < this->num)  
     38             tmp = &((*tmp)->rb_left);  
     39         else if (data->num > this->num)  
     40             tmp = &((*tmp)->rb_right);  
     41         else   
     42             return -1;  
     43     }  
     44 
     45     /* Add new node and rebalance tree. */  
     46     rb_link_node(&data->my_node, parent, tmp);  
     47     rb_insert_color(&data->my_node, root);  
     48 
     49     return 0;  
     50 }  
     51 
     52 
     53 void my_delete(struct rb_root *root, int num)  
     54 {  
     55     struct mytype *data = my_find(root, num);  
     56     if(data != NULL)
     57     {
     58         rb_erase(&data->my_node, root);  
     59         free(data);  
     60     }
     61 }  
     62 
     63 void my_destory(struct rb_root *tree)
     64 {
     65     struct rb_node *node;  
     66 
     67     for(node = rb_first(tree); node; node = rb_next(node))
     68     {
     69         my_delete(tree, rb_entry(node, struct mytype, my_node)->num);
     70     }
     71 }
     72 
     73 void my_printf(struct rb_root *tree)  
     74 {  
     75     struct rb_node *node;  
     76 
     77     for(node = rb_first(tree); node; node = rb_next(node))
     78     {
     79         printf("%d ", rb_entry(node, struct mytype, my_node)->num);  
     80     }
     81 
     82     printf("\n");  
     83 }  
     84 
     85 
     86 #define RBTREE_MAX_NUM 10
     87 
     88 int main(int argc, char *argv[])  
     89 {  
     90     struct mytype *tmp = NULL;
     91     struct rb_root mytree = RB_ROOT; 
     92     
     93     srand((unsigned int)time(NULL));
     94 
     95     unsigned int i = 0;
     96     for(i = 0; i < RBTREE_MAX_NUM; ++i)
     97     {
     98         tmp = malloc(sizeof(struct mytype)); 
     99         if(tmp == NULL)
    100         {
    101             perror("Allocate dynamic memory");
    102             exit(-1);
    103         }
    104         
    105         tmp->num = rand()%100;
    106         
    107         printf("%d ", tmp->num);
    108         
    109         int ret = my_insert(&mytree, tmp);  
    110         if (ret < 0) 
    111         {  
    112             fprintf(stderr, "The %d already exists\n", tmp->num);  
    113             free(tmp);  
    114         }
    115     }
    116     
    117     printf("\n");
    118 
    119     my_printf(&mytree); 
    120     
    121     char buf[10];
    122     
    123     while(1)
    124     {
    125         printf("\n****************************************");
    126         printf("\n* +number to insert :");
    127         printf("\n* -number to delete :");
    128         printf("\n*       q to quit   :");
    129         printf("\n****************************************\n");
    130         
    131         fgets(buf, sizeof(buf), stdin);
    132 
    133         if(buf[0] == 'q')
    134         {
    135             break;
    136         }
    137         else if(buf[0] == '+')
    138         {
    139             tmp = malloc(sizeof(struct mytype)); 
    140             if(tmp == NULL)
    141             {
    142                 perror("Allocate dynamic memory");
    143                 continue;
    144             }
    145             
    146             tmp->num = atoi(&buf[1]);
    147             
    148             int ret = my_insert(&mytree, tmp);  
    149             if (ret < 0) 
    150             {  
    151                 fprintf(stderr, "The %d already exists\n", tmp->num);  
    152                 free(tmp);  
    153             }
    154         }
    155         else if(buf[0] == '-')
    156         {
    157             my_delete(&mytree, atoi(&buf[1])); 
    158         }
    159         else
    160         {
    161             continue;
    162         }
    163         
    164         my_printf(&mytree); 
    165 
    166     }
    167 
    168     my_destory(&mytree);
    169 
    170     return 0;  
    171 }

![复制代码][copycode.gif]

[Link 1]: http://www.cnblogs.com/li-hao/archive/2013/04/16/3024856.html
[copycode.gif]: /images/20220806/fc0163f03bb9438fb8e50254aa2702ea.png