JPH0363739A - リスト処理方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は記憶単位であるデータがポインタで連結された
リスト構造に関し、特にそのリスト構造を有するリスト
処理システムに関する。

（従来の技術） 従来、この種のリスト処理方式では記憶領域中のリスト
領域に各データを割付け、データは互いに他のデータへ
のポインタを保持してリスト構造を構成していた。この
リスト構造を処理するには、各データの形を識別するた
め次のような方法を用いていた。

ひとつはデータが存在するリスト領域中のアドレスとと
もに、当該データの形を示すタグを計算機表現の一語中
に併せ持つタグドポインタ方式が公知である。

第６図は、タグドポインタの一例を表わした説明図であ
る。タグドポインタ２０１の中には、データ２０２が割
付けられているアドレスを示すポインタ２０３と、デー
タ２０２の形を示すタグ２０４とがある。このタグによ
ってポインタを指す先のデータ形を識別することができ
る。

他に、データ形を示すタグを各データの先頭に付与する
オブジェクトタグ方式が公知である。

第７図は、オブジェクトタグ方式によるデータの一例を
示す説明図である。ポインタ３０１で一語をすべてポイ
ンタとして使用する代りに、データ３０２の先頭に当該
データ形を示すタグを設けている。

どちらの方式も、各データには他のデータへのポインタ
、もしくは即位を保持してリスト構造を構成している。

リスト処理システムは、これらのリスト構造を作成する
とともに、変更するシステムである。そのため、システ
ム実行中に、どこからも参照されなくなるデータが出現
することがある。このようなデータを、ガーベジデータ
と呼ぶ。リスト処理システムでは、リスト領域に次々に
データを割付けていくと、やがてリスト領域が尽き、ガ
ーベジデータの置かれているリスト領域を再利用するた
めにガーベジコレクションを行う。

ガーベジコレクションには数種類の方式があるが、基本
的にはあるルートとなるポインタからたどることのでき
るデータを使用中のデータとし、どの方式でも、それら
使用中のデータのみをリスト領域の一端に詰め寄せてい
る。これによって、残りの領域が再利用可能になるとい
う点で各方式は一致している。例えば、コピー法は、リ
スト領域を２等分にし、一方のリスト領域を使いきると
、いま一方のリスト領域の先頭から使用中のデータを詰
め寄せることによりガーベジ領域を回収する。移動した
データが元に置かれていた場所には、移動先へのポイン
タを記しておき、他のデータがそれを参照していれば、
移動先へ向ける。

また、マークスィーブ法では、使用中のデータがどこか
ら参照されているかを知るために、参照されているデー
タから参照しているデータへの逆転ポインタを作成し、
使用中のデータをリスト領域の先頭へ詰め寄せる。この
ときに、逆転ポインタで指示されるそのデータをポイン
タで参照しているので、当該ポインタを移動先に向ける
。

（発明が解決しようとする課題） 上述した従来のリスト処理方式において、タグドポイン
タではポインタデータ内にタグを付与しているため、デ
ータを割付けるリスト領域に制限ができる。例えば、−
語が３２ビツトでポインタ部がそのうち２４ビツトであ
れば、論理的に４ギガバイトを使用できる。ところが１
６メガバイトしか使用できないと言う欠点がある。

オブジェクトタグ方式では、データを参照しないと当該
テ′−夕の形がわからないため、データの形の判定効率
が低くなると言う欠点がある。

ガーベジコレクションではマークスイープ法では、デー
タを指すすべてのポインタを逆転、および回復するため
に処理が複雑になる。これによって、リスト処理システ
ムの中断時間が長くなってしまうか、もしくはコピー法
によってＪスト領域を２分割し、実質的に利用できる記
憶領域が半減してしまうと言う欠点がある。

本発明の目的は、あるデータから他のデータへ直接ポイ
ンタを張らずに間接ポインタを介して指示するとともに
、各データ中の他のデータへの参照情報には、そのデー
タを指す間接ポインタのアドレスに、そのデータの種類
を表すタグを付与したタグドポインタを用い、未使用の
間接ポインタをポインタで連結して管理することにより
上記欠点を除去し、データの形を効率的に判定でき、実
効記憶領域を大きくとることができるように構成したリ
スト処理方式を提供することにある。

（課題を解決するための手段） 本発明によるリスト処理方式は間接ポインタ参照手段と
、データ識別手段と、フリーチェーン管理手段とを具備
して構成したものである。

間接ポインタ参照手段は、あるデータから他のデータへ
直接ポインタを張らずに間接ポインタを介して指示する
ためのものである。

データ識別手段は、各データ中の他のデータへの参照情
報には当該データを指す間接ポインタのアドレスに当該
データの種類を表すタグを付与したタグドポインタを用
いるためのものである。

