ハクソク

世界を動かす技術を、日本語で。

C言語で型安全なジェネリックデータ構造を作成します

329日前原文(danielchasehooper.com)

概要

  • C言語で型安全なジェネリックデータ構造を実現する独自手法の紹介
  • unionを活用し、型情報をデータ構造に関連付ける方法
  • 既存のマクロ多重インクルード法やvoid *による手法との比較
  • 柔軟配列メンバやtypeofによる型安全性の向上
  • typedefによる型名解決や複数型対応の拡張性

C言語における型安全なジェネリックデータ構造の実装手法

  • union を用いて、ジェネリックなデータ構造に 型情報 を埋め込む独自手法
  • List, Map, Tree など様々なデータ構造に適用可能
  • 本記事では 基本的なリンクリスト を例に実装方法を解説

従来手法：マクロ多重インクルードによる型安全性

  • データ構造を ヘッダファイル でマクロ展開し、型ごとに複数回インクルード
  • 例：
    • #define T Foo
    • #include "list.h"
    • 型ごとに関数名や構造体名が生成 される（例: Foo_list_prepend）
  • 欠点
    • 定義箇所の特定が困難 （マクロ展開による可読性低下）
    • コード補完やリファクタリングが難しい
    • バイナリサイズやビルド時間の増大
    • 型名プレフィックス付き関数 が必要（例: Foo_list_prepend）

Genericsレベル1：void *による汎用化

  • *void 型 でデータ構造を汎用化
  • 例：
    • struct ListNode { ListNode *next; void *data; };
    • list_prepend(ListNode **head, void *data);
  • 欠点
    • 型安全性が失われる
    • 2回のメモリアクセス が必要（ノードとデータが別アロケーション）

Genericsレベル2：インラインストレージ（柔軟配列メンバ）

  • 柔軟配列メンバ を利用し、ノードとデータを 同一メモリブロック に格納
  • 例：
    • struct ListNode { ListNode *next; uint64_t data[]; };
    • list_prepend(ListNode **head, void *data, size_t data_size);
  • パフォーマンス向上 と メモリ効率化
    • nextとdataが隣接することで キャッシュ効率 向上
  • 欠点
    • data_sizeの明示的指定 が必要

Genericsレベル3：typeofとunionによる型安全性

  • union を用いてリストに型情報を持たせる
    • 例：#define List(type) union { ListNode *head; type *payload; }
  • payload はランタイムで未使用、 型情報のみを保持
  • typeof を使い、 list_prependマクロ で型安全な関数呼び出しを実現
    • #define list_prepend(list, item) ((void (*)(ListNode **, __typeof__((list)->payload), size_t))_list_prepend) (&((list)->head), item, sizeof(*(list)->payload))
  • 型不一致時はコンパイルエラー
    • 例：int型リストにFoo型を追加するとエラー

typeof未対応コンパイラへの対応

  • typeof非対応の場合 はstructで型情報を保持
    • 例：#define List(type) struct { ListNode *head; type *payload; }
  • payloadへの代入で型チェック を実現
    • #define list_prepend(list, item) do { (list)->payload = (item); _list_prepend(&((list)->head), item, sizeof(*(list)->payload)); } while(0)

typedefによる型名の統一

  • typedef でList(Foo)型をListFooなどに定義
  • 関数引数や代入時の型不一致エラー を回避
  • 例：
    • typedef List(Foo) ListFoo;
    • ListFoo a; ListFoo b = a; void my_function(ListFoo list); my_function(a);

応用：複数型対応データ構造

  • Map など複数型を持つデータ構造も同様に拡張可能
    • 例：
      • #define Map(key_type, value_type) union { MapInternal map; key_type *key; value_type *value; }

まとめ・参考

  • union + typeof による型安全なジェネリックデータ構造
  • 柔軟な拡張性 と 型安全性 を両立
  • stb_ds.h など他の型安全実装との比較
  • typeof はC23で標準化、主要コンパイラで広くサポート

参考リンク・謝辞

  • stb_ds.h ：配列やマップの型安全な実装例
  • Martin Fouilleul ：記事執筆の励ましと初期フィードバック

Hackerたちの意見

いいトリックだね。もう実験的なライブラリで使ってるけど ;-) https://github.com/uecker/noplate/blob/main/src/list.h

└

