JPH0581093A - 双方向チエーン処理方式 - Google Patents

Abstract

(57)【要約】 【構成】双方向チェーンを持つテーブルの各エントリ１
〜５に物理的な順番を示すインデックスを付し、前後エ
ントリ１〜５が持つインデックスの合計をリンク情報と
してリンク情報格納領域６〜１０に格納する。 【効果】唯一のリンク情報格納領域を各エントリに確保
することにより、双方向チェーンのテーブル構造を実現
することができるため、メモリの節約を達成できるとと
もに、インデックスと加減算を使用しているため、アド
レスやプール演算を扱えないコンピュータ言語でも使用
できるので、メモリを節約しつつ双方向チェーンのテー
ブルを構築達成できる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、双方向チェーン処理方
式、特に、リンク情報を用いて双方向チェーンを処理す
る双方向チェーン処理方式に関する。

【０００２】

【従来の技術】従来の双方向チェーン処理方式は、一つ
の例では双方向チェーンを持つテーブル構造が、前後の
エントリのインデックス値、あるいはアドレス値を、す
べてのエントリに前方向および後方向のリンク情報とし
てそれぞれ保持させることにより実現している。

【０００３】また、従来の双方向チェーン処理方式は他
の例では、「テーブル処理における双方向リスト構成方
式（特開昭６３−２１９０３２）」に掲載されているよ
うに次のようにすることで１つのリンク情報で実現して
いる。

【０００４】あらかじめ前方向と後方向の隣り合うテー
ブルのアドレスの排他的論理和を算出し、各テーブルの
ポインタ領域に格納しておく。

【０００５】順方向の場合、現在処理しているテーブル
のポインタ領域の内容と順方向で１つ前のテーブルのア
ドレスとの排他的論理和を算出することにより、順方向
で１つ後のテーブルのアドレスを求める。

【０００６】また、逆方向の場合、現在処理しているテ
ーブルのポインタ領域の内容と逆方向で１つ前のテーブ
ルのアドレスとの排他的論理和を算出することにより、
逆方向で１つ後のテーブルのアドレスを求める。

【０００７】

【発明が解決しようとする課題】しかしながら、このよ
うな上述した従来の双方向チェーン処理方式は、前方向
および後方向のリンク情報を格納する処理方式では、二
つのリンク情報格納領域が必要であるため、リンク情報
格納領域が占有するメモリサイズがエントリ数の大きな
テーブル程、無視できなくなるという欠点がある。

【０００８】また、前後のエントリのアドレス値の排他
的論理和を格納する処理方式では、リンク情報格納領域
を一つにすることでメモリを節約できるが、アドレスに
ついてブール演算が扱えるプログラム言語を必要とする
という欠点があった。

【０００９】

【課題を解決するための手段】本発明の双方向チェーン
処理方式は、双方向チェーンを持つテーブルの各エント
リに物理的な順番を示すインデックスを付し、前後のエ
ントリが持つインデックスの合計をリンク情報としてリ
ンク情報格納領域に格納するように構成される。

【００１０】

【実施例】次に、本発明の実施例について、図面を参照
して詳細に説明する。

【００１１】図１は本発明の一実施例を示すリンク状態
図である。

【００１２】図１に示す双方向チェーン処理方式におい
て、エントリ１は始端となるエントリでありインテック
ス値＝１を持ち、エントリ２は終端となるエントリであ
りインデックス値＝２を持つ。エントリ３〜５は中間に
位置するエントリである。

【００１３】リンク情報格納領域６〜１０は、（１）式
の結果であるリンク情報Ａを格納している。なお、リン
ク情報格納領域６を計算する場合の前方向エントリのイ
ンデックス値は“０”とし、リンク情報格納領域７を計
算する場合の後方向エントリのインデックス値は“０”
とする。

【００１４】さらに、リンク状態ａ〜ｄは各エントリ間
の正順方向のリンク状態を示し、リンク状態ｅ〜ｈは各
エントリ間の逆順方向のリンク状態を示す。

【００１５】順方向チェーンは、エントリ１→エントリ
４→エントリ３→エントリ５→エントリ２とし、逆順方
向のチェーンは、前記順方向チェーンの逆向きとする。

【００１６】以下の説明では、チェーンを辿ってｉ番目
のエントリのインデックス値をＩ（ｉ）として表す。

【００１７】ここで、正順検索の場合はエントリ１を１
番目と数え、逆順検索の場合はエントリ２を１番目と数
える。

【００１８】インデックスＩ（ｉ）のエントリｉのリン
ク情報格納領域の値であるリンク情報Ａは次の（１）式
で示される。

【００１９】 Ａ＝Ｉ（ｉ−１）＋Ｉ（ｉ＋１）・・・（１） また、後続エントリ（ｉ＋１）のインデックス値Ｉ（ｉ
＋１）は、次の（２）式で示されるリンク値Ｂとして求
められる。

【００２０】 Ｂ＝Ａ−Ｉ（ｉ−１）・・・（２） さて、正順検索ではリンク状態ａ〜ｄを用いるが、エン
トリ３からエントリ５のインデックス値Ｉ（４）を求め
る場合は、式（３）に示すようとなる。

【００２１】 エントリ５の エントリ３の エントリ４の インデックス値＝リンク情報格納領域８の値−インデックス ＝｛Ｉ（２）＋Ｉ（４）｝−Ｉ（２） ・・・（３） ＝Ｉ（４） また、逆順検索はリンク状態ｅ〜ｈを用いるが、エント
リ３からエントリ４のインデックス値Ｉ（２）を求める
場合は、式（４）に示すようとなる。

【００２２】 エントリ４の エントリ３の エントリ５の インデックス値＝リンク情報格納領域８の値−インデックス ＝｛Ｉ（２）＋Ｉ（４）｝−Ｉ（４） ・・・（４） ＝Ｉ（２） なお、式（２）で示されるリンク情報Ｂが“１”か
“２”かを判定することで、検索の終了を判断できる。

【００２３】

【発明の効果】本発明の双方向チェーン処理方式は、唯
一のリンク情報格納領域を各エントリに確保することに
より、双方向チェーンのテーブル構造を実現することが
できるため、メモリの節約を達成できるとともに、イン
デックスと加減算を使用しているため、アドレスやプー
ル演算を扱えないコンピュータ言語でも使用できるの
で、メモリを節約しつつ双方向チェーンのテーブルを構
築達成できるという効果がある。

【図面の簡単な説明】

【図１】本発明の一実施例を示すリンク状態図。

【符号の説明】

１〜４ エントリ ６〜１０ リンク情報格納領域 ａ〜ｈ リンク状態

───────────────────────────────────────────────────── フロントページの続き (72)発明者 市川 博之 新潟県新潟市万代四丁目４番27号新潟日本 電気ソフトウエア株式会社内

Claims (2)

【特許請求の範囲】
1. 【請求項１】 双方向チェーンを持つテーブルの各エン
   トリに物理的の順番を示すインデックスを付し、前後の
   チェーンのエントリが持つインデックスの合計を当該エ
   ントリのリンク情報としてリンク情報格納領域に格納す
   ることを特徴とする双方向チェーン処理方式。
2. 【請求項２】 後続エントリのインデックス値を当該エ
   ントリのリンク情報と先行するエントリのインデックス
   値との差により求めることを特徴とする双方向チェーン
   処理方式。