ネットワークとセキュリティ
前回の授業では、バックエンドのプログラムの問題によるセキュリティ問題を説明した。今回は、ネットワークの物理的な接続方法などの話を中心にセキュリティについて説明を行う。
ネットワークからの攻撃とFireWall
脆弱性とバッファオーバーフロー
プログラムには、何らかのバグが潜んでいる可能性があり、悪用すると悪意のプログラムの実行や、情報の漏えい、システム異常を発生させサービスができなくするなどの脆弱性があって、悪意のある利用者から攻撃をうける可能性がある。
例えば、下記のようなC言語のプログラムは、配列をはみ出るようなデータを与えることで、関数の戻り番地を破壊させ、はみ出た部分に送り込んだ悪意のプログラムを実行させることが可能となる。このような入力用のデータ領域(バッファ)をはみ出させる攻撃はバッファオーバーフローと呼ばれる。
なお、最近のC言語のライブラリでは、上記のようなバッファオーバーフロー攻撃が一般的であることから、ASLR(Address Space Layout Randomization)により、スタック領域などの位置をランダム化することで、バッファオーバーフローによる攻撃が失敗するようになっている。
ルータとFireWall
外部にサービスを提供するようなシステムで、何らかの脆弱性のあるプログラムが使われていると、外部からのネットワーク接続で悪意のあるプログラム(マルウェア)を実行させられてしまうかもしれない。
このため、コンピュータでは不必要なプログラム(ネットワークサービス)は、起動されないようにする必要がある。もしくは、そのサービスは外部から利用できないように、途中のルータで FireWall(防火壁) を設置する。
FireWall では、(1)攻撃の可能性のあるIPアドレスからの接続を拒否、(2)外部に公開していないネットワークサービスのポート番号の接続を拒否といった方法をとる(拒否リスト方式)。もっと厳しい対策であれば、(3)特定のIPアドレスの機器からのみ接続を許可、(4)許可されているネットワークサービスのポート番号だけからだけ許可する方式をとる(許可リスト方式)
外部に公開する必要のないサービスがFireWallなどで正しく保護されていないと、攻撃をうける可能性がある。
ネットワーク接続のための装置
ルータやFireWallなどの仕組みをもう少し理解するために、組織内でネットワークを接続するための機器とその機能について改めて確認する。
ルータとは
元々の有線LANでは、1本のケーブルを時分割多重で共有しながら通信を行う。このため、瞬間的にはとある機器がネットワークを使用している時は、他の機器はデータ通信ができなくなる。この1本の線を大量の機器で使おうとすると、機器が使えるタイミングは減ってしまう。そこで、1本の線に直接接続する機器を分割したサブネットに分けて、必要な時だけ隣接するサブネットにパケットを中継するルータ or ブリッジが重要となる。
ルータは、隣接するサブネットのネットワーク番号(IPアドレスとサブネットマスク)を確認し、パケットを流す先を決定する。このネットワーク番号(IPアドレスとサブネットマスクの論理積)と中継を依頼するゲートウェイ(転送先)の一覧をルーティングテーブルと呼ぶ。
組織内のルータであれば、ネットワークの構造に合わせてあらかじめルーティングテーブルを定義しておく(静的ルーティング)。組織と組織を接続するようなルータは、自分に送ってほしいネットワーク番号の情報を相互に交換している(動的ルーティング)。
ブリッジとHUB
スイッチングHUB
機器を接続するための古いHUB(ダムHUB)では、通信中は他の機器の通信ができず効率が悪い。最近のHUBでは、通信する相手に応じて、内部のネットワークケーブルをスイッチのように接続・分離することができるスイッチングHUBを用いる。通信相手の識別には、一般的にMACアドレスが用いられる。(レイヤ2でのスイッチングHUB)
家庭用のスイッチングHUBは、特に細かい設定などは不要で管理機能が無いものは、アン マネージド スイッチングHUBと呼ばれる。
L2スイッチとL3スイッチ
サブネットに分割し、それぞれに異なるネットワーク番号を割り振り、中継するルータで FireWall を機能させることで、セキュリティを高めることが行われる。しかし、性能の高いスイッチングHUBは高価でもあり、1つのHUBに異なるネットワークを接続する必要がでてくることもある。この場合、IPアドレスを異なるネットワークの番号を偽装されると、データが盗み見られるかもしれない。
こういった相互に分離すべきネットワークであっても、柔軟なネットワーク構成とするためには、VLAN機能を持った L2スイッチ(レイヤ2スイッチングHUB) が使われる。タグVLAN機能付きのL2スイッチでは、特定のポートにVLANのタグ番号を割り当て、ポートに入る時にパケットに VLAN のタグ情報を付加し、そのパケットは同じ VLAN のタグをもつポートからしかデータを取り出せない。
L2スイッチ(レイヤ2スイッチ)は、機器のMACアドレスやパケットに付けられたVLANのタグ番号の情報(レイヤ2=データリンク層)でパケットの流れを制御している(下記OSI参照モデルの表を参照)。最近では、許可されていない機器がネットワークに侵入する不正侵入を防ぐために、登録されていないMACアドレスのパケットを通さないといった機能がある。
OSI参照モデルとレイヤ 第7層 アプリケーション層 アプリケーションの種類の規定 第6層 プレゼンテーション層 データフォーマットの交換 第5層 セッション層 コネクションの確立や切断などの管理 第4層 トランスポート層 パケットの分割合成や再送といった管理(TCP) 第3層 ネットワーク層 隣接するネットワーク間の通信(IPアドレス) 第2層 データリンク層 直接接続された機器間の通信(MACアドレス) 第1層 物理層 物理的な接続方法(コネクタや電圧など)
スイッチングHUBの中には、レイヤ3(IPアドレス)の情報でパケットの流れを制御するものもある。こういったスイッチは、L3スイッチ(レイヤ3スイッチ)と呼ばれるが、機能的にはルータと同じである。
一般的には、LANとWANを接続するための機器はルータ、LAN内部のネットワークを分離するためのものはL3スイッチと呼ぶ。
インターネットと接続するルータの機能
ネットワーク通信のIPアドレスとポート番号
クライアントの機器と通信相手との通信では、通信相手のIPアドレスとポート番号を指定してパケットを送出するが、処理結果を送信元に送り返すために、送信元のIPアドレスとポート番号が付加されている。送信元ではポート番号は、通信でよく使われる0~1023までのポート番号(ウェルノウンポート)以外で、1024~65535のポート番号(エフェメラルポート)の中から使われていないものをランダムに選んで使う。
送信相手に届いたパケットの返信データには、送信元と送信相手のIPアドレスとポート番号を入れ替えたものを割り当てることで、送信元にパケットが戻ってくる。
- DIP = 送信先IPアドレス、DP = 送信先ポート番号
- SIP = 送信元IPアドレス、SP = 送信元ポート番号
NAT(Network Address Translation)
現在広く使われているIPv4アドレス(32bit)では、40億台の機器間の通信しかできない。このため、組織内だけで使われるIPアドレス(プライベートIPアドレス)を使い、インターネットではグローバルIPアドレスを使う。
プライベートIPアドレス クラスA/8 10.0.0.0~10.255.255.255 大規模組織向け クラスB/12 172.16.0.0~172.31.255.255 中規模組織向け クラスC/16 192.168.0.0~192.168.255.255 家庭用ルータ向け
組織内のLANからインターネット(WAN)に接続する際には、プライベートアドレスをグローバルアドレスに変換するNAT(Network Address Translation)の機能が使われる。
NATの問題点
しかし、インターネットの内側で異なる機器で同じポート番号が割り振られると、戻ってきたパケットをどちらの機器に送ればいいのか区別できなくなる。
NAPT(Netowrk Address and Port Translation)
そこで、最近のNATでは、IPアドレスの変換だけでなくポート番号の付け替えも行われる。この機能は正式には NAPT(Network Address and Port Translation) と呼ぶが、単に NAT と呼ぶことも多い。Linuxでは、NAPTの実装をIPマスカレードと呼ぶ。
FireWall と DMZ
組織内で外部に公開しているサーバがある場合は、以下の図のような構成にするかもしれない。しかし、このようなネットワーク構成では、FireWallの内側の公開サーバが攻撃されて、踏み台となった場合、組織内のPCが簡単に攻撃をうけてしまう。
そこで、外部からの接続を行う DMZ(De-Militarized Zone 非武装地帯) を設け、外部公開用の公開サーバは DMZ 内に設置する。外部とつながる FireWall では、外部からのパケットは DMZ に流れるように構成する。DMZ 内のサーバが踏み台になった場合を想定し、組織内のルータでは DMZ のサーバと組織内PCは通信できないように FireWall を2重に設置する。
様々なデータの覚え方のレポート課題
前回の 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 ) ; }
安全な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 NamePAge* 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)考察 を記載すること。
考察には、自分のプログラムが正しく動かない事例はどういう状況でなぜ動かないのか…などを検討したり、プログラムで良くなった点はどういう所かを説明すること。
プログラム言語(C言語)の基礎
学際科目の情報制御基礎において、学科間でプログラミングの初歩の理解差があるので、簡単なC言語プログラミングの基礎の説明。
Hello World
“Hello World”と表示するだけのC言語プログラムは以下のようになる。
// コメントの書き方1 // "//"で始まる行は、プログラムの説明(コメント) /* コメントの書き方2 */ // "/*"から"*/"で囲まれる範囲もコメント #include <stdio.h> // #で始まる行はプリプロセッサ行 // stdio.h には、入出力関数の説明が書いてある int main() { // 一連の処理の塊を関数と呼ぶ。 // C言語では main() 関数を最初に実行する。 printf( "Hello World\n" ) ; // printf() は、以下の物を表示する関数。 // "\n"は、文字を出力して改行するための特殊文字 return 0 ; // main() 関数が、正常終了したことを意味する } // 0 を返り値として返す。
“#include <…>“のプリプロセッサ行は、最初のうちは解りにくいので、「これを書かないとダメ…」と思っていればいい。
#include <stdio.h> は、別ファイル(ヘッダファイル) stdio.h に記載されているプログラムリストを読み込む機能。
stdio.h には、printf() や scanf() などの基本的な関数や定数などの情報が記載されている。
C言語の基本的な命令(文)は、”;”で終わる。(単文)
複数の処理をまとめる場合には、”{“から”}”の中に、複数の文を書き並べる。(複文)
関数とは、複数の処理をひとまとめにした、処理の「かたまり」と思えばいい。
関数の型 関数名( 仮引数 ... ) { 処理1 ... ; 処理2 ... ; }printf() の 文字列中の”\n”(あるいは”¥n”)は、改行を意味する。
「\:バックスラッシュ」は、日本語環境では「¥:円記号」で入力・表示することが多い。
Paiza.io で動かしてみよう
C言語を本格的に使いたいなら、Microsoft Visual Studio などをインストールして使う方が便利だが、情報制御基礎で説明する程度のプログラムなら、Paiza.io が便利。ブラウザの画面で簡単にプログラムの動作を確認することができる。https://paiza.io/jaにアクセスして、上述の Hello World を動かしてみよう。
変数と代入
#include <stdio.h> #include <math.h> // 数学関数を使う 平方根 sqrt() を使っている int main() { // 変数の宣言 int i ; // 符号付き32bit変数 i の宣言 int a = 123 , j ; // a を 123 で初期化 , j も整数型 float x ; // 単精度実数の x を宣言 double y = 1.234 , z ; // 倍精度実数の y を宣言し 1.234 で初期化, // z も倍精度実数 // 変数への代入 i = 1 ; // i に 1 を代入 i = 12 + 2 * a ; // 12+2*a を代入 a は123なので、 // iには、258 が入る。 x = sqrt( 2.0 ) ; // x に 2.0 の平方根(1.4142)を代入 z = y * 2.0 + x * 3.0 ; // y*2+x*3をzに代入 // 変数の内容の表示 printf( "%d\n" , i ) ; // 整数型(%d)で、 i の値を表示 printf( "%f\n" , x ) ; // 単精度実数(%f) で、x の値を表示 printf( "%lf\n" , z ) ; // 倍精度実数(%lf)で、z の値を表示 printf( "iの値は%d,xの値は%lfです。\n" , i , x ) ; return 0 ; // 正常終了 0 を返す }
変数(計算結果を格納する入れ物)を使う場合は、変数を宣言する。
変数名には、何が入っているのか理解しやすいように、名前をつければいい。(英字で始まり、英数字が続くもの,_が入ってもいい)
変数に値を記憶する時は、”変数名=式 ;”の様に書くと、代入演算子”=” の右辺を計算し、その計算結果が左辺の変数に保存される。
変数の内容を表示する時には、printf() の文字列の中に、%d,%f,%lf などの表示したい式の型に応じたものを書いておく。%d=int型 , %f=float型 , %lf=double型
式の値が、その %.. の部分に書き込まれて、出力される。
繰り返しの制御命令
最も基礎的な繰り返し命令として、for() 文を説明。
#include <stdio.h> int main() { int i ; for( i = 1 ; i <= 10 ; i++ ) { // iを1から10まで変化させる。 printf( "%d %d\n" , i , i*i ) ; // i と iの二乗を表示 } return 0 ; }
for文の意味を説明するために、対応するフローチャートを示す。
先のプログラムをフローチャートで示し、その命令の実行順序と、その変数の変化を下図に示す。
練習問題1
簡単なプログラミングの練習として、前回講義の練習問題をC言語で書いてみよう。
- 電気電子工学科,電子情報工学科の学生は、出席番号が奇数は処理C,偶数は処理Dについて回答せよ。
- それ以外の学科の学生は、出席番号が奇数は処理A,偶数は処理Bの結果について回答せよ。
- 自分が考えたプログラムは、前述の Paiza.io や、自分のパソコンのC言語環境で入力し、動作結果も確認せよ。
制御構文とフローチャート
構文の入れ子
文と複文
C言語の文法で、{,} は複数の処理を連続して実行し、複文とよばれる。複数ので文を構成する。
これに対して、a = 123 ; といったセミコロンで終わる「処理 ;」は単文といい、1つの式で文となる。
制御構文のif文は、「if ( 条件 ) 文真」で文となる。このため条件が満たされたときに実行する文真が単文であれば、{,} は不要である。条件が満たされない場合の処理も記述するときには、「if ( 条件 ) 文真 else 文偽」を使う。
// if文 if ( 条件 ) { a = 123 ; } if ( 条件 ) a = 123 ; // 単文なら中括弧は不要 // if-then-else if ( x >= 60 ) { printf( "合格点\n" ) ; } else { printf( "不合格点\n" ) ; }
同じように、「while(条件) 文」、「for(A,B,C) 文」、「do 文 while(条件) ;」も、それぞれ文を構成する。
{,} の複文は、{ 文 文 文… } のように、一連の文を実行し、それを1つの文として扱うための機能である。
// while 文 i = 0 ; while( i < 10 ) { printf( "%d\n" , i ) ; i++ ; } // for 文 for( i = 0 ; i < 10 ; i++ ) { printf( "%d\n" , i ) ; } // do-while 文 i = 0 ; do { printf( "%d\n" , i ) ; i++ ; } while( i < 10 ) ;
練習問題2
プログラムの制御構造の確認として、以下の3つ(No.1,No.2,No.3)の問題から、
M科,C科,B科の学生は((自分の出席番号+1) % 2)+1 の問題、E科,EI科の学生は、((自分の出席番号+1) % 3)+1について、プログラムのフローチャートを描き、その処理がどのように進むのか答えよ。
レポートには、以下の点を記載すること。
- フローチャート
- 実行順序と変数の変化がわかる内容
- (できれば、実際にプログラムを動かし、正しいことを検証すること)
// No.1 --------------------------------------------------------- #include <stdio.h> int main() { int i , j ; for( i = 1 ; i <= 4 ; i++ ) { if ( i % 2 == 0 ) { // i%2 は2で割った余り,i%2==0ならば偶数のとき for( j = 1 ; j <= 2 ; j++ ) printf( "%d %d\n" , i , j ) ; } } return 0 ; } // No.2 --------------------------------------------------------- #include <stdio.h> int main() { int x = 10 , y = 7 , s = 0 ; while( x > 0 ) { if ( x % 2 != 0 ) s = s + y ; y = y * 2 ; x = x / 2 ; // 注意: xは整数型 } printf( "%d\n" , s ) ; return 0 ; } // No.3 --------------------------------------------------------- #include <stdio.h> int a[ 6 ] = { 2 , 3 , 5 , 8 , 13 , 21 } ; int main() { int left = 0 , right = 6 , mid ; int key = 13 ; while( right - left > 0 ) { mid = (left + right) / 2 ; // 整数型で計算 printf( "%d\n" , a[ mid ] ) ; if ( a[ mid ] == key ) break ; else if ( a[ mid ] > key ) right = mid ; else left = mid + 1 ; } return 0 ; }
派生と継承と仮想関数
前回の派生と継承のイメージを改めて記載する。
// 基底クラス class Person { private: char name[ 20 ] ; int age ; public: Person( const char s[] , int x ) : age( x ) { strcpy( name , s ) ; } void print() { printf( "%s %d\n" , name , age ) ; } } ; // 派生クラス(Student は Person から派生) class Student : public Person { private: char dep[ 20 ] ; int grade ; public: Student( const char s[] , int x , const char d[] , int g ) : Person( s , x ) // 基底クラスのコンストラクタ { // 追加された処理 strcpy( dep , d ) ; grade = g ; } void print() { Person::print() ; // 基底クラスPersonで名前と年齢を表示 printf( "- %s %d\n" , dep , grade ) ; } } ; int main() { Person saitoh( "t-saitoh" , 55 ) ; Student yama( "yamada" , 21 , "ES" , 1 ) ; Student nomu( "nomura" , 22 , "PS" , 2 ) ; saitoh.print() ; // 表示 t-saitoh 55 yama.print() ; // 表示 yamada 21 // - ES 1 nomu.print() ; // 表示 nomura 22 return 0 ; // - PS 2 }
このような処理でのデータ構造は、次のようなイメージで表される。
派生クラスでの問題提起
基底クラスのオブジェクトと、派生クラスのオブジェクトを混在してプログラムを記述したらどうなるであろうか?
上記の例では、Person オブジェクトと、Student オブジェクトがあったが、それをひとまとめで扱いたいこともある。
以下の処理では、Person型の saitoh と、Student 型の yama, nomu を、一つの table[] にまとめている。
int main() { Person saitoh( "t-saitoh" , 55 ) ; Student yama( "yamada" , 21 , "ES" , 1 ) ; Student nomu( "nomura" , 22 , "PS" , 2 ) ; Person* table[3] = { &saitoh , &yama , &nomu , } ; for( int i = 0 ; i < 3 ; i++ ) { table[ i ]->print() ; } return 0 ; }
C++では、Personへのポインタの配列に代入する時、Student型ポインタは、その基底クラスへのポインタとしても扱える。ただし、このように記述すると、table[] には、Person クラスのデータして扱われる。
このため、このプログラムを動かすと、以下のように、名前と年齢だけが3人分表示される。
t-saitoh 55 yamada 21 nomura 22
派生した型に応じた処理
上記のプログラムでは、 Person* table[] に、Person*型,Student*型を混在して保存をした。しかし、Person*として呼び出されると、yama のデータを表示しても、所属・学年は表示されない。上記のプログラムで、所属と名前を表示することはできないのだろうか?
// 混在したPersonを表示 for( int i = 0 ; i < 3 ; i++ ) table[i]->print() ; // Student は、所属と名前を表示して欲しい t-saitoh 55 yamada 21 - ES 1 nomura 22 - PS 2
上記のプログラムでは、Person型では、後でStudent型と区別ができないと困るので、Person型に、Person型(=0)なのか、Student型(=1)なのか区別するための type という型の識別番号を追加し、type=1ならば、Student型として扱うようにしてみた。
// 基底クラス class Person { private: int type ; // 型識別情報 char name[ 20 ] ; int age ; public: Person( int tp , const char s[] , int x ) : type( tp ) , age( x ) { strcpy( name , s ) ; } int type_person() { return type ; } void print() { printf( "%s %d\n" , name , age ) ; } } ; // 派生クラス(Student は Person から派生) class Student : public Person { private: char dep[ 20 ] ; int grade ; public: Student( int tp , const char s[] , int x , const char d[] , int g ) : Person( tp , s , x ) // 基底クラスのコンストラクタ { // 追加された処理 strcpy( dep , d ) ; grade = g ; } void print() { Person::print() ; // 基底クラスPersonで名前と年齢を表示 printf( "- %s %d\n" , dep , grade ) ; } } ; int main() { // type=0 は Person 型、type=1は Student 型 Person saitoh( 0 , "t-saitoh" , 55 ) ; Student yama( 1 , "yamada" , 21 , "ES" , 1 ) ; Student nomu( 1 , "nomura" , 22 , "PS" , 2 ) ; Person* table[3] = { &saitoh , &yama , &nomu , } ; for( int i = 0 ; i < 3 ; i++ ) { switch( table[i]->type_person() ) { case 0 : table[i]->print() ; break ; case 1 : // 強制的にStudent*型として print() を呼び出す。 // 最近のC++なら、(static_cast<Student*>(table[i]))->>print() ; ((Student*)table[i])->print() ; break ; } } return 0 ; }
しかし、このプログラムでは、プログラマーがこのデータは、Personなので type=0 で初期化とか、Studentなので type=1 で初期化といったことを記述する必要がある。
また、関数を呼び出す際に、型情報(type)に応じて、その型にふさわしい処理を呼び出すための switch 文が必要になる。
もし、派生したクラスの種類がいくつもあるのなら、(1)型情報の代入は注意深く書かないとバグの元になるし、(2)型に応じた分岐処理は巨大なものになるだろう。実際、オブジェクト指向プログラミングが普及する前の初期の GUI プログラミングでは、巨大な switch 文が問題となっていた。巨大な switch 文は、選択肢だけの if else-if else-if が並ぶと処理効率も悪い。
仮想関数
上記の、型情報の埋め込みと巨大なswitch文の問題の解決策として、C++では仮想関数(Virtual Function)が使える。
型に応じて異なる処理をしたい関数があったら、その関数の前に virtual と書くだけで良い。このような関数を、仮想関数と呼ぶ。
// 基底クラス class Person { private: char name[ 20 ] ; int age ; public: Person( const char s[] , int x ) : age( x ) { strcpy( name , s ) ; } virtual void print() { printf( "%s %d\n" , name , age ) ; } } ; // 派生クラス(Student は Person から派生) class Student : public Person { private: char dep[ 20 ] ; int grade ; public: Student( const char s[] , int x , const char d[] , int g ) : Person( s , x ) // 基底クラスのコンストラクタ { // 追加された処理 strcpy( dep , d ) ; grade = g ; } virtual void print() { Person::print() ; // 基底クラスPersonで名前と年齢を表示 printf( "- %s %d\n" , dep , grade ) ; } } ; int main() { // type=0 は Person 型、type=1は Student 型 Person saitoh( "t-saitoh" , 55 ) ; Student yama( "yamada" , 21 , "ES" , 1 ) ; Student nomu( "nomura" , 22 , "PS" , 2 ) ; Person* table[3] = { &saitoh , &yama , &nomu , } ; for( int i = 0 ; i < 3 ; i++ ) { table[i]->print() ; } return 0 ; }
クラスの中に仮想関数が使われると、C++ では、プログラム上で見えないが、何らかの型情報をオブジェクトの中に保存してくれる。
また、仮想関数が呼び出されると、その型情報を元に、ふさわしい関数を自動的に呼び出してくれる。このため、プログラムも table[i]->print() といった極めて簡単に記述できるようになる。
関数ポインタ
仮想関数の仕組みを実現するためには、関数ポインタが使われる。
以下の例では、返り値=int,引数(int,int)の関数( int(*)(int,int) )へのポインタfpに、最初はaddが代入され、(*fp)(3,4) により、7が求まる。
int add( int a , int b ) { return a + b ; } int mul( int a , int b ) { return a * b ; } int main() { int (*fp)( int , int ) ; fp = add ; printf( "%d\n" , (*fp)( 3 , 4 ) ) ; // 3+4=7 fp = mul ; printf( "%d\n" , (*fp)( 3 , 4 ) ) ; // 3*4=12 int (*ftable[2])( int , int ) = { add , mul , } ; for( int i = 0 ; i < 2 ; i++ ) printf( "%d\n" , (*ftable[i])( 3 , 4 ) ) ; return 0 ; }仮想関数を使うクラスが宣言されると、一般的にそのコンストラクタでは、各クラス毎の仮想関数へのポインタのテーブルが型情報として保存されるのが一般的。仮想関数の呼び出しでは、仮想関数へのポインタを使って処理を呼び出す。このため効率よく仮想関数を動かすことができる。
仮想関数の実装方法
仮想関数の一般的な実装方法としては、仮想関数を持つオブジェクトには型情報として仮想関数へのポインタテーブルへのポインタを保存する。この場合、仮想関数の呼び出しは、object->table[n]( arg… ) のような処理が行われる。
Webプログラミングとセキュリティ
ここまでの授業では、Webを使った情報公開で使われる、HTML , JavaScirpt , PHP , SQL などの解説を行ってきたが、これらを組み合わせたシステムを構築する場合には、セキュリティについても配慮が必要である。
今回は、初心者向けの情報セキュリティの講習で使われるCTFという競技の練習問題をつかって、ここまで説明してきた Web の仕組みを使ったセキュリティの問題について解説を行う。
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[] ポインタ ;」のように、配列を開放することを明記する必要がある。
フローチャートと整数型
学際科目の情報制御基礎において、プログラムの基本としてフローチャートと基本的な処理を説明し、数値型の注意点を説明。
フローチャートの基本
プログラムの処理の順序を理解するには、初心者であればフローチャート(流れ図)を使う。
処理の1つ1つを箱で表し、流れを箱の間の矢印で示すことでアルゴリズム(プログラムの考え方)や処理順序を表現する。処理単位の箱は、命令の種類によって箱の書き方が決まっている。
上図右側のフローチャートの例では、以下の説明のように実行され、0,1,2,…,9 が表示され、最終的に変数 i が10以上になり処理を停止する。
(1) 変数 i に 0 を保存
(2) 変数 i は10未満なら(3)、10以上なら終了
(3) 変数 i を表示
(4) i = i + 1 右辺の計算結果を、左辺に代入。iが0から1に変化
(5) 処理(2)から繰り返し。
上記のようなプログラムは、C言語であれば以下のようになる。
#include <stdio.h> | 入出力関数を使うための準備 int main() { | 最初に main() という関数が呼び出される。 int i ; | 変数 i の入れ物を準備 for( i = 0 ; i < 10 ; i++ ) { | 最初に i = 0 を行い、i < 10 の条件を満たす間繰り返し、 | 繰り返しの度に i を1つ増やす printf( "%d\n" , i ) ; | i の値を表示 } return 0 ; | 正しく終わったら0を返す。 }
練習問題1
以下のフローチャートの処理A,処理B,処理C,処理Dの実行結果を答えよ。
- 電気電子工学科,電子情報工学科の学生は、出席番号が偶数は処理C,奇数は処理Dについて回答せよ。
- それ以外の学科の学生は、出席番号が偶数は処理A,奇数は処理Bの結果について回答せよ。
- このプログラムではどういった意味の値を求めようとしているのか答えよ。
情報量の単位
データを覚える最小単位は、0と1の2通りで表される1bit (ビット)と呼ぶ。単位として書く場合には b で表す。さらに、その1bitを8個組み合わせると、256通りの情報を保存できる。256通りあれば一般的な英数字などの記号を1文字保存する入れ物として便利であり、この単位を 1byte (バイト) と呼ぶ。単位として書く場合には B で表す。
通信関係の人は8bit=1byteを1オクテットと呼ぶことも多い。日本語を表現するには、かなや漢字を使うため16bit = 2byte = 1word(ワード) で表現することが多い。(ただしワードは32bitを意味することもあるので要注意, double word=32bit, quad word=64bit という呼び方もある。)
物理では単位が大きくなると、103=kキロ,106=Mメガ,109=Gギガ,1012=Tテラ を使うが、コンピュータの世界では、103≒210=1024 なので、1kB(キロバイト)というと1024Bを意味することが多い。明確に区別する時は、1024B(バイト)=1KiB(キビバイト), 10242B=1MiB(メビバイト), 10243B=1GiB(ギビバイト) などと記載する。
2進数,8進数,16進数
プログラムの中で整数値を覚える場合は、2進数の複数桁で記憶する。例えば、2進数3桁(3bit)であれば、000, 001, 010, 011, 100, 101, 110, 111 で、10進数であれば 0~7 の8通りの値が扱える。(8進数)
2進数4桁(4bit)であれば、0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 の16通りを表現できる(16進数)。これを1桁で表現するために、0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F を使って表現する。
例 8進数 16進数 0123 0x123 ※C言語では、 + 026 + 0xEA 8進数を表す場合、先頭に0をつけて表す。 -------- -------- 16進数を表す場合、先頭に0xをつけて表す。 0151 0x20D 0x3+0xA = 0xD 0x2+0xE = 2+14 = 16 = 0x0 + 桁上がり 0x1+桁上がり = 0x2
整数型と扱える値の範囲
コンピュータの開発が進むにつれ計算の単位となるデータ幅は、8bit, 16bit, 32bit, 64bit と増えていった。整数型データには、正の値しか覚えられない符号無し整数と、2の補数で負の数を覚える符号付き整数に分けられる。
プログラムを作るためのC言語では、それぞれ 8bitの文字型(char)、16bitの short int型、32bitの int 型、64bitの long int 型(※C言語では long int で宣言すると32bitの場合も多いので要注意)があり、それぞれに符号なし整数(unsigned), 符号あり整数(signed: C言語の宣言では書かない)がある。
精度 | 符号あり | 符号なし |
8bit(1byte) | char (int8_t) | unsigned char (uint8_t) |
16bit(2byte) | short int (int16_t) | unsigned short int (uint16_t) |
32bit(4byte) | int (int32_t) | unsigned int (uint32_t) |
64bit(8byte) | long int※ (int64_t) | unsigned long int※ (uint64_t) |
符号付きのデータは、負の数は2の補数によって保存され、2進数の最上位bit(符号ビット)は負の数であれば1、正の数であれば0となる。
整数型で扱える数
(例) 符号なしの1byte(8bit)であれば、いくつの数を扱えるであろうか?
符号なしの N bit の整数であれば2N通りの値を表現でき、0~(2N-1) までの値が扱える。
bit数 | 型 | 符号なし(unsigned) | |
8 | unsigned char | 0~28-1 | 0~255 |
16 | unsigned short int | 0~216-1 | 0~65535 |
32 | unsigned int | 0~232-1 | 0~4294967295 |
符号付きの N bit の整数であれば、2の補数表現では最上位ビットが符号を表すために使われる。
100)10 | 64)16 | 0110,0100)2 |
-100)10 | 9C)16 | 1001,1100)2 |
正の数なら残りの(N-1)bitで扱うため 0〜2N-1-1を表現できる。負の数は2N-1通りを表現できるので、N bit の符号つき整数は、-2N-1 〜0〜 2N-1-1の範囲の値を覚えられる。
bit数 | 型 | 符号あり(signed) | |
8 | char | -27~0~27-1 | -128~127 |
16 | short int | -215~0~215-1 | -32768~32767 |
32 | int | -231~0~231-1 | -2147483648~2147483647 |
2の べき乗 の概算
プログラムを作る場合、2のべき乗がだいたいどの位の値なのか知りたいことが多い。この場合の計算方法として、2つの方法を紹介する。
- 232 = 22 × (210)3 = 4 × 10243 ≒ 4,000,000,000
- 232をN桁10進数で表すとすれば
なので、両辺のlog10を求める。
(つまり、bit数に0.3をかければ10進数の桁数が求まる。)
数値の範囲の問題で動かないプログラム
この話だけだと、扱える数値の上限について実感がわかないかもしれないので、以下のプログラムをみてみよう。(C言語の詳細は説明していないので、問題点がイメージできるだけでいい。)
組み込み系のコンピュータでは、int 型で宣言される変数でも、16bitの場合もある。以下のプログラムは期待した値が計算できない例である。以下の例では、16bit int型として short int で示す。
// ✳️コード1 #include <stdio.h> #include <math.h> int main() { // 原点から座標(x,y)までの距離を求める short int x = 200 ; short int y = 200 ; short int r2 = x*x + y*y ; // (x,y)までの距離の2乗 short int r = sqrt( r2 ) ; // sqrt() 平方根 printf( "%d\n" , r ) ; // 何が求まるか? return 0 ; // (例) 282ではなく、120が表示された。 }
コンピュータで一定時間かかる処理を考えてみる。
// コード2.1 // 1 [msec] かかる処理が以下のように書いてあったとする。 short int i ; for( i = 0 ; i < 1000 ; i++ ) NOP() ; // NOP() = 約1μsecかかる処理とする。 // ✳️コード2.2 // 0.5 [sec]かかる処理を以下のようにかいた。 short int i ; for( i = 0 ; i < 500000 ; i++ ) NOP() ; // でもこの処理は16bitコンピュータでは、1μsecもかからずに終了する。なぜか?
上記の例は、性能の低い16bit コンピュータの問題で、最近は32bit 整数型のコンピュータが普通だし、特に問題ないと思うかもしれない。でも、32bit でも扱える数の範囲で動かなくなるプログラムを示す。
OS(unix) では、1970年1月1日からの経過秒数で時間(unix時間)を扱う。ここで、以下のプログラムは、正しい値が計算できなかった有名な例である。(2004年1月11日にATMが動かなくなるトラブルの原因だった)
// ✳️コード3.1 int t1 = 1554735600 ; // 2019年4月09日,00:00 int t2 = 1555340400 ; // 2019年4月16日,00:00 // この2日の真ん中の日を求める。 // t1 | t2 // |--------+--------| // | t_mid | // 以下のプログラムは、正しい 2019年4月12日12:00 が求まらない。なぜか? int t_mid = (t1 + t2) / 2; // (例) 1951年03月25日 08:45 になった。 // コード3.2 // 以下のプログラムは正しく動く。 time_t 型(時間処理用の64bit整数)を使えば問題ない。 time_t t1 = 1554735600 ; // 2019年4月09日,00:00 time_t t2 = 1555340400 ; // 2019年4月16日,00:00 // time_t型が32bitであったとしても桁溢れない式 time_t t_mid = t1 + (t2 - t1) / 2 ;
練習問題2
以下の整数の範囲を具体的な値で答えよ。
出席番号・自分の誕生日(の日にち)に合わせて該当する2問について答えること。
- 7bitの符号なし整数で扱える数値の範囲 (出席番号が偶数)
- 12bitの符号あり整数で扱える数値の範囲 (出席番号が奇数)
- 20bitの符号なし整数で扱える数値の範囲 (誕生日の日づけが偶数)
- 24bitの符号あり整数で扱える数値の範囲 (誕生日の日づけが奇数)
練習問題3
先に示した数値の範囲が原因で動かないプログラム(コード1,コード2.2,コード3.1)の中から1つを選んで、計算結果が正しく求まらない原因を、具体的な値を示しながら説明せよ。
練習問題1,練習問題2,練習問題3について、レポートとして提出せよ。
Teamsのこちらの共有フォルダに、回答記入用のひな型がおいてあるので、この書式を参考に各自レポートにまとめ、同フォルダに提出してください。
派生と継承
隠ぺい化の次のステップとして、派生・継承を説明する。オブジェクト指向プログラミングでは、一番基本となるデータ構造を宣言し、その基本構造に様々な機能を追加した派生クラスを記述することでプログラムを作成する。今回は、その派生を理解するためにC言語で発生する問題点を考える。
派生を使わずに書くと…
元となるデータ構造(例えばPersonが名前と年齢)でプログラムを作っていて、 途中でその特殊パターンとして、所属と学年を加えた学生(Student)という データ構造を作るとする。
// 元となる構造体(Person) / 基底クラス struct Person { char name[ 20 ] ; // 名前 int age ; // 年齢 } ; // 初期化関数 void set_Person( struct Person* p , char s[] , int x ) { strcpy( p->name , s ) ; p->age = x ; } // 表示関数 void print_Person( struct Person* p ) { printf( "%s %d\n" , p->name , p->age ) ; } int main() { struct Person saitoh ; set_Person( &saitoh , "t-saitoh" , 50 ) ; print_Person( &saitoh ) ; return 0 ; }
パターン1(そのまんま…)
上記のPersonに、所属と学年を加えるのであれば、以下の方法がある。 しかし以下パターン1は、要素名がname,ageという共通な部分があるようにみえるが、 プログラム上は、PersonとPersonStudent1は、まるっきり関係のない別の型にすぎない。
このため、元データと共通部分があっても、同じ処理を改めて書き直しになる。(プログラマーの手間が減らせない)
// 元のデータに追加要素(パターン1) struct PersonStudent1 { // Personと同じ部分 char name[ 20 ] ; // 名前 int age ; // 年齢 // 追加部分 char dep[ 20 ] ; // 所属 int grade ; // 学年 } ; void set_PersonStudent1( struct PersonStudent1* p , char s[] , int x , char d[] , int g ) { // set_Personと同じ処理を書いている。 strcpy( p->name , s ) ; p->age = x ; // 追加された処理 strcpy( p->dep , d ) ; p->grade = g ; } // 名前と年齢 / 所属と学年を表示 void print_PersonStudent1( struct PersonStudent1* p ) { // print_Personと同じ処理を書いている。 printf( "%s %d\n" , p->name , p->age ) ; printf( "- %s %d¥n" , p->dep , p->grade ) ; } int main() { struct PersonStudent1 yama1 ; set_PersonStudent1( &yama1 , "yama" , 22 , "PS" , 2 ) ; print_PersonStudent1( &yama1 ) ; return 0 ; }
パターン2(元データの処理を少し使って…)
パターン1では、機能が追加された新しいデータ構造のために、同じような処理を改めて書くことになりプログラムの記述量を減らせない。面倒なので、 元データ用の関数をうまく使うように書いてみる。
// 元のデータに追加要素(パターン2) struct PersonStudent2 { // 元のデータPerson struct Person person ; // 追加部分 char dep[ 20 ] ; int grade ; } ; void set_PersonStudent2( struct PersonStudent2* p , char s[] , int x , char d[] , int g ) { // Personの関数を部分的に使う set_Person( &(p->person) , s , x ) ; // 追加分はしかたない strcpy( p->dep , d ) ; p->grade = g ; } void print_PersonStudent2( struct PersonStudent2* p ) { // Personの関数を使う。 print_Person( &p->person ) ; printf( "- %s %d¥n" , p->dep , p->grade ) ; } int main() { struct PersonStudent2 yama2 ; set_PersonStudent2( &yama2 , "yama" , 22 , "PS" , 2 ) ; print_PersonStudent2( &yama2 ) ; return 0 ; }
このパターン2であれば、元データ Person の処理をうまく使っているので、 プログラムの記述量を減らすことはできるようになった。
しかし、print_PersonStudent2() のような処理は、名前と年齢だけ表示すればいいという場合、元データ構造が同じなのに、 PersonStudent2 用のプログラムをいちいち記述するのは面倒ではないか?
そこで、元データの処理を拡張し、処理の流用ができないであろうか?
基底クラスから派生クラスを作る
オブジェクト指向では、元データ(基底クラス)に新たな要素を加えたクラス(派生クラス)を 作ることを「派生」と呼ぶ。派生クラスを定義するときは、クラス名の後ろに、 「:」,「public/protected/private」, 基底クラス名を書く。
// 基底クラス class Person { private: char name[ 20 ] ; int age ; public: Person( const char s[] , int x ) : age( x ) { strcpy( name , s ) ; } void print() { printf( "%s %d\n" , name , age ) ; } } ; // 派生クラス(Student は Person から派生) class Student : public Person { private: // 追加部分 char dep[ 20 ] ; int grade ; public: Student( const char s[] , int x , const char d[] , int g ) : Person( s , x ) // 基底クラスのコンストラクタ { // 追加された処理 strcpy( dep , d ) ; grade = g ; } } ; int main() { Person saitoh( "t-saitoh" , 50 ) ; saitoh.print() ; Student yama( "yama" , 22 , "PS" , 2 ) ; yama.print() ; // "yama 22"が表示される return 0 ; }
ここで注目すべき点は、main()の中で、Studentクラス”yama”に対し、yama.print() を呼び出しているが、パターン2であれば、print_PersonStudent2()に相当するプログラムを 記述していない。 しかし、この派生を使うと Person の print() が自動的に流用することができる。 これは、基底クラスのメソッドを「継承」しているから、 このように書け、名前と年齢「yama 22」が表示される。
さらに、Student の中に、以下のような Student 専用の新しい print()を記述してもよい。
class Student ...略... { ...略... // Student クラス専用の print() void print() { // 親クラス Person の print() を呼び出す Person::print() ; // Student クラス用の処理 printf( "%s %d\n" , dep , grade ) ; } } ; void main() { ...略... Student yama( "yama" , 22 , "PS" , 2 ) ; yama.print() ; }
この場合は、継承ではなく機能が上書き(オーバーライト)されるので、 「yama 22 / PS 2」が表示される。
派生クラスを作る際の後ろに記述した、public は、他にも protected , private を 記述できる。
public だれもがアクセス可能。 protected であれば、派生クラスからアクセスが可能。 派生クラスであれば、通常は protected で使うのが一般的。 private 派生クラスでもアクセス不可。
C言語で無理やりオブジェクト指向の”派生”を使う方法
オブジェクト指向の機能の無いC言語で、このような派生と継承を実装する場合には、共用体を使う以下のようなテクニックが使われていた。
unix の GUI である X11 でも共用体を用いて派生を実装していた。// 基底クラス struct PersonBase { // 基底クラス char name[ 20 ] ; int age ; } ; struct PersonStudent { // 派生クラス struct PersonBase base ; char dep[ 20 ] ; int grade ; } ; //(base) //(student) union Person { // name //[name] struct PersonBase base ; // age //[age ] struct PersonStudent student ; // dep } ; // grade void person_Print( struct Person* p ) { printf( "%s %d\n" , p->base.name , p->base.age ) ; } int main() { struct PersonBase tsaitoh = { "tsaitoh" , 55 } ; struct PersonStudent mitsuki = { { "mitsuki" , 21 } , "KIT" , 4 } ; print_Person( (struct Person*)&tsaitoh ) ; print_Person( (struct Person*)&mitsuki ) ; // 無理やり print_Person を呼び出す return 0 ; }
仮想関数への伏線
上記のような派生したプログラムを記述した場合、以下のようなプログラムでは何が起こるであろうか?
class Student ... { : void print() { Person::print() ; // 名前と年齢を表示 printf( " %s %d¥n" , dep , grade ) ; // 所属と学年を表示 } } ; int main() { Person saitoh( "t-saitoh" , 55 ) ; saitoh.print() ; // t-saitoh 55 名前と年齢を表示 Student mitsu( "mitsuki" , 20 , "KIT" , 3 ) ; Student ayuka( "ayuka" , 18 , "EI" , 4 ) ; mitsu.print() ; // mitsuki 20 / KIT 3 名前,年齢,所属,学年を表示 ayuka.print() ; // ayuka 18 / EI 4 名前,年齢,所属,学年を表示 Person* family[] = { &saitoh , &mitsu , &ayuka , // 配列の中に、Personへのポインタと } ; // Studentへのポインタが混在している // 派生クラスのポインタは、 // 基底クラスのポインタとしても扱える for( int i = 0 ; i < 3 ; i++ ) family[ i ]->print() ; // t-saitoh 55/mitsuki 20/ayuka 18 return 0 ; // が表示される。 } // # "mitsuki 20/KIT 3" とか "ayuka 18/EI 4" // # が表示されてほしい?
バックエンドと所有権の設定
前回の講義でファイルのパーミッション(読み書き権限)について確認したが、バックエンドプログラミングで必要となるファイルの所有権の設定を通して、演習を行う。これに合わせ、サーバ上のファイルの編集作業なども体験する。
サーバ上のファイルの編集
以前のバックエンドのプログラムの演習ではサーバの設定などの体験もできていないため、フロントエンドの処理でサーバ上に送られたデータは、最終的な書き込み処理は行っていなかった。今回は、サーバ上でデータをサーバ上のバックエンドプログラムの PHP ファイルを修正し、データが書き込めるようにプログラムの修正を行う。
サーバ上のファイルを編集するには、色々な方法がある。
- サーバ上のエディタで直接編集
- unix のシステムで直接ファイルを編集するのであれば、vim や emacs を利用するのが一般的であろう。これらのエディタはリモートサーバにsshなどでログインしている時は、端末ソフトの文字表示機能だけで動作し、GUI 機能を使わない。vim や emacs は、古くから使われ、Windows で動く vim や emacs もある。
- システム管理者権限で編集する必要があるファイルの場合は、以下に紹介するような方法は煩雑であり、サーバ上で直接編集も知っておくべき。
- プログラムをローカルPCで編集しアップロード(今回はコレ)
- 前回の演習では、リモートサーバに接続する際には ssh コマンドを用いたが、ssh にはファイル転送のための scp コマンドも用意されている。
- scp コマンドは、通常の cp 命令 ( cp コピー元 コピー先 ) を ssh のプロトコルでリモートする機能を拡張したものであり、リモートのコンピュータをコピー元やコピー先として指定する場合は、 ユーザ名@リモートホスト:ファイル場所 と記載する。
-
# remotehostのファイル helloworld.c をローカルホストのカレントディレクトリ.にダウンロード C:\Users\tsaitoh> scp tsaitoh@remotehost:helloworld.c . # ローカルホストの foobar.php を remotehostの/home/tsaitoh/public_html/ フォルダにアップロード C:\Users\tsaitoh> scp foobar.php tsaitoh@remotehost:/home/tsaitoh/public_html/
- VSCode でリモートファイルを編集
- 最近のエディタでは、前述のローカルPCで編集しアップロードといった作業を、自動的に行う機能が利用できる。emacs の tramp-mode や、VS Code の Remote ssh プラグインなどがこれにあたる。利用する演習用のサーバが高機能であれば、vscode + remote-ssh が一番便利と思われるが、remote-ssh はサーバで大きな node.js を動かすため、サーバ負担が大きいので今回はこの方式は使わない。
Webアプリと所有権の問題
PHPで書かれたバックエンドでのプログラムにおいて、Webサーバは www-data(uid),www-data(groupid) というユーザ権限で動作している。そして、webサーバと連動して動く PHP のプログラムも www-data の権限で動作する。一方で、通常ユーザが開発しているプログラムが置かれる $HOME/public_html フォルダは、何もしなければそのユーザのものである。このため、PHP のプログラムがユーザのフォルダ内にアクセスする際には、www-data に対してのアクセス権限が必要となる。
Windows ユーザが Web プログラミングの体験をする際には、XAMPP などのパッケージを利用することも多いだろう。しかし XAMPP などは、中身のWebサーバ(apache), DBサーバ(MySQL)などすべてがインストールしたユーザ権限で動いたりするため、所有権の設定の知識が無くても簡単に利用することができる(あるいはユーザ自身が管理者権限を持っているため設定が無くてもアクセス権問題が発生しない)。このため Linux 環境での Web プログラミングに移行する際に、ユーザ権限の設定を忘れ、プログラムが動かず戸惑うことも多い。
今回の演習では、XAMPPを使わず、演習用サーバを用いる。
データベースサーバの場合
また、データの保存でデータベースを利用する場合、Oracle や MySQL といった、ネットワーク型のデータベースでは、Webサーバとは別にデータベースのサーバプログラムが動作している。ネットワーク型のデータベースでは、様々なユーザ・アプリケーションがデータの読み書きを行うため、SQL の create user 命令でユーザを割り当て、grant 命令でユーザのデータへのアクセス権限を指定する。
簡易データベースSQLiteの場合
簡単なデータベースシステムの SQLite は、PHP の SQLite プラグインを経由してディレクトリ内のファイルにアクセスする。このため、データベースファイルやデータベースのファイルが置かれているフォルダへのアクセス権限が必要となる。今回の演習用サーバでは、ゲストアカウントは www-data グループに所属しているので、データベースファイルやフォルダに対し、www-data グループへの書き込み権限を与える。
chown , chgrp , chmod コマンド
ファイル所有者やグループを変更する場合には、chown (change owner) 命令や chgrp (change group) 命令を使用する。
chown ユーザID ファイル 例: $ chown tsaitoh helloworld.c chgrp グループID ファイル 例: $ chgrp www-data public_html
ファイルに対するパーミッション(利用権限)を変更するには、chmod (change mode) 命令を用いる。
chmod 命令では、読み書きの権限は2進数3桁の組み合わせで扱う。読書可 “rw-“ = 6, 読出可 = “r–“ = 4 , ディレクトリの読み書き可 “rwx” = 7 など。ファイルには、所有者,グループ,その他の3つに分けて、読み書きの権限を割り当てる。2進数3桁=8進数1桁で表現できることから、一般的なファイルの “rw-,r–,r–“ は、8進数3桁 で 644 , ディレクトリなら “rwx,r-x,r-x” は 755 といった値で表現する。
chmod 権限 ファイル 例: $ chmod 664 helloworld.c $ ls -al -rw-rw-r-- tsaitoh ei 123 5月20 12:34 helloworld.c $ chmod 775 public_html drwxrwxr-x tsaitoh www-data 4096 5月20 12:34 public_html 8進数表現を使わない場合 $ chmod u+w,g+w helloworld.c ユーザ(u)への書き込み権限,グループ(g)への書き込み権限の追加(+) $ chmod g-w,o-rw helloworld.c グループ(g)書き込み権限を消す、その他(o)の読み書き権限を消す(-) $ chmod u=rw,g=r,o=r helloworld.c ユーザ(u)への読み書き,グループ(g),その他(o)への読み出し権限を設定(=)
演習内容
前回の演習と同じ方法でサーバにログインし、サーバ上で直接ファイル編集をしてみよう。
C:\Users\tsaitoh> ssh -P 443 guest00@nitfcei.mydns.jp $ ls -al -rw-r--r-- 1 guest00 root 76 Mar 8 12:06 helloworld.c $ vi helloworld.c もしくは $ emacs helloworld.c
- vim の使い方
- 挿入 iテキストESC
削除 x
ファイルの保存 :w
エディタの修了 ZZ
- emacs の使い方
- ファイルの保存 Ctrl-X Ctrl-S
エディタの修了 Ctrl-X Ctrl-C
GitHubから演習ファイルを複製
GitHub は、複数の開発者が共同でプログラムを開発するための環境で、プログラムの情報共有などに広く使われている。ファイルは、git コマンドで複製や更新ができる。
(( public_html の中に演習用ファイルを github からダウンロード )) $ cd ~/public_html public_html$ git clone https://github.com/tohrusaitoh/recp.git public_html/recp$ cd recp/ public_html/recp$ ls -al -rw-r--r-- 1 t-saitoh home 870 11月 10 2021 Makefile -rw-r--r-- 1 t-saitoh home 1152 10月 8 2021 README.md :
サーバ上のファイルをパソコンにコピーして編集
(( サーバ上のファイル sampleI.php (sample-アイ.php) をダウンロード )) C:\Users\tsaitoh> scp -P 443 guest00@nitfcei.mydns.jp:public_html/recp/sampleI.php . VSCode などのエディタで編集 (( 編集した sampleI.php をサーバにアップロード )) C:\Users\tsaitoh> scp -P 443 sampleI.php guest00@nitfcei.mydns.jp:public_html/recp/
Webサーバで書き込みができるように設定
(( public_html のデータベースファイル shopping.db を書き込み可能にする )) $ chgrp www-data ~guest00/public_html/recp/shopping.db $ chmod g+w ~guest00/public_html/recp/shopping.db (( public_html/recp フォルダを書き込み可能にする )) $ chgrp www-data ~guest00/public_html/recp $ chmod g+w ~guest00/public_html/recp
バックエンドプログラムを実行してみる
パソコンのブラウザで、http://nitfcei.mydns.jp/~guest00/recp/sampleI.php を開く。
書き込み結果を確認してみる
(( データベースファイル shopping.db の書込み結果を確認 )) $ cd ~guest00/public_html/recp public_html/recp$ sqlite3 shopping.db SQLite version 3.31.1 2020-01-27 19:55:54 Enter ".help" for usage hints. sqlite> select * from BUYLIST ; 1010|10001|2021-11-05|1 1020|10001|2021-11-05|2 1022|10001|2021-11-05|3 : sqlite> [Ctrl-D] コントロールDで sqlite3 を抜ける public_html/recp$
ポインタとメモリの使用効率
前回の授業で時間切れだったので、再度掲載してから、次のメモリーの使用効率について説明し、必要に応じてメモリを確保するための方法を考える。
ポインタインクリメントと式
C言語では、ポインタを動かしながら処理を行う場合に以下のようなプログラムもよくでてくる。
// string copy 配列のイメージで記載 void strcpy( char d[] , char s[] ) { int i ; for( i = 0 ; s[ i ] != '// string copy 配列のイメージで記載 void strcpy( char d[] , char s[] ) { int i ; for( i = 0 ; s[ i ] != '\0' ; i++ ) d[ i ] = s[ i ] ; d[ i ] = '\0' ; } int main() { char a[] = "abcde" ; char b[ 10 ] ; strcpy( b , a ) ; printf( "%s\n" , b ) ; return 0 ; }' ; i++ ) d[ i ] = s[ i ] ; d[ i ] = '// string copy 配列のイメージで記載 void strcpy( char d[] , char s[] ) { int i ; for( i = 0 ; s[ i ] != '\0' ; i++ ) d[ i ] = s[ i ] ; d[ i ] = '\0' ; } int main() { char a[] = "abcde" ; char b[ 10 ] ; strcpy( b , a ) ; printf( "%s\n" , b ) ; return 0 ; }' ; } int main() { char a[] = "abcde" ; char b[ 10 ] ; strcpy( b , a ) ; printf( "%s\n" , b ) ; return 0 ; }
しかし、この strcpy は、ポインタを使って書くと以下のように書ける。
// string copy ポインタのイメージで記載 void strcpy( char* p , char* q ) { while( *q != '// string copy ポインタのイメージで記載 void strcpy( char* p , char* q ) { while( *q != '\0' ) { *p = *q ; p++ ; q++ ; } *p = '\0' ; } // ポインタ加算と代入を一度に書く void strcpy( char* p , char* q ) { while( *q != '\0' ) *p++ = *q++ ; // *(p++) = *(q++) *p = '\0' ; } // ポインタ加算と代入と'¥0'判定を一度に書く void strcpy( char* p , char* q ) { while( (*p++ = *q++) != '\0' ) // while( *p++ = *q++ ) ; でも良い ; }' ) { *p = *q ; p++ ; q++ ; } *p = '// string copy ポインタのイメージで記載 void strcpy( char* p , char* q ) { while( *q != '\0' ) { *p = *q ; p++ ; q++ ; } *p = '\0' ; } // ポインタ加算と代入を一度に書く void strcpy( char* p , char* q ) { while( *q != '\0' ) *p++ = *q++ ; // *(p++) = *(q++) *p = '\0' ; } // ポインタ加算と代入と'¥0'判定を一度に書く void strcpy( char* p , char* q ) { while( (*p++ = *q++) != '\0' ) // while( *p++ = *q++ ) ; でも良い ; }' ; } // ポインタ加算と代入を一度に書く void strcpy( char* p , char* q ) { while( *q != '// string copy ポインタのイメージで記載 void strcpy( char* p , char* q ) { while( *q != '\0' ) { *p = *q ; p++ ; q++ ; } *p = '\0' ; } // ポインタ加算と代入を一度に書く void strcpy( char* p , char* q ) { while( *q != '\0' ) *p++ = *q++ ; // *(p++) = *(q++) *p = '\0' ; } // ポインタ加算と代入と'¥0'判定を一度に書く void strcpy( char* p , char* q ) { while( (*p++ = *q++) != '\0' ) // while( *p++ = *q++ ) ; でも良い ; }' ) *p++ = *q++ ; // *(p++) = *(q++) *p = '// string copy ポインタのイメージで記載 void strcpy( char* p , char* q ) { while( *q != '\0' ) { *p = *q ; p++ ; q++ ; } *p = '\0' ; } // ポインタ加算と代入を一度に書く void strcpy( char* p , char* q ) { while( *q != '\0' ) *p++ = *q++ ; // *(p++) = *(q++) *p = '\0' ; } // ポインタ加算と代入と'¥0'判定を一度に書く void strcpy( char* p , char* q ) { while( (*p++ = *q++) != '\0' ) // while( *p++ = *q++ ) ; でも良い ; }' ; } // ポインタ加算と代入と'¥0'判定を一度に書く void strcpy( char* p , char* q ) { while( (*p++ = *q++) != '// string copy ポインタのイメージで記載 void strcpy( char* p , char* q ) { while( *q != '\0' ) { *p = *q ; p++ ; q++ ; } *p = '\0' ; } // ポインタ加算と代入を一度に書く void strcpy( char* p , char* q ) { while( *q != '\0' ) *p++ = *q++ ; // *(p++) = *(q++) *p = '\0' ; } // ポインタ加算と代入と'¥0'判定を一度に書く void strcpy( char* p , char* q ) { while( (*p++ = *q++) != '\0' ) // while( *p++ = *q++ ) ; でも良い ; }' ) // while( *p++ = *q++ ) ; でも良い ; }
インクリメント演算子
C言語での++ や — といった演算子は、変数の前に書く場合と後ろに書く場合で挙動が異なる。
前置記法の “++i” は、i の値を使う前に +1 加算が行われ、”i++” は、iの値を使った後に、 +1 が行われる。
int main() { int i = 11 ; printf( "%d\n" , ++i ) ; // i = i + 1 ; // printf( "%d\n" , i ) ; と同じ // 12 が表示される printf( "%d\n" , i++ ) ; // printf( "%d\n" , i ) ; // i = i + 1 ; と同じ // 12 が表示され、i の値は13 return 0 ; }
構造体とポインタ
構造体を関数に渡して処理を行う例を示す。
struct Person { char name[ 10 ] ; int age ; } ; struct Person table[3] = { { "t-saitoh" , 55 } , { "tomoko" , 44 } , { "mitsuki" , 19 } , } ; void print_Person( struct Person* p ) { printf( "%s %d\n" , (*p).name , // * と . では . の方が優先順位が高い // p->name と簡単に書ける。 p->age ) ; // (*p).age の簡単な書き方 } void main() { for( int i = 0 ; i < 3 ; i++ ) { print_Person( &(table[i]) ) ; // print_Person( table + i ) ; でも良い } }
配列宣言でサイズは定数
C言語では、配列宣言を行う時は、配列サイズに変数を使うことはできない。
こういった話をすると「C# とか C++ とか JavaScript とか使えば、配列のサイズなんて考える必要ないから、そんなこと考えなくてもいいじゃん…」って思うかもしれないけど、こういった新しい言語では、この後の授業で説明するリスト構造やらハッシュといった機能を使っていて、それをどう扱っているのか知らずに、処理速度が遅い原因を見逃してしまうかもしれない。
void foo( int size ) { int array[ size ] ; // エラー for( int i = 0 ; i < size ; i++ ) array[ i ] = i*i ; } void main() { foo( 3 ) ; // 最近のC(C99)では、こういったプログラムも foo( 4 ) ; // 裏で後述のalloca()を使って動いたりする。(^_^; }
メモリ利用の効率
配列サイズには、定数式しか使えないので、1クラスの名前のデータを覚えるなら、以下のような宣言が一般的であろう。
#define MEMBER_SIZE 50 #define NAME_LENGTH 20 char name[ MEMBER_SIZE ][ NAME_LENGTH ] ;
しかしながら、クラスに寿限無とか銀魂の「ビチグソ丸」のような名前の人がいたら、20文字では足りない。(C言語の普通の配列宣言では、”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[ size ] ; と宣言したい。 int* p ; // size件のint型配列を作る p = (int*)alloca( sizeof( int ) * size ) ; // 確保した配列に値を保存 for( int i = 0 ; i < size ; i++ ) p[ i ] = i*i ; // 確保した値を使う for( int i = 0 ; i < size ; i++ ) printf( "%d\n" , p[ i ] ) ; } void main() { foo( 3 ) ; foo( 4 ) ; }
alloca() は、指定された byte 数のデータ領域の先頭ポインタを返すが、その領域を 文字を保存するために使うか、int を保存するために使うかは alloca() では解らない。alloca() の返り値は、使う用途に応じて型キャストが必要である。文字を保存するなら、(char*)alloca(…) 、 intを保存するなら (int*)alloca(…) のように使う。
ただし、関数内で alloca で確保したメモリは、その関数が終了すると、その領域は使えなくなる。このため、最後に alloca で確保したメモリが、最初に不要となる…ような使い方でしか使えない。
必要に応じてメモリを確保して、その領域が不要となる順序が「最後に確保したものから不要になる」という順序でなかったら、メモリはどのように管理すればいいだろうか?こういった場合のために、C 言語では malloc() 関数と free() 関数によるヒープメモリ領域がある。次の講義ではこの malloc, free について解説を行う。