Home > C言語 Archive

C言語 Archive

VC++でメモリリークを発見する

やっぱり肩こりはいやだ・・・。

VCを用いている場合、crtdbg.hを使えば簡単にCやC++のメモリリークを発見することができる。
(以上既報)

やり方は簡単です。


#define _CRTDBG_MAP_ALLOC
#include <crtdbg.h>

ってな感じでヘッダをインクルードして、main関数の冒頭で


_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF); 

を実行すればよろしい。あとはデバッグ実行するだけ。プログラム終了後、出力ウインドウにリークしている箇所が表示されます。
#includeの前_CRTDBG_MAP_ALLOCを定義しておけば該当ソースファイル名もわかります。
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF); の引数はなんだか忘れちゃったので、各々調べてください。

とまあ、こんな感じですが、なんかcrtdbg.hは頭悪いらしく、C++でクラスとかを使ってると上記のままだとリークしている箇所が正しく表示されません。
以下のようにするとOKです。


#include <stdio.h>
#include <stdlib.h>

#define _CRTDBG_MAP_ALLOC
#include <crtdbg.h>                // 最後にインクルードしたほうがいい気がする。C++の場合。標準ヘッダの中にnewとかあると変になる??
#ifdef _DEBUG
#define new new(_NORMAL_BLOCK,__FILE__,__LINE__)     // これが重要
#endif

int main(void)
{
   char *aznable;

   _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);

   aznable = (char *)malloc(3*sizeof(char));

   return 0;
}

newを再定義するのが重要です。正しくリーク位置を取得するためには、すべてのファイルでcrtdbg.hをインクルードする必要があり、newの再定義も必要になるので、


#ifndef MEMORY_LEAK_H
#define MEMORY_LEAK_H
#define _CRTDBG_MAP_ALLOC
#include <crtdbg.h>
#ifdef _DEBUG
#define new new(_NORMAL_BLOCK,__FILE__,__LINE__)
#endif
#endif

みたいなmemory_leak.hを作ってこいつをみんなでインクルードしようぜ!って感じにするといいかもしんない。

参考文献 http://support.microsoft.com/kb/140858/ja

以上

キャストでミスアラインメント

組み込みとかはミスアラインメントがやばい。


int a;
char *b;

b = (char *)&a;

これはやばい。intからcharへのキャストはミスアラインメントが起こる可能性がある。逆は特に問題ない(気がする)。
実はよく知らないんだけども、たぶんintで定義すると4バイトのレジスタに格納されて、それが1バイト単位でアクセスできない場合はミスアラインメントが起こるということじゃないかなぁ。PCだと大丈夫だったりするから性質が悪い。

という、漠然としたあまり意味があるとは思えないメモ。

乱数のメモ

ある範囲の乱数を作成する場合、PHPならメルセンスツイスターというアルゴリズムを利用したmt_rand()を使えるので困らない。たぶん。

しかし、Cだと困る。例えば0~100の乱数を作りたい場合、


int num;
num = rand()%100;

ってやりたくなるが、これだと乱数とは思えない数字が生成される。
特に0~1としてみたら、そのひどさがわかる。


for (i = 0; i < 100; i++) {
    num = rand()%2;
    print("%d\\n", num);
}

たぶん、0と1が交互に出るんじゃないかと思う。
で、どうしたらいいかというと、もっとちゃんとした乱数発生アルゴリズム、つまりメルセンスツイスターを使えばいい。
ということになりますが、そこまでたいそうな話じゃない場合、簡単な変換式で対応できます。
このページ
がとっても参考になるんですが、いつもググって見つけてるのでメモしておいた次第です。
以下のような式です(こぴぺ)。


num = (int)((double)rand() / ((double)RAND_MAX + 1) * N);

あるいは


num = rand() / (RAND_MAX / N + 1);

Nは整数で、上記の例の10とか2。RAND_MAXは乱数の最大値。たぶん定義されてると思う。

以上

インクリメントはインプリメント依存

o-taki氏からのタレコミです。
まずはC言語。
問題のコードは下記です。


#include <stdio.h>

int main(int argc, int *argv[]){
    int a[2][2] = {{6,8},{100,120}};    // ①
    int *t = *a;        // ②
    int **l = &t-1;    // ③

    printf("%d\n",++*++*++l*++*++*l++);   // ④
    
    return 0;
}

