C言語編 第35章 ポインタ⑤(動的なメモリの再割り当て)

先頭へ戻る

この章の概要

この章の概要です。

realloc関数

前章に引き続いて、動的なメモリ割り当てに関する関数を紹介します。

今回紹介する realloc関数は、動的に確保した領域の大きさを、後から変更するものです。realloc関数は、stdlib.h に次のように宣言されています。

void* realloc(void* ptr, size_t size);

第1引数に、既に動的に確保済みの領域を指すポインタを渡します。 既に動的に確保済みな領域というのは、malloc関数や calloc関数、あるいは realloc関数によって確保された領域ということです。
なお、第1引数にヌルポインタを指定することができ、この場合、malloc関数と同じ動作になります

第2引数には、領域の新しい大きさを指定します。 以前の大きさよりも、小さくても大きくても、同じでも構いません。
なお、第2引数に 0 を指定した場合、free関数と同じ動作になります。 これは非常に分かりづらい仕様であり、注意が必要です。

戻り値は、新しい大きさに変更された後の領域を指すポインタが返されます。失敗した場合にはヌルポインタが返されます。成功した場合は、その領域が必要なくなった後、free関数で解放する必要があります。

realloc関数は少々複雑なので、イメージを掴みづらいかも知れません。 実際にどんなことをしているのか、具体的な実装例をお見せしましょう。

void* realloc(void* ptr, size_t size)
{
    char* p;

    if( ptr == NULL ){
        return malloc( size );  /* 第1引数が NULL の場合、malloc関数と同じ動作になる */
    }

    if( size == 0 ){
        free( ptr );            /* 第2引数が 0 の場合、free関数と同じ動作になる */
        return NULL;            /* 新たに確保される領域はないので NULL を返す */
    }

    p = malloc( size );             /* malloc関数を使って、新しい方の大きさの領域を確保する */
    if( p == NULL ){
        return NULL;            /* malloc関数が失敗した場合、NULL を返す。元の領域はそのまま残る */
    }

    memcpy( p, ptr, size );         /* 元の領域にあるデータを、新しく確保した領域にコピーする */
    free( ptr );                    /* 元の領域は解放する */

    return p;                       /* 新しい領域の先頭アドレスを返す */
}

上記のサンプルプログラムは、realloc関数がどのように実装されているかの一例を示すものであって、 必ずこの程度に実装されているということではありません。 しかし、標準規格に従っていれば、行っている内容は同等のはずです。

まず、最初の if文では、第1引数がヌルポインタの場合の処理を行っています。前述したように、第1引数が ヌルポインタの場合、malloc関数と同じことを行います。

2つ目の if文では、第2引数が 0 の場合の処理を行っています。 これも前述したように、第2引数が 0 の場合、free関数と同じことを行います。

このような仕様は、よくない設計の代表格とされています。つまり、「処理を詰め込みすぎ」です。極論すれば、malloc関数も free関数も必要なくて、realloc関数だけで賄えてしまえる訳ですが、関数名には、処理の内容を説明する効果もあるので、できるだけ特化した関数の方が分かりやすく、間違いにくいです。第1引数がヌルポインタのときの挙動はまだマシで、使いどころもありますが、第2引数が 0 のときに free関数の意味になるのは「realloc」という関数名の「alloc」の部分がまったく活きていません。

その後、新しい大きさの領域を動的に割り当てています。これは当然、元々確保されていた領域とは別のメモリアドレスに作られています。ここでメモリ不足などで失敗する可能性がありますが、その際には realloc関数自身の失敗としてヌルポインタを返して終了します。この場合には、元々確保されていた領域には、何ら変化は起きていません。

元々確保されていた領域にあった内容は、新しい領域に引き継がせたいので、内容をコピーする必要があります。これを行っているのが、memcpy関数です。
memcpy関数は、第2引数で指定したメモリアドレスを起点にして、第1引数で指定したメモリアドレスへと、第3引数で指定した大きさの分だけコピーを行います。 文字列専用に特化された strcpy関数に対する、汎用版と考えられます。文字列専用ならば終端文字('\0') でコピーする大きさを判断できますが、汎用版だとそうはいかないので、第3引数に大きさを指定します。

コピーを終えたら、元々確保されていた領域は必要なくなるので、free関数を使って解放します。

まとめると、流れは以下のようになります。

  1. malloc関数で、新しいメモリ領域を割り当てる
  2. memcpy関数で、古いメモリ領域にあったデータを、新しいメモリ領域へコピーする
  3. free関数で、古いメモリ領域を解放する
  4. 新しい領域のメモリアドレスを返す

