0

(C) realloc 配列は、items が指すデータを変更します

こんにちは、

共有したい素敵な奇妙なバグ ;-) いくつかの予備的な説明が必要です。

まず、PStringサイズ (およびハッシュ値) を保持する文字列の型があり、その後にバイトを持つ柔軟な配列メンバーが続きます。コンストラクターのタイプと種類は次のとおりです (最後の printfl ステートメントは debug です)。

typedef struct {
   size_t   size;
   uint     hash;
   char     bytes[];
} PString;

// offset from start of pstring struct to start of data bytes:
static const size_t PSTRING_OFFSET = sizeof(size_t) + sizeof(uint);

PString * pstring_struct (string str, size_t size, uint hash) {
   // memory zone
   char *mem = malloc(PSTRING_OFFSET + size * sizeof(char));
   check_mem(mem);

   // string data bytes:
   memcpy(mem + PSTRING_OFFSET, str, size);
   mem[PSTRING_OFFSET + size] = NUL;

   // pstring struct:
   PString * pstr = (PString *) mem;
   pstr->size = size;
   pstr->hash = hash;

   printfl("*** str:'%s' (%u) --> pstr:'%s' (%u) 0x%X",
   str, size, pstr->bytes, pstr->size, pstr);   ///////////////////////
   return pstr;
}

[この構築についてのコメントは歓迎します: ここで物事を正しく行うかどうかはまったくわかりません。柔軟な配列メンバーを使用するのはこれが初めてであり、割り当てられた構造体でそれらを使用する例を見つけることができませんでした.]

次に、これらの pstring は文字列プールに格納されます。これは、ハッシュ テーブルとして実装されたセットを意味します。いつものように、衝突 (ハッシュとモジュロの後) の「バケット」は、セルの単純なリンクされたリストであり、それぞれが pstringポインターと次のセルへのポインターを保持します。唯一の特別な詳細は、ヒープのどこかに割り当てられるのではなく、セル自体が配列に格納されることです [1]。絵がはっきりしていることを願っています。の定義は次のCellとおりです。

typedef struct SCell {
   PString        * pstr;
   struct SCell   * next;
} Cell;

プール自体の一連のテストを含め、すべてが正常に機能しているように見えました。ここで、pstring ルーチン (検索) をテストしているときに、文字列が変更されていることに気付きました。いくつかの調査の後、私は最終的に問題がプールの成長に関連していると推測し、最終的にはセルの配列の成長に関する問題を正確に減らすことができました(したがって、セルをリストに再分配する前に)。これは、この成長に関するデバッグ出力の行でありshow_pool、出力を生成するルーチンのコピー (文字列のみを表示) と出力自体を示しています。

static void pool_grow (StringPool * pool, uint n_new) {
    ...
   // Grow arrays:
   show_pool(pool);  /////////////////////
   pool->cells = realloc(pool->cells, pool->n_cells * sizeof(Cell));
   check_mem(pool->cells);
   show_pool(pool);  ////////////////////
   ...

static void show_pool (StringPool * pool) {
   if (pool->n == 0) {
      printfl("{}");
      return;
   }

   printf("pool          : {\"%s\"", pool->cells[0].pstr->bytes);

   PString * pstr;
   uint i;
   for (i = 1; i < pool->n; i++) {
      pstr = pool->cells[i].pstr;
      printf(", \"%s\"", pstr->bytes);
   }

   printl("}");
}

// output:
pool          : {"", "abc", "b", "abcXXXabcXXX"}
pool          : {"", "abc", "b", "abcXXXabcXXXI"}

ご覧のとおり、格納された最後の文字列には追加のバイト「I」があります。その間、私は realloc を呼び出しているだけなので、さらにデバッグするには少しブロックされていることに気付きます。一生懸命考えても、この謎を解明する助けにはなりません。(セルは pstringポインターを保持するだけなので、セルの配列を拡張すると文字列バイトがどのように変更されるのでしょうか?) また、printfそこで止まります。

ありがとうございました。手伝ってくれますか？

[1] ここでは、文字列プールでそれを行う特別な理由はありません。私は通常、順序付けられたセットまたはマップを無料で取得し、さらに参照の局所性を取得するためにこれを行います. (唯一のオーバーヘッドは、セルの配列がバケットの配列に加えて成長しなければならないことですが、事前に次元を設定することで成長の数を減らすことができます。)

4

1 に答える 1

2

sizeヌルターミネータが含まれていないため、

   mem[PSTRING_OFFSET + size] = NUL;

無効です。他のすべての問題はこれに起因します。

于 2012-12-14T17:55:09.627 に答える