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