Tools.h++ 7.0 ユーザーズガイド: 8 - クラス RWBTreeOnDisk の使用法

Copyright 1999 Rogue Wave Software
Copyright 1999 Sun Microsystems, Inc.

# クラス RWBTreeOnDisk の使用法 | # 8 |

クラス RWBTreeOnDisk はディスクファイル内の B ツリーを管理するために設計されたものです。このクラスはキーと値の関連の順序付けられた (ordered) コレクションを表現します。この順序付けはキーの比較によって内部的に決定されます。キーが与えられれば、値を取り出すことができます。重複キーは使用できません。

キーは `char` 型の配列です。キー長はコンストラクタによって設定されます。B ツリー内での順序付けは、外部関数でキーを比較して決定されます。この関数はユーザーが変更できます。

値の型は `typedef` で次のように設定されます。

      typedef long RWstoredValue;

一般に、これらの値はオブジェクトが格納されたファイル内の位置までのオフセットを表現します。したがって、キーが与えられればオブジェクトが格納されている場所を見つけ、それを取り出すことができます。しかし、クラス RWBTreeOnDisk に関する限り、この値は特別な意味を持ちません。それを解釈するのはユーザー自身です。

このクラス RWBTreeOnDisk は、クラス RWFileManager を使用して B ツリーのノード用領域の割り当てと解放を管理します。B ツリーとデータを同じファイルに格納する場合は、同じ RWFileManager を使用してオブジェクト用の領域も管理することができます。また、B ツリーとデータを別々のファイルに格納する方がよい場合は、別の RWFileManager によって別のファイルを管理することもできます。

クラス RWBTreeOnDisk に関連したメンバー関数は、クラス RWBTreeDictionary (メモリー内の B ツリーを管理する) のメンバー関数とほぼ同じですが、キーが RWCollectables ではなく `char` 型の配列であるという点が異なります。キーと値の対を追加したり、キーを削除したり、キーについての情報を照会したり、すべてのキーと値の対を順に操作したり、ツリー内のエントリ数を返したり、特定のキーがツリー内に含まれているかどうか判別したりするためのメンバー関数があります。

## 作成

RWBTreeOnDisk は常に RWFileManager から作成されます。RWFileManager が新しいファイルを管理している場合、RWBTreeOnDisk はそれを空のルートノードで初期化します。たとえば、次のコードの断片は、"`filename.dat`" という新しいファイルに対する RWFileManager を作成し、そこから RWBTreeOnDisk を作成します。

      #include <rw/disktree.h>
      #include <rw/filemgr.h>

      main(){
        RWFileManager fm("filename.dat");

        // filename.dat を空のルートノードで初期化
        RWBTreeOnDisk bt(fm);
      }

## 例

この例では、文字列のキーと値の対および誕生日を表現する RWDate までのオフセットが格納されます。名前が与えられると、ディスクから誕生日を取り出すことができます。

    #include <rw/disktree.h>
    #include <rw/filemgr.h>
    #include <rw/cstring.h>
    #include <rw/rwdate.h>
    #include <rw/rstream.h>

    main(){
       RWCString name;
       RWDate birthday;

       RWFileManager fm("birthday.dat");
       RWBTreeOnDisk btree(fm);                                  // 1

       while (cin >> name)                                       // 2
       {
         cin >> birthday;                                        // 3
         RWoffset loc =  fm.allocate(birthday.binaryStoreSize());// 4
         fm.SeekTo(loc);                                         // 5
         fm << birthday;                                         // 6
         btree.insertKeyAndValue(name, loc);                     // 7
       }
       return 0;
    }

次に、このプログラムを 1 行ずつ説明します。

