JPS62194554A - メモリ内容管理方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、ワードプロセシングなどに代表される文字列
データを編集するためのメモリ内容管理方式に係り、特
にデータの挿入や削除、およびファイルの更新に要する
処理時間を短縮するためのメモリ内容管理方式に関する
。

〔従来の技術〕

一般にワードプロセシング機能は、書き込み／読み出し
可能な外部記憶装置に蓄えられた文字列データを修正す
るためのものである。しかしながら、その実現方式とし
て、データの挿入・削除によって生じるデータの移動を
外部記憶装置上のデータに対して直接に行うことは、Ｒ
／Ｗベッドの移動など機械系統の動作が頻繁に発生する
ことになり、応答性能の面で実用的なものにならない。

そこで、従来の装置では、外部記憶装置から編集対象と
なる範囲の文字列データの写しを主記憶装置上に取り出
し、この上で編集を行って、編集が終了するときや別の
範囲に対する編集を行おうとするとき、編集の加えられ
た主記憶上のデータを外部記憶装置上の元の場所に書き
込むようにしている。なお、この種の技術は、例えば、
雑誌ｒｂｉｔＪにおいて連載された汎用エディタＳＰＥ
が挙げられる（連載「エディタを作ろう」：　ｂ　ｉ　
ｔＶｏｌ、１６．Ｎｎ１ｌ−）ｋｉ１３　Ｖｏｌ、１７
．Ｎａ１−Ｎａ５）。

〔発明が解決しようとする問題点〕

従来方式の多くは、外部記憶装置および主記憶上の文字
列データを一次元的に偏成するものであり、このため、
データの挿入・削除によって生じるデータの移動は、主
記憶上の文字列データに対して広域的に行われ、さらに
、この主記憶上のデータを外部記憶上に格納する段階に
おいても、外部記憶装置上のデータ移動が広域的に行わ
れることになり１機械系統の動作の発生頻度は軽減され
るものの、やはり時間を要するものであった。

本発明の目的は、従来方式に比べ、より高速なワードプ
ロセシングを可能とするメモリ内容管理方式を提供する
ことにある。

〔問題点を解決するための手段〕

上記目的を達成するために、本発明のメモリ内容管理方
式では、外部記憶領域に格納されている文字列データの
中から、編集対象とする範囲の文字列データを読み出し
、主記憶領域に格納するステップと、上記主記憶領域を
複数のメモリブロックと分割し、各ブロック毎に、そこ
に格納された文字列データの長さと、該文字列データの
繋がりに従ったブロック間の接続関係を示す管理情報を
記憶するステップと、上記主記憶領域に格納された文字
列データに対して更新および削除処理を加えるステップ
と、上記更新および削除による状態変化の有無を上記ブ
ロック毎に記憶すると共に上記管理情報を更新するステ
ップと、上記状態変化のあったブロックに対応する上記
外部記憶領域上の文字列データに対して、上記主記憶領
域の内容に従ったデータ書き換え処理を施すステップと
を有することを特徴とする。

〔作用〕

本発明によれば、基本的に、外部記憶領域上の文字列デ
ータの一部を主記憶領域上に置くという点で公知技術を
踏襲しながらも、データの更新。

挿入、削除によって生じるデータの移動範囲を局所化し
ているため、これによって、処理時間の向上を実現でき
る。

〔本発明の実施例〕

以下、本発明の実施例を図を用いて説明する。

第１図は、ワードプロセシング機能を実現する典型的な
システム構成を示したものである。

図において、１０１は主記憶装置１０２に格納されたプ
ログラムに従ってデータ処理動作を行う処理装置、１０
３は外部記憶装置１０４に対するデータの入出力を制御
するための外部記憶制御装置、１０５はキーボード１０
６を制御するための装置、１０７はＣＲＴディスプレイ
１０８に対する表示制御を行うディスプレイ制御装置で
ある。

主記憶袋［１０２上には、データの他に、例えばオペレ
ーティングシステム（以下Ｏ８と略す）１０９、および
ワードプロセシングプログラム（以下ＷＰと略す）１１
０が格納されている。ここで、０３１０９はシステム規
模に応じた各種の制御機能を備えるが、本実施例におい
ては、○５１０９は少なくとも、システムに接続されて
いる各種デバイス１０３〜１０８の制御プログラムと。

