技术杂谈:如何以 C 语言撰写泛型程序?

PUBLISHED ON MAY 1, 2018

    泛型 (Generics) 是一种无类型的程序,主要是用在静态类型的语言上。撰写泛型程序的好处是同一个算法可以套件在不同类型上,减少重覆撰写相同算法但不同类的程序代码。由于泛型的好处,很多数据结构和算法的函式库会用泛型程序来实现,一些实例像是 C++ 的 STL (Standard Template Library)、Java (或 C#) 的 Collections 等。

    在 C11 以前的 C 不支援实质的泛型,所以在网络上宣称的 C 泛型程序并不是真的泛型程序,而是用其他语法特性仿真出来的;所以在学习这些「泛型」程序时要注意其手法和限制。一般来说,C 的拟泛型程序有以下三种实现方式:

    • 指向 void 的指针 (pointer to void)
    • 宏 (macro)
    • _Generic 叙述 (注:限 C11 后可用)

    本文将逐一介绍。

    指向 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) 本身是一种字串代换的程序代码,撰写时不需考虑变量的类型。利用这个特性,可以撰写一些拟泛型程序,像是以下的 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 the definition of `max`.
    #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 特有的语法。透过这个特性,我们可以将叙述 (statement) 转为表达式 (expression) 后回传,在该表达式内部的变量于宏展开后不会污染该区块外部的命名空间,算是这个语法的优点。此外,我们也运用到 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) 这样的非标准特性,读者可自行考量。

    _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 撰写泛型程序,仍然算是一个次等的选择,毕竟我们无法同时满足类型安全和减少重覆的程序代码数量。一般来说,我们想用较进阶的语法特性来写程序时,仍会优先考虑 C++ (或 Java),本文介绍的这些做法,有点在玩语法特性的味道,还是留在必要时才使用为佳。