JP7082275B2 - 配列制御プログラム、配列制御方法、配列制御装置 - Google Patents

Description

本発明は，配列制御プログラム、配列制御方法、配列制御装置に関する。

配列（array）は、データ集計等で使用する基本的なデータ構造の一つである。配列はインデックスに対応してデータである値を記憶する記憶領域（主領域）を有する。配列は、インデックス0≦i＜Nに対して、読み出し（read）と書込み（write）を実行し、あるインデックスiに対して読み出しを行うとインデックスiの主領域に最後に書き込まれた値を返す。通常の配列の初期化は、全てインデックスの主領域に初期値を書き込む初期化処理を行うため、配列サイズNに比例した初期化時間がかかる。

一方、初期化可能配列（initializable array）というデータ構造は、上記の読み出し（read）と書込み（write）に加えて、初期化（initialize）を行うと全てのインデックス0≦i＜Nの値を初期値にする。初期化可能配列は、初期化を特別にサポートする構成を有し、初期化処理を配列サイズNにかかわらず一定時間で行う。例えば、word RAM(Random Access Machine)モデルにおいて、初期化initialize(x)が呼ばれた時に初期値xを記憶しておき、各インデックスiに書込み（write）されたかどうかを示す管理情報を記憶しておき、書込みが行われていないインデックスに読み出し（read）が呼ばれた場合は初期化で記憶した初期値xを返す技術が知られている。

このような初期化可能配列のデータ構造は、例えば、リアルタイムで動作しなければならないアプリケーションプログラムにおいて、初期化処理を配列のサイズNに依存しない固定時間で行う必要がある場合に利用される。配列のデータ構造については以下の特許文献、非特許文献に記載がある。

特開平０５－１５８７８３号公報 特開２００２－２０７６３４号公報 特開２００４－３０３５３号公報 特表２００９－５２１０４９号公報

A. Aho, J. Hopcroft, and J. Ullman, "The Design and Analysis of Computer Algorithms" Addison-Wesley, 1974 2 G. Navarro, "Dynamic dictionaries in constant worst-case time" Technical Report TR/DCC-2007-11, University of Chile, Department of Computer Science, October 2007

しかしながら、従来の初期化可能配列は、インデックスに書込みが行われたか否かを示す管理情報を記憶するための追加領域が、配列の主領域に加えて必要である。

さらに、初期化可能配列において配列の要素が「NULL」や「NONE」などの通常のデータ以外の特殊な状態を持つ配列（オプショナルアレイ：Optional Arrayと称する）を実現しようとすると、配列の要素に通常のデータと区別可能なフラグや、通常データの組み合わせで区別するエスケープ処理を行う必要がある。そのようなフラグやエスケープ処理は、配列の記憶容量の増大を招き、好ましくない。

そこで，実施の形態の第1の側面の目的は，記憶容量を抑制しつつ特殊な状態を記憶する配列の配列制御プログラム、配列制御方法、配列制御装置を提供することにある。

第１の側面は，少なくともアドレスワードとデータワードを含む２以上の定数個のワードをそれぞれ有する複数のブロックを連続して構成する配列を有し、前記配列の複数のブロックの二分割位置を示す境界を記憶し、前記二分割された第１領域内の未書き込みブロックの数と、前記二分割された第２領域内の書込み済みブロックの数とが整数比になる位置を前記境界とするオプショナル配列を制御する処理をコンピュータに実行させる配列制御プログラムであって、前記処理は、
前記第１領域の未書込みブロックまたは前記第２領域の未書込みブロックに対する有効値書込みが呼ばれると、前記境界を移動して前記第１領域を拡張し前記第１領域内に任意値書込済み書込みブロックを生成するエクステンド処理を行い、
前記有効値書込みの書込み先ブロックが、前記エクステンド処理で生成した任意値書込済み書込み済みブロックと同じではなく、前記第２領域の未書込みブロックの場合、前記エクステンド処理で生成した第１領域の任意値書込済み書込みブロックのアドレスワードと、前記第２領域の前記書込み先ブロックのアドレスワードとに、互いのアドレスを記憶してリンクを形成し、
前記第２領域の前記書込み先ブロックに前記有効値を書き込み、
書込み先ブロックを前記第２領域の書込み済みブロックとする特殊値書込みが呼ばれると、前記境界を移動して前記第１領域を縮小するシュリンク処理を行って、前記境界に隣接する第１領域側の第１隣接ブロックを前記第２領域側に移動し、
前記第１隣接ブロックが書込み済みブロックの場合、
前記第１隣接ブロックのアドレスワードと、前記書込み先ブロックとリンクを形成する第１リンク先ブロックのアドレスワードとに、互いのアドレスを記憶してリンクを形成し、前記書込み先ブロックのリンクを解消して前記書込み先ブロックを未書込みブロックに変更し、
前記第１隣接ブロックが未書込みブロックの場合、
前記第１隣接ブロックとリンクを形成する第２リンク先ブロックのアドレスワードと、前記第１リンク先ブロックのアドレスワードとに、互いのアドレスを記憶してリンクを形成し、前記書込み先ブロックのリンクを解消して前記書込み先ブロックを未書込みブロックに変更する
ことを有する配列制御プログラム、である。

第１の側面によれば，配列の記憶容量を抑制しつつ特殊な状態を記憶することができる。

オプショナル配列と配列制御プログラムの一例を示す図である。 配列制御装置の構成例を示す図である。 本実施の形態におけるオプショナル配列を示す図である。 図３の配列の値の保存場所を説明する図である。 初期化と非リンクの制御を示すフローチャート図である。 初期化処理を示す図である。 読み出しの制御を示すフローチャート図である。 読み出し制御を示す図である。 非リンクの制御を示す図である。 エクステンドextend()の制御のフローチャート図である。 境界に隣接するＷ領域のブロックＢ１の種別がＷＳの場合のエクステンド制御Ｅ１を示す図である。 境界に隣接するＷ領域のブロックＢ１の種別がＷＰの場合のエクステンド制御Ｅ２を示す図である。 有効値書込みwrite(i,V)の制御を示すフローチャート図である。 有効値書込みの処理Ｗ１を示す図である。 有効値書き込み処理Ｗ２－１を示す図である。 有効値書き込み処理Ｗ２－２を示す図である。 有効値書き込み処理Ｗ２－３を示す図である。 NULL書込みwrite(i,NULL)の制御を示すフローチャート図である。 NULL書込みの処理ＷＮ１を示す図である。 NULL書込み処理ＷＮ２－１を示す図である。 NULL書込み処理ＷＮ２－２を示す図である。 NULL書込み処理ＷＮ２－３を示す図である。 NULL書込み処理ＷＮ３－１を示す図である。 NULL書込み処理ＷＮ３－２を示す図である。 NULL書込み処理ＷＮ３－３を示す図である。 配列ARの具体例と、初期化を示す図である。 図１６で説明した書込みＷ２－２の具体例を示す図である。 図１６で説明した書込みＷ２－２の具体例を示す図である。 図１６で説明した書込みＷ２－３の具体例を示す図である。 図１６で説明した書込みＷ２－１の具体例を示す図である。 図１６で説明した書込みＷ１の具体例を示す図である。 読み出しreadの３種類の具体例を示す図である。 読み出しreadの１種類の具体例の具体例を示す図である。 NULL書込みの具体例を示す図である。 通常のデータである有効値以外に、特殊値であるNULLを配列に記憶するデータ例を示す図である。 本実施の形態のNULL状態を記憶するための追加メモリ容量を示す図である。 配列の第１の例を示す図である。 初期化可能配列の２つの例を示す図である。 図３８の２つの配列をハイブリッド化した配列の例である。

図１は、オプショナル配列と配列制御プログラムの一例を示す図である。図１には、配列制御プログラムがオプショナル配列に対して行う制御が示される。図１中、処理制御部２は、処理対象データ１について所定の処理を実行し、その所定の処理に伴ってオプショナル配列４に初期化（initialize）、読み出し（read）、書込み（write）を実行する。そして、配列制御部３は、配列に対する初期化処理、書き込み処理、読み出し処理などの制御を実行する。配列４には、配列の書込み済み（または未書込み）要素などの管理情報を記憶する管理領域５が設けられる。

配列４は、配列の要素のデータ（値）を記憶するメモリなどの記憶装置である。また、管理領域５は、書込み済み（または未書込み）要素などの管理情報を記憶するメモリなどの記憶装置である。

そして、処理制御部２は、コンピュータのプロセッサがあるアプリケーションプログラム（以下単にアプリケーション）を実行することにより構築される。また、配列制御部３は、プロセッサが配列制御プログラムを実行することにより構築される。

図２は、配列制御装置の構成例を示す図である。配列制御装置は、プロセッサであるCPU（Central Processing Unit）１０と、CPUによりアクセスされるRAM(Random Access Memory)などのメインメモリ１２と、外部とのインターフェース１４とを有し、それらがバス２８を介して接続される。また、バス２８には大容量の補助記憶装置２０－２６がCPUからアクセス可能に設けられる。補助記憶装置には、基本プログラムであるOS（Operating System）や各種ミドルウエアを格納する記憶装置２０と、アプリケーションプログラム（以下、アプリケーションと称する）２２と、処理対象データ２３と、配列制御プログラム２４とを記憶する記憶装置とを有する。さらに、CPUが配列制御プログラム２４を実行して、記憶装置２６内に記憶した配列に対してアプリケーション２２からの初期化処理、書き込み処理、読み出し処理を行う。記憶装置２６内には配列の主領域に加えて、その管理データを記憶する管理領域が記憶される。

ここで、初期化可能配列について一例に基づいて説明する。配列はインデックスに対応してデータを記憶する複数の要素を含む主領域を有する。そして、配列の「初期化」とは全ての要素を初期値で初期化することで、「書込み」とは初期化された要素に書込み値を上書きすることで、「未書込み」とは初期化されたままの要素で未だ書込み値が上書きされていないことをそれぞれ意味する。

図３７は、配列の第１の例を示す図である。配列ARは、インデックスに対応してデータ（値）をそれぞれ記憶する複数の要素を含む主領域を有する。図３７の配列ARは、主領域にインデックス０－７それぞれに対応する８つの要素を有する。また、主領域に加えて、ある集計値を記憶する集計値領域AGを有する。例えば、プロセッサがアプリケーションを実行して、８名のユーザのうちサーバに１日３回以上アクセスしたユーザ数をリアルタイムに集計する場合を想定する。つまり、配列ARのインデックス０－７は８名のユーザに対応し、各要素には各ユーザのアクセス回数が書き込まれる。そして、アクセス回数が３回以上のユーザ数が、集計値として集計値領域AGに記憶される。

