つーさのくーかん

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ばりに再実装しないといけなくて、

それめんどくさいなぁ。

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

「つーさのくーかん」は、ぼくんちのNAS上で動いてるのですが、
プロバイダを変えてからちょこちょこIPアドレスが変わるようになり、
GoogleのWebmasterツールから、サイトにアクセスできない！と怒られては、
手動でDNSレコードを更新していたりということをやっていたのですが、
最近この作業にうんざりしてきていたので、
ようやくValue DomainのDDNSを更新するためのプログラムを作ることにしました。

DNS更新には、自分のグローバルIPが要るのですが、これをどっから取ってくるか。
手っ取り早くどっか外部サイトのサービスを呼ぶ手もあるにはありますが、
やっぱ自宅鯖してるくらいだからその辺は閉じていたいとも思いまして、
UPnPでルータに問い合わせることにしようと思いました。

予てから、UPnPを使って自分のグローバルIPアドレスを得るC#プログラムを公開してましたが*1、
こいつは、Windowsなupnp.dllを使ってる関係で、Linuxでは動かなかったので、
NASが定期的に自分のIPを確認してDDNSに登録することはできなかった。

LinuxでUPnPと言われても門外漢で、
ちょっと調べるとgupnp-toolsとかいうのもあるらしいのですが、
Xなしで動くのかどうかよくわからなかったので、
まぁ、自分で書くことにしました。

https://gist.github.com/ttsuki/7723258

書きました。

VSでexeをビルドして、NASへコピーしました。

nohup mono ValueDomainDDNSUpdator.exe > vdddnsu.log 2>&1 &
echo kill $! > kill-vdddnsu.sh

動きました。

これからは安定して、サイトにアクセスできるようになると思います。

UPnPは、最初にUDP multicastでネットワーク上にいるデバイスを探すのですが、
今回はルータのIPが既知、かつ、変化しないので、その辺はすっ飛ばしました。
って、考えたらコントロールURLも変わらないはずだし、もっと楽できたなぁ……。
反省です。

おわりです。

Windowsには昔からAudioCodecManagerという音声形式を色々扱える系のAPI群があるので、
それをP/InvokeでC#から呼び出してMP3をデコードすることができる。

Windows 95の頃には既に存在した古のAPIであるが、
Windowsの機能を使うので、ライセンス的にも特に怖くないし、
対象プラットフォームがWindowsで、かつ目的がMP3の仕組みを勉強するのでなければ、
これでいいよね。

https://github.com/ttsuki/ttsuki/blob/master/WinMM/AcmMp3Decoder.cs

タイトルの通り、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って変更履歴が全部見えて恥ずかしいω