2

C をブラッシュアップするために、便利なライブラリ コードをいくつか書いています。テキスト ファイルの読み取りに関しては、面倒な作業のほとんどを行う便利なトークン化関数があると常に便利です (ループstrtokは不便で危険です)。

この関数を書いたとき、その複雑さに驚かされました。実を言うと、バグ (特に割り当てエラーの場合のメモリ リーク) が含まれているとほぼ確信しています。コードは次のとおりです。

/* Given an input string and separators, returns an array of 
** tokens. Each token is a dynamically allocated, NUL-terminated
** string. The last element of the array is a sentinel NULL 
** pointer. The returned array (and all the strings in it) must
** be deallocated by the caller.
**
** In case of errors, NULL is returned.
** 
** This function is much slower than a naive in-line tokenization,
** since it copies the input string and does many allocations.
** However, it's much more convenient to use.
*/ 
char** tokenize(const char* input, const char* sep)
{
    /* strtok ruins its input string, so we'll work on a copy 
    */
    char* dup;

    /* This is the array filled with tokens and returned
    */
    char** toks = 0;

    /* Current token
    */
    char* cur_tok;

    /* Size of the 'toks' array. Starts low and is doubled when
    ** exhausted.
    */
    size_t size = 2;

    /* 'ntok' points to the next free element of the 'toks' array
    */
    size_t ntok = 0;
    size_t i;

    if (!(dup = strdup(input)))
        return NULL;

    if (!(toks = malloc(size * sizeof(*toks))))
        goto cleanup_exit;

    cur_tok = strtok(dup, sep);

    /* While we have more tokens to process...
    */
    while (cur_tok)
    {
        /* We should still have 2 empty elements in the array, 
        ** one for this token and one for the sentinel.
        */
        if (ntok > size - 2)
        {
            char** newtoks;
            size *= 2;

            newtoks = realloc(toks, size * sizeof(*toks));

            if (!newtoks)
                goto cleanup_exit;

            toks = newtoks;
        }

        /* Now the array is definitely large enough, so we just
        ** copy the new token into it.
        */
        toks[ntok] = strdup(cur_tok);

        if (!toks[ntok])
            goto cleanup_exit;

        ntok++;
        cur_tok = strtok(0, sep);
    }    

    free(dup);
    toks[ntok] = 0;
    return toks;

cleanup_exit:
    free(dup);
    for (i = 0; i < ntok; ++i)
        free(toks[i]);
    free(toks);
    return NULL;
}

簡単な使い方は次のとおりです。

int main()
{
    char line[] = "The quick brown fox jumps over the lazy dog";
    char** toks = tokenize(line, " \t");
    int i;

    for (i = 0; toks[i]; ++i)
        printf("%s\n", toks[i]);

    /* Deallocate
    */
    for (i = 0; toks[i]; ++i)
        free(toks[i]);
    free(toks);

    return 0;
}

ああ、そしてstrdup：

/* strdup isn't ANSI C, so here's one...
*/
char* strdup(const char* str)
{
    size_t len = strlen(str) + 1;
    char* dup = malloc(len);

    if (dup)
        memcpy(dup, str, len);

    return dup;
}

tokenize関数のコードについて注意すべき点がいくつかあります。

  1. strtokには、入力文字列を上書きするという失礼な癖があります。ユーザーのデータを保存するには、入力の複製に対してのみ呼び出します。を使用して複製を取得しstrdupます。
  2. strdupただし、ANSI-C ではないため、ANSI-C を作成する必要がありました

  3. トークンの数が事前にわからないため、toks配列は で動的に拡張されます。reallocテスト用の初期サイズは 2 です。実際のコードでは、おそらくもっと大きな値に設定します。また、ユーザーに返され、ユーザーは使用後に割り当てを解除する必要があります。

  4. いずれの場合も、リソースをリークしないように細心の注意を払っています。たとえば、reallocNULL を返す場合、古いポインターは実行されません。古いポインターが解放され、関数が戻ります。返されたときにリソースがリークすることはありませんtokenize(ユーザーに返された配列を使用後に割り当てを解除する必要がある名目上のケースを除きます)。

  5. Aは、場合によっては適切な哲学gotoに従って、より便利なクリーンアップ コードに使用されます(これは良い例です。IMHO)。goto

次の関数は、1 回の呼び出しで単純な割り当て解除を行うのに役立ちます。

/* Given a pointer to the tokens array returned by 'tokenize',
** frees the array and sets it to point to NULL.
*/
void tokenize_free(char*** toks)
{
    if (toks && *toks)
    {
        int i;

        for (i = 0; (*toks)[i]; ++i)
            free((*toks)[i]);
        free(*toks);
        *toks = 0;
    }
}