配列AR1は、初期化した状態を示す。すなわち、アプリケーションからの初期化処理の呼び出しに応答して、プロセッサは配列制御プログラムを実行して、配列AR1の全ての要素に初期値０（アクセス数０回）を、集計値領域AG1には初期値０（０人）をそれぞれ書き込む。そして、配列AR2では、インデックス２に対応するユーザがアクセスしたことに伴い、アプリケーションによりインデックス２の要素の値「２」が加算されて「３」が書き込まれる。同時に、集計値領域AG1の値「３」が加算されて「４」が書き込まれる。最後に、アプリケーションにより、要求された任意のタイミングで、配列AR3に対応する集計値領域AG3の値「４」が読み出される。そして、毎日所定のタイミングで、配列が初期化処理される。上記の初期化処理、配列の要素の値の読み出し処理、書込み処理は、配列制御プログラムによりプロセッサが実行する。

図３７の例では、初期化処理では、全てのインデックスに初期値「０」を書き込む必要がある。したがって、初期化処理は、配列サイズＮに比例した時間Ｏ（Ｎ）がかかり、初期化処理中は配列に対して書込みや読み出しを実行できない。一方、読み出しと書込みは定数時間Ｏ（１）で可能である。図３７の配列は、リアルタイムのサーバへのアクセス回数を記録するアプリケーションには不向きである。なお、前記Ｏはオーダーの頭文字である。

図３８は、初期化可能配列の２つの例を示す図である。初期化可能配列とは、初期化を高速に行うことができるデータ構造である。初期化可能配列がサポートする機能には、次のものがある。
（１）読み出しread(i)では、インデックスｉの要素の値を返す。
（２）書込みwrite(i,x)では、インデックスｉの要素にｘを書き込む。
（３）初期化initialize(x)では、全てのインデックス０≦ｉ＜Ｎの要素にｘを書き込む。

そして、プロセッサは、配列制御プログラムを実行することにより、初期化initialize(x)が呼ばれたとき、配列の全ての要素に初期値ｘを書き込まず単に初期値ｘを記憶し、各インデックスについて書込みされたか否かの管理情報を記憶する。そして、書き込みされてないインデックスiへの読み出しread(i)が呼ばれた場合、初期化で記憶した初期値ｘを返す。これにより、初期化処理を配列のサイズNに依存しない固定時間で行う。

図３８（Ａ）の配列では、インデックス０－１５のＮ＝１６の要素を有する配列ARが、４要素ずつのブロック０－３に分割され、管理領域として、各ブロックの未書込みと書込み済みを区別するビットマップBT_MPと、配列の全要素の初期値を記憶する初期値領域INTとを有する。プロセッサが配列制御プログラムを実行し、初期化が呼ばれると初期値領域INTに初期値「０」が書き込まれ、ビットマップブロックに「０」が書き込まれる。初期化では全インデックスに初期値を書き込むことは行わない。書き込みが呼ばれると、そのブロックの書込み先インデックスに書込み値が書き込まれ残りのインデックスに初期値「０」が書き込まれ、ビットマップの対応するブロックに書込み済みを示す「１」が書き込まれる。ビットマップは、書込みが行われたブロックには「１」を、未書込みのブロックには「０」を記憶し、書込み済みブロックと未書込みブロックの管理情報を記憶する。

図３８（Ａ）の配列では、初期化は図３７の配列より短い時間Ｏ（Ｎ／ｌｏｇＮ）で完了するが、ビットマップを初期化する必要があるので初期化時間は配列サイズＮに依存する時間ｏ（Ｎ）である。なお、時間ｏ（Ｎ）＝Ｏ（Ｎ／ｌｏｇＮ）は、時間Ｏ（Ｎ）より短いことを意味し、logは底を２とする二進対数である。但し、管理情報として初期値INTに加えてビットマップBT_MPが含まれるので、管理にＯ（Ｎ／ｌｏｇＮ）＝ｏ（Ｎ）の追加領域が必要になる。つまり、ビットマップはブロック毎の要素を有するので、配列サイズＮに依存した領域Ｏ（Ｎ）より小さいが領域ｏ（Ｎ）が必要である。

図３８（Ｂ）の配列は、インデックス０－１５のＮ＝１６の要素を有する配列ARに加えて、管理情報を記憶するための補助領域AUX、スタック領域ST、スタックポインタ領域ST_P、初期値領域INTを有する。補助領域とスタック領域は共に１６の要素を有する。この配列では、配列制御プログラムを実行するプロセッサが、配列ARのあるインデックスに書込みを行うと、補助領域の同じインデックスの要素とスタック領域の最小未書込み要素とに互いのインデックスを書き込んで双方向リンクを生成する。双方向リンクの生成とともに、スタックポインタが最大書込み要素のインデックスに更新される。

図３８（Ｂ）の例では、配列ARには５つのインデックスの要素に書込みが行われ、補助領域AUXの同じ５つのインデックスの要素とスタック領域の要素との間に双方向リンクが形成されている。例えば、配列のインデックス３には値「０」が書き込まれ、補助領域の同じインデックス３の値「４」に対応するスタック領域のインデックス４には補助領域のインデックス「３」が書き込まれ、補助領域とスタック領域との間で双方向リンクが形成されている。また、スタックポインタの値「４」は、スタック領域内の双方向リンクが形成されている最大インデックスを指している。

読み出しが呼ばれると、プロセッサは、読み出し先インデックスｉの補助領域の要素が双方向リンクを形成していれば、配列の読み出し先インデックスの値を返し、形成されていなければ初期値領域INTの値を返す。

この配列において、初期化が呼ばれると初期値領域INTに初期値「０」を書込み、スタックポインタST_Pに最小インデックス「０」を書き込む。したがって、初期化に要する時間は配列サイズＮに依存せず定数時間Ｏ（１）である。しかし、管理領域は配列の主領域の２００％程度を要し、追加領域は配列サイズＮに依存するＯ（Ｎ）である。

図３９は、図３８の２つの配列をハイブリッド化した配列の例である。図３９では、図３８（Ａ）と同様の配列ARの主領域とビットマップBT_MPを有する。さらに、ビットマップについて、図３８（Ｂ）と同様の補助領域AUX、スタックST、スタックポインタST_Pを有する。ビットマップが配列ARの主領域より小さいサイズであり、その分管理領域を小さくできる。

この例では、初期化が定数時間Ｏ（１）で可能である。一方、管理情報を記憶する管理領域にＯ（Ｎ／ｌｏｇＮ）＝ｏ（Ｎ）の追加領域が必要である。一般に、図３８（Ａ）のビットマップ法の３倍程度の追加領域になる。

図３７，図３８（Ａ），図３８（Ｂ），図３９をまとめると、図３７の配列は、初期化時間は配列サイズＮに依存する（Ｏ（Ｎ））が、管理の追加領域は定数サイズ（Ｏ（１））である。図３８（Ａ）の配列は、初期化時間は配列サイズＮに依存する時間よりも短く（Ｏ（Ｎ／ｌｏｇＮ）＝ｏ（Ｎ））、管理の追加領域も同様である（Ｏ（Ｎ／ｌｏｇＮ）＝ｏ（Ｎ））。図３８（Ｂ）の配列は初期化時間は定数時間（Ｏ（１））であるが、管理の追加領域は配列サイズＮに依存するサイズ（Ｏ（Ｎ））。そして、図３９の配列は、初期化時間は定数時間（Ｏ（１））、管理の追加領域は配列サイズに依存するサイズより小さい（Ｏ（Ｎ／ｌｏｇＮ）＝ｏ（Ｎ））。

［第１の実施の形態の初期化可能配列］
以下説明する本実施の形態の配列は、通常のデータ以外の特殊状態を少ないメモリ容量で記憶することができ、特殊状態（特殊値）への初期化時間は定数時間、管理の追加領域も少ない容量である。

配列はインデックスに対応してデータを記憶する複数の要素を含む主領域を有する。各要素は複数のインデックスに対応する複数のワード（アドレスワードとデータワード）を有する。そして、配列の「初期化」とは全ての要素を特殊状態（以下特殊状態（特殊値）の一例であるNULLで説明する）で初期化すること、「有効値の書込み」とはNULL（特殊値）が記憶されている要素に有効な値（有効値）である書込み値を上書きすること、「特殊値の書込み」とは要素を有効なデータが書き込まれていない（保存されていない）、言い換えると、特殊値（NULL）が書き込まれた状態にすることをそれぞれ意味する。

図３５は、通常のデータである有効値以外に、特殊値であるNULLを配列に記憶するデータ例を示す図である。（１）は表現したいデータ例である。この例は、配列の主領域内の要素に、通常データ（有効値）とNULL（特殊値）とを混在して記憶する例である。通常データは０と１からなる二進数であり、図中１６進数表記で示される。例えば、「FF」は二進数の「1111 1111」であり、「AC」は二進数の「1010 1100」である。但し、NULLは通常データとは異なる特殊値であるので、通常データと混在することはできない。

（２）はフラグを利用してNULLを記憶する例である。この場合、配列の要素の主領域に加えて、各要素に１ビットのフラグ領域FLAGを有する。そして、フラグFLAGが「０」であれば通常データ（有効値）、「１」であればNULL（特殊値）とすることで、NULLを記憶する。

（３）はエスケープ方式でNULLを記憶する例である。エスケープ方式では、通常データFFを「FF FF」と、NULLを「FF 00」とそれぞれ定義する。主領域の各要素には、00～FEはそのまま記憶され、FFは「FF FF」と記憶され、NULLは「FF 00」と記憶される。

上記のフラグ方式では、配列にフラグビットを記憶するフラグ領域を追加する必要がある。また、エスケープ方式でも、配列の各要素を「FF FF」「FF 00」を記憶するために、通常データを記憶する場合の主領域と同じ容量の追加領域が必要になる。

図３は、本実施の形態におけるオプショナル配列を示す図である。この配列は、読み出しと書き込みが配列サイズに依存しない定数時間で行われ、初期化も定数時間で行われる。さらに、要素にNULLを書き込むために要素の領域に追加される領域はない。また、管理の追加領域は配列サイズに依存するが非常に少ない記憶サイズである。

図３の配列ARは、インデックス０≦ｉ＜１６でＮ（＝１６／２）個の要素を有し、アドレスワードとデータワードを含む２以上の定数個（図３の例は２個）のワード（主領域の各要素に対応）をそれぞれ有する複数（図３の例は８個）の要素（またはブロック）を連続して構成する。

図３の例では、各要素（ブロック）には２個のワードが含まれ（１要素（１ブロック）が２ワードを含む）、要素（ブロック）内の最小インデックスのワードは後述する双方向リンクのリンク先インデックスを書き込むアドレスワード、その他のインデックスのワードは有効値を書き込むデータワードである。但し、アドレスワードにもデータが書き込まれる。したがって、各要素（ブロック）は偶数インデックスで特定され、各ワードはインデックスで特定される。

ここで、値が書き込まれる要素内の２つの領域をワードと称する理由は、書き込まれる値が８ビット、３２ビット、６４ビットなどのワードであることに起因する。

さらに、管理領域として、配列の複数のブロックの二分割位置を示す境界BDを記憶する境界ポインタBD_Pを有する。境界ポインタBD_Pには境界BDの右側のインデックス「６」が書き込まれている。

