Cで型安全なジェネリックデータ構造を書く方法

 (danielchasehooper.com)
3 ポイント 投稿者 GN⁺ 2025-07-01 | 2件のコメント | WhatsAppで共有
  • Cでもマクロ、void *、flexible array member、unionを組み合わせれば型安全なジェネリックデータ構造を作ることができ、例では連結リストの段階的な実装を示す
  • 型ごとのヘッダーを複数回 include する方式は安全だが、マクロ生成コードのため定義の追跡とコード補完が難しく、バイナリサイズやビルド時間が増える可能性がある
  • void * ベースのリストは汎用性がある一方で型エラーを防げず、ノードとデータを別々に割り当てるとノードあたり2回の割り当てとキャッシュミスが発生し得る
  • flexible array member でデータをノード内に格納し、List(type)をunionで包むと、ランタイムコストなしでコンパイル時の型情報を付与できる
  • list_prependマクロは三項演算子で渡された値とpayloadの型を一致させてコンパイルエラーを誘発し、戻り値のポインタ型には__typeof__()を活用できる

Cジェネリック実装の出発点

  • 目標は、CでList(int)、List(Foo)のように型別のリストを宣言し、誤った型を入れようとするとコンパイルできないようにすること
  • 例ではList(Foo)にFooの値を入れられるが、list_prepend(&foo_list, 7)のように別の型を入れるコードはコンパイルされない
  • list_for(item, &foo_list)内のitemはFoo *型として扱える

レベル0: ジェネリックヘッダー方式

  • 1つの方法は、データ構造をヘッダーに書き、型マクロTを変えながら#includeを複数回行うこと
  • list.hはTをもとに、FooListNode、Foo_list_prependのような型や関数をマクロで生成する
  • この方式はジェネリックで型安全だが、使い勝手は荒くなる
    • 型や関数がマクロで構成されるため、定義位置を見つけにくい
    • コード補完がうまく動作しない場合がある
    • 同じ関数のコピーが型ごとに生成され、バイナリサイズとビルド時間が増える
    • list_prepend()ひとつではなく、Foo_list_prepend()、int_list_prepend()のように型プレフィックス付きの関数を使う必要がある
  • 型ごとのコード生成が必要なジェネリック関数には、この方式のほうが適している場合がある

レベル1: void *ベースのリスト

  • ListNodeがvoid *dataを持てば、複数の型のデータを格納できる
  • list_prepend(ListNode **head, void *data)はデータポインタをそのまま保存するため、実装は単純
  • 問題は、この構造が型安全ではない点
  • ノードとデータが別々に割り当てられると、メモリと性能のコストも大きくなる
    • ノード1つにつき2回の割り当てが必要
    • dataポインタ自体が追加メモリを使う
    • リスト走査時に、次のノードへのアクセスとデータへのアクセスでそれぞれキャッシュミスが起こり得る
  • サンプルコードではなじみやすさのためにmallocを使っているが、実際には Arena の使用を推奨しており、関連資料として動画と記事を参照できる

レベル2: ノード内にデータを格納する

  • void *dataの代わりにFlexible Array Memberを使うと、データをノード内に置ける
  • struct ListNodeはListNode *nextとchar data[]を持ち、割り当て時にsizeof(* node) + data_size分を一度に確保する
  • list_prependは渡されたデータとサイズを受け取り、memcpyでnode->dataにコピーする
  • この方式ではnextと実データがメモリ上で近くに配置されるため、void *方式の割り当てとキャッシュの問題を減らせる
  • その代わり、呼び出し側がdata_sizeを渡す負担が生じる
  • memcpyを避けたい場合は、list_alloc_frontがノードのデータ領域ポインタを返すようにし、呼び出し側がそのメモリを直接初期化できる
  • dataメンバーのアラインメント、パディング、サイズ計算の問題は別のテーマなので、例では詳しく扱わない

レベル3: unionで型情報を付ける

  • 中心となるテクニックは、List(type)をunionとして定義し、実際のリストヘッドと型情報用ポインタを一緒に持たせること
#define List(type) union { \
    ListNode *head; \
    type *payload; \
}
  • payloadはランタイムでは使われず、コンパイル時の型情報を提供する
  • unionを使うため、payloadは別途メモリを消費しない
  • List(Foo) foo_list、List(int) int_listのように型別のリストを作れる

