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

C 語言泛型
Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email

前言

泛型程式是一種無型別的程式,主要的好處在於可將同一套核心邏輯套用在不同型別的程式上。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_fnfree_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 的指標。雖然我們可以達到一些泛型的特性,但要不要這樣做就留給讀者自行思考。

關於作者

身為資訊領域碩士,美思認為開發應用程式的目的是為社會帶來價值。如果在這個過程中該軟體能成為永續經營的項目,那就是開發者和使用者雙贏的局面。

美思喜歡用開源技術來解決各式各樣的問題,但必要時對專有技術也不排斥。閒暇之餘,美思將所學寫成文章,放在這個網站上和大家分享。