境界で二分割された左側の第１領域は未書込みブロックの数が記憶されるＭ領域と、右側の第２領域は書込みブロックの数が記憶されるＷ領域と、それぞれ称する。分割方法は、Ｍ領域の未書込みブロック（ＭＰと称する）の数と、Ｗ領域の書込み済みブロック（ＷＰと称する）の数とが同数になる位置に境界BDを選択することである。この境界は一意に定まる。

さらに、Ｍ領域の未書込みブロックＭＰとＷ領域の書込み済みブロックＷＰとを一対一に対応付ける。一対一の対応付けは、両ブロックＭＰ，ＷＰ間に双方向リンクを形成することで行われる。図中、双方向リンクは実線の矢印で示される。

具体的には、インデックス０，１の未書込みブロックＭＰとインデックス１２，１３の書込み済みブロックＷＰの場合、未書込みブロックＭＰのアドレスワードAWD（インデックス０）には書込み済みブロックＷＰのインデックス「１２」が書き込まれ、書込み済みブロックＷＰのアドレスワードAWD（インデックス１２）には未書込みブロックＭＰのインデックス「０」が書き込まれる。これにより両ブロックＭＰ，ＷＰは双方向リンクを形成する。インデックス２，３のブロックＭＰとインデックス８，９のブロックＷＰも同様に双方向リンクを形成する。Ｍ領域内の未書込みブロックＭＰの数とＷ領域内の書込み済みブロックＷＰの数が同じになるよう境界BDを管理し、両ブロックＭＰ、ＷＰの間に双方向リンクを形成することで、Ｍ領域の未書込みブロックＭＰとＷ領域の書込み済みブロックＷＰを管理情報として記憶する。また、境界BDの両側の両ブロックＭＰ、ＷＰの数を同数に管理する。

双方向リンクを形成するとＷ領域の書込み済みブロックＷＰのアドレスワードAWD（インデックス１２）には値を書き込むことができない。そこで、Ｗ領域の書込み済みブロックＷＰのリンク先のＭ領域の未書込みブロックＭＰのデータワードDWD（インデックス１）にブロックＷＰの値を書き込む。この点については後で詳述する。

一方、Ｍ領域の書込み済みブロックＭＳとＷ領域の未書込みブロックＷＳとが、一対一に対応付けされないように、つまり上記の双方向リンクができないように、Ｗ領域のブロックのアドレスワードにＭ領域の書込みブロックＭＳのインデックスが格納されないよう制御する。

具体的には、インデックス４，５の書込み済みブロックＭＳのアドレスワードには「１４」が書き込まれているので、インデックス１４，１５のブロックに片方リンクを形成している。そこで、インデックス１４，１５のブロックのアドレスワードにはＭ領域のインデックスが記憶されないようにする。図３の例では、インデックス１４，１５のブロックのアドレスワードには自分のインデックス「１４」が書き込まれている。また、インデックス６，７のブロックＷＳ、インデックス１０，１１のブロックＷＳは、未書込みブロックであり記憶されている値は読み出しでは参照されず（図中？で示す。）、特殊値のＮＵＬＬが読み出される。

ブロックの種別は、対応付けのあるブロックをＰ（pair）ブロック、対応付けのないブロックをＳ（single）ブロックと称する。したがって、Ｍ領域とＷ領域にそれぞれＰブロックとＳブロックが存在しうるので、ブロックの種別は以下の４種類になる。
Ｍ領域
ＭＰ：未書込みブロック、ＮＵＬＬのブロック、ＷＰと双方向リンクが形成される。
ＭＳ：書込み済みブロック、ｍビットの要素であるブロック内の２つのワードにそれぞれm/2ビットの有効値が書き込まれ、Ｗ領域のブロックと双方向リンクは形成されない。
Ｗ領域
ＷＰ：書込み済みブロック、ＭＰと双方向リンクが形成される。ｍビットの要素であるブロック内の２つのワードのうち最小インデックス以外のデータワードと、リンク先のブロックＭＰの最小インデックス以外のデータワードとにm/2ビットの有効値がそれぞれ書き込まれる。
ＷＳ：未書込みブロック、ＮＵＬＬのブロック、Ｍ領域のブロックと双方向リンクは形成されない。

図４は、図３の配列の値の保存場所を説明する図である。図４の配列ARは図３の配列ARと同じである。まず、Ｍ領域の書込み済みブロックＭＳには、そのブロックの２つのワードに値を保存する。例えば、インデックス４，５のブロックＭＳが例である。

次に、Ｗ領域の書込み済みブロックＷＰには、そのブロックＷＰのデータワードDWDと、ブロックＷＰと双方向リンクするＭ領域の未書込みブロックＭＰのデータワードDWDと に２つの値を保存する。つまり、Ｍ領域の未書込みブロックＭＰとＷ領域の書込み済みブロックＷＰは双方向リンクを形成するためにアドレスワードAWDにはリンク先インデック スが互いに書き込まれる。したがって、アドレスワード以外のワードに値を保存する。例えば、ブロックＷＰのインデックス８に保存する値「０」はリンク先ブロックＭＰのインデックス３のデータワードDWDに保存される。また、ブロックＷＰのインデックス１２に保存される値「０」はリンク先ブロックＭＰのインデックス１のデータワードDWDに保存される。なお、１つのブロックの最小インデックスはアドレスワードであり、残りのインデックスはデータワードである。１ブロックのワード数をｂ≧２とすると、対応付けられた１対のブロックの２＊ｂワードのうち、２ワードがアドレスワードに、２＊ｂ－２のワードがデータワードとして使用される。

最後に、未書込みブロックＭＰ、ＷＳは、ＮＵＬＬが保存されているとみなし、但し、ブロックＭＰ，ＷＳのワードには任意の値が保存される。たとえば、インデックス１４，１５のブロックＷＳの読み出し値は、ＮＵＬＬである。

図４には、実際に保存されている値が示される実配列ARに対応して、保存されているインデックスと値を論理的に示した論理配列L_ARが示されている。特にインデックス８，１２に書き込まれた値「９」「０」は、それぞれインデックス３，１に保存されていることが論理配列L_ARに示される。

図３の初期化可能配列は、以下のような特徴を有する。

（１）配列の未だ書き込みが行われていない主領域に、書込み済み領域（ブロックＷＰ）と未書込み領域（ブロックＭＰ）を区別する管理情報（双方向リンク）を保存することで、管理の追加領域を境界ポインタBD_Pにする。したがって、管理の追加領域は配列サイズＮに依存するオーダーより小さいＯ（ｌｏｇＮ）になる。

（２）配列の主領域の書込み済み領域と未書込み領域を区別する管理情報として、書込み済み領域のインデックスを記憶すると、書込みが進むに従い配列内の未書込み領域が減少するので、管理情報を保存できる領域が不足する。一方、管理情報として未書込み領域を記憶すると、初期化処理で全ての領域が未書込み領域になるので、初期化処理が配列サイズに依存する時間を要し定数時間で完了できない。そこで、書込み済み領域を記憶することと未書込み領域を記憶することをハイブリッド化する。すなわち、配列の主領域を、未書込み領域を管理するＭ領域と、書込み領域を管理するＷ領域とに分割し、初期化ではＭ領域のサイズを０にし、書込みが進むにつれてＷ領域のサイズが減少しＭ領域のサイズが増加するようにする。それにより、初期化時間を定数時間で完了し（境界ポインタをインデックス０にし全要素をＷＳブロックにして全要素をＮＵＬＬにする）、書込みが進むにつれて管理するＷ領域の書込み済み領域ＷＰの数を減らして管理情報（双方向リンク）が減少するよう制御する。また、書き込み時に管理情報（境界BD、双方リンク）の変更を行う。

（３）管理情報は配列の未書込み領域に保存するが、ユーザがどこに書き込むかどこに書き込まないかを決定するので、未書込み領域が断片化してしまう。そこで、配列の主領域をアドレスワードとデータワードを持つ要素（ブロック）単位で管理し、１対のブロックのアドレスワードを利用して双方向リンクを生成して管理情報を保存し、ユーザデータの一部を双方向リンク先のブロックのデータワードに保存する。

（４）そして、未書込みブロックＭＰ，ＷＳをＮＵＬＬと定義することで、有効なデータとＮＵＬＬとを区別可能にする。つまり、境界ポインタと双方向リンクを含む管理情報により、ＮＵＬＬを記憶する要素（ブロック）を区別可能にする。

［配列制御プログラム］
次に、プロセッサにより実行される配列制御プログラムの処理、配列の全要素（ブロック）をＮＵＬＬにする初期化initialize(x)、インデックスｉの読み出しread(i)、インデックスi（ｉは偶数）の要素（ブロック）に有効値[x1,x2]を書き込む書込みwrite(i,[x1,x2])と、インデックスｉ（ｉは偶数）の要素(ブロック)にＮＵＬＬを書き込むwrite(i,NULL)と、書込み機能を実現するための補助機能であるインデックスｉのブロックの非リンクunlink(i)、境界BDを右シフトしてＭ領域を拡張するエクステンドextend()、境界BDを左シフトしてＷ領域を拡張するシュリンク、それぞれの制御方法を説明する。

まず、プロセッサは、配列制御プログラムを実行して、初期化initialize(ｘ)が呼ばれると以下の初期化処理を行い、読み出しread(i)が呼ばれるとインデックスｉの値を読み出して返し、有効値書込みwrite(i,[x1,x2])が呼ばれるとインデックスｉの要素の２つのワードに値[x1,x2]を書き込む。さらに、ＮＵＬＬ書込みwrite(i,NULL)が呼ばれるとインデックスｉの要素をＮＵＬＬ記憶状態にする。

［初期化initialize(x)］
図５は、初期化と非リンクの制御を示すフローチャート図である。図６は、初期化処理を示す図である。初期化initialize(x)が呼ばれると、配列制御プログラムを実行するプロセッサは、境界ポインタBD_Pにインデックス０を保存して境界を左端に移動して初期化する（S1）。境界ポインタBD_Pには境界の右側のインデックス0が保存される。境界の初期化により配列ARの主領域は全てＷ領域になり、双方向リンクはなくなり、Ｗ領域は全て未書込みブロックＷＳになり、ＮＵＬＬ記憶状態のブロックになる。図５の非リンクは後述する。

［インデックスｉの読み出しread(i)］
図７は、読み出しの制御を示すフローチャート図である。図８は、読み出し制御を示す図である。ここでは読み出し先インデックスｉのブロックをＢ１と称する。

読み出しread(i)（iは偶数）が呼ばれると、配列制御プログラムを実行するプロセッサは、インデックスｉのブロックＢ１の種別をチェックする(S21)。ブロックの種別の判別は、インデックスｉが境界ポインタより小さいか（Ｍ領域）以上か（Ｗ領域）の判定と、インデックスｉのブロックが双方向リンクを持つか否か（双方向リンクならＭＰ，ＷＰ、それ以外ならＭＳ，ＷＳ）により行う。インデックスｉのブロックＢ１の種別がＭ領域の未書込みブロックＭＰまたはＷ領域の未書込みブロックＷＳの場合（S21のMPまたはWS）、ＮＵＬＬを返して終了する（S22）。図８中のA:read(14)が一例である。

