HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

Type Safe Generic Data Structures in C (danielchasehooper.com)

130 pointsby AlexeyBrin100 コメント

要約

この記事では、C言語でジェネリックデータ構造を型安全に実装する手法について解説しています。マクロ、void*、そしてユニオンと三項演算子(または__typeof__)を組み合わせたコンパイル時の型チェックを実現する最新のアプローチまで、段階的に説明されています。著者は、これらの概念を説明するために基本的な連結リストの実装例を示し、各アプローチのトレードオフを強調しています。

全文翻訳

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

フォローアップ記事をご覧ください:「Cにおける高速でポインタが安定した拡張可能な配列」

私は、まだ他では見たことのないテクニック1を使って、C言語で型安全なジェネリックデータ構造を書いています。それは、unionを使って型情報をジェネリックデータ構造に関連付けますが、それについては後述します。私の手法は、マップ、配列、二分木など、あらゆる種類のデータ構造に有効ですが、この記事では基本的なリンクリストを実装することでアイデアを説明します。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 });

// これはコンパイルされません。良いことです!
// list_prepend(&foo_list, 7);

list_for(item, &foo_list) {
    // `item`は`Foo *`型です
    printf("%i\n", item->value);
}

これを言及することさえためらいますが、私はそれが好きではありません2。しかし、この記事の最後にあるテクニックと比較する価値はあります。それは次のように機能します。ヘッダーファイルにデータ構造を書き、型にはマクロを使用し、その後、データ構造が使用される各型ごとにヘッダーファイルを複数回 #include します。

コードを見るにはクリック

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})

ジェネリックで型安全ではありますが、欠点があります。

  • 型と関数がマクロによって構築されるため、それらがどこで定義されているかを見つけるのが困難になる
  • コード補完がうまく機能しない可能性がある
  • 同じ関数のコピーでバイナリサイズとビルド時間を肥大化させる
  • list_prepend() ではなく、型でプレフィックスされた関数 (Foo_list_prepend() や int_list_prepend()) を使用する必要がある
ジェネリックレベル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 とその data を別々の割り当てにするのは、メモリとパフォーマンスの観点からは理想的ではありません。ノードごとに1回の割り当てで済むところを2回の割り当てが必要になり、data ポインタは不必要にメモリを消費し、リストをトラバースする際にノードごとに2回のキャッシュミスが発生する可能性が高くなります(一度ノードを取得し、一度そのデータを取得します)。これらの問題は、次の方法で解決できます。

ジェネリックレベル2: インラインストレージ

ノードのデータへのポインタを格納する代わりに、フレキシブル配列メンバーを使用して、ノード内にデータを格納できます。これを行うには、ノードとその格納する型の両方に十分な大きさの単一の割り当てを行います3。

typedef struct ListNode ListNode;
struct ListNode {
    ListNode *next;
    char data[]; // ここではパディング/アライメントの詳細を省略しています
};

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;
    *head = node;
    return node->data;
}

Foo *new_foo = list_alloc_front(&foo_list, sizeof(*new_foo));
new_foo->value = 5;
ジェネリックレベル3: 型チェック

皆さんが待ち望んでいた部分です。リストに間違った型のデータを追加しようとしたときに、コンパイラにエラーを出させる方法です。私が発見した方法は、パラメータ化された型を持つ payload メンバーを持つ union を使用することです。

#define List(type) union { 
    ListNode *head;
    type *payload;
}

List(Foo) foo_list = {0};
List(int) int_list = {0};

それはどのように役立つのでしょうか? ターナリ演算子を使用して、item パラメータがリストの payload と同じ型であることを強制できます。

// 注: 先頭のアンダースコアは関数名に追加されています。マクロのみが呼び出すためです。
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); // エラー!

マクロはアイテムサイズを渡す処理も行ってくれます! これは、間違った型をリストに追加したときに 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 は実行時には決して使用されず、コンパイル時の型情報のためだけに存在します。union を使用すると、payload はメモリを消費しません。

