- 论坛徽章:
- 9
|
BiscuitOS 上轻松使用红黑树
红黑树作为 Linux 内核重要的数据结构，负责 Linux 的基本运作，其重要程度和难易程度让人望而却步。
本节通过一个简单例子介绍红黑树在 BiscuitOS 以及 Linux 内核中的使用方法。
红黑树在 Linux 内核很多地方都有使用，比如进程调度的“完全公平调度”，虚拟空间对进程地址管理以及本章重点例子 vmalloc 内存区的管理。
红黑树由于其复杂的构成，这里不过多讲理论，本章侧重讲述如何使用红黑树。
1. 红黑树 API
rb_link_node 将红黑树节点插入到红黑树。
rb_insert_color 红黑树翻转颜色
rb_erase 从红黑树中移除一个节点
rb_first 获得红黑树的第一个节点
rb_next 获得红黑树节点的下一个节点
2. 红黑树在内核中的使用案例
VMALLOC 分配的虚拟地址通过红黑树进行管理，我们可以通过红黑树的 root 和虚拟地址大小来查找 VMALLOC 区的内容。
代码如下：(源码位置 /BiscuitOS/tools/TestCase_vmalloc.c)- void TestCase_vmalloc(void)
- {
- unsigned int addr;
- struct rb_node *node;
- addr = vmalloc(PAGE_SIZE);
- addr = vmalloc(PAGE_SIZE);
- addr = vmalloc(PAGE_SIZE);
-
- addr = vmalloc(PAGE_SIZE);
-
- /* Trave all node */
- for(node = rb_first(&vmap_area_root) ; node ; node = rb_next(node)) {
- struct vmap_area *va;
- struct vm_struct *area;
- va = rb_entry(node,struct vmap_area,rb_node);
- area = va->private;
- printk(KERN_INFO "VA %p\n",(void *)(unsigned long)va->va_start);
- }
-
- vfree(addr);
- }
(源码位置 /BiscuitOS/tools/TestCase_RB_tree.c)- #include "linux/kernel.h"
- #include "linux/rbtree.h"
- #include "linux/debug.h"
- #include "linux/mm.h"
- #include "linux/gfp.h"
- #include "linux/slab.h"
- struct node {
- struct rb_node node;
- int num;
- };
- /*
- * Insert a node into RBtree.
- */
- int insert(struct node *data,struct rb_root *root)
- {
- struct rb_node **link = &(root->rb_node);
- struct rb_node *parent = NULL;
- while(*link) {
- struct node *node = container_of(*link,struct node,node);
- parent = *link;
- if(data->num < node->num)
- link = &((*link)->rb_left);
- else if(data->num > node->num)
- link = &((*link)->rb_right);
- else
- return -1;
- }
- rb_link_node(&data->node,parent,link);
- rb_insert_color(&data->node,root);
- return 0;
- }
- /*
- * Search a node from RBtree.
- */
- struct node *search(int num,struct rb_root *root)
- {
- struct rb_node *node = root->rb_node;
- while(node) {
- struct node *data = container_of(node,struct node,node);
- if(num < data->num)
- node = node->rb_left;
- else if(num > data->num)
- node = node->rb_right;
- else
- return data;
- }
- return NULL;
- }
- /*
- * Delete a node from RBtree.
- */
- void delete(int num,struct rb_root *root)
- {
- struct node *node = search(num,root);
- if(node) {
- rb_erase(&node->node,root);
- kfree(node);
- } else
- mm_err("%2d doesn't exits\n",num);
- }
- /*
- * Print all node
- */
- void print_all(struct rb_root *root)
- {
- struct rb_node *node;
- for(node = rb_first(root) ; node ; node = rb_next(node))
- mm_debug("%2d ",rb_entry(node,struct node,node)->num);
- mm_debug("\n");
- }
- /*
- * TestCase_RB_user
- */
- void TestCase_RB_user(void)
- {
- struct rb_root root = RB_ROOT;
- struct node *node;
- int num,i,ret;
- int value[30] = { 2 , 84 , 43 , 11 , 7 , 54 , 21 , 1 , 2 , 10 ,
- 34 , 5 , 6 , 45 , 76 , 0 , 12 , 25 , 44 , 11 ,
- 99 , 65 , 38 , 91 , 35 , 16 ,93 , 74 , 33 , 67 };
- num = 30;
- for(i = 0 ; i < num ; i++) {
- node = (struct node *)kmalloc(sizeof(struct node),GFP_KERNEL);
- if(!node) {
- mm_err("No Memory\n");
- /* Never Waste memory */
- for(i-- ; i >= 0 ; i--)
- delete(value[i],&root);
- return;
- }
- node->num = value[i];
- /* Insert node into RBtree */
- ret = insert(node,&root);
- if(ret < 0) {
- mm_err("%2d has existed\n",node->num);
- kfree(node);
- }
- }
- mm_debug("First Check\n");
- print_all(&root);
- /* Delete a node */
- delete(value[4],&root);
- mm_debug("Second Check [%d]\n",value[4]);
- print_all(&root);
- /* Search a node */
- node = search(value[2],&root);
- mm_debug("Find %d\n",node->num);
- /* Get prev node */
- mm_debug("Prev num is %d\n",
- rb_entry(rb_prev(&node->node),struct node,node)->num);
- /* Get next node */
- mm_debug("Next num is %d\n",
- rb_entry(rb_next(&node->node),struct node,node)->num);
- /* The first node */
- mm_debug("Min num is %d\n",
- rb_entry(rb_first(&root),struct node,node)->num);
- /* The last node */
- mm_debug("Max num is %d\n",
- rb_entry(rb_last(&root),struct node,node)->num);
- /* Free All node */
- for(i = 0 ; i < num ; i++)
- delete(value[i],&root);
- mm_debug("Last Check\n");
- print_all(&root);
- }
|
|
免费注册
发表于 2016-03-30 10:17