インデックスｉのブロックＢ１の種別がＭ領域の書込み済みブロックＭＳの場合(S21のMS)、インデックスｉとｉ＋１に保存されている値を返して終了する(S23)。図８中のB:read(4)が一例である。

インデックスｉのブロックＢ１の種別がＷ領域の書込み済みブロックＷＰの場合(S21のWP)、ブロックＢ１に対応付けられた（双方向リンクされた）ブロックＭＰの該当するデータワードに保存されている値と、インデックスｉ＋１の値を返して終了する(S25)。図８中のC:read(8)が一例である。図８の例ではブロックのデータワードは１個しかないので、インデックス２のブロックＭＰのインデックス３のデータワードの値と、インデックス９の値を返す。１つのブロックが複数のデータワードを有する場合、あらかじめ決められたデータワードに双方向リンク先のアドレスワードに書き込まれる値が保存される。

次に、有効値書込みwrite(i,V)（iは偶数、Vは有効値または有効データ）が呼ばれると、以下の非リンクunlink(i)と、境界をシフトするエクステンドextend()とを適宜呼んで、インデックスiのブロックに値V（インデックスｉにx1、i+1にx2）を書き込む処理が行われる。エクステンドextendは２種類のエクステンド処理Ｅ１，Ｅ２がある。有効値書込みwriteは４種類の書込み処理Ｗ１、Ｗ２－１，Ｗ２－２，Ｗ２－３がある。また、それぞれの処理で、意図しないリンクが形成されたＭ領域のブロックのリンクを切断して種別ＭＳにする非リンクunlink処理が行われる。つまり、エクステンドextendと非リンクunlinkは、書き込みの補助機能である。

［インデックスｉのブロックの非リンクunlink(i)］
図５は、非リンクの制御を示すフローチャート図である。図９は、非リンクの制御を示す図である。非リンクunlinkは、種別ＭＳのブロックの値を書き替えた時にＷ領域のブロックと偶然双方向リンクができてしまう場合、意図してないリンクを切断して種別ＭＳを維持するなどの目的で使用する。非リンクは、例えば偶然生成された双方向リンクのＷ領域側のブロックのアドレスワードを自身のインデックスで書き換えることで行われる。

非リンクunlink(i)が呼ばれると、配列制御プログラムを実行するプロセッサは、Ｍ領域のインデックスiのブロックＢ１に双方向リンクが形成されたＷ領域のブロックＢ２が存在するかチェックし(S11)、存在する場合、Ｗ領域のブロックＢ２のアドレスワードをＭ領域のブロック以外のインデックスに書き換える(S12)。具体的には、例えばＷ領域のブロックＢ２のアドレスワードを自身のインデックスに書き換える。

図９の具体例では、配列AR1でブロックＢ１がＭ領域の書込み済みブロックＭＳであり、一方Ｗ領域内の未書込みブロックＷＳ（Ｂ２）のアドレスワードに偶然「２」が保存されていたとする。配列AR2にて、インデックス２に値「１０」が書き込まれると、偶然にＭ領域の書込み済みブロックＢ１とＷ領域の未書込みブロックＢ２との間に意図しない双方向リンクが発生する。そこで、非リンクunlink(2)を呼び出し、Ｗ領域のブロックＢ２のアドレスワードに自身のインデックス「１０」を書き込んで意図しないリンクを切断する。非リンクにはＷ領域のインデックスを書き込めばよいが、前述のように自身のインデックスを書き込んでも良い。

［エクステンドextend()］
エクステンドextendは、未書込みブロックＭＰまたはＷＳに有効値書込みが行われる場合、未書込みのブロックのうち一つのブロックに任意値を書込み、任意値が書き込まれた種別ＭＳのブロックを生成し返す処理である。そして、有効値書込みwrite処理では、この任意値書込済ブロックＭＳに書込みが行われるか、任意値書込済ブロックＭＳの位置をユーザの書込み先に実質的に移動させ移動した任意値書込済ブロックに書込みが行われる。１つのブロックは２つ以上のワードを有しその２つのワードに書込みが行われる。したがって、任意値書込済ブロックＭＳを取得し、その任意値書込済ブロックＭＳの２つのワードに書込み値を書き込む（または移動した任意値書込済ブロックの１つのワードに書込み値を書き込む）。

別の言葉で説明すると、未書込みブロックＭＰまたはＷＳに有効値書込みが行われると、未書込みブロックＭＰまたはＷＳが１つ減り、書込み済みブロックＭＳまたはＷＰが１つ増加する。そこで、エクステンドextend処理は、Ｍ領域のブロックＭＳとＷ領域のブロックＷＰの数を等しく保つための処理を行う。

上記の通り、エクステンドで取得した任意値書込済ブロックＭＳには書込み値（有効値）の書込みが行われるので、以下のエクステンド処理では任意値の書込み処理S32,S36を省略することができる。つまり、任意値であるから、任意値の書き込み処理S32,S36を省略してもそのブロックＭＳが任意値書込済であることに変わりはない。

図１０は、エクステンドextend()の制御のフローチャート図である。図１１は、境界に隣接するＷ領域のブロックＢ１の種別がＷＳの場合のエクステンド制御Ｅ１を示す図である。図１２は、境界に隣接するＷ領域のブロックＢ１の種別がＷＰの場合のエクステンド制御Ｅ２を示す図である。

図１０のフローチャートに示されるとおり、エクステンドextend()が呼ばれると、配列制御プログラムを実行するプロセッサは、境界に隣接するＷ領域のブロックＢ１（境界ポインタのインデックスのブロック）の種別を判定する(S31)。

（Ｅ１）図１１に示されるとおり、境界に隣接するＷ領域のブロックＢ１が種別ＷＳの場合(S31のWS)、プロセッサは、この未書込みブロックＷＳ（Ｂ１）に任意値を書込み(S32)、境界をシフトしてＭ領域を1ブロック分拡張し（S33）、必要な場合非リンクunlink処理してブロックＢ１の種別をＭＳ(Ｂ１)にする（S34）。この任意値書込み済みブロックＭＳ（Ｂ１）が、書き込み対象の空ブロックＭＳとしてリターンされる(S35)。つまり、この処理では、境界隣接のＷ領域のブロックＷＳ（Ｂ１）を直接任意値書込済ＭＳ（Ｂ１）に変更し、直接境界隣接のＷ領域のブロックＷＳ（Ｂ１）を1減らしＭＳ（Ｂ１）を1増やし、ＭＰとＷＰの数に変動がなく、ＭＰとＷＰの数が等しい状態を維持する。

（Ｅ２）一方、図１２に示されるとおり、境界に隣接するＷ領域のブロックＢ１が種別ＷＰの場合(S31のWP)、プロセッサは、この書込み済みブロックＷＰ（Ｂ１）のアドレスワードに、ブロックＷＰ（Ｂ１）のリンク先ブロックＭＰ（Ｂ２）のデータワードに書き込んでいたデータを書込み（コピー）（S36）、リンク先ブロックＭＰ（Ｂ２）の全てのワードに任意値を書込む（この書込みは省略可）（S37）。そして、境界をシフトしてＭ領域を1ブロック拡張し（S38）、必要な非リンクunlink処理し（S39）、境界に隣接するＷ領域のブロックＷＰ（Ｂ１）とそのリンク先ブロックＭＰ（Ｂ２）を共に任意値書込み済みＭＳ（Ｂ１），ＭＳ（Ｂ２）にする。そして、任意値書込み済みブロックＭＳ（Ｂ２）がリターンされる(S40)。つまり、この処理では、エクステンドによりＷＰ（Ｂ１）が１減るので、ＭＰ（Ｂ２）を１減らしＭＳ（Ｂ２）を１増やすことで、ＭＰとＷＰの数が等しい状態を維持する。但し、境界に隣接するＷ領域のブロックＷＰ（Ｂ１）のリンク先のＭＰ（Ｂ２）を任意値書込み済みＭＳに変更することができないので、境界右ブロックＷＰ（Ｂ１）にそのリンク先ＭＰ（Ｂ２）のデータを書き込んでＭＳ（Ｂ１）に変更し、リンク先ＭＰ（Ｂ２）に任意値を書き込んで任意値書込み済みＭＳ（Ｂ２）を生成する。これにより、Ｍ領域のＭＰとＷ領域のＷＰの数を等しく保つ数合わせを行う。

上記のとおり、エクステンドextend処理の意味は次の通りである。例えば、未書込みブロックＭＰに書込みが行われて書込み済みＭＳに変更されるとＭ領域のＭＰが減少し、一方、未書込みブロックＷＳに書込みが行われて書込み済みブロックＷＰに変更されるとＷ領域のＷＰが増加し、Ｍ,Ｗ領域の管理対象ブロックＭＰ,ＷＰのうちＭＰの減少またはＷＰの増加になる。その結果、ＭＰ,ＷＰの数を同じに保つという条件を維持するために、境界を右側にシフトさせて、ＭＰの減少にはＭＰの追加を行い、ＷＰの増加にもＭＰの追加を行うことが必要になる。

この数合わせのために、エクステンドextend処理を行う。上記の通り、エクステンドextend処理では、境界を右シフトし任意値書込み済みＭＳを生成する。そして、以下に説明するwrite処理では、この任意値書込み済みＭＳに書込み値が直接書き込まれるか、任意値書込み済みＭＳの位置を変更して変更後のブロックに書込み値が書き込まれる。

［インデックスiの要素に有効値Ｖの書込みwrite(i,V)但しiは偶数、V=[x1,x2]］
図１３は、有効値書込みwrite(i,V)の制御を示すフローチャート図である。また、図１４は、有効値書込みの処理Ｗ１を示す図である。図１５，図１６，図１７は、有効値書き込み処理Ｗ２－１，Ｗ２－２，Ｗ２－３をそれぞれ示す図である。ここでは、書込み先インデックスのブロックをＢ１、エクステンドextendにより取得するブロックをＢ２、書込み先ブロックＢ１と対応付けられているブロックをＢ３と称する。

有効値書込みwrite(i,V)の呼び出しがあると、配列制御プログラムを実行中のプロセッサは、書込み先インデックスｉのブロックＢ１の種別を判別する(S51)。

（Ｗ１）図１４に示されるとおり、書込み先のインデックスｉのブロックＢ１の種別が書込み済みブロックＭＳまたはＷＰの場合（S51のMSまたはWP）、読み出しread処理と同じ方法で書込み先を特定し、その書込み先に書込み値ｘを書き込む。例えば、インデックスｉのブロックＢ１がＭＳの場合、インデックスｉのブロックＢ１（ＭＳ）のインデックスｉ、ｉ＋１のワードに書込み値V=[x1,x2]を書込み（S52）、非リンクunlinkを使って意図しないリンクを切断する（S53）。また、インデックスｉのブロックＢ１がＷＰの場合、書込み先のブロックＷＰ（Ｂ１）のリンク先ブロックＭＰのデータワードに値x1を、インデックスi+1に値x2をそれぞれ書き込む(S56)。図１４には、write(0,[12,0])が工程S52で書き込まれ、write(8,[12,12])が工程S56で書き込まれることが示される。