`//1` | BTree を生成します。デフォルトコンストラクタが使用され、キー長は 16 文字 (デフォルト) になります。
`//2` | 標準入力から名前を読み取ります。このループは EOF に達したときに終了します。
`//3` | 対応する誕生日を読み取ります。
`//4` | 誕生日を格納するのに十分な領域を RWFileManager から割り当てます。メンバー関数 `binaryStoreSize()` は Rogue Wave のほとんどのクラスにあるメンバー関数です。この関数は、バイナリファイルにオブジェクトを格納するのに必要なバイト数を返します。RWCollection 全体を格納するか、あるいは `recursiveSaveOn()` か `operator<<` (`RWFile&, RWCollectable`) のどちらか 1 つのメソッドを使用する場合は、必ず `recursiveStoreSize`() をかわりに使用するようにしてください。
`//5` | RWDate が格納される位置にシークします。
`//6` | その位置に日付を格納します。Rogue Wave のほとんどのクラスにはストリーム (`<<` と >>) 演算子の多重定義バージョンがあります。
`//7` | オブジェクトまでのオフセットとキーを B ツリーに挿入します。

名前と誕生日をファイルに格納したら、それを取り出すにはどうすればよいのでしょうか。次のプログラムがこれを実行します。

    #include <rw/disktree.h>
    #include <rw/filemgr.h>
    #include <rw/cstring.h>
    #include <rw/rwdate.h>
    #include <rw/rstream.h>

    main(){
       RWCString name;
       RWDate birthday;

       RWFileManager fm("birthday.dat");
       RWBTreeOnDisk btree(fm);

       while(1)
       {
         cout << "Give name: ";
         if (!( cin >> name)) break;                             // 1
         RWoffset loc = btree.findValue(name);                   // 2
         if (loc==RWNIL)                                         // 3
           cerr << "Not found.\n";
         else

         {
           fm.SeekTo(loc);                                       // 4
           fm >> birthday;                                       // 5
           cout << "Birthday is " << birthday << endl;           // 6
         }
       }
       return 0;
    }

次に、このプログラムを 1 行ずつ説明します。

`//1` | このプログラムは EOF に達するまで名前を受け入れます。
`//2` | この名前は RWBTreeOnDisk へのキーとして使用されています。 この関数はキーに関連した値が記憶されているファイルへのオフセットを返します。
`//3` | 名前が見つかったかどうか調べます。
`//4` | 名前が有効なものであれば、その値を使用して関連した誕生日が格納されている位置にシークします。
`//5` | ファイルからその誕生日を読み取ります。
`//6` | 誕生日を出力します。

わずかな作業で、1 つのファイルに複数の B ツリーを簡単に作成することができます。その結果、複数のキーにもとづく複数のインデックスを保持することができるようになります。次に、1 つのファイルの中に B ツリーを 3 つ作成するプログラムを示します。

    #include <rw/disktree.h>
    #include <rw/filemgr.h>

    main(){
       RWoffset rootArray[3];

       RWFileManager fm("index.dat");
       RWoffset rootArrayOffset =     fm.allocate(sizeof(rootArray));

       for (int itree=0; itree<3; itree++)
       {
         RWBTreeOnDisk btree(fm, 10, RWBTreeOnDisk::create);
         rootArray[itree] = btree.baseLocation();
       }
       fm.SeekTo(fm.start());
       fm.Write(rootArray, 3);
       return 0;
    }

3 つの B ツリーをオープンする方法は、次のとおりです。

    #include <rw/disktree.h>
    #include <rw/filemgr.h>

    main(){
       RWoffset rootArray[3];           // ツリールートの位置
       RWBTreeOnDisk* treeArray[3]; // RWBTreeOnDisk へのポインタ
       RWFileManager fm("index.dat");
       fm.SeekTo(fm.start());      // ルートノードの位置を復帰
       fm.Read(rootArray, 3);

       for (int itree=0; itree<3; itree++)
       {
         // 3 つのツリーを初期化:
         treeArray[itree] = new RWBTreeOnDisk(fm,
                          10,          // キャッシュされる最大ノード
           RWBTreeOnDisk::autoCreate,  // 古いツリーを読み取る
                          16,          // キー長
                          FALSE,       // NULL を無視しない
                          rootArray[itree] // ルートの位置
                                              );
       }

       .
       .
       .
       for (itree=0; itree<3; itree++)  // ヒープメモリーを解放する
          delete treeArray[itree];

       return 0;
    }