JPH0644232B2 - 前方および後方への入れ子構造をもつ複数デ−タの記憶領域割り付け処理方式 - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はデータ処理システムに関するものであり、特に
前方および後方への入れ子構造をもつ複数データの記憶
領域割り付け処理方式に関する。

〔従来技術〕

たとえばプログラムでは、使用するデータとして他の所
定範囲のロケーション（記憶位置）にあるデータを参照
する、いわゆる入れ子（ネスト）構造をとっている場合
が少なくない。この場合順次のデータを記憶領域へ割り
付けて行く際に、それらの入れ子を解決して実際に参照
するロケーションの範囲の長さを求め代入する処理が必
要となる。

第２図は、このような入れ子構造をもつデータを参照す
るプログラムの例を示す。ただし、この例ではロケーシ
ョンが割当てられているが、このロケーションは最終的
な値であり、このロケーションを解決するために、本方
法が用いられる。この例では、ロケーション１００の要
素がＡからＢまでのロケーションの範囲を参照してお
り、ロケーションの長さは（Ｂ−Ａ）で算出される。し
かし、（Ｂ−Ａ）内にはロケーション３００の要素にそ
の段階で不確定な入れ子（Ｄ−Ｃ）があるため、最初の
段階では長さ（Ｂ−Ａ）を決定することができない。そ
こでロケーション３００の要素の入れ子の長さ（Ｄ−
Ｃ）を算出し、これに基づいて（Ｂ−Ａ）の全体の長さ
を決定している。このようにして入れ子を含むデータ長
さが確定すれば、データを先頭から順次記憶領域へ割り
付けることができる。

第３図は，さらに複雑な前方および後方への入れ子構造
をもつデータ列の例を示し、第４図は従来におけるその
記憶領域割り付け処理とを示したものである。

第３図において、実線はデータ列に対応する１本のロケ
ーション列を説明の便宜上分割して示したもので、
ｉ），ii），iii）はそれぞれ実線の接続部を表してい
る。また△印は入れ子をもつことにより長さが未決定な
ロケーションを示し、そして△印のロケーションから発
する２本の点線は入れ子となる他のロケーションの範囲
を示している。なお△印のロケーションには標識として
乃至の番号を付してある。

第４図は、第３図のデータ列を矢印で示す順方向に繰り
返し走査して、１回の走査ごとに入れ子が解決される未
決定ロケーションの番号を表している。すなわち、第１
回目の走査ではロケーションの入れ子しか解決できな
い。２回目にはロケーションの入れ子が解決できる。
これはロケーションが参照する範囲に含まれるロケー
ションが既に第１回目の走査で長さが決定済であるか
らである。しかし、他の未決定ロケーション，，
，，はいずれも入れ子の長さが不確定のままであ
る。次の第３回目の走査では、ロケーションとの入
れ子が解決し、第４回目にはロケーションが解決し、
第５回目にはロケーションが解決し、そして第６回目
には最後のロケーションが解決する。

このように従来方式によれば、入れ子が前方および後方
に存在する場合を含む第３図の例では、全ロケーション
が確定し、記憶領域が割り付け可能となるまで６回の走
査が必要であった。

〔発明が解決しようとする問題点〕

従来方式ではデータの入れ子が前方および後方に存在す
るような複雑な構造になる程そのようなデータ列を記憶
領域に割り付ける処理に手間がかかり、処理効率が低下
するという問題点があった。本発明はこの問題点を解決
することを目的とする。

〔問題点を解決するための手段〕

本発明は、前方および後方への入れ子構造をもつ複数デ
ータの記憶領域割り付け処理の高速化を図るため、ある
ロケーションの入れ子となるロケーションがその前方に
あれば順方向走査が有効であり、他方入れ子となるロケ
ーションが後方にあれば逆方向走査が有効であることに
着目して、入れ子解決のための走査を逆方向と順方向と
で交互に繰り返すことにより、１回の走査で解決可能な
入れ子に遭遇する可能性を高めるものであり、その構成
として、データ処理システムにおいて、前方および後方
への入れ子構造を含み要素順に配列された複数のデータ
とその決定されたデータ長とを記憶するための第１の手
段と、該第１の手段に保持されているデータ配列を指示
により配列の逆方向あるいは順方向に走査し、入れ子構
造をもつデータのうち可能なものについてのみ入れ子を
解決してその未決定のデータ長を決定し、当該データの
データ長として第１の手段に書き込む第２の手段と、上
記第２の手段に対して指示を行い、データの入れ子構造
が全て解決し、全てのデータのデータ長が決定されるま
で逆方向と順方向の走査を交互に実行させる第３の手段
とをそなえ、データ長が決定されたデータ配列について
ロケーションの順に記憶領域を割り付けることを特徴と
している。

〔実施例〕

以下に、本発明の詳細を実施例にしたがって説明する。

はじめに第３図に例示されたデータ列に本発明方式を適
用した場合の記憶領域割り付け処理を第５図に示す。

第５図において、第１回目は逆方向走査であり、ロケー
ション、，の入れ子を解決することができる。第
２回目は順方向走査であり、ロケーションの入れ子が
解決できる。第３回目は再び逆方向走査であり、ロケー
ション，，の入れ子が解決し、これで全てのロケ
ーションが確定する。次の第４回目は順方向走査である
がこのとき先頭のロケーションから順に記憶領域を割り
付ける。