（Ｗ２）書込み先のインデックスｉのブロックＢ１の種別が未書込みブロックＭＰまたはＷＳの場合(S51のMPまたはWS)、エクステンドextend処理を行って任意値書込み済みブロックＢ２(ＭＳ)を取得する（S57）。

（Ｗ２－１）図１５に示すとおり、書込み先ブロックＢ１と任意値書込み済みブロックＢ２とが同じブロックの場合（S58のYES）、書込み先ブロックＢ１が任意値書込み済みＭＳ（Ｂ１）であるので、書込み先がＭＳの場合と同様にインデックスｉ、i+1に値V=[x1,x2]を書込み（S52）、必要なunlink処理をして意図しないリンクを切断してＭＳ（Ｂ１）を維持する（S53）。図１５では、write(2,[12,0])について、extendで書込み先ブロックＢ１（ＭＰ）がＭＳ（Ｂ１）に変更され、代わりにインデックス６のブロックがＢ１のリンク先ブロックＷＰのリンク先に変更されている。そして、ＭＳに変更された書込み先ブロックＭＳ（Ｂ１）のインデックス２，３に値[12,0]が書き込まれ、unlink(2)によりリンクが切断されている。

つまり、書込みＷ２－１では、エクステンド処理で取得した任意値書込み済みブロックＢ２(ＭＳ)が書込み先ブロックＢ１と一致したので、書込み先インデックスｉ，ｉ＋１に値を書き込む。

（Ｗ２－２）図１６に示す通り、書込み先ブロックＢ１と任意値書込み済みブロックＢ２とが異なるブロックで(S58のNO)、Ｂ１の種別がＷＳの場合（S59のWS）、書込み先ブロックＢ１（ＷＳ）とエクステンドで生成した任意値書込み済みブロックＢ２（ＭＳ）の間に双方向リンクを作成して対応付け（S60）、書込み先ブロックＢ１（リンク付けでＷＳから変更したＷＰ）に任意値を書込む（S61）。そして、書込み先ブロックＢ１（ＷＰ）がＷＰの場合と同様にインデックス１０，１１に書込み値V=[12,0]を書き込む（S56）。

つまり、書込み先ブロックＢ１（ＷＳ）をＷＳから任意値書込み済みＷＰ（Ｂ１）に変更して書き込む必要があるので、extendで取得した任意値書込み済みブロックＢ２(ＭＳ)を上記任意値書込み済みＷＰ（Ｂ１）のリンク先ブロックＭＰ（Ｂ２）に変更する。この変更は、実質的に、extend処理で取得した任意値書込み済みブロックＢ２（ＭＳ）の位置を、書込み先ブロックＢ１（ＷＰ）に移動させたことを意味する。

（Ｗ２－３）図１７に示す通り、書込み先ブロックＢ１と初期化済みブロックＢ２とが異なるブロックで（S58のNO）、Ｂ１の種別がＭＰの場合（S59のMP）、書込み先ブロックＢ１（ＭＰ）のデータワードの値をextendで得た任意値書込み済みブロックＢ２（ＭＳ）に書き込んで（S62）、書込み先ブロックＢ１（ＭＰ）のリンク先ブロックＢ３（ＷＰ）と任意値書込み済みブロックＢ２（ＷＰ）間にリンクを張る（S63）。この結果、任意値書込み済みブロックＢ２（ＭＳ）はＭＳからＭＰに変更される。そして、書込み先ブロックＢ１に任意値を書込んで（S64）任意値書込み済みブロックＢ１（ＭＳ）とする。これによりextend処理で取得したブロックＢ２（ＭＳ）が実質的に書込み先ブロックＢ１（ＭＳ）に移動する。そして、書込み先ブロックＢ１（ＭＳ）がＭＳの場合と同様に値を書き込む（S52,S53）。すなわち、書込み先ブロックＢ１（ＭＳ）に書込み値V=[12,0]を書込み（S52）、unlink処理で意図しないリンクを切断する（S53）。

つまり、書込み先ブロックＢ１をＭＰから任意値書込み済みＭＳにして書き込む必要があるので、エクステンドで生成した任意値書込み済みブロックＢ２(ＭＳ)を、書込み先ブロックＢ１（ＭＰ）に代えて、ブロックＢ３（ＷＰ）のリンク先ＭＰに変更する。これにより、実質的に、extendで取得したブロックＢ２(ＭＳ)を、書込み先Ｂ１(ＭＳ)のリンク先だったＢ３(ＷＰ)のリンク先に変更し、書込み先ブロックＢ１を任意値書込み済みＭＳに変更してそのＢ１（ＭＳ）に値を書き込む。

［インデックスｉの要素にNULLを書込みwrite(i,NULL)］
図１８は、NULL書込みwrite(i,NULL)の制御を示すフローチャート図である。また、図１９は、NULL書込みの処理ＷＮ１を示す図である。図２０，２１，２２は、NULL書き込み処理ＷＮ２－１，ＷＮ２－２，ＷＮ２－３をそれぞれ示す図である。図２３，２４，２５は、NULL書込み処理ＷＮ３－１、ＷＮ３－２，ＷＮ３－３をそれぞれ示す図である。

ここでは、書込み先インデックスのブロックをＢ１、境界に隣接するＭ領域のブロック（以下、境界Ｍ側隣接ブロックと称する）をＢ２、Ｂ１のリンク先をＢ３、Ｂ２のリンク先をＢ４とそれぞれ称する。

NULL書込みは、書込み先ブロックが未書込みブロックＭＰ，ＷＳの場合、既にNULLを記憶した状態であるので特に処理を行う必要がない。

一方、書込み先ブロックが書込み済みブロックＭＳ、ＷＰの場合、境界をＭ領域側に１ブロックシフトしＷ領域を1ブロック増加するシュリンク処理と、書込み先ブロックについて、ＭＳをＭＰにまたはＷＰをＷＳに変更する処理が必要になる。

その場合、書込み先ブロックがＭＳの場合、書込み先ブロックＭＳをNULL記憶状態のＭＰに変更するための新たなリンクの生成処理が必要になる。一方、書込み先ブロックがＷＰの場合、書込み先ブロックＷＰをNULL記憶状態のＷＳに変更するために、書込み先ブロックＷＰと対応付けられているＭＰとのリンクの削除処理が必要になる。

さらに、境界Ｍ側隣接ブロックがＭＰの場合、シュリンク処理に対応して境界Ｍ側隣接ブロックＭＰと対応付けられているＷＰとの既存のリンクの処理が必要になる。

NULLの書込みは６種類の処理を有する。即ち、NULL書込みは、書込み先ブロックがＭＳの場合、Ｂ２がＢ１と同じ場合の処理ＷＮ２－１と、Ｂ２がＢ１と異なる場合で境界Ｍ側隣接ブロックＢ２がＭＳかＭＰかの２つの場合の処理ＷＮ２－２，ＷＮ２－３がある。さらに、NULL書込みは、書込み先ブロックがＷＰの場合、Ｂ２がＢ３と同じ場合の処理ＷＮ３－１と、Ｂ２がＢ３と異なる場合で境界Ｍ側隣接ブロックＢ２がＭＳかＭＰかの２つの場合の処理ＷＮ３－２，ＷＮ３－３がある。

図１８において、NULL書込みwrite(i,NULL)の呼び出しがあると、配列制御プログラムを実行中のプロセッサは、書込み先インデックスｉのブロックＢ１の種別を判別する(S71)。

（ＷＮ１）図１９に示されるとおり、書込み先のインデックスｉのブロックＢ１の種別が未書込みブロックＭＰまたはＷＳの場合（S71のMPまたはWS）、プロセッサは、何も行わない。即ち、書込み先ブロックＢ１（ＭＰ），Ｂ１（ＷＳ）は、未書込み状態であるので既にNULL状態である。したがって、プロセッサは特に書き込み処理を行わない。

（ＷＮ２）図１８のとおり、プロセッサは、書込み先ブロックＢ１の種別が書込み済みブロックＭＳまたはＷＰの場合（S71のMSまたはWP）、境界に隣接するＭ領域のブロックをＢ２と設定し(S72)、書込み先ブロックＢ１の種別がＭＳの場合(S73のMS)、以下のNULL書込みＷＮ２－１～ＷＮ２－３を実行する。

（ＷＮ２－１）図２０は、NULL書込み処理ＷＮ２－１を示す図である。図１８のとおり、プロセッサは、ブロックＢ２とＢ１が同じ場合(S74のYES)、書込み先ブロックＢ１のアドレスワードの値を自分のブロックのインデックス（図２０中インデックス「４」）に書き換えて意図しないリンクを削除し(S75)、境界を移動してＭ領域を1ブロック縮小する(S76)。この境界を移動する処理は、Ｍ領域を縮小するのでシュリンク（Shrink）処理と称する。２つの処理S75,S76の順番が逆でも良い。この結果、書込み先ブロックＢ１は未書込みブロックＷＳになるので、NULLが書込まれた状態になる。

このように、NULL書き込みは、境界をＭ領域側に移動してＭ領域を縮小する処理と、書込み先ブロックＢ１を未書込み状態ＭＰまたはＷＳにする処理である。つまり、後者の処理は、書込み先ブロックＢ１が最終的にＭ領域になるならＭＰにする処理で、Ｗ領域になるならＷＳにする処理である。以下のNULL書込みも同様である。

（ＷＮ２－２）図２１は、NULL書込み処理ＷＮ２－２を示す図である。図１８のとおり、NULL書き込み処理ＷＮ２－２は、書込み先ブロックＢ１が書込み済みブロックＭＳの場合(S73のMS)、さらに境界Ｍ側隣接ブロックＢ２と書込み先ブロックＢ１が異なる場合(S74のNO)、そして境界Ｍ側隣接ブロックＢ２がＭＳの場合(S77のMS)の処理である。書込み先ブロックＢ１（ＭＳ）を未書込みブロックＢ１（ＭＰ）にする必要があるので、Ｗ領域内にそのリンク先ブロックＷＰを取得する必要がある。

そこで、プロセッサは、境界を移動してＭ領域を１ブロック縮小する(S76：シュリンク処理)。さらに、境界Ｍ側隣接ブロックＢ２（ＭＳ）を書込み先ブロックＢ１（ＭＳ）のリンク先にするために、ブロックＢ２（ＭＳ）のアドレスワードの値「１」をブロックＢ１（ＭＳ）のデータワードに書込み（移動し） (S78)、ブロックＢ２（ＭＳ）とブロックＢ１（ＭＳ）のアドレスワードに互いのインデックス「２」「６」をそれぞれ書込み、ブロックＢ２，Ｂ１との間にリンクを形成する(S78)。その結果、書込み先ブロックＢ１は未書込みブロックＭＰになり、NULL状態になる。

