【ITニュース解説】Generic Data Structures in C

C言語でさまざまな種類のデータを扱える汎用的なデータ構造を作ることは、しばしば工夫が必要となる。C++のような「テンプレート」機能がないため、データ構造の設計者はデータの型に依存しないコードを書くために、いくつかの方法を検討しなければならない。

一般的に使われる方法の一つに「void*（ボイドポインタ）」を利用するものがある。void* は、どんな種類のデータも指し示すことができる特殊なポインタで、具体的なデータの型を気にせずにポインタを保持できる。例えば、赤黒木という効率的なデータ構造のノードを考えると、そのノードが保持するデータ部分には void* data; のように記述される。これにより、整数でも文字列でも、どんなデータでもこの data メンバーに格納できるようになる。

しかし、この void* にはいくつかデメリットが存在する。一つは、データそのものをノード内に直接格納するのではなく、データが別のメモリ領域に存在するため、データを格納する際に追加で malloc() という関数を使ってメモリを確保し、不要になった際には free() で解放する必要がある点だ。これはメモリ管理の手間を増やし、プログラムの複雑性を増す可能性がある。もう一つのデメリットは、データがノードとは別のメモリ領域にあるため、データにアクセスする速度が遅くなる場合があることだ。コンピュータのメモリは、CPUに近いほど高速なキャッシュメモリとして機能するが、データがノードと同じキャッシュライン（CPUが一度に読み込むメモリの単位）に乗らないことで、パフォーマンスが低下することがある。ただし、もし格納したいデータのサイズが void* のサイズ以下、例えば整数型のような小さなデータであれば、ポインタとして解釈できる範囲内でデータを直接 void* に「詰め込んで」扱うテクニックもある。しかし、多くの複雑なデータでは、やはり別途メモリを確保するしかないのが現状である。

そこで、これらの課題を克服するためのより良い方法として、「フレキシブル配列メンバー（FAM: Flexible Array Member）」というC99標準で導入された機能が紹介されている。これは、構造体の最後のメンバーとして、サイズが指定されていない配列を置くことができる機能だ。具体的には、赤黒木のノード構造を alignas( max_align_t ) char data[]; のように定義する。alignas はメモリの配置を適切に調整するための指示であり、char data[]; がフレキシブル配列メンバーである。この方法の利点は、ノード自体のメモリと、ノードが保持するデータのためのメモリを、malloc() を一度呼び出すだけで連続した領域として確保できる点にある。例えば、sizeof(rb_node_t) + data_size のように、ノードの基本サイズに加えてデータのサイズ分のメモリを確保し、その後に memcpy() でデータをコピーする。これにより、メモリの確保と解放が一度で済み、データがノードと物理的に近い場所（同じキャッシュライン）に配置される可能性が高まるため、データアクセス速度の向上が期待できる。また、ノードごとに異なるサイズのデータを格納できる柔軟性も持つ。キーと値のように複数の情報を格納したい場合でも、それらを一つの構造体にまとめてFAMに格納することで、セット（Set）としてもマップ（Map）としても機能する汎用的なデータ構造を構築できる。

しかし、FAMにもデメリットは存在する。データをノードに挿入する際には、データをメモリにコピーする必要があり、大きなデータの場合にはこのコピー処理がコストになることがある。また、ノードを木から削除してもそのデータは保持したい、という場合には、削除前にデータをノードから別の場所にコピーし出す手間がかかる。

このように、どの方法にも長所と短所があるため、最終的には状況に応じたトレードオフが発生する。このニュース記事では、さらに進んだアプローチとして、ユーザーがこれらのデータ格納方法（ポインタによる外部格納か、FAMによる内部格納か）を選択できるようにする仕組みが提案されている。

具体的には、rb_dloc という列挙型（enum）を定義し、データの格納場所を RB_DINT（データがノード内に内部格納される場合）と RB_DPTR（データへのポインタがノード内に格納される場合）の二通りで指定できるようにする。そして、赤黒木全体を管理する rb_tree 構造体に、この rb_dloc_t 型のメンバー dloc を追加する。これにより、一つの赤黒木インスタンスが、どのデータ格納方法を採用しているかを記憶できるようになる。

データ構造を初期化する rb_tree_init 関数では、この dloc を引数として受け取り、木全体のデータ格納ポリシーを設定する。データ挿入を行う rb_tree_insert 関数では、この dloc の値に応じて内部処理を切り替える。RB_DINT が選択されていれば、FAMを使ってノードとデータを一括で確保しコピーする。RB_DPTR が選択されていれば、ノードとポインタ分のメモリを確保し、データへのポインタを格納する。

さらに、rb_node_data と rb_tree_cmp というヘルパー関数が導入される。rb_node_data は、木の dloc に応じて、ノード内のデータ本体、あるいはデータへのポインタを返す。これにより、データがどこに格納されているかを意識することなく、統一された方法でデータにアクセスできる。rb_tree_cmp は、この rb_node_data を利用して、新しいデータとノード内のデータを比較する。これらの工夫により、データの格納方法が異なっていても、データの探索や削除といった赤黒木の中核的なアルゴリズム部分は共通のコードで実現できるようになる。

結論として、C言語でジェネリックなデータ構造を構築する際には、void* やフレキシブル配列メンバーといった機能を活用し、それぞれの利点と欠点を理解することが重要である。そして、今回紹介されたように、ユーザーがデータ格納方法を選択できるような柔軟な設計を取り入れることで、さまざまな利用状況に最適なパフォーマンスと使いやすさを両立させることが可能になる。これは、リンク付きリストやハッシュテーブルなど、他の動的にノードを割り当てるデータ構造にも応用できる汎用的なアプローチと言える。