[技術雜談] 如何以 C 語言撰寫泛型程式？

前言

泛型 (Generics) 是一種無型別的程式，主要是用在靜態型別的語言上。撰寫泛型程式的好處是同一個演算法可以套用在不同型別上，減少重覆撰寫相同演算法但不同類別的程式碼。

由於泛型的好處，很多資料結構和演算法的函式庫會用泛型程式來實作，一些實例像是 C++ 的 STL (Standard Template Library)、Java (或 C#) 的 Collections 等。

C 在 C11 前沒有原生的泛型特性，所以我們來看各種模擬泛型的手法。

在 C 語言中實踐泛型的方式

在 C11 以前的 C 不支援實質的泛型，所以在網路上宣稱的 C 泛型程式並不是真的泛型程式，而是用其他語法特性模擬出來的，包括本文在內。

所以在學習這些「泛型」程式時要注意其手法和限制。一般來說，C 的擬泛型程式有以下三種實作方式：

• 指向 void 的指標 (pointer to void)
• 巨集 (macro)
• _Generic 敘述 (C11)

本文將逐一介紹。

使用指向 void 的指標

指向 void 的指標是最常見的手法，利用 void * 可搭配任意型別的指標的特性來模擬泛型。

這種手法在一些中階的教材會看到，像是以下的宣告就用到這個特性：

// Excerpt.

// Some generic type implemented in pointer to void.
typedef void * item_p;

typedef struct node Node;

// Some generic node.
struct node {
    item_p data;
    Node *prev;
    Node *next;
};

typedef struct list List;

struct list {
    Node *head;
    Node *tail;
};

// Some generic function.
void list_push(List *self, item_p data);

比起巨集來說，使用 void * 的限制在於處理的資料一定要是指標型別，通用性沒那麼好。然而，比起巨集來說，用這種手法撰寫程式碼會比較安全，而且實作上也比較簡單。若情境許可，採用此種方式較佳。

使用巨集 (Macro)

巨集 (macro) 本身是一種字串代換的小型語言，和 C 語言共生。撰寫巨集時時不需考慮變數的型別，只要符合巨集的規則即可。利用這個特性，可以撰寫一些擬泛型程式，像是以下的 max 「函式」：

#include <assert.h>

// Generic max implemented in macro.
#define max(a, b) (((a) > (b)) ? (a) : (b))

int main(void) {
    // max on `int`
    assert(max(3, 5) == 5);

    // max on `double`
    assert(max(3.7, 2.9) == 3.7);

    return 0;
}

乍看之下，max 部分的程式碼好像是函式呼叫，但實際上是透過字串代換更替成等效的 C 程式碼。像是 max(3, 5) 在巨集展開後變成以下程式碼：

// Excerpt.
(((3) > (5)) ? (3) : (5))

而 max(3.7, 2.9) 展開後變成以下程式碼：

// Excerpt.
(((3.7) > (2.9)) ? (3.7) : (2.9))

在使用和撰寫巨集「函式」時要謹記這些巨集其實不是什麼函式，而是透過字串代換的方式展開後得到等效的程式碼。因此，巨集比起一般的 C 程式碼來說，除錯較為困難，因為多一層轉換的步驟。此外，巨集也缺乏一般 C 程式碼的型別安全等優點，有時會出現一些奇奇怪怪的 bug。

我們稍微改寫上述程式而成一個新的範例：

#include <assert.h>
#include "max.h"

int main()
{
    // Definition: type max(type, size, value, ...)
    // max on `int`
    assert(max(int, 5, 2, 1, 0, 4, -1) == 4);

    // max on `double`
    assert(max(double, 4, 2.3, 3.7, 1.9, 5.2) == 5.2);

    return 0;
}

這個範例已經有一些泛型程式的味道在裡面。在這個新版的 max 「函式」中，第一個參數是型別，第二個參數是該串數字的長度，第三個以後的參數則是要進行比較的一串數字。在真正有泛型程式的語言中，也是由外部程式提供型別的資訊，我們的泛型「函式」看來的確有幾分神似。

接著，我們來看新版 max 「函式」的實作，雖然這個巨集行數很短，卻用上數個巨集的特性，我們會於下文說明：

#define max(type, sz, value, ...) ({ \
        max_declare(type) \
        type out = max_##type((sz), (value), ##__VA_ARGS__); \
        out; \
    })

