関数ポインタ
関数ポインタとコールバック関数
JavaScript のプログラムで、以下のようなコーディングがよく使われる。このプログラムでは、3と4を加えた結果が出てくるが、関数の引数の中に関数宣言で使われるfunctionキーワードが出てきているが、この意味を正しく理解しているだろうか？
このような (function()…)は、無名関数と呼ばれている。「関数を引数として渡す機能」と、「一度しか使わないような関数にいちいち名前を付けないで関数を使うための機能」であり、このような機能は、関数を引数で渡す機能はC言語では関数ポインタと呼ばれたり、新しいプログラム言語では一般的にラムダ式などと呼ばれる。
// JavaScriptの無名関数の例 3+4=7 を表示
console.log( (function( x , y ) {
return x + y ;
})( 3 , 4 ) ) ; // 無名関数
console.log( ((x,y) => {
return x + y ;
})( 3 , 4 ) ) ; // アロー関数
C言語の関数ポインタの仕組みを理解するために、以下のプログラムを示す。
int add( int x , int y ) {
return x + y ;
}
int mul( int x , int y ) {
return x * y ;
}
void main() {
int (*f)( int , int ) ; // fは2つのintを引数とする関数へのポインタ
f = add ; // f = add( ... ) ; ではないことに注意
printf( "%d¥n" , (*f)( 3 , 4 ) ) ; // 3+4=7
// f( 3 , 4 ) と書いてもいい
f = mul ;
printf( "%d¥n" , (*f)( 3 , 4 ) ) ; // 3*4=12
}
このプログラムでは、関数ポインタの変数 f を定義している。「 int (*f)( int , int ) ; 」 は、“int型の引数を2つ持つ、返り値がint型の関数”へのポインタであり、「 f = add ; 」では、f に加算する関数を覚えている。add に実引数を渡す()がないことに注目。
そして、「 (*f)( 3 , 4 ) ; 」により、実引数を3,4にて f の指し示す add を呼び出し、7 が答えとして求まる。
こういう、関数に「自分で作った関数ポインタ」を渡し、その相手側の関数の中で自分で作った関数を呼び出してもらうテクニックは、コールバックとも呼ばれる。コールバック関数を使うC言語の関数で分かり易い物は、クイックソートを行う qsort() 関数だろう。qsort 関数は、引数にデータを比較するための関数を渡すことで、様々な型のデータの並び替えができる。
#include <stdio.h>
#include <stdlib.h>
// 整数を比較するコールバック関数
int cmp_int( int* a , int* b ) {
return *a - *b ;
}
// 実数を比較するコールバック関数
int cmp_double( double* a , double* b ) {
double ans = *a - *b ;
if ( ans == 0.0 )
return 0 ;
else if ( ans > 0.0 )
return 1 ;
else
return -1 ;
}
// ソート対象の配列
int array_int[ 5 ] = { 123 , 23 , 45 , 11 , 53 } ;
double array_double[ 4 ] = { 1.23 , 12.3 , 32.1 , 3.21 } ;
void main() {
// 整数配列をソート
qsort( array_int , 5 , sizeof( int ) ,
(int(*)(const void*,const void*))cmp_int ) ;
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~この分かりにくい型キャストが必要なのがC言語の面倒な所
for( int i = 0 ; i < 5 ; i++ )
printf( "%d\n" , array_int[ i ] ) ;
// 実数配列をソート
qsort( array_double , 4 , sizeof( double ) ,
(int(*)(const void*,const void*))cmp_double ) ;
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
for( int i = 0 ; i < 5 ; i++ )
printf( "%f\n" , array_double[ i ] ) ;
}
無名関数
コールバック関数を使っていると、データを比較するだけの関数とか簡単な短い処理が使われることが多い。こういった処理を実際に使われる処理と離れた別の場所に記述すると、プログラムが読みづらくなる。この場合には、その場で関数の名前を持たない関数(無名関数)を使用する。(C++の無名関数機能は、最近のC++の文法なのでテストには出さない)
void main() {
int (*f)( int , int ) ; // fは2つのintを引数とする関数へのポインタ
f = []( int x , int y ) { return x + y ; } ; // add を無名関数化
printf( "%d¥n" , (*f)( 3 , 4 ) ) ; // 3+4=7
// mul を無名関数にしてすぐに呼び出す3*4=12
printf( "%d¥n" , []( int x , int y ) { return x * y ; }( 3 , 4 ) ) ;
// メモ：C++11では、ラムダ式=関数オブジェクト
// C++14以降は、変数キャプチャなどの機能が追加されている。
}
動的メモリ管理 malloc() と free()
動的メモリ領域とフリーリスト
動的なメモリ領域(ヒープ領域)は、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_list のリストが長いと malloc() の処理でジャストサイズのメモリブロック検索などの処理効率が悪くなる。
そこで、free() で返却される際には、隣り合うメモリブロックと併合できるかを確認し、大きなメモリブロックになるような処理を行う。さらに、併合によりより free_list の長さも短くできる。
また、隣り合うメモリブロックが併合できるかの判定が簡単になるように、free_listにつなぐ際は、次のメモリブロックへのポインタは、昇順となるように並べる。
一般的には、上記のようにmalloc(),free()を行うが(K&R の mallocアルゴリズム)、mallocのサイズが小さい場合には小さいメモリブロック毎にnextブロックポインタやブロックサイズを記憶する場合、メモリのムダが多い。
そこで、最初に説明した一定サイズのmalloc()の手法で、8byte専用のfreelist,16byte専用のfreelist,32byte専用のfreelistのように2Nbyteのfreelistで管理する。10byteといった中途半端なサイズの時は、それより大きい16byteのfreelistを使う。
ヒープメモリの断片化
ヒープメモリの malloc() , free() を繰り返すと、最悪、以下の図の様に、使用中領域(赤)とfreeされた未使用領域(黒)が交互に並ぶ状態が発生するかもしれない。この場合、全体の未使用領域の合計では十分なサイズでも、小さなメモリブロックばかりとなって、大きなメモリブロックを要求されても十分な大きさのメモリが見つからない状態が発生する場合がある。
この状態をヒープメモリの断片化といい、使用しづらい小さなメモリブロックはヒープホールと呼ばれる。
(補足) 断片化
断片化というと、OSではハードディスクの断片化(フラグメンテーション)を思い浮かべるかもしれない。ハードディスクの断片化とは、ファイル領域の割り当てとファイルの削除を繰り返すことで、ファイルのセクタが不連続となり、アクセス効率が悪くなる現象。OSによっては、ファイル実体の位置を動かすことで断片化を改善できる。以下の図のようにフラグメンテーションを防ぐための実体の移動を行う最適化はデフラグと呼ばれる。
上記の図では、上の青の図が断片化が発生している事例で、a1→a2,a2→a3の時にヘッド移動(シーク時間)が発生する。下の赤の図のように、デフラグ処理を施すことでシーク時間が減らせる。
Windows が 95,98,Me といった時代ではOSが不安定で、フラグメントが多く発生する場合Windowsがフリーズすることが多く、OSが不安定になったらデフラグを実行する…というテクニックが定番だった。最新のWindowsでは、デフラグが自動的に実行されるのでユーザが意識的に実行する機会はほぼなくなった。