書き込み・読み出し可能な外部記憶装置１０３゜１０４
に対して、レコード単位での入出力を可能とする制御プ
ログラム（よく知られた［相対編成ランダムアクセス」
を可能としたもの）を具備しているものとする。尚、こ
れら２つの制御プログラムは、いずれも公知のものであ
り、○５１０９の具備機能としてではなく、ＷＰＩＩＯ
が具備するものとして用意してもよい。

次に、本発明によるメモリ管理方式の基本的な考え方に
ついて述べる。

ワードプロセシング機能の編集対象である文字列データ
の管理としては、大別すると次の２種のものがある。

第１のものは、ロール紙方式と称されるものであり、無
限に長い紙のうえに文字が巴かれるという考え方に立脚
したデータ管理方式である。よく知られたプログラムエ
ディタなどが、これに相当する。

第２のものはカット紙方式と称されるもので、１枚の紙
の単位で文字が置かれ、これらの紙を１列に並べること
で、全体の文書が完成されているという考え方に立脚し
たデータ管理方式である。

この方式は、ワードプロセッサなどの文書編集機能にお
いて採用されている。

これら２つの方式のデータ管理上の具体的に相違点は、
カット紙方式では紙（ページと呼ぶ）という管理単位が
存在し、ロール紙方向にはそのようなものは存在しない
という点である。本発明によるメモリ管理方式は、上記
カット紙方式に関するものである。

第２図は、第１図で示した外部記憶装置１０４上に文字
列データの並びを相対編成ファイルとして編成したとき
のデータ管理形式を説明するための図である。同図から
明らかなように、ファイルは、文字列データを格納する
ためのレコード群２０３と、これらを管理するためのレ
コード群２０１．２０２とから成り、すべてのレコード
には、他のレコードと区別するためのレコード番号が付
与されている。ここでレコード番号の付与とは、各レコ
ードの中にそれを表す値を実際に書き込むことではなく
、先述の０３１０９の機能により、成るレコード番号を
指定して入出力動作を起こさせるとき、その対象となる
レコードがファイルの中で一意的に決められ、かつ、同
じレコード番号を指定するならば、常に同じレコードと
対応づけてできるようにしておくことを意味する。

本発明において、文字列のデータレコード２０３は、「
ページ」と呼ぶ管理単位に分けて管理される。具体的に
は、ページ管理レコードと称する管理レコード２０２が
用意され、この上に当該ページに含まれる各データレコ
ードのレコード番号が書き込まれる。さらに該ファイル
全体に渡り存在するページを管理するため、言い換えれ
ばページ管理レコードを管理するために、ファイル管理
レコードと称するレコード２０１が用意される。この管
理レコードには、複数のページ管理レコードのレコード
番号がページの上昇順に格納される。また、１つの管理
レコードで管理することができる上限値よりもページの
数が多いような場合に対処するために、ファイル管理レ
コード２０１は複数個用意され、各々をポインタでつな
ぐようにしである。この場合のポインタは、前方及び後
方にくるファイル管理レコードを示すレコード番号であ
り、これらのポインタは該ファイル管理レコードの所定
のフィールドに書き込まれる。

尚、ファイル管理レコードの連鎖において、先頭にくる
ファイル管理レコードのレコード番号は、予め決められ
た値（例えば”０″）に設定され、これにより上述のよ
うにレコード番号を手掛かりとして行う検索の最初の手
掛かりが与えられるようになっている。

第３図は、主記憶装置１０２上に置かれるＷＰのデータ
部のうち１本発明の構成要件となる編集バッファ３０１
と状態テーブル３０３の２種類のデータを示している。

