12 3 / 3 页下一页

linux内核priority search tree详解--->王者归来，先发一篇狠的 [复制链接]

cluter

稍有积蓄

论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2011-04-24 00:44 |只看该作者 |倒序浏览

本帖最后由 cluter 于 2011-04-24 00:49 编辑

忙了好久，总有有时间看内核，最近研究下了LINUX内核“页面回收”时候采用的PST树算法。

PST是 radix tree和heap tree的综合体。而且LINUX的实现和传统的算法还不一样，甚是花了不少时间啊。废话少说了，先上图。

下面是插入操作：还是先上图再帖代码

struct prio_tree_node *prio_tree_insert(struct prio_tree_root *root,struct prio_tree_node *node)
{
            获取insert_node的radix和heap
get_index(root, node, &radix_index, &heap_index);

            1 如果树是空
         2 要insert_node的heap大于root的maxindex，则要先"扩展"树
if (prio_tree_empty(root) ||heap_index > prio_tree_maxindex(root->index_bits))
return prio_tree_expand(root, node, heap_index);

            从root节点开始比较
cur = root->prio_tree_node;
            获取mask掩码
mask = 1UL << (root->index_bits - 1);

while (mask) {
                              获取cur_node的radix和heap
get_index(root, cur, &r_index, &h_index);

                              如果insert_node已经存在,则直接返回当前node
if (r_index == radix_index && h_index == heap_index)
return cur;

                              1 cur_node->heap < insert_node->heap
                              2 cur_node->heap == insert_node->heap&&cur_node->radix > insert_node->radix，则交互两个节点
                              if (h_index < heap_index ||(h_index == heap_index && r_index > radix_index))
                              {
struct prio_tree_node *tmp = node;

                                             交换insert_node和cur_node
注意：insert_node已经变成cur_node
                                             node = prio_tree_replace(root, cur, node);

                                             让cur指针指向已经插入的node节点
cur = tmp;

/* 交换radix和heap的值*/
index = r_index;
r_index = radix_index;
radix_index = index;
index = h_index;
h_index = heap_index;
heap_index = index;
}

                              获取radix
if (size_flag)
index = heap_index - radix_index;
else
index = radix_index;

                              radix和mask&操作,决定insert_node插入left还是right
if (index & mask)
                              {
                                             如果right==NULL则直接插入,否则继续比较
if (prio_tree_right_empty(cur))
                                             {
INIT_PRIO_TREE_NODE(node);
cur->right = node;
node->parent = cur;
return res;
} else
cur = cur->right;
}
                              else
                              {
                                             如果left==NULL直接插入,否则继续比较
if (prio_tree_left_empty(cur))
                                             {
INIT_PRIO_TREE_NODE(node);
cur->left = node;
node->parent = cur;
return res;
} else
cur = cur->left;
}

                              mask移位，进行下一位的比较操作
mask >>= 1;

if (!mask) {
                                             如果mask已经到了最低位，则开始利用size进行比较
mask = 1UL << (BITS_PER_LONG - 1);
size_flag = 1;
}
}
/* Should not reach here */
BUG();
return NULL;
}

删除操作:

//算法核心:删除一个node,用其heap index比较大的child node来循环替代就OK了。
void prio_tree_remove(struct prio_tree_root *root, struct prio_tree_node *node)
{
struct prio_tree_node *cur;
unsigned long r_index, h_index_right, h_index_left;

cur = node;
//找到叶子结点,找到替换的路径path
while (!prio_tree_left_empty(cur) || !prio_tree_right_empty(cur)) {
if (!prio_tree_left_empty(cur))
get_index(root, cur->left, &r_index, &h_index_left);
else {
cur = cur->right;
continue;
}

if (!prio_tree_right_empty(cur))
get_index(root, cur->right, &r_index, &h_index_right);
else {
cur = cur->left;
continue;
}

/* both h_index_left and h_index_right cannot be 0 */
//找heap_index大的孩子结点
if (h_index_left >= h_index_right)
cur = cur->left;
else
cur = cur->right;
}
//如果当前结点是root,则重新初始化下root node
if (prio_tree_root(cur)) {
BUG_ON(root->prio_tree_node != cur);
__INIT_PRIO_TREE_ROOT(root, root->raw);
return;
}
//删除当前结点
if (cur->parent->right == cur)
cur->parent->right = cur->parent;
else
cur->parent->left = cur->parent;
//循环向上替代parent结点
while (cur != node)
cur = prio_tree_replace(root, cur->parent, cur);
}

扩展操作:

static struct prio_tree_node *prio_tree_expand(struct prio_tree_root *root,struct prio_tree_node *node, unsigned long max_heap_index)
{
struct prio_tree_node *first = NULL, *prev, *last = NULL;

            首先扩展下index_bits，如果不进入while循环，可直接把insert_node当做root节点。
if (max_heap_index > prio_tree_maxindex(root->index_bits))
root->index_bits++;

            核心思想：
         1 循环删除原来的root_node，然后插入到insert_node的left左子树上
         2 如果原来的tree最后还是非空，则把整个树插入到新的树的left左子树上

while (max_heap_index > prio_tree_maxindex(root->index_bits)) {
root->index_bits++;

if (prio_tree_empty(root))
continue;

if (first == NULL) {
first = root->prio_tree_node;
prio_tree_remove(root, root->prio_tree_node);
INIT_PRIO_TREE_NODE(first);
last = first;
} else {
                                             此时last=first，而first是树第一个被删除的root_node
prev = last;

                                             先删除root_node
last = root->prio_tree_node;
prio_tree_remove(root, root->prio_tree_node);

                                             然后把root_node插入prev_node的左子树上
INIT_PRIO_TREE_NODE(last);
prev->left = last;
last->parent = prev;
}
}

INIT_PRIO_TREE_NODE(node);

            【first,last】是原先tree的被删除的跟节点集合,并且以left指针相连
         1 然后first挂在node的left子树上
         2 原来的tree挂在last的left子树上

         操作1
if (first) {
node->left = first;
first->parent = node;
} else
last = node;

         操作2
            如果此时树还是非空的,则把树的剩余部分挂在last的左子树上
if (!prio_tree_empty(root)) {
last->left = root->prio_tree_node;
last->left->parent = last;
}

            更新root节点
root->prio_tree_node = node;
return node;
}

图和代码稍微有点不一样，就是被删除的跟节点先自己用LEFT指针组合成LIST
然后在 NODE->LEFT=LIST.HEAD
      LIST.HEAD->LEFT=remain_TREE