米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> 松下電器産業株式会社

発明の名称 データ処理方法及びその装置
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開平7−200619
公開日 平成7年(1995)8月4日
出願番号 特願平6−787
出願日 平成6年(1994)1月10日
代理人 【弁理士】
【氏名又は名称】前田 弘 (外2名)
発明者 永田 昭二 / 三宅 二郎
要約 目的
データを持つテーブルが連鎖されてなる連鎖リストに対して処理を行なうデータ処理装置において、記憶手段におけるテーブル領域のサイズを縮小することによって、双方向リストが記憶手段に占める領域のサイズを縮小する。

構成
キュー記憶領域11内には、各々のテーブルがテーブル毎の次テーブルキューにより双方向に連鎖される連鎖リストが格納される。ここで、各々のテーブルの中の次テーブルキューには、当該テーブルの前後のテーブルのアドレス値同士の排他的論理和により算出される値が設定されている。前記連鎖リストに対して、エンキュー手段21はテーブル追加を行ない、デキュー手段22はテーブル削除を行ない、検索手段23はテーブル検索を行なう。
特許請求の範囲
【請求項1】 記憶手段に格納される、データを持つテーブルが連鎖されてなる連鎖リストに対して、テーブルの動的な追加、削除及び検索を行なうデータ処理方法であって、各々のテーブルがテーブル毎の次テーブルキューにより双方向に連鎖される連鎖リストに対して、テーブル追加を行なうエンキュー処理と、テーブル削除を行なうデキュー処理と、テーブル検索を行なう検索処理とを備え、各々のテーブルの中の次テーブルキューには、当該テーブルの前後のテーブルのアドレス値同士の排他的論理和により算出される値を設定することを特徴とするデータ処理方法。
【請求項2】 前記エンキュー処理は、(1) 順方向又は逆方向のキューヘッダから連鎖リストの先頭テーブルのアドレスを求め該先頭テーブルのアドレスを現在のアドレスとして設定するステップと、(2) 現在のアドレスにより示されるテーブルである現在のテーブルの中のデータの内容を調べるステップと、(3) 現在のテーブルが追加位置のテーブルであるか否かを調べるステップと、(4) 現在のテーブルが追加位置のテーブルでない場合に、現在のテーブルの直前のテーブルのアドレス値と現在のテーブル中の次テーブルキューの値との排他的論理和により現在のテーブルの次のテーブルのアドレスを導出し該次のテーブルのアドレスを新たに現在のアドレスとして設定し、ステップ(2)に戻るステップと、(5) 現在のテーブルが追加位置のテーブルである場合に、追加テーブルを加えて連鎖リストを再構成するステップとを有していることを特徴とする請求項1に記載のデータ処理方法。
【請求項3】 前記デキュー処理は、(1) 順方向又は逆方向のキューヘッダから連鎖リストの先頭テーブルのアドレスを求め該先頭テーブルのアドレスを現在のアドレスとして設定するステップと、(2) 現在のアドレスにより示されるテーブルである現在のテーブルの中のデータの内容を調べるステップと、(3) 現在のテーブルが削除位置のテーブルであるか否かを調べるステップと、(4) 現在のテーブルが削除位置のテーブルでない場合に、現在のテーブルの直前のテーブルのアドレス値と現在のテーブル中の次テーブルキューの値との排他的論理和により現在のテーブルの次のテーブルのアドレスを導出し該次のテーブルのアドレスを新たに現在のアドレスとして設定し、ステップ(2)に戻るステップと、(5) 現在のテーブルが削除位置のテーブルである場合に、削除テーブルを除いて連鎖リストを再構成するステップとを有していることを特徴とする請求項1に記載のデータ処理方法。
【請求項4】 前記検索処理は、(1) 順方向又は逆方向のキューヘッダから連鎖リストの先頭テーブルのアドレスを求め該先頭テーブルのアドレスを現在のアドレスとして設定するステップと、(2) 現在のアドレスにより示されるテーブルである現在のテーブルの中のデータの内容を調べるステップと、(3) 現在のテーブルが検索目的に一致するテーブルであるか否かを調べるステップと、(4) 現在のテーブルが検索目的に一致するテーブルでない場合に、現在のテーブルの直前のテーブルのアドレス値と現在のテーブル中の次テーブルキューの値との排他的論理和により現在のテーブルの次のテーブルのアドレスを導出し該次のテーブルのアドレスを新たに現在のアドレスとして設定し、ステップ(2)に戻るステップと、(5) 現在のテーブルが検索目的に一致するテーブルである場合に、目的のテーブルに対して処理を行なうステップと有していることを特徴とする請求項1に記載のデータ処理方法。
【請求項5】 データを持つテーブルが連鎖されてなる連鎖リストに対してテーブルの動的な追加、削除及び検索を行なうデータ処理装置であって、各々のテーブルがテーブル毎の次テーブルキューにより双方向に連鎖される連鎖リストを格納する記憶手段と、該記憶手段に格納される連鎖リストに対して、テーブル追加を行なうエンキュー手段と、テーブル削除を行なうデキュー手段と、テーブル検索を行なう検索手段とを備え、各々のテーブルの中の次テーブルキューは、当該テーブルの前後のテーブルのアドレス値同士の排他的論理和により算出される値を有していることを特徴とするデータ処理装置。
【請求項6】 前記エンキュー手段は、順方向又は逆方向のキューヘッダから連鎖リストの先頭テーブルのアドレスを発生させる先頭テーブルアドレス発生手段と、追加位置のテーブルを見つけるために一のテーブルの次のテーブルのアドレスを導出する次テーブルアドレス導出手段とを有していることを特徴とする請求項5に記載のデータ処理装置。
【請求項7】 前記デキュー手段は、順方向又は逆方向のキューヘッダから連鎖リストの先頭テーブルのアドレスを発生させる先頭テーブルアドレス発生手段と、削除位置のテーブルを見つけるために一のテーブルの次のテーブルのアドレスを導出する次テーブルアドレス導出手段とを有していることを特徴とする請求項5に記載のデータ処理装置。
【請求項8】 前記検索手段は、順方向又は逆方向のキューヘッダから連鎖リストの先頭テーブルのアドレスを発生させる先頭テーブルアドレス発生手段と、検索位置のテーブルを見つけるために一のテーブルの次のテーブルのアドレスを導出する次テーブルアドレス導出手段とを有していることを特徴とする請求項5に記載のデータ処理装置。
【請求項9】 前記次テーブルアドレス導出手段は、一のテーブルの直前のテーブルのアドレス値と前記一のテーブルの中の次テーブルキューの値との排他的論理和により前記一のテーブルの次のテーブルのアドレスを導出することを特徴とする請求項6、請求項7又は請求項8に記載のデータ処理装置。
【請求項10】 前記エンキュー手段は、順方向又は逆方向のキューヘッダから連鎖リストの先頭テーブルのアドレスを発生させる第1の先頭テーブルアドレス発生手段と、追加位置のテーブルを見つけるために一のテーブルの次のテーブルのアドレスを導出する第1の次テーブルアドレス導出手段とを有し、前記デキュー手段は、順方向又は逆方向のキューヘッダから連鎖リストの先頭テーブルのアドレスを発生させる第2の先頭テーブルアドレス発生手段と、削除位置のテーブルを見つけるために一のテーブルの次のテーブルのアドレスを導出する第2の次テーブルアドレス導出手段とを有し、前記検索手段は、順方向又は逆方向のキューヘッダから連鎖リストの先頭テーブルのアドレスを発生させる第3の先頭テーブルアドレス発生手段と、検索位置のテーブルを見つけるために一のテーブルの次のテーブルのアドレスを導出する第3の次テーブルアドレス導出手段とを有しており、前記第1、第2及び第3の先頭テーブルアドレス発生手段同士は一体であると共に、前記第1、第2及び第3の次テーブルアドレス導出手段同士は一体であることを特徴とする請求項5に記載のデータ処理装置。
【請求項11】 前記第1、第2及び第3の次テーブルアドレス導出手段は、一のテーブルの直前のテーブルのアドレス値と前記一のテーブルの中の次テーブルキューの値との排他的論理和により前記一のテーブルの次のテーブルのアドレスを導出することを特徴とする請求項10に記載のデータ処理装置。
発明の詳細な説明
【0001】
【産業上の利用分野】本発明は、データを持つテーブルが連鎖されてなる連鎖リストに対して、テーブルの動的な追加、削除及び検索を行なうデータ処理方法及びその装置に関する。
【0002】
【従来の技術】従来より、データ処理システムにおいてテーブル処理は多く用いられ、各々のテーブルの構成は固定されているが、テーブルの個数を動的に変動させる場合に連鎖リストを構成することにより、テーブルのエンキュー、デキュー及び検索の処理を効率よく行なう方法が広く採用されている。
【0003】連鎖リストには、キューヘッダを始点として片方向の検索を可能とする片方向リストと、2本のキューヘッダから双方向の検索を可能とする双方向リストとがある。
【0004】
【発明が解決しようとする課題】しかしながら、前記のような従来のデータ処理方法においては、双方向の検索を可能とするために、テーブル連鎖のための次テーブルキュー領域が各テーブル毎に2アドレス長必要であり、テーブル領域のサイズが大きくなるという問題点がある。
【0005】本発明は、前記に鑑みなされたものであって、記憶手段におけるテーブル領域のサイズを縮小することができるデータ処理方法及びその装置を提供することを目的とする。
【0006】
【課題を解決するための手段】前記の目的を達成するため、本発明は、各々のテーブルの中の次テーブルキューに、当該テーブルの前後のテーブルのアドレス値同士の排他的論理和により算出される値を格納することにより双方向リストを構成することによって、次テーブルキュー領域を縮小するものである。
【0007】具体的に請求項1の発明が講じた解決手段は、記憶手段に格納される、データを持つテーブルが連鎖されてなる連鎖リストに対して、テーブルの動的な追加、削除及び検索を行なうデータ処理方法を対象とし、各々のテーブルがテーブル毎の次テーブルキューにより双方向に連鎖される連鎖リストに対して、テーブル追加を行なうエンキュー処理と、テーブル削除を行なうデキュー処理と、テーブル検索を行なう検索処理とを備え、各々のテーブルの中の次テーブルキューには、当該テーブルの前後のテーブルのアドレス値同士の排他的論理和により算出される値を設定する構成とするものである。
【0008】請求項2の発明は、具体的には、請求項1の発明の構成に、前記エンキュー処理は、(1) 順方向又は逆方向のキューヘッダから連鎖リストの先頭テーブルのアドレスを求め該先頭テーブルのアドレスを現在のアドレスとして設定するステップと、(2) 現在のアドレスにより示されるテーブルである現在のテーブルの中のデータの内容を調べるステップと、(3) 現在のテーブルが追加位置のテーブルであるか否かを調べるステップと、(4) 現在のテーブルが追加位置のテーブルでない場合に、現在のテーブルの直前のテーブルのアドレス値と現在のテーブル中の次テーブルキューの値との排他的論理和により現在のテーブルの次のテーブルのアドレスを導出し該次のテーブルのアドレスを新たに現在のアドレスとして設定し、ステップ(2)に戻るステップと、(5) 現在のテーブルが追加位置のテーブルである場合に、追加テーブルを加えて連鎖リストを再構成するステップとを有している構成を付加するものである。
【0009】請求項3の発明は、具体的には、請求項1の発明の構成に、前記デキュー処理は、(1) 順方向又は逆方向のキューヘッダから連鎖リストの先頭テーブルのアドレスを求め該先頭テーブルのアドレスを現在のアドレスとして設定するステップと、(2) 現在のアドレスにより示されるテーブルである現在のテーブルの中のデータの内容を調べるステップと、(3) 現在のテーブルが削除位置のテーブルであるか否かを調べるステップと、(4) 現在のテーブルが削除位置のテーブルでない場合に、現在のテーブルの直前のテーブルのアドレス値と現在のテーブル中の次テーブルキューの値との排他的論理和により現在のテーブルの次のテーブルのアドレスを導出し該次のテーブルのアドレスを新たに現在のアドレスとして設定し、ステップ(2)に戻るステップと、(5) 現在のテーブルが削除位置のテーブルである場合に、削除テーブルを除いて連鎖リストを再構成するステップとを有している構成を付加するものである。
【0010】請求項4の発明は、具体的には、請求項1の発明の構成に、前記検索処理は、(1) 順方向又は逆方向のキューヘッダから連鎖リストの先頭テーブルのアドレスを求め該先頭テーブルのアドレスを現在のアドレスとして設定するステップと、(2) 現在のアドレスにより示されるテーブルである現在のテーブルの中のデータの内容を調べるステップと、(3) 現在のテーブルが検索目的に一致するテーブルであるか否かを調べるステップと、(4) 現在のテーブルが検索目的に一致するテーブルでない場合に、現在のテーブルの直前のテーブルのアドレス値と現在のテーブル中の次テーブルキューの値との排他的論理和により現在のテーブルの次のテーブルのアドレスを導出し該次のテーブルのアドレスを新たに現在のアドレスとして設定し、ステップ(2)に戻るステップと、(5) 現在のテーブルが検索目的に一致するテーブルである場合に、目的のテーブルに対して処理を行なうステップとを有している構成を付加するものである。
【0011】また、具体的に請求項5の発明が講じた解決手段は、データを持つテーブルが連鎖されてなる連鎖リストに対してテーブルの動的な追加、削除及び検索を行なうデータ処理装置を対象とし、各々のテーブルがテーブル毎の次テーブルキューにより双方向に連鎖される連鎖リストを格納する記憶手段と、該記憶手段に格納される連鎖リストに対して、テーブル追加を行なうエンキュー手段と、テーブル削除を行なうデキュー手段と、テーブル検索を行なう検索手段とを備え、各々のテーブルの中の次テーブルキューは、当該テーブルの前後のテーブルのアドレス値同士の排他的論理和により算出される値を有している構成とするものである。
【0012】請求項6は、具体的には、請求項5の発明の構成に、前記エンキュー手段は、順方向又は逆方向のキューヘッダから連鎖リストの先頭テーブルのアドレスを発生させる先頭テーブルアドレス発生手段と、追加位置のテーブルを見つけるために一のテーブルの次のテーブルのアドレスを導出する次テーブルアドレス導出手段とを有している構成を付加するものである。
【0013】請求項7は、具体的には、請求項5の発明の構成に、前記デキュー手段は、順方向又は逆方向のキューヘッダから連鎖リストの先頭テーブルのアドレスを発生させる先頭テーブルアドレス発生手段と、削除位置のテーブルを見つけるために一のテーブルの次のテーブルのアドレスを導出する次テーブルアドレス導出手段とを有している構成を付加するものである。
【0014】請求項8は、具体的には、請求項5の発明の構成に、前記検索手段は、順方向又は逆方向のキューヘッダから連鎖リストの先頭テーブルのアドレスを発生させる先頭テーブルアドレス発生手段と、検索位置のテーブルを見つけるために一のテーブルの次のテーブルのアドレスを導出する次テーブルアドレス導出手段とを有している構成を付加するものである。
【0015】請求項9は、具体的には、請求項6、請求項7又は請求項8の発明の構成に、前記次テーブルアドレス導出手段は、一のテーブルの直前のテーブルのアドレス値と前記一のテーブルの中の次テーブルキューの値との排他的論理和により前記一のテーブルの次のテーブルのアドレスを導出する構成を付加するものである。
【0016】請求項10は、具体的には、請求項5の発明の構成に、前記エンキュー手段は、順方向又は逆方向のキューヘッダから連鎖リストの先頭テーブルのアドレスを発生させる第1の先頭テーブルアドレス発生手段と、追加位置のテーブルを見つけるために一のテーブルの次のテーブルのアドレスを導出する第1の次テーブルアドレス導出手段とを有し、前記デキュー手段は、順方向又は逆方向のキューヘッダから連鎖リストの先頭テーブルのアドレスを発生させる第2の先頭テーブルアドレス発生手段と、削除位置のテーブルを見つけるために一のテーブルの次のテーブルのアドレスを導出する第2の次テーブルアドレス導出手段とを有し、前記検索手段は、順方向又は逆方向のキューヘッダから連鎖リストの先頭テーブルのアドレスを発生させる第3の先頭テーブルアドレス発生手段と、検索位置のテーブルを見つけるために一のテーブルの次のテーブルのアドレスを導出する第3の次テーブルアドレス導出手段とを有しており、前記第1、第2及び第3の先頭テーブルアドレス発生手段同士は一体であると共に、前記第1、第2及び第3の次テーブルアドレス導出手段同士は一体である構成を付加するものである。
【0017】請求項11は、具体的には、請求項10の発明の構成に、前記第1、第2及び第3の次テーブルアドレス導出手段は、一のテーブルの直前のテーブルのアドレス値と前記一のテーブルの中の次テーブルキューの値との排他的論理和により前記一のテーブルの次のテーブルのアドレスを導出する構成を付加するものである。
【0018】
【作用】請求項1の発明の構成により、データ処理方法において、各々のテーブルの中の次テーブルキューには、当該テーブルの前後のテーブルのアドレス値同士の排他的論理和により算出される値を設定する。これにより、例えば、順方向にテーブルを辿る場合には、一のテーブルの直前のテーブルのアドレス値と前記一のテーブル中の次テーブルキューの値との排他的論理和を求めることによって、前記一のテーブルの次のテーブルのアドレスを導出することができる。同様にして、逆方向にテーブルを辿る場合にも、次のテーブルのアドレスを導出することができる。したがって、テーブルの動的な追加、削除及び検索を、順方向及び逆方向の何れの方向にも行なうことができる。
【0019】ここで、次テーブルキューに設定される値は、2つのアドレス値同士の排他的論理和の演算結果であるため、記憶手段における次テーブルキュー領域は1アドレス長となる。
【0020】請求項2の発明の構成により、追加位置のテーブルが見つかるまで、前述したような「次のテーブルのアドレスの導出」を繰り返し行なうことによって、連鎖リストにおけるテーブルのエンキュー処理を実現することができる。
【0021】請求項3の発明の構成により、削除位置のテーブルが見つかるまで、前述したような「次のテーブルのアドレスの導出」を繰り返し行なうことによって、連鎖リストにおけるテーブルのデキュー処理を実現することができる。
【0022】請求項4の発明の構成により、検査目的に一致するテーブルが見つかるまで、前述したような「次のテーブルのアドレスの導出」を繰り返し行なうことによって、連鎖リストにおけるテーブルの検索処理を実現することができる。
【0023】また、請求項5の発明の構成により、データ処理装置において、記憶手段に格納される連鎖リストの各々のテーブルの中の次テーブルキューは、当該テーブルの前後のテーブルのアドレス値同士の排他的論理和により算出される値を有している。これにより、例えば、順方向にテーブルを辿る場合には、一のテーブルの直前のテーブルのアドレス値と前記一のテーブル中の次テーブルキューの値との排他的論理和を求めることによって、前記一のテーブルの次のテーブルのアドレスを導出することができる。同様にして、逆方向にテーブルを辿る場合にも、次のテーブルのアドレスを導出することができる。したがって、テーブルの動的な追加、削除及び検索を、順方向及び逆方向の何れの方向にも行なうことができる。
【0024】ここで、次テーブルキューが有する値は、2つのアドレス値同士の排他的論理和の演算結果であるため、記憶手段における次テーブルキュー領域は1アドレス長となる。
【0025】請求項6の発明の構成により、次テーブルアドレス導出手段が、追加位置のテーブルが見つかるまで、次のテーブルのアドレスの導出動作を繰り返し実行することによって、エンキュー手段は、連鎖リストにおけるテーブルのエンキュー処理を実現することができる。
【0026】請求項7の発明の構成により、次テーブルアドレス導出手段が、削除位置のテーブルが見つかるまで、次のテーブルのアドレスの導出動作を繰り返し実行することによって、デキュー手段は、連鎖リストにおけるテーブルのデキュー処理を実現することができる。
【0027】請求項8の発明の構成により、次テーブルアドレス導出手段が、検査位置のテーブルが見つかるまで、次のテーブルのアドレスの導出動作を繰り返し実行することによって、検索手段は、連鎖リストにおけるテーブルの検索処理を実現することができる。
【0028】請求項10の発明の構成により、エンキュー手段、デキュー手段及び検索手段における先頭テーブルアドレス発生手段同士を一体化すると共に、次テーブルアドレス導出手段同士を一体化することによってデータ処理装置の小型化を図ることが可能である。
【0029】請求項9、11の発明の構成により、一のテーブルの次のテーブルのアドレスの導出を、前記一のテーブルの直前のテーブルのアドレス値と前記一のテーブル中の次テーブルキューの値との排他的論理和を求めることにより実現することができる。
【0030】
【実施例】以下、本発明の一実施例について図面を参照しながら説明する。
【0031】図1は本発明の一実施例に係るデータ処理装置の構成を示す図である。本実施例のデータ処理装置は、データを持つテーブルが連鎖されてなる連鎖リストに対して、テーブルの動的な追加、削除及び検索を行なうものであり、例えばオペレーションズシステムのタスク管理システム等をに適用できるものである。
【0032】図1において、本発明のデータ処理装置は、キュー記憶領域11を有する記憶部1と、エンキュー処理、デキュー処理及び検索処理を行なう処理部2と、エンキュー処理、デキュー処理及び検索処理を選択的に実行させるための命令としてのエンキュー要求、デキュー要求及び検索要求を受け付ける入出力部3とを備えている。記憶部1のキュー記憶領域11内には、各々のテーブルがテーブル毎の双方向次テーブルキューにより双方向に連鎖される連鎖リストが格納されており、さらにエンキュー処理において追加される追加テーブルも格納されている。
【0033】また、処理部2は、連鎖リストに対して、テーブル追加を行なうエンキュー手段21と、テーブル削除を行なうデキュー手段22と、テーブル検索を行なう検索手段23と、制御手段24とを有している。制御手段24は、入出力部3から、エンキュー要求、デキュー要求及び検索要求にそれぞれ対応するエンキュー要求信号、デキュー要求信号及び検索要求信号のうち、例えば、エンキュー要求信号を受け取ると、エンキュー手段21にエンキュー処理を行なわせる。同様に、制御手段24は、デキュー要求信号を受け取ると、デキュー手段22にデキュー処理を行なわせ、検索要求信号を受け取ると、検索手段23に検索処理を行なわせる。
【0034】エンキュー手段21は、順方向又は逆方向のキューヘッダから連鎖リストの先頭テーブルのアドレスを発生させる先頭テーブルアドレス発生手段21aと、次テーブルアドレス導出手段としての排他的論理和演算手段21bとを有している。排他的論理和演算手段21bは、連鎖リストのテーブルの中から追加位置のテーブルを見つけるために、一のテーブルの直前のテーブルのアドレス値と前記一のテーブルの中の双方向次テーブルキューの値との排他的論理和を演算し、前記一のテーブルの次のテーブルのアドレスを導出する。さらに、排他的論理和演算手段21bは、追加テーブルを加えて連鎖リストを再構成する際に、追加テーブルとこの追加テーブルの前後のテーブルとの合わせて3つのテーブルの中の双方向次テーブルキューにそれぞれ設定される値を与える。各々のテーブルの中の双方向次テーブルキューには、当該テーブルの新たな前後のテーブルのアドレス値同士の排他的論理和により算出される値が設定される。
【0035】デキュー手段22は、順方向又は逆方向のキューヘッダから連鎖リストの先頭テーブルのアドレスを発生させる先頭テーブルアドレス発生手段22aと、次テーブルアドレス導出手段としての排他的論理和演算手段22bとを有している。排他的論理和演算手段22bは、連鎖リストのテーブルの中から削除位置のテーブルを見つけるために、一のテーブルの直前のテーブルのアドレス値と前記一のテーブルの中の双方向次テーブルキューの値との排他的論理和を演算し、前記一のテーブルの次のテーブルのアドレスを導出する。さらに、排他的論理和演算手段22bは、削除テーブルを除いて連鎖リストを再構成する際に、削除テーブルの前後の2つのテーブルの中の双方向次テーブルキューにそれぞれ設定される値を与える。各々のテーブルの中の双方向次テーブルキューには、当該テーブルの新たな前後のテーブルのアドレス値同士の排他的論理和により算出される値が設定される。
【0036】検索手段23は、順方向又は逆方向のキューヘッダから連鎖リストの先頭テーブルのアドレスを発生させる先頭テーブルアドレス発生手段23aと、次テーブルアドレス導出手段としての排他的論理和演算手段23bとを有している。排他的論理和演算手段23bは、連鎖リストのテーブルの中から検索位置のテーブルを見つけるために、一のテーブルの直前のテーブルのアドレス値と前記一のテーブルの中の双方向次テーブルキューの値との排他的論理和を演算し、前記一のテーブルの次のテーブルのアドレスを導出する。
【0037】図2は以上のように構成されたデータ処理装置の記憶部1のキュー記憶領域11に格納される連鎖リストの一例を示す図である。図2において、4は順方向キューヘッダであり、順方向での先頭のテーブルのアドレスを格納する。テーブルA、B、Cは、それぞれ、前後のテーブルのアドレス値同士の排他的論理和の演算結果を格納する双方向次テーブルキュー6a、6b、6cと、データを格納するデータ領域7a、7b、7cとを有している。5は逆方向キューヘッダであり、逆方向での先頭のテーブルのアドレスを格納する。各テーブルは動的にエンキュー及びデキューが繰り返されるため、そのアドレスや個数は固定ではないが、ここでは、テーブル数を3個とし、テーブルA、B、Cのアドレスを、それぞれ、16進数の“A000”、“B000”、“C000”と仮定している。各テーブルの双方向次テーブルキューは、前後に位置する2つのテーブルのアドレス値同士の排他的論理和の演算結果を保持するが、テーブルがキューの終端に位置する場合には次のテーブルのアドレスの値を“0”として排他的論理和を演算する。
【0038】ここで、具体的な計算により、前記例示したテーブルのアドレス値を用いて、各テーブルが双方向の連鎖リストを構成することを示す。まず、順方向キューヘッダ4は順方向の先頭テーブルのアドレスを格納するから16進数“A000”を格納し、逆方向キューヘッダ5は逆方向の先頭テーブルのアドレスを格納するから16進数“C000”を格納する。テーブルA、B、Cの双方向次テーブルキュー6a、6b、6cは、それぞれ、前後のテーブルのアドレス値同士の排他的論理和の演算結果を格納する。ただし、テーブルがキューの終端に位置する場合には、次のテーブルのアドレスの値を“0”として排他的論理和を演算しその演算結果を格納する。したがって、テーブルA、B、Cの双方向次テーブルキュー6a、6b、6cには、それぞれ、下記の計算式により、16進数“B000”、“6000”、“B000”が格納される。
【0039】テーブルAの双方向次テーブルキュー= 0^(テーブルBのアドレス値)
= 0^B000= B000テーブルBの双方向次テーブルキュー=(テーブルAのアドレス値)^(テーブルCのアドレス値)
= A000^C000= 6000テーブルCの双方向次テーブルキュー=(テーブルBのアドレス値)^0= B000^0= B000ここで、「^」の記号は、排他的論理和の演算を表す。
【0040】この状態で、順方向キューヘッダ4から連鎖リストを順方向に辿る場合には、テーブルAのアドレス=(順方向キューヘッダの内容)
= A000テーブルBのアドレス= 0^(テーブルAの双方向次テーブルキューの内容)
= 0^B000= B000テーブルCのアドレス=(テーブルAのアドレス値)^(テーブルBの双方向次テーブルキューの内容)
= A000^6000= C000のようにして、次々と次のテーブルのアドレスを求めることができる。
【0041】また、この状態で、逆方向キューヘッダから連鎖リストを逆方向に辿る場合は、テーブルCのアドレス=(逆方向キューヘッダの内容)
= C000テーブルBのアドレス= 0^(テーブルCの双方向次テーブルキューの内容)
= 0^B000= B000テーブルAのアドレス=(テーブルCのアドレス値)^(テーブルBの双方向次テーブルキューの内容)
= C000^6000= A000のようにして、次々と次のテーブルのアドレスを求めることができる。
【0042】以上、具体的に示した計算はテーブルの個数がいくつの場合でも同様に行なうことができることは容易に理解できよう。
【0043】次に、本実施例のデータ処理装置のエンキュー手段21によるエンキュー処理動作について図面を用いて説明する。ここでは、図3(a)に示す、テーブルA、B、Cで構成される連鎖リストに、例えば図3(b)に示すテーブルDを追加する場合について説明を行なう。なお、図3(a)〜(c)において、4は順方向キューヘッダ、5は逆方向キューヘッダ、6a〜6dはそれぞれテーブルA〜Dの双方向次テーブルキュー、7a〜7dはそれぞれテーブルA〜Dのデータ領域を示す。
【0044】図4(a)はエンキュー処理の流れを示す図であり、図4(a)に示すように、まず、順方向キューヘッダ4から連鎖リストの先頭テーブルすなわちテーブルAのアドレスを求める(ステップS11)。次に、テーブル中のデータの内容(例えば、タスクの優先度)を調べ(ステップS12)、目的の位置にあるテーブルであるか否かを調べる(ステップ13)。目的のテーブルであった場合には、追加テーブルDを含めて、テーブル連鎖を再設定する(ステップS15)。一方、目的のテーブルでなかった場合には、ステップS14に移り、図4(b)に示すように、前のテーブルアドレスとテーブル中の双方向次テーブルキューの内容との排他的論理和により次のテーブルのアドレスを求め(ステップS16)、ステップS12に戻り、目的のテーブルが見つかるまでステップS12〜S14を繰り返す。なお、図3(c)は、一例として、テーブルAとテーブルBとの間にテーブルDを追加した場合におけるエンキュー処理終了後の新たな連鎖リストを示している。また、ステップS11において、逆方向キューヘッダ5から連鎖リストの先頭テーブルを求め、ステップS12〜S15と同様の処理を行なうことによって、連鎖リストを逆方向に辿りながらテーブルを追加することも可能である。
【0045】次に、本実施例のデータ処理装置のデキュー手段22によるデキュー処理動作について図面を用いて説明する。ここでは、図5(a)に示す、テーブルA、B、Cで構成される連鎖リストから、例えばテーブルBを削除する場合について説明を行なう。なお、図5(a)、(b)において、4は順方向キューヘッダ、5は逆方向キューヘッダ、6a〜6cはそれぞれテーブルA〜Cの双方向次テーブルキュー、7a〜7cはそれぞれテーブルA〜Cのデータ領域を示す。
【0046】図6(a)はデキュー処理の流れを示す図であり、図6(a)に示すように、まず、順方向キューヘッダ4から連鎖リストの先頭テーブルすなわちテーブルAのアドレスを求める(ステップS21)。次に、テーブル中のデータの内容(例えば、タスクID)を調べ(ステップS22)、目的の位置にあるテーブル、この場合テーブルBであるか否かを調べる(ステップS23)。目的のテーブルであった場合には、削除テーブルを除いて、テーブル連鎖を再設定する(ステップS25)。一方、目的のテーブルでなかった場合には、ステップS24に移り、図6(b)に示すように、前のテーブルアドレスとテーブル中の双方向次テーブルキューの内容との排他的論理和により次のテーブルのアドレスを求め(ステップS26)、ステップS22に戻り、目的のテーブルが見つかるまでステップS22〜S24を繰り返す。なお、図5(b)は、デキュー処理終了後の新たな連鎖リストを示している。また、ステップS21において、逆方向キューヘッダ5から連鎖リストの先頭テーブルを求め、ステップS22〜S25と同様の処理を行なうことによって、連鎖リストを逆方向に辿りながらテーブルを削除することも可能である。
【0047】次に、本実施例のデータ処理装置の検索手段23による検索処理動作について図面を用いて説明する。ここでは、図2に示す、テーブルA、B、Cで構成される連鎖リストを検索する場合について説明を行なう。
【0048】図7(a)は検索処理の流れを示す図であり、図7(a)に示すように、まず、順方向キューヘッダ4から連鎖リストの先頭テーブルすなわちテーブルAのアドレスを求める(ステップS31)。次に、テーブル中のデータの内容を調べ(ステップS32)、目的のテーブルであるか否か(例えば、テーブルの内容が条件式を満たすか否か)を調べる(ステップS33)。目的のテーブルであった場合には、そのテーブルに対して、処理を行なう(ステップS35)。一方、目的のテーブルでなかった場合には、ステップS34に移り、図7(b)に示すように、前のテーブルアドレスとテーブル中の双方向次テーブルキューの内容との排他的論理和により次のテーブルのアドレスを求め(ステップS36)、ステップS32に戻り、目的のテーブルが見つかるまでステップS32〜S34を繰り返す。なお、ステップS31において、逆方向キューヘッダ5から連鎖リストの先頭テーブルを求め、ステップS32〜S35と同様の処理を行なうことによって、連鎖リストを逆方向に辿りながらテーブルを検索することも可能である。
【0049】本実施例によると、以上のような一連の処理を行なうことによって双方向リストを構成することができる。このとき、記憶手段に占めるテーブル領域のサイズを縮小することができるので、様々なリスト処理の応用分野においてデータ量の低減を実現する効果がある。
【0050】なお、本実施例では、先頭テーブルアドレス発生手段及び排他的論理和演算手段は、エンキュー処理、デキュー処理及び検索処理の各処理毎に設けているが、先頭テーブルアドレス発生手段21a、22a及び23aを一体にして共用し、排他的論理和演算手段21b、22b及び23bを一体にして共用することによって、データ処理装置の小型化を図ることができる。
【0051】また、本実施例では、単純な構成を持つテーブル及び連鎖リストを例に示したが、より複雑な構成を持つテーブル及び連鎖リストに対しても同様に適用可能である。
【0052】
【発明の効果】以上説明したように、請求項1の発明に係るデータ処理方法によると、各々のテーブルの中の次テーブルキューに、当該テーブルの前後のテーブルのアドレス値同士の排他的論理和により算出される値を設定することによって、双方向リストを構成することが可能である。ここで、次テーブルキューに設定される値は、2つのアドレス値同士の排他的論理和の演算結果であるため、記憶手段における次テーブルキュー領域は1アドレス長となり、従来に比較して領域のサイズを半減化することができる。
【0053】請求項2〜4の発明に係るデータ処理方法によると、一のテーブルの直前のテーブルのアドレス値と前記一のテーブル中の次テーブルキューの値との排他的論理和により前記一のテーブルの次のテーブルのアドレスを導出することによって、テーブルの動的な追加、削除及び検索を実現することができる。
【0054】また、請求項5の発明に係るデータ処理装置によると、記憶手段に格納される連鎖リストの各々のテーブルの中の次テーブルキューが、当該テーブルの前後のテーブルのアドレス値同士の排他的論理和により算出される値を有することによって、双方向リストを構成することが可能である。ここで、次テーブルキューに設定される値は、2つのアドレス値同士の排他的論理和の演算結果であるため、記憶手段における次テーブルキュー領域は1アドレス長となり、従来に比較して領域のサイズを半減化することができる。
【0055】請求項6〜8の発明に係るデータ処理装置によると、次のテーブルのアドレスの導出を繰り返し実行することによって、テーブルの動的な追加、削除及び検索を実現することができる。
【0056】請求項10の発明に係るデータ処理装置によると、テーブルの追加、削除及び検索において先頭テーブルのアドレスを発生させる手段同士を一体化すると共に次のテーブルのアドレスを導出する手段同士を一体化することによって、データ処理装置の小型化を図ることが可能である。
【0057】請求項9、11の発明に係るデータ処理装置によると、一のテーブルの次のテーブルのアドレスの導出を、前記一のテーブルの直前のテーブルのアドレス値と前記一のテーブルの中の次テーブルキューの値との排他的論理和を求めることにより実現することができる。
【0058】以上のように、本発明によると、記憶手段におけるテーブル領域のサイズを縮小することができ、双方向リストが記憶手段に占める領域のサイズを縮小することが可能であり、その効果は大きい。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013