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

Daniel Hooper Home ・ Articles ・ Projects ・ About ・ X.com Bluesky Mastodon RSS Type Safe Generic Data Structures in C June 25, 2025・8 minute read See my follow-up article: “A Fast, Growable Array With Stable Pointers in C” 私は、これまでどこでも見たことのないテクニックを使用して、C言語で型安全なジェネリックデータ構造を記述しています1。ユニオンを使用してジェネリックデータ構造に型情報を関連付けますが、それは後で説明します。私の方法は、マップ、配列、二分木など、あらゆる種類のデータ構造に適用できます。しかし、この記事では、基本的な連結リストを実装することでアイデアを説明します。Cでジェネリックを実装できることを知らない人も多いので、シンプルに始めて徐々に発展させていくことにしました。 typedef struct { int value; } Foo; List(int) int_list = {0}; list_prepend(&int_list, 3); List(Foo) foo_list = {0}; list_prepend(&foo_list, (Foo){ 5 }); list_prepend(&foo_list, (Foo){ 3 }); // this won't compile, which is good! // list_prepend(&foo_list, 7); list_for(item, &foo_list) { // `item` is of type `Foo *` printf("%i\n", item->value); } Generics level 0: Generic Headers 私はこのことを言及することに躊躇しますが、それは私がそれを好まないからです2。しかし、この記事の最後にあるテクニックと比較する価値はあります。それは次のように機能します。データ構造をヘッダーファイルに記述し、型にマクロを使用し、その後、データ構造が使用される各型に対してヘッダーファイルを複数回インクルードします。 Click to see the Code list.h #ifndef T #error "T must be defined before including this header" #endif #define _CONCAT(a, b) a##b #define CONCAT(a, b) _CONCAT(a, b) #define NODE_TYPE CONCAT(T, ListNode) #define PREPEND_FUNC CONCAT(T, _list_prepend) typedef struct NODE_TYPE NODE_TYPE; struct NODE_TYPE { NODE_TYPE *next; T data; }; void PREPEND_FUNC(NODE_TYPE **head, T data) { NODE_TYPE *node = malloc(sizeof(*node)); node->data = data; node->next = *head; *head = node; } #undef T #undef _CONCAT #undef CONCAT #undef NODE_TYPE #undef PREPEND_FUNC main.c typedef struct { int a; } Foo; typedef struct { char *str; double num; } Bar; #define T Foo #include "list.h" #define T Bar #include "list.h" FooListNode *foo_head = NULL; Foo_list_prepend(&foo_head, (Foo){1}) BarListNode *bar_head = NULL; Bar_list_prepend(&bar_head, (Bar){"hello", 5.4}) これはジェネリックで型安全ですが、欠点があります。 型と関数がどこで定義されているかを見つけにくい（マクロによって構築されるため） コード補完がうまく機能しない可能性がある 同じ関数のコピーでバイナリサイズとビルド時間が肥大化する 型プレフィックス付きの関数を使用する必要がある：Foo_list_prepend() と int_list_prepend() vs just list_prepend() Generics level 1: void * データ構造をジェネリックにするもう一つの方法は、void *を使用することです。これは型安全ではありませんが、後で説明します。 typedef struct ListNode ListNode; struct ListNode { ListNode *next; void *data; }; void list_prepend(ListNode **head, void *data) { ListNode *node = malloc(sizeof(*node)); node->data = data; node->next = *head; *head = node; } 注：mallocは慣れ親しんでいるため使用していますが、私はArenasを強く推奨します。それらについては、視聴または読むことができます。 ListNodeとそのデータを別々の割り当てにするのは、メモリとパフォーマンスの観点からは理想的ではありません。ノードごとに2回の割り当てが必要になり、データポインタは不要なメモリを消費し、リストをトラバースするたびにノードごとに2回のキャッシュミスが発生する可能性があります。1回は次のノードを取得するため、もう1回はそのデータの取得のためです。これらの問題を…で解決できます。 Generics level 2: Inline storage ノードのデータへのポインタを格納する代わりに、Flexible Array Memberを使用してノード内にデータを格納できます。これを行うには、ノードとそれが格納する型の両方に十分な大きさの単一の割り当てを行います3。 typedef struct ListNode ListNode; struct ListNode { ListNode *next; char data[]; // glossing over some padding/alignment details here }; void list_prepend(ListNode **head, void *data, size_t data_size) { ListNode *node = malloc(sizeof(*node) + data_size); memcpy(node->data, data, data_size); node->next = *head; *head = node; } void main() { ListNode *foo_list = NULL; Foo foo = {5}; list_prepend(&foo_list, &foo, sizeof(foo)); } これで、nextとdataの実際のコンテンツがメモリ上で隣接し、void *アプローチの問題が解決されました。残念ながら、memcpyを回避し、ノードのメモリを直接初期化したい場合は、list_alloc_front関数を使用できます。 void *list_alloc_front(ListNode **head, size_t data_size) { ListNode *node = malloc(sizeof(*node) + data_size); node->next = *head; return node->data; } Foo *new_foo = list_alloc_front(&foo_list, sizeof(*new_foo)); new_foo->value = 5; Generics level 3: Type Checking 皆さんが待ち望んでいた部分：コンパイラに、リストに間違った型を追加しようとしたときにエラーを発生させる方法です。私がこれを見つけた方法は、パラメータ化された型を持つペイロードメンバーを持つユニオンを使用することです。 #define List(type) union { \ ListNode *head; \ type *payload; \ } List(Foo) foo_list = {0}; List(int) int_list = {0}; これはどのように役立つのでしょうか？三項演算子を使用して、itemパラメータがリストのペイロードと同じ型であることを強制できます。 // Note: leading underscore add to the // function name since only the macro should call it void _list_prepend(ListNode **head, void *data, size_t data_size); #define list_prepend(list, item) \ _list_prepend(&((list)->head), \ (1 ? (item) : (list)->payload), \ sizeof(*(list)->payload)) List(Foo) *foo_list = NULL; Bar bar = {5, 6}; list_prepend(&foo_list, &bar); // error! マクロはアイテムサイズを渡す処理も私たちに代わって行ってくれます！これが、Clangがリストに間違った型を追加したときに生成するエラーです。 error: pointer type mismatch ('Foo *' and 'Bar *') [-Werror,-Wpointer-type-mismatch] 38 | list_prepend(&foo_list, &bar); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~ note: expanded from macro 'list_prepend' 15 | _list_prepend(&((list)->head), (1 ? (item) : (list)->payload), sizeof(*(list)->payload)) マクロは悪い評判を得ていますが、これはかなり理解しやすいと思います。注意点として、payloadは実行時には決して使用されず、コンパイル時の型情報のためだけに存在します。ユニオンを使用すると、payloadはメモリを消費しません。 ジェネリック関数が格納されたデータへのポインタを返す必要がある場合、__typeof__()を使用して戻り値をvoid *からデータ構造のペイロード型にキャストできます。__typeof__()は、3つの主要なCコンパイラ（clang、gcc、およびMSVC 19.39以降）すべてでサポートされています。 #define list_alloc_front(list) \ (__typeof__((list)->payload))_list_alloc_front(&(list)->head, sizeof(*(list)->payload)) void *_list_alloc_front(ListNode **head) {...} 何らかの理由で、2つの型が同じであることを保証するために三項演算子を使用するのが好きでない場合は、この記事の以前のバージョンでは異なるテクニックを使用していました。 Read the old technique __typeof__(foo_list.payload) を使用して、リストが格納している型を取得できます。リストのペイロード型にvoid *パラメータをキャストするキャスト関数型を呼び出す list_prepend マクロを記述します。 // Note: I added a leading underscore to the // function name since only the macro should call it void _list_prepend(ListNode **head, void *data, size_t data_size); #define list_prepend(list, item) \ /* cast function type */ \ ((void (*)(ListNode **, \ __typeof__((list)->payload), \ size_t))_list_prepend) \ /* call function */ \ (&((list)->head), item, sizeof(*(list)->payload)) List(Foo) *foo_list = NULL; Bar bar = {5}; list_prepend(&foo_list, &bar); // error! 型キャスト関数ポインタを呼び出すことは技術的には未定義の動作ですが、実際には最新のコンパイラが最新のプラットフォームをターゲットにコンパイルする場合、問題ありません。 old compilersでのtypeof __typeof__() はC23までオプションの拡張機能でしたが、C標準の一部になりました。Clangとgccは長い間これをサポートしてきましたが、一部のコンパイラ（19.39より前のMSVCなど）はサポートしていませんでした。これらのコンパイラでこのテクニックを機能させるには、typeofの代わりに三項演算子を使用できます。 #define List(type)