三項演算子で型チェックする

  • list_prependマクロは内部関数_list_prependを呼び出す際、三項演算子でitemと(list)->payloadの型を一致させる
#define list_prepend(list, item) \
    _list_prepend(&((list)->head), \
                  (1 ? (item) : (list)->payload), \
                  sizeof(*(list)->payload))
  • 三項演算子の2つの候補の型が一致しない場合、コンパイラが型不一致エラーを出す
  • たとえばList(Foo)にBar *を渡すと、ClangはFoo *とBar *のポインタ型不一致をエラーとして表示する
  • 同じマクロがsizeof(*(list)->payload)で保存する型のサイズも自動的に渡す
  • 実際の処理は、_list_prepend(ListNode **head, void *data, size_t data_size)のようなジェネリックな内部関数が担当する

戻り値の型には__typeof__()を使う

  • ジェネリック関数が内部データポインタを返す必要がある場合は、__typeof__()でvoid *の戻り値をpayloadの型にキャストできる
#define list_alloc_front(list) \
    (__typeof__((list)->payload))_list_alloc_front(&(list)->head, sizeof(*(list)->payload))
  • __typeof__()はClang、GCC、MSVC 19.39以降でサポートされている
  • __typeof__()はC23で標準に含まれるまで、任意の拡張だった
  • MSVC 19.39以前のように__typeof__()がないコンパイラでは、三項演算子ベースの型チェックを使える
  • 型安全な戻り値もpayloadを通した割り当て方式で実現できるが、詳細な実装は省略されている

以前の方式と定義上の注意点

  • 以前の方式は、_list_prependを__typeof__((list)->payload)を含む関数ポインタ型にキャストして呼び出す構造だった
  • 型キャストされた関数ポインタの呼び出しは技術的には未定義動作だが、現代のコンパイラと現代のプラットフォームでは実際には問題ないものとして扱っている
  • 現在の方式は関数ポインタのキャストではなく、三項演算子による型一致でエラーを誘発する

List(Foo)を引数として渡すときの問題

  • Cコンパイラは、同一構造を持つ2つのList(Foo)定義を同じ型と見なさない場合がある
List(Foo) a;
List(Foo) b = a; // error
  • 関数引数としてvoid my_function(List(Foo) list)を定義し、my_function(a)を呼び出しても、互換性のない型のエラーが出る場合がある
  • 解決策はtypedefで型名を付けること
typedef List(Foo) ListFoo;

ListFoo a;
ListFoo b = a; // ok

void my_function(ListFoo list);
my_function(a); // ok
  • ローカル変数ではList(Foo) local_foo_listという形を引き続き使える
  • GCC 15と2025年末のClangでは、ルール変更により、同じタグ名を持つ構造的に同一の型が同じ型として扱われる予定

リスト以外のデータ構造にも適用可能

  • 同じテクニックはリストだけでなく、マップ、配列、二分木のようなさまざまなデータ構造に適用できる
  • 複数の関連型が必要なデータ構造にも拡張可能
  • たとえばハッシュマップでは、内部構造とキー型、値型をunion内にまとめて置ける
#define Map(key_type, value_type) union { \
    MapInternal map; \
    key_type *key; \
    value_type *value; \
}
  • stb_ds.hも型安全なジェネリックデータ構造の例だが、配列とマップがC配列を使うため、一部の型エラーは値を渡す時点ではなく配列代入の時点で検出される構造になっている

関連記事

2件のコメント

 
click 2025-07-01

単純に Zig を使えばいいのでは？という疑問は湧きます。
 
