[Glue!] 簡易データベース・ユーティリティ


GlueLogic の API は簡易データベースのごく簡単な実装である、 dictionary と名付けたデータ構造と一連の操作関数を提供し、 これを用いてアプリケーション・プログラムとのインタフェースを行なっている。 これらを使うと、 GlueLogic サーバが行なっているような、 名前とその値との管理を容易に行なうことができる。
以下に簡単な使い方を示すが、詳細は API 仕様またはソースコードを参照して頂きたい。

dictionary に関連するデータ構造

概要

dictionary では二つのデータ構造を定義している。 一つは dictionary の基礎となるデータ構造で、これを用いてその dictionary に属するデータ項目を管理している。 もう一つは dictionary に属する一つひとつのデータ項目を管理するもので、データ項目ごとのキーとその値、および管理情報を含む。 dictionary を操作する関数はすべて、最初の引数として dictionary の基礎となるデータ構造を取ることにより、 これらを扱うアプリケーション・プログラムは同時に複数の dictionary を維持し、操作することができる。

キーはハッシュ関数によって 32 bit のハッシュ値に圧縮され、 データ項目はそのハッシュ値の modulo によって 2 の累乗個のリニア・リストに分割されて管理される。
これらのリニア・リストの始点はひとつの配列に保管され、 さらにこの配列自体は初期化の際に malloc 関数によって領域を確保されて、 dictionary の基礎となる構造からポインタによって指示される。 この配列の大きさは、最初に初期化する時に決定され、その後変更することはできない。

値の管理

キーは任意の長さの通常の文字列で表現され '\0' 文字で終端される。 dictionary 内部では引数に与えられた文字列は必要に応じてコピーされ、 引数に与えられたポインタが指している文字列が変更されても、 dictionary の持つ値には影響を与えない。

キーの値は任意のデータ構造であるが、実際に dictionary が管理するのはその構造を指すポインタそのものである。 このため、このポインタが指しているデータ構造が直接書き換えられた場合には、必然的にキーの値も変化することになる。 これが望ましくない場合には、 dictionary に値を与える前に、 ユーザの責任でポイントされているデータ構造のコピーを行なう必要がある。
この場合、たとえばキーの値を通常の文字列で保持するのであれば、 dictionary に値を与える前に strcpy 関数や strdup 関数などを用いてコピーを行なうことになるが、 strdup 関数を使ってコピーする場合にはこのコピー関数がメモリの割当を伴うものであるため、 値を書き換えるたびにそれまでの古い値を保持していた領域を解放することも、 ユーザの責任で確実に行なわなければならない。
一方、キーの値が static なメモリ領域に存在する変数で保持される場合には、 このようなメモリ空間の管理を行なう必要は無くなる。


dictionary の初期化

dictionary の初期化は NewDictionary 関数によって行なわれる。 初期化を行なっていない dictionary に対して操作を行なった場合、その結果がどのようになるかは予想できない。
この関数に与える第二引数はその dictionary が保持するであろう最大のデータ項目数であり、 その値は 2 の累乗に切り上げられてリニア・リストの数として用いられる。 しかし、このようなパラメータの決定の方法は速度を最適化する必要がある場合のものであって、 アクセスの速度が遅くてもメモリの利用効率を良くしたいという場合であれば、 その dictionary が保持するであろう最大のデータ項目数の数分の一を指定すれば良い。

実行効率とメモリ利用効率

もしも dictionary に収容されているデータ項目数が、dictionary の持つリニア・リストの数より充分少ない場合には、 リニア・リストの長さがほとんどのものについて 1 以下になり、良好なアクセス速度をもたらすことが予想される。 しかし、リニア・リストの始点を管理する配列のうち有効なエントリの割合が低下して、メモリ空間の利用効率は低下する。

一方、dictionary に収容されているデータ項目数が、dictionary の持つリニア・リストの数の数倍になると、 リニア・リストの長さが長くなってリスト内の探索が増え、アクセス速度の若干の低下を招く。 しかしこの場合でも、 dictionary の論理的な動作には全く影響は無く、 リニア・リストの始点を管理する配列はほとんど全てが有効なエントリとなって、メモリの利用効率は 100% に近付く。

