ホーム » 「free」タグがついた投稿
タグアーカイブ: free
fgetsではみ出たら
C言語で長い一行を読み込むのであれば、通常は”それなりに”大きい配列に読み込んでから、strdup() などでデータに応じた大きさで保存する。しかし、それ以上に長い1行を扱いたいのならどうするか…
どうしても長い一行を扱いたいのなら、realloc() などで拡張しながらデータを読み込む。
#include <stdio.h> #include <stdlib.h> #include <string.h> int main() { char buff[ 10 ] ; char*str ; if ( fgets( buff , sizeof( buff ) , stdin ) != NULL ) { // '#include <stdio.h> #include <stdlib.h> #include <string.h> int main() { char buff[ 10 ] ; char*str ; if ( fgets( buff , sizeof( buff ) , stdin ) != NULL ) { // '\0'を覚える必要があるので最大sizeof(buff)-1文字まで読み込まれる int len = strlen( buff ) ; if ( (str = (char*)malloc( len + 1 )) != NULL ) { strcpy( str , buff ) ; // printf( "|%s|\n" , str ) ; // 通常はここまで書けばひとまず十分。 // fgetsは行末文字'\n'まで読み込むのが基本 // 最終文字が'\n'でなかったら、読み残しがある。 while( buff[ len ] != '\n' ) { char*rp ; // '読み残し'を読み込む if ( fgets( buff , sizeof( buff ) , stdin ) == NULL ) break ; len = strlen( buff ) ; // str を realloc() で領域を拡張する // realloc()は、拡張するときは新しくメモリを確保し、 // 格納されているデータをコピーし、元領域を解放してくれる if ( (rp = (char*)realloc( str , strlen( str ) + len + 1 )) == NULL ) break ; else str = rp ; // reallocでは、広げられた領域に元データがコピーされているので、 // 後ろに'読み残し'分を追加する。 strcpy( str + strlen( str ) , buff ) ; // printf( "%s\n" , str ) ; } // 読み込んだ一行を表示 printf( "|%s|\n" , str ) ; free( str ) ; } } }'を覚える必要があるので最大sizeof(buff)-1文字まで読み込まれる int len = strlen( buff ) ; if ( (str = (char*)malloc( len + 1 )) != NULL ) { strcpy( str , buff ) ; // printf( "|%s|\n" , str ) ; // 通常はここまで書けばひとまず十分。 // fgetsは行末文字'\n'まで読み込むのが基本 // 最終文字が'\n'でなかったら、読み残しがある。 while( buff[ len ] != '\n' ) { char*rp ; // '読み残し'を読み込む if ( fgets( buff , sizeof( buff ) , stdin ) == NULL ) break ; len = strlen( buff ) ; // str を realloc() で領域を拡張する // realloc()は、拡張するときは新しくメモリを確保し、 // 格納されているデータをコピーし、元領域を解放してくれる if ( (rp = (char*)realloc( str , strlen( str ) + len + 1 )) == NULL ) break ; else str = rp ; // reallocでは、広げられた領域に元データがコピーされているので、 // 後ろに'読み残し'分を追加する。 strcpy( str + strlen( str ) , buff ) ; // printf( "%s\n" , str ) ; } // 読み込んだ一行を表示 printf( "|%s|\n" , str ) ; free( str ) ; } } }
malloc()とfree()
前回の授業で説明した、alloca() は、スタック領域にデーターを覚えるので、allocaを実行した関数の終了ともに配列領域が消えてしまう。しかし、関数が終わってもそのデータを使いたいといった場合には、malloc()+free()を使う必要がある。
malloc()とfree()
malloc() は、動的(ヒープ領域)にメモリを確保する命令で、データを保存したい時に malloc() を実行し、不要になった時に free() を実行する。
malloc() では、alloca() と同じように、格納したいデータの byte 数を指定する。また、malloc() は、確保したメモリ領域の先頭を返すが、ヒープメモリが残っていない場合 NULL ポインタを返す。処理が終わってデータ領域をもう使わなくなったら、free() で解放する必要がある。
基本的には、確保したメモリ領域を使い終わった後 free() を実行しないと、再利用できないメモリ領域が残ってしまう。こういう処理を繰り返すと、次第にメモリを食いつぶし、仮想メモリ機能によりハードディスクの読み書きで性能が低下したり、最終的にOSが正しく動けなくなる可能性もある。こういった free() 忘れはメモリーリークと呼ばれ、malloc(),free()に慣れない初心者プログラマーによく見られ、注意が必要。
ただし、ヒープメモリ全体は、プロセスの起動と共に確保され(不足すればOSから追加でメモリを分けてもらうこともできる)、プログラムの終了と同時にOSに返却される。このため、malloc()と処理のあとすぐにプロセスが終了するようなプログラムであれば、free() を忘れても問題はない。授業では、メモリーリークによる重大な問題を理解してもらうため、原則 free() は明記する。
文字列を保存する場合
#include <stdlib.h> char* names[ 10 ] ; char buff[ 1000 ] ; // 名前を10件読み込む void inputs() { for( int i = 0 ; i < 10 ; i++ ) { if ( fgets( buff , sizeof( buff ) , stdin ) != NULL ) { names[ i ] = (char*)malloc( strlen(buff)+1 ) ; if ( names[ i ] != NULL ) strcpy( names[ i ] , buff ) ; } } } // 名前を出力する void prints() { for( int i = 0 ; i < 10 ; i++ ) printf( "%s" , names[ i ] ) ; } void main() { // 文字列の入力&出力 inputs() ; prints() ; // 使い終わったら、free() で解放 for( int i = 0 ; i < 10 ; i++ ) free( names[ i ] ) ; }
文字列を保存する場合には、上記の names[i] への代入のような malloc() と strcpy() を組み合わせて使うことが多い。しかし、この一連の処理の関数として、strdup() がある。基本的には、以下のような機能である。
char* strdup( char* s ) { char* p ; if ( (p = (char*)malloc( strlen(s)+1 )) != NULL ) strcpy( p , s ) ; return p ; }また、入力した文字列をポインタで保存する場合、以下のようなプログラムを書いてしまいがちであるが、図に示すような状態になることから、別領域にコピーする必要がある。
char buff[ 1000 ] ; char* name[10] ; for( int i = 0 ; i < 10 ; i++ ) { if ( fgets( buff , sizeof(buff) , stdin ) != NULL ) name = buff ; // ここは、name = strdup( buff ) ; と書くべき。 }
配列に保存する場合
基本的な型の任意サイズの配列を作りたい場合には、malloc() で一括してデータの領域を作成し、その先頭アドレスを用いて配列として扱う。
#include <stdlib.h> void main() { int size ; int* array ; // 処理するデータ件数を入力 scanf( "%d" , &size ) ; // 整数配列を作る if ( (array = (int*)malloc( sizeof(int) * size )) != NULL ) { int i ; for( i = 0 ; i < size ; i++ ) array[i] = i*i ; // あんまり意味がないけど for( i = 0 ; i < size ; i++ ) printf( "%d¥n" , array[i] ) ; // mallocしたら必ずfree free( array ) ; } }
構造体の配列
同じように、任意サイズの構造体(ここではstruct Complex)の配列を作りたいのであれば、mallocの引数のサイズに「sizeof( struct Complex ) * データ件数」を指定すればいい。
後半の array2[] では、ポインタの配列を使った例を示す。この例では、1つの構造体毎に1つのmallocでメモリを確保している。
#include <stdlib.h> struct Complex { double re , im ; } ; // 指定した場所にComplexを読み込む。 int input_Complex( struct Complex* p ) { return scanf( "%lf %lf" , &(p->re) , &(p->im) ) == 2 ; } // 指定したComplexを出力 void print_Complex( struct Complex* p ) { printf( "%lf+j%lf¥n" , p->re , p->im ) ; } void main() { int size ; struct Complex* array ; struct Complex** array2 ; // 処理する件数を入力 scanf( "%d" , &size ) ; // 配列を確保して、データの入力&出力 if ( (array = (struct Complex*)malloc( sizeof(struct Complex) * size )) != NULL ) { int i ; for( i = 0 ; i < size ; i++ ) if ( !input_Complex( &array[i] ) ) break ; for( i = 0 ; i < size ; i++ ) print_Complex( &array[i] ) ; // or printf( "%lf + j%lf\n" , // array[ i ].re , array[ i ].im ) ; // mallocしたら必ずfree free( array ) ; } // ポインタの配列で保存 if ( (array2 = (struct Complex**)malloc( sizeof(struct Complex*) * size)) != NULL ) { int i ; for( i = 0 ; i < size ; i++ ) { // 各データごとにmalloc() array2[ i ] = (struct Complex*)malloc( sizeof( struct Complex ) ) ; if ( array2[ i ] != NULL ) { array2[ i ]->re = (double)i ; array2[ i ]->im = (double)i ; } } // 保存した構造体をすべて表示 for( i = 0 ; i < size ; i++ ) print_Complex( array2[ i ] ) ; // 各データごとに free for( i = 0 ; i < size ; i++ ) free( array2[ i ] ) ; // ポインタの配列を free free( array2 ) ; } }
(おまけ)C++の場合
C言語における malloc() + free () でのプログラミングは、mallocの結果を型キャストしたりするので、間違ったコーディングの可能性がある。このため、C++ では、new 演算子, delete 演算子というものが導入されている。
// 同じ処理をC++で書いたら // 文字列の保存 char str[] = "ABCDE" ; char* pc = new char[ strlen( str ) + 1 ] ; strcpy( pc , str ) ; // pcを使った処理 delete[] pc ; // new型[]を使ったらdelete[] // int配列の保存 int data[] = { 11 , 22 , 33 } ; int* pi ; pi = new int[ 3 ] ; for( int i = 0 ; i < 3 ; i++ ) pi[ i ] = data[ i ] ; // piを使った処理 delete[] pi ; // 構造体の保存 struct Person { char name[ 10 ] ; int age ; } ; Person* pPsn ; pPsn = new Person ; strcpy( pPsn->name , "t-saitoh" ) ; pPsn->age = 55 ; // pPsnを使った処理 delete pPsn ; // new型ならdelete
注意すべき点は、malloc+freeとの違いは、mallocがメモリ確保に失敗した時の処理の書き方。返り値のNULLをチェックする方法は、呼び出し側ですべてでNULLの場合を想定した書き方が必要になり、処理が煩雑となる。C++の new 演算子は、メモリ確保に失敗すると、例外 bad_alloc を投げてくるので、try-catch 文で処理を書く。(上記例はtry-catchは省略)
また、C++ではデストラクタの呼び出しが必要となることから、配列を開放する場合には 「delete[] ポインタ ;」のように、配列を開放することを明記する必要がある。
malloc()とfree()
前回の授業で説明した、alloca() は、スタック領域にデーターを覚えるので、allocaを実行した関数の終了ともに配列領域が消えてしまう。しかし、関数が終わってもそのデータを使いたいといった場合には、malloc()+free()を使う必要がある。
malloc()とfree()
malloc() は、動的(ヒープ領域)にメモリを確保する命令で、データを保存したい時に malloc() を実行し、不要になった時に free() を実行する。
malloc() では、alloca() と同じように、格納したいデータの byte 数を指定する。また、malloc() は、確保したメモリ領域の先頭を返すが、ヒープメモリが残っていない場合 NULL ポインタを返す。処理が終わってデータ領域をもう使わなくなったら、free() で解放する必要がある。
基本的には、確保したメモリ領域を使い終わった後 free() を実行しないと、再利用できないメモリ領域が残ってしまう。こういう処理を繰り返すと、次第にメモリを食いつぶし、仮想メモリ機能によりハードディスクの読み書きで性能が低下したり、最終的にOSが正しく動けなくなる可能性もある。こういった free() 忘れはメモリーリークと呼ばれ、malloc(),free()に慣れない初心者プログラマーによく見られる。
ただし、ヒープメモリ全体は、プロセスの起動と共に確保され(不足すればOSから追加でメモリを分けてもらうこともできる)、プログラムの終了と同時にOSに返却される。このため、malloc()と処理のあとすぐにプロセスが終了するようなプログラムであれば、free() を忘れても問題はない。授業では、メモリーリークによる重大な問題を理解してもらうため、原則 free() は明記する。
文字列を保存する場合
#include <stdlib.h> char* names[ 10 ] ; char buff[ 1000 ] ; // 名前を10件読み込む void inputs() { for( int i = 0 ; i < 10 ; i++ ) { if ( fgets( buff , sizeof( buff ) , stdin ) != NULL ) { names[ i ] = (char*)malloc( strlen(buff)+1 ) ; if ( names[ i ] != NULL ) strcpy( names[ i ] , buff ) ; } } } // 名前を出力する void prints() { for( int i = 0 ; i < 10 ; i++ ) printf( "%s" , names[ i ] ) ; } void main() { // 文字列の入力&出力 inputs() ; prints() ; // 使い終わったら、free() で解放 for( int i = 0 ; i < 10 ; i++ ) free( names[ i ] ) ; }
文字列を保存する場合には、上記の names[i] への代入のような malloc() と strcpy() を組み合わせて使うことが多い。しかし、この一連の処理の関数として、strdup() がある。基本的には、以下のような機能である。
char* strdup( char* s ) { char* p ; if ( (p = (char*)malloc( strlen(s)+1 )) != NULL ) strcpy( p , s ) ; return p ; }また、入力した文字列をポインタで保存する場合、以下のようなプログラムを書いてしまいがちであるが、図に示すような状態になることから、別領域にコピーする必要がある。
char buff[ 1000 ] ; char* name[10] ; for( int i = 0 ; i < 10 ; i++ ) { if ( fgets( buff , sizeof(buff) , stdin ) != NULL ) name = buff ; // ここは、name = strdup( buff ) ; と書くべき。 }
配列に保存する場合
基本的な型の任意サイズの配列を作りたい場合には、malloc() で一括してデータの領域を作成し、その先頭アドレスを用いて配列として扱う。
#include <stdlib.h> void main() { int size ; int* array ; // 処理するデータ件数を入力 scanf( "%d" , &size ) ; // 整数配列を作る if ( (array = (int*)malloc( sizeof(int) * size )) != NULL ) { int i ; for( i = 0 ; i < size ; i++ ) array[i] = i*i ; // あんまり意味がないけど for( i = 0 ; i < size ; i++ ) printf( "%d¥n" , array[i] ) ; // mallocしたら必ずfree free( array ) ; } }
構造体の配列
同じように、任意サイズの構造体(ここではstruct Complex)の配列を作りたいのであれば、mallocの引数のサイズに「sizeof( struct Complex ) * データ件数」を指定すればいい。
後半の array2[] では、ポインタの配列を使った例を示す。この例では、1つの構造体毎に1つのmallocでメモリを確保している。
#include <stdlib.h> struct Complex { double re , im ; } ; // 指定した場所にComplexを読み込む。 int input_Complex( struct Complex* p ) { return scanf( "%lf %lf" , &(p->re) , &(p->re) ) == 2 ; } // 指定したComplexを出力 void print_Complex( struct Complex* p ) { printf( "%lf+j%lf¥n" , p->re , p->im ) ; } void main() { int size ; struct Complex* array ; struct Complex** array2 ; // 処理する件数を入力 scanf( "%d" , &size ) ; // 配列を確保して、データの入力&出力 if ( (array = (struct Complex*)malloc( sizeof(struct Complex) * size )) != NULL ) { int i ; for( i = 0 ; i < size ; i++ ) if ( !input_Complex( &array[i] ) ) break ; for( i = 0 ; i < size ; i++ ) print_Complex( &array[i] ) ; // or printf( "%lf + j%lf\n" , // array[ i ].re , array[ i ].im ) ; // mallocしたら必ずfree free( array ) ; } // ポインタの配列で保存 if ( (array2 = (struct Complex**)malloc( sizeof(struct Complex*) * size)) != NULL ) { int i ; for( i = 0 ; i < size ; i++ ) { // 各データごとにmalloc() array2[ i ] = (struct Complex*)malloc( sizeof( struct Complex ) ) ; if ( array2[ i ] != NULL ) { array2[ i ]->re = (double)i ; array2[ i ]->im = (double)i ; } } // 保存した構造体をすべて表示 for( i = 0 ; i < size ; i++ ) print_Complex( array[ i ] ) ; // 各データごとに free for( i = 0 ; i < size ; i++ ) free( array[ i ] ) ; // ポインタの配列を free free( array2 ) ; } }
(おまけ)C++の場合
C言語における malloc() + free () でのプログラミングは、mallocの結果を型キャストしたりするので、間違ったコーディングの可能性がある。このため、C++ では、new 演算子, delete 演算子というものが導入されている。
// 同じ処理をC++で書いたら // 文字列の保存 char str[] = "ABCDE" ; char* pc = new char[ strlen( str ) + 1 ] ; strcpy( pc , str ) ; // pcを使った処理 delete[] pc ; // new型[]を使ったらdelete[] // int配列の保存 int data[] = { 11 , 22 , 33 } ; int* pi ; pi = new int[ 3 ] ; for( int i = 0 ; i < 3 ; i++ ) pi[ i ] = data[ i ] ; // piを使った処理 delete[] pi ; // 構造体の保存 struct Person { char name[ 10 ] ; int age ; } ; Person* pPsn ; pPsn = new Person ; strcpy( pPsn->name , "t-saitoh" ) ; pPsn->age = 55 ; // pPsnを使った処理 delete pPsn ; // new型ならdelete
注意すべき点は、malloc+freeとの違いは、mallocがメモリ確保に失敗した時の処理の書き方。返り値のNULLをチェックする方法は、呼び出し側ですべてでNULLの場合を想定した書き方が必要になり、処理が煩雑となる。C++の new 演算子は、メモリ確保に失敗すると、例外 bad_alloc を投げてくるので、try-catch 文で処理を書く。(上記例はtry-catchは省略)
動的メモリ管理 malloc() と free()
C言語では、動的メモリ領域をどのように管理していくのか解説する。
局所変数とスタック
局所変数は、関数に入った時に作られるメモリ領域であり、関数の処理を抜けると自動的に開放されるデータ領域である。
関数の中で関数が呼び出されると、スタックには戻り番地情報を保存し、関数に移動する。最初の処理で局所変数領域が確保され、関数を終えると局所変数は開放される。
この局所変数の確保と開放は、最後に確保された領域を最初に開放される(Last In First Out)ことから、スタック上に保存される。
baz()の中で、「*((&c)+8) = 123 ;」を実行したら、bar()のxを書き換えられるかも…
動的メモリ領域とフリーリスト
動的なメモリ領域(ヒープ領域)は、malloc()関数で処理用のメモリを借り、free()関数で使わなくなったメモリを返却する。
この返却されたメモリ領域は、改めて malloc() が呼び出されたときに再利用を行う。この再利用するメモリ領域は、簡単に扱えるようにリスト構造にして保存する。この free された再利用候補のリスト構造は、free_list と呼ばれる。
mallocが一定サイズの場合
仕組みを理解する第1歩として、free_list の考え方を説明するために、malloc() でのメモリサイズが一定として説明を行う。free_list には、貸し出すためのメモリ空間をリスト構造で繋がった状態にしておく。
malloc() が呼び出される度に、free_list の先頭から貸し出すメモリを取り出し(a=malloc(),b=malloc(),c=malloc()まで)、free() が呼び出されると、返却されたメモリは、free_list の先頭につないでおく。
任意サイズのメモリ確保の場合
最初のステップでの説明は、mallocのメモリサイズを一定としていたが、本来は確保するメモリサイズが指定する。この場合は、以下の様に管理されている。mallocで貸し出されるメモリ空間には、ヒープメモリの利用者が使うブロックの前に、次のメモリブロックへのポインタとブロックサイズを記憶する領域をつけておく。こういったメモリブロックを free_list の考え方と同じようにリスト構造となるようにつないで保存されている。
この図の一番下の赤部分は、次のメモリブロックへのポインタとブロックサイズの大きさが20byteの場合の例。
malloc() で、指定されたサイズのものが、free_list の中にあれば、それを使う。malloc(40)
丁度いいサイズが無い場合は、それより大きいメモリブロックの後半を切り分けて、貸し出す。malloc(60)
free()の処理とメモリブロックの併合
この例の最後の処理では、20byte,60byte,40byte,50byteが併合された例。併合後のブロックサイズは、すこしいい加減に書いてある。
使用されていたメモリブロックが free() で返却された場合は、free_list につないでいく。ただし、単純にリストに繋ぐだけであれば、malloc(),free() を繰り返すと、小さなメモリブロックばかりになってしまい、大きいメモリのmalloc()ができなくなる。
そこで、free() で返却される際には、隣り合うメモリブロックと併合できるかを確認し、大きなメモリブロックになるような処理を行う。
また、隣り合うメモリブロックが併合できるかの判定が簡単になるように、free_listにつなぐ際は、次のメモリブロックへのポインタは、昇順となるように並べる。
一般的には、上記のようにmalloc(),free()を行うが(K&Rのmallocアルゴリズム)、mallocのサイズが小さい場合には小さいメモリブロック毎にnextブロックポインタやブロックサイズを記憶する場合、メモリのムダが多い。
そこで、最初に説明した一定サイズのmalloc()の手法で、8byte専用のfreelist,16byte専用のfreelist,32byte専用のfreelistのように2Nbyteのfreelistで管理する。10byteといった中途半端なサイズの時は、それより大きい16byteのfreelistを使う。(dlmallocのアルゴリズム)
ヒープメモリの断片化
ヒープメモリの malloc() , free() を繰り返すと、最悪、以下の図の様に、使用中領域(赤)とfreeされた未使用領域(黒)が交互に並ぶ状態が発生するかもしれない。この場合、全体の未使用領域の合計では十分なサイズでも、小さなメモリブロックばかりとなって、大きなメモリブロックを要求されても十分な大きさのメモリが見つからない状態が発生する場合がある。
この状態をヒープメモリの断片化といい、使用しづらい小さなメモリブロックはヒープホールと呼ばれる。
(補足) 断片化
断片化というと、OSではハードディスクの断片化(フラグメンテーション)を思い浮かべるかもしれない。ハードディスクの断片化とは、ファイル領域の割り当てとファイルの削除を繰り返すことで、ファイルのセクタが不連続となり、アクセス効率が悪くなる現象。OSによっては、ファイル実体の位置を動かすことで断片化を改善できる。以下の図のようにフラグメンテーションを防ぐための実体の移動を行う最適化はデフラグと呼ばれる。
上記の図では、上の青の図が断片化が発生している事例で、a1→a2,a2→a3の時にヘッド移動(シーク時間)が発生する。下の赤の図のように、デフラグ処理を施すことでシーク時間が減らせる。
Windows が 95,98,Me といった時代ではOSが不安定で、フラグメントが多く発生する場合Windowsがフリーズすることが多く、OSが不安定になったらデフラグを実行する…というテクニックが定番だった。最新のWindowsでは、デフラグが自動的に実行されるのでユーザが意識的に実行する機会はほぼなくなった。
malloc()とfree()
前回の授業で説明した、alloca() は、スタック領域にデーターを覚えるので、allocaを実行した関数の終了ともに配列領域が消えてしまう。しかし、関数が終わってもそのデータを使いたいといった場合には、malloc()+free()を使う必要がある。
malloc()とfree()
malloc() は、動的(ヒープ領域)にメモリを確保する命令で、データを保存したい時に malloc() を実行し、不要になった時に free() を実行する。
malloc() では、alloca() と同じように、格納したいデータの byte 数を指定する。また、malloc() は、確保したメモリ領域の先頭を返すが、ヒープメモリが残っていない場合 NULL ポインタを返す。処理が終わってデータ領域をもう使わなくなったら、free() で解放する必要がある。
基本的には、確保したメモリ領域を使い終わった後 free() を実行しないと、再利用できないメモリ領域が残ってしまう。こういう処理を繰り返すと、次第にメモリを食いつぶし、仮想メモリ機能によりハードディスクの読み書きで性能が低下したり、最終的にOSが正しく動けなくなる可能性もある。こういった free() 忘れはメモリーリークと呼ばれ、malloc(),free()に慣れない初心者プログラマーによく見られる。
ただし、ヒープメモリ全体は、プロセスの起動と共に確保され(不足すればOSから追加でメモリを分けてもらうこともできる)、プログラムの終了と同時にOSに返却される。このため、malloc()と処理のあとすぐにプロセスが終了するようなプログラムであれば、free() を忘れても問題はない。授業では、メモリーリークによる重大な問題を理解してもらうため、原則 free() は明記する。
文字列を保存する場合
#include <stdlib.h> char* names[ 10 ] ; char buff[ 1000 ] ; // 名前を10件読み込む void inputs() { for( int i = 0 ; i < 10 ; i++ ) { if ( fgets( buff , sizeof( buff ) , stdin ) != NULL ) { names[ i ] = (char*)malloc( strlen(buff)+1 ) ; if ( names[ i ] != NULL ) strcpy( names[ i ] , buff ) ; } } } // 名前を出力する void prints() { for( int i = 0 ; i < 10 ; i++ ) printf( "%s" , names[ i ] ) ; } void main() { // 文字列の入力&出力 inputs() ; prints() ; // 使い終わったら、free() で解放 for( int i = 0 ; i < 10 ; i++ ) free( names[ i ] ) ; }
文字列を保存する場合には、上記の names[i] への代入のような malloc() と strcpy() を組み合わせて使うことが多い。しかし、この一連の処理の関数として、strdup() がある。基本的には、以下のような機能である。
char* strdup( char* s ) { char* p ; if ( (p = (char*)malloc( strlen(s)+1 )) != NULL ) strcpy( p , s ) ; return p ; }また、入力した文字列をポインタで保存する場合、以下のようなプログラムを書いてしまいがちであるが、図に示すような状態になることから、別領域にコピーする必要がある。
char buff[ 1000 ] ; char* name[10] ; for( int i = 0 ; i < 10 ; i++ ) { if ( fgets( buff , sizeof(buff) , stdin ) != NULL ) name = buff ; // ここは、name = strdup( buff ) ; と書くべき。 }
配列に保存する場合
基本的な型の任意サイズの配列を作りたい場合には、malloc() で一括してデータの領域を作成し、その先頭アドレスを用いて配列として扱う。
#include <stdlib.h> void main() { int size ; int* array ; // 処理するデータ件数を入力 scanf( "%d" , &size ) ; // 整数配列を作る if ( (array = (int*)malloc( sizeof(int) * size )) != NULL ) { int i ; for( i = 0 ; i < size ; i++ ) array[i] = i*i ; // あんまり意味がないけど for( i = 0 ; i < size ; i++ ) printf( "%d¥n" , array[i] ) ; // mallocしたら必ずfree free( array ) ; } }
構造体の配列
同じように、任意サイズの構造体(ここではstruct Complex)の配列を作りたいのであれば、mallocの引数のサイズに「sizeof( struct Complex ) * データ件数」を指定すればいい。
後半の array2[] では、ポインタの配列を使った例を示す。この例では、1つの構造体毎に1つのmallocでメモリを確保している。
#include <stdlib.h> struct Complex { double re , im ; } ; // 指定した場所にComplexを読み込む。 int input_Complex( struct Complex* p ) { return scanf( "%lf %lf" , &(p->re) , &(p->re) ) == 2 ; } // 指定したComplexを出力 void print_Complex( struct Complex* p ) { printf( "%lf+j%lf¥n" , p->re , p->im ) ; } void main() { int size ; struct Complex* array ; struct Complex** array2 ; // 処理する件数を入力 scanf( "%d" , &size ) ; // 配列を確保して、データの入力&出力 if ( (array = (struct Complex*)malloc( sizeof(struct Complex) * size )) != NULL ) { int i ; for( i = 0 ; i < size ; i++ ) if ( !input_Complex( &array[i] ) ) break ; for( i = 0 ; i < size ; i++ ) print_Complex( &array[i] ) ; // or printf( "%lf + j%lf\n" , // array[ i ].re , array[ i ].im ) ; // mallocしたら必ずfree free( array ) ; } // ポインタの配列で保存 if ( (array2 = (struct Complex**)malloc( sizeof(struct Complex*) * size)) != NULL ) { int i ; for( i = 0 ; i < size ; i++ ) { // 各データごとにmalloc() array2[ i ] = (struct Complex*)malloc( sizeof( struct Complex ) ) ; if ( array2[ i ] != NULL ) { array2[ i ]->re = (double)i ; array2[ i ]->im = (double)i ; } } // 保存した構造体をすべて表示 for( i = 0 ; i < size ; i++ ) print_Complex( array[ i ] ) ; // 各データごとに free for( i = 0 ; i < size ; i++ ) free( array[ i ] ) ; // ポインタの配列を free free( array2 ) ; } }
動的メモリ管理 malloc() と free()
C言語では、動的メモリ領域をどのように管理していくのか解説する。
局所変数とスタック
局所変数は、関数に入った時に作られるメモリ領域であり、関数の処理を抜けると自動的に開放されるデータ領域である。
関数の中で関数が呼び出されると、スタックには戻り番地情報を保存し、関数に移動する。最初の処理で局所変数領域が確保され、関数を終えると局所変数は開放される。
この局所変数の確保と開放は、最後に確保された領域を最初に開放される(Last In First Out)ことから、スタック上に保存される。
baz()の中で、「*((&c)+8) = 123 ;」を実行したら、bar()のxを書き換えられるかも…
動的メモリ領域とフリーリスト
動的なメモリ領域(ヒープ領域)は、malloc()関数で処理用のメモリを借り、free()関数で使わなくなったメモリを返却する。
この返却されたメモリ領域は、改めて malloc() が呼び出されたときに再利用を行う。この再利用するメモリ領域は、簡単に扱えるようにリスト構造にして保存する。この free された再利用候補のリスト構造は、free_list と呼ばれる。
mallocが一定サイズの場合
仕組みを理解する第1歩として、free_list の考え方を説明するために、malloc() でのメモリサイズが一定として説明を行う。free_list には、貸し出すためのメモリ空間をリスト構造で繋がった状態にしておく。
malloc() が呼び出される度に、free_list の先頭から貸し出すメモリを取り出し(a=malloc(),b=malloc(),c=malloc()まで)、free() が呼び出されると、返却されたメモリは、free_list の先頭につないでおく。
任意サイズのメモリ確保の場合
最初のステップでの説明は、mallocのメモリサイズを一定としていたが、本来は確保するメモリサイズが指定する。この場合は、以下の様に管理されている。mallocで貸し出されるメモリ空間には、ヒープメモリの利用者が使うブロックの前に、次のメモリブロックへのポインタとブロックサイズを記憶する領域をつけておく。こういったメモリブロックを free_list の考え方と同じようにリスト構造となるようにつないで保存されている。
この図の一番下の赤部分は、次のメモリブロックへのポインタとブロックサイズの大きさが20byteの場合の例。
malloc() で、指定されたサイズのものが、free_list の中にあれば、それを使う。malloc(40)
丁度いいサイズが無い場合は、それより大きいメモリブロックの後半を切り分けて、貸し出す。malloc(60)
free()の処理とメモリブロックの併合
この例の最後の処理では、20byte,60byte,40byte,50byteが併合された例。併合後のブロックサイズは、すこしいい加減に書いてある。
使用されていたメモリブロックが free() で返却された場合は、free_list につないでいく。ただし、単純にリストに繋ぐだけであれば、malloc(),free() を繰り返すと、小さなメモリブロックばかりになってしまい、大きいメモリのmalloc()ができなくなる。
そこで、free() で返却される際には、隣り合うメモリブロックと併合できるかを確認し、大きなメモリブロックになるような処理を行う。
また、隣り合うメモリブロックが併合できるかの判定が簡単になるように、free_listにつなぐ際は、次のメモリブロックへのポインタは、昇順となるように並べる。
一般的には、上記のようにmalloc(),free()を行うが(K&Rのmallocアルゴリズム)、mallocのサイズが小さい場合には小さいメモリブロック毎にnextブロックポインタやブロックサイズを記憶する場合、メモリのムダが多い。
そこで、最初に説明した一定サイズのmalloc()の手法で、8byte専用のfreelist,16byte専用のfreelist,32byte専用のfreelistのように2Nbyteのfreelistで管理する。10byteといった中途半端なサイズの時は、それより大きい16byteのfreelistを使う。(dlmallocのアルゴリズム)
ヒープメモリの断片化
ヒープメモリの malloc() , free() を繰り返すと、最悪、以下の図の様に、使用中領域(赤)とfreeされた未使用領域(黒)が交互に並ぶ状態が発生するかもしれない。この場合、全体の未使用領域の合計では十分なサイズでも、小さなメモリブロックばかりとなって、大きなメモリブロックを要求されても十分な大きさのメモリが見つからない状態が発生する場合がある。
この状態をヒープメモリの断片化といい、使用しづらい小さなメモリブロックはヒープホールと呼ばれる。
(補足) 断片化
断片化というと、OSではハードディスクの断片化(フラグメンテーション)を思い浮かべるかもしれない。ハードディスクの断片化とは、ファイル領域の割り当てとファイルの削除を繰り返すことで、ファイルのセクタが不連続となり、アクセス効率が悪くなる現象。OSによっては、ファイル実体の位置を動かすことで断片化を改善できる。以下の図のようにフラグメンテーションを防ぐための実体の移動を行う最適化はデフラグと呼ばれる。
上記の図では、上の青の図が断片化が発生している事例で、a1→a2,a2→a3の時にヘッド移動(シーク時間)が発生する。下の赤の図のように、デフラグ処理を施すことでシーク時間が減らせる。
Windows が 95,98,Me といった時代ではOSが不安定で、フラグメントが多く発生する場合Windowsがフリーズすることが多く、OSが不安定になったらデフラグを実行する…というテクニックが定番だった。最新のWindowsでは、デフラグが自動的に実行されるのでユーザが意識的に実行する機会はほぼなくなった。
様々なデータの覚え方
前回の malloc() + free() の説明では、実例が少なくイメージがわかりにくいので、名前と年齢のデータを覚える場合の様々な方法を議論する。最後に前期中間のプログラム課題を示す。
malloc+freeの振り返り
// 文字列(可変長)の保存 char str[] = "ABCDE" ; char* pc ; pc = (char*)malloc( strlen( str ) + 1 ) ; if ( pc != NULL ) { // ↑正確に書くと sizeof( char ) * (strlen(str)+1) strcpy( pc , str ) ; //////////////////// // pcを使った処理 //////////////////// free( pc ) ; } // // 可変長の配列の保存 int data[] = { 11 , 22 , 33 } ; int* pi ; pi = (int*)malloc( sizeof( int ) * 3 ) ; if ( pi != NULL ) { for( int i = 0 ; i < 3 ; i++ ) pi[ i ] = data[ i ] ; //////////////////// // piを使った処理 //////////////////// free( pi ) ; } // // 1件の構造体の保存 struct Person { char name[ 10 ] ; int age ; } ; struct Person* pPsn ; pPsn = (struct Person*)malloc( sizeof( struct Person ) ) ; if ( pPsn != NULL ) { strcpy( pPsn->name , "t-saitoh" ) ; pPsn->age = 55 ; //////////////////// // pPsnを使った処理 //////////////////// free( pPsn ) ; }
(おまけ)C++の場合
malloc+freeでのプログラミングは、mallocの結果を型キャストしたりするので、間違ったコーディングの可能性がある。このため、C++ では、new 演算子, delete 演算子というものが導入されている。
// 同じ処理をC++で書いたら // 文字列の保存 char str[] = "ABCDE" ; char* pc = new char[ strlen( str ) + 1 ] ; strcpy( pc , str ) ; // pcを使った処理 delete[] pc ; // new型[]を使ったらdelete[] // int配列の保存 int data[] = { 11 , 22 , 33 } ; int* pi ; pi = new int[ 3 ] ; for( int i = 0 ; i < 3 ; i++ ) pi[ i ] = data[ i ] ; // piを使った処理 delete[] pi ; // 構造体の保存 struct Person { char name[ 10 ] ; int age ; } ; Person* pPsn ; pPsn = new Person ; strcpy( pPsn->name , "t-saitoh" ) ; pPsn->age = 55 ; // pPsnを使った処理 delete pPsn ; // new型ならdelete注意すべき点は、malloc+freeとの違いは、mallocがメモリ確保に失敗した時の処理の書き方。返り値のNULLをチェックする方法は、呼び出し側ですべてでNULLの場合を想定した書き方が必要になり、処理が煩雑となる。C++の new 演算子は、メモリ確保に失敗すると、例外 bad_alloc を投げてくるので、try-catch 文で処理を書く。(上記例はtry-catchは省略)
安全な1行1件のデータ入力
C言語では、scanf などの関数は、バッファオーバーフローなどの危険性があるため、以下のような処理を使うことが多い。fgets は、指定されたファイルから1行分のデータを読み込む。sscanf は、文字列のなかから、scanf() と同じようなフォーマット指定でデータを読み込む。
fgets は、これ以上の入力データが無い場合には、NULL を返す。
(Windowsであれば、キー入力でCtrl+Z を入力、macOSやLinuxであれば、Ctrl+Dを入力)
sscanf() は、読み込めたデータ件数を返す。
int main() { char buff[ 1024 ] ; for( int i = 0 ; i < 3 ; i++ ) { if ( fgets( buff , sizeof( buff ) , stdin ) != NULL ) { char name[ 1024 ] ; int age ; if ( sscanf( buff , "%s%d" , name , &age ) == 2 ) { // 名前と年齢の2つのデータが正しく読み込めたとき ... } } } return 0 ; }
様々なデータの覚え方
配列サイズ固定・名前が固定長
例えば、このデータ構造であれば、table1[] の場合、長い名前にある程度対応できるように nameの配列を100byteにしたりすると、データ件数が少ない場合には、メモリの無駄も多い。
そこで、実際に入力された存在するデータだけをポインタで覚える方法 table2[] という保存方法も考えられる。
// 固定長データのプログラム #define SIZE 50 // 名前(固定長)と年齢の構造体 struct NameAge { char name[ 32 ] ; int age ; } ; struct NameAge table1[ SIZE ] ; int size1 = 0 ; void entry1( char s[] , int a ) { strcpy( table1[ size1 ].name , s ) ; table1[ size1 ].age = a ; size1++ ; } // ポインタで覚える場合 struct NameAge* table2[ SIZE ] ; int size2 = 0 ; void entry2( char s[] , int a ) { table2[size2] = (struct NameAge*)malloc( sizeof( struct NameAge ) ) ; if ( table2[size2] != NULL ) { // なぜ != NULL のチェックを行うのか、説明せよ strcpy( table2[size2]->name , s ) ; table2[size2]->age = a ; size2++ ; } } // データ出力 void print_NA( struct NameAge* p ) { printf( "%s %d¥n" , p->name , p->age ) ; } int main() { // table1に保存 entry1( "t-saitoh" , 55 ) ; entry1( "tomoko" , 44 ) ; print_NA( &table1[0] ) ; print_NA( &table1[1] ) ; // table2に保存 entry2( "t-saitoh" , 55 ) ; entry2( "tomoko" , 44 ) ; print_NA( _________________ ) ; // table2の中身を表示せよ print_NA( _________________ ) ; return 0 ; }
配列サイズ固定・名前が可変長
しかしながら、前回の授業で説明したように、際限なく長い名前があるのであれば、以下の様に名前は、ポインタで保存し、データを保存する時に strdup(…) を使って保存する方法もあるだろう。
// 名前が可変長のプログラム // 名前(固定長)と年齢の構造体 struct NamePAge { char* name ; // ポインタで保存 int age ; } ; struct NamePAge table3[ SIZE ] ; int size3 = 0 ; void entry3( char s[] , int a ) { table3[ size3 ].name = strdup( s ) ; // ★★★★ table3[ size3 ].age = a ; size3++ ; } // ポインタで覚える場合 struct NamePAge* table4[ SIZE ] ; int size4 = 0 ; void entry4( char s[] , int a ) { table4[size4] = (struct NamePAge*)malloc( ____________________ ) ; if ( table4[size4] != NULL ) { // ↑適切に穴埋めせよ table4[size4]->name = strdup( s ) ; // ★★★★ _________________________________ ; // ←適切に穴埋めせよ size4++ ; } } // データ出力 void print_NPA( struct NameAge* p ) { printf( "%s %d¥n" , ____________ , ____________ ) ; } // ↑適切に穴埋めせよ int main() { // table3に保存 entry3( "t-saitoh" , 55 ) ; entry3( "jyugemu jyugemu ..." , 44 ) ; print_NPA( _________________ ) ; // table3[] の中身を表示せよ。 print_NPA( _________________ ) ; // table4に保存 entry4( "t-saitoh" , 55 ) ; entry4( "jyugemu jyugemu ..." , 44 ) ; print_NPA( table4[0] ) ; print_NPA( table4[1] ) ; return 0 ; }
データ件数が可変長ならば
前述のプログラムでは、データ件数全体は、SIZE という固定サイズを想定していた。しかしながら、データ件数自体も数十件かもしれないし、数万件かもしれないのなら、配列のサイズを可変長にする必要がある。
struct NamePAge* table5 ; int size5 = 0 ; void entry5( char s[] , int a ) { strcpy( table5[ size5 ].name , s ) ; table5[ size5 ].age = a ; size5++ ; } int main() { // table5に保存 table5 = (struct NameAge*)malloc( sizeof( struct NameAge ) * 2 ) ; if ( table5 != NULL ) { entry5( "t-saitoh" , 55 ) ; entry5( "tomoko" , 44 ) ; } return 0 ; }
メモリの管理に十分気を付ける必要があるが、名前の長さも配列全体のサイズも可変長であれば、以下のようなイメージ図のデータを作る必要があるだろう。(JavaScriptやJavaといった言語ではデータのほとんどがこういったポインタで管理されている)
レポート課題
授業での malloc , free を使ったプログラミングを踏まえ、以下のレポートを作成せよ。
以下のデータのどれか1つについて、データを入力し、何らかの処理を行うこと。
課題は、原則として、(自分の出席番号%3)+1 についてチャレンジすること。
- 名前と電話番号
- 名前と生年月日
- 名前と身長・体重
このプログラムを作成するにあたり、以下のことを考慮しmallocを適切に使うこと。
名前は、長い名前の人が混ざっているかもしれない。
保存するデータ件数は、10件かもしれない1000件かもしれない。(データ件数は、処理の最初に入力すること。)
ただし、mallocの理解に自信がない場合は、名前もしくはデータ件数のどちらか一方は固定値でも良い。
レポートには、(a)プログラムリスト, (b)プログラムの説明, (c)正しく動いたことがわかる実行例, (d)考察 を記載すること。
考察には、自分のプログラムが正しく動かない事例はどういう状況でなぜ動かないのか…などを検討したり、プログラムで良くなった点はどういう所かを説明すること。
効率のよいメモリ使用と動的メモリ/スタック/malloc+free
次にメモリの利用効率の話について解説する。
配列宣言でサイズは定数
C言語では、配列宣言を行う時は、本来ならば、配列サイズに変数を使うことはできない。
最近のC(C99)では、実は下記のようなものは、裏で後述のalloca()を使って動いたりするので普通に書けるけど…。(^_^;
void foo( int size ) { int array[ size ] ; // エラー for( int i = 0 ; i < size ; i++ ) array[ i ] = i*i ; } int main() { foo( 3 ) ; foo( 4 ) ; return 0 ; }
メモリ利用の効率
配列サイズには、定数式しか使えないので、1クラスの名前のデータを覚えるなら、以下のような宣言が一般的であろう。
#define MEMBER_SIZE 50 #define NAME_LENGTH 20 char name[ MEMBER_SIZE ][ NAME_LENGTH ] ;
しかしながら、クラスに寿限無とか銀魂の「ビチグソ丸」のような名前の人がいたら、20文字では足りない。(“t-saitoh”くんは配列サイズ9byte、”寿限無”くんは配列220byte といった使い方はできない) また、クラスの人数も、巨大大学の学生全員を覚えたいとい話であれば、 10000人分を用意する必要がある。 ただし、10000人の”寿限無”ありを考慮して、5Mbyte の配列を準備したのに、与えられたデータ量が100件で終わってしまうなら、その際のメモリの利用効率は極めて低い。
このため、最も簡単な方法は、以下のように巨大な文字配列に先頭から名前を入れていき、 文字ポインタ配列に、各名前の先頭の場所を入れる方式であれば、 途中に寿限無がいたとしても、問題はない。
char array[2000] = "ayuka¥0mitsuki¥0t-saitoh¥0tomoko¥0....." ; char *name[ 50 ] = { array+0 , array+6 , array+14 , array+23 , ... } ;
この方式であれば、2000byte + 4byte(32bitポインタ)×50 のメモリがあれば、 無駄なメモリ空間も必要最低限とすることができる。
参考:
寿限無(文字数:全角103文字)
さる御方、ビチクソ丸(文字数:全角210文字)
引用Wikipedia(2020年5月リンク切れてる…)
大きな配列を少しづつ貸し出す処理
// 巨大な配列 char str[ 10000 ] ; // 使用領域の末尾(初期値は巨大配列の先頭) char* sp = str ; // 文字列を保存する関数 char* entry( char* s ) { char* ret = sp ; strcpy( sp , s ) ; sp += strlen( s ) + 1 ; return ret ; } int main() { char* names[ 10 ] ; names[ 0 ] = entry( "saitoh" ) ; names[ 1 ] = entry( "jugemu-jugemu-gokono-surikire..." ) ; return 0 ; } // str[] s a i t o h ¥0 j u g e m u - .... ¥0 // ↑ ↑ // names[0] names[1]
このプログラムでは、貸し出す度に、sp のポインタを後ろに移動していく。
スタック
この貸し出す度に、末尾の場所をずらす方式にスタックがある。
int stack[ 100 ] ; int* sp = stack ; void push( int x ) { *sp = x ; // 1行で書くなら sp++ ; // *sp++ = x ; } int pop() { sp-- ; return *sp ; // return *(--sp) ; } int main() { push( 1 ) ; push( 2 ) ; push( 3 ) ; printf( "%d¥n" , pop() ) ; printf( "%d¥n" , pop() ) ; printf( "%d¥n" , pop() ) ; return 0 ; }
スタックは、最後に保存したデータを最初に取り出せる(Last In First Out)から、LIFO とも呼ばれる。
このデータ管理方法は、最後に呼び出した関数が最初に終了することから、関数の戻り番地の保存や、最後に確保した局所変数が最初に不要となることから、局所変数の管理に利用されている。
alloca() 関数
局所変数と同じスタック上に、一時的にデータを保存する配列を作り、関数が終わると不要になる場合には、alloca() 関数が便利である。alloca の引数には、必要なメモリの byte 数を指定する。100個の整数データを保存するのであれば、int が 32bit の 4byte であれば 400byte を指定する。ただし、int 型は16bitコンピュータなら2byteかもしれないし、64bitコンピュータなら、8byte かもしれないので、sizeof() 演算子を使い、100 * sizeof( int ) と書くべきである。
#include <alloca.h> void foo( int size ) { int* p ; // p = (int*)alloca( sizeof( int ) * size ) ; for( int i = 0 ; i < size ; i++ ) p[ i ] = i*i ; } int main() { foo( 3 ) ; foo( 4 ) ; return 0 ; }
alloca() は、指定された byte 数のデータ領域の先頭ポインタを返すが、その領域を 文字を保存するために使うか、int を保存するために使うかは alloca() では解らない。alloca() の返り値は、使う用途に応じて型キャストが必要である。文字を保存するなら、(char*)alloca(…) 、 intを保存するなら (int*)alloca(…) のように使う。
ただし、関数内で alloca で確保したメモリは、その関数が終了すると、その領域は使えなくなる。このため、最後に alloca で確保したメモリが、最初に不要となる…ような使い方でしか使えない。
malloc()とfree()
malloc() は、動的(ヒープ領域)にメモリを確保する命令で、データを保存したい時に malloc() を実行し、不要になった時に free() を実行する。
malloc() では、alloca() と同じように、格納したいデータの byte 数を指定する。また、malloc() は、確保したメモリ領域の先頭を返すが、ヒープメモリが残っていない場合 NULL ポインタを返す。処理が終わってデータ領域をもう使わなくなったら、free() で解放する必要がある。
基本的には、確保したメモリ領域を使い終わった後 free() を実行しないと、再利用できないメモリ領域が残ってしまう。こういう処理を繰り返すと、次第にメモリを食いつぶし、仮想メモリ機能によりハードディスクの読み書きで性能が低下したり、最終的にOSが正しく動けなくなる可能性もある。こういった free() 忘れはメモリーリークと呼ばれ、malloc(),free()に慣れない初心者プログラマーによく見られる。
ヒープメモリは、プロセスの起動と共に確保され、プログラムの終了と同時にOSに返却される。このため、malloc()と処理のあとすぐにプロセスが終了するようなプログラムであれば、free() を忘れても問題はない。授業では、メモリーリークによる重大な問題を理解してもらうため、原則 free() は明記する。
文字列を保存する場合
#include <stdlib.h> char* names[ 10 ] ; char buff[ 1000 ] ; // 名前を10件読み込む void inputs() { for( int i = 0 ; i < 10 ; i++ ) { if ( fgets( buff , sizeof( buff ) , stdin ) != NULL ) { names[ i ] = (char*)malloc( strlen(buff)+1 ) ; if ( names[ i ] != NULL ) strcpy( names[ i ] , buff ) ; } } } // 名前を出力する void prints() { for( int i = 0 ; i < 10 ; i++ ) printf( "%s" , names[ i ] ) ; } int main() { // 文字列の入力&出力 inputs() ; prints() ; // 使い終わったら、free() で解放 for( int i = 0 ; i < 10 ; i++ ) free( names[ i ] ) ; return 0 ; }
文字列を保存する場合には、上記の names[i] への代入のような malloc() と strcpy() を使うことが多い。
このための専用の関数として、strdup() がある。基本的には、以下のような機能である。char* strdup( char* s ) { char* p ; if ( (p = (char*)malloc( strlen(s)+1 )) != NULL ) strcpy( p , s ) ; return p ; }また、入力した文字列をポインタで保存する場合、以下のようなプログラムを書いてしまいがちであるが、図に示すような状態になることから、別領域にコピーする必要がある。
char buff[ 1000 ] ; char* name[10] ; for( int i = 0 ; i < 10 ; i++ ) { if ( fgets( buff , sizeof(buff) , stdin ) != NULL ) name = buff ; }
配列に保存する場合
任意サイズの配列を作りたい場合には、malloc() で一括してデータの領域を作成し、その先頭アドレスを用いて配列として扱う。
#include <stdlib.h> void main() { int size ; int* array ; // 処理するデータ件数を入力 scanf( "%d" , &size ) ; // 整数配列を作る if ( (array = (int*)malloc( sizeof(int) * size )) != NULL ) { int i ; for( i = 0 ; i < size ; i++ ) array[i] = i*i ; // あんまり意味がないけど for( i = 0 ; i < size ; i++ ) printf( "%d¥n" , array[i] ) ; // mallocしたら必ずfree free( array ) ; } }
構造体の配列
同じように、任意サイズの構造体の配列を作りたいのであれば、配列サイズに「sizeof( struct Complex ) * データ件数」を指定すればいい。
#include <stdlib.h> struct Complex { double re , im ; } ; // 指定した場所にComplexを読み込む。 int input_Complex( struct Complex* p ) { return scanf( "%f %f" , &(p->re) , &(p->re) ) == 2 ; } // 指定したComplexを出力 void print_Complex( struct Complex* p ) { printf( "%f+j%f¥n" , p->re , p->im ) ; } void main() { int size ; struct Complex* array ; // 処理する件数を入力 scanf( "%d" , &size ) ; // 配列を確保して、データの入力&出力 if ( (array = (struct Complex*)malloc( sizeof(struct Complex) * size )) != NULL ) { int i ; for( i = 0 ; i < size ; i++ ) if ( !input_Complex( &array[i] ) ) break ; for( i = 0 ; i < size ; i++ ) print_Complex( &array[i] ) ; // mallocしたら必ずfree free( array ) ; } }
malloc()とfree()
malloc()とfree()
malloc() は、動的(ヒープ領域)にメモリを確保する命令で、データを保存したい時に malloc() を実行し、不要になった時に free() を実行する。
malloc() では、alloca() と同じように、格納したいデータの byte 数を指定する。また、malloc() は、確保したメモリ領域の先頭を返すが、ヒープメモリが残っていない場合 NULL ポインタを返す。処理が終わってデータ領域をもう使わなくなったら、free() で解放する必要がある。
基本的には、確保したメモリ領域を使い終わった後 free() を実行しないと、再利用できないメモリ領域が残ってしまう。こういう処理を繰り返すと、次第にメモリを食いつぶし、仮想メモリ機能によりハードディスクの読み書きで性能が低下したり、最終的にOSが正しく動けなくなる可能性もある。こういった free() 忘れはメモリーリークと呼ばれ、malloc(),free()に慣れない初心者プログラマーによく見られる。
ヒープメモリは、プロセスの起動と共に確保され、プログラムの終了と同時にOSに返却される。このため、malloc()と処理のあとすぐにプロセスが終了するようなプログラムであれば、free() を忘れても問題はない。授業では、メモリーリークによる重大な問題を理解してもらうため、原則 free() は明記する。
文字列を保存する場合
#include <stdlib.h> char* names[ 10 ] ; char buff[ 1000 ] ; // 名前を10件読み込む void inputs() { for( int i = 0 ; i < 10 ; i++ ) { if ( fgets( buff , sizeof( buff ) , stdin ) != NULL ) { names[ i ] = (char*)malloc( strlen(buff)+1 ) ; if ( names[ i ] != NULL ) strcpy( names[ i ] , buff ) ; } } } // 名前を出力する void prints() { for( int i = 0 ; i < 10 ; i++ ) printf( "%s" , names[ i ] ) ; } void main() { // 文字列の入力&出力 inputs() ; prints() ; // 使い終わったら、free() で解放 for( int i = 0 ; i < 10 ; i++ ) free( names[ i ] ) ; }
文字列を保存する場合には、上記の names[i] への代入のような malloc() と strcpy() を使うことが多い。
このための専用の関数として、strdup() がある。基本的には、以下のような機能である。char* strdup( char* s ) { char* p ; if ( (p = (char*)malloc( strlen(s)+1 )) != NULL ) strcpy( p , s ) ; return p ; }また、入力した文字列をポインタで保存する場合、以下のようなプログラムを書いてしまいがちであるが、図に示すような状態になることから、別領域にコピーする必要がある。
char buff[ 1000 ] ; char* name[10] ; for( int i = 0 ; i < 10 ; i++ ) { if ( fgets( buff , sizeof(buff) , stdin ) != NULL ) name = buff ; }
配列に保存する場合
任意サイズの配列を作りたい場合には、malloc() で一括してデータの領域を作成し、その先頭アドレスを用いて配列として扱う。
#include <stdlib.h> void main() { int size ; int* array ; // 処理するデータ件数を入力 scanf( "%d" , &size ) ; // 整数配列を作る if ( (array = (int*)malloc( sizeof(int) * size )) != NULL ) { int i ; for( i = 0 ; i < size ; i++ ) array[i] = i*i ; // あんまり意味がないけど for( i = 0 ; i < size ; i++ ) printf( "%d¥n" , array[i] ) ; // mallocしたら必ずfree free( array ) ; } }
構造体の配列
同じように、任意サイズの構造体の配列を作りたいのであれば、配列サイズに「sizeof( struct Complex ) * データ件数」を指定すればいい。
#include <stdlib.h> struct Complex { double re , im ; } ; // 指定した場所にComplexを読み込む。 int input_Complex( struct Complex* p ) { return scanf( "%f %f" , &(p->re) , &(p->re) ) == 2 ; } // 指定したComplexを出力 void print_Complex( struct Complex* p ) { printf( "%f+j%f¥n" , p->re , p->im ) ; } void main() { int size ; struct Complex* array ; // 処理する件数を入力 scanf( "%d" , &size ) ; // 配列を確保して、データの入力&出力 if ( (array = (struct Complex*)malloc( sizeof(struct Complex) * size )) != NULL ) { int i ; for( i = 0 ; i < size ; i++ ) if ( !input_Complex( &array[i] ) ) break ; for( i = 0 ; i < size ; i++ ) print_Complex( &array[i] ) ; // mallocしたら必ずfree free( array ) ; } }
効率のよいメモリ使用と動的メモリ確保
次にメモリの利用効率の話について解説する。
配列宣言でサイズは定数
C言語では、配列宣言を行う時は、配列サイズに変数を使うことはできない。
最近のC(C99)では、実は下記のようなものは、裏で後述のalloca()を使って動いたりする。(^_^;
void foo( int size ) { int array[ size ] ; // エラー for( int i = 0 ; i < size ; i++ ) array[ i ] = i*i ; } void main() { foo( 3 ) ; foo( 4 ) ; }
メモリ利用の効率
配列サイズには、定数式しか使えないので、1クラスの名前のデータを覚えるなら、以下のような宣言が一般的であろう。
#define MEMBER_SIZE 50 #define NAME_LENGTH 20 char name[ MEMBER_SIZE ][ NAME_LENGTH ] ;
しかしながら、クラスに寿限無とか銀魂の「ビチグソ丸」のような名前の人がいたら、20文字では足りない。(“t-saitoh”くんは配列サイズ9byte、”寿限無”くんは配列220byte といった使い方はできない) また、クラスの人数も、巨大大学の学生全員を覚えたいとい話であれば、 10000人分を用意する必要がある。 ただし、10000人の”寿限無”ありを考慮して、5Mbyte の配列を準備したのに、与えられたデータ量が100件で終わってしまうなら、その際のメモリの利用効率は極めて低い。
このため、最も簡単な方法は、以下のように巨大な文字配列に先頭から名前を入れていき、 文字ポインタ配列に、各名前の先頭の場所を入れる方式であれば、 途中に寿限無がいたとしても、問題はない。
char array[2000] = "ayuka¥0mitsuki¥0t-saitoh¥0tomoko¥0....." ; char *name[ 50 ] = { array+0 , array+6 , array+14 , array+23 , ... } ;
この方式であれば、2000byte + 4byte(32bitポインタ)×50 のメモリがあれば、 無駄なメモリ空間も必要最低限とすることができる。
参考:
寿限無(文字数:全角103文字)
さる御方、ビチクソ丸(文字数:全角210文字)
引用Wikipedia
大きな配列を少しづつ貸し出す処理
// 巨大な配列 char str[ 10000 ] ; // 使用領域の末尾(初期値は巨大配列の先頭) char* sp = str ; // 文字列を保存する関数 char* entry( char* s ) { char* ret = sp ; strcpy( sp , s ) ; sp += strlen( s ) + 1 ; return ret ; } int main() { char* names[ 10 ] ; names[ 0 ] = entry( "saitoh" ) ; names[ 1 ] = entry( "jugemu-jugemu-gokono-surikire..." ) ; return 0 ; } // str[] s a i t o h ¥0 t o m o k o ¥0 // ↑ ↑ // names[0] names[1]
このプログラムでは、貸し出す度に、sp のポインタを後ろに移動していく。
スタック
この貸し出す度に、末尾の場所をずらす方式にスタックがある。
int stack[ 100 ] ; int* sp = stack ; void push( int x ) { *sp = x ; // 1行で書くなら sp++ ; // *sp++ = x ; } int pop() { sp-- ; return *sp ; // return *(--sp) ; } int main() { push( 1 ) ; push( 2 ) ; push( 3 ) ; printf( "%d¥n" , pop() ) ; printf( "%d¥n" , pop() ) ; printf( "%d¥n" , pop() ) ; return 0 ; }
スタックは、最後に保存したデータを最初に取り出せる(Last In First Out)から、LIFO とも呼ばれる。
このデータ管理方法は、最後に呼び出した関数が最初に終了することから、関数の戻り番地の保存や、最後に確保した局所変数が最初に不要となることから、局所変数の管理に利用されている。
alloca() 関数
局所変数と同じスタック上に、一時的にデータを保存する配列を作り、関数が終わると不要になる場合には、alloca() 関数が便利である。alloca の引数には、必要なメモリの byte 数を指定する。100個の整数データを保存するのであれば、int が 32bit の 4byte であれば 400byte を指定する。ただし、int 型は16bitコンピュータなら2byteかもしれないし、64bitコンピュータなら、8byte かもしれないので、sizeof() 演算子を使い、100 * sizeof( int ) と書くべきである。
#include <alloca.h> void foo( int size ) { int* p ; // p = (int*)alloca( sizeof( int ) * size ) ; for( int i = 0 ; i < size ; i++ ) p[ i ] = i*i ; } void main() { foo( 3 ) ; foo( 4 ) ; }
alloca() は、指定された byte 数のデータ領域の先頭ポインタを返すが、その領域を 文字を保存するために使うか、int を保存するために使うかは alloca() では解らない。alloca() の返り値は、使う用途に応じて型キャストが必要である。文字を保存するなら、(char*)alloca(…) 、 intを保存するなら (int*)alloca(…) のように使う。
ただし、関数内で alloca で確保したメモリは、その関数が終了すると、その領域は使えなくなる。このため、最後に alloca で確保したメモリが、最初に不要となる…ような使い方でしか使えない。