GN⁺ 2025-07-01
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 の sizeof を知ることができません。このコードが正しく動作するには、まだ足りない部分がかなりあります
    現在の C のジェネリクスには大きな制約が 2 つあります。第一に、vtable に委譲する方式は、構造体がマクロを含められず関数しか含められないため、機能が制限されます。第二に、オーバーヘッドを避けるには外部 vtable に委譲する必要がありますが、そのためには vtable を使うすべての型を前方宣言しなければなりません
    これまでに見つけた最善策は、typedef を宣言する前方ヘッダーに static 関数を宣言だけして定義しない方式でした。実際、特定の型のヘッダーをある翻訳単位に含めなかったときに “undefined static” 警告が出る段階は、GCC と Clang で異なります
    たとえば、異なるヘッダー由来の struct SizedBuffer {void *p; size_t len;}; や struct BoundedBuffer {void *begin; void *end;};、そしてそれぞれの const 版をすべて受け取る関数を考えればよいでしょう

    • 外部 vtable に委譲するには vtable を使うすべての型を前方宣言しなければならないという問題のため、以前参加していた Apache Clownfish プロジェクトでは、そのためのコンパイラまで作りました
      当初は .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 の目的は、複数の動的言語バインディング向けに最小公分母となるオブジェクトモデルを提供することで、.cfh ファイルはバインディング言語用の型を導出するためにも使われていました。それでも、指摘された問題を避けるために生成したボイラープレートコードの量は本当に途方もないものでした
      そのため、ほとんどの人は型安全性を諦め、呼び出し先に void* キャストをそのまま使うほうを選びます
      https://github.com/apache/lucy-clownfish

    • C で int main() は引数を取らないという意味ではなく、不明な個数の引数を取るという意味です。引数を取らないという意味にするには int main(void) と書く必要があります。C++ を使う人がよく忘れる事実です

    • union が和的に拡張できるとよいと思います。ある型が、可能なすべての型を一か所に事前宣言しなくても、別の型と同じ union の一部であるかのように自分自身を宣言できる方式です

    • malloc(sizeof(*node) + data_size); もパディングのせいで問題になる可能性があります。計算されたサイズが小さすぎることがあります

  • 反対です
    記事で言っている trick#0 で、C 方言全体を作ったことがあります。たとえばジェネリックなバイナリヒープは https://github.com/gritzko/librdx/blob/master/abc/HEAPx.h にあります
    構文はやや重いですが、最終的に得られるものが普通で予測可能、かつ最適化しやすい通常の C 構造体であるという大きな利点があります。コンパイラがドーナツのようにぺろりと平らげるコードです
    他の方式は結局 void* と実行時のメモリサイズ計算が必要になり、どうせマクロも定義しなければなりません

    • 著者です。バイナリヒープと連結リストではユースケースが違います。バイナリヒープは正しく保存するために投入するデータを読む必要がありますが、連結リストにはその必要がありません
      ジェネリックなバイナリヒープを使うなら、選択肢を別の形で比較検討していたかもしれません。脚注でもこの点に触れています
    • ヘッダー実装を好む理由は実際にいくつもあります。マクロ関数と違って、ヘッダーコードはデバッガでステップインでき、デバッガが参照できる型情報もより良いため、デバッグしやすくなります
      各インスタンスが単相化されるので、コンパイラ最適化の余地も大きく、可変サイズによる実行時コストを払わずに済みます。固定サイズなので、ジェネリック構造体をスタックに置くこともできます
      著者が挙げた問題のうち少なくとも 2 つは回避可能です。名前は単純な名前マングリング用マクロで、Bar_func(args…) から func(Bar)(args…) に変えられます。バイナリ肥大化は弱シンボルを使い、リンク時に翻訳単位間で共有される関数を重複排除させれば、ある程度減らせます
      ポインタ型のジェネリックコンテナには別の問題がありますが、typedef や型エイリアスで回避できます
      C では intrusive なデータ構造のほうが依然として便利ですが、デバッガで扱うのは苦痛です

  • 関数型のキャストは、要素ポインタ型、たとえば Foo* が void* と同じ表現を持つと仮定しているが、C標準はこれを保証していない。標準の用語では、この2つの型は「互換」ではない
    したがって、変換後の型で関数を呼び出すことは未定義動作である。ポインタ表現がたまたま同じでも、コンパイラのエイリアス解析にも影響する。関連して [0] も参考になる
    異なる引数型へ関数をキャストすることが、ジェネリック呼び出しの型安全性の核心のように見えるが、これが修正可能な問題なのかは分からない
    https://news.ycombinator.com/item?id=44421185

    • これは脚注で扱っている。キャストが型安全性の核心ではない。記事全体を読めばよい

  • 「ジェネリクスのあるC」が欲しいなら、ここまで回り道せずに単に C++ を使えばいいのではないか

    • 安全規制やその他の品質保証に縛られたレガシープロジェクトで働いているからだ。次のリリースどころか、10回先のリリースでも、C++へ移植した解決策を単純に出荷することはできない。だから可能になるまで、どうにか動かし続ける必要がある場合がある
      ただし新規プロジェクトではC++を使うよう標準と期待値を定めることができ、実際そうしており、特定の std をターゲットにするよう決めている
      Hacker Newsではこういう態度をかなりよく見るが、「腕を上げろ」に近い感じがする。ここにはもっと多くの文脈が必要だと思う
    • Cが使われる多くのユースケースでは、C++へ移行するほうがむしろより多くの回り道を必要とするからだ
    • C++を骨の髄まで嫌っている人たちがいて、そのためこういう種類の取り組みが出続けているのだ
      MicrosoftがLinuxや自由・オープンソースソフトウェアに新たに好意的になった後でさえ、「C++が未来」という立場から後退したのは本当に残念だった
      https://herbsutter.com/2012/05/03/reader-qa-what-about-vc-an...
      https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-...
      最近は政府やサイバー関連法規のため、MicrosoftでCとC++に新しい方針ができたので、それほど重要ではない
      https://azure.microsoft.com/en-us/blog/microsoft-azure-secur...
      https://blogs.windows.com/windowsexperience/2024/11/19/windo...
    • 本当の答えは、こちらのほうが面白いからだ
    • Cでいくつかの回り道だけで同じ結果を得られるなら、なぜC++を使うのか

  • 見事なトリックだ。すでに自分の実験用ライブラリでも使っている https://github.com/uecker/noplate/blob/main/src/list.h

    • これを知っていそうな人がいるとすればあなたのように思うが、intrusive データ構造にもこの方式を適用する方法は見えるだろうか？
      今のようにノードの中にデータを入れるのではなく、データの中にノード構造体を入れ、副次的に1つのオブジェクトを複数のコンテナに入れられるようにする方式だ

  • 「構造的に同一の型は、GCC 15と2025年後半のClangでは規則変更のおかげで同じ型と見なされる」という部分には注意が必要だ
    新しい規則で同じ型と見なされるのはタグ付き unionだけであり、構造が同じでタグも同じでなければならない
    List(T) マクロは、異なる T ごとに異なるタグを生成するよう変更する必要がある。単純な1語の型なら ## で簡単だが、char ポインタ、つまり文字列のように少し複雑になるだけで不可能になる
    もちろん List に使う前にすべての型を typedef するよう強制することはできるが、そうすると汎用性が大きく下がる

    typedef char *str;
    List(str) my_list_of_str;
    List(str) tokenize(str input) {...}

    • 「タグ付き unionだけが同じ型と見なされる」という話が理解できない。タグ付きユニオンは単なる設計パターンではないのか

  • 「何もせず型だけを保持するメンバー」の一般的な用語は type witness だと思う。だが、思ったより type witness 関連の文献はずっと少ない

    • 実際の変数の型としてはまったく使われない型変数があるときは、phantom type という似た用語がある
      主にHaskellで見かけたし、Scalaでも実際の型システムにはない型階層をまねるために使ったことがある
      ある意味では、この union トリックも補助型が実際にはまったく使われないので、phantom typeに似ている

  • Linuxカーネルで使われる方式もある。型ごとの構造体の中にリスト情報である struct list_head を埋め込む方式だ
    https://kernelnewbies.org/FAQ/LinkedLists

    • LIST_HEAD_INIT と INIT_LIST_HEAD という名前は紛らわしい

  • こうしなければならないなら、むしろ C++ テンプレートを直接使う

  • Dではこうすればよい

    struct ListNode(T) {
    ListNode* next;
    T data;
    }

    T!int node;

なぜ C プリプロセッサで苦労しなければならないのか？ プリプロセッサマクロを使うのは、仕上げ大工仕事で釘打ち機の代わりに金づちを使うようなもの。釘打ち機は10倍速く、毎回正確に釘を打ち込み、作業物に半月形のへこみも残さない。

  • この記事は C についてのもの。プロジェクトによっては C を必ず使わなければならない場合がある。
  • 金づちだけを使うのではなく、ポンチも併用すればよい。仕上げ釘を金づちで1/8インチほど残して打ち込み、その後ポンチで最後まで沈めればよい。