まあ、②、③のあたりでやや意味不明ですが、要はlはtのアドレスの一個手前だからaの一個手前、つまり何もないところ指してる。多分、直接**lにアクセスすると怒られると思われます。

④の所を解析すると、演算子の優先順位を考えると


++*++*++l*++*++*l++

= ++*++(*(++l)) * ++*++(*(l++))

= (++(*(++(*(++l))))) * (++(*(++(*(l++)))))

= (++(*(++(*(++l))))) * (++(*(++(*(l++)))))      //  ⑤

になるんじゃないかと思います。ややこしいことは間違いないですが、問題は「後置インクリメントがどのタイミングで評価されるのか」ということに集約されると思います。
まず、⑤の最初の大きな括弧


(++(*(++(*(++l)))))   // ⑤-i

が最終的にどこを指しているか考えます。a[][]のメモリ領域を便宜的に下記の表現すると、


Z.a:0   Z.b:0
A.a:6   A.b:8
B.a:100  B.b:120

初期状態でlはZ(=Z.a)を指しています。順を追うと、


(++l) => A (=A.a)
(*(++l)) => A.a
(++(*(++l))) => A.b   // ⑥
</code></pre>
したがって最後の
<pre><code>
(++(*(++(*(++l)))))

でA.bの値が8から9に変更されます。
注意すべきは、最後の時点でlが指している先はA.bです。(多分)
⑥のインクリメントは*lに対するインクリメントですが、*lもlも一緒な気がします。

で、⑤の二つめの大きな括弧(これが問題)


(++(*(++(*(l++)))))     // ⑤-ii

も同様に考えると


(l++) => A (=A.b)   // ⑦
(*(++l)) => A.b
(++(*(++l))) => B.a

というわけで、⑦は後置のため、参照される段階ではまだインクリメントされません。(多分)
したがって最後の


(++(*(++(*(l++))))) 

でB.aの値が100から101に変更されます。

ということは、④=⑤=


(++(*(++(*(++l))))) * (++(*(++(*(l++))))) 

は9*101=909になります。
といいたいところなんですけど、コンパイラの実装依存ぽい感があります。まあ、上の解析が間違っている可能性も大ですが、最初のmainをコンパイルして実行すると、
・cygwin gcc ⇒ 909
・cygwin g++ ⇒ 909
・VC6 ⇒ 909
・VC2005 ⇒ 10201
謎です。VC2005。
これを解釈するには、二項演算子*は最後に評価されるため、前半の括弧(⑤-i)と後半の括弧(⑤-ii)の前置インクリメントが評価された後のlを考えれば、説明が付くような、付かないような・・・。

次にPerl。
超単純な次のコード。


$i = 1;

print ++$i + $i++;
print "\n";

$i = 1;
print $i++ + ++$i;
print "\n";

$i = 1;
print $i++ + $i++;

最初の出力は後置インクリメントなわけですから、2+2=4と表示されると思われたんですが結果は5。謎。
上記結果は下記のようになります。


5
4
3

全く謎。

Cでやると


 i = 1;
 printf("%d\n", ++i + i++);

 i = 1;
 printf("%d\n", i++ + ++i);

 i = 1;
 printf("%d\n", i++ + i++);

もちろん結果は


4
4
2

よって、結論!
インクリメントは使ってはならない。ルビーのように。

追記:2009-04-27
匿名さんのコメントより
>少なくともC/C++言語仕様上、副作用完了点の前に同じ変数を複数回変更した結果は「未定義(undefined)」です。
ということらしいです。他の言語についてまだ調べてませんが、言語使用上は動作を規定する義務はないので、どうなろうが知ったこっちゃないという。そうだったのか・・・。
まあ結論は同じで、そんな変なインクリメントをするなってことだと思います。

以上

バイナリサーチ

