- 論壇徽章:
- 9
|
BiscuitOS 上輕松使用紅黑樹(shù)
紅黑樹(shù)作為 Linux 內(nèi)核重要的數(shù)據(jù)結(jié)構(gòu)，負(fù)責(zé) Linux 的基本運(yùn)作，其重要程度和難易程度讓人望而卻步。
本節(jié)通過(guò)一個(gè)簡(jiǎn)單例子介紹紅黑樹(shù)在 BiscuitOS 以及 Linux 內(nèi)核中的使用方法。
紅黑樹(shù)在 Linux 內(nèi)核很多地方都有使用，比如進(jìn)程調(diào)度的“完全公平調(diào)度”，虛擬空間對(duì)進(jìn)程地址管理以及本章重點(diǎn)例子 vmalloc 內(nèi)存區(qū)的管理。
紅黑樹(shù)由于其復(fù)雜的構(gòu)成，這里不過(guò)多講理論，本章側(cè)重講述如何使用紅黑樹(shù)。
1. 紅黑樹(shù) API
rb_link_node 將紅黑樹(shù)節(jié)點(diǎn)插入到紅黑樹(shù)。
rb_insert_color 紅黑樹(shù)翻轉(zhuǎn)顏色
rb_erase 從紅黑樹(shù)中移除一個(gè)節(jié)點(diǎn)
rb_first 獲得紅黑樹(shù)的第一個(gè)節(jié)點(diǎn)
rb_next 獲得紅黑樹(shù)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
2. 紅黑樹(shù)在內(nèi)核中的使用案例
VMALLOC 分配的虛擬地址通過(guò)紅黑樹(shù)進(jìn)行管理，我們可以通過(guò)紅黑樹(shù)的 root 和虛擬地址大小來(lái)查找 VMALLOC 區(qū)的內(nèi)容。
代碼如下：(源碼位置 /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);
- }
|
|
免費(fèi)注冊(cè)
念章.png "2016科比退役紀(jì)念章
日期:2016-07-28 17:42:52")
發(fā)表于 2016-03-30 10:17
