随笔 - 119  文章 - 290  trackbacks - 0

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

常用链接

留言簿(12)

随笔分类

我的博客

搜索

  •  

积分与排名

  • 积分 - 299306
  • 排名 - 84

最新评论

阅读排行榜

从gc_link中发现了node_add,通过记录两块内存对应的id来表达两块内存之间的依赖关系。废话不多说,先看看node_add的实现,更深入一点的接触gc下的数据结构。
1static void
2node_add(int parent,int child)
3{
4    while (!cache_insert(parent,child))    {
5        cache_flush();
6    }

7}
代码很少,而且看起来意思很明了:将内存的parent_id和child_id插入到cache中,如果插入失败的话,就处理cache中的数据,直到插入操作成功为止。
首先,这是一个对cache的操作。其次,向cache中插入数据很可能失败,但是可以通过处理消耗掉cache现有的数据,让插入操作成功。这个cache是怎样一种数据结构啊,看看cache_insert的实现吧。
 1static bool
 2cache_insert(int parent,int child)
 3{
 4    int hash = (parent & CACHE_PARENT_MASK) << CACHE_CHILD_BITS | (child & CACHE_CHILD_MASK) ;
 5    struct cache_node *cn = &E.cache[hash];
 6    E.cache_dirty=true;
 7
 8    if (cn->parent == -1{
 9        cn->parent=parent;
10        cn->child=child;
11        return true;
12    }

13    else if (cn->parent == parent && (cn->child ^ child) == UNSET_MASK) {
14        cn->parent = -1;
15        return true;
16    }

17    return false;
18}
第4、5行,通过parent和child计算出了一个hash,然后利用hash充当索引,从 E.cache中取出一个cache节点。
用一个数组作为cache容器,用两个id计算出来的hash作为索引,这算是一个简单的hash_map吧。

在往下看代码之前,先看下cache_node的定义
struct cache_node {
    
int parent;
    
int child;
}
;
挺简单,如实的记录两个id而已。

现在看cache_insert的第8、9、10、11行,如果节点中的parent_id = -1的话,说明这个节点还没有被使用,可以记录传入的id实参。hash_map用不同的输入计算出来的hash值是很容易相同的,这个hash_map处理同hash插入的方式是插入失败,最简单的处理方式。

再看13、14、15行,那个if判断有点奇怪,不过14行parent_id = -1,像是cache_delete的意思,即从cache中删除一条依赖关系的记录。现在的问题是凭什么知道我传入的两个id要进行的是插入还是删除呢?关键就在
#define UNSET_MASK 0x80000000

(cn
->child ^ child) == UNSET_MASK
根据之前的map_id(),我们了解到id其实是数组索引,所以一定是正数,那最高位的符号位就没有什么意义,于是就被用来当作删除标记了。
cn->child的符号位一定是0,因为是之前插入cache的。如果当前传入的实参child的绝对值等于cn->child,且符号位是1的话,那么他们相异或的结果一定是0x80000000。
所以,如果要删除某个依赖关系,只要执行 child | UNSET_MASK就可以了。

在cache_insert的实现中提到,hash索引所对应的cache_node有可能已经被占用了,因此插入操作会失败。那么cache_flush就负责把整个cache清理,把那些有效的cache节点处理一下,让其进入正确的数据结构中。
有关证据表明,这个cache设计,是优化的结果,作为增加或者删除内存间依赖关系的一个加速器。

明天再讲cache_flush吧。
posted on 2008-09-13 20:20 LOGOS 阅读(1619) 评论(0)  编辑 收藏 引用

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