C言語編 第35章 ポインタD(動的なメモリA)

このエントリーをはてなブックマークに追加

この章の概要

この章の概要です。

realloc関数

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

ここで紹介する realloc関数(⇒リファレンス)は、 1度、動的に確保された領域の大きさを変更します。

realloc関数は、stdlib.h に次のように宣言されています。

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

第1引数に、既に動的確保済みの領域を指すポインタを渡します。
第2引数には、新しい領域のサイズを指定します。
戻り値は、新しいサイズに変更された後の領域のアドレスが返されます。 失敗した場合には NULL が返されます。

新しい領域を解放する際には、これまで同様、free関数を使います。

この関数は少々複雑なので、どのような処理を行っているのか、具体的なコードをお見せしましょう。

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;                       /* 新しい領域の先頭アドレスを返す */
}

上記のサンプルコードは、標準ライブラリがどのように実装されているかの一例を示すものであって、コンパイラによって、記述は当然異なります。 しかし、C言語の標準仕様に従っていれば、行っている内容は同一のはずです。

このコードの最初の 2つの if文については、とりあえず置いておくとして、その先の部分を先に説明します。

この中で、新しい標準関数として memcpy関数(⇒リファレンス) が登場しています。
この関数は、第2引数で指定したアドレスから、第1引数で指定したアドレスへ、第3引数で指定したサイズ分だけ、メモリ上のデータをコピーするものです。 文字列専用に特化された strcpy関数(⇒リファレンス)に対する、汎用版と考えられます。 文字列専用ならば終端文字('\0') でコピーするサイズが判断できますが、汎用版だとそうはいかないので、第3引数にサイズを指定する訳です。

ということで、流れとしては、

  1. malloc関数で、新しい領域を確保する。
  2. memcpy関数で、古い領域のデータを、新しい領域へコピーする。
  3. free関数で、古い領域を解放する。
  4. 新しい領域のアドレスを返す。

となります。 従って、古い領域に存在していたデータは、新しい領域にもちゃんと存在します。 しかし、領域は新しく確保しているのですから、アドレスは変わってしまいます

また、古い領域を free関数で解放するので、realloc関数の第1引数に渡すアドレスは、 malloc関数、calloc関数、realloc関数のいずれかで確保されたものでなければなりません
このように、古い領域は realloc関数の中で解放されるので、自分で free関数を呼び出す必要はありません。

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

#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回目の realloc関数の呼び出しが少し不思議な感じがします。 realloc関数は、第1引数に、既に動作に確保されている領域のアドレスを渡すはずなのに、1回目に関しては NULL を渡してしまっています。
実は、realloc関数の第1引数を NULL にした場合は、malloc関数と同じ動作をすることになっています。 これは、少し前に載せた、realloc関数の実装例のコードを見ても明らかです。
ちなみに、第2引数を 0 にした場合は、free関数と同じ動作をします。 ただし、第1引数が NULL でかつ、第2引数が 0 の場合の挙動は不定です

このような仕様は、よくない設計の代表格とされています。 realloc関数はこの仕様のせいで、いかなる実引数を与えても、何かしらの意味を伴うため、エラーが検出できません。 第1引数が NULL のときの挙動はまだ良いとしても、第2引数が 0 のときに free関数の意味になるのは、ちょっとやり過ぎな感じがします。 もはや関数名の「alloc」という部分が生きていませんし。

realloc関数の戻り値を受け取るポインタ変数は、第1引数に渡すポインタ変数とは異なるものにするべきです。 もし、同じ変数を使って、

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

こんな風に使うと、realloc関数が失敗したとき、戻り値の NULL によって、これまで array が保持していたアドレスが上書きされてしまいます。 このとき、array が保持していたアドレスにある領域は、まだ解放されていません。 free関数を呼ぼうにも、array の中身は NULL で上書きされてしまったため、もうアドレスが分からず、解放できない訳です。

そのため、一旦異なるポインタ変数で戻り値で受け取り、realloc関数が成功したとき(戻り値が NULL でないとき)に、 改めて、array へ代入してやるようにします。

実行効率の改善

前の節で見た 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か所の領域を足し合わせれば、十分割り当てが可能な大きさですが、分断されてしまっているため割り当てに失敗してしまいます。
1回の割り当てが分断された複数の領域に対して行われることはありません。 特に、C言語では配列が連続したアドレスに存在することを保証しないといけないため、分断されてしまうと都合が悪いです。

フラグメンテーションは、メモリ領域の確保と解放が繰り返されると起こります。 メモリ確保を6回行い、

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

こういう状態になった後、途中の2か所が解放されれば、

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

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

といったことが考えられます。

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

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

後者は、確保するサイズを 256バイトなどの特定のサイズに限定してしまい、たとえ必要な大きさが 100バイト程度であったとしても、 常に 256バイトで確保してしまうという方法です。
後者の方法の場合、結局、無駄な領域が出来てしまいます。 256バイト確保していても、100バイトしか使っていないのなら、残りの 156バイトが無駄になります。 これは、内部フラグメンテーションと呼ばれる状態で、 これに対して、これまでに解説してきたフラグメンテーションを外部フラグメンテーションと呼びます。
従ってこの方法は、外部フラグメンテーションを改善する代わりに、内部フラグメンテーションを助長すると言えます。


realloc関数は、フラグメンテーションを助長する可能性が高いと言えます。 新しいサイズで領域を確保する際、

  1. malloc関数で、新しい領域を確保する。
  2. memcpy関数で、古い領域のデータを、新しい領域へコピーする。
  3. free関数で、古い領域を解放する。

この順序で処理が進む訳ですから、解放して未使用状態になった古い領域は、断片化状態で取り残される可能性があるのです。
フラグメンテーションが起きること自体が、常に問題である訳ではありませんから、realloc関数を使ってはいけないということではないのですが、 規模の大きいプログラムを開発する際には、こういう状況を招く可能性があることを知っておくべきでしょう。


練習問題

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

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

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

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


解答ページはこちら

参考リンク

更新履歴

'2009/12/25 新規作成。



前の章へ

次の章へ

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

Programming Place Plus のトップページへ