先说下背景,有同学看了我写的
yfgc库的分析,留言问我能不能用c实现一个教学用gc库,力求简单,无需优化。这个月实在写不出blog,正好充数一篇。
相关连接:
http://www.cppblog.com/darkdestiny/archive/2008/09.html
真正能用的gc库我不会写,简单表达问题本质的东西倒还能应付,就写了一下。不过只用c没有容器是不行的,用了stl,相信同学能看明白。
首先还是先说一下基本概念,gc本质就是把你分配出去的内存都记好了,俩俩内存之间的依赖关系都记好了。回收的时候查找依赖关系,将被根节点依赖的内存都标记为不可删除,删除没有被标记的内存即可。
说实话,gc对于c/cpp这种中级语言意义不大,因为你不得不手动修改两块内存之间的依赖关系,这和手动管理内存是没有差别的。你忘了解除依赖关系,等价于忘了释放内存。
gc这种东西,只对于能把指针变量进行特殊编译的编译器,或者基于虚拟机的语言有价值。我用c/cpp的话还是倾向于手动管理内存,不管依赖关系如何复杂,只要所有权内保证唯一就可单点手动释放;对于所有权不唯一的依赖关系,则采用引用计数机制。
话说太多了,贴点代码吧,也许改改就能编译过去。
#define ROOT (void*)NULL
void* gc_malloc(size_t s);
void gc_link(void* parent, void* child);
void gc_unlink(void* parent, void* child);
void gc_collect();
#include <map>
static std::multimap<void*,void*> s_links, s_linkClean;
static std::map<void*,int> s_allPtrs;
static int s_color = 0;
void* gc_malloc(size_t s)
{
void* ptr = ::malloc(s);
s_allPtrs[ptr] = s_color;
return ptr;
}
void gc_link(void* parent, void* child)
{
s_links.insert(std::make_pair(parent,child));
}
void gc_unlink(void* parent, void* child)
{
s_links.erase(std::make_pair(parent, child));
}
void gc_collect()
{
s_color = (s_color+1) % 2;
gc_mark_r(ROOT);
s_links = s_linkClean;
s_linkClean.clear();
auto iter = s_allPtrs.begin();
while(iter!=s_allPtrs.end())
{
auto cur = iter++;
if(cur->second != s_color)
{
::free(cur->first);
s_allPtrs.erase(cur);
}
}
}
void gc_mark_r(void* parent)
{
if(parent!=ROOT && s_allPtrs[parent]==s_color)
{
return;
}
s_allPtrs[parent] = s_color;
auto iter = s_links.lower_bound(parent);
auto end = s_links.upper_bound(parent);
for(; iter!=end; ++iter)
{
s_linkClean.insert(iter);
void* child = iter->second;
gc_mark_r(child);
}
}
int main()
{
void* p1 = gc_malloc(10);
gc_link(ROOT, p1);
void* p2 = gc_malloc(20);
gc_link(p1, p2);
gc_collect();
return 0;
}
yfgc库里的gc_enter/gc_leave是实现在gc_link/gc_unlink上的,算拓展api吧。同学完全可以自己实现的,hint是,为每个函数调用分配一点内存,建立父子函数内存上的依赖关系,函数里分配的临时内存和函数对应的内存也建立依赖关系,函数退出时解除相关的依赖关系。
云风不久前又给出一个基于继承的gc解决方案,很简单,可以看看:
http://blog.codingnow.com/2010/02/cpp_gc.html
posted on 2010-04-29 21:13
LOGOS 阅读(2910)
评论(6) 编辑 收藏 引用 所属分类:
垃圾收集