Cでタイプセーフな（Generic）データ構造を書く方法
(danielchasehooper.com)- この記事は、C言語でタイプセーフな（Generic）データ構造を作る新しい方法を説明する
- unionを活用して型情報をデータ構造に関連付ける手法を、連結リストの実装を例に説明する
- 既存のCのジェネリックパターン（マクロ、
voidポインタ、Flexible Array Member）との違いと各方式の欠点を比較する - コンパイル時の型チェックが可能で、誤った型の使用を事前に防げる
- 新しい手法は
foo_listのような明確で一貫した関数／データ構造インターフェースを提供する
序論
- C言語でジェネリックなデータ構造を型安全に作る方法を紹介する
- この手法は、unionを使って型情報をコンパイル時にデータ構造へ結び付ける
- マップ、配列、二分木など、あらゆるデータ構造に適用でき、例として基本的な連結リストの実装で説明する
- 多くの開発者がCではジェネリックは不可能だと考えているため、段階を追って分かりやすく説明する
従来のマクロベースのジェネリック
- Cでジェネリックなデータ構造を実装する従来の方法は、マクロを使って構造体や関数の名前、型を生成すること
- データ構造のヘッダを複数の型向けに何度も
includeする形で拡張する
例:
- 型に応じた構造体名と関数名を生成するために**マクロ（例:
CONCAT,NODE_TYPE,PREPEND_FUNC）**を使う - 各型ごとに関数と構造体が個別に生成されるため、
intやFooなど型ごとに別々のデータ構造定義ができる
欠点:
- 型や関数の定義場所を把握しにくい（マクロで生成されるため追跡が難しい）
- コード補完機能を活用しにくい
- 同じ関数が複数生成されることで、バイナリサイズやビルド時間が増える
- 関数名に型プレフィックスが必要（例:
Foo_list_prepend）
ジェネリック段階 1: void ポインタ方式
- データ構造のデータ型を
void *にして、型に依存しない形にする - 連結リストの
dataフィールドをvoid *として宣言する - 型チェックができないため、実行時に型エラーが発生する可能性があり、コンパイル時の安全性が低い
- メモリおよびキャッシュ利用の非効率: ノードとデータを別々に割り当てるため、不要なオーバーヘッドやキャッシュミスが増える
ジェネリック段階 2: インラインストレージ（Flexible Array Member）
- Flexible Array Member（柔軟配列メンバ） を活用し、ポインタを保存する代わりにデータそのものをノード内に一緒に格納する
- ノードごとに1回の割り当てで済み、キャッシュ上ではデータと
nextポインタが隣接して配置される - この方式では
memcpyやサイズ情報の受け渡しが必要だが、一貫したメモリ配置によって性能が向上する list_alloc_front関数を使えば、memcpyなしで構造体を直接初期化できる
ジェネリック段階 3: 型チェックの実装
- unionの
payloadメンバにパラメータ化された型ポインタを宣言し、コンパイル時にデータ構造へ型情報を追加する - 例)
#define List(type) union { ListNode *head; type *payload; } - こうすることで
__typeof__(foo_list.payload)により、そのリストの型を取得できる - マクロ（
list_prepend）で関数型キャストを行うことで、正しい型でなければコンパイルできないようにする - 誤った型を使うとコンパイル時にエラーになる
エラー例:
foo_listにintを追加すると、incompatible integer to pointer conversionというコンパイルエラーメッセージが出力される
typeof 非対応コンパイラへの対応
- C23以前では
__typeof__は標準ではないため、一部のコンパイラ（例: 旧バージョンのMSVC）では動作しない struct内のpayloadメンバを活用するなどの回避策で、似た効果を得ることは可能
パラメータ受け渡しと typedef
- 同じ形の
List(Foo)であっても、コンパイラは互いに異なる型だと判断する typedefを使うと、引数の受け渡しや代入がスムーズになる
例:
typedef List(Foo) ListFoo;ListFoo型の変数宣言や関数引数として使用できる
まとめとさまざまなデータ構造への拡張
- この手法は、複数の型パラメータが必要なデータ構造（例: ハッシュマップ）にも活用できる
unionによってkeyとvalueそれぞれの型安全性を保証できる- より詳しい実践例やマクロ実装は、関連コードのgistリンク を参照
結論
- この新しい方式は、既存方式の欠点（可読性、ビルド効率、保守性）を克服し、一貫した関数命名体系と型安全性を提供する
- 複数のデータ構造や複数型パラメータへの対応が容易
- コンパイル時の型チェックによって、ジェネリックなデータ構造利用の安全性と効率性を同時に確保できる
謝辞
- この記事は Martin Fouilleul のフィードバックと励ましを受けて完成した
2件のコメント
単純に Zig を使えばいいのでは？という疑問は湧きます。
Hacker Newsのコメント
ステップ2のコードで
uint64_t data[];を使う方法について、アラインメント要件がuint64_tより大きい型には適さず、逆に小さい型には不必要に無駄が出るとの指摘。たとえば 64ビットアーキテクチャの ilp32 ABI ではさらに問題になり得る。ステップ3のコードではint main() { List(Foo) foo_list = {NULL};のようにすべきだという意見。typeofがない環境では戻り値を返せず、代替コードではconst関連のエラーが起こり得るうえ、==演算子の対称性によってこの問題が目立つ。payloadを外すとサイズ情報がなくなって安全ではなく、たとえばList(int64_t)にint32_tを追加しても一見問題なさそうに見えるが、実際にはint32_tのサイズを判断できない。より安全にするには補強が必要だという話。Cでジェネリクスを使う際には大きく二つの限界があると考えており、第一に vtable 委譲方式は構造体にマクロを含められないため機能が制限されること、第二に外部 vtable に委譲する場合は使う型をすべて事前に宣言しておく必要があること。最良の方法は typedef 宣言の入ったヘッダーで静的関数だけを宣言することだが、GCC と Clang では undefined static 警告が出るタイミングが異なるとも補足。最後に、異なるバッファ構造体を受け取る関数設計の例を挙げ、const版まで含めてすべて管理する必要がある点を強調外部 vtable 委譲の問題について、昔のプロジェクトでこれを解決するためにコンパイラまで作った経験を共有。Apache Clownfish プロジェクト開始時には .h ファイルをパースしていたが、最終的に Clownfish ヘッダー（.cfh）という独自フォーマットを作ったという。実際の obj の "Clone" メソッドを呼び出すコード例を示しつつ、オブジェクト指向機能が必要な動的言語バインディング向けに、こうした無理のあるコードを大量生成しなければならなかった経験を紹介。Clownfish の目的は最小公倍数的なオブジェクトモデルを提供することであり、バインディング先言語の型も .cfh から生成していたという。この複雑さのため、大半の人は
void*キャストで型安全性を諦めていると付け加える。 https://github.com/apache/lucy-clownfishint main()について、Cではint main()は引数の個数が未定であることを意味する。引数がないことを示すにはint main(void)と宣言しなければならない。多くの C++ 開発者がよく忘れる事実だと強調union が本当に「連合」される構造、つまりある型が別の型の union の一部として自分自身を宣言できたらよいのに、という意見
malloc 時の内部 padding の問題により、計算したサイズが実際より小さくなる可能性があるとの指摘。たとえば
malloc(sizeof(*node) + data_size);のような書き方には危険があるとするトリック#0への反論として、自分は C の完全な方言を作った際にこのトリックを使ったという話。たとえば generic binary heap の実装例コードを共有 https://github.com/gritzko/librdx/blob/master/abc/HEAPx.h。文法はやや重いが、最終的には普通の C 構造体になるため、最適化と予測可能性の面で大きな利点があるという。他の実装では
void*や実行時のメモリサイズ指定、マクロ定義が避けられないと見る筆者として、binary heap と linked list は目的が異なると説明。binary heap は格納時にデータを読む必要があるためアプローチが異なり、generic binary heap を書く場合は選択も変わり得ると述べる。本文の脚注でも触れたと補足
ヘッダー実装を好む理由をいくつか提示。デバッグ時にマクロ関数よりコード追跡や型情報の活用がしやすい。コンパイラが各インスタンスごとに monomorphized 最適化を行えるため、ランタイムコストや可変サイズの負担がない。generic 構造体をスタックに置ける。著者が挙げた二つの問題点も回避可能で、関数名マクロで名前を簡単に変えられ、weak symbol を使えばリンク時に二重定義を自動で統合できる。ポインタ型 generic コンテナには別の問題もあるが、typedef などで解決可能。Cでは intrusive data structure が依然として便利だが、デバッグは難しいという考え
「コンパイラがおやつのように食べる」という表現に大笑いした
関数の型変換では、たとえば Foo* と
void*の内部表現が同じだと仮定しがちだが、標準 C では保証されていない。型同士に互換性（"compatible"）がない状況でこのようなキャストを行うと未定義動作につながり得る。コンパイラの alias 解析などにも影響する可能性があるとのこと（参考リンクあり） https://news.ycombinator.com/item?id=44421185「Cで generics を使うために、なぜここまで無理をするのか。素直に C++ を使えばよいのでは」という質問
安全基準やその他の要件のため、レガシープロジェクトでは C++ への移行がすぐには不可能なことが多いという経験談を共有。新規プロジェクトでは標準を整えて C++ を導入するが、既存プロジェクトはしばらく C を維持せざるを得ないと考える。単に「C++ を使えば？」という見方にも、もう少し文脈への理解があってほしいという意見
実際、C を使う現場では C++ への移行の方が複雑で、より多くの問題を引き起こすことがある
逆に、少し手を加えるだけで C でも同じ結果が得られるのだから、わざわざ C++ まで持ち出す必要はないという立場もある
Linux カーネルで実際に使われている方法を紹介。リスト情報を持つ
struct list_headを型ごとの構造体に埋め込むパターンで、関連リンクも提示 https://kernelnewbies.org/FAQ/LinkedListsLIST_HEAD_INIT、INIT_LIST_HEADというマクロ名は直感的ではないと感じる"typeof on old compilers" セクションのコードで、
(list)->payload = (item);は実際には no-op ではなく、リストヘッドが item で上書きされてしまうという指摘。意図した動作ならif(0)で囲むべきだとの提案if(0)の中で処理した方がよさそうだという意見D 言語ではこうした generic list 構造がはるかに簡単だと示しつつ、C のプリプロセッサはまるで爪にハンマーを打ちつけるようなもので、釘打ちには Nail gun の方がずっと速くてきれいだ、という比喩で C マクロの不便さを強調
union と
typeof()を活用するアイデアは興味深いという感想。自分の場合、intrusive データ構造では結局巨大なマクロで包むラッパーが必要だと感じており、union とtypeofでもこの種の実装が可能なのか疑問だと述べる。例として hash table ラッパー実装コードとドキュメントへのリンクを共有 https://github.com/FRRouting/frr/blob/master/lib/typesafe.h#L823-L971 https://docs.frrouting.org/projects/dev-guide/en/latest/lists.html個人的に、すでに実験的ライブラリでこの手法を使っているという共有 https://github.com/uecker/noplate/blob/main/src/list.h
関数ポインタの型を活用して型安全性を確保するという発想が核心に見えるとするコメント。一般的なハンドル型の代わりにそう実装しているという。C23 標準では型互換性の問題が改善されており、該当する標準文書と最新の GCC/Clang の対応状況も共有 https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3037.pdf