第5章 データの取扱い 5.1 5.2 5.3 5.4 5.5 領域管理 記号表 型 中間言語 実行時のデータの取扱い 5.1 領域管理 (1)領域管理の種類 ①スタック ②ヒープ領域 領域確保単位が固定長の場合と不定長がある。 (2)スタック //初期設定 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 (2)固定長領域の管理 【データ領域例】 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; } (3)不定長領域の管理 むやみに不定長領域を使うとガーベジコレクション処理が必要となる。 処理速度の低下を引き起こす。 ①できるだけ固定長にして管理できるようにする。 ②物理的には不定長だがプログラム上は固定長で扱うようにする。 (言語に備わっている文字列の配列等を使って管理する) 不定長領域の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
© Copyright 2025 ExpyDoc