従って、古いメモリ領域にあったデータは、新しいメモリ領域にきちんと移動します。 しかし、新しく確保しなおしているのですから、メモリアドレスは変わってしまいます。 これは、古いメモリ領域にあったオブジェクトを指していたポインタを使って間接参照を行ってはならないということです。

また、realloc関数が成功したのであれば、古いメモリ領域は、realloc関数内で解放済みですから、自分で解放する必要はありません。

ではここで、実際に使用感を確かめておきましょう。

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

int main(void)
{
    char buf[40];
    int num;
    int* tmp;
    int* array = NULL;
    size_t size = 0;
    size_t i;


    while( 1 ){
        puts( "次のデータを整数で入力して下さい。負数を入力すると終了します。" );
        fgets( buf, sizeof(buf), stdin );
        sscanf( buf, "%d", &num );

        if( num < 0 ){
            break;
        }

        size++;

        /* 領域を拡張する */
        tmp = realloc( array, sizeof(int)*size );
        if( tmp == NULL ){
            /* realloc関数が失敗した場合、元の領域は解放されずに残されている */
            /* 自分で free関数を呼び出して終了する */
            free( array );
            exit( EXIT_FAILURE );
        }
        array = tmp;
        tmp = NULL;  /* 安全策。確保された領域を指すポインタを array だけに限定する */

        /* 入力されたデータを格納 */
        array[size-1] = num;
    }

    /* 結果を出力 */
    for( i = 0; i < size; ++i ){
        printf( "%d\n", array[i] );
    }

    free( array );

    return 0;
}

実行結果:

次のデータを整数で入力して下さい。負数を入力すると終了します。
3
次のデータを整数で入力して下さい。負数を入力すると終了します。
5
次のデータを整数で入力して下さい。負数を入力すると終了します。
7
次のデータを整数で入力して下さい。負数を入力すると終了します。
10
次のデータを整数で入力して下さい。負数を入力すると終了します。
-1
3
5
7
10

標準入力から受け取ったデータを出力するだけの、お馴染みのプログラムです。

realloc関数を使うときに注意する点して、 第1引数に指定するポインタ変数と、戻り値を受け取るポインタ変数を別のものにするべきです。 同じ変数を使って、以下のように書いたとします。

array = realloc( array, sizeof(int)*size );

こうしてしまうと、realloc関数が失敗した場合にヌルポインタが返されますから、ポインタ変数 array にはヌルポインタが代入されます。しかし、元々 array が指していたメモリ領域はまだ解放されていません。realloc関数が失敗した場合、realloc関数内の free関数は実行されないためです(前述の実装例を確認して下さい)。

ポインタ変数array が元々持っていたメモリアドレスの情報が失われてしまったため、 free関数を呼ぶことができず(実引数に何を渡せばいいのか?)、メモリ領域を解放する術がなくなってしまうのです。

そのため、realloc関数の戻り値は、第1引数に渡すポインタ変数とは異なるポインタ変数で受け取り、 realloc関数が成功したときに、改めて array へ代入しなおすようにします。

また、サンプルプログラム内で「安全策」というコメントがあります。realloc関数の戻り値を一旦受け取るために使ったポインタ変数(tmp) は、本来代入すべきポインタ変数(array) に値をコピーした後には不要になります。使わなければよいだけのことではありますが、間違って「free(tmp);」と「free(array);」を両方書いてしまうようなミスを犯すと、解放済みのメモリ領域を再度解放するという未定義の動作になってしまいます(第34章)。そこで、もう使わなくなったポインタ変数にはヌルポインタを入れておくという手を取っています。これで間違って「free(tmp);」を書いたとしても、何も起こりませんから安全です。

実行効率の改善

前の節で見た realloc関数の使用例は、うまく動くものの、データ件数が多い場合の実行効率は良いものではありません。

前に説明したとおり、realloc関数は以下のような流れで処理されます。

  1. malloc関数で、新しいメモリ領域を割り当てる
  2. memcpy関数で、古いメモリ領域にあったデータを、新しいメモリ領域へコピーする
  3. free関数で、古いメモリ領域を解放する
  4. 新しい領域のメモリアドレスを返す

この最初の2つの過程は、特に実行速度への影響が大きいですから、データが 1件増えるたびに毎回実行するのは避けるべき行為です。