編集バッファ３０１は、それぞれが１バイトである記憶
単位を２次元配列して構成される。２次元配列は、高級
言語（例えば、ＦＯＲＴＲＡＮ　）の文法に従って定義
することが可能であり、言語プロセッサ（コンパイラ）
の働きによって、実際のメモリ確保が行われる。この２
次元配列において、各要素のアドレスが連続する方向の
１つの列を「ブロック」３０２と定義すると、この−２
次元配列は、複数のブロック集まりからなる。この場合
、各ブロックのサイズを大きく取ると、ファイルアクセ
スの回数が減る反面、ブロック内でのメモリ使用効率、
即ち、ブロック長とブロック内での有効データ長との比
が悪くなり、小さく取ると、その逆の性質となるため、
これら２種の因子の双方を極端に劣化させない値、例え
ば前述のファイルにおけるレコード長と一致した値にブ
ロック長を定める。また、ブロックの個数は、１ページ
に格納される文字列データの情報量として、ワードプロ
セシング業務に支障をきたさない範囲の容量確保が行え
るような値とする。いずれにしても、これまでに述べた
ブロック長と個数は、ワードプロセシング機能の設計段
階において、その値を決めるものであり、ワードプロセ
シング機能の実行特番二番よ、すでに与えられた値とし
て、途中変更することなく処理していくものである。

このようなブロック構造において、文字列データは以下
のように管理される。すなわち、一般しこ文字列データ
は一次元的に連続するため、この文字列データを各々が
１つのブロックに入るような長さに分割する。各ブロッ
クには、この分割された文字列データが格納され、ブロ
ックの中に格納された文字列データの長さが処理される
。また、文字列データの一次元的な並びに従って、分割
格納したブロックのつながりも管理される。

一方、状態テーブル３０３は、各ブロック対応に異なる
値を取り得るようにした１次元配列であり、各ブロック
に対してどのような変更が行われたかを４種類の状態に
集約して管理するものである。これ６４種類の状態は、
それぞれ他の状態と区別するための固有の値（状態値と
呼ぶ）で表わされる。また、これらの状態値は、ワード
プロセシング機能において、例えば、あるブロック上の
データに対する編集操作が行われるときなどの機会に、
参照／更新され、また、編集バッファに対して行われた
編集操作をファイルに反映（出力）する際に、その対象
となるブロックが（新規に使われたものか、あるいは内
容の変更のあったものか等の識別のために用いられる。

本実施例において、上記４種の状態の意味と各状態値は
以下の通りである。

（１）未使用ブロック（００） （２）ファイルからロードされた後、何の更新もおこな
われていないブロック（１０） （３）新規に使われたか、あるいはファイルからロード
された後、更新の行われたブロック（１１）（４）ファ
イルからロードされた後、編集によって削除されたブロ
ック（ｏｌ） 次に、前述した主記憶装置上および外部記憶装置上のデ
ータの編成法をもとに、ワードプロセシング機能の典型
的な処理を解説し、本発明の特徴であるデータ移動の影
響範囲の局所化について、その実現方式を開示する６ワ
一ドプロセシング機能の典型的な処理としては、（１）
ページ取り出し、（２）データ挿入、（３）データ削除
、（４）ページ格納、の４種をとりあげ、フローチャー
トを参照して説明する。ここで、開示する範囲は、編集
バッファ、状態テーブル、およびファイルに対する操作
に焦点を絞ったものにとどめ、他のキー人力処理、画面
表示処理などは、本発明と直接関係しないため省略する
ことにする。

第４図は、ページ取り出しのための処理フローチャート
である。本処理への入力パラメータは、編集対象とする
ファイルの名称と、そのファイル内のページの番号であ
る。まず、テーブル類の初期化のために、状態テーブル
の各要素に対して。

状態値として「００」を書き込む。（ステップ４０１）
。

次に指定ファイルの内容を検索し、指定ページ番号に該
当するページ管理レコードを読み出す（ステップ４０２
，４０３）。その結果、ページ管理レコードの上に管理
されたデータレコードのレコード番号の一覧が入手され
る。このレコード番号列をもとに、そのレコードの内容
を順次読み出し、編集バッファの先頭ブロックから順次
格納していくとともに、状態テーブルの該ブロックに関
する状態値を「１０」として設定していく（ステップ４
０４）。

以上の読み出し動作がすべて終了すれば、最後に読み出
したデータレコードの総数を一時的な格納場所に登録す
る（ステップ４０５）。この値は、後述するページの格
納処理の中で使用される。

第５図は、データ挿入のための処理フローチャートであ
る。今、挿入データの長さをＮ、ブロック長さをＢ、ブ
ロック上のそれまでに書かれたあるデータの長さをＬと
し、挿入位置を該ブロック上のデータの先頭からの位置
で表して符号Ｐで示すことにする。