このどちらを選ぶかはその dictionary が保持するデータの性質に依存するものであり、 一概にどちらが良いと決定できるものではない。


データ項目の書き込み

データ項目の書き込みには AssignDict 関数を用いる。 この関数は引数として dictionary の指定と、キー文字列へのポインタ、および値へのポインタを取る。
もしもこの関数が呼ばれた時点で、指定されたキーを持つデータ項目が既に登録されていなければ、 新しいデータ項目を管理するデータ構造が新規に作られて、その値が書き込まれる。

書き込みが成功し、そのキーが既に値を与えられていた場合には、以前の値がこの関数の戻り値として戻される。 この値はユーザが記憶領域の管理を行なっている場合には必須のもので、 そのデータの占める領域が他のどこからも参照できなくなる場合には、その領域を解放しなければならない。
また、新しいデータ項目が新規に作成された場合には、この関数は NULL を返す。 しかし、 AssignDict 関数が NULL を返したからと言って、 このデータ項目が新規に作成されたとは限らない。 古いデータ項目が、値として NULL ポインタを持っていたという可能性もあるからである。


データの参照

データの参照には RetrieveDict 関数を用いる。 この関数は引数として dictionary の指定と、キー文字列へのポインタを取る。
この関数は戻り値として、指定されたキーを持つデータ項目が既に登録されていればその値を、 そうでなければ NULL を返す。 しかし、 RetrieveDict 関数が NULL を返したからと言って、 このデータ項目がまだ登録されていないとは限らない。

この関数の戻り値は、登録されているキーの値を指すポインタそのものである。 このため、このポインタで指されるデータ構造を直接書き換えると、 その影響は dictionary に登録されている値にも影響を与えることになる。


データの消去

データが存在しないという状態を示すためには、幾つかの手段がある。 例えば、 等が考えられるが、これらの手段のうちどれを採用するか、 あるいは複数を採用してそれぞれにどのような意味付けをするかは、 利用者の選択に任されている。

データ構造からデータ項目そのものを削除するためには、 DeleteDict 関数を用いる。 この関数は引数として dictionary の指定と、キー文字列へのポインタを取る。
指定された dictionary に指定されたキーをもつデータ項目が存在する時には削除が成功し、 この関数は削除されたデータ項目が削除される直前に持っていた値へのポインタを返す。 この値を用いて、ユーザはメモリ管理などの必要な処理を行なう事ができる。
一方、削除すべきキーが見つからなかった時には NULL を返す。


全てのデータ項目の処理

dictionary に含まれる全てのデータ項目に対して一定の処理を行なう時のために、 EachDict 関数が用意されている。 この関数は引数として dictionary の指定と、その dictionary に含まれるひとつの項目へのポインタを取る。
キー文字列として NULL が指定されると、この関数は dictionary の中の最初のリニア・リストの最初の項目を返す。 キー文字列で示されるデータ項目がリニア・リスト中の最後の要素でなければ、そのリニア・リスト中で次の項目を返す。 キー文字列で示されるデータ項目がリニア・リスト中の最後の要素であれば、次のリニア・リスト中の最初の項目を返す。 キー文字列で示されるデータ項目が最後のリニア・リストの最後の要素であれば、 NULL を返す。

このため第二引数として、最初の EachDict 関数の呼出では NULL を与え、 その後は直前の EachDict 関数の戻してきた項目を与えれば、 順次 dictionary に含まれる全てのデータ項目を得ることができ、 NULL が返ってきた時点で全ての項目に関する処理が完了した事を知る事ができる。

ただし、直前の EachDict 関数が戻してきた項目を DeleteDict 関数で削除してしまうと、 その後に予期できない状態に陥る可能性がある。 ある dictionary に含まれる全てのデータ項目を削除する場合には、 常に EachDict 関数の第二引数として NULL を指定し、 この戻り値の示す項目の要素を DeleteDict 関数で削除するようにすればよい。


 [M.T. HomePage]  [written & copyrighted by Masayuki Takata]