バイナリサーチ(2分探索)ってのがあります。ソートされたデータから高速に値を検索できます。O(log(N))です。
Cでも標準ライブラリ的にあるし、JavaでもArraysクラスにあったりするわけです。
が、これらのバイナリサーチって同じ値がデータ中に複数あるときその中のどれが選ばれるかは保証されていないそうです。
順序(インデックス)自体に、意味がある場合、それじゃ困るという場合もあります。
横着プログラミングで取り上げられている例とか。
同じ値のものが複数ある場合は、一番最初に現れるインデックスを探して欲しいと思うわけです。
で、結局のところ、ここにあげられているbsearch_first()を使えばいいわけですが、
ソースを見ても普通のバイナリサーチとどう違うのか、一見してわからなかったり、自分で実装してみたら端点で挙動がおかしかったり、無限ループになったりとかなりはまったので、メモします。

まず、普通のバイナリサーチは次のようになります。
(検索対象配列をarray[]、検索する値をsearchValue、比較関数をcompareとし、戻り値は-1のときNotFound、それ以外のとき見つかったインデックスとします。)


foundIndex = -1;
while(low <= high) {
   middle = (low + high) >> 1;   /* いわゆる(low+high)/2 */
   compareResult = compare(array[middle], searchValue); /* いわゆるarray[middle] - searchValue。 */
   /* array[]の中身が数値ならただの引き算で。 */

   if (0 == compareResult) { /* 真ん中の値が検索値と等しい */
       foundIndex = middle;
       break;
   } else if (0 > compareResult) { /* 真ん中の値が検索値より小さい */
       low = middle + 1; /* 上へ */
   } else { /* 真ん中の値が検索値より大きい */
       high = middle - 1; /* 下へ */
   }
}

return foundIndex;

で、本題の最初のインデックスを取ってくるにはどうしたらいいか。多分以下です。

 
/* first探索 */
foundIndex = -1;
while(low < high) {   /* <=にすると無限ループ */
    middle = (low + high) >> 1;        /* 切り捨て。下へ移動するように。 */
    compareResult = compare(array[middle], searchValue);

    if (compareResult < 0) { /* 真ん中の値が検索値より小さい */
        low = middle + 1;
   } else if (compareResult == 0) {/* 真ん中の値が検索値と等しい */
      foundIndex = middle;
      high = middle; /* highがcompareResult==0であることを保証する */
  } else { /* 真ん中の値が検索値より大きい */
      high = middle - 1; /* 下へ */
  }
}

if (foundIndex == -1 && 0 == compare(array[high], searchValue)) {
    foundIndex = high;
}

return foundIndex;

最終的にhighに入っている値をインデックスとして返しているわけですが、==0になってもループを抜けずにギリギリのhighを探してくるというのがミソです(多分)。
whileの判定を(low <= high)とすると、例えばlow=25、high=26、array[25]==searchvalueみたいな状況で無限ループになります。つぎで high=25となって、延々そのままです。オリジナルのバイナリサーチと違って、highの値がmiddleのままになるため、探索領域が変化しなくなります。
また、最後のifでチェックしているのは、while()の条件で=を取ったことにより、最後にhighに格納されているインデックスが調べられていない可能性があるためです。

最後のインデックスを検索するやつは、面倒なのでコードだけ。


/* last探索 */
foundIndex = -1;
while(low < high) {
    middle = (low + high + 1) >> 1;        /* 切り上げ。上へ移動するように。 */
    compareResult = compare(array[middle], searchValue);

    if (compareResult == 0) {
        foundIndex = middle;
        low = middle; /* lowがcompareResult==0であることを保証する */
    } else if (compareResult < 0) {
        low = middle + 1;
    } else {
        high = middle - 1;
    }
}

if (foundIndex == -1 && 0 == compare(array[low], searchValue)) {
    foundIndex = low;
}

return foundIndex;

最初のインデックスと最後のインデックスを両方調べる必要がある場合は、横着プログラミングでやられているように、最初のインデックスを検索するときに、はじめてcomparedResult==0となったときのlowとhighを憶えておいて、最後のインデックスを調べるときはそのlowとhighからスタートすると良いです。どうせ途中まで同じことをやるのですから。

上記にあげたソースですが、プログラムから抜粋してちょっと編集しちゃったのでバグってるかも。気をつけて!(もとのプログラム自体バグってる可能性も・・・。。。)

ソートソーターソーテスト

ソートを考えてみる。

C:


#include <stdlib .h>
void qsort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *)); 


まあ、以上だな。最後の引数で比較関数へのポインタを渡してあげれば(人間)万事(塞翁が馬)OKだ。