まず、ステップ５０１でＮ、Ｂ、Ｌ、Ｐ値を設定し、第
一段階の判定として、当該ブロック上に挿入データが入
りきるかを、下式により判定する（ステップ５０２）。

Ｎ＋Ｌ≦Ｂ　　　　　　　　　　　　　　・・・・・・
（１）これが成立するならば、該ブロックにデータが格
納可能であり、他のブロック・には影響を与えないこと
を示している。そこで、Ｐバイト目よりＬバイト目まで
のデータを現在位置よりＮバイト後に移動しくステップ
５０３）、その結果空けられた場所に挿入データＮバイ
トを書き込む（ステップ５０４）。この後、当該ブロッ
クに変更が起こったことを示すために、上記ブロックに
対応する状態テーブルの内容を１例えば「１１」という
値に設定しくステップ５０５）、この処理を終了する。

また、式（１）が成立しない場合は、当該ブロックには
データは入りきらないこと、すなわち新たな空きブロッ
クが必要となることを示している。

そこで、必要とされる空きブロックの数Ｅを、下式によ
り求める（ステップ５０６）。

Ｅ＝　（Ｎ＋Ｌ）／Ｂ　　　　　　　　・・・・・・（
２）但し、式（２）における記号“／″は、除算の商だ
けを求める演算子を意味している。

必要とされるＥ個の空きブロックは、編集バッファ上の
各ブロックの状態値を順次参照し、その値が「Ｏｏ」あ
るいは「０１」のものをＥ個見付は出すことにより用意
される（ステップ５０７）。

次にステップ５０８で、挿入の対象となったブロックと
用意された空きブロック（計Ｅ＋１個）の中で、Ｎ＋Ｌ
バイトのデータを、平均的に配置するようにする６また
。これらＥ＋１個のブロックの間に、文字列の並びに従
ったブロックのつながりを定義する（ステップ５０９）
。これらＥ＋１個のブロックは、いずれも内容に変更が
あったため、ステップ５１１で当該ブロックに対応する
状態値を「１１」と設定した後、この処理を終了する。

第６図は、データ削除のための処理フローチャートであ
る。データ削除処理では、削除する範囲として開始点と
終了点の２点を指定し、その範囲の文字列データを消去
し、以降に続く文字列を前に詰める。開始点、終了点の
指定は、ステップ６０１に示すように、いずれも編集バ
ッファ上のブロックと、そのブロックの中での文字列デ
ータのバイト位置により指定されるものとし、開始点の
位置は終了点の位置よりも小さいものとする。

この場合、上記２点が同じブロック内の位置を示すとき
、そのブロックの中だけで変更が行われることを意味し
ているため、指定範囲の文字列データを削除し、ブロッ
ク内の残りの部分を前に詰めるようにすればよい。また
、この場合も、当該ブロックに内容の変更が生じたこと
を示すために、状態値として「１１」を設定して処理を
終了する（ステップ６０２〜６０５）。

尚、上記のデータ消除処理において、特に削除開始位置
が当該ブロック内の先頭バイト位置を示し、かつ削除終
了位置が当該ブロック内の最終バイト位置を示している
ような場合、本削除処理の実行の結果、当該ブロックは
文字列データを全く持たないブロック（削除ブロックと
称する）となってしまう。このような場合には、ブロッ
クの状態値を「０１」とし、ブロック間のつながりも当
該ブロックを飛ばすように更新しておく（ステップ６０
６，６０７）。

次に、削除範囲が２つ以上のブロックにまたがって設定
された場合の処理について述べる。

今、削除開始位置に該当したブロックの先頭から削除開
始バイト位置までの長さをＦ、削除終了位置に該当した
ブロック中の削除終了バイト位置から当該ブロックの文
字列データの最終バイトまでの長さを、Ｒ，ブロック長
をＢと定義すると。

更新するブロックの数を最小限にとどめてＦとＲを格納
するのに必要な最小限のブロック数Ｍを求めると、次式
のようになる。

Ｍ＝↑（（Ｆ＋Ｒ）÷Ｂ）　　　　・・・・・・（３）
但し、記号″↑″は、小数点以下の切り上げを意味する
。

