C 言語で型安全なジェネリックデータ構造を構築する：ユニオンを活用した手法

C 言語において、安定したポインタを持ちながら高速かつ伸縮可能な汎用（ジェネリック）データ構造を実装する方法について解説します。本稿では、ユニオンを活用して汎用データ構造に型情報を付与する独自の手法を取り上げます。このアプローチはマップ、配列、二木など多様なデータ構造に応用可能ですが、今回は具体的な実装例として基本的なリンクリストに焦点を当てて説明します。

多くの人が C 言語でジェネリックプログラミングが難しいと認識していますが、実は型安全な汎用化が可能です。ここでは単純な例から始め、徐々に高度な内容へと深掘りしていきます。

従来の手法との比較

独自の手法と比較対象として挙げられるのが、ヘッダファイルに構造体を定義し、マクロで型を指定して複数回

#include

従来手法のサンプル（マクロによる重複定義）

この手法は以下の動作原理を持ちます：

• ヘッダファイルにデータ構造を記述する
• マクロによって型を定義する（例：

  #define T Foo

  ）
• そのヘッダファイルを必要な型ごとに複数回

  #include

  する

list.h の実装例

#ifndef T
#error "このヘッダを含める前に、T が定義されている必要があります"
#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;
}

// Cleanup: 汚染防止のためマクロを無効化
#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;
BarListNode *bar_head = NULL;

従来手法の課題

• 理解困難: マクロによる実装のため、型の定義場所や関数の実装箇所が把握しにくい
• コード補完の不具合: IDE の IntelliSense などが正しく機能しない可能性が高い
• バイナリの肥大化: 同じ関数を各型ごとに複製するため、ファイルサイズ増大とビルド時間延長を招く
• 冗長な命名:

  Foo_list_prepend()

  や

  int_list_prepend()

  といった長い関数名が必要になり、簡潔さがない

ジェネリックの実装レベルごとのアプローチ

レベル 1: 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;
}

改善すべき点:

• メモリ効率が悪い（ノードとデータを別々に割り当てている）
• データポインタ自体がメモリを消費する
• キャッシュミスが発生しやすい（リスト走査時に 2 回以上のメモリアクセスが必要）

注記: ここでは

malloc

を使用していますが、実際には**アリーナ（Arena）**の使用を強く推奨します。

Flexbile Array Member を用いたインラインストレージ（レベル 2）

ノード内のメモリに直接データを格納することで、メモリアクセス効率を向上させます。

typedef struct ListNode ListNode;
struct ListNode {
    ListNode *next;
    char data[]; // Flexible Array Member: パディング・整列の処理は省略
};

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

// メモリ初期化例（memcpy 回避）
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; // ダミーポインタとして返す（実際のデータ構造に応じて変更）
}

メリット:

• next

  ポインタとデータがメモリ上で隣接している
• キャッシュヒット率の向上

欠点: データのサイズを明示的に渡す必要があるため不便。

レベル 3: ユニオンによる型チェック（最終的な手法）

コンパイラが不適切な型の代入を検知する、完全な型安全を実現するための手法です。ユニオンを利用して、実用上はメモリを消費しないまま型情報を保持します。

データ構造の定義

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

• head

  : リンクリストの先頭ポインタ

• payload

  : そのリストに格納される型（例：

  Foo*

  、

  int*

  ）

実装サンプル

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

マクロによる安全な追加機能

三項演算子を用いて、渡されたデータがリストのペイロード型と一致することを強制します。

// 内部関数（マクロから呼ばれるもの）
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: pointer type mismatch ('Foo *' and 'Bar *') [-Werror,-Wpointer-type-mismatch]

機能の補足

• メモリ効率: ユニオンの特性上、

  payload

  はコンパイル時情報のみであり、実行時はメモリを消費しません。
• 自動サイズ管理: マクロ内で

  sizeof(*(list)->payload)

  を計算し、自動的に渡します。

型安全なリターン値の取得

汎用関数から正しい型のポインタを返す場合、

__typeof__()

// 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) {...}

旧コンパイラや三項演算子への対応

__typeof__()

#define list_prepend(list, item) \
    /* 型キャスト関数ポインタ */ \
    ((void (*)(ListNode **, \
               __typeof__((list)->payload), \
               size_t))_list_prepend)  \
               (&((list)->head), item, sizeof(*(list)->payload)) 

注意: これらの手法は、現代のコンパイラでコンパイルされる限り未定義動作の問題はなく、安全に使用可能です。

C23 標準化後の対応 (

typeof

)

C23 標準では

__typeof__

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

型派生の問題と解決策（typedef）

C コンパイラは、同じ定義であっても変数ごとに異なる「型」とみなす傾向があります。

問題例

List(Foo) a;
List(Foo) b = a; // エラー：互換性のない型として処理される

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; 

まとめと応用

ハッシュマップへの拡張

この手法は、ハッシュマップのような複雑なデータ構造にも適用可能です。内部実装とキー・値型をユニオンで分離します。

typedef struct {
    // ... 内部実装（HashMap, Tree など）...
} MapInternal;

// キー型 K と、値型 V を持つマップ定義
#define Map(key_type, value_type) union { \
    MapInternal map; \
    key_type *key; \
    value_type *value; \
}

サンプルコードの入手

• リスト処理マクロ

  list_for

  などを含む完全なソースコードは、ニュースレターの登録を通じてダウンロード可能です。

このユニオンを活用した手法は、C 言語において型安全かつ汎用的なデータ構造を実装するための強力なアプローチです。