超賢いポインタ (後編)
- 本題
循環参照を解決できるポインタを作るには
どのようにすればよいのか。
一般的なGCで残すべきオブジェクトを決めるとき、
ルートからポインタをたどっていって、到達できるものを残すというようにする。
逆に考えると、
削除すべきオブジェクトとは、それをポイントするすべてのオブジェクトが
削除すべきオブジェクトである場合である。
上からも分かるように、どこからもポイントされていないオブジェクトは
削除可能である(参照カウント方式だと、これがカウンタが0になった状態か)。
残すべきオブジェクトからポイントされていればこれまた
自明に削除してはいけないオブジェクトなのである。
そういうわけで、アルゴリズムとしてはこれだけなのだが、
これを実現するにはとあるオブジェクトをポイントしている
オブジェクトを知っている必要がある。
つまり、オブジェクトをポイントしているスマートポインタを
所有するオブジェクト、がわかる必要がある。
オブジェクトをポイントしているスマートポインタは簡単に管理することが出来る。
しかし、それがどのオブジェクトに所有されているかは、
個々のデータ構造によるものなので一般的には解決不可能である。
ではどうするか。ここでは非常に強引にメモリをスキャンして
スマートポインタを検索することにした。
(半ば反則技か…他の環境で動くかどうかわからんし)
スマートポインタは(高確率で…)識別できるようにシグニチャを持つことにした。
これで、"とあるオブジェクトが所有するスマートポインタの列挙"が可能である。
スマートポインタがどのオブジェクトに所有されているかであるが、
これはオブジェクトが所有するスマートポインタをたどってとあるノードから
到達可能なオブジェクトを集めて、それを用いて算出できる。
到達不能なオブジェクトが所有するスマートポインタからポイントされている
ケースもあるが、この場合は、そのオブジェクトは削除してはいけない
ノード扱いなので、特に問題になるわけではない。
これで一応実装できるような感じである。
実装は以下の通り。
class base_gptr;
template <class T>
class genius_ptr;
class base_gobj{
public:
virtual ~base_gobj() {}
set<base_gptr*> parent;
};
template <class T>
class gobj : public base_gobj {
public:
gobj(T *p) :p(p) {}
~gobj() { delete p; }
void incr(base_gptr *bp) { parent.insert(bp); }
void decr(base_gptr *bp){
parent.erase(bp);
if (p!=NULL&&can_erase())
erase();
if (parent.empty())
delete this;
}
void erase(){
T *q=p;
p=NULL;
delete q; // これが死んだら、pが持ってるスマートポインタもデストラクトされるはず…
}
bool can_erase(){
if (parent.empty())
return true;
// 準備。スマートポインタ→gobjなマップを作成する。
set<base_gptr*> ptrs;
collect_ptrs(*parent.begin(),ptrs);
// map<base_gptr*,base_gobj*> ...
map<void*,void*> tbl;
for (set<base_gptr*>::iterator p=ptrs.begin();p!=ptrs.end();p++){
vector<base_gptr*> c=(*p)->children();
for (int i=0;i<(int)c.size();i++)
tbl[c[i]]=(*p)->get_gobj();
}
// 消しても良いものか、探索を行う。
// 自分が指されているノード全てが削除可能ノードな場合は削除してよい、
// ということを再帰的に計算する
set<void*> hist;
return search(this,tbl,hist);
}
bool search(base_gobj *p,map<void*,void*> &m,set<void*> &hist){
if (hist.count((void*)p)!=0)
return true;
hist.insert((void*)p);
for (set<base_gptr*>::iterator it=p->parent.begin();it!=p->parent.end();it++){
if (m.count((void*)*it)==0)
return false;
if (!search((base_gobj*)m[(void*)*it],m,hist))
return false;
}
hist.erase((void*)p);
return true;
}
void collect_ptrs(base_gptr *p,set<base_gptr*> &ptrs){
if (ptrs.count(p)!=0) return;
ptrs.insert(p);
vector<base_gptr*> next=p->children();
for (int i=0;i<(int)next.size();i++)
collect_ptrs(next[i],ptrs);
}
T *get() { return p; }
private:
T *p;
};
#define GENIUS_CODE 0xabcdfedc
class base_gptr{
public:
virtual ~base_gptr() {}
virtual vector<base_gptr*> children()=0;
bool is_valid() { return code==GENIUS_CODE; }
int get_code() { return code; }
void *get_gobj() { return go; }
protected:
int code;
void *go;
};
template <class T>
class genius_ptr : public base_gptr {
public:
genius_ptr(){
code=GENIUS_CODE;
g=NULL;
go=NULL;
}
genius_ptr(T *p){
code=GENIUS_CODE;
g=new gobj<T>(p);
go=g;
g->incr(this);
}
~genius_ptr(){
if (g)
g->decr(this);
}
genius_ptr<T> &operator=(const genius_ptr<T> &r){
if (g) g->decr(this);
g=r.g;
go=g;
if (g) g->incr(this);
return *this;
}
T &operator *() { if (g==NULL) throw "nullp_exc"; return *g->get(); }
T *operator->() { if (g==NULL) throw "nullp_exc"; return g->get(); }
vector<base_gptr*> children(){
if (g==NULL) return vector<base_gptr*>();
char *p=(char*)g->get();
vector<base_gptr*> ret;
if (p!=NULL){
for (int i=0;i<sizeof(T);i++){
try{
base_gptr *bp=(base_gptr*)(p+i);
if (bp->is_valid())
ret.push_back(bp);
}catch(...){}
}
}
return ret;
}
private:
gobj<T> *g;
};長い。そのうえ微妙に怪しげな技法が…。
一応、名前は超賢いポインタということでgenius_ptrということに…(つっこみは無しで)。
基本的に参照カウント方式のカウンタを参照しているスマートポインタの
リストを持つことでグラフ構造をたどれるようにしている。
参照関係が変化したとき(要するにスマートポインタがデストラクトされるとき)
そのオブジェクトが破壊可能かを頑張って調べている。
毎回グラフを探索しているのでたぶん規模が大きくなってくると非常に重くなる。
(大きくならなくてもそのコストは参照カウンタの比ではないけども…)
ちなみにこの決定はDPアルゴリズムが存在するが(というか、メモライズするだけか)、
テーブルを用意するのが面倒だったので、上の実装ではNPな感じになっている。
実装も適当なので間違っても実用しないよう…。
以下はテストコード。
class gaa;
class gbb;
class gaa{
public:
gaa() {}
~gaa(){ cout<<"gaa死す"<<endl; }
genius_ptr<gbb> p;
};
class gbb{
public:
gbb() {}
~gbb(){ cout<<"gbb死す"<<endl; }
genius_ptr<gaa> p,q;
};まずはクラスの定義。
昨日のと大体同じ。
void f4()
{
genius_ptr<gaa> pa(new gaa());
genius_ptr<gbb> pb(new gbb());
}これは単に孤独なスマートポインタ。
普通にデストラクトされるはず。
void f5()
{
genius_ptr<gaa> pa(new gaa());
genius_ptr<gbb> pb(new gbb());
pa->p=pb;
pb->p=pa;
}循環参照。これがちゃんと消えてくれよ。
genius_ptr<gaa> gl_a;
void f6()
{
genius_ptr<gaa> pa(new gaa());
genius_ptr<gbb> pb(new gbb());
pa->p=pb;
pb->p=pa;
gl_a=pa;
}リングごとどっかに保持。消えちゃだめ。
void f7()
{
genius_ptr<gaa> pa(new gaa());
pa->p=genius_ptr<gbb>(new gbb());
pa=genius_ptr<gaa>();
// ↑ここで死ぬはず
cout<<"もう死んでますか?"<<endl;
}途中で死ぬはず、なコード。
int main()
{
cout<<"** 普通のスマートポインタ。循環参照なし"<<endl;
f1();
cout<<"** 普通のスマートポインタ。循環参照あり"<<endl;
f2();
cout<<"** 普通のスマートポインタ。循環参照を作った後、循環参照を壊してある"<<endl;
f3();
cout<<"** 頑張ってるスマートポインタ。循環参照なし"<<endl;
f4();
cout<<"** 頑張ってるスマートポインタ。循環参照あり"<<endl;
f5();
cout<<"** 頑張ってるスマートポインタ。循環参照があるけど消したら駄目なケース"<<endl;
f6();
cout<<"** 頑張ってるスマートポインタ。循環参照その2"<<endl;
f7();
cout<<"** 終わり"<<endl;
return 0;
}これで昨日のやつとまとめてテストしてみた。
** 普通のスマートポインタ。循環参照なし bb死す aa死す ** 普通のスマートポインタ。循環参照あり ** 普通のスマートポインタ。循環参照を作った後、循環参照を壊してある bb死す aa死す ** 頑張ってるスマートポインタ。循環参照なし gbb死す gaa死す ** 頑張ってるスマートポインタ。循環参照あり gaa死す gbb死す ** 頑張ってるスマートポインタ。循環参照があるけど消したら駄目なケース ** 頑張ってるスマートポインタ。循環参照その2 gaa死す gbb死す もう死んでますか? ** 終わり gaa死す gbb死す
普通のスマートポインタでは循環参照が削除できていないのと、
ジーニアスポインタでは循環参照を削除できているのと、
消したら駄目なケースではちゃんと消えていないのと、
消したら駄目なやつがプログラムの終わりでちゃんと消されているのに注目。
それではこんなところで。