そこで改善策の1つとして、動的に確保する領域の大きさが、倍々されていくように実装するという方法があります。 まずは、その方法で実装されたプログラムをご覧下さい。

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

#define INITIAL_SIZE    2

int main(void)
{
    char buf[40];
    int num;
    int* tmp;
    int* array;
    size_t capacity;  /* 確保されている領域の大きさ */
    size_t size;      /* データ総数=実際に使用されている領域の個数 */
    size_t i;


    /* 初回確保 */
    capacity = INITIAL_SIZE;
    array = malloc( sizeof(int) * capacity );
    size = 0;


    while( 1 ){
        puts( "次のデータを整数で入力して下さい。負数を入力すると終了します。" );
        fgets( buf, sizeof(buf), stdin );
        sscanf( buf, "%d", &num );

        if( num < 0 ){
            break;
        }

        size++;

        /* 領域が足りなくなったら、既存の領域の大きさの倍を再確保する */
        if( size >= capacity ){
            capacity *= 2;
            tmp = realloc( array, sizeof(int) * capacity );
            if( tmp == NULL ){
                /* realloc関数が失敗した場合、元の領域は解放されずに残されている */
                /* 自分で free関数を呼び出して終了する */
                free( array );
                exit( EXIT_FAILURE );
            }
            array = tmp;
            tmp = NULL;  /* 安全策。確保された領域を指すポインタを array だけに限定する */
        }

        /* 入力されたデータを格納 */
        array[size-1] = num;
    }

    /* 結果を出力 */
    for( i = 0; i < size; ++i ){
        printf( "%d\n", array[i] );
    }

    free( array );

    return 0;
}

実行結果:

次のデータを整数で入力して下さい。負数を入力すると終了します。
3
次のデータを整数で入力して下さい。負数を入力すると終了します。
5
次のデータを整数で入力して下さい。負数を入力すると終了します。
7
次のデータを整数で入力して下さい。負数を入力すると終了します。
10
次のデータを整数で入力して下さい。負数を入力すると終了します。
-1
3
5
7
10

今回は、最初に malloc関数を使って領域を作っておきます。 このときの要素数は INITIAL_SIZE で表現されます。 テストということで、かなり小さな値を設定していますが、通常は、実際のデータ数がどの程度かによって調整します。

現在確保されている領域の要素数と、実際に使用されている領域の要素数とを個別に管理する必要があります。 そして、実際に使用されている領域の要素数が、確保済みの要素数を超えてしまうタイミングまで、realloc関数の呼び出しをしないようにするのです。 realloc関数を呼び出すときには、現在の領域の大きさの倍を指定します。 このように実装することによって、realloc関数の呼び出し回数は大幅に削減されます。

倍々で確保しなければならないという訳ではありません。 最大限の効率を求めるのなら、実際のデータを使って調整を繰り返して、最適な答えを探す必要があります。

フラグメンテーション

realloc関数に限った話ではありませんが、動的なメモリ割り当てを行う場合、 フラグメンテーション(断片化)という現象が問題になることがあります。 フラグメンテーションとは、メモリ上に、使われていない細切れの領域が出来てしまい、無駄の多い状態に陥ることを言います。

例えば、メモリの状態が、次の図のようになっているとします。

フラグメンテーションの例

塗りつぶされた部分は使用済みの領域で、塗りつぶされていない部分は未使用な領域を表しています。 この状態は、次の図に比べると、無駄があると考えられます。

フラグメンテーションの例

なぜなら、最初の図の状態では、少し大きめのメモリ割り当て要求が発生した場合、割り当てができない可能性が出てくるからです。 例えば、次の図で、黄色の四角形が、新たに発生したメモリ割り当て要求の大きさを表しているとします。

フラグメンテーションの例

未使用の2か所の領域を足し合わせれば、割り当てが可能な大きさですが、分断されてしまっているため割り当てに失敗してしまいます。 このように、未使用の領域をすべてまとめれば十分に領域が残っていても、メモリの利用状況が悪くなっていると、割り当てに失敗することがあります

フラグメンテーションは、異なる大きさのメモリ領域の確保と解放が繰り返されると起こりやすいです。 例えば、メモリ領域の確保を6回行い、以下のような状態になったとします。

フラグメンテーションの例

この後、途中の2か所が解放されると、以下の状態が生まれます。

フラグメンテーションの例

フラグメンテーションを完全に防ぐことは困難であり、一般的には、幾つかの方策によって軽減させることを目指すのが基本です。 例えば、次のような手段があります。

