21

ノードのプライオリティ キュー (定義済みの構造体) を使用する圧縮アルゴリズム (ハフマン コーディングを使用) を実装しました。今、Linuxまたはビジュアルスタジオでコードを実行すると、すべて正常に動作します. Visual Studio でメモリ リークをチェックすると、何も表示されません。

問題は、valgrind を使用してプログラムを分析すると、シグナル 11 (sigsegv) で終了することです。発生した最初のエラーは、メソッド delete min での「サイズ 4 の無効な読み取り」です。その後のその他のエラー: アドレスは解放されたサイズ 453 のブロック内で 0 バイト、サイズ 4 の無効な書き込み、無効な解放、削除、または再割り当てです。

私が犯した可能性のあるエラーの種類について、誰かアドバイスをもらえますか? 私は何時間もインターネットを検索してきましたが、間違っていることを見つけることができません (特に、valgrind を使用していないときに機能するため)。または、読み取りエラーの原因をデバッグして見つける方法のヒント。

どうもありがとう！

誰かがレビューしたい場合のコードを次に示しますが、この特定のコードに飛び込むのは簡単ではないと思います.

コードの優先キューと関係があると思います：

私がハフマン部分を行う部分->毎回2つの最小ノードを削除し、両方の合計を1つのノードとして追加します。

while(queue->size > 1){
    node* n1 = delete_min(queue);
    node* n2 = delete_min(queue); // all the errors are encountered in this call
    node* temp = (node*) calloc(sizeof(node),1);
    temp->amount = n1->amount + n2->amount;
    insert_node(queue,temp);
    n1->parent = temp;
    n2->parent = temp;
    temp->left = n1;
    temp->right = n2;
}

以下は、プライオリティ キューの delete_min および insert_node メソッドです。

void insert_node(priority_queue* p_queue, node* x){
    int i = p_queue->size;
    if(i == 0){
        p_queue->queue = (node**) malloc(sizeof(node*));
    }
    else{
        p_queue->queue = (node**) realloc(p_queue->queue,sizeof(node*)*(p_queue->size+1));
    }
    p_queue->queue[p_queue->size] = x;

    while(i>=0 && p_queue->queue[i]->amount < p_queue->queue[(i-1)/2]->amount){
        node* temp = p_queue->queue[i];
        p_queue->queue[i] = p_queue->queue[(i-1)/2];
        p_queue->queue[(i-1)/2] = temp;
        i = (i-1)/2;
    }
    p_queue->size++;
}

node* delete_min(priority_queue* p_queue){
    node** queue = p_queue->queue;
    node* min = queue[0];

    if(p_queue->size>1){
        int r = 0;
        int current = 1; //left child of root

        queue[0] = queue[p_queue->size-1];
        queue = (node**) realloc(queue,sizeof(node*)*(--p_queue->size));
        while(current < p_queue->size){
            //in case of 2 children, check if current needs to be right or left child
            if(current < p_queue->size-1 && queue[current] > queue[current+1]){
                current++;
            } 
            if(queue[current] < queue[r]){
                node* temp = queue[r];
                queue[r] = queue[current];
                queue[current] = temp;

                r = current;
                current = 2 * current;
            }
            else{
                break;
            }
            current++;
        }
    }
    else{
        free(queue);
        p_queue->size--;
    }
    return min;
}

編集: valgrind 出力を追加しました:

Invalid read of size 4
==1893==    at 0x80498E0: delete_min (huffman.c:331)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==  Address 0x441d9a8 is 0 bytes inside a block of size 452 free'd
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492CC: huffman_encode (huffman.c:195)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893== 
==1893== Invalid read of size 4
==1893==    at 0x8049901: delete_min (huffman.c:333)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==  Address 0x441db64 is 444 bytes inside a block of size 452 free'd
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492CC: huffman_encode (huffman.c:195)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893== 
==1893== Invalid write of size 4
==1893==    at 0x8049906: delete_min (huffman.c:333)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==  Address 0x441d9a8 is 0 bytes inside a block of size 452 free'd
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492CC: huffman_encode (huffman.c:195)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893== 
==1893== Invalid free() / delete / delete[] / realloc()
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==  Address 0x441d9a8 is 0 bytes inside a block of size 452 free'd
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492CC: huffman_encode (huffman.c:195)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893== 
==1893== Invalid read of size 4
==1893==    at 0x8049A0E: delete_min (huffman.c:337)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==1893== 
==1893== 
==1893== Process terminating with default action of signal 11 (SIGSEGV)
==1893==  Access not within mapped region at address 0x0
==1893==    at 0x8049A0E: delete_min (huffman.c:337)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)

行 331 は、次の delete_min の行です。 node* min = queue[0];

編集：

問題は解決しました。受け入れられた回答では、その理由が説明されています。delete_min で再割り当てされた値を正しく割り当てるだけで、すべての問題が解決しました。

//realloc queue and assign new value to local queue var
p_queue->queue = (node**) realloc(queue,sizeof(node*)*(--p_queue->grootte));
queue = p_queue->queue;
4

2 に答える 2

28

最初のエラーについて説明します。

==1893== Invalid read of size 4
==1893==    at 0x80498E0: delete_min (huffman.c:331)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)

331 行目で、おそらく、独自のプログラムに割り当てていないメモリの一部で (unsigned) int を読み取っています。

==1893==  Address 0x441d9a8 is 0 bytes inside a block of size 452 free'd
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492CC: huffman_encode (huffman.c:195)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==

この部分は、読み取ろうとしたメモリの部分に関する詳細情報を提供します。すでにメモリを使用していると表示されますが、reallox によって解放されました。つまり、再割り当てしたメモリの一部への古いポインターから読み取っています。

古いものではなく、ポインタ realloc が返すことを確認する必要があります。

これが valgrind の外で実行しているときにクラッシュしない理由は、ほとんどの場合、メモリの同じ部分が realloc によって割り当てられるためです。したがって、ポインターは同じままであり、コードは機能します。ただし、realloc がメモリの一部を移動することを決定し、コードがクラッシュすることがあります。ヴァルグリンドはこれについてあなたに警告しようとしています.

残りのエラーは、返されたポインターを使用しているときに解決される可能性があります。

于 2012-11-25T10:41:40.283 に答える
3

Valgrind エラーに基づいて、既に削除したノードにアクセスして解放している可能性があります。Valgrind エラーを対応する行番号とともに投稿することを検討してください (gcc で -g を使用してコンパイルします)。

編集: 最も明白なエラーである segfault は、デバッグを開始する場所です。この行は失敗します:

while((2*i)+2 < p_queue->grootte-1 && (queue[i]->amount > queue[(2*i)+1]->amount || queue[i]->amount > queue[(2*i)+2]->amount)){

おそらくqueueNULLのためです。なぜNULLなのですか？おそらく、 realloc が何も割り当てていないためです。なぜ何も割り当てなかったのですか？メモリが足りなくなった (可能性は低い) か、サイズ 0 のものを割り当てようとしたためです ( realloc の詳細については、http: //www.cplusplus.com/reference/cstdlib/realloc/ を参照してください)。どのようにサイズ 0 をリクエストできますか? 0 の場合p_queue->size-1。

于 2012-11-24T23:30:50.310 に答える