SO の他のユーザーとこのコードについて話し合いたいと思います。何がもっとうまくできたでしょうか？そのようなトークナイザーに異なるインターフェイスをお勧めしますか? ユーザーからの割り当て解除の負担はどのように取り除かれますか? とにかくコードにメモリリークがありますか?

前もって感謝します

4

6 に答える 6

2

私がお勧めすることの 1 つはtokenize_free、すべての割り当て解除を処理できるようにすることです。ユーザーにとってより簡単で、ライブラリのユーザーを壊すことなく、将来的に割り当て戦略を柔軟に変更できます。

以下のコードは、文字列の最初の文字が区切り文字の場合に失敗します。

もう 1 つのアイデアは、個々のトークンをわざわざ複製しないことです。何が追加されるのかはわかりませんが、コードをファイルできる場所が増えるだけです。代わりに、作成した完全なバッファーの複製を保持してください。私が意味するのは変化です：

toks[ntok] = strdup(cur_tok);

if (!toks[ntok])
    goto cleanup_exit;

に：

toks[ntok] = cur_tok;

free(buf)エラーのないパスから行を削除します。最後に、これによりクリーンアップが次のように変更されます。

free(toks[0]);
free(toks);

于 2009-11-07T06:34:15.397 に答える
1

いくつかのこと：

  1. goto の使用は、プリプロセッサと同様に、本質的に悪いことでも悪いことでもありません。悪用されることがよくあります。あなたのように、状況に応じて異なる方法で関数を終了する必要がある場合、それらは適切です。
  2. 返された配列を解放する機能的な手段を提供します。すなわち tok_free(ポインタ)。
  3. 最初は再入可能バージョンの strtok()、つまり strtok_r() を使用します。そのために誰かが追加の引数 (必要でなければ NULL であっても) を渡すことは面倒ではありません。
于 2009-11-07T08:18:24.590 に答える
1

文字列をインラインで変更するための strtok アプローチに問題はありません。セマンティクスがよく理解されているため、重複した文字列を操作するかどうかは呼び出し元の選択です。以下は、意図したとおりに strtok を使用するように少し単純化された同じメソッドですが、便利な char * ポインターの配列を返します (現在は、元の文字列のトークン化されたセグメントを指すだけです)。元の main() 呼び出しと同じ出力が得られます。

このアプローチの主な利点は、すべての要素をクリアするためにループするのではなく、返された文字配列を解放するだけでよいということです。通常の C の慣例によって期待されること。

また、コードをリファクタリングしたため、goto ステートメントもあまり意味をなさなかったので削除しました。単一のクリーンアップ ポイントを持つことの危険性は、扱いにくくなりすぎて、特定の場所の問題をクリーンアップするのに不要な追加の手順を実行する可能性があることだと思います。

個人的には、特にライブラリの種類の呼び出しを作成するときに、言語を使用する他の人々が期待することを尊重する必要があるという主な哲学的ポイントがあると思います。strtok 置換の動作が奇妙に思える場合でも、大多数の C プログラマーは C 文字列の途中に \0 を配置して、それらを分割したり、短い文字列を作成したりすることに慣れているため、これは非常に自然なことのように思えます。また、前述のように、関数からの戻り値を使用して単一の free() 以外のことを行うことを期待する人は誰もいません。コードがそのように機能することを確認するために必要な方法でコードを記述する必要があります。人々はあなたが提供する可能性のあるドキュメントを単に読まず、代わりに戻り値のメモリ規則に従って動作するためです (これは char * です) * したがって、呼び出し元はそれを解放する必要があると予想します)。

char** tokenize(char* input, const char* sep)
{
  /* Size of the 'toks' array. Starts low and is doubled when
  ** exhausted.
  */
  size_t size = 4;

  /* 'ntok' points to the next free element of the 'toks' array
   */
  size_t ntok = 0;

  /* This is the array filled with tokens and returned
   */
  char** toks = malloc(size * sizeof(*toks));

  if ( toks == NULL )
    return;

  toks[ntok] = strtok( input, sep );


  /* While we have more tokens to process...
   */

  do
    {
      /* We should still have 2 empty elements in the array, 
      ** one for this token and one for the sentinel.
      */
      if (ntok > size - 2)
        {
      char** newtoks;
      size *= 2;

      newtoks = realloc(toks, size * sizeof(*toks));

      if (newtoks == NULL)
        {
          free(toks);
          return NULL;
        }

      toks = newtoks;
        }
      ntok++;
      toks[ntok] = strtok(0, sep);
    }  while (toks[ntok]);

  return toks;
}
于 2009-11-07T07:06:33.820 に答える
0

メモリ リークを見つけたい場合、1 つの可能性はvalgrindで実行することです。

于 2009-11-07T06:34:04.470 に答える
0

Valgrind と呼ばれるメモリ リークを検出する優れたツールがあります。

http://valgrind.org/

于 2009-11-07T06:38:12.363 に答える