前者は、「確保→確保→解放→確保→解放→解放」のように混ざり合うことを避け、「確保→確保→確保→解放→解放→解放」のように 確保はまとめて行い、解放も最後にまとめて行うという考え方です。 確保がメモリ領域の前方から順番に行われると仮定すると、この方法で綺麗にメモリ領域が使えることが分かります。

メモリ割り当ての要求に対して、どうやって空き領域を探し出すかという部分は、実行環境に依存します。 ここで考えている、「最初に見つけた十分な広さの領域を割り当てる方法」はファーストフィット法と呼ばれる手法です。 この手法以外でメモリ割り当てを行う実行環境では、この方法では改善できないかも知れません。

後者は、確保する大きさを 256バイトなどの固定値に統一する方法です。 例えば、必要な大きさが 100バイトであったとしても、256バイトで確保してしまうということです。 この方法では、途中のメモリ領域が解放されて空きになったとしても、その空き領域の大きさは 256バイトですから、 次回の 256バイトの確保要求に応えられます。

後者の方法は、ここまでに考えてきたフラグメンテーションを解決することができる反面、メモリの利用効率は悪化する可能性があります。 つまり、100バイトのメモリ領域が欲しくても、256バイト分のメモリ領域を使ってしまうため、 156バイト分は実質的に使っていないということになります。 このような状態は、内部フラグメンテーションと呼ばれます。 (これに対して、ここまでに解説してきたフラグメンテーションを外部フラグメンテーションと呼ぶことがあります)。


realloc関数は、フラグメンテーションを助長する可能性が高いと言えます。 新しい大きさで領域を確保する際、以下の順序で処理が進みます。

  1. malloc関数で、新しいメモリ領域を割り当てる
  2. memcpy関数で、古いメモリ領域にあったデータを、新しいメモリ領域へコピーする
  3. free関数で、古いメモリ領域を解放する

realloc関数を呼ぶ前には、malloc関数などで古い領域の確保が行われていますから、 全体としては「(古い領域の)確保→(新しい領域の)確保→(古い領域の)解放→(新しい領域の)解放」という順番になります。 そのため、古い領域が解放された後、その部分が未使用の断片として取り残さる可能性があります。

フラグメンテーションが起きること自体が、常に問題である訳ではありませんから、realloc関数を使ってはいけないということではないのですが、 規模の大きいプログラムを開発する際には、こういう状況を招く可能性があることを知っておくべきでしょう。 不用意に、細かく動的なメモリ割り当てを使うべきではない理由の1つです。


練習問題

問題① 標準入力から、long型に収まる整数値が繰り返し入力されるとして、 全ての入力を受け取った後、それらの中で最も大きい値を出力するプログラムを書いて下さい。 入力件数は不明で、負数が入力されると終了します。

問題② 標準入力から、long型に収まる整数値が繰り返し入力されるとして、 全ての入力を受け取った後、入力された数値の平均値を出力するプログラムを書いて下さい。 入力件数は不明ですが、最大でも 1000件とし、負数が入力されると終了します。
ただし、必要なメモリ領域はプログラムの開始直後にまとめて確保し、 最後に realloc関数を使って、使われなかった領域を切り詰める方法で実装して下さい。

問題③ realloc関数を次の条件でラップした関数を作成して下さい。

問題④ フラグメンテーションを解決するために、使用済みの領域を詰め直すことで、 細切れの未使用領域を無くすという手段を取ることは可能でしょうか?


解答ページはこちら

参考リンク

更新履歴

'2018/5/14 章のタイトルを変更(「ポインタ⑤ 動的なメモリ割り当て②」->「ポインタ⑤(動的なメモリの再割り当て)」)

'2018/4/20 「NULL」よりも「ヌルポインタ」が適切な箇所について、「ヌルポインタ」に修正。

'2018/3/11 全面的に文章を見直し、修正を行った。

'2018/3/10 章のタイトルを変更(「動的なメモリ」->「動的なメモリ割り当て」)

'2018/2/22 「サイズ」という表記について表現を統一。 型のサイズ(バイト数)を表しているところは「大きさ」、要素数を表しているところは「要素数」。

'2009/12/25 新規作成。





前の章へ(第34章 ポインタ④(動的なメモリ割り当て))

次の章へ(第36章 ポインタ⑥(データ構造の構築))

C言語編のトップページへ

Programming Place Plus のトップページへ


このエントリーをはてなブックマークに追加
rss1.0 取得ボタン RSS