フリーチェーン管理手段は、未使用の間接ボインクをポ
インタで連結して管理するためのものである。

（実施例） 次に、本発明について図面を参照して説明する。

第１図は、本発明によるリスト処理方式の一実施例を示
すブロック図である。

第１図において、１は入出力制御部、２はリスト処理制
御部、３は記憶域管理部、４は記憶領域、５は間接ポイ
ンタ領域、６はリスト領域、７は間接参照手段、８はデ
ータ識別手段、９はフリーチェーン管堺手段、１０．１
１はそれぞれデータ、１２〜１４はそれぞれ変数、１５
．１６はそれぞれ間接ポインタである。

入出力制御部１から利用者の要求を受付けると、リスト
処理制御部２は構文解析を行い、必要に応じて記憶域管
理部３ヘデータの作成／更新を要求する。その結果がリ
スト処理制御部２に返され、入出力制御部１から利用者
へ伝えられる。記憶域Ｗ球部３は、記憶領域４を管理し
ている。記憶領域４に間接ポインタ領域５、ならびにリ
スト領域６を設けることにより間接参照手段７を実現し
ている。また、記憶領域４はさらにいくつかの変数から
構成されている。変数ＦＴ１４は、間接ポインタ領域中
の未使用データを指し、その未使用データ中には他の未
使用データのアドレスが記されている。

このようにして、最後の未使用データにはＮＵＬＬポイ
ンタが記され、間接ポインタ領域中の未使用データはポ
インタで結ばれたチェーン構造を構成している。このよ
うに、未使用の間接ポインタはフリーチェーン管理手段
９により管理されている。

変数ＬＴ１３には、初期値としてリスト領域６の先頭ア
ドレスを保持している。データがリスト領域６に割付け
られるごとに変数ＬＴ１３の値は増加し、常に、次に割
付けられるべきデータの位置を示している。変数ＲＯＯ
Ｔｌ　２はガーベジコレクションのときに、現在使用中
であるデータを抽出するためのルートポインタである。

いま、変数ＲＯＯＴｌ２は間接ポインタ１５を指し、間
接ポインタ１５はデータ１０を指している。データ１０
の最初の要素は、データ１１へのポインタであるが、直
接データ１１をポイントせずに、データ１１のデータ形
ｔとともに間接ポインタ１６のアドレスを保持し、間接
ポインタ１６がデータ１１をポイントしている。

このように、タグとアドレスとを一体化することによっ
て、データ識別手段８を実現している。

ここで、間接ポインタ領域５は記憶領域４の下位アドレ
スから割当てる。一般には、データは複数語の大きさを
有し、−語の間接ポインタより十分大きいと考えられる
。そこで、間接ポインタ領域５とリスト領域６との境界
は、アドレス空間内の下位アドレスに設けることができ
る。

例えば、−語が３２ビツトより成る計算機において、間
接ポインタ領域５とリスト領域６との境界アドレスを、
１６進級の１００００００以下であるとする。すると、
間接ポインタへのアドレスでは、必ず上位１バイトがＯ
という規則が成立つ。そこで、この上位１バイトをタグ
して用いる。そうすることによって、ポインタの指す先
を参照せずに、データの形が識別でき、且つリスト領域
の大きさに制限が起こらない。

次に、新しいデータを割付ける手順を説明する。データ
の割付けには、間接ポインタとリスト領域６とのなかに
データの割付は領域を確保するＯ 第２図は、データの割付は処理を表わした流れ図である
。ここで、←は代入を表し、（）はポインタによって指
される記憶領域の内容を意味している。まず、間接ポイ
ンタを割付ける。

ＦＴ１４がＮＵＬＬポインタであったならば、ガーベジ
コレクションを行い、それでもＦＴ１４がＮＵＬＬであ
ったならば、間接ポインタ領域不足のため、リスト処理
システムを終了する。

このとき、ＦＴ１４がＮＵＬＬでなかったならば、レジ
スタＰＫ″ＦＴ１４の値を代入し、Ｐの指す次の間接ポ
インタのアドレスをＦＴ１４に代入して、Ｌｉ２Ｓが指
す先からデータを割付けるだけのリスト領域６が確保で
きるかを調べる。もし、ガーベジコレクションを行って
もリスト領域６が確保できなければ、リスト領域不足の
ためリスト処理システムを終了する。もし、確保できた
ならば、レジスタＰの指す間接ポインタにＬｉ２Ｓの値
を代入し、ＬＴ１３Ｖｃ割付けたデータサイズを加算す
る。レジスタＰの先頭の１バイトに割付けられたデータ
の形の示すタグを代入し、結果としてＰを戻す。