従って、削除前の状態で削除開始位置から終了位置まで
に使用されていたブロック数をＵとすると、このＵ個の
連続ブロックのうち、後方から（Ｕ−Ｍ）個のブロック
は不用なブロックとなるため、これらの該ブロックの状
態値を「０１」として削除ブロックであることを表示す
るとともに、それまでに設定されていたブロック間のつ
ながりも消去するようにすればよい（ステップ６０８〜
６１１）。

また、結果的に残ったＭ個のブロックに対しは、データ
挿入の場合と同様に、Ｆ＋Ｒバイトのデータを平均的に
配置しくステップ６１２）、これらのブロックに対して
は、内容に変更があったことを表示するために、当該ブ
ロックに対応する状態値を「１１」に設定して処理を終
了する（ステップ６１４）。

第７図は、ページ格納のための処理フローチャートを示
す。ステップ７０１，７０２ではブロックの状態判定の
ための各種パラメータを設定する。

編集バッファの内、前半の部分はファイルから読み出し
たものである。但し、ここで言う「前半の部分」とは、
先述のページ読み出しで求められた「読み出しデータレ
コード総数」の個数（Ｎ）分に該当する。この範囲のブ
ロックに対して状態値の判定を行い、もし状態値が「１
０」であれば、（ステップ７０５）、ファイルからロー
ドした内容に変更が生じなかったことを示しているため
、このブロックをファイルに格納する必要はない。

もし、状態値が「１１」であれば（ステップ７０６）、
ファイルからロードした後に、何んらかの内容変更がな
されたことを示しているため、ファイル上の元のレコー
ドの内容をこのブロックの内容と置き換える（ステップ
７０７）。さらに。

状態値が「０１」であれば、（ステップ７０８）、ファ
イルからロードされた後、編集操作によって該ブロック
が削除されたことを示しており、ファイル上の対応する
レコードをファイルから削除する（ステップ７０９）、
尚、状態値「００」は、上記範囲のブロックに対しては
設定されないこと明らかであり、判定から除外しても構
わない。つぎに、「読み出しデータレコード総数」の示
す値よりも大きいブロックについて、その状態値を調べ
ていく。この範囲のブロックは、ファイルからロードさ
れたものでなく１編集操作の過程において、新たに加わ
ったブロックであるため、これらのブロックは、ファイ
ルに対して新たなデータレコードとして追加して書き込
む必要のあるものである。その対象となるブロックは、
状態値が「１１」となっているものである（ステップ７
１１．７１２）。

〔発明の効果〕

以上の説明から明らかな如く、本発明は４ワ一ドプロセ
シング機能において要請される文字列データの挿入・削
除の処理において、それらの処理過程で発生するデータ
移動の対象範囲を局所化することができるため、対象デ
ータ量が限定された分だけ処理速度を向上することが可
能となる。

【図面の簡単な説明】

第１図は典型的なワードプロセシング機能を備えたシス
テムの構成を示すブロック図、第２図は外部記憶装置上
のファイルのデータ管理形式を説明するための図、第３
図は主記憶上のデータ管理形式を説明するための図、第
４図〜第７図は本発明による典型的なワードプロセシン
グ機能の処理冨１図 第　２　図 ３ρｌ 篤　〆　図 １７　　固

Claims (1)

【特許請求の範囲】
1. １、外部記憶領域に格納されている文字列データの中か
   ら、編集対象とする範囲の文字列データを読み出し、主
   記憶領域に格納するステップと、上記主記憶領域を複数
   のメモリブロックに分割し、各ブロック毎に、そこに格
   納された文字列データの長さと、該文字列データの繋が
   りに従つたブロック間の接続関係を示す管理情報を記憶
   するステップと、上記主記憶領域に格納された文字列デ
   ータに対して更新および削除処理を加えるステップと、
   上記更新および削除による状態変化の有無を上記ブロッ
   ク毎に記憶すると共に上記管理情報を更新するステップ
   と、上記状態変化のあつたブロックに対応する上記外部
   記憶領域上の文字列データに対して、上記主記憶領域の
   内容に従つたデータ書き換え処理を施すステップとを有
   することを特徴とするメモリ内容管理方式。