（ＷＮ２－３）図２２は、NULL書込み処理ＷＮ２－３を示す図である。図１８のとおり、NULL書き込み処理ＷＮ２－３は、書込み先ブロックＢ１が書込み済みブロックＭＳの場合(S73のMS)、さらに境界Ｍ側隣接ブロックＢ２と書込み先ブロックＢ１が異なる場合(S74のNO)、そして境界Ｍ側隣接ブロックＢ２がＭＰの場合(S77のMP)の処理である。この場合も、書込み先ブロックＢ１（ＭＳ）を未書込みブロックＢ１（ＭＰ）にする必要があるので、Ｗ領域内にそのリンク先ブロックＷＰを取得する必要がある。

そこで、プロセッサは、境界を移動してＭ領域を１ブロック縮小する(S76：シュリンク処理)。さらに、境界Ｍ側隣接ブロックＢ２（ＭＰ）のリンク先ブロックＢ４（ＷＰ）を書込み先ブロックＢ１（ＭＳ）のNULL書込み後のリンク先にするために、ブロックＢ２（ＭＰ）のデータワードの値「８」をブロックＢ１（ＭＳ）のデータワードに書込み（移動し） (S80)、ブロックＢ１（ＭＳ）のアドレスワードにブロックＢ４（ＷＰ）のインデックス「１０」を書き込み（S80）ブロックＢ４（ＷＰ）とブロックＢ１（ＭＳ）のアドレスワードに互いのインデックス「１０」「２」をそれぞれ書込み、ブロックＢ４，Ｂ２との間にリンクを形成する(S80)。つまり、ブロックＢ２とＢ４間のリンクを、ブロックＢ１とＢ４間のリンクに置き換える。その結果、書込み先ブロックＢ１は未書込みブロックＭＰになり、NULL状態になる。

（ＷＮ３）図１８のとおり、プロセッサは、書込み先ブロックＢ１の種別が書込み済みブロックＭＳまたはＷＰの場合（S71のMSまたはWP）、境界に隣接するＭ領域のブロックをＢ２と設定し(S72)、書込み先ブロックＢ１の種別がＷＰの場合(S73のWP)、以下のNULL書込みＷＮ３－１～ＷＮ３－３を実行する。

（ＷＮ３－１）図２３は、NULL書込み処理ＷＮ３－１を示す図である。図１８のとおり、NULL書き込み処理ＷＮ３－１は、書込み先ブロックＢ１がＷＰの場合(S73のMP)で、境界Ｍ側隣接ブロックＢ２と書込み先ブロックＢ１のリンク先Ｂ３とが同じブロックの場合(S82のYES)の処理である。この場合、書込み先ブロックＢ１（ＷＰ）のリンクを解消してＷＳにする必要がある。

そこで、プロセッサは、書込み先ブロックＢ１のリンク先ブロックをＢ３に設定し(S81)、境界を移動してＭ領域を1ブロック縮小する(S76：シュリンク処理)。この結果、書込み先ブロックＢ１は未書込みブロックＷＳになるので、NULLが書込まれた状態になる。NULL書き込みの結果、Ｗ領域の書込み済みブロックＷＰが１つ減るので、シュリンク処理により境界Ｍ側隣接ブロックＭＰ（未書込みブロック）をＷＳに変更し、Ｂ１，Ｂ２間のリンクが削除され、ＷＰとＭＰの数が等しく保たれる。

（ＷＮ３－２）図２４は、NULL書込み処理ＷＮ３－２を示す図である。図１８のとおり、NULL書き込み処理ＷＮ３－２は、書込み先ブロックＢ１が書込み済みブロックWPの場合(S73のWP)、さらに境界Ｍ側隣接ブロックＢ２が書込み先ブロックＢ１のリンク先Ｂ３と異なる場合(S82のNO)、そして境界Ｍ側隣接ブロックＢ２がＭＳの場合(S83のMS)の処理である。この場合、書込み先ブロックＢ１（ＷＰ）を未書込みブロックＢ１（ＷＳ）にする必要があるので、ブロックＢ３（ＭＰ）のリンク先である書込み先ブロックＢ１（ＷＰ）の代わりに、新たにＢ３のリンク先ブロックＷＰを取得する必要がある。また、書込み先ブロックＢ１（ＷＰ）に対応付けられたブロックＢ２（ＭＰ）が存在する。

そこで、プロセッサは、書込み先ブロックＢ１のリンク先ブロックをＢ３に設定する(S81)。そして、プロセッサは、境界を移動してＭ領域を１ブロック縮小する(S76)。さらに、境界Ｍ側隣接ブロックＢ２（ＭＳ）をブロックＢ３（ＭＰ）の新たなリンク先にするために、ブロックＢ２（ＭＳ）のアドレスワードの値「１」をブロックＢ３（ＭＰ）のデータワードに書込み（移動し）(S84)、ブロックＢ３（ＭＰ）とブロックＢ２（ＭＳ→ＷＰ）のアドレスワードに互いのインデックス「２」「６」を書き込んで、ブロックＢ３，Ｂ２との間にリンクを形成する(S83)。即ち、プロセッサは、Ｂ３－Ｂ１間のリンクをＢ３－Ｂ２間のリンクに置き換えることで、書込み先ブロックＢ１をＷＳに変更し、NULL状態にする。そして、リンクが維持され、Ｗ領域のＷＰとＭ領域のＭＰの数も変更されない。

（ＷＮ３－３）図２５は、NULL書込み処理ＷＮ３－３を示す図である。図１８のとおり、NULL書き込み処理ＷＮ３－３は、書込み先ブロックＢ１が書込み済みブロックWPの場合(S73のWP)、さらに境界Ｍ側隣接ブロックＢ２が書込み先ブロックＢ１のリンク先Ｂ３と異なる場合(S82のNO)、そして境界Ｍ側隣接ブロックＢ２がＭＰの場合(S83のMP)の処理である。この場合、書込み先ブロックＢ１（ＷＰ）を未書込みブロックＢ１（ＷＳ）にする必要があり、ブロックＢ１とＢ３間のリンクが解消されるので、ＭＰブロックＢ３（ＭＰ）のリンク先である書込み先ブロックＢ１（ＷＰ）の代わりに、新たにＢ３のリンク先ブロックＷＰを取得する必要がある。また、境界Ｍ側隣接ブロックＢ２がＭＰでありシュリンク処理によりそのリンクが解消される。

そこで、プロセッサは、書込み先ブロックＢ１のリンク先ブロックをＢ３に設定する(S81)。そして、プロセッサは、境界を移動してＭ領域を１ブロック縮小し(S76)する。さらに、ブロックＢ１（ＷＰ）のリンク先Ｂ３と、境界Ｍ側隣接ブロックＢ２（ＭＰ）のリンク先Ｂ４との間に新たなリンクを形成するために、ブロックＢ２（ＭＳ）のデータワードの値「２」をブロックＢ３（ＭＰ）のデータワードに書込み（移動し） (S86)、ブロックＢ３（ＭＰ）とブロックＢ４（ＷＰ）のアドレスワードに互いのインデックス「１０」「２」を書き込んで、ブロックＢ３，Ｂ４との間にリンクを形成する(S86)。即ち、プロセッサは、Ｂ３－Ｂ１間のリンクを解消し、Ｂ２－Ｂ４間のリンクを解消し、Ｂ３－Ｂ４間のリンクを形成して、その結果、書込み先ブロックＢ１（ＷＰ）をＷＳに変更し、NULL状態にし、リンクを１つ減らして、Ｗ領域のＷＰとＭ領域のＭＰの数を等しく保つ。

［初期化、書込み、読み出しの具体例］
次に、初期化、書込み、読み出しを具体例に沿って説明する。以下の具体例では、通常データの書き込みでは、未書込みブロックＷＳに書込みして書込み済みブロックＷＰが１増加し双方向リンクも増加し、境界Ｗ側ブロックがＷＰの場合のエクステンドにより書込み済みブロックＷＰが１減少することを示す。また、エクステンドによりＭ領域が増加し、Ｗ領域が減少することを示す。さらに、Ｗ領域が少なくなると双方向リンクの数が減少し管理情報量が減少することを示す。そして、NULL書込みではシュリンク処理とリンクの変更により書込み済みブロックが未書込み状態に変更されてNULL状態になることを示す。

図２６は、配列ARの具体例と、初期化を示す図である。配列AR0は、配列の長さ１６、１要素（1ブロック）が２ワードを含む配列である。境界ポインタBD_Pの値「１２」により境界BDがインデックス１１と１２の間にあることが示される。したがって、配列の主領域の値は、境界ポインタの値が「０」の初期状態では不定値であり、境界ポインタの値が「０」より大きいと書込み済みブロックＭＳ、ＷＰ内の値は真の値であり、未書込みブロックＭＰ，ＷＳ内のデータはNULL状態である。また、ブロックの種別ＭＳ，ＭＰ，ＷＳ，ＷＰは実際に値が保存されているわけではない。ブロックの種別は、ブロックのインデックスｉ、境界ポインタBD_P、ブロック内のアドレスワードの値により定数時間で計算可能である。

初期化initialize(0)が呼ばれると、プロセッサは、配列AR1で、境界ポインタBD_Pの値を「０」に書き換える(図５のS1)。境界ポインタが「０」になるので、全てのブロックの種別は未書込みブロックＷＳ（NULL状態）になる。また、全インデックスの値は不定値となる。

図２７は、図１６で説明した書込みＷ２－２の具体例を示す図である。配列AR2は初期状態の配列AR1と同じである。配列AR2で、書込みwrite(4,[0,9])が呼ばれ、以下の通り、プロセッサがインデックス４のブロックに値[0,9]を書き込む。この書込みの場合、書き込むブロックの種別は未書込みブロックＷＳであり、境界BDに隣接するＷ領域のブロックの種別はＷＳである。

そこで、配列AR3では、プロセッサが、エクステンドextendにより境界ポインタBD_Pを「２」に書き換えて境界BDをシフトし、Ｍ領域内に任意値書込み済み（任意値「０、０」が書き込まれた）ブロックＭＳ（Ｂ２）を生成する(S57)。このエクステンドextendは図１１の処理Ｅ１である。また、任意値の書込みは省略可能である。さらに、配列AR4では、プロセッサが書込み先ブロックＢ１とブロックＭＳ（Ｂ２）との間に双方向リンクを作成し(S60)、書込み先ブロックＢ１のアドレスワードに書込み値「９」を、リンク先ブロックＢ１のデータワードに書込み値「０」をそれぞれ書込む（S55）。このように、境界BDに隣接するＷ領域のブロック以外の未書込みブロックＷＳへの書込みが発生すると、エクステンドで境界がシフトしてＭ領域が増加しＷ領域が減少し、双方リンクが１増加する。

図２８は、図１６で説明した書込みＷ２－２の具体例を示す図である。配列AR5(=AR4)で、書込みwrite(10,[8,0])が呼ばれてプロセッサがインデックス１０のブロックに値[8,0]を書き込む。この書込みの場合、書き込むブロックの種別は未書込みブロックＷＳであり、境界BDに隣接するＷ領域のブロックの種別はＷＳである。