リストのペイロード型から void * をキャストする必要があるジェネリック関数を記述する場合、__typeof__() を使用できます。__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つの型が同じであることを保証するためにターナリ演算子を使用するのが気に入らない場合は、この記事の以前のバージョンでは別のテクニックを使用していました。

古いテクニックを読む

__typeof__(foo_list.payload) を使用して、リストが含む型を取得できます。list_prepend マクロを記述し、void * パラメータがリストの payload 型になるようにキャスト関数型を呼び出すようにします。

// 注: 先頭にアンダースコアを追加しました。
// 関数名には、マクロのみが呼び出すためです。
void _list_prepend(ListNode **head, 
                 void *data, 
                 size_t data_size);

#define list_prepend(list, item) \
    /* 関数型をキャスト */ \
    ((void (*)(ListNode **, \
               __typeof__((list)->payload), \
               size_t))_list_prepend) \
               /* 関数を呼び出す */ \
               (&((list)->head), item, sizeof(*(list)->payload))
               
List(Foo) *foo_list = NULL;
Bar bar = {5};
list_prepend(&foo_list, &bar); // エラー!

型キャスト関数ポインタを呼び出すことは、技術的には未定義の動作ですが、最新のプラットフォームをターゲットとする最新のコンパイラでコンパイルされる場合、実際には問題ありません。

古いコンパイラでのtypeof

__typeof__() はC23で標準の一部になるまで、オプションの拡張機能でした。Clangとgccは長い間これをサポートしてきましたが、一部のコンパイラ(19.39より前のmsvcなど)はそうではありませんでした。これらのコンパイラでこのテクニックを機能させるには、typeofの代わりにターナリ演算子を使用できます。

#define List(type) struct { 
    ListNode *head;
    type *payload;
}

#define list_prepend(list, item) \
    _list_prepend(&((list)->head), (1 ? (item) : (list)->payload), sizeof(*(list)->payload))

ペイロードに代入することで、型安全な戻り値も可能です。ただし、詳細は読者の演習とします。#

パラメータの渡し方

Cコンパイラの悩ましい点の1つは、これら2つの変数が同じ型であると見なされないことです。

List(Foo) a;
List(Foo) b = a; // エラー

void my_function(List(Foo) list);
my_function(a); // エラー: 型が互換性がありません

変数は同じ型定義を持っていますが、コンパイラはそれらが2つの異なる定義であるため、依然としてエラーを出します。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; // これはまだ機能します
結論

この手法は、複数の関連型を持つハッシュマップのような、あらゆる種類のデータ構造に使用できます。

typedef struct {
    ...
} MapInternal;

#define Map(key_type, value_type) union { 
    MapInternal map;
    key_type *key;
    value_type *value;
}

list_for マクロを含むサンプルソースコードは、このページの最下部にあるニュースレターに登録することでダウンロードできます。


  1. stb_ds.hは型安全なジェネリックデータ構造の例ですが、それが使用するテクニックはここで提示するものほど一般的ではありません。配列とマップはC配列を使用して実装されているため、これは機能します。コンパイラは、C配列への代入時に一部の型エラーを検出しますが、ジェネリック関数へのパラメータとして値が渡される時点ではありません。つまり、struct {int a; int b;} baz; STUBDS_ADDRESSOF(baz, 5) は正常にコンパイルされますが、実際には型エラーを期待するところです。↩︎
  2. 型固有のコード生成(同じソースから add_int と add_double を生成するなど)を必要とするジェネリック関数を書きたい場合、このオプションはより価値があります。ハッシュ関数など、型固有の動作を得るために、Cの機能を使って創造的になることができます。↩︎
  3. data メンバーに関連するアライメント、パディング、サイズ計算に関するいくつかの情報については省略していますが、それは全く別のトピックであり、もし不慣れであればどこかで調べて読むべきです。↩︎
  4. タグ名が同じ構造的に同一の型は、GCC 15および2025年後半のClangでは、ルール変更のおかげで同じ型と見なされるようになります。↩︎