2度目のテスト(→1度目)。
今度はGC本見たからすっきりしたはず。
GC対象となるオブジェクトのベースクラス:
class GCObject { GCObject* next; bool mark_bit : 1; public: GCObject() { } virtual ~GCObject() { } virtual void mark() { this->mark_bit = true; } protected: bool marked() { return mark_bit; } friend class MarkSweepGC; };
|
作られたオブジェクトはスイープフェーズですべてをたどるために、単方向リストでつなぐためのメンバnext
と、マークビットのメンバmark_bit
を持つ。
継承するオブジェクトが内部にGCObject
を指すメンバを持つ場合は mark()
メソッドをオーバーライドしてそれらもマークするようにする。
構造体のサイズはvtbl(4)+next(4)+mark_bit(4) = 12
。
デカい…。
mark_bit
はnext
の下位1ビットに埋め込むとかいうハックをすれば8バイトに減らせる。
オブジェクトを管理し、マークスイープGCするクラス:
class MarkSweepGC { GCObject* chain; public: MarkSweepGC() : chain(NULL) { } void collect_garbage() { this->mark_phase(); this->sweep_phase(); } protected: GCObject* alloc_object(size_t size) { GCObject* p = static_cast<GCObject*>(malloc(size)); if (p == NULL) { this->collect_garbage(); p = static_cast<GCObject*>(malloc(size)); if (p == NULL) { error_exit("Out of memory"); } } p->mark_bit = false; p->next = this->chain; this->chain = p; return p; } void free_object(GCObject* p) { free(p); }
virtual void mark_phase() = 0; void sweep_phase() { GCObject* prev = NULL; for (GCObject* p = this->chain; p != NULL; ) { if (p->mark_bit) { p->mark_bit = false; prev = p; p = p->next; } else { GCObject* next = p->next; if (prev == NULL) this->chain = next; else prev->next = next; p->~GCObject(); free_object(p); p = next; } } } };
|
GCするオブジェクトは alloc_object()
メソッドで確保する。
そのため直接new
は呼ばずに、確保したメモリ領域にplacement newでコンストラクタを呼び出す。
作られたオブジェクトはすべてchainにつながれる。
GCの開始にはcollect_garbage()
を呼びだすか、allocate_object()
内でメモリ確保に失敗すると呼び出される。
mark_phase()
は継承先で独自に実装して、ルートからたどれるGCObject
をマークする必要がある。
sweep_phase()
は共通で、全オブジェクトを順にたどっていって、マークされてたら削除しないでマークをはずし、マークされてなかたら削除する。
placement newを使って確保したオブジェクトなので、直接delete
は呼ばない。
使用のテスト:GCObject
とMarkSweepGC
を継承して
class Value : public GCObject { Value* child; public: Value() : GCObject(), child(NULL) { } virtual void mark() { if (this->child != NULL) this->child->mark(); } };
class Context : public MarkSweepGC { map<const string, Value*> buf; public: void alloc(const string& key) { Value* p = new(alloc_object(sizeof(*p))) Value(); this->buf[key] = p; } void remove(const string& key) { this->buf.erase(this->buf.find(key)); } virtual void mark_phase() { struct Functor { void operator ()(map<string, Value*>::value_type& e) { if (e.second != NULL) e.second->mark(); } }; for_each(this->buf.begin(), this->buf.end(), Functor()); } };
|