そこで、配列AR6で、プロセッサが、エクステンドextendにより境界ポインタBD_Pを「４」に書き換えて境界BDをシフトし、Ｍ領域内に任意値書込み済ブロックＭＳ（Ｂ２）を生成する(S57)。このエクステンドextendは図１１の処理Ｅ１である。さらに、配列AR7では、プロセッサが書込み先ブロックＢ１と任意値書込み済ブロックＭＳ（Ｂ２）との間に双方向リンクを作成し(S60)、書込み先インデックス１０がＷＰであるので、書込み先ブロックＢ１のリンク先ブロックＢ２のデータワード(インデックス３)に書込み値「８」を書込み、書込み先ブロックＢ１のデータワードに書込み値「０」を書き込む（S56）。図２７と同様に、境界BDに隣接するＷ領域のブロック以外の未書込みブロックＷＳへの書込みが発生すると、境界がシフトしてＭ領域が増加しＷ領域が減少し、双方リンクが１増加する。

図２９は、図１６で説明した書込みＷ２－３の具体例を示す図である。配列AR8(=AR7)で、書込みwrite(2,[14,0])が呼ばれ、プロセッサがインデックス２に値[14,0]を書き込む。この書込みの場合、書き込むブロックの種別は未書込みブロックＭＰであり、境界BDに隣接するＷ領域のブロックの種別はＷＰである。

そこで、配列AR9で、プロセッサが、エクステンドextendにより境界ポインタBD_Pを「６」に書き換えて境界BDをシフトし、Ｍ領域内に任意値書込み済ブロックＭＳ（Ｂ２）を生成する(S57)。このエクステンドは図１２の処理Ｅ２である。さらに、配列AR10で、プロセッサが書込み先ブロックＢ１（ＭＰ）の値[10,8]を任意値書込み済ブロックＢ２（ＭＳ）に書込み(S62)、書込み先ブロックＢ１のリンク先ブロックＢ３（ＷＰ）のアドレスワードにＢ２のインデックス０を書き込んでブロックＢ２とＢ３との間に双方向リンクを変更する(S63)。また、書込み先ブロックＢ１に任意値を書き込んで任意値書込み済ブロックＭＳに変更する(S64)。その後、配列AR11で、プロセッサが書込み先ブロックＢ１に書込み値[14,0]を書込み（S52）、配列AR12で書込み先ブロックＢ１に生成された意図しないリンクを切断する(S53)。この場合、エクステンドextendによりＭ領域が増加しＷ領域が減少し、さらに書込み済みブロックＷＰが１減少し、双方向リンクも１減少している。

図３０は、図１６で説明した書込みＷ２－１の具体例を示す図である。配列AR13(=AR12)で、書込みwrite(6,[10,0])が呼ばれ、プロセッサがインデックス６の要素に値[10,0]を書き込む。この書込みの場合、書き込むブロックの種別は未書込みブロックＷＳであり、書込み先ブロックＢ１と境界Ｗ側ブロックＢ２とが同じブロックである。

そこで、配列AR14で、プロセッサが、エクステンドextendにより境界ポインタBD_Pを「８」に書き換えて境界BDをシフトし、Ｍ領域内に任意値書込み済ブロックＭＳ（Ｂ２）を生成する(S57)。このエクステンドは図１２の処理Ｅ１である。そして、配列AR14では、書込み先ブロックＢ１とエクステンドで生成した任意値書込み済ブロックＭＳ（Ｂ２）とが一致している(S58のYES)。そこで、配列AR15で、プロセッサが書込み先ブロックＢ１（ＭＳ）に値[10,0]を書込み（S52）、書込み先ブロックＢ１に意図しないリンクが発生しないことを確認する(S53)。この場合、エクステンドextendによりＭ領域が増加しＷ領域が減少し、しかし未書込みブロックＭＰと書込み済みブロックＷＰの数は不変で、双方向リンク数も不変である。

図３１は、図１６で説明した書込みＷ１の具体例を示す図である。配列AR16(=AR15)で、書込みwrite(4,[8,12])が呼ばれ、プロセッサがインデックス４のブロックに値[8,12]を書き込む。この書込みの場合、書き込むブロックの種別は書込み済みブロックＭＳである(S51のMS)。書込み済みブロックに書き込むので、エクステンドextendにより境界をシフトして任意値書込み済ブロックＭＳを生成する必要はない。

そこで、配列AR17で、プロセッサが書込み先ブロックＢ１（ＭＳ）に値[8,12]を書込む（S52）。この書き込みにより、書込み先ブロックＢ１にインデックス８のブロックとの間に意図しないリンクが発生している。そこで、配列AR18で、インデックス８に自身のインデックス８を書き込んで意図しないリンクを切断する(S53)。この場合、Ｍ領域とＷ領域の数は不変で、未書込みブロックＭＰと書込み済みブロックＷＰの数も不変、双方向リンク数も不変である。

以上のとおり、配列への書込みが繰り返されると境界が徐々にシフトしＭ領域が増加していく。初期化直後は双方向リンク数が少ないので、Ｍ領域のブロック数が少なくても少ない管理情報（双方向リンクの情報）を配列の主領域に保存することができる。その後、未書込みブロックＷＳへの書込みにより境界がシフトし徐々に双方向リンク数が増えるが、Ｍ領域のブロック数も増えるので増加する管理情報（双方向リンクの情報）を配列の主領域に保存できる。そして、境界がＷ領域の最大インデックスに近づいてくると、書込み済みブロックＷＰがエクステンドにより書込み済みブロックＭＳに変更されるなどにより双方向リンク数が減ってくる。その結果、Ｗ領域のブロック数が少なくても減少した管理情報を保存することができる。つまり、Ｍ領域の未書込みブロック数とＷ領域の書込み済みブロック数を管理するというハイブリッド的管理により、双方向リンクの最大数を抑制し、且つ合計書き込み数が少ないほど及び合計書き込み数が多いほど双方向リンクの数が少なく、配列内に双方向リンクの管理情報を保存することができる。

図３２は、読み出しreadの３種類の具体例を示す図である。配列AR19（＝AR18）で、読み出しread(0)が呼ばれ、プロセッサがインデックス１の値を読み出す。読み出し先ブロックの種別が未書込みブロックＭＰであるので(S21のMP)、プロセッサはNULLを読み出して返す（S22）。

配列AR20で、読み出しread(2)が呼ばれ、プロセッサがインデックス２のブロックの値を読み出す。読み出し先ブロックの種別が書込み済みブロックＭＳであるので(S21のMS)、プロセッサはインデックス２の値[14,0]を読み出して返す（S23）。

配列AR21で、読み出しread(8)が呼ばれ、プロセッサがインデックス８のブロックの値を読み出す。読み出し先ブロックの種別が未書込みブロックＷＳであるので(S21のWS)、プロセッサはNULLを読み出して返す（S22）。

図３３は、読み出しreadの１種類の具体例の具体例を示す図である。配列AR22（＝AR21）で、読み出しread(10)が呼ばれ、プロセッサがインデックス１０のブロックの値を読み出す。読み出し先ブロックの種別が書込み済みブロックＷＰであるので(S21のWP)、プロセッサは読み出し先ブロックＷＰのリンク先の未書込みブロックＭＰのデータワードの値「８」（インデックス１の値）と、読み出し先ブロックＷＰのデータワードの値「０」を読み出して返す（S25）。

図３４は、NULL書込みの具体例を示す図である。図３４では、NULL書込みwrite(10,NULL)が呼ばれる。したがって、書込み先ブロックＢ１はＷＰ、境界Ｍ側隣接ブロックＢ２はＭＳであり、Ｂ２とＢ１は異なるブロックであり、図２４のNULL書込みＷＮ３－２の処理が行われる。

プロセッサは、境界を移動してＭ領域を１ブロック縮小する(S76)。さらに、境界Ｍ側隣接ブロックＢ２（ＭＳ）をブロックＢ３（ＭＰ）の新たなリンク先にするために、ブロックＢ２（ＭＳ）のアドレスワードの値「１０」をブロックＢ３（ＭＰ）のデータワードに書込み（移動し） (S84)、ブロックＢ３（ＭＰ）とブロックＢ２（ＭＳ→ＷＰ）のアドレスワードに互いのインデックス「２」「６」を書き込んで、ブロックＢ３，Ｂ２との間にリンクを形成する(S83)。それにより、書込み先ブロックＢ１をＷＳに変更し、NULL状態にする。

図３６は、本実施の形態のNULL状態を記憶するための追加メモリ容量を示す図である。本実施の形態では、ｍビットの要素の場合、配列長Ｎ≦ 2^(m/2)までの配列を、境界値を記憶する追加領域m/2ビットでオプショナル配列に拡張できる。このオプショナル配列は、1要素が2^m種類の通常のデータと１つの特殊状態（NULL状態）とを持つことができる。但し、配列長が2^(m/2) より長い場合は、 2^(m/2) ごとに追加領域 m/2 bitを使用する。「^」はべき乗を意味する。

その理由は、要素がｍビットの場合、要素の小さい側のインデックスのアドレスワードがm/2ビットになるため、配列の要素数である配列長Ｎは最大で2^(m/2)までとなる。そこで、配列長が最大長2^(m/2)を超える場合は、配列長Ｎ＝2^(m/2)の配列を必要な数有し、配列毎に追加領域m/2ビットを有する。

図３６に示した例では、要素サイズｍが８ビット、配列長が１０００の場合、本実施の形態では配列長１６（=２^(8/2)）の配列を６３個（1000/16 = 62.5, よって 63個）有し、追加領域が６３個の配列毎に追加領域8/2ビット(4ビット)を有するので、追加領域は合計で63*4 = 252 bitとなる。

それに対して、フラグ方式は、配列長Ｎに対してＮビットの追加領域が必要である。すなわち、配列長１０００に対応して各要素に1ビットのフラグが必要となるので、追加領域は1,000ビットである。

また、エスケープ方式は、最悪でも全要素に「FF FF」、「FF 00」を書き込む必要があるので、各要素に8*2ビットを記憶するために、追加領域は8,000bitとなる。すなわち、エスケープ方式の場合は、ｍビットの要素、配列長Ｎの場合、最悪でｍ＊Ｎビットの追加領域が必要になる。

他の要素サイズ、他の配列長も同様にして算出できる。

AR：配置（Array）
BD：境界（Boundary）
BD_P：境界ポインタ（Boundary Pointer）
INT：初期値（Initial Value）
Ｍ：未書込みブロックを記憶するＭ領域、第１領域
ＭＰ：Ｍ領域の未書込みブロック
ＭＳ：Ｍ領域の書込み済みブロック
Ｗ：書込み済みブロックを記憶するＷ領域、第２領域
ＷＳ：Ｗ領域の未書込みブロック
ＷＰ：Ｗ領域の書込み済みブロック
EX_C：エクステンド完了フラグ
read：読み出し
write(i,V)：有効値書込み
write(i,NULL)：特殊値書込み
extend：エクステンド、エクステンド処理
initialize：初期化処理

Claims (12)

