つーさのくーかん

tree を作ることを考える。

根があって、任意数の子をとれる。
子も任意数の子をとれる。

汎用的なtreeクラスの節、template class Node 中身; の中身について考える。

どうやったら引き回しやすいか。

まぁ、複数の子っても、たくさんの子を持つか、
あるいはまったく子を持たないかわからないので、
二分木で表現することにする。

思いつくまま定義を書くと、

template<class TValue>
class Node
{
  TValue value;
  Node<T> *parent, *firstChild, *nextSibling;
};

みたいになって、それを実装してみたのが
https://gist.github.com/ttsuki/95ceef4cacdc9c5e0294 なのだけど、
いざ使ってみようと思って、
使う側に回ってからTValueにあたる型を作ってて思ったんだけど、

普通、Treeで何らかの構造を表そうと思ったら、
その要素TValueはデータ構造的にツリーになる前提があるわけで
TValue自身がTValue::ナントカ() が自分の親・兄弟にアクセスできないと、
トラヴァーサルしにくいなーということに後から気づいた。

じゃあ、

class 実際に扱いたい型 : public Node<実際に扱いたい型 *>
{
  ctor()
    : Node(this)
  {
  }
  
};

なら？
にしても、parentは、Node<TValue *>の型であって、
それをTValueとして扱うにはダウンキャストがいるのでなんか気持ち悪い。
って考えてると、

class 実際に扱いたい型
{ 
  Node<実際に扱いたい型 *> link;
  ctor()
    : link(this)
  {
  }
};

になって、マジで？ってなる。

これだと、でもまぁ、これだとキャストなしに、
自分の親ノードを得るのに return link.parent.value; できるので……。

ただ、GetParent() とか、ApplyAllChildren等を
全部pImplばりに再実装しないといけなくて、

それめんどくさいなぁ。

なんか、お約束のレシピはないのかしら。

タイトルの通り、template struct Hoge ; の T を POD に制約したい。

というわけで、 Hoge がインスタンス化されようとするとき
コンパイルエラーを生成できるような、PRECONDITIONAL_ERROR なるものを作ってみた。
STATIC_ASSERTの親戚のような感じで使えるかなー。

今回作ってみたのは、template実体化時にTがPODじゃないとコンパイルエラー。
ついでに、引数に渡された配列の長さがある一定以上ないとコンパイルエラー。

自作コンテナを作るとき、TがPODならコンストラクタもデストラクタも呼ばなくてよいので、
コンテナを clear するときも、for (int i = 0; i < size(); i++) this[i]->~T(); する必要が無いっていう。

以下 gist

続きを読む

独自コンテナ template struct Container のTがPODだと、
メンバ追加時にコンストラクタもデストラクタも呼ばなくてよい。
コンテナを clear するときも、for (int i = 0; i < size(); i++) this[i]->~T(); する必要が無い。

では、型をPODとして定義するにはどうすればいいのかという話だ。

C++11の情報ばかりヒットして、
C++03までのPODについて、いまいちまとまった情報が得られないので、
自分なりに調べた情報をまとめておく。

続きを読む

コピペ用CRC32

#include <stdint.h>
uint32_t ComputeCRC32(void *data, size_t len, uint32_t crc = 0);
uint32_t ComputeCRC32(void *data, size_t len, uint32_t crc)
{
	static uint32_t tbl[256] = { 1 };
	if (tbl[0] == 1) for (uint32_t i = 0; i < 256; i++) { uint32_t c = i; for (int j = 0; j < 8; j++) c = (c & 1) ? (0xEDB88320 ^ (c >> 1)) : (c >> 1); tbl[i] = c; }
	uint32_t c = crc ^ 0xFFFFFFFF;
	for (size_t i = 0; i < len; i++) { c = tbl[(c ^ static_cast<uint8_t*>(data)[i]) & 0xFF] ^ (c >> 8); }
	return c ^ 0xFFFFFFFF;
}

↓おもしろいです
http://codegolf.stackexchange.com/questions/3268/compute-the-crc32-table-at-compile-time

簡単な連続領域のSHA1求めたい。
分割に対応してないのででかいファイルのハッシュ求めるのにはちょっと使えない。

WTFPL or NYSL

つーさゎ、デバッグ用のメモリアロケータを書ぃてゐて、思つた。
標準の_CrtSetDbgFlagナントカカントカはどうも小回りが効かぬ。(というか使い方がよく分からぬ)
ちうか、operator newのoverloadはともかく、置換すんのはやだな……。
C#とかJavaScriptみたいに、関数の呼び出し元アドレスがどこかわかればなー。

かくして、インラインアセンブラの扉は開かれた。ちな、今回の舞台はx86世界な。

実現方法を少し考えてみたら、要は、関数呼び出し時にスタックに積まれてるはずの
リターンアドレス(=関数呼び出しの瞬間のEIPレジスタの値)を変数に読み出して、
それを引数に本命関数を呼び出せればいいんでしょ！　ということなので……

じゃあ

こんなんでどうでしょ？

最初はこれがnewとdeleteのオーバーロードの数だけ並んでいたのだけど、
なんかもうちょっとどうにかならないかと思ってマクロにしたものが

こちらになります！　ってか。

関数の呼び出し元をくすねてcallee変数に入れておいてくれる
proxy関数を作ってくれる小気味よいマクロにしてみたった。
うむ、小気味よい(陶酔)

呼び出す関数の戻り値について、橋渡しするようなコードを書いてないので、
構造体を返すような関数には使えないけど、まぁ十分というか。

かくして、つーさは、プログラムを動かしつつも
未だdeleteされてゐないnewされたブロックのリストを得る魔を得た。

Releaseビルドでも.mapファイルとcalleeを照合すれば、
呼び出し元が分かるという点、時と場を超えた強みとなろう。

めでたし　めでたし。

どちらかというと、C++というよりはx86の寓話であったか。

今回作ってたメモリアロケータ(のラッパ)

双方向リンクドリストをわっかにしておいて、
空になる時の例外処理を書かずに済ますことがマイブーム。
https://gist.github.com/ttsuki/98a60653f398062b15e5

まぁ、最初から、こいつのお世話にならないよう予防策を講じてプログラムを書くのがよい。
というか、普通はそうしてるはずなので、今回の話は思ってたより役に立たなそう。
酒の肴くらいにはなるかの。

Gistって変更履歴が全部見えて恥ずかしいω