先說下背景，有同學看了我寫的
yfgc庫的分析，留言問我能不能用c實現一個教學用gc庫，力求簡單，無需優化。這個月實在寫不出blog，正好充數一篇。
相關連接：
http://www.shnenglu.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 閱讀(2968)
評論(6) 編輯 收藏 引用 所屬分類:
垃圾收集