このように本発明方式によれば、第４図に示した従来方
式の場合にくらべて走査回数を大幅に削減することがで
きる。

第１図は本発明の１実施例システムの構成図であり、第
６図はその処理フロー図である。第１図において１は処
理データ記憶部、２は長さ決定処理部、３は制御部、４
は記憶漁期割り当て処理部、５は結果データ記憶部を表
す。次に、第６図の処理フロー図を参照しつつ、第１図
の実施例システムの動作機能を説明する。

処理データ記憶部１には、要素名と、データの“長さ”
が決定済みであるか否かを表すフラグ（“０”＝決定と
する）と、“長さ”と、データの各領域が設けられてい
る。図示の例では要素Ａ、Ｂがそれぞれ他のロケーショ
ン（Ｂ１−Ａ１）、（Ｄ１−Ｃ１）を参照する入れ子構
造をとっていて長さが未決定であり、他の要素Ａ１，Ｂ
１，Ｂ２は４バイトの長さをもつものとして決定済みで
ある。

長さ決定処理部２は処理データ記憶部１を逆あるいは順
方向に走査し、入れ子構造のデータ要素であるためにロ
ケーションが不確定であるような要素を順次取り出し
て、解決可能であればその入れ子のロケーション間差で
ある“長さ”を求めて処理データ記憶部１の長さ領域に
書き込み、そして同時にフラグを“１”にセットして決
定済みを表示させる。走査を逆方向に行うか順方向に行
うかは制御部３からの指示にしたがう。また長さ決定処
理部２は走査を１回終了するたびに制御部３へ通知す
る。

制御部３は、長さ決定処理部２からの通知にしたがっ
て、逆方向走査終了時に記憶領域割り当て処理部４に処
理を要求して、可能なものについて記憶領域割り当てを
行わせる（第６図参照）。

記憶領域割り当て処理部４は、処理データ記憶部１から
要素ごとに“長さ”とデータとを読み出し、各要素ごと
のデータに“長さ”によって示される大きさの記憶領域
すなわちロケーションを割り付けて、結果データ記憶部
５に格納する。しかし、処理データ記憶部１中に要素に
解決未済の要素があれば制御部３にその旨を通知する
（第６図参照）。

これにより制御部３は、走査方向を順方向に反転して、
走査実行を長さ決定処理部２へ指示する。長さ決定処理
部２は処理データ記憶部１を順方向に走査して不確定要
素の解決処理を行い、走査終了時に制御部３へ終了を通
知する（第６図参照）。

制御部３はこれに応答して走査方向を逆方向にした走査
実行を長さ決定処理部２へ指示する（第６図参照）。
長さ決定処理部２は逆方向走査を行い、不確定要素があ
れば解決し、前回と同様に走査終了時に制御部３へ通知
し、記憶領域割り当て処理部４の処理を要求する。

このようにして、全ての不確定要素について解決と記憶
領域割り当てが完了したとき、動作は終了する。

〔発明の効果〕

以上のように、本発明によれば前方および後方への入れ
子構造をもつ複数データの記憶領域割り当てが従来より
も著しく高速化され、たとえば入れ子の複雑さにもよる
が数倍程度の高速化が得られる場合があり、処理効率の
改善に役立てることができる。

【図面の簡単な説明】

第１図は本発明の１実施例システムの構成図、第２図は
入れ子構造のデータをもつプログラムの説明図、第３図
は前方および後方への入れ子構造をもつデータの１例の
説明図、第４図は従来方式による記憶領域割り当て処理
の説明図、第５図は本発明方式に基づく記憶領域割り当
て処理の説明図、第６図は第１図に示した実施例システ
ムの処理フロー図である。 図中、１は処理データ記憶部、２は長さ決定処理部、３
は制御部、４は記憶領域割り当て処理部、５は結果デー
タ記憶部を示す。

フロントページの続き (72)発明者 林 登喜雄 神奈川県川崎市中原区上小田中1015番地 富士通株式会社内 (56)参考文献 特開 昭58−178453（ＪＰ，Ａ)

Claims (1)

【特許請求の範囲】
1. 【請求項１】データ処理システムにおいて，前方および
   後方への入れ子構造を含み要素順に配列された複数のデ
   ータとその決定されたデータ長とを記憶するための第１
   の手段と，該第１の手段に保持されているデータ配列を
   指示により配列の逆方向あるいは順方向に走査し，入れ
   子構造をもつデータのうち可能なものについてのみ入れ
   子を解決してその未決定のデータ長を決定し，当該デー
   タのデータ長として第１の手段に書き込む第２の手段
   と，上記第２の手段に対して指示を行い，データの入れ
   子構造が全て解決し，全てのデータのデータ長が決定さ
   れるまで逆方向と順方向の走査を交互に実行させる第３
   の手段とをそなえ，データ長が決定されたデータ配列に
   ついてロケーションの順に記憶領域を割り付けることを
   特徴とする前方および後方への入れ子構造をもつ複数デ
   ータの記憶領域割り付け処理方式。