Chinaunix首页 | 论坛 | 博客
  • 博客访问: 690718
  • 博文数量: 192
  • 博客积分: 1875
  • 博客等级: 上尉
  • 技术积分: 2177
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-23 23:21
个人简介

有时候,就是想窥视一下不知道的东东,因为好奇!

文章分类

全部博文(192)

文章存档

2024年(8)

2023年(3)

2019年(1)

2018年(1)

2017年(2)

2016年(69)

2015年(53)

2014年(14)

2013年(1)

2012年(5)

2011年(25)

2010年(9)

分类: LINUX

2012-03-06 08:55:08

内核中rbtreeAPI简单使用备忘:一个rbtree根,向其中插入结点,遍历之,删除节点,再遍历之。

 

系统环境:ubuntu-10.04/linux-2.6.32-38-generic

 

代码:

  1. #include <linux/init.h>
  2. #include <linux/module.h>
  3. #include <linux/kernel.h>

  4. #include <linux/rbtree.h>

  5. MODULE_LICENSE("GPL");
  6. MODULE_AUTHOR("zl");
  7. MODULE_DESCRIPTION("rbtree test");

  8. struct mytype {
  9.     struct rb_node node;
  10.     char *keystring;
  11. };

  12. struct rb_root mytree = RB_ROOT;

  13. /** Same as binary sort tree**/
  14. struct mytype *my_search(struct rb_root *root, char *string)
  15. {
  16.     struct rb_node *node = root->rb_node;
  17.     while (node) {
  18.         struct mytype *data = container_of(node, struct mytype, node);
  19.         int result;

  20.         result = strcmp(string, data->keystring);

  21.         if (result < 0)
  22.             node = node->rb_left;
  23.         else if (result > 0)
  24.             node = node->rb_right;
  25.         else
  26.             return data;
  27.     }
  28.     return NULL;
  29. }

  30. int my_insert(struct rb_root *root, struct mytype *data)
  31. {
  32.     struct rb_node **new = &(root->rb_node), *parent = NULL;

  33.     /* Figure out where to put new node */
  34.     while (*new) {
  35.         struct mytype *this = container_of(*new, struct mytype, node);
  36.         int result = strcmp(data->keystring, this->keystring);

  37.         parent = *new;
  38.         if (result < 0)
  39.             new = &((*new)->rb_left);
  40.         else if (result > 0)
  41.             new = &((*new)->rb_right);
  42.         else
  43.             return 0;
  44.     }

  45.     /* Add new node and rebalance tree. */
  46.     rb_link_node(&(data->node), parent, new);
  47. #if 1
  48.     rb_insert_color(&(data->node), root);
  49. #endif
  50.     return 1;
  51. }

  52. #if 0
  53. /** remove **/
  54. struct mytype *data = mysearch(mytree, "walrus");

  55. if (data) {
  56.       rb_erase(data->node, mytree);
  57.       myfree(data);
  58. }
  59. #endif

  60. #if 0
  61. void rb_replace_node(struct rb_node *old, struct rb_node *new,
  62.                      struct rb_root *tree);
  63. #endif

  64. #if 0
  65. struct rb_node *rb_first(struct rb_root *tree);
  66. struct rb_node *rb_last(struct rb_root *tree);
  67. struct rb_node *rb_next(struct rb_node *node);
  68. struct rb_node *rb_prev(struct rb_node *node);
  69. #endif

  70. char *array[] = {
  71.     "aaaaa",
  72.     "bbb",
  73.     "333",
  74.     "c",
  75.     "dddd",
  76.     "111",
  77.     "eeeeeeeee",
  78.     "ffffghi",
  79.     "222",
  80.     "gggabcd",
  81.     "12345"
  82.     "abcdefg"
  83. };

  84. #define TAB_SIZE(array) (sizeof(array)/sizeof(array[0]))

  85. static int __init rbtree_init(void)
  86. {
  87.     struct rb_node *node;
  88.     struct mytype *mynode;
  89.     int i;

  90.     for(i = 0; i < TAB_SIZE(array); i++)
  91.     {
  92.         mynode = kmalloc(sizeof(struct mytype), GFP_KERNEL);
  93.         mynode->keystring = (char *)array[i];
  94.         printk("kerstring is %s\n", mynode->keystring);
  95.         my_insert(&mytree, mynode);
  96.     }

  97.     printk("*********** 升序 ****************************\n");
  98.     i = 0;
  99.     for(node = rb_first(&mytree); node; node = rb_next(node))
  100.     {
  101.         printk("i = %d, key = %s\n", i, (rb_entry(node, struct mytype, node))->keystring);
  102.         i++;
  103.     }
  104.     printk("------------降序---------------------------\n");
  105.     i = 0;
  106.     for(node = rb_last(&mytree); node; node = rb_prev(node))
  107.     {
  108.         printk("i = %d, key = %s\n", i, (rb_entry(node, struct mytype, node))->keystring);
  109.         i++;
  110.     }

  111.     printk("------------删除后升序---------------------------\n");
  112.     mynode = my_search(&mytree, "eeeeeeeee");
  113.     if(mynode)
  114.     {
  115.         rb_erase(&(mynode->node), &mytree);
  116.         kfree(mynode);
  117.         printk("Erased eeeeeeeee node !\n");
  118.     }

  119.     for(node = rb_first(&mytree); node; node = rb_next(node))
  120.     {
  121.         printk("i = %d, key = %s\n", i, (rb_entry(node, struct mytype, node))->keystring);
  122.         i++;
  123.     }

  124.     return 0;
  125. }

  126. static void __exit rbtree_exit(void)
  127. {
  128.     printk("exit !\n");
  129. }

  130. module_init(rbtree_init);
  131. module_exit(rbtree_exit);
 
Makefile:
  1. obj-m = myrbtree.o
  2. #KERNELS = /media/STUDY/linux/kernel/my2440-2.6.36
  3. KERNELS = /lib/modules/$(shell uname -r)/build/
  4. default:
  5. make -C $(KERNELS) M=$(shell pwd) modules
  6. .PHONY:clean
  7. clean:
  8. make -C $(KERNELS) M=$(shell pwd) clean

编译,运行,及查看运行结果:符合预期

make clean;make;sudo rmmod myrbtree;sudo insmod myrbtree.ko ;dmesg


阅读(3801) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~