随笔 - 119  文章 - 290  trackbacks - 0

博客搬家了哦,请移步
叫我abc

常用链接

留言簿(12)

随笔分类

我的博客

搜索

  •  

积分与排名

  • 积分 - 299306
  • 排名 - 84

最新评论

阅读排行榜

接着昨天的cache_flush,首先进入以此开头的这个代码块
        if (children) {
            
while (j<children->number) {
这个代码块主要是处理一些取消内存关系的cache节点,并预估需要重新分配的children大小。这里有一个先决条件是,cache是按child_id升序排序的,同样children也是升序排序的。

                if (child == (children->children[j] | UNSET_MASK)) {
                    
--k;
                    head
->parent=-1;
                    
--sz;
                    
++head;
                }
从上面可以看出,如果是取消内存关系的cache节点,之前统计的cache节点数量sz就要减一。估计有些人会纳闷为什么还要减一,毕竟当初统计节点数量的时候,就没有把UNSET_MASK的cache节点算进去。这是因为sz的作用并不是用来表示节点的数量,而是表示children需要拓展的尺寸,由于标记UNSET_MASK的child要从children中删除,那么children数组中就有空闲的位置,所以需要拓展的尺寸也就减少,sz就减一了。

再看
                if (head>=next) {
                    
goto copy_next;
                }
如果cache中的所有节点都是UNSET_MASK的话,就会跳到copy_next处,移动children的其他部分来填充被删除的那些child_id。copy_next的代码我就不贴了。

                else if ((child & ~UNSET_MASK) < children->children[j]) {
                    
break;
                }
如果进入这个判断,则说明cache中不全是UNSET_MASK节点,还包含添加新关系的节点存在。虽然这个判断不直观,但是鉴于他们都是升序排序的,这样的判断也就行得通了。

进入下面的代码,就是利用上面计算出来的sz拓展children的时候了。
        if (sz>0{
            children
=node->u.n.children=link_expand(node->u.n.children,sz);
            assert(children);
            memmove(children
->children + j + sz, children->children +j , (children->number - j) * sizeof(int));
            j
+=sz;
        }
其中的link_expand就是拓展数组的地方,里面的实现基本上就是realloc,策略不同而已。
拓展之后,用移动内存的方式,在children数组中留个空缺,容纳还没有处理的cache节点。空缺要留得足够大,搞不好剩下的cache节点都是添加的。

接下来有再进入一个代码块
while(j<children->number) {
这个while循环和上面讲述的有点像,不过其任务不再是计算需要拓展的空间。
第1个if,仍旧是从children中删除关系的。但是第2个if,则不再是一个break了
            else if ((child & ~UNSET_MASK) < children->children[j]) {
                assert(child 
>= 0 );
                children
->children[k]=child;
                head
->parent=-1;
                
++head;
                
--j;
            }
新添加的child_id,放到刚才拓展children时腾出来的空间中去,并保持children升序排序,这一点很重要。

剩下的代码就没什么了,就是复制child_id到children中,无论child_id来自children还是cache,总之要保证他们升序排序。

看起来,cache_flush是看完了。但是仍旧觉得这个函数无比烂,有太多的地方,需要用人类有限的处理能力去进行分析和维护。
明天,是应该看看之前那些暂时略过不看的代码了。到这里为止,只是跟着程序一条分支看看而已,还有其他分支呢。
posted on 2008-09-16 21:41 LOGOS 阅读(1699) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理