誰かが知ってるかもしれないと思うけど、君はどう思う？侵入型データ構造で、データの中にノード構造体を埋め込む方法（それによってオブジェクトが複数のコンテナに存在できるようにする）ってできるかな？君がやってるように、ノードの中にデータを入れるんじゃなくて。

unionとtypeof()を使った面白いアイデアだね。俺たちは（俺は）大きなマクロでラッパーを定義する方向に行ったけど、これは侵入型データ構造には必要だと思う。unionとtypeofでどうやるかはすぐには思いつかないな。もしかしたらできるかも…？例えば、ハッシュテーブルのラッパー: https://github.com/FRRouting/frr/blob/master/lib/typesafe.h#... （参考: https://docs.frrouting.org/projects/dev-guide/en/latest/list...）

君のレベル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のsizeofはできない。君のコードは実際にこれを動かすにはかなり足りてないよ。===== Cのジェネリクスには今のところ2つの大きな制限がある: * vtable（内部または外部）への委譲は機能が限られていて、構造体はマクロを含められず、関数だけだから。 * 外部vtableへの委譲（オーバーヘッドを避けるために必須）は、使うすべての型を前方宣言しなきゃいけない。今のところ、見つけた最良のアプローチは、typedefを宣言するのと同じ前方ヘッダーで静的関数を宣言（でも定義はしない）することだよ。GCCとClangは、特定の型のヘッダーを含めない場合に「未定義の静的」警告がどの段階で出るかが異なるから注意してね。（struct SizedBuffer {void *p; size_t len;};かstruct BoundedBuffer {void *begin; void *end;};のどちらかを受け取る関数を書くことを考えてみて、さらにそれらのconstバージョンも - すべて異なるヘッダーから。）

└

unionが連携できたらいいなと思ってる。つまり、型が他の型とのunionの一部であるかのように自分を宣言できて、すべての可能な型を一箇所で事前に宣言する必要がないってこと。

└

外部のvtableに委譲する（オーバーヘッドを避けるために必須）ということは、使用するすべての型を前方宣言しなければならないということです。私は以前のプロジェクトの一環でこれに関するコンパイラを書くことに挑戦しました（Apache Clownfish[1]、引退したApache Lucyプロジェクトのサブプロジェクトです）。最初は.hファイルを解析していましたが、最終的には独自の小さなヘッダー言語（.cfh「Clownfish Header」ファイル）を作る方が理にかなっていました。以下は、親クラス「Obj」で定義された「Clone」メソッドのCharBufバージョンを呼び出すために生成されたコードです： typedef cfish_CharBuf* (CFISH_CharBuf_Clone_t)(cfish_CharBuf self); extern uint32_t CFISH_CharBuf_Clone_OFFSET; static inline cfish_CharBuf* CFISH_CharBuf_Clone(cfish_CharBuf* self) { const CFISH_CharBuf_Clone_t method = (CFISH_CharBuf_Clone_t)cfish_obj_method(self, CFISH_CharBuf_Clone_OFFSET); return method(self); } 使用例： cfish_CharBuf *charbuf = cfish_CharBuf_new(); cfish_CharBuf clone = CFISH_CharBuf_Clone(charbuf); こうした極端なことをした理由はあって、Clownfishの目的は複数の動的言語へのバインディングのための最小公倍数のオブジェクトモデルを提供することでした（SWIGと似た問題領域です）。.cfhファイルはバインディング言語の型を導出するためにも使われていました。しかし、あなたが指摘する問題を回避するために生成されるボイラープレートは本当にばかげた量でした。だからほとんどの人は型安全性を無視して、invocantにはvoidへのキャストを使うんだよ。[1] https://github.com/apache/lucy-clownfish

└

これも問題があって、パディングがあるかもしれないし、計算されたサイズが小さすぎるかもしれない： malloc(sizeof(*node) + data_size);

└

int main()は不明な数の引数を取る関数を意味するんだ。引数を取らないことを示すにはint main(void)が必要だよ。これ、C++を書く人にはよく忘れられがちな事実だね。

こんにちは。反対意見です。君が言ってるトリック#0は、俺がCの方言を作った方法なんだ。例えば、こちらが汎用のバイナリヒープ: https://github.com/gritzko/librdx/blob/master/abc/HEAPx.h 構文はちょっと重いけど、最大の利点は、最終的に普通のC構造体が得られること。とてもシンプルで、予測可能で、最適化しやすい。コンパイラはそれをドーナツのように食べるよ。他の場合はvoid*とランタイムメモリサイズが必要で、マクロを定義しなきゃいけないしね。