1. 少なくともアドレスワードとデータワードを含む２以上の定数個のワードをそれぞれ有する複数のブロックを連続して構成する配列を有し、前記配列の複数のブロックの二分割位置を示す境界を記憶し、前記二分割された第１領域内の未書き込みブロックの数と、前記二分割された第２領域内の書込み済みブロックの数とが同数になる位置を前記境界とするオプショナル配列を制御する処理をコンピュータに実行させる配列制御プログラムであって、
   前記処理は、
   前記第１領域の未書込みブロックまたは前記第２領域の未書込みブロックに対する有効値書込みが呼ばれると、前記境界を移動して前記第１領域を拡張し前記第１領域内に任意値書込済み書込みブロックを生成するエクステンド処理を行い、
   前記有効値書込みの書込み先ブロックが、前記エクステンド処理で生成した任意値書込済み書込みブロックと同じではなく、前記第２領域の未書込みブロックの場合、前記エクステンド処理で生成した第１領域の任意値書込済み書込みブロックのアドレスワードと、前記第２領域の前記書込み先ブロックのアドレスワードとに、互いのアドレスを記憶してリンクを形成し、
   前記第１領域の前記任意値書込済み書込みブロックのデータワードに前記有効値の一部分を書き込み、前記第２領域の前記書込み先ブロックのデータワードに前記有効値の残りの部分を書き込み、
   書込み先ブロックを前記第２領域の書込み済みブロックとする特殊値書込みが呼ばれると、前記境界を移動して前記第１領域を縮小するシュリンク処理を行って、前記境界に隣接する第１領域側の第１隣接ブロックを前記第２領域側に移動し、
   前記第１隣接ブロックが書込み済みブロックの場合、
   前記第１隣接ブロックのアドレスワードと、前記書込み先ブロックとリンクを形成する第１リンク先ブロックのアドレスワードとに、互いのアドレスを記憶してリンクを形成し、前記書込み先ブロックのリンクを解消して前記書込み先ブロックを未書込みブロックに変更し、
   前記第１隣接ブロックが未書込みブロックの場合、
   前記第１隣接ブロックとリンクを形成する第２リンク先ブロックのアドレスワードと、前記第１リンク先ブロックのアドレスワードとに、互いのアドレスを記憶してリンクを形成し、前記書込み先ブロックのリンクを解消して前記書込み先ブロックを未書込みブロックに変更する
   ことを有する配列制御プログラム。
2. 前記処理は、さらに、
   書込み先ブロックを前記第１領域の書込み済みブロックとする特殊値書込みが呼ばれると、前記シュリンク処理を行って、前記境界に隣接する第１領域側の第１隣接ブロックを前記第２領域側に移動し、
   前記第１隣接ブロックが書込み済みブロックの場合、
   前記第１隣接ブロックのアドレスワードと、前記書込み先ブロックのアドレスワードとに、互いのアドレスを記憶してリンクを形成し、前記書込み先ブロックを未書込みブロックに変更し、
   前記第１隣接ブロックが未書込みブロックの場合、
   前記第１隣接ブロックとリンクを形成する第２リンク先ブロックのアドレスワードと、前記書込み先ブロックのアドレスワードとに、互いのアドレスを記憶してリンクを形成し、前記書込み先ブロックを未書込みブロックに変更する
   ことを有する、請求項１に記載の配列制御プログラム。
3. 前記処理は、さらに、
   初期化が呼ばれると、全てのブロックが前記第２領域の未書込みブロックになるよう前記境界の位置を初期化することを有する、請求項１に記載の配列制御プログラム。
4. 前記処理は、さらに、
   読み出しが呼ばれると、
   読み出し先ブロックが未書込みブロックの場合、前記特殊値を返し、
   前記読み出し先ブロックが書込み済みブロックの場合、読み出し先の値を返すことを有する、請求項３に記載の配列制御プログラム。
5. 前記処理は、さらに、
   前記有効値書込みが呼ばれると、前記有効値書込みの書込み先ブロックを示すアクセス先インデックスと前記境界とに基づいて前記書込み先ブロックが前記第１領域のブロックかまたは第２領域のブロックかを判別し、前記書込み先ブロックが前記リンクを形成するか否かに基づいて前記書込み先ブロックが前記第１領域の未書込みブロックかまたは前記第２領域の書込み済みブロックかを判別することを有する、請求項１に記載の配列制御プログラム。
6. 前記処理は、さらに、
   前記リンクの形成を目的とせず前記第１領域の書込み済みブロックの値を書き換えた場合、前記第２領域の未書込みブロックのアドレスワードを、前記第１領域の書込み済みブロックとリンクが形成されないよう制御する非リンクすることを有する、請求項１に記載の配列制御プログラム。
7. 書込み先ブロックを前記第２領域の書込み済みブロックとする特殊値書込みが呼ばれると、
   前記第1隣接ブロックと前記書込み先ブロックとリンクを形成する第１リンク先ブロッ
   クとが同じブロックの場合、前記リンクを形成する処理を行わない、請求項１に記載の配列制御プログラム。
8. 書込み先ブロックを前記第１領域の書込み済みブロックとする特殊値書込みが呼ばれると、
   前記第1隣接ブロックと前記書込み先ブロックとが同じブロックの場合、前記リンクを
   形成する処理を行わない、請求項１に記載の配列制御プログラム。
9. 前記処理は、さらに、
   前記書込みの書込み先ブロックが、前記第１領域の未書込みブロックまたは前記第２領域の未書込みブロックであり、前記エクステンド処理で生成した任意値書込済み書込みブロックと同じ場合、前記書込み先ブロックに値を書込み、前記書込み先ブロックの不要なリンクを切断する非リンクを行うことを有する、請求項１に記載の配列制御プログラム。
10. 前記処理は、さらに、
    前記書込みの書込み先ブロックが、前記エクステンド処理で生成した任意値書込済み書込みブロックと同じではなく、前記第１領域の未書込みブロックの場合、
    前記書込み先ブロックである前記第１領域の未書込みブロックの値を、前記エクステンド処理で生成した前記第１領域の任意値書込済み書込みブロックに書込んで、前記書込み先ブロックである前記第１領域の未書込みブロックのリンク先の第２領域の書込み済みブロックと前記エクステンド処理で生成した前記第１領域の任意値書込済み書込みブロックとの間にリンクを生成し、前記書込み先ブロックである前記第１領域の未書込みブロックに前記有効値を書き込むことを有する、請求項１に記載の配列制御プログラム。
11. 少なくともアドレスワードとデータワードを含む２以上の定数個のワードをそれぞれ有する複数のブロックを連続して構成する配列を有し、前記配列の複数のブロックの二分割位置を示す境界を記憶し、前記二分割された第１領域内の未書き込みブロックの数と、前
    記二分割された第２領域内の書込み済みブロックの数とが同数になる位置を前記境界とするオプショナル配列を制御する配列制御方法であって、
    前記第１領域の未書込みブロックまたは前記第２領域の未書込みブロックに対する有効値書込みが呼ばれると、前記境界を移動して前記第１領域を拡張し前記第１領域内に任意値書込済み書込みブロックを生成するエクステンド処理を行い、
    前記有効値書込みの書込み先ブロックが、前記エクステンド処理で生成した任意値書込済み書込みブロックと同じではなく、前記第２領域の未書込みブロックの場合、前記エクステンド処理で生成した第１領域の任意値書込済み書込みブロックのアドレスワードと、前記第２領域の前記書込み先ブロックのアドレスワードとに、互いのアドレスを記憶してリンクを形成し、
    前記第１領域の前記任意値書込済み書込みブロックのデータワードに前記有効値の一部分を書き込み、前記第２領域の前記書込み先ブロックのデータワードに前記有効値の残りの部分を書き込み、
    書込み先ブロックを前記第２領域の書込み済みブロックとする特殊値書込みが呼ばれると、前記境界を移動して前記第１領域を縮小するシュリンク処理を行って、前記境界に隣接する第１領域側の第１隣接ブロックを前記第２領域側に移動し、
    前記第１隣接ブロックが書込み済みブロックの場合、
    前記第１隣接ブロックのアドレスワードと、前記書込み先ブロックとリンクを形成する第１リンク先ブロックのアドレスワードとに、互いのアドレスを記憶してリンクを形成し、前記書込み先ブロックのリンクを解消して前記書込み先ブロックを未書込みブロックに変更し、
    前記第１隣接ブロックが未書込みブロックの場合、
    前記第１隣接ブロックとリンクを形成する第２リンク先ブロックのアドレスワードと、前記第１リンク先ブロックのアドレスワードとに、互いのアドレスを記憶してリンクを形成し、前記書込み先ブロックのリンクを解消して前記書込み先ブロックを未書込みブロックに変更する
    ことをコンピュータが実行する配列制御方法。
12. 少なくともアドレスワードとデータワードを含む２以上の定数個のワードをそれぞれ有する複数のブロックを連続して構成する配列を有し、前記配列の複数のブロックの二分割位置を示す境界を記憶し、前記二分割された第１領域内の未書き込みブロックの数と、前記二分割された第２領域内の書込み済みブロックの数とが同数になる位置を前記境界とするオプショナル配列を記憶する記憶装置と、
    前記記憶装置にアクセス可能なプロセッサとを有し、
    前記プロセッサは、
    前記第１領域の未書込みブロックまたは前記第２領域の未書込みブロックに対する有効値書込みが呼ばれると、前記境界を移動して前記第１領域を拡張し前記第１領域内に任意値書込済み書込みブロックを生成するエクステンド処理を行い、
    前記有効値書込みの書込み先ブロックが、前記エクステンド処理で生成した任意値書込済み書込みブロックと同じではなく、前記第２領域の未書込みブロックの場合、前記エクステンド処理で生成した第１領域の任意値書込済み書込みブロックのアドレスワードと、前記第２領域の前記書込み先ブロックのアドレスワードとに、互いのアドレスを記憶してリンクを形成し、
    前記第１領域の前記任意値書込済み書込みブロックのデータワードに前記有効値の一部分を書き込み、前記第２領域の前記書込み先ブロックのデータワードに前記有効値の残りの部分を書き込み、
    書込み先ブロックを前記第２領域の書込み済みブロックとする特殊値書込みが呼ばれると、前記境界を移動して前記第１領域を縮小するシュリンク処理を行って、前記境界に隣接する第１領域側の第１隣接ブロックを前記第２領域側に移動し、
    前記第１隣接ブロックが書込み済みブロックの場合、
    前記第１隣接ブロックのアドレスワードと、前記書込み先ブロックとリンクを形成する第１リンク先ブロックのアドレスワードとに、互いのアドレスを記憶してリンクを形成し、前記書込み先ブロックのリンクを解消して前記書込み先ブロックを未書込みブロックに変更し、
    前記第１隣接ブロックが未書込みブロックの場合、
    前記第１隣接ブロックとリンクを形成する第２リンク先ブロックのアドレスワードと、前記第１リンク先ブロックのアドレスワードとに、互いのアドレスを記憶してリンクを形成し、前記書込み先ブロックのリンクを解消して前記書込み先ブロックを未書込みブロックに変更する配列制御装置。

Images