[C 語言] 程式設計教學：使用 void 指標撰寫泛型程式

前言

泛型程式是一種無型別的程式，主要的好處在於可將同一套核心邏輯套用在不同型別的程式上。C 語言在 C11 前沒有原生的泛型，通常是用以下三種方法之一來模擬：

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

三種方法各有優缺點，我們在這裡有討論過，本文不重覆這些內容。本文的重點在展示一個用指向 void 的指標所做的擬泛型程式。

完整的程式碼略長，我們將其放在這裡，本文僅展示部分內容。

使用泛型函式的外部程式

我們先藉由外部程式來看如何使用這個泛型佇列：

#include <assert.h>
#include <stdio.h>
#include "integer.h"  // Home-made `int`-wrapping box class.
#include "queue.h"

#define ERROR(msg, ...) \
    fprintf(stderr, "(%s:%d) " msg "\n", __FILE__, __LINE__, ##__VA_ARGS__);

int main()
{
    // queue_t: NULL
    queue_t *queue = queue_new(int_copy, int_delete);
    if (!queue) {
        ERROR("Failed to allocate the queue");
        goto ERROR;
    }

    int_t *temp;

    // queue_t: 9 -> NULL
    temp = int_new(9);
    if (!temp) {
        ERROR("Failed to allocate the int object");
        goto ERROR;
    }
    queue_push_front(queue, temp);

    temp = (int_t *) queue_peek_front(queue);
    if (!(int_value(temp) == 9)) {
        ERROR("Wrong value");
        goto ERROR;
    }
    temp = (int_t *) queue_peek_rear(queue);
    if (!(int_value(temp) == 9)) {
        ERROR("Wrong value");
        goto ERROR;
    }

    // queue_t: 4 -> 9 -> NULL
    temp = int_new(4);
    if (!temp) {
        ERROR("Failed to allocate the int object");
        goto ERROR;
    }
    queue_push_front(queue, temp);

    temp = (int_t *) queue_peek_front(queue);
    if (!(int_value(temp) == 4)) {
        ERROR("Wrong value");
        goto ERROR;
    }
    temp = (int_t *) queue_peek_rear(queue);
    if (!(int_value(temp) == 9)) {
        ERROR("Wrong value");
        goto ERROR;
    }

    // queue_t: 4 -> 9 -> 5 -> NULL
    temp = int_new(5);
    if (!temp) {
        ERROR("Failed to allocate the int object");
        goto ERROR;
    }
    queue_push_rear(queue, temp);

    temp = (int_t *) queue_peek_front(queue);
    if (!(int_value(temp) == 4)) {
        ERROR("Wrong value");
        goto ERROR;
    }
    temp = (int_t *) queue_peek_rear(queue);
    if (!(int_value(temp) == 5)) {
        ERROR("Wrong value");
        goto ERROR;
    }

    // queue_t: 9 -> 5 -> NULL
    temp = (int_t *) queue_pop_front(queue);
    if (!temp) {
        ERROR("No valid value");
        goto ERROR;
    }
    if (!(int_value(temp) == 4)) {
        ERROR("Wrong value");
        goto ERROR;
    }
    int_delete(temp);

    temp = (int_t *) queue_peek_front(queue);
    if (!(int_value(temp) == 9)) {
        ERROR("Wrong value");
        goto ERROR;
    }
    temp = (int_t *) queue_peek_rear(queue);
    if (!(int_value(temp) == 5)) {
        ERROR("Wrong value");
        goto ERROR;
    }

    // queue_t: 9 -> NULL
    temp = (int_t *) queue_pop_rear(queue);
    if (!temp) {
        ERROR("No valid value");
        goto ERROR;
    }
    if (!(int_value(temp) == 5)) {
        ERROR("Wrong value");
        goto ERROR;
    }
    int_delete(temp);

    temp = (int_t *) queue_peek_front(queue);
    if (!(int_value(temp) == 9)) {
        ERROR("Wrong value");
        goto ERROR;
    }
    temp = (int_t *) queue_peek_rear(queue);
    if (!(int_value(temp) == 9)) {
        ERROR("Wrong value");
        goto ERROR;
    }

    // queue_t: NULL
    temp = (int_t *) queue_pop_rear(queue);
    if (!temp) {
        ERROR("No valid value");
        goto ERROR;
    }
    if (!(int_value(temp) == 9)) {
        ERROR("Wrong value");
        goto ERROR;
    }
    int_delete(temp);

    queue_delete(queue);

    return 0;

ERROR:
    if (queue)
        queue_delete(queue);

    return 1;
}

如果觀察這段程式碼，可能無法立即發現有泛型程式，不過，我們的佇列的確可以接收不同的指標型別。由於指向 void 的指標無法承接整數或其他的基礎型別，我們在這個使用一個簡易的 box class 來包裝整數；由於 C 語言沒有自動回收記憶體的機制，拋出整數物件後要記得手動釋放記憶體。

泛型函式的宣告

觀察一下本例的泛型佇列的宣告：

#pragma once

#include <stdbool.h>

typedef void * item_t;
typedef bool (*copy_fn) (void **, void *);
typedef void (*free_fn) (void *);

typedef struct queue_t queue_t;

queue_t* queue_new(copy_fn, free_fn);
bool queue_is_empty(queue_t *self);
item_t queue_peek_front(queue_t *self);
item_t queue_peek_rear(queue_t *self);
bool queue_push_front(queue_t *self, item_t data);
item_t queue_pop_front(queue_t *self);
bool queue_push_rear(queue_t *self, item_t data);
item_t queue_pop_rear(queue_t *self);
void queue_delete(void *self);

由此宣告可知我們的確沒有把型別寫死在參數中，而是可承接不同的型別。

泛型函式的內部實作

此佇列的「類別」宣告如下：

typedef struct node_t node_t;

struct node_t {
    item_t data;
    node_t *prev;
    node_t *next;
};

typedef struct queue_t queue_t;

struct queue_t {
    copy_fn item_copy;
    free_fn item_free;
    node_t *head;
    node_t *tail;
};

除了在資料結構中常見的 node_t 型別外，我們額外宣告 copy_fn 和 free_fn 兩個函式型別，因為我們無法預先知道如何釋放該型別的記憶體，要用函式庫使用者提供。

以下是將資料推入佇列前端的程式碼：

bool queue_push_front(queue_t *self, item_t data)
{
    node_t *node = node_new(data);
    if (!node)
        return false;

    if (!(self->head)) {
        self->head = node;
        self->tail = node;
        return true;
    }

    node->next = self->head;
    self->head->prev = node;
    self->head = node;

    return true;
}

其實和一般的佇列程式差不多。

再看一下將資料移出佇列前端的程式碼：

item_t queue_pop_front(queue_t *self)
{
    assert(!queue_is_empty(self));

    if (self->head == self->tail) {
        item_t popped;
        self->item_copy(&popped, self->head->data);

        self->item_free(self->head->data);
        free(self->head);
        self->head = NULL;
        self->tail = NULL;

        return popped;
    }

    node_t *curr = self->head;
    item_t popped;
    self->item_copy(&popped, curr->data);

    self->head = self->head->next;
    self->item_free(curr->data);
    free(curr);

    return popped;
}

可以發現我們在此處用到額外的函式，一個用來拷貝物件，一個用來釋放重覆的物件。對於基礎型別來說，這些動作都可以省下來；但對指標型別來說，就要考慮如何處理指標指向的物件。此處我們參考 Rust 的做法，將物件複製一份後傳出。

最後來看釋放佇列的程式碼：

void queue_delete(void *self)
{
    if (!self)
        return;

    free_fn fn = ((queue_t *) self)->item_free;
    node_t *curr = ((queue_t *) self)->head;
    node_t *temp = NULL;

    while (curr) {
        temp = curr;
        curr = curr->next;

        (*fn)(temp->data);
        free(temp);
    }

    free(self);
}

同樣地，在釋放節點內的物件時，會用到額外的 item_free 函式，這函式無法預先得知，需由函式庫使用者提供。

結語

由本例可知，在 C 語言中，的確可以模擬泛型程式，但會比一般的高階語言來得麻煩一些，像是要為基礎型態額外宣告 boxing 物件。

此外，這樣的程式不具有型別安全，因為所有傳入的物件的型別都是指向 void 的指標。雖然我們可以達到一些泛型的特性，但要不要這樣做就留給讀者自行思考。