max_declare 是另一個巨集，這個巨集會宣告一個函式，我們待會兒會看到其實作。

我們為什麼要再額外用另一個巨集做出函式宣告呢？因為在 C 的巨集裡無法直接處理不定數量參數 (varargs)，只能將該參數透過 __VA_ARGS__ 再帶到一個函式呼叫裡。我們我們這個巨集就使用另一個巨集動態地做出一個函式，然後將不定參數帶進該函式中進行函式呼叫，最後將結果回傳給外部程式。

讀者可發現這個巨集的內容用 ({ ... }) 包起來，這並不是標準 C 的語法，而是 GCC extension 中的 statement expression，這是 GCC 特有的語法。透過這個特性，我們可以將敘述轉為表達式後回傳，在該表達式內部的變數於巨集展開後不會汙染該區塊外部的命名空間，算是這個語法的優點。

此外，我們也運用到 nested function 的功能，這是另一個 GCC extension；要不然在區塊內宣告函式是非法的 C 程式碼。

我們來看 max_declare 的實作：

#define max_declare(type) \
    type max_##type(size_t sz, type value, ...) \
    { \
        type out = value; \
        va_list args; \
        va_start(args, value); \
        type temp; \
        for (size_t i = 1; i < sz; i++) { \
            temp = va_arg(args, type); \
            out = temp > out ? temp : out; \
        } \
        return out; \
    }

由於這個巨集展開後會變成一個函式呼叫，所以我們可以在這裡處理不定數量參數。此處這裡我們使用 stdarg.h 函式庫裡的函式來處理不定數量參數。

經筆者實測，本例在 GCC 可以成功編譯和執行，但在 clang 則會引發錯誤。由於 GCC 是相當普遍的編譯器，是否要利用 (exploit) 這樣的非標準特性，讀者可自行考量。

使用泛型型別敘述 (C11)

_Generic 則提供了真正的型別安全的 (type-safe) 泛型。以下是一個用 _Generic 實作泛型的向量 (Vector)：

// Excerpt.

typedef struct vector Vector;

Vector * vector_add_vec_vec(Vector *u, Vector *v);
Vector * vector_add_vec_scalar(Vector *v, double scalar);
Vector * vector_add_scalar_vec(double scalar, Vector *v);

#define vector_add(a, b) _Generic((a), \
    Vector *: _Generic((b), \
        Vector *: vector_add_vec_vec, \
        double: vector_add_vec_scalar), \
    double: vector_add_scalar_vec)(a, b)

讀者不需要在意 Vector 內部如何實作，重點在 vector_add 巨集，透過這個巨集，我們傳入不同型別的參數時，_Generic 敘述會根據傳入參數的型別挑選合適的函式，藉此達成泛型的特性。

以兩個 Vector 物件相加的例子如下：

// Func Def: vector_init(size, value, ...)
// Initialize two Vectors.
Vector *u = vector_init(3, 1.0, 2.0, 3.0);
Vector *v = vector_init(3, 2.0, 3.0, 4.0);

// Polymorphic call: vec + vec.
Vector *t = vector_add(u, v);

以一個 Vector 物件和一個純量 (scalar) 相加的實例如下：

// Func Def: vector_init(size, value, ...)
// Initialize one Vector.
Vector *u = vector_init(3, 1.0, 2.0, 3.0);

// Polymorphic call: scalar + vec.
Vector *v = vector_add(0.5, u);

其實 _Generic 敘述就像是一個在編譯期的 switch 敘述，透過該特性選取合適的函式來使用，藉以達成泛型的特型。雖然要多寫許多函式來滿足泛型呼叫，但 _Generic 的確有滿足型別安全的特點。

附註

本文算是通論，所以內容較簡短。筆者另外撰寫一些以 C 語言實作泛型程式的文章：

• 使用void 指標
• 使用前置處理器
• 使用泛型型別敘述
• 使用外部模板語言 (非主流)

有需要的讀者可以參考。

結語

透過本文，我們可以發現，使用 C 撰寫泛型程式，仍然算是一個次等的選擇，畢竟我們無法同時滿足型別安全和減少重覆的程式碼數量。一般來說，我們想用較進階的語法特性來寫程式時，仍會優先考慮 C++ (或 Java)，本文介紹的這些做法，有點在玩語法特性的味道，還是留在必要時才使用為佳。