次に、ガーベジコレクションを説明する。

第３図は、ガーベジコレクションの処理を表わした流れ
図である。まず、ＲＯＯＴ１２から、たどることのでき
るすべての間接ポインタにマークをする。マークの方法
は特に限定しないが、すべてのデータを４バイトの倍数
にすることによってアドレス値の下位２ビツトを常にＯ
にすることができ、これらのビットを１にすることで行
える。

次に、間接ポインタのフリーチェーンを作成する。ＦＴ
１４にＮＵＬＬポインタの先頭アドレスを代入し、レジ
スタＰに間接ポインタ領域の先頭アドレスを代入する。

もし、Ｐの指す間接ポインタのマークがオフならば、Ｐ
の指す間接ポインタにＦＴ１４の値を代入し、ＦＴ１４
にはＰの値を代入する。Ｐの指す間接ポインタのマーク
がオンであれば、Ｐの指す間接ポインタの先にあるデー
タの先頭４バイトの内容を、Ｐの指す間接ポインタに退
避する。データの先頭４バイトにＰの値（間接ポインタ
のアドレス）を代入する。これを第４図に示す。ここで
、タグ値０は未定義であるとする。

次に、レジスタＰを次の間接ポインタに向け、間接ポイ
ンタ領域５の終端になるまで上記操作を繰返し、最後に
、リスト領域を回収する。レジスタＰ、Ｑの内容をリス
ト領域６の先頭アドレスで初期化し、レジスタＰの内容
がＬｉ２Ｓと等しくなるまで次の処理を繰返す。

レジスタＰの指すデータの先頭４バイトのタグがＯであ
るならば、その先頭４バイトは間接ポインタを指してい
るので、その間接ポインタに退避されている値をデータ
に戻し、レジスタＱの値を間接ポインタに代入する。そ
して、そのデータをレジスタＱの指す先に転送する。こ
れを第５図に示す。レジスタＰ、Ｑの内容にそれぞれデ
ータサイズを加算する。もし、レジスタＰの指す先のタ
グが０でなければ、そのデータはガーベジデータである
のでレジスタＰの内容だけをデータサイズに加算する。

レジスタＰの内容がＬｉ２Ｓと等しくなったならば、レ
ジスタＱの内容をＬｉ２Ｓに代入し、ガーベジコレクシ
ョンを終了する。

（発明の効果） 以上説明したように本発明は、あるデータから他のデー
タへ直接ポインタを張らずに間接ポインタを介して指示
するとともに、各データ中の他のデータへの参照情報に
は、そのデータを指す間接ポインタのアドレスに、その
データの種類を表わすタグを付与したタグドポインタを
用い、未使用の間接ポインタをポインタで連結して管理
することにより、リスト領域の大きさに制限を与えず、
タグドポインタを実現し、データを参照せずにデータの
形が識別できると言う効果がある。また、ガーベジコレ
クションでは、各データの内容を書換えずに間接ポイン
タのみを修正するだけで、データの移動に対応できるた
め、効率良く処理が行え、リスト領域を２等分する必要
もないという効果がある。

【図面の簡単な説明】

第１図は、本発明によるリスト処理方式の一実施例を示
すブロック図である。 第２図は、本発明のデータ割付は処理を表わす流れ図で
ある。 第３図は、本発明のガーベジコレクション処理を表わす
流れ図である。 第４図および第５図は、それぞれ本発明のガーベジコレ
クション処理における間接ポインタ、およびデータの変
化を表わす説明図である。 第６図は、従来技術によるタグドポインタを示す説明図
である。 第７図は、従来技術によるオブジェクトタグを示す説明
図である。 １・・・入出力制御部　　２・・・リスト処理制御部３
・・・記憶域管理部　　４・・・記憶領域５・・・間接
ポインタ領域 ６・・・リスト領域　　　７・・・間接参照手段８・・
・データ識別手段 ９・・・フリーチェーン管理手段 １０．１１．２０２．３０２・・・データ１２〜１４・
・・変数 １５．１６・・・間接ポインタ ２０１・・・タグドポインタ ２０３．３０１・・・ポインタ ２０４・・・タグ

Claims (1)

【特許請求の範囲】
1. あるデータから他のデータへ直接ポインタを張らずに間
   接ポインタを介して指示するための間接ポインタ参照手
   段と、前記各データ中の他のデータへの参照情報には当
   該データを指す前記間接ポインタのアドレスに当該デー
   タの種類を表わすタグを付与したタグドポインタを用い
   るためのデータ識別手段と、未使用の間接ポインタをポ
   インタで連結して管理するためのフリーチェーン管理手
   段とを具備して構成したことを特徴とするリスト処理方
   式。