└

同意するよ、実際にヘッダー実装を好む理由はいくつかある。デバッグがしやすいから、マクロ関数ではできないヘッダーコードをステップ実行できるし、デバッガに利用できる型情報も良いからね。各インスタンス化が単一形にされるから、コンパイラの最適化の機会も増えるし、固定サイズのおかげでジェネリック構造体はスタックに置ける。著者が言ってる問題のうち、少なくとも2つにはワークアラウンドがあるよ。名前をBar_func(args…)からfunc(Bar)(args…)に変更することができるし、名前マングリングをするマクロを使えばいい。リンク時に翻訳単位間で共有される関数をリンカが重複排除できるように、弱いシンボルを使うことでバイナリの膨張を避けられる。ただし、ポインタ型のジェネリックコンテナには他にも問題があって、typedefや型エイリアスを使うことで回避できる。侵入型データ構造はCではまだ便利だけど、デバッガで扱うのは面倒だね。

└

ここで著者です。バイナリヒープと連結リストは異なるユースケースだよ。バイナリヒープは正しくデータを格納するために、入れたデータを読み取る必要があるけど、連結リストはそうじゃない。もし俺が汎用のバイナリヒープを書いてたら、選択肢を違う風に考えるかもしれない。これについては脚注で触れたよ。

└

コンパイラはそれをドーナツのように食べるだろうね。めっちゃ笑った！

この関数型のキャストは、アイテムポインタ型（例えば、Foo*）がvoid*と同じ表現を持つと仮定していますが、C標準ではそれが保証されていません（標準的には、二つの型は「互換性がない」とされています）。したがって、変換された型で関数を呼び出すことは未定義の動作を引き起こします。ポインタの表現がたまたま同じであっても、コンパイラによるエイリアス解析にも影響を与えます。この関数を異なる引数型にキャストすることは、ジェネリック呼び出しの型安全性の核心を成していますが、これを修正できるかどうかは分かりません。

└

これは脚注で触れられています。キャストは型安全性の核心ではありません。記事全体を読んでみてください。

Linuxカーネルで使われている方法もあって、リスト情報（struct list_head）を型特有の構造体に埋め込むことができます。

└

LIST_HEAD_INITとINIT_LIST_HEADの名前が混乱するなぁ。

もし「ジェネリック付きのC」が欲しいなら、なんでこんなに面倒なことをするの？普通にC++を書けばいいのに。

└

Cが使われる多くのユースケースでは、C++に切り替えるとさらに多くの面倒が増えるからだよ。

└

私は安全規制や他の品質保証に結びついたレガシープロジェクトで働いているから、次のリリースでC++に移行したソリューションを簡単に導入することはできないんだ。だから、できるまでこのまま動かすしかないかな。でも、新しいプロジェクトにはC++を使う基準と期待を設定できるし、実際にそうしてるよ。特定の標準を目指す期待もね。ハッカーニュースでもこういう意見をよく見るけど、みんな「もっと頑張れ」と言ってるように感じる。ここにはもっとニュアンスが必要だと思うんだ。

└

Cでいくつかの手間をかけるだけで同じ結果が得られるなら、なんでC++を書くの？

Dでのやり方はこうだよ:

struct ListNode(T) {
    ListNode* next;
    T data;
}
T!int node;

Cのプリプロセッサを使うのは、仕上げの大工仕事にハンマーを使うようなもんだよ。釘打ち機を使った方が10倍早いし、毎回完璧に釘を打てるし、作業に半月の凹みもできないからね。

└

ありがとう、この記事はCについてのものだね。いくつかのプロジェクトではCを使わなきゃいけないんだ。

“古いコンパイラでのtypeof”セクションには、以下のコードが含まれてる:

(list)->payload = (item); /* 型チェックのためだけ */

これはノーオペレーションじゃないよ。リストのヘッドをあなたの(item)で上書きしてるんだから。if(0)で囲むつもりだったの？

└

その例では、ユニオンを構造体に置き換えたみたいだけど、これはこの問題を回避するためだろうね。でも、それも無駄に思えるなぁ。if(0)の中でやる方がずっと良さそうだ。