1．1 オートマトンと状態遷移図

第５章データの取扱い
５．１
５．２
５．３
５．４
５．５
領域管理
記号表
型
中間言語
実行時のデータの取扱い
５．１領域管理
（１）領域管理の種類
①スタック
②ヒープ領域
領域確保単位が固定長の場合と不定長がある。
（２）スタック
//初期設定
StackPointer=0;
//内容表示
private void Push(element E)
{ if(StackPointer>=MAXSTACK) MessageBox.Show("スタックが満杯です");
else
Stack[StackPointer++]=E ;
}
private element Pop()
{ if(StackPointer<=0) MessageBox.Show("スタックが空です");
else return Stack[--StackPointer] ;
}
Push
Pop
Pop
（２）固定長領域の管理
【データ領域例】
public struct ElementSet
{
public ElementData Element;
public long
Next;
}
public ElementSet[] DataArea = new ElementSet[500];
public long ErasedP;
//
未使用領域の先頭領域
public long DataP;
//
格納しているデータの先頭
固定長領域の初期状態
最初、以下のような状態にしておく。
未使用ポインタ
未使用要素
未使用要素
未使用要素
未使用要素
未使用要素
未使用要素
未使用要素
未使用要素
初期化処理の例
// 配列による表現（空ポインタを-1としておく）
public struct ElementData
{
…（領域構成の宣言）
}
public struct ElementSet
{
public ElementData Element; public long Next;
}
public ElementSet[] DataArea = new ElementSet[500];
public long ErasedP;
//
未使用領域の先頭領域
private void 初期化( )
{
for(int i=0;i<DataArea.Length-1;i++) DataArea[i].Next=i+1;
DataArea[DataArea.Length - 1].Next = -1;
ErasedP=0;
}
領域の確保
領域確保では，現在の未使用ポインタが指している要素を使うものとする。
① 未使用ポインタを関数値とする。
② 未使用ポインタが指しているポインタを未使用ポインタとする。
未使用ポインタ
この値を
関数値とする
未使用ポインタ
未使用要素
使用領域
未使用要素
未使用要素
未使用要素
未使用要素
未使用要素
未使用要素
未使用要素
未使用要素
未使用要素
未使用要素
未使用要素
未使用要素
未使用要素
未使用要素
領域の返却
領域の返却とは，指定された要素を未使用領域の管理下に戻すこと。
①未使用ポインタの内容を返却領域のポインタとする。
②未使用ポインタを返却領域へのポインタとする。
未使用ポインタ
未使用ポインタ
使用領域
ⅰ）
使用領域
使用領域
ⅱ）
返却領域
使用領域
ⅰ）
使用領域
未使用要素
使用領域
未使用要素
未使用要素
未使用要素
未使用要素
未使用要素
未使用要素
未使用要素
未使用要素
プログラム例
private long GetArea()
{
// 領域の確保
long R = ErasedP; ErasedP = DataArea[ErasedP].Next;
return R;
}
private void FreeArea(long P)
{ if(P<0) return;
DataArea[P].Next=ErasedP; ErasedP = P;
}
（３）不定長領域の管理
むやみに不定長領域を使うとガーベジコレクション処理が必要となる。
処理速度の低下を引き起こす。
①できるだけ固定長にして管理できるようにする。
②物理的には不定長だがプログラム上は固定長で扱うようにする。
（言語に備わっている文字列の配列等を使って管理する）
不定長領域のGC処理例
①使用領域の管理テーブルを作業領域としての管理テーブルに移す。（元の
格納位置を保存）
②作業領域としての管理テーブルをアドレス順にソートする。
③アドレスの若い順にシフトして新しいアドレスを得る。
④作業領域としての管理テーブルを元の管理テーブルに戻す。
不定長領域のGC処理例
①元の管理テーブル
③データ領域の移動とポインタ付替え
ID サイズ
ID サイズ
1
6
2
2
3
1
4
4
5
5
6
3
②作業用管理テーブル（ソート後）
ID サイズ
④元の管理テーブルに戻す
ID サイズ
6
1
2
2
1
3
4
4
5
5
3
6

Download Report