先說(shuō)下背景，有同學(xué)看了我寫(xiě)的
yfgc庫(kù)的分析，留言問(wèn)我能不能用c實(shí)現(xiàn)一個(gè)教學(xué)用gc庫(kù)，力求簡(jiǎn)單，無(wú)需優(yōu)化。這個(gè)月實(shí)在寫(xiě)不出blog，正好充數(shù)一篇。
相關(guān)連接：
http://www.shnenglu.com/darkdestiny/archive/2008/09.html
真正能用的gc庫(kù)我不會(huì)寫(xiě)，簡(jiǎn)單表達(dá)問(wèn)題本質(zhì)的東西倒還能應(yīng)付，就寫(xiě)了一下。不過(guò)只用c沒(méi)有容器是不行的，用了stl，相信同學(xué)能看明白。
首先還是先說(shuō)一下基本概念，gc本質(zhì)就是把你分配出去的內(nèi)存都記好了，倆倆內(nèi)存之間的依賴(lài)關(guān)系都記好了。回收的時(shí)候查找依賴(lài)關(guān)系，將被根節(jié)點(diǎn)依賴(lài)的內(nèi)存都標(biāo)記為不可刪除，刪除沒(méi)有被標(biāo)記的內(nèi)存即可。
說(shuō)實(shí)話(huà)，gc對(duì)于c/cpp這種中級(jí)語(yǔ)言意義不大，因?yàn)槟悴坏貌皇謩?dòng)修改兩塊內(nèi)存之間的依賴(lài)關(guān)系，這和手動(dòng)管理內(nèi)存是沒(méi)有差別的。你忘了解除依賴(lài)關(guān)系，等價(jià)于忘了釋放內(nèi)存。
gc這種東西，只對(duì)于能把指針變量進(jìn)行特殊編譯的編譯器，或者基于虛擬機(jī)的語(yǔ)言有價(jià)值。我用c/cpp的話(huà)還是傾向于手動(dòng)管理內(nèi)存，不管依賴(lài)關(guān)系如何復(fù)雜，只要所有權(quán)內(nèi)保證唯一就可單點(diǎn)手動(dòng)釋放；對(duì)于所有權(quán)不唯一的依賴(lài)關(guān)系，則采用引用計(jì)數(shù)機(jī)制。
話(huà)說(shuō)太多了，貼點(diǎn)代碼吧，也許改改就能編譯過(guò)去。
#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庫(kù)里的gc_enter/gc_leave是實(shí)現(xiàn)在gc_link/gc_unlink上的，算拓展api吧。同學(xué)完全可以自己實(shí)現(xiàn)的，hint是，為每個(gè)函數(shù)調(diào)用分配一點(diǎn)內(nèi)存，建立父子函數(shù)內(nèi)存上的依賴(lài)關(guān)系，函數(shù)里分配的臨時(shí)內(nèi)存和函數(shù)對(duì)應(yīng)的內(nèi)存也建立依賴(lài)關(guān)系，函數(shù)退出時(shí)解除相關(guān)的依賴(lài)關(guān)系。
云風(fēng)不久前又給出一個(gè)基于繼承的gc解決方案，很簡(jiǎn)單，可以看看：
http://blog.codingnow.com/2010/02/cpp_gc.html
posted on 2010-04-29 21:13
LOGOS 閱讀(2942)
評(píng)論(6) 編輯 收藏 引用 所屬分類(lèi):
垃圾收集