C++:


#include <algorithm>
void std::sort(RanIt first, RanIt last, BinPred pr); 

まあ、STL使いましょうやってことでな。最後のprはなくてもいいが、比較関数を自分で用意する場合に渡してあげれば(人間)(略)。
たとえばvectorをソートするには下記のようにする。


#include <algorithm>
struct cmp { 
   bool operator()(int a, int b) const { 
      return b > a; // 昇順ソート 
      // return a > b; 降順ソート 
   } 
};

int main() { 
   std::vector< int > a; 
   a.push_back(10); 
   a.push_back(2); 
   a.push_back(5); 

   std::sort(a.begin(), a.end(), cmp()); 
   for(int i = 0; i < a.size(); i++) { 
      printf("%d\n",a[i]); 
   } 
} 

なんかしらんが、operator()をオーバーロードしたクラスを作ってインスタンスをstd::sortに渡せばいいらしい。ちなみにoperator()をオーバーロードしたクラスを関数オブジェクトって言うらしい。関数のオブジェクトだな。インスタンス名()みたいな使い方できるからな。
なんでboolなのか、なんであれで昇順なのかはしらん。
たぶん、strcmpみたいなんと同じような理屈で結果を解釈して、大きいほうの引数を後ろに配置するんだろう。関数ポインタでもいいらしい。

 
std::vector< char * >

みたいな場合は


struct cmp { 
   bool operator()(const char *a, const char *b) const { 
   for (int i = 0; a[i] != '\\0' && b[i] != '\\0'; i++) { 
      if (a[i] != b[i]) { 
         return b[i] > a[i]; 
      } 
   } 
   if (a[i] == '\\0' && b[i] != '\\0') { 
      return true; 
   } 
   return false; 
}; 

みたいな感じでいいんじゃないかと思った。

Perl:


@array = sort @array; 

まあ、こんな感じ。比較関数を定義したい場合は、


@array = sort { $a cmp $b } @array; 

見たいな感じ。
{ }の中が-1なら$aを前に、1なら$bを前にするということらしい。
→http://www.uopmu.ees.osakafu-u.ac.jp/~yabu/soft/perl.html
がとっても参考になる。今まで雰囲気で使ってた。
そういうわけで、[C++]のやつと同じような考え方でよさげ。
$aと$bは予約語みたいなもんなのか?

Java:
配列なら
Arrays.sort()
コレクションなら
Collections.sort()

まあ、これはJavadocあるし、こまるこたぁないだろう。
Comparatorを作れば好きなように比較できる

キーワード:
クイックソート,quick,sort,ファンクタ,アルゴリズム,演算子,ソート,sort,list,コンテナ,アダプタ

たまのCはビタミンが足りない


void function(std::vector a) { 
    for (int i = 0; i < a.size() - 1; i++) { 
       // 処理  
         yabee(a.at(i)); 
    } 
} 

上のはやばい感じです。
はまりますた。
正しくは多分下。


for (int i = 0; i + 1 < a.size(); i++) { 
    // 処理 
    yabee(a.at(i)); 
} 

a.size()-1はsize()がsize_tなので-1にならない感じです。

キーワード:
C++,unsigned,オーバーフロー

字句解析

cygwinでflexを使ったら、gccは-llオプションではなくて
-lflにするといいっぽい。
yywrapを定義せぇってことかも知らんが。

キーワード:
yacc,lex,flex,bison,リンク,リンカ,コンパイル

省略

C言語って


int a();
b();

main(void) {
   a();
   b(1,2);
   return 1;
}

int a() {
   printf("a\n");
   return 0;
}

b(int c) {
   printf("b %d\n", c);
}

############################
>a.out
>a
>b 1
############################

これ、OKなんですね。
と知って驚いたのは昨日の話だ。
関数宣言で引数を省略すると、引数に関しては照合を行わないという意味になるとかならないとか。
ちなみに、gccでは通ったがg++では通らなかった。

キーワード:
引数を省略,引数の省略,戻り値の省略,戻り値を省略,プロトタイプ宣言,C言語

Home > C言語 Archive

Search
Feeds
Meta
 合計:018987
 今日:0126 昨日:0157

Return to page top