(57)【特許請求の範囲】
【請求項１】
データ要素の記憶を管理する方法において、
第１の端および第２の端を有する記憶域をデータ要素の記憶用に提供するステップと、
前記記憶域中の第１のスタックに第１のデータ要素セットを記憶するステップであって、前記第１のスタックが、前記記憶域の前記第１の端に向いた第１の端および前記記憶域の前記第２の端に向いた第２の端を有するステップと、
前記記憶域中の第２のスタックに第２のデータ要素セットを記憶するステップであって、単一のスタックとして機能し且つ分割されている前記第２のスタックが、前記第１のスタックの前記第１の端と前記記憶域の前記第１の端との間に位置するデータ要素を少なくとも１つと、前記第１のスタックの前記第２の端と前記記憶域の前記第２の端との間に位置するデータ要素を少なくとも１つ含むステップとを含み、
前記データ要素の連続した１つ１つが前記第２のスタックに記憶されるのに応答して、前記第２のスタックのサイズが、前記記憶域の前記第１の端と前記記憶域の前記第２の端の両方に向かって大きくなる、方法。
【請求項２】
前記第２のスタックのサイズが前記記憶域の前記第１の端および前記第２の端に向かって大きくなることが、前記第１のスタックから離れる方向にサイズが大きくなることを含む、請求項１に記載の方法。
【請求項３】
前記第２のスタックのサイズが前記記憶域の前記第１の端および前記第２の端に向かって大きくなることが、前記第１のスタックに向かってサイズが大きくなることを含む、請求項１に記載の方法。
【請求項４】
前記記憶域が、相互に排他的な４つのセクション、すなわち、ｉ）セクションのうちの端部セクションである第１のセクションであって、前記記憶域の端のうちの一方に近接する端を有する第１のセクションと、ｉｉ）セクションのうちのもう１つの端部セクションである第２のセクションであって、前記記憶域の端のうちの第２の端に近接する端を有する第２のセクションと、ｉｉｉ）セクションのうちの中間セクションである第３および第４のセクションであって、前記第１のセクションと前記第２のセクションの間に位置する第３および第４のセクションとを有し、
前記第１のスタックが前記セクションのうちの前記中間セクションに限定され、前記第２のスタックが前記セクションのうちの前記端部セクションに限定される、請求項１ないし請求項３の何れか１項に記載の方法。
【請求項５】
データ要素の記憶を管理する方法において、
第１の端および第２の端を有する記憶域をデータ要素の記憶用に提供するステップと、
前記記憶域中の第１のスタックに第１のデータ要素セットを記憶するステップであって、前記第１のスタックが、前記記憶域の前記第１の端に向いた第１の端および前記記憶域の前記第２の端に向いた第２の端を有するステップと、
前記記憶域中の第２のスタックに第２のデータ要素セットを記憶するステップであって、単一のスタックとして機能し且つ分割されている前記第２のスタックが、前記第１のスタックの前記第１の端と前記記憶域の前記第１の端との間に位置するデータ要素を少なくとも１つと、前記第１のスタックの前記第２の端と前記記憶域の前記第２の端との間に位置するデータ要素を少なくとも１つ含むステップと、
前記記憶域中の第３のスタックに第３のデータ要素セットを記憶するステップであって、単一のスタックとして機能し且つ分割されている前記第３のスタックが、前記第１のスタックの前記第１の端と前記記憶域の前記第１の端との間に位置するデータ要素を少なくとも１つと、前記第１のスタックの前記第２の端と前記記憶域の前記第２の端との間に位置するデータ要素を少なくとも１つ含むステップとを含み、
前記データ要素の連続した１つ１つが前記第３のスタックに記憶されるのに応答して、前記第３のスタックのサイズが、前記記憶域の前記第１の端と前記記憶域の前記第２の端の両方に向かって大きくなる、方法。
【請求項６】
前記第３のスタックのサイズが前記記憶域の前記第１の端および前記第２の端に向かって大きくなることが、前記第１のスタックに向かってサイズが大きくなることを含む、請求項５に記載の方法。
【請求項７】
前記第３のスタックのサイズが前記記憶域の前記第１の端および前記第２の端に向かって大きくなることが、前記第１のスタックから離れる方向にサイズが大きくなることを含む、請求項５に記載の方法。
【請求項８】
前記記憶域が、相互に排他的な４つのセクション、すなわち、ｉ）セクションのうちの端部セクションである第１のセクションであって、前記記憶域の端のうちの一方に近接する端を有する第１のセクションと、ｉｉ）セクションのうちのもう１つの端部セクションである第２のセクションであって、前記記憶域の端のうちの第２の端に近接する端を有する第２のセクションと、ｉｉｉ）セクションのうちの中間セクションである第３および第４のセクションであって、前記第１のセクションと前記第２のセクションの間に位置する第３および第４のセクションとを有し、
前記第１のスタックが前記セクションのうちの前記中間セクションに限定され、前記第２のスタックが前記セクションのうちの前記端部セクションに限定され、前記第３のスタックが前記セクションのうちの前記中間セクションに限定される、請求項５ないし請求項７の何れか１項に記載の方法。
【請求項９】
データ要素の記憶を管理するためのシステムであって、
第１の端および第２の端を有する記憶域をデータ要素の記憶用に規定する手段と、
前記記憶域中に第１のスタックを規定する手段であって、前記第１のスタックが、前記記憶域の前記第１の端に向いた第１の端および前記記憶域の前記第２の端に向いた第２の端を有する手段と、
前記記憶域中に第２のスタックを規定する手段であって、単一のスタックとして機能し且つ分割されている前記第２のスタックが、前記第１のスタックの前記第１の端と前記記憶域の前記第１の端との間に位置するデータ要素を少なくとも１つと、前記第１のスタックの前記第２の端と前記記憶域の前記第２の端との間に位置するデータ要素を少なくとも１つ含む手段とを備え、
前記データ要素の連続した１つ１つが前記第２のスタックに記憶されるのに応答して、前記第２のスタックのサイズが、前記記憶域の前記第１の端と前記記憶域の前記第２の端の両方に向かって大きくなる、システム。
【請求項１０】
前記第２のスタックのサイズが前記記憶域の前記第１の端および前記第２の端に向かって大きくなることが、前記第１のスタックから離れる方向にサイズが大きくなることを含む、請求項９に記載のシステム。
【請求項１１】
前記第２のスタックのサイズが前記記憶域の前記第１の端および前記第２の端に向かって大きくなることが、前記第１のスタックに向かってサイズが大きくなることを含む、請求項９に記載のシステム。
【請求項１２】
前記記憶域が、相互に排他的な４つのセクション、すなわち、ｉ）セクションのうちの端部セクションである第１のセクションであって、前記記憶域の端のうちの一方に近接する端を有する第１のセクションと、ｉｉ）セクションのうちのもう１つの端部セクションである第２のセクションであって、前記記憶域の端のうちの第２の端に近接する端を有する第２のセクションと、ｉｉｉ）セクションのうちの中間セクションである第３および第４のセクションであって、前記第１のセクションと前記第２のセクションの間に位置する第３および第４のセクションとを有し、
前記記憶域中に前記第１のスタックを規定する前記手段が、前記第１のスタックを前記セクションのうちの前記中間セクションに限定する手段を含み、前記記憶域中に前記第２のスタックを規定する前記手段が、前記第２のスタックを前記セクションのうちの前記端部セクションに限定する手段を含む、請求項９ないし請求項１１の何れか１項に記載のシステム。
【請求項１３】
データ要素の記憶を管理するためのシステムであって、
第１の端および第２の端を有する記憶域をデータ要素の記憶用に規定する手段と、
前記記憶域中に第１のスタックを規定する手段であって、前記第１のスタックが、前記記憶域の前記第１の端に向いた第１の端および前記記憶域の前記第２の端に向いた第２の端を有する手段と、
前記記憶域中に第２のスタックを規定する手段であって、単一のスタックとして機能し且つ分割されている前記第２のスタックが、前記第１のスタックの前記第１の端と前記記憶域の前記第１の端との間に位置するデータ要素を少なくとも１つと、前記第１のスタックの前記第２の端と前記記憶域の前記第２の端との間に位置するデータ要素を少なくとも１つ含む手段と、
前記記憶域中に第３のスタックを規定する手段であって、単一のスタックとして機能し且つ分割されている前記第３のスタックが、前記第１のスタックの前記第１の端と前記記憶域の前記第１の端との間に位置するデータ要素を少なくとも１つと、前記第１のスタックの前記第２の端と前記記憶域の前記第２の端との間に位置するデータ要素を少なくとも１つ含む手段とを備え、前記データ要素の連続した１つ１つが前記第３のスタックに記憶されるのに応答して、前記第３のスタックのサイズが、前記記憶域の前記第１の端と前記記憶域の前記第２の端の両方に向かって大きくなる、システム。
【請求項１４】
前記第３のスタックのサイズが前記記憶域の前記第１の端および前記第２の端に向かって大きくなることが、前記第１のスタックに向かってサイズが大きくなることを含む、請求項１３に記載のシステム。
【請求項１５】
前記第３のスタックのサイズが前記記憶域の前記第１の端および前記第２の端に向かって大きくなることが、前記第１のスタックから離れる方向にサイズが大きくなることを含む、請求項１３に記載のシステム。
【請求項１６】
前記記憶域が、相互に排他的な４つのセクション、すなわち、ｉ）セクションのうちの端部セクションである第１のセクションであって、前記記憶域の端のうちの一方に近接する端を有する第１のセクションと、ｉｉ）セクションのうちのもう１つの端部セクションである第２のセクションであって、前記記憶域の端のうちの第２の端に近接する端を有する第２のセクションと、ｉｉｉ）セクションのうちの中間セクションである第３および第４のセクションであって、前記第１のセクションと前記第２のセクションの間に位置する第３および第４のセクションとを有し、
前記記憶域中に前記第１のスタックを規定する前記手段が、前記第１のスタックを前記セクションのうちの前記中間セクションに限定する手段を含み、前記記憶域中に前記第２のスタックを規定する前記手段が、前記第２のスタックを前記セクションのうちの前記端部セクションに限定する手段を含み、前記記憶域中に前記第３のスタックを規定する前記手段が、前記第３のスタックを前記セクションのうちの前記中間セクションに限定する手段を含む、請求項１３ないし請求項１５の何れか１項に記載のシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は一般に、改良型のデータ処理システムに関し、より詳細には、メモリ配列内における改良型の先入れ後出しデータ構造に関する。
【０００２】
【従来の技術】
関連出願の相互参照
本出願は、本出願と同一の出願人に譲渡され同日に出願される、以下の出願に関するものであり、ここにこれらを参照により本明細書に組み込む。
整理番号ＡＵＳ９−２０００−０４３６−ＵＳ１
整理番号ＡＵＳ９−２０００−０４９１−ＵＳ１
【０００３】
スタックまたは先入れ後出し（ＦＩＬＯ）データ構造は、多くのコンピュータ・アプリケーションで用いられている。しばしば、単一のアプリケーション中に複数のスタックが必要であり、これらは必要に応じて追加される。というのは、アプリケーションの開始時点では、スタックがいくつ必要になるか分からないからである。コンピュータ・システム中のメモリは線形配列に構成されているので、アプリケーションは、複数のスタックを配置するのに使用することになる、この線形配列のいくつかのセグメントを有する。従来、スタックが実装される方式は、ベース・ポインタおよびヘッド・ポインタを用いる方式である。
【０００４】
通常の場合では、２つのスタックが、メモリ配列の向かい合う端に配置される。一方のスタックは右に増大し、他方のスタックは左に増大する。各スタックは増大して、ついには反対方向からくるスタックに当たる恐れがある（衝突と呼ばれる）。
【０００５】
２つのスタックが配列の向かい合う端から相互に増大する構成は、両方のスタックが同じレートで増大する場合には有効である。すなわち、メモリ配列中のすべてのメモリが、衝突の前に消費されることになる。しかし、第３のスタックが必要な場合には問題が生じる可能性がある。３つのスタックすべてが同じレートで増大し、第３のスタックが一方向にしか増大せず、この第３のスタックが最初の２つのスタックの真ん中に配置されている場合、第３のスタックは、他の２つのスタックの一方がその空間すべてを使い終わる前に、他の２つのスタックの他方と衝突する傾向がある。この問題を予期しようとして、第３のスタックを中央からずらした位置にすることもできるが、３つのスタックが同じレートで増大しない場合、選択した第３のスタックのオフセット位置は、助けとはならない可能性があり、問題を悪化させる可能性さえある。
【０００６】
【発明が解決しようとする課題】
関連出願のうちの一方では、１つまたは複数の両方向増大スタックによってこれらの問題に対処している。両方向増大スタックは、空間の割振りを含めた、線形メモリ配列中の空間の管理において生じる問題に対処するのに有用である。しかし、これらの問題の態様に別の形で関係する他の特徴であって、いくつかの状況ではより大きな適合性さえもたらすことのできる他の特徴を有する、メモリを管理するための方法および装置が必要とされている。
【０００７】
【課題を解決するための手段】
本発明は、データ要素の記憶を管理するための方法、システム、および装置におけるこうした必要性に対処するものである。第１の端および第２の端を有する記憶域が、データ要素記憶用に提供される。この記憶域中では、データ要素の第１のスタックが、記憶域の第１の端および第２の端にそれぞれ向いた第１の端および第２の端を有し、データ要素の第２のスタックが、第１のスタックの両端に近接して位置するデータ要素を有する。すなわち、第２のスタックは分割されており、第１のスタックは第２のスタックのデータ要素間に介在している。同様に、第３や第４のスタック等があってもよく、これらも複数の部分に分割される。データ要素の連続した１つ１つがそれぞれのスタックに記憶されるのに応答して、スタックのサイズは、記憶域の第１の端と記憶域の第２の端の両方に向かって大きくなる。さらに、分割されたスタックのうちの１つのサイズが大きくなることには、第１のスタックから離れる方向に大きくなること、あるいは、第１のスタックに向かって大きくなることを含めることができる。
【０００８】
別の態様では、記憶域は、相互に排他的な４つのセクションを有する。第１のセクション（セクションのうちの「端部」セクション）は、記憶域の一方の端に近接した端を有する。第２のセクション（セクションのうちのもう１つの「端部」セクション）は、記憶域の第２の端に近接した端を有する。第３のセクション（「中間」セクション）は、第１のセクションと第２のセクションの間に位置する。第４のセクション（もう１つの「中間」セクション）もまた、第１のセクションと第２のセクションの間に位置する。第１のスタックは、２つの中間セクションに限定され、第２のスタックは、２つの端部セクションに限定される。
【０００９】
別の態様では、分割された第３のスタックは、２つの中間セクションに限定される。
【００１０】
第２や第３のスタックなどのスタックが、記憶域の第１の端と第２の端の両方に向かって大きいサイズになる態様に関し、一実施形態では、第２のスタックが第１のスタックから離れる方向に大きくなり、第３のスタックが第１のスタックに向かって大きくなる。別法としては、第２のスタックが第１のスタックに向かって大きくなり、第３のスタックが第１のスタックから離れる方向に大きくなる。
【００１１】
関連出願のうちの一方に記述されているように、両方向増大スタックの利点の１つは、ある状況下およびある制限内では、奇数の両方向スタックにより、奇数の単一方向スタックによる場合よりも効率的に記憶域が使用されることである。本発明の利点の１つは、記憶域の中央部に位置する第１の両方向スタックを有し、２つの部分に分割された第２の両方向スタックを第１のスタックのどちら側にも１つずつ有することにより、ある状況下およびある制限内では記憶域中の空間がより効率的に使用されることである。
【００１２】
【発明の実施の形態】
本明細書では、用語「配列」は、離散的な記憶要素を有する、限られたサイズのメモリ記憶空間（メモリ記憶域とも呼ばれる）を指す。本質的に、配列の記憶要素は、相互に対しそれぞれの位置を有する。用語「線形配列」は、配列中の記憶要素の位置が線形方式で定義される記憶域を指す。すなわち、配列の要素は、単一のファイル・ライン中にスタックアップされると考えることができる。したがって、各要素は、「ライン」に沿ったその位置に従って一意に識別することができ、限られたサイズの線形配列は、ラインの第１の端と第２の端、例えば「右端」や「左端」を境界とすると言うことができる。したがって、線形配列の記憶要素は、別の記憶要素に対し、ラインに沿って「右端寄り」または「左端寄り」に位置すると言うことができる。より簡潔には、線形配列の、ある記憶要素は、線形配列の別の記憶要素の「右」または「左」にあると言うことができる。
【００１３】
配列に記憶されたデータ要素のセットはまた、配列内の個々の「スタック」、すなわち単一のファイル「ライン」中にスタックアップされたデータ要素のセットと言うことができ、そうした「スタック」として管理される。スタックには連続したデータ要素が追加されるので、スタックは、「増大する」と言うことができる。第１のスタック中にデータ要素の途切れがない場合、例えば第１のスタックのどのデータ要素の間にも第２のスタックのデータ要素が介在していない場合は、第１のスタックは、第１の端および第２の端のみを有すると言うことができる（スタックが途切れている場合は、そのスタックは２つよりも多くの端を有する可能性がある）。本明細書では、第１のスタックの「端に近接して」、または「端に」位置するデータ要素を有する第２のスタックについて言及する場合、第２のスタックのデータ要素のいずれかが第１のスタックの端に接していることを必ずしも意味するとは限らず、第２のスタックのデータ要素のいくつかが、第１のスタックの端とそれに対応する記憶域端部との間に位置する構成も含む。
【００１４】
ここで図１を参照すると、データ要素を記憶するための記憶域１１０が示されている。この記憶域は、第１の端１１４および第２の端１１６を有する。第１のデータ要素セット１１６〜１２０が、記憶域１１０中の第１のスタック１２４に記憶されている。第１のスタックは、記憶域１１０の第１の端１１４を向いた第１の端１３０と、記憶域１１０の第２の端１１６を向いた第２の端１３２を有する。
【００１５】
次に図２を参照すると、第２のデータ要素セット１３６〜１３８が、記憶域中の第２のスタック１４０に記憶されている。データ要素１３７は、第１のスタック１２４の第１の端１３０に近接して位置し、データ要素１３６および１３８は、第１のスタック１２４の第２の端１３２に近接して位置する。
【００１６】
次に図３を参照すると、第３のデータ要素セット１４４および１４５が、記憶域１１０中の第３のスタック１５０に記憶されている。データ要素１４５は、第１のスタック１２４の第１の端１３０に近接して位置し、データ要素１４４は、第１のスタック１２４の第２の端１３２に近接して位置する。
【００１７】
再び図２を参照すると、記憶域１１０は、相互に排他的な４つのセクション１５４、１６０、１６６、および１７０を有する。セクション１５４は、セクションのうちの端部セクションである。すなわち、セクション１５４は、記憶域の端１１４のところに端１５６を有する。セクション１６０は、セクションのうちのもう１つの端部セクションである。すなわち、セクション１６０は、記憶域の端１１６のところに端１６２を有する。セクション１６６および１７０は、セクションのうちの中間セクションである。すなわち、セクション１６６および１７０は、端部セクション１５４と端部セクション１６０の間に位置する。第１のスタック１２４は中間セクション１６６および１７０に限定され、第２のスタック１４０は端部セクション１５４および１６０に限定されることに留意されたい。
【００１８】
再び図３を参照するが、第３のスタック１５０は、中間セクション１６６および１７０に限定されていることに留意されたい。
【００１９】
次に図４を参照すると、第４のデータ要素セット１７４および１７５が、記憶域１１０中の第４のスタック１７８に記憶されている。データ要素１７５は、第１のスタック１２４の第１の端１３０に近接して位置し、データ要素１７４は、第１のスタック１２４の第２の端１３２に近接して位置する。第４のスタックは、スタック１２４および１５０と同様、記憶域の中間セクションに限定されている。
【００２０】
注目すべきは、図１〜４に示す各スタックにデータ要素の連続した１つ１つが記憶されるのに応答して、各スタックのサイズが記憶域の第１の端と記憶域の第２の端の両方に向かって大きくなることである。すなわち、各スタックは両方向に増大する。第２のスタック１４０のサイズが記憶域の第１の端および第２の端に向かって大きくなることは、第１のスタック１２４から離れる方向に、すなわち記憶域の中間から離れる方向にサイズが大きくなることを含み、第３のスタック１５０のサイズが大きくなることは、第１のスタック１２４に向かって、すなわち記憶域の中間に向かって大きくなることを含む。
【００２１】
図１の単一スタック構成では、スタック１２４が記憶域１１０の中間にあり両方向に増大するが、この構成は、中間に位置し単一方向にしか増大しない単一スタックよりも記憶域中の空間を有利に利用し、一方の端に位置し一方向にしか増大しない単一スタックと同様にうまく空間を利用することは明らかである。さらに、図２の２スタック構成では、スタック１２４が中間にあり、第２のスタック１４０の一方の部分の始点１４１が第１のスタックの片側１３０に近接して記憶域の左半分にセンタリングされて、第２のスタック１４０の他方の部分の始点１４２が第１のスタックの他方の側１３２で記憶域の右半分にセンタリングされるように、第２のスタック１４０の一部があるが、この構成は、記憶域の端に位置し中央に向かって単一方向にしか増大しない２つのスタックと同様にうまく記憶域中の空間を利用し、１つの単一方向スタックが中間にあり１つの単一方向スタックが一方の端にある構成よりも有利に空間を利用することに留意されたい。
【００２２】
一般に、スタックがいくつ記憶域中に配置されることになるかが最初に分からないと仮定した場合、かつ、本関連出願のうちの一方により、追加された第１のスタックが両方向である場合、追加される次のスタックには、追加の両方向スタックを使用するのが有利であり、最終的なスタックの数が偶数ならば、本出願に述べるような分割された両方向スタックを使用するのが好ましい。追加された第１のスタックが単一方向の場合、最終的に偶数になるスタックでは、単一方向スタックまたは分割された両方向スタックを残りのスタックに使用するのが好ましい。
【００２３】
次に図５を参照すると、スタック２２４が示されている。このスタックは最初、単一のデッド（ｄｅａｄ）要素２１５を有する。（図示の実施形態はデッド要素ＦＩＬＯスタックなので、要素２１５はデータを有しない。）図５に示すように、最初、スタック２２４に対する方向ポインタ・ビット２２４ｄｐは値「０」を有する。この値は右を指す効果を有し、したがって、スタック２２４中の次の要素が現在要素２１５の右に位置することになることを示す。図示のように、最初は、すなわちスタック２２４中にデータがないときは、ベース・ポインタＢもヘッド・ポインタＨも両方とも要素２１５を示す。
【００２４】
次に図６を参照すると、データ要素２１６がスタック２２４に追加されている。このとき、データ・ポインタ２２４ｄｐは値「１」に設定されており、スタック中の次の要素が現在要素２１６の左に追加されることになることを示す。データ要素がスタック２２４に追加すなわち「プッシュ」された後、ベース・ポインタＢは図示のように要素２１６を指し、ヘッド・ポインタＨは図示のように要素２１５を指している。ヘッド・ポインタＨは要素２１５を指して、次の要素が要素２１５に隣接するように、すなわちスタック２２４の左端に追加されることになることを示す。ベース・ポインタＢは要素２１６を指して、要素２１６がスタック２２４の右端であることを示し、これは現在におけるスタックのトップに対応する。
【００２５】
次に図７を参照すると、第２のデータ要素２１７がスタックに追加されている。このとき、データ・ポインタ２２４ｄｐは値「０」を有し、次の要素が要素２１７の右すなわちスタック２２４の右端に追加されることになることを示す。これに応じて、ヘッド・ポインタＨは、スタック２２４の右端の要素である要素２１６に移動されており、この要素に隣接するように次の要素が追加されることになる。ベース・ポインタＢは、要素２１７に、すなわちスタック２２４の新しい左端に動かされている。
【００２６】
次に図８を参照すると、第３のデータ要素２１８が追加されている。このとき、データ・ポインタ２２４ｄｐは値「１」を有し、次の要素がスタックの左端に追加されることになることを示す。したがって、ヘッド・ポインタは左端に動かされ、ベース・ポインタは右端に動かされている。
【００２７】
次に図９を参照すると、追加された最後のデータ要素、すなわち第３のデータ要素２１８が、前にスタックの右端だった位置から除去すなわち「ポップ」されており、したがって、ヘッド・ポインタＨは、今やスタックの右端となったところにある要素２１６に戻されている。ここに隣接するように、追加される次の要素がプッシュされることになる。
【００２８】
図１０〜１４に２つのスタック、スタック３２４およびスタック３４０を示す。スタック３４０は、２つの部分に分割されて、スタック３２４の各側に１つの部分が近接しており、外向きに増大する。２つに分割されているので、スタック３４０は、図示のように２つのデッド要素３３４および３３５を有する。図１０に示すように、これらのスタックは両方とも、最初はデータ要素が空である。次いで、図６〜９でスタック２２４に対して行われたのとちょうど同じく、図１１〜１３それぞれで、分割されたスタックすなわちスタック３４０にデータ要素が１つずつ追加され、最後に図１４で除去される。ポインタＨおよびＢは、図６〜９でポインタが動くのと同様に、連続したプッシュまたはポップのそれぞれに伴ってスタック３４０の一方の端から他方の端に動き、方向ポインタは、図６〜９とちょうど同じく、連続したプッシュおよびポップのそれぞれに伴って値を交互に変えることに留意されたい。
【００２９】
図１０〜１４は、予想されたかもしれないことに反し、図５〜９に示した分割されない両方向スタックと比較して、スタック３４０の各部分の間に介在するスタック３２４の存在によってスタック３４０のポインタおよびフラグの動作が複雑にはならないことを示している。スタックが空であるときを決定するために、分割されたスタックには、もう１つの情報が必要である。すなわち、ベース・ポインタとヘッド・ポインタの初期オフセットを現在オフセットと比較することによって空のスタックを検出できるように、ベース・ポインタとヘッド・ポインタの間の初期オフセットにも対応する２つのデッド要素間の初期オフセットを保存しなければならない。したがって、図１０〜１４には、スタックに対してデータ３４０オフセットが示してあり、これは、ベース・ポインタとヘッダ・ポインタの初期オフセットを示す。
【００３０】
図１８〜２２に、２つのスタック、スタック７２４および７４０を示す。スタック７４０は、２つの部分に分割されており、それぞれは、図１０〜１４のスタック３２４および３４０と同様にスタック７２４の各側に近接しているが、スタック３４０とは異なり、スタック７４０は内向きに増大する。次いで、先に図示したように、図１９〜２１のそれぞれで、分割されたスタックすなわちスタック７４０にデータ要素が１つずつ追加され、最後に図２２で除去される。前に図示した場合とちょうど同様に、ポインタＨおよびＢは、連続したプッシュおよびポップのそれぞれに伴ってスタック３４０の一方の端から他方の端に動き、方向ポインタは、連続したプッシュおよびポップのそれぞれに伴って値を交互に変えるが、スタックが最初に右側部分から内向きに増大する場合、方向ポインタは値「０」で開始することに留意されたい。
【００３１】
図１５に、データ要素を両方向スタックにプッシュする動作をフロー・チャートで示す。４１０で、データ要素をスタックに追加するためのアルゴリズムが開始する。まず４２０で、方向ポインタが検査される。方向ポインタが０に等しい場合は、４３０でヘッド・ポインタが１つ減分され、これにより、このポインタは記憶域中で左に１要素動かされる。方向が０に等しくない場合、すなわち方向ポインタ＝１の場合は、４４０でヘッド・ポインタは１つ増分され、これにより、このポインタは記憶域中で右に１要素動かされる。次いで、ヘッド・ポインタが適切に位置変更された後、４５０に示すように、ヘッド・ポインタによって示された新しい位置にデータが追加すなわちプッシュされる。４５０に示すようにまた、データがプッシュされた後、ヘッド・ポインタおよびベース・ポインタが指す位置が交換され、方向ポインタの新しい値が、前の値の逆に設定される。４６０で、アルゴリズムは終了する。
【００３２】
図１７に、データ要素を両方向スタックの外にポップする動作をフロー・チャートで示す。６１０でアルゴリズムが開始する。６２０に示すように、方向ポインタが逆転され、ヘッド・ポインタおよびベース・ポインタが指す位置が交換され、次いで、ヘッド・ポインタによって指された位置からデータがポップされる。次に６３０で、方向ポインタがテストされる。方向が０に等しい場合は、６４０でヘッド・ポインタは１つ増分され、これにより、ヘッド・ポインタは右に動かされる。方向が１に等しい場合は、６５０でヘッド・ポインタは１つ減分され、これにより、ヘッド・ポインタは左に動かされる。次に６６０で、アルゴリズムは終了する。
【００３３】
次に図１６を参照すると、本発明を実施することのできるデータ処理システムのブロック図が示されている。データ処理システム５００は、ＰＣＩ（ｐｅｒｉｐｈｅｒａｌ  ｃｏｍｐｏｎｅｎｔ  ｉｎｔｅｒｃｏｎｎｅｃｔ）ローカル・バス・アーキテクチャを採用する。図示の例ではＰＣＩバスを採用しているものの、マイクロチャネルやＩＳＡなど、他のバス・アーキテクチャを使用してもよい。プロセッサ５０２およびメイン・メモリ５０４が、ＰＣＩブリッジ５０８を介してＰＣＩローカル・バス５０６に接続されている。ＰＣＩブリッジ５０８はまた、プロセッサ５０２に対する統合メモリ・コントローラ／キャッシュ・メモリを含むこともできる。直接コンポーネント相互接続またはアドイン・ボードを介して、ＰＣＩローカル・バス５０６への追加の接続を行うこともできる。図示の例では、ローカル・エリア・ネットワーク（ＬＡＮ）アダプタ５１０、ＳＣＳＩホスト・バス・アダプタ５１２、および拡張バス・インタフェース５１４が、直接コンポーネント接続を介してＰＣＩローカル・バス５０６に接続されている。これとは対照的に、オーディオ・アダプタ５１６、グラフィックス・アダプタ５１８、およびオーディオ／ビデオ・アダプタ（Ａ／Ｖ）５１９が、拡張スロットに挿入されたアドイン・ボードによってＰＣＩローカル・バス５０６に接続されている。拡張バス・インタフェース５１４は、キーボード／マウス・アダプタ５２０、モデム５２２、および追加メモリ５２４に接続を提供する。図示の例では、ＳＣＳＩホスト・バス・アダプタ５１２は、ハード・ディスク・ドライブ５２６、テープ・ドライブ５２８、ＣＤ−ＲＯＭドライブ５３０、およびディジタル・ビデオ・ディスク読取り専用メモリ・ドライブ（ＤＶＤ−ＲＯＭ）５３２に接続を提供する。通常のＣＰＩローカル・バス実装は、３つまたは４つのＰＣＩ拡張スロットまたはアドイン・コネクタをサポートすることになる。
【００３４】
オペレーティング・システムが、プロセッサ５０２上で稼動し、図１６のデータ処理システム５００内の様々なコンポーネントの制御を調整および実現するのに使用される。オペレーティング・システムは、インターナショナル・ビジネス・マシーンズ・コーポレーションから入手可能なＯＳ／２などの、市販のオペレーティング・システムとすることができる。「ＯＳ／２」は、インターナショナル・ビジネス・マシーンズ・コーポレーションの商標である。オペレーティング・システムと共に、Ｊａｖａ（Ｒ）などのオブジェクト指向プログラミング・システムを稼動させて、データ処理システム５００上で実行されるＪａｖａ（Ｒ）プログラムまたはアプリケーションからオペレーティング・システムへの呼出しを実現することもできる。オペレーティング・システムに対する命令、オブジェクト指向オペレーティング・システム、およびアプリケーションまたはプログラムは、ハード・ディスク・ドライブ５２６などの記憶装置上にあり、プロセッサ５０２によって実行されるようにメイン・メモリ５０４にロードすることができる。
【００３５】
図１６のハードウェアは実装形態に応じて異なる場合があることを、当業者なら理解するであろう。例えば、図１６に示すハードウェアに加えて、または代わりに、光学ディスク・ドライブなどの他の周辺装置を使用することもできる。図示の例は、本発明に関する構造上の制限を意味するものではない。例えば、本発明のプロセスは、マルチプロセッサ・データ処理システムに適用することもできる。
【００３６】
本発明を、主に、単一方向増大デッド要素スタックを両方向増大デッド要素スタックに変化させるのに必要な修正に関して述べたが、他のタイプの両方向増大スタックを生み出すのに本発明を適用することもできることを、当業者なら理解するであろう。例えば、デッド要素スタックではなく、両方向増大使用済み要素スタックを生み出すのに本発明を適用することもできる。使用済み要素スタック中では、スタックを開始する前にヘッド・ポインタとベース・ポインタの両方が指すメモリ位置は、要素を記憶するのに用いられる。ただし、デッド要素（または空の要素）スタック中では、前述のように、スタックが開始する前にヘッド・ポインタとベース・ポインタの両方が発生するメモリ位置は、要素を記憶するのに用いられない。他のタイプのスタックも、両方向増大スタックを生み出すように修正することができる。したがって本発明は、デッド要素スタックに限定したものではない。
【図面の簡単な説明】
【図１】スタックを１つ有するメモリ記憶域を示す図である。
【図２】スタックを２つ有するメモリ記憶域を示す図である。
【図３】スタックを３つ有するメモリ記憶域を示す図である。
【図４】スタックを４つ有するメモリ記憶域を示す図である。
【図５】最初にデータ要素が空であるスタックを示す図である。
【図６】次いでデータ要素が１つずつ加えられるスタックを示す図である。
【図７】次いでデータ要素が１つずつ加えられるスタックを示す図である。
【図８】次いでデータ要素が１つずつ加えられるスタックを示す図である。
【図９】最後にデータ要素のうちの１つが除去されるスタックを示す図である。
【図１０】２つのスタックであって、両方とも外向きに増大し、一方２つの部分に分割されて他方のスタックの各側に１つずつあり、両方とも最初はデータ要素が空であるスタックを示す図である。
【図１１】次いで、分割されたスタックにデータ要素が１つずつ加えられる、２つのスタックを示す図である。
【図１２】次いで、分割されたスタックにデータ要素が１つずつ加えられる、２つのスタックを示す図である。
【図１３】次いで、分割されたスタックにデータ要素が１つずつ加えられる、２つのスタックを示す図である。
【図１４】最後にデータ要素が除去される、２つのスタックを示す図である。
【図１５】データ要素を両方向スタックにプッシュする動作を示すフロー・チャートである。
【図１６】本発明を実施するための例示的なシステムを示すブロック図である。
【図１７】データ要素を両方向スタックの外にポップする動作を示すフロー・チャートである。
【図１８】２つのスタックであって、一方が外向きに増大し、一方が２つの部分に分割されて他方のスタックの各側に近接し、かつ内向きに増大し、両方とも最初はデータ要素が空であるスタックを示す図である。
【図１９】次いで、分割されたスタックにデータ要素が１つずつ加えられる、２つのスタックを示す図である。
【図２０】次いで、分割されたスタックにデータ要素が１つずつ加えられる、２つのスタックを示す図である。
【図２１】次いで、分割されたスタックにデータ要素が１つずつ加えられる、２つのスタックを示す図である。
【図２２】最後にデータ要素が除去される、２つのスタックを示す図である。
【符号の説明】
１１０  記憶域
１１４  記憶域の第１の端
１１６  記憶域の第２の端
１１６〜１２０  第１のデータ要素セット
１２４  第１のスタック
１３０  第１のスタックの第１の端
１３２  第１のスタックの第２の端
１３６〜１３８  第２のデータ要素セット
１４０  第２のスタック
１４４、１４５  第３のデータ要素セット
１５０  第３のスタック
１５４  端部セクション
１５６  端部セクション１５４の端
１６０  端部セクション
１６２  端部セクション１６０の端
１６６、１７０  中間セクション
１７４、１７５  第４のデータ要素セット
１７８  第４のスタック
２１５  デッド要素
２１６  データ要素
２１７  第２のデータ要素
２１８  第３のデータ要素
２２４  スタック
２２４ｄｐ  スタック２２４に対する方向ポインタ・ビット
３２４  スタック
３３４、３３５  デッド要素
３４０  スタック
７２４  スタック
７４０  スタック
Ｂ  ベース・ポインタ
Ｈ  ヘッド・ポインタ
【図１】
0003564090.tif 000002
【図２】
0003564090.tif 000003
【図３】
0003564090.tif 000004
【図４】
0003564090.tif 000005
【図５】
0003564090.tif 000006
【図６】
0003564090.tif 000007
【図７】
0003564090.tif 000008
【図８】
0003564090.tif 000009
【図９】
0003564090.tif 000010
【図１０】
0003564090.tif 000011
【図１１】
0003564090.tif 000012
【図１２】
0003564090.tif 000013
【図１３】
0003564090.tif 000014
【図１４】
0003564090.tif 000015
【図１５】
0003564090.tif 000016
【図１６】
0003564090.tif 000017
【図１７】
0003564090.tif 000018
【図１８】
0003564090.tif 000019
【図１９】
0003564090.tif 000020
【図２０】
0003564090.tif 000021
【図２１】
0003564090.tif 000022
【図２２】
0003564090.tif 000023